lang/pc/comp/casestat.C

   1 /* 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 */
   2 #include        "debug.h"
   3
   4 #include        <alloc.h>
   5 #include        <assert.h>
   6 #include        <em.h>
   7
   8 #include        "LLlex.h"
   9 #include        "Lpars.h"
  10 #include        "chk_expr.h"
  11 #include        "density.h"
  12 #include        "main.h"
  13 #include        "node.h"
  14 #include        "type.h"
  15
  16 struct case_hdr {
  17         struct case_hdr *ch_next;               /* in the free list */
  18         int ch_nrofentries;             /* number of cases */
  19         struct type *ch_type;           /* type of case expression */
  20         arith ch_lowerbd;               /* lowest case label */
  21         arith ch_upperbd;               /* highest case label */
  22         struct case_entry *ch_entries;  /* the cases */
  23 };
  24
  25 /* ALLOCDEF "case_hdr" 5 */
  26
  27 struct case_entry       {
  28         struct case_entry *ce_next;     /* next in list */
  29         arith ce_value;                 /* value of case label */
  30         label ce_label;                 /* generated label */
  31 };
  32
  33 /* ALLOCDEF "case_entry" 10 */
  34
  35 /* The constant DENSITY determines when CSA and when CSB instructions
  36    are generated. Reasonable values are: 2, 3, 4.
  37    On machines that have lots of address space and memory, higher values
  38    might also be reasonable. On these machines the density of jump tables
  39    may be lower.
  40 */
  41 #define compact(nr, low, up)    (nr != 0 && (up - low) / nr <= DENSITY)
  42
  43 CaseExpr(nd)
  44         struct node *nd;
  45 {
  46         /* Check the expression and generate code for it
  47         */
  48
  49         register struct node *expp = nd->nd_left;
  50
  51         if( !ChkExpression(expp) ) return;
  52         MarkUsed(expp);
  53
  54         if( !(expp->nd_type->tp_fund & T_ORDINAL) )     {
  55                 node_error(expp, "case-expression must be ordinal");
  56                 return;
  57         }
  58
  59         if( !err_occurred )     {
  60                 CodePExpr(expp);
  61                 C_bra(nd->nd_lab);
  62         }
  63 }
  64
  65 CaseEnd(nd, exit_label)
  66         struct node *nd;
  67         label exit_label;
  68 {
  69         /*      Stack a new case header and fill in the necessary fields.
  70         */
  71         register struct case_hdr *ch = new_case_hdr();
  72         register struct node *right;
  73
  74         assert(nd->nd_class == Link && nd->nd_symb == CASE);
  75
  76         ch->ch_type = nd->nd_left->nd_type;
  77
  78         right = nd->nd_right;
  79
  80         /* Now, create case label list
  81         */
  82         while( right )  {
  83                 assert(right->nd_class == Link && right->nd_symb == ':');
  84
  85                 if( !AddCases(ch, right->nd_left, right->nd_lab) )      {
  86                                 FreeCh(ch);
  87                                 return;
  88                 }
  89                 right = right->nd_right;
  90         }
  91
  92         if( !err_occurred )
  93                 CaseCode(nd->nd_lab, ch, exit_label);
  94
  95         FreeCh(ch);
  96         FreeNode(nd);
  97 }
  98
  99 FreeCh(ch)
 100         register struct case_hdr *ch;
 101 {
 102         /*       free the allocated case structure
 103         */
 104         register struct case_entry *ce;
 105
 106         ce = ch->ch_entries;
 107         while( ce )     {
 108                 struct case_entry *tmp = ce->ce_next;
 109
 110                 free_case_entry(ce);
 111                 ce = tmp;
 112         }
 113
 114         free_case_hdr(ch);
 115 }
 116
 117 AddCases(ch, nd, CaseLabel)
 118         register struct case_hdr *ch;
 119         register struct node *nd;
 120         label CaseLabel;
 121 {
 122         while( nd )     {
 123                 if( !AddOneCase(ch, nd, CaseLabel) )
 124                         return 0;
 125                 nd = nd->nd_next;
 126         }
 127         return 1;
 128 }
 129
 130 AddOneCase(ch, nd, lbl)
 131         register struct case_hdr *ch;
 132         register struct node *nd;
 133         label lbl;
 134 {
 135         register struct case_entry *ce = new_case_entry();
 136         register struct case_entry *c1 = ch->ch_entries, *c2 = 0;
 137
 138         ce->ce_value = nd->nd_INT;
 139         ce->ce_label = lbl;
 140         if( !TstCompat(ch->ch_type, nd->nd_type) )      {
 141                 node_error(nd, "case-statement: type incompatibility in case");
 142                 free_case_entry(ce);
 143                 return 0;
 144         }
 145         if( bounded(ch->ch_type) )      {
 146                 arith lo, hi;
 147
 148                 getbounds(ch->ch_type, &lo, &hi);
 149                 if( ce->ce_value < lo || ce->ce_value > hi )
 150                         warning("case-statement: constant out of bounds");
 151         }
 152
 153         if( !ch->ch_entries )   {
 154                 /* first case entry
 155                 */
 156                 ce->ce_next = (struct case_entry *) 0;
 157                 ch->ch_entries = ce;
 158                 ch->ch_lowerbd = ch->ch_upperbd = ce->ce_value;
 159                 ch->ch_nrofentries = 1;
 160         }
 161         else    {
 162                 /* second etc. case entry
 163                    find the proper place to put ce into the list
 164                 */
 165
 166                 if( ce->ce_value < ch->ch_lowerbd )
 167                         ch->ch_lowerbd = ce->ce_value;
 168                 else if( ce->ce_value > ch->ch_upperbd )
 169                         ch->ch_upperbd = ce->ce_value;
 170
 171                 while( c1 && c1->ce_value < ce->ce_value )      {
 172                         c2 = c1;
 173                         c1 = c1->ce_next;
 174                 }
 175                 /*      At this point three cases are possible:
 176                         1: c1 != 0 && c2 != 0:
 177                                 insert ce somewhere in the middle
 178                         2: c1 != 0 && c2 == 0:
 179                                 insert ce right after the head
 180                         3: c1 == 0 && c2 != 0:
 181                                 append ce to last element
 182                         The case c1 == 0 && c2 == 0 cannot occur, since
 183                         the list is guaranteed not to be empty.
 184                 */
 185                 if( c1 )        {
 186                         if( c1->ce_value == ce->ce_value )      {
 187                                 node_error(nd,
 188                                         "case-statement: multiple case entry");
 189                                 free_case_entry(ce);
 190                                 return 0;
 191                         }
 192                         if( c2 )        {
 193                                 ce->ce_next = c2->ce_next;
 194                                 c2->ce_next = ce;
 195                         }
 196                         else    {
 197                                 ce->ce_next = ch->ch_entries;
 198                                 ch->ch_entries = ce;
 199                         }
 200                 }
 201                 else    {
 202                         assert(c2);
 203
 204                         ce->ce_next = (struct case_entry *) 0;
 205                         c2->ce_next = ce;
 206                 }
 207                 (ch->ch_nrofentries)++;
 208         }
 209         return 1;
 210 }
 211
 212 CaseCode(lbl, ch, exit_label)
 213         label lbl;
 214         struct case_hdr *ch;
 215         label exit_label;
 216 {
 217         label CaseDescrLab = ++data_label;      /* rom must have a label */
 218
 219         register struct case_entry *ce;
 220         register arith val;
 221
 222         C_df_dlb(CaseDescrLab);
 223         C_rom_icon("0", pointer_size);
 224
 225         if( compact(ch->ch_nrofentries, ch->ch_lowerbd, ch->ch_upperbd) ) {
 226                 /* CSA */
 227                 C_rom_cst(ch->ch_lowerbd);
 228                 C_rom_cst(ch->ch_upperbd - ch->ch_lowerbd);
 229                 ce = ch->ch_entries;
 230                 for( val = ch->ch_lowerbd; val <= ch->ch_upperbd; val++ ) {
 231                         assert(ce);
 232                         if( val == ce->ce_value )       {
 233                                 C_rom_ilb(ce->ce_label);
 234                                 ce = ce->ce_next;
 235                         }
 236                         else
 237                                 C_rom_icon("0", pointer_size);
 238                 }
 239                 C_df_ilb(lbl);
 240                 C_lae_dlb(CaseDescrLab, (arith) 0);
 241                 C_csa(word_size);
 242         }
 243         else    {
 244                 /* CSB */
 245                 C_rom_cst((arith) ch->ch_nrofentries);
 246                 for( ce = ch->ch_entries; ce; ce = ce->ce_next )        {
 247                                 C_rom_cst(ce->ce_value);
 248                                 C_rom_ilb(ce->ce_label);
 249                 }
 250                 C_df_ilb(lbl);
 251                 C_lae_dlb(CaseDescrLab, (arith) 0);
 252                 C_csb(word_size);
 253         }
 254
 255         C_df_ilb(exit_label);
 256 }