lang/m2/comp/casestat.C

   1 /*
   2  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
   3  * See the copyright notice in the ACK home directory, in the file "Copyright".
   4  *
   5  * Author: Ceriel J.H. Jacobs
   6  */
   7
   8 /* C A S E   S T A T E M E N T   C O D E   G E N E R A T I O N */
   9
  10 /* $Id: casestat.C,v 1.31 1994/06/24 12:39:42 ceriel Exp $ */
  11
  12 /*      Generation of case statements is done by first creating a
  13         description structure for the statement, build a list of the
  14         case-labels, then generating a case description in the code,
  15         and generating either CSA or CSB, and then generating code for the
  16         cases themselves.
  17 */
  18
  19 #include        "debug.h"
  20
  21 #include        <em_label.h>
  22 #include        <em_arith.h>
  23 #include        <em_code.h>
  24 #include        <alloc.h>
  25 #include        <assert.h>
  26
  27 #include        "Lpars.h"
  28 #include        "type.h"
  29 #include        "LLlex.h"
  30 #include        "node.h"
  31 #include        "desig.h"
  32 #include        "walk.h"
  33 #include        "chk_expr.h"
  34 #include        "def.h"
  35
  36 #include        "density.h"
  37
  38 struct switch_hdr       {
  39         label sh_break;                 /* label of statement after this one */
  40         label sh_default;               /* label of ELSE part, or 0 */
  41         int sh_nrofentries;             /* number of cases */
  42         t_type *sh_type;                /* type of case expression */
  43         arith sh_lowerbd;               /* lowest case label */
  44         arith sh_upperbd;               /* highest case label */
  45         struct case_entry *sh_entries;  /* the cases with their generated
  46                                            labels
  47                                         */
  48 };
  49
  50 /* STATICALLOCDEF "switch_hdr" 5 */
  51
  52 struct case_entry       {
  53         struct case_entry *ce_next;     /* next in list */
  54         label ce_label;                 /* generated label */
  55         arith ce_low, ce_up;            /* lower and upper bound of range */
  56 };
  57
  58 /* STATICALLOCDEF "case_entry" 20 */
  59
  60 /* The constant DENSITY determines when CSA and when CSB instructions
  61    are generated. Reasonable values are: 2, 3, 4.
  62    On machines that have lots of address space and memory, higher values
  63    might also be reasonable. On these machines the density of jump tables
  64    may be lower.
  65 */
  66
  67 compact(nr, low, up)
  68         arith low, up;
  69 {
  70         /*      Careful! up - low might not fit in an arith. And then,
  71                 the test "up-low < 0" might also not work to detect this
  72                 situation! Or is this just a bug in the M68020/M68000?
  73         */
  74         arith diff = up - low;
  75
  76         return (nr != 0 && diff >= 0 && fit(diff, (int) word_size) &&
  77                 diff / nr <= (DENSITY - 1));
  78 }
  79 #define nd_lab  nd_symb
  80
  81 int
  82 CaseCode(nd, exitlabel, end_reached)
  83         t_node *nd;
  84         label exitlabel;
  85 {
  86         /*      Check the expression, stack a new case header and
  87                 fill in the necessary fields.
  88                 "exitlabel" is the exit-label of the closest enclosing
  89                 LOOP-statement, or 0.
  90         */
  91         register struct switch_hdr *sh = new_switch_hdr();
  92         register t_node *pnode = nd;
  93         register struct case_entry *ce;
  94         register arith val;
  95         label CaseDescrLab;
  96         int rval;
  97
  98         assert(pnode->nd_class == Stat && pnode->nd_symb == CASE);
  99
 100         if (ChkExpression(&(pnode->nd_LEFT))) {
 101                 MkCoercion(&(pnode->nd_LEFT),BaseType(pnode->nd_LEFT->nd_type));
 102                 CodePExpr(pnode->nd_LEFT);
 103         }
 104         sh->sh_type = pnode->nd_LEFT->nd_type;
 105         sh->sh_break = ++text_label;
 106
 107         /* Now, create case label list
 108         */
 109         while (pnode = pnode->nd_RIGHT) {
 110                 if (pnode->nd_class == Link && pnode->nd_symb == '|') {
 111                         if (pnode->nd_LEFT) {
 112                                 /* non-empty case
 113                                 */
 114                                 pnode->nd_LEFT->nd_lab = ++text_label;
 115                                 AddCases(sh, /* to descriptor */
 116                                          pnode->nd_LEFT->nd_LEFT,
 117                                              /* of case labels */
 118                                          (label) pnode->nd_LEFT->nd_lab
 119                                              /* and code label */
 120                                               );
 121                         }
 122                 }
 123                 else {
 124                         /* Else part
 125                         */
 126
 127                         sh->sh_default = ++text_label;
 128                         break;
 129                 }
 130         }
 131
 132         if (!sh->sh_nrofentries) {
 133                 /* There were no cases, so we have to check the case-expression
 134                    here
 135                 */
 136                 if (! (sh->sh_type->tp_fund & T_DISCRETE)) {
 137                         node_error(nd, "illegal type in CASE-expression");
 138                 }
 139         }
 140
 141         /* Now generate code for the switch itself
 142            First the part that CSA and CSB descriptions have in common.
 143         */
 144         CaseDescrLab = ++data_label;    /* the rom must have a label    */
 145         C_df_dlb(CaseDescrLab);
 146         if (sh->sh_default) C_rom_ilb(sh->sh_default);
 147         else C_rom_ucon("0", pointer_size);
 148         if (compact(sh->sh_nrofentries, sh->sh_lowerbd, sh->sh_upperbd)) {
 149                 /* CSA
 150                 */
 151                 int gen = 1;
 152
 153                 ce = sh->sh_entries;
 154                 while (! ce->ce_label) ce = ce->ce_next;
 155                 C_rom_cst((arith) 0);
 156                 C_rom_cst(sh->sh_upperbd - sh->sh_lowerbd);
 157                 for (val = sh->sh_lowerbd; val <= sh->sh_upperbd; val++) {
 158                         assert(ce);
 159                         if (gen || val == ce->ce_low) {
 160                                 gen = 1;
 161                                 C_rom_ilb(ce->ce_label);
 162                                 if (val == ce->ce_up) {
 163                                         gen = 0;
 164                                         ce = ce->ce_next;
 165                                         while (ce && ! ce->ce_label) ce = ce->ce_next;
 166                                 }
 167                         }
 168                         else if (sh->sh_default) C_rom_ilb(sh->sh_default);
 169                         else C_rom_ucon("0", pointer_size);
 170                 }
 171                 C_loc(sh->sh_lowerbd);
 172                 C_sbu(word_size);
 173                 c_lae_dlb(CaseDescrLab);        /* perform the switch */
 174                 C_csa(word_size);
 175         }
 176         else    {
 177                 /* CSB
 178                 */
 179                 C_rom_cst((arith)sh->sh_nrofentries);
 180                 for (ce = sh->sh_entries; ce; ce = ce->ce_next) {
 181                         /* generate the entries: value + prog.label
 182                         */
 183                         if (! ce->ce_label) continue;
 184                         val = ce->ce_low;
 185                         do {
 186                                 C_rom_cst(val);
 187                                 C_rom_ilb(ce->ce_label);
 188                         } while (val++ != ce->ce_up);
 189                 }
 190                 c_lae_dlb(CaseDescrLab);        /* perform the switch */
 191                 C_csb(word_size);
 192         }
 193
 194         /* Now generate code for the cases
 195         */
 196         pnode = nd;
 197         rval = 0;
 198         while (pnode = pnode->nd_RIGHT) {
 199                 if (pnode->nd_class == Link && pnode->nd_symb == '|') {
 200                         if (pnode->nd_LEFT) {
 201                                 rval |= LblWalkNode((label) pnode->nd_LEFT->nd_lab,
 202                                             pnode->nd_LEFT->nd_RIGHT,
 203                                             exitlabel, end_reached);
 204                                 c_bra(sh->sh_break);
 205                         }
 206                 }
 207                 else {
 208                         /* Else part
 209                         */
 210                         assert(sh->sh_default != 0);
 211
 212                         rval |= LblWalkNode(sh->sh_default,
 213                                         pnode, exitlabel, end_reached);
 214                         break;
 215                 }
 216         }
 217
 218         def_ilb(sh->sh_break);
 219         FreeSh(sh);
 220         return rval;
 221 }
 222
 223 FreeSh(sh)
 224         register struct switch_hdr *sh;
 225 {
 226         /*       free the allocated switch structure
 227         */
 228         register struct case_entry *ce;
 229
 230         ce = sh->sh_entries;
 231         while (ce)      {
 232                 struct case_entry *tmp = ce->ce_next;
 233
 234                 free_case_entry(ce);
 235                 ce = tmp;
 236         }
 237
 238         free_switch_hdr(sh);
 239 }
 240
 241 AddCases(sh, node, lbl)
 242         struct switch_hdr *sh;
 243         register t_node *node;
 244         label lbl;
 245 {
 246         /*      Add case labels to the case label list
 247         */
 248
 249         if (node->nd_class == Link) {
 250                 if (node->nd_symb == UPTO) {
 251                         assert(node->nd_LEFT->nd_class == Value);
 252                         assert(node->nd_RIGHT->nd_class == Value);
 253
 254                         AddOneCase(sh, node->nd_LEFT, node->nd_RIGHT, lbl);
 255                         return;
 256                 }
 257
 258                 assert(node->nd_symb == ',');
 259                 AddCases(sh, node->nd_LEFT, lbl);
 260                 AddCases(sh, node->nd_RIGHT, lbl);
 261                 return;
 262         }
 263
 264         assert(node->nd_class == Value);
 265         AddOneCase(sh, node, node, lbl);
 266 }
 267
 268 AddOneCase(sh, lnode, rnode, lbl)
 269         register struct switch_hdr *sh;
 270         t_node *lnode, *rnode;
 271         label lbl;
 272 {
 273         register struct case_entry *ce = new_case_entry();
 274         register struct case_entry *c1 = sh->sh_entries, *c2 = 0;
 275         int fund = sh->sh_type->tp_fund;
 276         arith diff;
 277
 278         if (! ChkCompat(&lnode, sh->sh_type, "case") ||
 279             ! ChkCompat(&rnode, sh->sh_type, "case")) {
 280         }
 281         ce->ce_label = lbl;
 282         ce->ce_low = lnode->nd_INT;
 283         ce->ce_up = rnode->nd_INT;
 284         diff = rnode->nd_INT - lnode->nd_INT;
 285 #define MAXRANGE        100
 286         if (diff < 0 || diff > MAXRANGE) {
 287                 /* This is a bit of a hack, but it prevents the compiler
 288                    from crashing on things like
 289                    CASE a OF
 290                      10 .. MAX(CARDINAL): ....
 291
 292                    If the range covers more than MAXRANGE cases, this case
 293                    is dealt with separately.
 294                 */
 295                 label cont = ++text_label;
 296
 297                 C_dup(int_size);
 298                 C_loc(lnode->nd_INT);
 299                 if (fund == T_INTEGER) {
 300                         C_blt(cont);
 301                 }
 302                 else {
 303                         C_cmu(int_size);
 304                         C_zlt(cont);
 305                 }
 306                 C_dup(int_size);
 307                 C_loc(rnode->nd_INT);
 308                 if (fund == T_INTEGER) {
 309                         C_bgt(cont);
 310                 }
 311                 else {
 312                         C_cmu(int_size);
 313                         C_zgt(cont);
 314                 }
 315                 C_asp(int_size);
 316                 c_bra(lbl);
 317                 C_df_ilb(cont);
 318                 ce->ce_label = 0;
 319         }
 320         if (sh->sh_entries == 0)        {
 321                 /* first case entry
 322                 */
 323                 sh->sh_entries = ce;
 324                 if (ce->ce_label) {
 325                         sh->sh_lowerbd = ce->ce_low;
 326                         sh->sh_upperbd = ce->ce_up;
 327                 }
 328         }
 329         else    {
 330                 /* second etc. case entry
 331                    find the proper place to put ce into the list
 332                 */
 333
 334                 while (c1 && chk_bounds(c1->ce_low, ce->ce_low, fund)) {
 335                         c2 = c1;
 336                         c1 = c1->ce_next;
 337                 }
 338                 /*      At this point three cases are possible:
 339                         1: c1 != 0 && c2 != 0:
 340                                 insert ce somewhere in the middle
 341                         2: c1 != 0 && c2 == 0:
 342                                 insert ce right after the head
 343                         3: c1 == 0 && c2 != 0:
 344                                 append ce to last element
 345                         The case c1 == 0 && c2 == 0 cannot occur, since
 346                         the list is guaranteed not to be empty.
 347                 */
 348                 if (c2) {
 349                         if ( chk_bounds(ce->ce_low, c2->ce_up, fund)) {
 350 node_error(rnode, "multiple case entry for value %ld", (long)(ce->ce_low));
 351                                 free_case_entry(ce);
 352                                 return;
 353                         }
 354                 }
 355                 if (c1) {
 356                         if ( chk_bounds(c1->ce_low, ce->ce_up, fund)) {
 357 node_error(rnode, "multiple case entry for value %ld", (long)(ce->ce_up));
 358                                 free_case_entry(ce);
 359                                 return;
 360                         }
 361                         if (c2) {
 362                                 ce->ce_next = c2->ce_next;
 363                                 c2->ce_next = ce;
 364                         }
 365                         else    {
 366                                 ce->ce_next = sh->sh_entries;
 367                                 sh->sh_entries = ce;
 368                         }
 369                 }
 370                 else    {
 371                         assert(c2);
 372
 373                         c2->ce_next = ce;
 374                 }
 375                 if (ce->ce_label) {
 376                         if (! chk_bounds(sh->sh_lowerbd, ce->ce_low, fund)) {
 377                                 sh->sh_lowerbd = ce->ce_low;
 378                         }
 379                         if (! chk_bounds(ce->ce_up, sh->sh_upperbd, fund)) {
 380                                 sh->sh_upperbd = ce->ce_up;
 381                         }
 382                 }
 383         }
 384         if (ce->ce_label) sh->sh_nrofentries += ce->ce_up - ce->ce_low + 1;
 385 }