* 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

diff --git a/ChangeLog b/ChangeLog
index 437444f2bdd1ed54b9b8084d8e6aa54f2a06583d..45db80a0f43c1dd60a1e755a388ae437ce50bd2e 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,19 @@
+2004-09-06 Erik Petrich <epetrich AT ivorytower.norman.ok.us>
+
+       * 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 <epetrich AT ivorytower.norman.ok.us>
 
        * src/hc08/ralloc.c (canDefAccResult): multi-byte shift is unsafe for

diff --git a/src/SDCCicode.c b/src/SDCCicode.c
index 34002152e0b901e0b730ea48c98affe070939265..b46ab97629d3589885978001322625e8962b3ee2 100644 (file)
--- 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 9f5a4fcd1c33aa3102cf466e3839057ee90bf9da..e09ba53a0c23f5d2c7a7a88a5f9b5166d820ff05 100644 (file)
--- 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 65af1a65c5f4c308b656b5d64cf2706c8dbcdbe6..a1ff41aa7e3e3468af083db56133437b1dffe2e5 100644 (file)
--- 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 7a5d1730e6751d5743c3cc4b4477ee05f70bb15a..f586fc639ca2e7aae927da66c3662fd481cba60b 100644 (file)
--- 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 bfdd26d9bb53d81650e57355a398d3983bf95dfb..f43f4174e086f78050c95d0cb4add68757ec4bbd 100644 (file)
--- 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 47984a9990e1ac2bdaad072374b1a61887a3ffd1..a088adbba1e3f951da037766c898298c7694383e 100644 (file)
--- 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 b739f3426d7829624a394989d91e04f782ba5f4b..67cc81e2cb49d0cd3cd4681273ad16a12314cb81 100644 (file)
--- 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 605ddf51dfb6bc87ecdc9448b0a4a5ae7f87f672..778d67b4ccbadd2a0c451b4a5ef8c9e2f11ae134 100644 (file)
--- 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 9d2f9ba9cdbe5935fa98620956ffd44a8367efb7..26b52112b2716cd4e815b75b3e68b4559f481ee6 100755 (executable)
--- 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 99a518ddc909d0ad2b1210228885f5360ae00646..057d01d5ab14190fccb3ada01a162c6657031175 100644 (file)
--- 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,