From b0528af48546cdfe3f2be3c126732eaff8933fe2 Mon Sep 17 00:00:00 2001 From: epetrich Date: Mon, 6 Sep 2004 00:06:24 +0000 Subject: [PATCH] * src/port.h, * src/mcs51/main.c, * src/ds390/main.c, * src/z80/main.c, * src/hc08/main.c, * src/pic/main.c, * src/pic16/main.c, * src/avr/main.c, * src/xa51/main.c * src/SDCCicode.c (geniCodeJumpTable): Better logic to determine if a a jump table is the best form for a switch statement, including automatic insertion of missing cases to make the case range continuous. Developed in collaboration with Frieder Ferlemann. git-svn-id: https://sdcc.svn.sourceforge.net/svnroot/sdcc/trunk/sdcc@3475 4a8a32a2-be11-0410-ad9d-d568d2c75423 --- ChangeLog | 16 +++++++ src/SDCCicode.c | 122 +++++++++++++++++++++++++++++++++++------------ src/avr/main.c | 10 ++++ src/ds390/main.c | 24 ++++++++++ src/hc08/main.c | 8 ++++ src/mcs51/main.c | 8 ++++ src/pic/main.c | 10 ++++ src/pic16/main.c | 10 ++++ src/port.h | 13 ++++- src/xa51/main.c | 10 ++++ src/z80/main.c | 20 ++++++++ 11 files changed, 219 insertions(+), 32 deletions(-) diff --git a/ChangeLog b/ChangeLog index 437444f2..45db80a0 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,19 @@ +2004-09-06 Erik Petrich + + * src/port.h, + * src/mcs51/main.c, + * src/ds390/main.c, + * src/z80/main.c, + * src/hc08/main.c, + * src/pic/main.c, + * src/pic16/main.c, + * src/avr/main.c, + * src/xa51/main.c + * src/SDCCicode.c (geniCodeJumpTable): Better logic to determine if a + a jump table is the best form for a switch statement, including + automatic insertion of missing cases to make the case range + continuous. Developed in collaboration with Frieder Ferlemann. + 2004-09-02 Erik Petrich * src/hc08/ralloc.c (canDefAccResult): multi-byte shift is unsafe for diff --git a/src/SDCCicode.c b/src/SDCCicode.c index 34002152..b46ab976 100644 --- a/src/SDCCicode.c +++ b/src/SDCCicode.c @@ -3471,7 +3471,8 @@ exit: int geniCodeJumpTable (operand * cond, value * caseVals, ast * tree) { - int min = 0, max = 0, t, cnt = 0; + int min, max, cnt = 1; + int i, t; value *vch; iCode *ic; operand *boundary; @@ -3479,6 +3480,10 @@ geniCodeJumpTable (operand * cond, value * caseVals, ast * tree) set *labels = NULL; int needRangeCheck = !optimize.noJTabBoundary || tree->values.switchVals.swDefault; + sym_link *cetype = getSpec (operandType (cond)); + int sizeofMinCost, sizeofMaxCost; + int sizeofMatchJump, sizeofJumpTable; + int sizeIndex; if (!tree || !caseVals) return 0; @@ -3486,48 +3491,104 @@ geniCodeJumpTable (operand * cond, value * caseVals, ast * tree) /* the criteria for creating a jump table is */ /* all integer numbers between the maximum & minimum must */ /* be present , the maximum value should not exceed 255 */ - min = max = (int) floatFromVal (vch = caseVals); - SNPRINTF (buffer, sizeof(buffer), - "_case_%d_%d", - tree->values.switchVals.swNum, - min); - addSet (&labels, newiTempLabel (buffer)); - - /* if there is only one case value then no need */ - if (!(vch = vch->next)) - return 0; - - while (vch) + /* If not all integer numbers are present the algorithm */ + /* inserts jumps to the default label for the missing numbers */ + /* and decides later whether it is worth it */ + min = (int) floatFromVal (vch = caseVals); + + while (vch->next) { - if (((t = (int) floatFromVal (vch)) - max) != 1) - return 0; - SNPRINTF (buffer, sizeof(buffer), - "_case_%d_%d", - tree->values.switchVals.swNum, - t); - addSet (&labels, newiTempLabel (buffer)); - max = t; cnt++; vch = vch->next; } - - /* if the number of case statements <= 2 then */ - /* it is not economical to create the jump table */ - /* since two compares are needed for boundary conditions */ - if ((needRangeCheck && cnt <= 2) || max > (255 / 3)) + max = (int) floatFromVal (vch); + + /* Exit if the range is too large to handle with a jump table. */ + if (1 + max - min > port->jumptableCost.maxCount) return 0; + + switch (getSize (operandType (cond))) + { + case 1: sizeIndex = 0; break; + case 2: sizeIndex = 1; break; + case 4: sizeIndex = 2; break; + default: return 0; + } + + /* Compute the size cost of the range check and subtraction. */ + sizeofMinCost = 0; + sizeofMaxCost = 0; + if (needRangeCheck) + { + if (!(min==0 && IS_UNSIGNED (cetype))) + sizeofMinCost = port->jumptableCost.sizeofRangeCompare[sizeIndex]; + sizeofMaxCost = port->jumptableCost.sizeofRangeCompare[sizeIndex]; + } + if (min) + sizeofMinCost += port->jumptableCost.sizeofSubtract; + + /* If the size cost of handling a non-zero minimum exceeds the */ + /* cost of extending the range down to zero, then it might be */ + /* better to extend the range to zero. */ + if (min > 0 && sizeofMinCost >= (min * port->jumptableCost.sizeofElement)) + { + /* Only extend the jump table if it would still be manageable. */ + if (1 + max <= port->jumptableCost.maxCount) + min = 0; + } + + /* Compute the total size cost of a jump table. */ + sizeofJumpTable = (1 + max - min) * port->jumptableCost.sizeofElement + + port->jumptableCost.sizeofDispatch + + sizeofMinCost + sizeofMaxCost; + /* Compute the total size cost of a match & jump sequence */ + sizeofMatchJump = cnt * port->jumptableCost.sizeofMatchJump[sizeIndex]; + + /* If the size cost of the jump table is uneconomical then exit */ + if (sizeofMatchJump < sizeofJumpTable) + return 0; + + /* The jump table is preferable. */ + + /* First, a label for the default or missing cases. */ if (tree->values.switchVals.swDefault) { - SNPRINTF (buffer, sizeof(buffer), "_default_%d", tree->values.switchVals.swNum); + SNPRINTF (buffer, sizeof(buffer), + "_default_%d", + tree->values.switchVals.swNum); } else { - SNPRINTF (buffer, sizeof(buffer), "_swBrk_%d", tree->values.switchVals.swNum); + SNPRINTF (buffer, sizeof(buffer), + "_swBrk_%d", + tree->values.switchVals.swNum); } - - falseLabel = newiTempLabel (buffer); + + /* Build the list of labels for the jump table. */ + vch = caseVals; + t = (int) floatFromVal (vch); + for (i=min; i<=max; i++) + { + if (vch && t==i) + { + /* Explicit case: make a new label for it. */ + SNPRINTF (buffer, sizeof(buffer), + "_case_%d_%d", + tree->values.switchVals.swNum, + i); + addSet (&labels, newiTempLabel (buffer)); + vch = vch->next; + if (vch) + t = (int) floatFromVal (vch); + } + else + { + /* Implicit case: use the default label. */ + addSet (&labels, falseLabel); + } + } /* If cond is volatile, it might change after the boundary */ /* conditions are tested to an out of bounds value, causing */ @@ -3546,7 +3607,6 @@ geniCodeJumpTable (operand * cond, value * caseVals, ast * tree) cond = newcond; } - /* so we can create a jumptable */ /* first we rule out the boundary conditions */ /* if only optimization says so */ if (needRangeCheck) diff --git a/src/avr/main.c b/src/avr/main.c index 9f5a4fcd..e09ba53a 100644 --- a/src/avr/main.c +++ b/src/avr/main.c @@ -230,6 +230,16 @@ PORT avr_port = { { avr_emitDebuggerSymbol }, + { + 255/3, /* maxCount */ + 3, /* sizeofElement */ + /* The rest of these costs are bogus. They approximate */ + /* the behavior of src/SDCCicode.c 1.207 and earlier. */ + {4,4,4}, /* sizeofMatchJump[] */ + {0,0,0}, /* sizeofRangeCompare[] */ + 0, /* sizeofSubtract */ + 3, /* sizeofDispatch */ + }, "_", _avr_init, _avr_parseOptions, diff --git a/src/ds390/main.c b/src/ds390/main.c index 65af1a65..a1ff41aa 100644 --- a/src/ds390/main.c +++ b/src/ds390/main.c @@ -870,6 +870,14 @@ PORT ds390_port = { ds390_emitDebuggerSymbol }, + { + 255/4, /* maxCount */ + 4, /* sizeofElement */ + {8,12,20}, /* sizeofMatchJump[] */ + {10,14,22}, /* sizeofRangeCompare[] */ + 4, /* sizeofSubtract */ + 7, /* sizeofDispatch */ + }, "_", _ds390_init, _ds390_parseOptions, @@ -1173,6 +1181,14 @@ PORT tininative_port = { ds390_emitDebuggerSymbol }, + { + 255/4, /* maxCount */ + 4, /* sizeofElement */ + {8,12,20}, /* sizeofMatchJump[] */ + {10,14,22}, /* sizeofRangeCompare[] */ + 4, /* sizeofSubtract */ + 7, /* sizeofDispatch */ + }, "", _tininative_init, _ds390_parseOptions, @@ -1391,6 +1407,14 @@ PORT ds400_port = { ds390_emitDebuggerSymbol }, + { + 255/4, /* maxCount */ + 4, /* sizeofElement */ + {8,12,20}, /* sizeofMatchJump[] */ + {10,14,22}, /* sizeofRangeCompare[] */ + 4, /* sizeofSubtract */ + 7, /* sizeofDispatch */ + }, "_", _ds390_init, _ds390_parseOptions, diff --git a/src/hc08/main.c b/src/hc08/main.c index 7a5d1730..f586fc63 100644 --- a/src/hc08/main.c +++ b/src/hc08/main.c @@ -463,6 +463,14 @@ PORT hc08_port = 1, /* offsetSP */ }, }, + { + 255/3, /* maxCount */ + 3, /* sizeofElement */ + {8,16,32}, /* sizeofMatchJump[] */ + {8,16,32}, /* sizeofRangeCompare[] */ + 5, /* sizeofSubtract */ + 11, /* sizeofDispatch */ + }, "_", _hc08_init, _hc08_parseOptions, diff --git a/src/mcs51/main.c b/src/mcs51/main.c index bfdd26d9..f43f4174 100644 --- a/src/mcs51/main.c +++ b/src/mcs51/main.c @@ -715,6 +715,14 @@ PORT mcs51_port = { mcs51_emitDebuggerSymbol }, + { + 255/3, /* maxCount */ + 3, /* sizeofElement */ + {6,9,15}, /* sizeofMatchJump[] */ + {9,18,36}, /* sizeofRangeCompare[] */ + 4, /* sizeofSubtract */ + 7, /* sizeofDispatch */ + }, "_", _mcs51_init, _mcs51_parseOptions, diff --git a/src/pic/main.c b/src/pic/main.c index 47984a99..a088adbb 100644 --- a/src/pic/main.c +++ b/src/pic/main.c @@ -460,6 +460,16 @@ PORT pic_port = { pic14_emitDebuggerSymbol }, + { + 255/3, /* maxCount */ + 3, /* sizeofElement */ + /* The rest of these costs are bogus. They approximate */ + /* the behavior of src/SDCCicode.c 1.207 and earlier. */ + {4,4,4}, /* sizeofMatchJump[] */ + {0,0,0}, /* sizeofRangeCompare[] */ + 0, /* sizeofSubtract */ + 3, /* sizeofDispatch */ + }, "_", _pic14_init, _pic14_parseOptions, diff --git a/src/pic16/main.c b/src/pic16/main.c index b739f342..67cc81e2 100644 --- a/src/pic16/main.c +++ b/src/pic16/main.c @@ -870,6 +870,16 @@ PORT pic16_port = { pic16_emitDebuggerSymbol }, + { + 255/3, /* maxCount */ + 3, /* sizeofElement */ + /* The rest of these costs are bogus. They approximate */ + /* the behavior of src/SDCCicode.c 1.207 and earlier. */ + {4,4,4}, /* sizeofMatchJump[] */ + {0,0,0}, /* sizeofRangeCompare[] */ + 0, /* sizeofSubtract */ + 3, /* sizeofDispatch */ + }, "_", _pic16_init, _pic16_parseOptions, diff --git a/src/port.h b/src/port.h index 605ddf51..778d67b4 100644 --- a/src/port.h +++ b/src/port.h @@ -212,7 +212,18 @@ typedef struct dwarf; } debugger; - + + struct + { + int maxCount; + int sizeofElement; + int sizeofMatchJump[3]; + int sizeofRangeCompare[3]; + int sizeofSubtract; + int sizeofDispatch; + } + jumptableCost; + /** Prefix to add to a C function (eg "_") */ const char *fun_prefix; diff --git a/src/xa51/main.c b/src/xa51/main.c index 9d2f9ba9..26b52112 100755 --- a/src/xa51/main.c +++ b/src/xa51/main.c @@ -304,6 +304,16 @@ PORT xa51_port = { xa51_emitDebuggerSymbol }, + { + 255/3, /* maxCount */ + 3, /* sizeofElement */ + /* The rest of these costs are bogus. They approximate */ + /* the behavior of src/SDCCicode.c 1.207 and earlier. */ + {4,4,4}, /* sizeofMatchJump[] */ + {0,0,0}, /* sizeofRangeCompare[] */ + 0, /* sizeofSubtract */ + 3, /* sizeofDispatch */ + }, "_", _xa51_init, _xa51_parseOptions, diff --git a/src/z80/main.c b/src/z80/main.c index 99a518dd..057d01d5 100644 --- a/src/z80/main.c +++ b/src/z80/main.c @@ -627,6 +627,16 @@ PORT z80_port = { z80_emitDebuggerSymbol }, + { + 255, /* maxCount */ + 3, /* sizeofElement */ + /* The rest of these costs are bogus. They approximate */ + /* the behavior of src/SDCCicode.c 1.207 and earlier. */ + {4,4,4}, /* sizeofMatchJump[] */ + {0,0,0}, /* sizeofRangeCompare[] */ + 0, /* sizeofSubtract */ + 3, /* sizeofDispatch */ + }, "_", _z80_init, _parseOptions, @@ -732,6 +742,16 @@ PORT gbz80_port = { z80_emitDebuggerSymbol }, + { + 255, /* maxCount */ + 3, /* sizeofElement */ + /* The rest of these costs are bogus. They approximate */ + /* the behavior of src/SDCCicode.c 1.207 and earlier. */ + {4,4,4}, /* sizeofMatchJump[] */ + {0,0,0}, /* sizeofRangeCompare[] */ + 0, /* sizeofSubtract */ + 3, /* sizeofDispatch */ + }, "_", _gbz80_init, _parseOptions, -- 2.30.2