gnu/usr.bin/g++/cc1plus/case.c

   1 #ifndef FIRST_PSEUDO_REGISTER
   2 #define NULL 0
   3 #include "config.h"
   4 #include "rtl.h"
   5 #include "tree.h"
   6 #include "insn-flags.h"
   7 #endif
   8
   9 /* Functions and data structures for expanding case statements.  */
  10
  11 /* Case label structure, used to hold info on labels within case
  12    statements.  We handle "range" labels; for a single-value label
  13    as in C, the high and low limits are the same.  */
  14
  15 struct case_node
  16 {
  17   struct case_node      *left;
  18   struct case_node      *right;
  19   struct case_node      *parent;
  20   tree                  low;
  21   tree                  high;
  22   tree                  test_label;
  23   tree                  code_label;
  24 };
  25
  26 typedef struct case_node case_node;
  27 typedef struct case_node *case_node_ptr;
  28
  29 void balance_case_nodes ();
  30 void emit_case_nodes ();
  31 void group_case_nodes ();
  32 void emit_jump_if_reachable ();
  33
  34 /* Generate code to jump to LABEL if OP1 and OP2 are equal.  */
  35
  36 static void
  37 do_jump_if_equal (op1, op2, label, unsignedp)
  38      rtx op1, op2, label;
  39      int unsignedp;
  40 {
  41   if (GET_CODE (op1) == CONST_INT
  42       && GET_CODE (op2) == CONST_INT)
  43     {
  44       if (INTVAL (op1) == INTVAL (op2))
  45         emit_jump (label);
  46     }
  47   else
  48     {
  49       emit_cmp_insn (op1, op2, 0, unsignedp, 0);
  50       emit_jump_insn (gen_beq (label));
  51     }
  52 }
  53 \f
  54 /* Not all case values are encountered equally.  This function
  55    uses a heuristic to weight case labels, in cases where that
  56    looks like a reasonable thing to do.
  57
  58    Right now, all we try to guess is text, and we establish the
  59    following weights:
  60
  61         chars above space:      16
  62         digits:                 16
  63         default:                12
  64         space, punct:           8
  65         tab:                    4
  66         newline:                2
  67         other "\" chars:        1
  68         remaining chars:        0
  69
  70    Under this weighting, ranges are automagically taken care of.  */
  71
  72 #include <ctype.h>
  73 static char *cost_table;
  74 static int use_cost_table;
  75
  76 void
  77 estimate_case_costs (node, default_label)
  78      case_node_ptr node;
  79      rtx default_label;
  80 {
  81   tree min_ascii = build_int_2 (-1, -1);
  82   tree max_ascii = convert (TREE_TYPE (node->high), build_int_2 (127, 0));
  83   case_node_ptr n;
  84   use_cost_table = 0;
  85
  86   /* If the user is running without default, who are we
  87      to guess where values are likely to land?  */
  88   if (default_label == 0)
  89     return;
  90
  91   /* See if all the case expressions look like text.  It is text if the lowest
  92      constant is >= -1 and the highest constant is <= 127.  If the case
  93      expression is unsigned, suppress the test for >= -1, since it would always
  94      be true.  */
  95   for (n = node; n; n = n->right)
  96     if ((! TREE_UNSIGNED (TREE_TYPE (n->low))
  97          && tree_int_cst_lt (n->low, min_ascii))
  98         || tree_int_cst_lt (max_ascii, n->high))
  99         return;
 100
 101   /* All interesting values with within the range of
 102      interesting ASCII characters.  */
 103   if (cost_table == NULL)
 104     {
 105       int i;
 106       cost_table = ((char *)malloc (129)) + 1;
 107       bzero (cost_table-1, 128);
 108       for (i = 0; i < 128; i++)
 109         {
 110           if (isalnum (i))
 111             cost_table[i] = 16;
 112           else if (ispunct (i))
 113             cost_table[i] = 8;
 114           else if (iscntrl (i))
 115             cost_table[i] = -1;
 116         }
 117       cost_table[' '] = 8;
 118       cost_table['\t'] = 4;
 119       cost_table['\0'] = 4;
 120       cost_table['\n'] = 2;
 121       cost_table['\f'] = 1;
 122       cost_table['\v'] = 1;
 123       cost_table['\b'] = 1;
 124     }
 125   use_cost_table = 1;
 126 }
 127 \f
 128 /* Scan an ordered list of case nodes
 129    combining those with consecutive values or ranges.
 130
 131    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
 132
 133 void
 134 group_case_nodes (head)
 135      case_node_ptr head;
 136 {
 137   case_node_ptr node = head;
 138
 139   while (node)
 140     {
 141       rtx lb = next_real_insn (label_rtx (node->code_label));
 142       case_node_ptr np = node;
 143
 144       /* Try to group the successors of NODE with NODE.  */
 145       while (((np = np->right) != 0)
 146              /* Do they jump to the same place?  */
 147              && next_real_insn (label_rtx (np->code_label)) == lb
 148              /* Are their ranges consecutive?  */
 149              && tree_int_cst_equal (np->low,
 150                                     combine (PLUS_EXPR, node->high,
 151                                              integer_one_node)))
 152         {
 153           node->high = np->high;
 154         }
 155       /* NP is the first node after NODE which can't be grouped with it.
 156          Delete the nodes in between, and move on to that node.  */
 157       node->right = np;
 158       node = np;
 159     }
 160 }
 161
 162 /* Take an ordered list of case nodes
 163    and transform them into a near optimal binary tree,
 164    on the assumtion that any target code selection value is as
 165    likely as any other.
 166
 167    The transformation is performed by splitting the ordered
 168    list into two equal sections plus a pivot.  The parts are
 169    then attached to the pivot as left and right branches.  Each
 170    branch is is then transformed recursively.  */
 171
 172 void
 173 balance_case_nodes (head, parent)
 174      case_node_ptr *head;
 175      case_node_ptr parent;
 176 {
 177   register case_node_ptr np;
 178
 179   np = *head;
 180   if (np)
 181     {
 182       int cost = 0;
 183       int i = 0;
 184       int ranges = 0;
 185       register case_node_ptr *npp;
 186       case_node_ptr left;
 187
 188       /* Count the number of entries on branch.
 189          Also count the ranges.  */
 190       while (np)
 191         {
 192           if (!tree_int_cst_equal (np->low, np->high))
 193             {
 194               ranges++;
 195               if (use_cost_table)
 196                 {
 197                   int hi_cost = cost_table[TREE_INT_CST_LOW (np->high)];
 198                   if (hi_cost < 0)
 199                     use_cost_table = 0;
 200                   else
 201                     cost += hi_cost;
 202                 }
 203             }
 204           if (use_cost_table)
 205             {
 206               int lo_cost = cost_table[TREE_INT_CST_LOW (np->low)];
 207               if (lo_cost < 0)
 208                 use_cost_table = 0;
 209               else
 210                 cost += lo_cost;
 211             }
 212           else
 213             cost += 1;
 214           i++;
 215           np = np->right;
 216         }
 217       if (i > 2)
 218         {
 219           /* Split this list if it is long enough for that to help.  */
 220           npp = head;
 221           left = *npp;
 222           if (use_cost_table)
 223             {
 224               /* Find the place in the list that bisects the list's total cost,
 225                  Here I gets half the total cost.  */
 226               int n_moved = 0;
 227               i = (cost + 1) / 2;
 228               while (1)
 229                 {
 230                   /* Skip nodes while their cost does not reach that amount.  */
 231                   if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
 232                     i -= cost_table[TREE_INT_CST_LOW ((*npp)->high)];
 233                   i -= cost_table[TREE_INT_CST_LOW ((*npp)->low)];
 234                   if (i <= 0)
 235                     break;
 236                   npp = &(*npp)->right;
 237                   n_moved += 1;
 238                 }
 239               if (n_moved == 0)
 240                 {
 241                   /* Leave this branch lopsided, but optimize left-hand
 242                      side and fill in `parent' fields for right-hand side.  */
 243                   np = *head;
 244                   np->parent = parent;
 245                   balance_case_nodes (&np->left, np);
 246                   for (; np->right; np = np->right)
 247                     np->right->parent = np;
 248                   return;
 249                 }
 250             }
 251           /* If there are just three nodes, split at the middle one.  */
 252           else if (i == 3)
 253             npp = &(*npp)->right;
 254           else
 255             {
 256               /* Find the place in the list that bisects the list's total cost,
 257                  where ranges count as 2.
 258                  Here I gets half the total cost.  */
 259               i = (i + ranges + 1) / 2;
 260               while (1)
 261                 {
 262                   /* Skip nodes while their cost does not reach that amount.  */
 263                   if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
 264                     i--;
 265                   i--;
 266                   if (i <= 0)
 267                     break;
 268                   npp = &(*npp)->right;
 269                 }
 270             }
 271           *head = np = *npp;
 272           *npp = 0;
 273           np->parent = parent;
 274           np->left = left;
 275
 276           /* Optimize each of the two split parts.  */
 277           balance_case_nodes (&np->left, np);
 278           balance_case_nodes (&np->right, np);
 279         }
 280       else
 281         {
 282           /* Else leave this branch as one level,
 283              but fill in `parent' fields.  */
 284           np = *head;
 285           np->parent = parent;
 286           for (; np->right; np = np->right)
 287             np->right->parent = np;
 288         }
 289     }
 290 }
 291 \f
 292 /* Search the parent sections of the case node tree
 293    to see if a test for the lower bound of NODE would be redundant.
 294
 295    The instructions to synthesis the case decision tree are
 296    output in the same order as nodes are processed so it is
 297    known that if a parent node checks the range of the current
 298    node minus one that the current node is bounded at its lower
 299    span.  Thus the test would be redundant.  */
 300
 301 static int
 302 node_has_low_bound (node)
 303      case_node_ptr node;
 304 {
 305   tree low_minus_one;
 306   case_node_ptr pnode;
 307
 308   if (node->left)
 309     {
 310       low_minus_one = combine (MINUS_EXPR, node->low, integer_one_node);
 311       /* Avoid the screw case of overflow where low_minus_one is > low.  */
 312       if (tree_int_cst_lt (low_minus_one, node->low))
 313         for (pnode = node->parent; pnode; pnode = pnode->parent)
 314           {
 315             if (tree_int_cst_equal (low_minus_one, pnode->high))
 316               return 1;
 317             /* If a parent node has a left branch we know that none
 318                of its parents can have a high bound of our target
 319                minus one so we abort the search.  */
 320             if (node->left)
 321               break;
 322           }
 323     }
 324   return 0;
 325 }
 326
 327 /* Search the parent sections of the case node tree
 328    to see if a test for the upper bound of NODE would be redundant.
 329
 330    The instructions to synthesis the case decision tree are
 331    output in the same order as nodes are processed so it is
 332    known that if a parent node checks the range of the current
 333    node plus one that the current node is bounded at its upper
 334    span.  Thus the test would be redundant.  */
 335
 336 static int
 337 node_has_high_bound (node)
 338      case_node_ptr node;
 339 {
 340   tree high_plus_one;
 341   case_node_ptr pnode;
 342
 343   if (node->right == 0)
 344     {
 345       high_plus_one = combine (PLUS_EXPR, node->high, integer_one_node);
 346       /* Avoid the screw case of overflow where high_plus_one is > high.  */
 347       if (tree_int_cst_lt (node->high, high_plus_one))
 348         for (pnode = node->parent; pnode; pnode = pnode->parent)
 349           {
 350             if (tree_int_cst_equal (high_plus_one, pnode->low))
 351               return 1;
 352             /* If a parent node has a right branch we know that none
 353                of its parents can have a low bound of our target
 354                plus one so we abort the search.  */
 355             if (node->right)
 356               break;
 357           }
 358     }
 359   return 0;
 360 }
 361
 362 /* Search the parent sections of the
 363    case node tree to see if both tests for the upper and lower
 364    bounds of NODE would be redundant.  */
 365
 366 static int
 367 node_is_bounded (node)
 368      case_node_ptr node;
 369 {
 370   if (node->left || node->right)
 371     return 0;
 372   return node_has_low_bound (node) && node_has_high_bound (node);
 373 }
 374
 375 /*  Emit an unconditional jump to LABEL unless it would be dead code.  */
 376
 377 void
 378 emit_jump_if_reachable (label)
 379      rtx label;
 380 {
 381   rtx last_insn;
 382
 383   if (GET_CODE (get_last_insn ()) != BARRIER)
 384     emit_jump (label);
 385 }
 386 \f
 387 /* Emit step-by-step code to select a case for the value of INDEX.
 388    The thus generated decision tree follows the form of the
 389    case-node binary tree NODE, whose nodes represent test conditions.
 390    UNSIGNEDP is nonzero if we should do unsigned comparisons.
 391
 392    Care is taken to prune redundant tests from the decision tree
 393    by detecting any boundary conditions already checked by
 394    emitted rtx.  (See node_has_high_bound, node_has_low_bound
 395    and node_is_bounded, above.)
 396
 397    Where the test conditions can be shown to be redundant we emit
 398    an unconditional jump to the target code.  As a further
 399    optimization, the subordinates of a tree node are examined to
 400    check for bounded nodes.  In this case conditional and/or
 401    unconditional jumps as a result of the boundary check for the
 402    current node are arranged to target the subordinates associated
 403    code for out of bound conditions on the current node node.  */
 404
 405 void
 406 emit_case_nodes (index, node, default_label, unsignedp)
 407      rtx index;
 408      case_node_ptr node;
 409      rtx default_label;
 410      int unsignedp;
 411 {
 412   /* If INDEX has an unsigned type, we must make unsigned branches.  */
 413   typedef rtx rtx_function ();
 414   rtx_function *gen_bgt_pat = unsignedp ? gen_bgtu : gen_bgt;
 415   rtx_function *gen_bge_pat = unsignedp ? gen_bgeu : gen_bge;
 416   rtx_function *gen_blt_pat = unsignedp ? gen_bltu : gen_blt;
 417   rtx_function *gen_ble_pat = unsignedp ? gen_bleu : gen_ble;
 418   int defaulted_left = 0;
 419   int defaulted_right = 0;
 420
 421   if (node->test_label)
 422     {
 423       /* If this test node requires a label it follows that
 424          it must be preceeded by an unconditional branch.
 425          If control can pass to this point we can assume that
 426          a "br default" is in order.  */
 427       emit_jump_if_reachable (default_label);
 428       expand_label (node->test_label);
 429     }
 430   if (tree_int_cst_equal (node->low, node->high))
 431     {
 432       /* Node is single valued.  */
 433       do_jump_if_equal (index, expand_expr (node->low, 0, VOIDmode, 0),
 434                         label_rtx (node->code_label), unsignedp);
 435       if (node->right)
 436         {
 437           if (node->left)
 438             {
 439               /* This node has children on either side.  */
 440               emit_cmp_insn (index, expand_expr (node->high, 0, VOIDmode, 0), 0, unsignedp, 0);
 441
 442               if (node_is_bounded (node->right))
 443                 {
 444                   emit_jump_insn ((*gen_bgt_pat) (label_rtx (node->right->code_label)));
 445                   if (node_is_bounded (node->left))
 446                     emit_jump (label_rtx (node->left->code_label));
 447                   else
 448                     emit_case_nodes (index, node->left,
 449                                      default_label, unsignedp);
 450                 }
 451               else
 452                 {
 453                   if (node_is_bounded (node->left))
 454                     emit_jump_insn ((*gen_blt_pat) (label_rtx (node->left->code_label)));
 455                   else
 456                     {
 457                       node->right->test_label =
 458                         build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
 459                       emit_jump_insn ((*gen_bgt_pat) (label_rtx (node->right->test_label)));
 460                       emit_case_nodes (index, node->left,
 461                                        default_label, unsignedp);
 462                     }
 463                   emit_case_nodes (index, node->right,
 464                                    default_label, unsignedp);
 465                 }
 466             }
 467           else
 468             {
 469               /* Here we have a right child but no left
 470                  so we issue conditional branch to default
 471                  and process the right child.  */
 472
 473               /* Omit the conditional branch to default
 474                  if we it avoid only one right child;
 475                  it costs too much space to save so little time.  */
 476               if (node->right->right && !node_has_low_bound (node))
 477                 {
 478                   emit_cmp_insn (index, expand_expr (node->high, 0, VOIDmode, 0), 0, unsignedp, 0);
 479                   emit_jump_insn ((*gen_blt_pat) (default_label));
 480                 }
 481               if (node_is_bounded (node->right))
 482                 emit_jump (label_rtx (node->right->code_label));
 483               else
 484                 emit_case_nodes (index, node->right, default_label, unsignedp);
 485             }
 486         }
 487       else if (node->left)
 488         {
 489           if (use_cost_table
 490               && ! defaulted_right
 491               && cost_table[TREE_INT_CST_LOW (node->high)] < 12)
 492             {
 493               /* If our "most probably entry" is less probable
 494                  than the default label, emit a jump to
 495                  the default label using condition codes
 496                  already lying around.  With no right branch,
 497                  a branch-greater-than will get us to the default
 498                  label correctly.  */
 499               emit_cmp_insn (index, expand_expr (node->high, 0, VOIDmode, 0), 0, unsignedp, 0);
 500               emit_jump_insn ((*gen_bgt_pat) (default_label));
 501               /* No sense doing this too often.  */
 502               defaulted_right = 1;
 503             }
 504           if (node_is_bounded (node->left))
 505             emit_jump (label_rtx (node->left->code_label));
 506           else
 507             emit_case_nodes (index, node->left, default_label, unsignedp);
 508         }
 509     }
 510   else
 511     {
 512       /* Node is a range.  */
 513       if (node->right)
 514         {
 515           if (node->left)
 516             {
 517               emit_cmp_insn (index, expand_expr (node->high, 0, VOIDmode, 0), 0, unsignedp, 0);
 518               if (node_is_bounded (node->right))
 519                 {
 520                   /* Right hand node is fully bounded so we can
 521                      eliminate any testing and branch directly
 522                      to the target code.  */
 523                   emit_jump_insn ((*gen_bgt_pat) (label_rtx (node->right->code_label)));
 524                 }
 525               else
 526                 {
 527                   /* Right hand node requires testing so create
 528                      a label to put on the cmp code.  */
 529                   node->right->test_label =
 530                     build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
 531                   emit_jump_insn ((*gen_bgt_pat) (label_rtx (node->right->test_label)));
 532                 }
 533               emit_cmp_insn (index, expand_expr (node->low, 0, VOIDmode, 0), 0, unsignedp, 0);
 534               emit_jump_insn ((*gen_bge_pat) (label_rtx (node->code_label)));
 535               if (node_is_bounded (node->left))
 536                 {
 537                   /* Left hand node is fully bounded so we can
 538                      eliminate any testing and branch directly
 539                      to the target code.  */
 540                   emit_jump (label_rtx (node->left->code_label));
 541                 }
 542               else
 543                 emit_case_nodes (index, node->left, default_label, unsignedp);
 544               /* If right node has been given a test label above
 545                  we must process it now.  */
 546               if (node->right->test_label)
 547                 emit_case_nodes (index, node->right, default_label, unsignedp);
 548             }
 549           else
 550             {
 551               if (!node_has_low_bound (node))
 552                 {
 553                   emit_cmp_insn (index, expand_expr (node->low, 0, VOIDmode, 0), 0, unsignedp, 0);
 554                   emit_jump_insn ((*gen_blt_pat) (default_label));
 555                 }
 556               emit_cmp_insn (index, expand_expr (node->high, 0, VOIDmode, 0), 0, unsignedp, 0);
 557               emit_jump_insn ((*gen_ble_pat) (label_rtx (node->code_label)));
 558               if (node_is_bounded (node->right))
 559                 {
 560                   /* Right hand node is fully bounded so we can
 561                      eliminate any testing and branch directly
 562                      to the target code.  */
 563                   emit_jump (label_rtx (node->right->code_label));
 564                 }
 565               else
 566                 emit_case_nodes (index, node->right, default_label, unsignedp);
 567             }
 568         }
 569       else if (node->left)
 570         {
 571           if (!node_has_high_bound (node))
 572             {
 573               emit_cmp_insn (index, expand_expr (node->high, 0, VOIDmode, 0), 0, unsignedp, 0);
 574               emit_jump_insn ((*gen_bgt_pat) (default_label));
 575             }
 576           emit_cmp_insn (index, expand_expr (node->low, 0, VOIDmode, 0), 0, unsignedp, 0);
 577           emit_jump_insn ((*gen_bge_pat) (label_rtx (node->code_label)));
 578           if (node_is_bounded (node->left))
 579             {
 580               /* Left hand node is fully bounded so we can
 581                  eliminate any testing and branch directly
 582                  to the target code.  */
 583               emit_jump (label_rtx (node->left->code_label));
 584             }
 585           else
 586             emit_case_nodes (index, node->left, default_label, unsignedp);
 587         }
 588       else
 589         {
 590           /* Node has no children so we check low and
 591              high bounds to remove redundant tests. In practice
 592              only one of the limits may be bounded or the parent
 593              node will have emmited a jump to our target code.  */
 594           if (!node_has_high_bound (node))
 595             {
 596               emit_cmp_insn (index, expand_expr (node->high, 0, VOIDmode, 0), 0, unsignedp, 0);
 597               emit_jump_insn ((*gen_bgt_pat) (default_label));
 598             }
 599           if (!node_has_low_bound (node))
 600             {
 601               emit_cmp_insn (index, expand_expr (node->low, 0, VOIDmode, 0), 0, unsignedp, 0);
 602               emit_jump_insn ((*gen_bge_pat) (label_rtx (node->code_label)));
 603             }
 604           /* We allow the default case to drop through since
 605              it will picked up by calls to `jump_if_reachable'
 606              either on the next test label or at the end of
 607              the decision tree emission.  */
 608         }
 609     }
 610 }
 611