contrib/gcc-5.0/gcc/stmt.c

   1 /* Expands front end tree to back end RTL for GCC
   2    Copyright (C) 1987-2015 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 /* This file handles the generation of rtl code from tree structure
  21    above the level of expressions, using subroutines in exp*.c and emit-rtl.c.
  22    The functions whose names start with `expand_' are called by the
  23    expander to generate RTL instructions for various kinds of constructs.  */
  24
  25 #include "config.h"
  26 #include "system.h"
  27 #include "coretypes.h"
  28 #include "tm.h"
  29
  30 #include "rtl.h"
  31 #include "hard-reg-set.h"
  32 #include "hash-set.h"
  33 #include "machmode.h"
  34 #include "vec.h"
  35 #include "double-int.h"
  36 #include "input.h"
  37 #include "alias.h"
  38 #include "symtab.h"
  39 #include "wide-int.h"
  40 #include "inchash.h"
  41 #include "tree.h"
  42 #include "fold-const.h"
  43 #include "varasm.h"
  44 #include "stor-layout.h"
  45 #include "tm_p.h"
  46 #include "flags.h"
  47 #include "except.h"
  48 #include "function.h"
  49 #include "insn-config.h"
  50 #include "hashtab.h"
  51 #include "statistics.h"
  52 #include "real.h"
  53 #include "fixed-value.h"
  54 #include "expmed.h"
  55 #include "dojump.h"
  56 #include "explow.h"
  57 #include "calls.h"
  58 #include "emit-rtl.h"
  59 #include "stmt.h"
  60 #include "expr.h"
  61 #include "libfuncs.h"
  62 #include "recog.h"
  63 #include "diagnostic-core.h"
  64 #include "output.h"
  65 #include "langhooks.h"
  66 #include "predict.h"
  67 #include "insn-codes.h"
  68 #include "optabs.h"
  69 #include "target.h"
  70 #include "cfganal.h"
  71 #include "basic-block.h"
  72 #include "tree-ssa-alias.h"
  73 #include "internal-fn.h"
  74 #include "gimple-expr.h"
  75 #include "is-a.h"
  76 #include "gimple.h"
  77 #include "regs.h"
  78 #include "alloc-pool.h"
  79 #include "pretty-print.h"
  80 #include "params.h"
  81 #include "dumpfile.h"
  82 #include "builtins.h"
  83
  84 \f
  85 /* Functions and data structures for expanding case statements.  */
  86
  87 /* Case label structure, used to hold info on labels within case
  88    statements.  We handle "range" labels; for a single-value label
  89    as in C, the high and low limits are the same.
  90
  91    We start with a vector of case nodes sorted in ascending order, and
  92    the default label as the last element in the vector.  Before expanding
  93    to RTL, we transform this vector into a list linked via the RIGHT
  94    fields in the case_node struct.  Nodes with higher case values are
  95    later in the list.
  96
  97    Switch statements can be output in three forms.  A branch table is
  98    used if there are more than a few labels and the labels are dense
  99    within the range between the smallest and largest case value.  If a
 100    branch table is used, no further manipulations are done with the case
 101    node chain.
 102
 103    The alternative to the use of a branch table is to generate a series
 104    of compare and jump insns.  When that is done, we use the LEFT, RIGHT,
 105    and PARENT fields to hold a binary tree.  Initially the tree is
 106    totally unbalanced, with everything on the right.  We balance the tree
 107    with nodes on the left having lower case values than the parent
 108    and nodes on the right having higher values.  We then output the tree
 109    in order.
 110
 111    For very small, suitable switch statements, we can generate a series
 112    of simple bit test and branches instead.  */
 113
 114 struct case_node
 115 {
 116   struct case_node      *left;  /* Left son in binary tree */
 117   struct case_node      *right; /* Right son in binary tree; also node chain */
 118   struct case_node      *parent; /* Parent of node in binary tree */
 119   tree                  low;    /* Lowest index value for this label */
 120   tree                  high;   /* Highest index value for this label */
 121   tree                  code_label; /* Label to jump to when node matches */
 122   int                   prob; /* Probability of taking this case.  */
 123   /* Probability of reaching subtree rooted at this node */
 124   int                   subtree_prob;
 125 };
 126
 127 typedef struct case_node case_node;
 128 typedef struct case_node *case_node_ptr;
 129
 130 extern basic_block label_to_block_fn (struct function *, tree);
 131 \f
 132 static bool check_unique_operand_names (tree, tree, tree);
 133 static char *resolve_operand_name_1 (char *, tree, tree, tree);
 134 static void balance_case_nodes (case_node_ptr *, case_node_ptr);
 135 static int node_has_low_bound (case_node_ptr, tree);
 136 static int node_has_high_bound (case_node_ptr, tree);
 137 static int node_is_bounded (case_node_ptr, tree);
 138 static void emit_case_nodes (rtx, case_node_ptr, rtx, int, tree);
 139 \f
 140 /* Return the rtx-label that corresponds to a LABEL_DECL,
 141    creating it if necessary.  */
 142
 143 rtx
 144 label_rtx (tree label)
 145 {
 146   gcc_assert (TREE_CODE (label) == LABEL_DECL);
 147
 148   if (!DECL_RTL_SET_P (label))
 149     {
 150       rtx_code_label *r = gen_label_rtx ();
 151       SET_DECL_RTL (label, r);
 152       if (FORCED_LABEL (label) || DECL_NONLOCAL (label))
 153         LABEL_PRESERVE_P (r) = 1;
 154     }
 155
 156   return DECL_RTL (label);
 157 }
 158
 159 /* As above, but also put it on the forced-reference list of the
 160    function that contains it.  */
 161 rtx
 162 force_label_rtx (tree label)
 163 {
 164   rtx_insn *ref = as_a <rtx_insn *> (label_rtx (label));
 165   tree function = decl_function_context (label);
 166
 167   gcc_assert (function);
 168
 169   forced_labels = gen_rtx_INSN_LIST (VOIDmode, ref, forced_labels);
 170   return ref;
 171 }
 172
 173 /* Add an unconditional jump to LABEL as the next sequential instruction.  */
 174
 175 void
 176 emit_jump (rtx label)
 177 {
 178   do_pending_stack_adjust ();
 179   emit_jump_insn (gen_jump (label));
 180   emit_barrier ();
 181 }
 182 \f
 183 /* Handle goto statements and the labels that they can go to.  */
 184
 185 /* Specify the location in the RTL code of a label LABEL,
 186    which is a LABEL_DECL tree node.
 187
 188    This is used for the kind of label that the user can jump to with a
 189    goto statement, and for alternatives of a switch or case statement.
 190    RTL labels generated for loops and conditionals don't go through here;
 191    they are generated directly at the RTL level, by other functions below.
 192
 193    Note that this has nothing to do with defining label *names*.
 194    Languages vary in how they do that and what that even means.  */
 195
 196 void
 197 expand_label (tree label)
 198 {
 199   rtx_insn *label_r = as_a <rtx_insn *> (label_rtx (label));
 200
 201   do_pending_stack_adjust ();
 202   emit_label (label_r);
 203   if (DECL_NAME (label))
 204     LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label));
 205
 206   if (DECL_NONLOCAL (label))
 207     {
 208       expand_builtin_setjmp_receiver (NULL);
 209       nonlocal_goto_handler_labels
 210         = gen_rtx_INSN_LIST (VOIDmode, label_r,
 211                              nonlocal_goto_handler_labels);
 212     }
 213
 214   if (FORCED_LABEL (label))
 215     forced_labels = gen_rtx_INSN_LIST (VOIDmode, label_r, forced_labels);
 216
 217   if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
 218     maybe_set_first_label_num (label_r);
 219 }
 220 \f
 221 /* Parse the output constraint pointed to by *CONSTRAINT_P.  It is the
 222    OPERAND_NUMth output operand, indexed from zero.  There are NINPUTS
 223    inputs and NOUTPUTS outputs to this extended-asm.  Upon return,
 224    *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
 225    memory operand.  Similarly, *ALLOWS_REG will be TRUE iff the
 226    constraint allows the use of a register operand.  And, *IS_INOUT
 227    will be true if the operand is read-write, i.e., if it is used as
 228    an input as well as an output.  If *CONSTRAINT_P is not in
 229    canonical form, it will be made canonical.  (Note that `+' will be
 230    replaced with `=' as part of this process.)
 231
 232    Returns TRUE if all went well; FALSE if an error occurred.  */
 233
 234 bool
 235 parse_output_constraint (const char **constraint_p, int operand_num,
 236                          int ninputs, int noutputs, bool *allows_mem,
 237                          bool *allows_reg, bool *is_inout)
 238 {
 239   const char *constraint = *constraint_p;
 240   const char *p;
 241
 242   /* Assume the constraint doesn't allow the use of either a register
 243      or memory.  */
 244   *allows_mem = false;
 245   *allows_reg = false;
 246
 247   /* Allow the `=' or `+' to not be at the beginning of the string,
 248      since it wasn't explicitly documented that way, and there is a
 249      large body of code that puts it last.  Swap the character to
 250      the front, so as not to uglify any place else.  */
 251   p = strchr (constraint, '=');
 252   if (!p)
 253     p = strchr (constraint, '+');
 254
 255   /* If the string doesn't contain an `=', issue an error
 256      message.  */
 257   if (!p)
 258     {
 259       error ("output operand constraint lacks %<=%>");
 260       return false;
 261     }
 262
 263   /* If the constraint begins with `+', then the operand is both read
 264      from and written to.  */
 265   *is_inout = (*p == '+');
 266
 267   /* Canonicalize the output constraint so that it begins with `='.  */
 268   if (p != constraint || *is_inout)
 269     {
 270       char *buf;
 271       size_t c_len = strlen (constraint);
 272
 273       if (p != constraint)
 274         warning (0, "output constraint %qc for operand %d "
 275                  "is not at the beginning",
 276                  *p, operand_num);
 277
 278       /* Make a copy of the constraint.  */
 279       buf = XALLOCAVEC (char, c_len + 1);
 280       strcpy (buf, constraint);
 281       /* Swap the first character and the `=' or `+'.  */
 282       buf[p - constraint] = buf[0];
 283       /* Make sure the first character is an `='.  (Until we do this,
 284          it might be a `+'.)  */
 285       buf[0] = '=';
 286       /* Replace the constraint with the canonicalized string.  */
 287       *constraint_p = ggc_alloc_string (buf, c_len);
 288       constraint = *constraint_p;
 289     }
 290
 291   /* Loop through the constraint string.  */
 292   for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p))
 293     switch (*p)
 294       {
 295       case '+':
 296       case '=':
 297         error ("operand constraint contains incorrectly positioned "
 298                "%<+%> or %<=%>");
 299         return false;
 300
 301       case '%':
 302         if (operand_num + 1 == ninputs + noutputs)
 303           {
 304             error ("%<%%%> constraint used with last operand");
 305             return false;
 306           }
 307         break;
 308
 309       case '?':  case '!':  case '*':  case '&':  case '#':
 310       case '$':  case '^':
 311       case 'E':  case 'F':  case 'G':  case 'H':
 312       case 's':  case 'i':  case 'n':
 313       case 'I':  case 'J':  case 'K':  case 'L':  case 'M':
 314       case 'N':  case 'O':  case 'P':  case ',':
 315         break;
 316
 317       case '0':  case '1':  case '2':  case '3':  case '4':
 318       case '5':  case '6':  case '7':  case '8':  case '9':
 319       case '[':
 320         error ("matching constraint not valid in output operand");
 321         return false;
 322
 323       case '<':  case '>':
 324         /* ??? Before flow, auto inc/dec insns are not supposed to exist,
 325            excepting those that expand_call created.  So match memory
 326            and hope.  */
 327         *allows_mem = true;
 328         break;
 329
 330       case 'g':  case 'X':
 331         *allows_reg = true;
 332         *allows_mem = true;
 333         break;
 334
 335       default:
 336         if (!ISALPHA (*p))
 337           break;
 338         enum constraint_num cn = lookup_constraint (p);
 339         if (reg_class_for_constraint (cn) != NO_REGS
 340             || insn_extra_address_constraint (cn))
 341           *allows_reg = true;
 342         else if (insn_extra_memory_constraint (cn))
 343           *allows_mem = true;
 344         else
 345           {
 346             /* Otherwise we can't assume anything about the nature of
 347                the constraint except that it isn't purely registers.
 348                Treat it like "g" and hope for the best.  */
 349             *allows_reg = true;
 350             *allows_mem = true;
 351           }
 352         break;
 353       }
 354
 355   return true;
 356 }
 357
 358 /* Similar, but for input constraints.  */
 359
 360 bool
 361 parse_input_constraint (const char **constraint_p, int input_num,
 362                         int ninputs, int noutputs, int ninout,
 363                         const char * const * constraints,
 364                         bool *allows_mem, bool *allows_reg)
 365 {
 366   const char *constraint = *constraint_p;
 367   const char *orig_constraint = constraint;
 368   size_t c_len = strlen (constraint);
 369   size_t j;
 370   bool saw_match = false;
 371
 372   /* Assume the constraint doesn't allow the use of either
 373      a register or memory.  */
 374   *allows_mem = false;
 375   *allows_reg = false;
 376
 377   /* Make sure constraint has neither `=', `+', nor '&'.  */
 378
 379   for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
 380     switch (constraint[j])
 381       {
 382       case '+':  case '=':  case '&':
 383         if (constraint == orig_constraint)
 384           {
 385             error ("input operand constraint contains %qc", constraint[j]);
 386             return false;
 387           }
 388         break;
 389
 390       case '%':
 391         if (constraint == orig_constraint
 392             && input_num + 1 == ninputs - ninout)
 393           {
 394             error ("%<%%%> constraint used with last operand");
 395             return false;
 396           }
 397         break;
 398
 399       case '<':  case '>':
 400       case '?':  case '!':  case '*':  case '#':
 401       case '$':  case '^':
 402       case 'E':  case 'F':  case 'G':  case 'H':
 403       case 's':  case 'i':  case 'n':
 404       case 'I':  case 'J':  case 'K':  case 'L':  case 'M':
 405       case 'N':  case 'O':  case 'P':  case ',':
 406         break;
 407
 408         /* Whether or not a numeric constraint allows a register is
 409            decided by the matching constraint, and so there is no need
 410            to do anything special with them.  We must handle them in
 411            the default case, so that we don't unnecessarily force
 412            operands to memory.  */
 413       case '0':  case '1':  case '2':  case '3':  case '4':
 414       case '5':  case '6':  case '7':  case '8':  case '9':
 415         {
 416           char *end;
 417           unsigned long match;
 418
 419           saw_match = true;
 420
 421           match = strtoul (constraint + j, &end, 10);
 422           if (match >= (unsigned long) noutputs)
 423             {
 424               error ("matching constraint references invalid operand number");
 425               return false;
 426             }
 427
 428           /* Try and find the real constraint for this dup.  Only do this
 429              if the matching constraint is the only alternative.  */
 430           if (*end == '\0'
 431               && (j == 0 || (j == 1 && constraint[0] == '%')))
 432             {
 433               constraint = constraints[match];
 434               *constraint_p = constraint;
 435               c_len = strlen (constraint);
 436               j = 0;
 437               /* ??? At the end of the loop, we will skip the first part of
 438                  the matched constraint.  This assumes not only that the
 439                  other constraint is an output constraint, but also that
 440                  the '=' or '+' come first.  */
 441               break;
 442             }
 443           else
 444             j = end - constraint;
 445           /* Anticipate increment at end of loop.  */
 446           j--;
 447         }
 448         /* Fall through.  */
 449
 450       case 'g':  case 'X':
 451         *allows_reg = true;
 452         *allows_mem = true;
 453         break;
 454
 455       default:
 456         if (! ISALPHA (constraint[j]))
 457           {
 458             error ("invalid punctuation %qc in constraint", constraint[j]);
 459             return false;
 460           }
 461         enum constraint_num cn = lookup_constraint (constraint + j);
 462         if (reg_class_for_constraint (cn) != NO_REGS
 463             || insn_extra_address_constraint (cn))
 464           *allows_reg = true;
 465         else if (insn_extra_memory_constraint (cn))
 466           *allows_mem = true;
 467         else
 468           {
 469             /* Otherwise we can't assume anything about the nature of
 470                the constraint except that it isn't purely registers.
 471                Treat it like "g" and hope for the best.  */
 472             *allows_reg = true;
 473             *allows_mem = true;
 474           }
 475         break;
 476       }
 477
 478   if (saw_match && !*allows_reg)
 479     warning (0, "matching constraint does not allow a register");
 480
 481   return true;
 482 }
 483
 484 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
 485    can be an asm-declared register.  Called via walk_tree.  */
 486
 487 static tree
 488 decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED,
 489                               void *data)
 490 {
 491   tree decl = *declp;
 492   const HARD_REG_SET *const regs = (const HARD_REG_SET *) data;
 493
 494   if (TREE_CODE (decl) == VAR_DECL)
 495     {
 496       if (DECL_HARD_REGISTER (decl)
 497           && REG_P (DECL_RTL (decl))
 498           && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
 499         {
 500           rtx reg = DECL_RTL (decl);
 501
 502           if (overlaps_hard_reg_set_p (*regs, GET_MODE (reg), REGNO (reg)))
 503             return decl;
 504         }
 505       walk_subtrees = 0;
 506     }
 507   else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL)
 508     walk_subtrees = 0;
 509   return NULL_TREE;
 510 }
 511
 512 /* If there is an overlap between *REGS and DECL, return the first overlap
 513    found.  */
 514 tree
 515 tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs)
 516 {
 517   return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL);
 518 }
 519
 520
 521 /* A subroutine of expand_asm_operands.  Check that all operand names
 522    are unique.  Return true if so.  We rely on the fact that these names
 523    are identifiers, and so have been canonicalized by get_identifier,
 524    so all we need are pointer comparisons.  */
 525
 526 static bool
 527 check_unique_operand_names (tree outputs, tree inputs, tree labels)
 528 {
 529   tree i, j, i_name = NULL_TREE;
 530
 531   for (i = outputs; i ; i = TREE_CHAIN (i))
 532     {
 533       i_name = TREE_PURPOSE (TREE_PURPOSE (i));
 534       if (! i_name)
 535         continue;
 536
 537       for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
 538         if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
 539           goto failure;
 540     }
 541
 542   for (i = inputs; i ; i = TREE_CHAIN (i))
 543     {
 544       i_name = TREE_PURPOSE (TREE_PURPOSE (i));
 545       if (! i_name)
 546         continue;
 547
 548       for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
 549         if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
 550           goto failure;
 551       for (j = outputs; j ; j = TREE_CHAIN (j))
 552         if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
 553           goto failure;
 554     }
 555
 556   for (i = labels; i ; i = TREE_CHAIN (i))
 557     {
 558       i_name = TREE_PURPOSE (i);
 559       if (! i_name)
 560         continue;
 561
 562       for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
 563         if (simple_cst_equal (i_name, TREE_PURPOSE (j)))
 564           goto failure;
 565       for (j = inputs; j ; j = TREE_CHAIN (j))
 566         if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
 567           goto failure;
 568     }
 569
 570   return true;
 571
 572  failure:
 573   error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name));
 574   return false;
 575 }
 576
 577 /* A subroutine of expand_asm_operands.  Resolve the names of the operands
 578    in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
 579    STRING and in the constraints to those numbers.  */
 580
 581 tree
 582 resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels)
 583 {
 584   char *buffer;
 585   char *p;
 586   const char *c;
 587   tree t;
 588
 589   check_unique_operand_names (outputs, inputs, labels);
 590
 591   /* Substitute [<name>] in input constraint strings.  There should be no
 592      named operands in output constraints.  */
 593   for (t = inputs; t ; t = TREE_CHAIN (t))
 594     {
 595       c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
 596       if (strchr (c, '[') != NULL)
 597         {
 598           p = buffer = xstrdup (c);
 599           while ((p = strchr (p, '[')) != NULL)
 600             p = resolve_operand_name_1 (p, outputs, inputs, NULL);
 601           TREE_VALUE (TREE_PURPOSE (t))
 602             = build_string (strlen (buffer), buffer);
 603           free (buffer);
 604         }
 605     }
 606
 607   /* Now check for any needed substitutions in the template.  */
 608   c = TREE_STRING_POINTER (string);
 609   while ((c = strchr (c, '%')) != NULL)
 610     {
 611       if (c[1] == '[')
 612         break;
 613       else if (ISALPHA (c[1]) && c[2] == '[')
 614         break;
 615       else
 616         {
 617           c += 1 + (c[1] == '%');
 618           continue;
 619         }
 620     }
 621
 622   if (c)
 623     {
 624       /* OK, we need to make a copy so we can perform the substitutions.
 625          Assume that we will not need extra space--we get to remove '['
 626          and ']', which means we cannot have a problem until we have more
 627          than 999 operands.  */
 628       buffer = xstrdup (TREE_STRING_POINTER (string));
 629       p = buffer + (c - TREE_STRING_POINTER (string));
 630
 631       while ((p = strchr (p, '%')) != NULL)
 632         {
 633           if (p[1] == '[')
 634             p += 1;
 635           else if (ISALPHA (p[1]) && p[2] == '[')
 636             p += 2;
 637           else
 638             {
 639               p += 1 + (p[1] == '%');
 640               continue;
 641             }
 642
 643           p = resolve_operand_name_1 (p, outputs, inputs, labels);
 644         }
 645
 646       string = build_string (strlen (buffer), buffer);
 647       free (buffer);
 648     }
 649
 650   return string;
 651 }
 652
 653 /* A subroutine of resolve_operand_names.  P points to the '[' for a
 654    potential named operand of the form [<name>].  In place, replace
 655    the name and brackets with a number.  Return a pointer to the
 656    balance of the string after substitution.  */
 657
 658 static char *
 659 resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels)
 660 {
 661   char *q;
 662   int op;
 663   tree t;
 664
 665   /* Collect the operand name.  */
 666   q = strchr (++p, ']');
 667   if (!q)
 668     {
 669       error ("missing close brace for named operand");
 670       return strchr (p, '\0');
 671     }
 672   *q = '\0';
 673
 674   /* Resolve the name to a number.  */
 675   for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
 676     {
 677       tree name = TREE_PURPOSE (TREE_PURPOSE (t));
 678       if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
 679         goto found;
 680     }
 681   for (t = inputs; t ; t = TREE_CHAIN (t), op++)
 682     {
 683       tree name = TREE_PURPOSE (TREE_PURPOSE (t));
 684       if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
 685         goto found;
 686     }
 687   for (t = labels; t ; t = TREE_CHAIN (t), op++)
 688     {
 689       tree name = TREE_PURPOSE (t);
 690       if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
 691         goto found;
 692     }
 693
 694   error ("undefined named operand %qs", identifier_to_locale (p));
 695   op = 0;
 696
 697  found:
 698   /* Replace the name with the number.  Unfortunately, not all libraries
 699      get the return value of sprintf correct, so search for the end of the
 700      generated string by hand.  */
 701   sprintf (--p, "%d", op);
 702   p = strchr (p, '\0');
 703
 704   /* Verify the no extra buffer space assumption.  */
 705   gcc_assert (p <= q);
 706
 707   /* Shift the rest of the buffer down to fill the gap.  */
 708   memmove (p, q + 1, strlen (q + 1) + 1);
 709
 710   return p;
 711 }
 712 \f
 713
 714 /* Generate RTL to return directly from the current function.
 715    (That is, we bypass any return value.)  */
 716
 717 void
 718 expand_naked_return (void)
 719 {
 720   rtx end_label;
 721
 722   clear_pending_stack_adjust ();
 723   do_pending_stack_adjust ();
 724
 725   end_label = naked_return_label;
 726   if (end_label == 0)
 727     end_label = naked_return_label = gen_label_rtx ();
 728
 729   emit_jump (end_label);
 730 }
 731
 732 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
 733    is the probability of jumping to LABEL.  */
 734 static void
 735 do_jump_if_equal (machine_mode mode, rtx op0, rtx op1, rtx label,
 736                   int unsignedp, int prob)
 737 {
 738   gcc_assert (prob <= REG_BR_PROB_BASE);
 739   do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
 740                            NULL_RTX, NULL_RTX, label, prob);
 741 }
 742 \f
 743 /* Do the insertion of a case label into case_list.  The labels are
 744    fed to us in descending order from the sorted vector of case labels used
 745    in the tree part of the middle end.  So the list we construct is
 746    sorted in ascending order.
 747
 748    LABEL is the case label to be inserted. LOW and HIGH are the bounds
 749    against which the index is compared to jump to LABEL and PROB is the
 750    estimated probability LABEL is reached from the switch statement.  */
 751
 752 static struct case_node *
 753 add_case_node (struct case_node *head, tree low, tree high,
 754                tree label, int prob, alloc_pool case_node_pool)
 755 {
 756   struct case_node *r;
 757
 758   gcc_checking_assert (low);
 759   gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high)));
 760
 761   /* Add this label to the chain.  */
 762   r = (struct case_node *) pool_alloc (case_node_pool);
 763   r->low = low;
 764   r->high = high;
 765   r->code_label = label;
 766   r->parent = r->left = NULL;
 767   r->prob = prob;
 768   r->subtree_prob = prob;
 769   r->right = head;
 770   return r;
 771 }
 772 \f
 773 /* Dump ROOT, a list or tree of case nodes, to file.  */
 774
 775 static void
 776 dump_case_nodes (FILE *f, struct case_node *root,
 777                  int indent_step, int indent_level)
 778 {
 779   if (root == 0)
 780     return;
 781   indent_level++;
 782
 783   dump_case_nodes (f, root->left, indent_step, indent_level);
 784
 785   fputs (";; ", f);
 786   fprintf (f, "%*s", indent_step * indent_level, "");
 787   print_dec (root->low, f, TYPE_SIGN (TREE_TYPE (root->low)));
 788   if (!tree_int_cst_equal (root->low, root->high))
 789     {
 790       fprintf (f, " ... ");
 791       print_dec (root->high, f, TYPE_SIGN (TREE_TYPE (root->high)));
 792     }
 793   fputs ("\n", f);
 794
 795   dump_case_nodes (f, root->right, indent_step, indent_level);
 796 }
 797 \f
 798 #ifndef HAVE_casesi
 799 #define HAVE_casesi 0
 800 #endif
 801
 802 #ifndef HAVE_tablejump
 803 #define HAVE_tablejump 0
 804 #endif
 805
 806 /* Return the smallest number of different values for which it is best to use a
 807    jump-table instead of a tree of conditional branches.  */
 808
 809 static unsigned int
 810 case_values_threshold (void)
 811 {
 812   unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
 813
 814   if (threshold == 0)
 815     threshold = targetm.case_values_threshold ();
 816
 817   return threshold;
 818 }
 819
 820 /* Return true if a switch should be expanded as a decision tree.
 821    RANGE is the difference between highest and lowest case.
 822    UNIQ is number of unique case node targets, not counting the default case.
 823    COUNT is the number of comparisons needed, not counting the default case.  */
 824
 825 static bool
 826 expand_switch_as_decision_tree_p (tree range,
 827                                   unsigned int uniq ATTRIBUTE_UNUSED,
 828                                   unsigned int count)
 829 {
 830   int max_ratio;
 831
 832   /* If neither casesi or tablejump is available, or flag_jump_tables
 833      over-ruled us, we really have no choice.  */
 834   if (!HAVE_casesi && !HAVE_tablejump)
 835     return true;
 836   if (!flag_jump_tables)
 837     return true;
 838 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
 839   if (flag_pic)
 840     return true;
 841 #endif
 842
 843   /* If the switch is relatively small such that the cost of one
 844      indirect jump on the target are higher than the cost of a
 845      decision tree, go with the decision tree.
 846
 847      If range of values is much bigger than number of values,
 848      or if it is too large to represent in a HOST_WIDE_INT,
 849      make a sequence of conditional branches instead of a dispatch.
 850
 851      The definition of "much bigger" depends on whether we are
 852      optimizing for size or for speed.  If the former, the maximum
 853      ratio range/count = 3, because this was found to be the optimal
 854      ratio for size on i686-pc-linux-gnu, see PR11823.  The ratio
 855      10 is much older, and was probably selected after an extensive
 856      benchmarking investigation on numerous platforms.  Or maybe it
 857      just made sense to someone at some point in the history of GCC,
 858      who knows...  */
 859   max_ratio = optimize_insn_for_size_p () ? 3 : 10;
 860   if (count < case_values_threshold ()
 861       || ! tree_fits_uhwi_p (range)
 862       || compare_tree_int (range, max_ratio * count) > 0)
 863     return true;
 864
 865   return false;
 866 }
 867
 868 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
 869    one of the labels in CASE_LIST or to the DEFAULT_LABEL.
 870    DEFAULT_PROB is the estimated probability that it jumps to
 871    DEFAULT_LABEL.
 872
 873    We generate a binary decision tree to select the appropriate target
 874    code.  This is done as follows:
 875
 876      If the index is a short or char that we do not have
 877      an insn to handle comparisons directly, convert it to
 878      a full integer now, rather than letting each comparison
 879      generate the conversion.
 880
 881      Load the index into a register.
 882
 883      The list of cases is rearranged into a binary tree,
 884      nearly optimal assuming equal probability for each case.
 885
 886      The tree is transformed into RTL, eliminating redundant
 887      test conditions at the same time.
 888
 889      If program flow could reach the end of the decision tree
 890      an unconditional jump to the default code is emitted.
 891
 892    The above process is unaware of the CFG.  The caller has to fix up
 893    the CFG itself.  This is done in cfgexpand.c.  */
 894
 895 static void
 896 emit_case_decision_tree (tree index_expr, tree index_type,
 897                          struct case_node *case_list, rtx default_label,
 898                          int default_prob)
 899 {
 900   rtx index = expand_normal (index_expr);
 901
 902   if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
 903       && ! have_insn_for (COMPARE, GET_MODE (index)))
 904     {
 905       int unsignedp = TYPE_UNSIGNED (index_type);
 906       machine_mode wider_mode;
 907       for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
 908            wider_mode = GET_MODE_WIDER_MODE (wider_mode))
 909         if (have_insn_for (COMPARE, wider_mode))
 910           {
 911             index = convert_to_mode (wider_mode, index, unsignedp);
 912             break;
 913           }
 914     }
 915
 916   do_pending_stack_adjust ();
 917
 918   if (MEM_P (index))
 919     {
 920       index = copy_to_reg (index);
 921       if (TREE_CODE (index_expr) == SSA_NAME)
 922         set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr), index);
 923     }
 924
 925   balance_case_nodes (&case_list, NULL);
 926
 927   if (dump_file && (dump_flags & TDF_DETAILS))
 928     {
 929       int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
 930       fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
 931       dump_case_nodes (dump_file, case_list, indent_step, 0);
 932     }
 933
 934   emit_case_nodes (index, case_list, default_label, default_prob, index_type);
 935   if (default_label)
 936     emit_jump (default_label);
 937 }
 938
 939 /* Return the sum of probabilities of outgoing edges of basic block BB.  */
 940
 941 static int
 942 get_outgoing_edge_probs (basic_block bb)
 943 {
 944   edge e;
 945   edge_iterator ei;
 946   int prob_sum = 0;
 947   if (!bb)
 948     return 0;
 949   FOR_EACH_EDGE (e, ei, bb->succs)
 950     prob_sum += e->probability;
 951   return prob_sum;
 952 }
 953
 954 /* Computes the conditional probability of jumping to a target if the branch
 955    instruction is executed.
 956    TARGET_PROB is the estimated probability of jumping to a target relative
 957    to some basic block BB.
 958    BASE_PROB is the probability of reaching the branch instruction relative
 959    to the same basic block BB.  */
 960
 961 static inline int
 962 conditional_probability (int target_prob, int base_prob)
 963 {
 964   if (base_prob > 0)
 965     {
 966       gcc_assert (target_prob >= 0);
 967       gcc_assert (target_prob <= base_prob);
 968       return GCOV_COMPUTE_SCALE (target_prob, base_prob);
 969     }
 970   return -1;
 971 }
 972
 973 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
 974    one of the labels in CASE_LIST or to the DEFAULT_LABEL.
 975    MINVAL, MAXVAL, and RANGE are the extrema and range of the case
 976    labels in CASE_LIST. STMT_BB is the basic block containing the statement.
 977
 978    First, a jump insn is emitted.  First we try "casesi".  If that
 979    fails, try "tablejump".   A target *must* have one of them (or both).
 980
 981    Then, a table with the target labels is emitted.
 982
 983    The process is unaware of the CFG.  The caller has to fix up
 984    the CFG itself.  This is done in cfgexpand.c.  */
 985
 986 static void
 987 emit_case_dispatch_table (tree index_expr, tree index_type,
 988                           struct case_node *case_list, rtx default_label,
 989                           tree minval, tree maxval, tree range,
 990                           basic_block stmt_bb)
 991 {
 992   int i, ncases;
 993   struct case_node *n;
 994   rtx *labelvec;
 995   rtx fallback_label = label_rtx (case_list->code_label);
 996   rtx_code_label *table_label = gen_label_rtx ();
 997   bool has_gaps = false;
 998   edge default_edge = stmt_bb ? EDGE_SUCC (stmt_bb, 0) : NULL;
 999   int default_prob = default_edge ? default_edge->probability : 0;
1000   int base = get_outgoing_edge_probs (stmt_bb);
1001   bool try_with_tablejump = false;
1002
1003   int new_default_prob = conditional_probability (default_prob,
1004                                                   base);
1005
1006   if (! try_casesi (index_type, index_expr, minval, range,
1007                     table_label, default_label, fallback_label,
1008                     new_default_prob))
1009     {
1010       /* Index jumptables from zero for suitable values of minval to avoid
1011          a subtraction.  For the rationale see:
1012          "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html".  */
1013       if (optimize_insn_for_speed_p ()
1014           && compare_tree_int (minval, 0) > 0
1015           && compare_tree_int (minval, 3) < 0)
1016         {
1017           minval = build_int_cst (index_type, 0);
1018           range = maxval;
1019           has_gaps = true;
1020         }
1021       try_with_tablejump = true;
1022     }
1023
1024   /* Get table of labels to jump to, in order of case index.  */
1025
1026   ncases = tree_to_shwi (range) + 1;
1027   labelvec = XALLOCAVEC (rtx, ncases);
1028   memset (labelvec, 0, ncases * sizeof (rtx));
1029
1030   for (n = case_list; n; n = n->right)
1031     {
1032       /* Compute the low and high bounds relative to the minimum
1033          value since that should fit in a HOST_WIDE_INT while the
1034          actual values may not.  */
1035       HOST_WIDE_INT i_low
1036         = tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
1037                                      n->low, minval));
1038       HOST_WIDE_INT i_high
1039         = tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
1040                                      n->high, minval));
1041       HOST_WIDE_INT i;
1042
1043       for (i = i_low; i <= i_high; i ++)
1044         labelvec[i]
1045           = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
1046     }
1047
1048   /* Fill in the gaps with the default.  We may have gaps at
1049      the beginning if we tried to avoid the minval subtraction,
1050      so substitute some label even if the default label was
1051      deemed unreachable.  */
1052   if (!default_label)
1053     default_label = fallback_label;
1054   for (i = 0; i < ncases; i++)
1055     if (labelvec[i] == 0)
1056       {
1057         has_gaps = true;
1058         labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
1059       }
1060
1061   if (has_gaps)
1062     {
1063       /* There is at least one entry in the jump table that jumps
1064          to default label. The default label can either be reached
1065          through the indirect jump or the direct conditional jump
1066          before that. Split the probability of reaching the
1067          default label among these two jumps.  */
1068       new_default_prob = conditional_probability (default_prob/2,
1069                                                   base);
1070       default_prob /= 2;
1071       base -= default_prob;
1072     }
1073   else
1074     {
1075       base -= default_prob;
1076       default_prob = 0;
1077     }
1078
1079   if (default_edge)
1080     default_edge->probability = default_prob;
1081
1082   /* We have altered the probability of the default edge. So the probabilities
1083      of all other edges need to be adjusted so that it sums up to
1084      REG_BR_PROB_BASE.  */
1085   if (base)
1086     {
1087       edge e;
1088       edge_iterator ei;
1089       FOR_EACH_EDGE (e, ei, stmt_bb->succs)
1090         e->probability = GCOV_COMPUTE_SCALE (e->probability,  base);
1091     }
1092
1093   if (try_with_tablejump)
1094     {
1095       bool ok = try_tablejump (index_type, index_expr, minval, range,
1096                                table_label, default_label, new_default_prob);
1097       gcc_assert (ok);
1098     }
1099   /* Output the table.  */
1100   emit_label (table_label);
1101
1102   if (CASE_VECTOR_PC_RELATIVE || flag_pic)
1103     emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
1104                                                  gen_rtx_LABEL_REF (Pmode,
1105                                                                     table_label),
1106                                                  gen_rtvec_v (ncases, labelvec),
1107                                                  const0_rtx, const0_rtx));
1108   else
1109     emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
1110                                             gen_rtvec_v (ncases, labelvec)));
1111
1112   /* Record no drop-through after the table.  */
1113   emit_barrier ();
1114 }
1115
1116 /* Reset the aux field of all outgoing edges of basic block BB.  */
1117
1118 static inline void
1119 reset_out_edges_aux (basic_block bb)
1120 {
1121   edge e;
1122   edge_iterator ei;
1123   FOR_EACH_EDGE (e, ei, bb->succs)
1124     e->aux = (void *)0;
1125 }
1126
1127 /* Compute the number of case labels that correspond to each outgoing edge of
1128    STMT. Record this information in the aux field of the edge.  */
1129
1130 static inline void
1131 compute_cases_per_edge (gswitch *stmt)
1132 {
1133   basic_block bb = gimple_bb (stmt);
1134   reset_out_edges_aux (bb);
1135   int ncases = gimple_switch_num_labels (stmt);
1136   for (int i = ncases - 1; i >= 1; --i)
1137     {
1138       tree elt = gimple_switch_label (stmt, i);
1139       tree lab = CASE_LABEL (elt);
1140       basic_block case_bb = label_to_block_fn (cfun, lab);
1141       edge case_edge = find_edge (bb, case_bb);
1142       case_edge->aux = (void *)((intptr_t)(case_edge->aux) + 1);
1143     }
1144 }
1145
1146 /* Terminate a case (Pascal/Ada) or switch (C) statement
1147    in which ORIG_INDEX is the expression to be tested.
1148    If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
1149    type as given in the source before any compiler conversions.
1150    Generate the code to test it and jump to the right place.  */
1151
1152 void
1153 expand_case (gswitch *stmt)
1154 {
1155   tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
1156   rtx default_label = NULL_RTX;
1157   unsigned int count, uniq;
1158   int i;
1159   int ncases = gimple_switch_num_labels (stmt);
1160   tree index_expr = gimple_switch_index (stmt);
1161   tree index_type = TREE_TYPE (index_expr);
1162   tree elt;
1163   basic_block bb = gimple_bb (stmt);
1164
1165   /* A list of case labels; it is first built as a list and it may then
1166      be rearranged into a nearly balanced binary tree.  */
1167   struct case_node *case_list = 0;
1168
1169   /* A pool for case nodes.  */
1170   alloc_pool case_node_pool;
1171
1172   /* An ERROR_MARK occurs for various reasons including invalid data type.
1173      ??? Can this still happen, with GIMPLE and all?  */
1174   if (index_type == error_mark_node)
1175     return;
1176
1177   /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
1178      expressions being INTEGER_CST.  */
1179   gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
1180
1181   case_node_pool = create_alloc_pool ("struct case_node pool",
1182                                       sizeof (struct case_node),
1183                                       100);
1184
1185   do_pending_stack_adjust ();
1186
1187   /* Find the default case target label.  */
1188   default_label = label_rtx (CASE_LABEL (gimple_switch_default_label (stmt)));
1189   edge default_edge = EDGE_SUCC (bb, 0);
1190   int default_prob = default_edge->probability;
1191
1192   /* Get upper and lower bounds of case values.  */
1193   elt = gimple_switch_label (stmt, 1);
1194   minval = fold_convert (index_type, CASE_LOW (elt));
1195   elt = gimple_switch_label (stmt, ncases - 1);
1196   if (CASE_HIGH (elt))
1197     maxval = fold_convert (index_type, CASE_HIGH (elt));
1198   else
1199     maxval = fold_convert (index_type, CASE_LOW (elt));
1200
1201   /* Compute span of values.  */
1202   range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
1203
1204   /* Listify the labels queue and gather some numbers to decide
1205      how to expand this switch().  */
1206   uniq = 0;
1207   count = 0;
1208   hash_set<tree> seen_labels;
1209   compute_cases_per_edge (stmt);
1210
1211   for (i = ncases - 1; i >= 1; --i)
1212     {
1213       elt = gimple_switch_label (stmt, i);
1214       tree low = CASE_LOW (elt);
1215       gcc_assert (low);
1216       tree high = CASE_HIGH (elt);
1217       gcc_assert (! high || tree_int_cst_lt (low, high));
1218       tree lab = CASE_LABEL (elt);
1219
1220       /* Count the elements.
1221          A range counts double, since it requires two compares.  */
1222       count++;
1223       if (high)
1224         count++;
1225
1226       /* If we have not seen this label yet, then increase the
1227          number of unique case node targets seen.  */
1228       if (!seen_labels.add (lab))
1229         uniq++;
1230
1231       /* The bounds on the case range, LOW and HIGH, have to be converted
1232          to case's index type TYPE.  Note that the original type of the
1233          case index in the source code is usually "lost" during
1234          gimplification due to type promotion, but the case labels retain the
1235          original type.  Make sure to drop overflow flags.  */
1236       low = fold_convert (index_type, low);
1237       if (TREE_OVERFLOW (low))
1238         low = wide_int_to_tree (index_type, low);
1239
1240       /* The canonical from of a case label in GIMPLE is that a simple case
1241          has an empty CASE_HIGH.  For the casesi and tablejump expanders,
1242          the back ends want simple cases to have high == low.  */
1243       if (! high)
1244         high = low;
1245       high = fold_convert (index_type, high);
1246       if (TREE_OVERFLOW (high))
1247         high = wide_int_to_tree (index_type, high);
1248
1249       basic_block case_bb = label_to_block_fn (cfun, lab);
1250       edge case_edge = find_edge (bb, case_bb);
1251       case_list = add_case_node (
1252           case_list, low, high, lab,
1253           case_edge->probability / (intptr_t)(case_edge->aux),
1254           case_node_pool);
1255     }
1256   reset_out_edges_aux (bb);
1257
1258   /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
1259      destination, such as one with a default case only.
1260      It also removes cases that are out of range for the switch
1261      type, so we should never get a zero here.  */
1262   gcc_assert (count > 0);
1263
1264   rtx_insn *before_case = get_last_insn ();
1265
1266   /* Decide how to expand this switch.
1267      The two options at this point are a dispatch table (casesi or
1268      tablejump) or a decision tree.  */
1269
1270   if (expand_switch_as_decision_tree_p (range, uniq, count))
1271     emit_case_decision_tree (index_expr, index_type,
1272                              case_list, default_label,
1273                              default_prob);
1274   else
1275     emit_case_dispatch_table (index_expr, index_type,
1276                               case_list, default_label,
1277                               minval, maxval, range, bb);
1278
1279   reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
1280
1281   free_temp_slots ();
1282   free_alloc_pool (case_node_pool);
1283 }
1284
1285 /* Expand the dispatch to a short decrement chain if there are few cases
1286    to dispatch to.  Likewise if neither casesi nor tablejump is available,
1287    or if flag_jump_tables is set.  Otherwise, expand as a casesi or a
1288    tablejump.  The index mode is always the mode of integer_type_node.
1289    Trap if no case matches the index.
1290
1291    DISPATCH_INDEX is the index expression to switch on.  It should be a
1292    memory or register operand.
1293
1294    DISPATCH_TABLE is a set of case labels.  The set should be sorted in
1295    ascending order, be contiguous, starting with value 0, and contain only
1296    single-valued case labels.  */
1297
1298 void
1299 expand_sjlj_dispatch_table (rtx dispatch_index,
1300                             vec<tree> dispatch_table)
1301 {
1302   tree index_type = integer_type_node;
1303   machine_mode index_mode = TYPE_MODE (index_type);
1304
1305   int ncases = dispatch_table.length ();
1306
1307   do_pending_stack_adjust ();
1308   rtx_insn *before_case = get_last_insn ();
1309
1310   /* Expand as a decrement-chain if there are 5 or fewer dispatch
1311      labels.  This covers more than 98% of the cases in libjava,
1312      and seems to be a reasonable compromise between the "old way"
1313      of expanding as a decision tree or dispatch table vs. the "new
1314      way" with decrement chain or dispatch table.  */
1315   if (dispatch_table.length () <= 5
1316       || (!HAVE_casesi && !HAVE_tablejump)
1317       || !flag_jump_tables)
1318     {
1319       /* Expand the dispatch as a decrement chain:
1320
1321          "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1322
1323          ==>
1324
1325          if (index == 0) do_0; else index--;
1326          if (index == 0) do_1; else index--;
1327          ...
1328          if (index == 0) do_N; else index--;
1329
1330          This is more efficient than a dispatch table on most machines.
1331          The last "index--" is redundant but the code is trivially dead
1332          and will be cleaned up by later passes.  */
1333       rtx index = copy_to_mode_reg (index_mode, dispatch_index);
1334       rtx zero = CONST0_RTX (index_mode);
1335       for (int i = 0; i < ncases; i++)
1336         {
1337           tree elt = dispatch_table[i];
1338           rtx lab = label_rtx (CASE_LABEL (elt));
1339           do_jump_if_equal (index_mode, index, zero, lab, 0, -1);
1340           force_expand_binop (index_mode, sub_optab,
1341                               index, CONST1_RTX (index_mode),
1342                               index, 0, OPTAB_DIRECT);
1343         }
1344     }
1345   else
1346     {
1347       /* Similar to expand_case, but much simpler.  */
1348       struct case_node *case_list = 0;
1349       alloc_pool case_node_pool = create_alloc_pool ("struct sjlj_case pool",
1350                                                      sizeof (struct case_node),
1351                                                      ncases);
1352       tree index_expr = make_tree (index_type, dispatch_index);
1353       tree minval = build_int_cst (index_type, 0);
1354       tree maxval = CASE_LOW (dispatch_table.last ());
1355       tree range = maxval;
1356       rtx_code_label *default_label = gen_label_rtx ();
1357
1358       for (int i = ncases - 1; i >= 0; --i)
1359         {
1360           tree elt = dispatch_table[i];
1361           tree low = CASE_LOW (elt);
1362           tree lab = CASE_LABEL (elt);
1363           case_list = add_case_node (case_list, low, low, lab, 0, case_node_pool);
1364         }
1365
1366       emit_case_dispatch_table (index_expr, index_type,
1367                                 case_list, default_label,
1368                                 minval, maxval, range,
1369                                 BLOCK_FOR_INSN (before_case));
1370       emit_label (default_label);
1371       free_alloc_pool (case_node_pool);
1372     }
1373
1374   /* Dispatching something not handled?  Trap!  */
1375   expand_builtin_trap ();
1376
1377   reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
1378
1379   free_temp_slots ();
1380 }
1381
1382 \f
1383 /* Take an ordered list of case nodes
1384    and transform them into a near optimal binary tree,
1385    on the assumption that any target code selection value is as
1386    likely as any other.
1387
1388    The transformation is performed by splitting the ordered
1389    list into two equal sections plus a pivot.  The parts are
1390    then attached to the pivot as left and right branches.  Each
1391    branch is then transformed recursively.  */
1392
1393 static void
1394 balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
1395 {
1396   case_node_ptr np;
1397
1398   np = *head;
1399   if (np)
1400     {
1401       int i = 0;
1402       int ranges = 0;
1403       case_node_ptr *npp;
1404       case_node_ptr left;
1405
1406       /* Count the number of entries on branch.  Also count the ranges.  */
1407
1408       while (np)
1409         {
1410           if (!tree_int_cst_equal (np->low, np->high))
1411             ranges++;
1412
1413           i++;
1414           np = np->right;
1415         }
1416
1417       if (i > 2)
1418         {
1419           /* Split this list if it is long enough for that to help.  */
1420           npp = head;
1421           left = *npp;
1422
1423           /* If there are just three nodes, split at the middle one.  */
1424           if (i == 3)
1425             npp = &(*npp)->right;
1426           else
1427             {
1428               /* Find the place in the list that bisects the list's total cost,
1429                  where ranges count as 2.
1430                  Here I gets half the total cost.  */
1431               i = (i + ranges + 1) / 2;
1432               while (1)
1433                 {
1434                   /* Skip nodes while their cost does not reach that amount.  */
1435                   if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
1436                     i--;
1437                   i--;
1438                   if (i <= 0)
1439                     break;
1440                   npp = &(*npp)->right;
1441                 }
1442             }
1443           *head = np = *npp;
1444           *npp = 0;
1445           np->parent = parent;
1446           np->left = left;
1447
1448           /* Optimize each of the two split parts.  */
1449           balance_case_nodes (&np->left, np);
1450           balance_case_nodes (&np->right, np);
1451           np->subtree_prob = np->prob;
1452           np->subtree_prob += np->left->subtree_prob;
1453           np->subtree_prob += np->right->subtree_prob;
1454         }
1455       else
1456         {
1457           /* Else leave this branch as one level,
1458              but fill in `parent' fields.  */
1459           np = *head;
1460           np->parent = parent;
1461           np->subtree_prob = np->prob;
1462           for (; np->right; np = np->right)
1463             {
1464               np->right->parent = np;
1465               (*head)->subtree_prob += np->right->subtree_prob;
1466             }
1467         }
1468     }
1469 }
1470 \f
1471 /* Search the parent sections of the case node tree
1472    to see if a test for the lower bound of NODE would be redundant.
1473    INDEX_TYPE is the type of the index expression.
1474
1475    The instructions to generate the case decision tree are
1476    output in the same order as nodes are processed so it is
1477    known that if a parent node checks the range of the current
1478    node minus one that the current node is bounded at its lower
1479    span.  Thus the test would be redundant.  */
1480
1481 static int
1482 node_has_low_bound (case_node_ptr node, tree index_type)
1483 {
1484   tree low_minus_one;
1485   case_node_ptr pnode;
1486
1487   /* If the lower bound of this node is the lowest value in the index type,
1488      we need not test it.  */
1489
1490   if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
1491     return 1;
1492
1493   /* If this node has a left branch, the value at the left must be less
1494      than that at this node, so it cannot be bounded at the bottom and
1495      we need not bother testing any further.  */
1496
1497   if (node->left)
1498     return 0;
1499
1500   low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low),
1501                                node->low,
1502                                build_int_cst (TREE_TYPE (node->low), 1));
1503
1504   /* If the subtraction above overflowed, we can't verify anything.
1505      Otherwise, look for a parent that tests our value - 1.  */
1506
1507   if (! tree_int_cst_lt (low_minus_one, node->low))
1508     return 0;
1509
1510   for (pnode = node->parent; pnode; pnode = pnode->parent)
1511     if (tree_int_cst_equal (low_minus_one, pnode->high))
1512       return 1;
1513
1514   return 0;
1515 }
1516
1517 /* Search the parent sections of the case node tree
1518    to see if a test for the upper bound of NODE would be redundant.
1519    INDEX_TYPE is the type of the index expression.
1520
1521    The instructions to generate the case decision tree are
1522    output in the same order as nodes are processed so it is
1523    known that if a parent node checks the range of the current
1524    node plus one that the current node is bounded at its upper
1525    span.  Thus the test would be redundant.  */
1526
1527 static int
1528 node_has_high_bound (case_node_ptr node, tree index_type)
1529 {
1530   tree high_plus_one;
1531   case_node_ptr pnode;
1532
1533   /* If there is no upper bound, obviously no test is needed.  */
1534
1535   if (TYPE_MAX_VALUE (index_type) == NULL)
1536     return 1;
1537
1538   /* If the upper bound of this node is the highest value in the type
1539      of the index expression, we need not test against it.  */
1540
1541   if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
1542     return 1;
1543
1544   /* If this node has a right branch, the value at the right must be greater
1545      than that at this node, so it cannot be bounded at the top and
1546      we need not bother testing any further.  */
1547
1548   if (node->right)
1549     return 0;
1550
1551   high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high),
1552                                node->high,
1553                                build_int_cst (TREE_TYPE (node->high), 1));
1554
1555   /* If the addition above overflowed, we can't verify anything.
1556      Otherwise, look for a parent that tests our value + 1.  */
1557
1558   if (! tree_int_cst_lt (node->high, high_plus_one))
1559     return 0;
1560
1561   for (pnode = node->parent; pnode; pnode = pnode->parent)
1562     if (tree_int_cst_equal (high_plus_one, pnode->low))
1563       return 1;
1564
1565   return 0;
1566 }
1567
1568 /* Search the parent sections of the
1569    case node tree to see if both tests for the upper and lower
1570    bounds of NODE would be redundant.  */
1571
1572 static int
1573 node_is_bounded (case_node_ptr node, tree index_type)
1574 {
1575   return (node_has_low_bound (node, index_type)
1576           && node_has_high_bound (node, index_type));
1577 }
1578 \f
1579
1580 /* Emit step-by-step code to select a case for the value of INDEX.
1581    The thus generated decision tree follows the form of the
1582    case-node binary tree NODE, whose nodes represent test conditions.
1583    INDEX_TYPE is the type of the index of the switch.
1584
1585    Care is taken to prune redundant tests from the decision tree
1586    by detecting any boundary conditions already checked by
1587    emitted rtx.  (See node_has_high_bound, node_has_low_bound
1588    and node_is_bounded, above.)
1589
1590    Where the test conditions can be shown to be redundant we emit
1591    an unconditional jump to the target code.  As a further
1592    optimization, the subordinates of a tree node are examined to
1593    check for bounded nodes.  In this case conditional and/or
1594    unconditional jumps as a result of the boundary check for the
1595    current node are arranged to target the subordinates associated
1596    code for out of bound conditions on the current node.
1597
1598    We can assume that when control reaches the code generated here,
1599    the index value has already been compared with the parents
1600    of this node, and determined to be on the same side of each parent
1601    as this node is.  Thus, if this node tests for the value 51,
1602    and a parent tested for 52, we don't need to consider
1603    the possibility of a value greater than 51.  If another parent
1604    tests for the value 50, then this node need not test anything.  */
1605
1606 static void
1607 emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
1608                  int default_prob, tree index_type)
1609 {
1610   /* If INDEX has an unsigned type, we must make unsigned branches.  */
1611   int unsignedp = TYPE_UNSIGNED (index_type);
1612   int probability;
1613   int prob = node->prob, subtree_prob = node->subtree_prob;
1614   machine_mode mode = GET_MODE (index);
1615   machine_mode imode = TYPE_MODE (index_type);
1616
1617   /* Handle indices detected as constant during RTL expansion.  */
1618   if (mode == VOIDmode)
1619     mode = imode;
1620
1621   /* See if our parents have already tested everything for us.
1622      If they have, emit an unconditional jump for this node.  */
1623   if (node_is_bounded (node, index_type))
1624     emit_jump (label_rtx (node->code_label));
1625
1626   else if (tree_int_cst_equal (node->low, node->high))
1627     {
1628       probability = conditional_probability (prob, subtree_prob + default_prob);
1629       /* Node is single valued.  First see if the index expression matches
1630          this node and then check our children, if any.  */
1631       do_jump_if_equal (mode, index,
1632                         convert_modes (mode, imode,
1633                                        expand_normal (node->low),
1634                                        unsignedp),
1635                         label_rtx (node->code_label), unsignedp, probability);
1636       /* Since this case is taken at this point, reduce its weight from
1637          subtree_weight.  */
1638       subtree_prob -= prob;
1639       if (node->right != 0 && node->left != 0)
1640         {
1641           /* This node has children on both sides.
1642              Dispatch to one side or the other
1643              by comparing the index value with this node's value.
1644              If one subtree is bounded, check that one first,
1645              so we can avoid real branches in the tree.  */
1646
1647           if (node_is_bounded (node->right, index_type))
1648             {
1649               probability = conditional_probability (
1650                   node->right->prob,
1651                   subtree_prob + default_prob);
1652               emit_cmp_and_jump_insns (index,
1653                                        convert_modes
1654                                        (mode, imode,
1655                                         expand_normal (node->high),
1656                                         unsignedp),
1657                                        GT, NULL_RTX, mode, unsignedp,
1658                                        label_rtx (node->right->code_label),
1659                                        probability);
1660               emit_case_nodes (index, node->left, default_label, default_prob,
1661                                index_type);
1662             }
1663
1664           else if (node_is_bounded (node->left, index_type))
1665             {
1666               probability = conditional_probability (
1667                   node->left->prob,
1668                   subtree_prob + default_prob);
1669               emit_cmp_and_jump_insns (index,
1670                                        convert_modes
1671                                        (mode, imode,
1672                                         expand_normal (node->high),
1673                                         unsignedp),
1674                                        LT, NULL_RTX, mode, unsignedp,
1675                                        label_rtx (node->left->code_label),
1676                                        probability);
1677               emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1678             }
1679
1680           /* If both children are single-valued cases with no
1681              children, finish up all the work.  This way, we can save
1682              one ordered comparison.  */
1683           else if (tree_int_cst_equal (node->right->low, node->right->high)
1684                    && node->right->left == 0
1685                    && node->right->right == 0
1686                    && tree_int_cst_equal (node->left->low, node->left->high)
1687                    && node->left->left == 0
1688                    && node->left->right == 0)
1689             {
1690               /* Neither node is bounded.  First distinguish the two sides;
1691                  then emit the code for one side at a time.  */
1692
1693               /* See if the value matches what the right hand side
1694                  wants.  */
1695               probability = conditional_probability (
1696                   node->right->prob,
1697                   subtree_prob + default_prob);
1698               do_jump_if_equal (mode, index,
1699                                 convert_modes (mode, imode,
1700                                                expand_normal (node->right->low),
1701                                                unsignedp),
1702                                 label_rtx (node->right->code_label),
1703                                 unsignedp, probability);
1704
1705               /* See if the value matches what the left hand side
1706                  wants.  */
1707               probability = conditional_probability (
1708                   node->left->prob,
1709                   subtree_prob + default_prob);
1710               do_jump_if_equal (mode, index,
1711                                 convert_modes (mode, imode,
1712                                                expand_normal (node->left->low),
1713                                                unsignedp),
1714                                 label_rtx (node->left->code_label),
1715                                 unsignedp, probability);
1716             }
1717
1718           else
1719             {
1720               /* Neither node is bounded.  First distinguish the two sides;
1721                  then emit the code for one side at a time.  */
1722
1723               tree test_label
1724                 = build_decl (curr_insn_location (),
1725                               LABEL_DECL, NULL_TREE, NULL_TREE);
1726
1727               /* The default label could be reached either through the right
1728                  subtree or the left subtree. Divide the probability
1729                  equally.  */
1730               probability = conditional_probability (
1731                   node->right->subtree_prob + default_prob/2,
1732                   subtree_prob + default_prob);
1733               /* See if the value is on the right.  */
1734               emit_cmp_and_jump_insns (index,
1735                                        convert_modes
1736                                        (mode, imode,
1737                                         expand_normal (node->high),
1738                                         unsignedp),
1739                                        GT, NULL_RTX, mode, unsignedp,
1740                                        label_rtx (test_label),
1741                                        probability);
1742               default_prob /= 2;
1743
1744               /* Value must be on the left.
1745                  Handle the left-hand subtree.  */
1746               emit_case_nodes (index, node->left, default_label, default_prob, index_type);
1747               /* If left-hand subtree does nothing,
1748                  go to default.  */
1749               if (default_label)
1750                 emit_jump (default_label);
1751
1752               /* Code branches here for the right-hand subtree.  */
1753               expand_label (test_label);
1754               emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1755             }
1756         }
1757
1758       else if (node->right != 0 && node->left == 0)
1759         {
1760           /* Here we have a right child but no left so we issue a conditional
1761              branch to default and process the right child.
1762
1763              Omit the conditional branch to default if the right child
1764              does not have any children and is single valued; it would
1765              cost too much space to save so little time.  */
1766
1767           if (node->right->right || node->right->left
1768               || !tree_int_cst_equal (node->right->low, node->right->high))
1769             {
1770               if (!node_has_low_bound (node, index_type))
1771                 {
1772                   probability = conditional_probability (
1773                       default_prob/2,
1774                       subtree_prob + default_prob);
1775                   emit_cmp_and_jump_insns (index,
1776                                            convert_modes
1777                                            (mode, imode,
1778                                             expand_normal (node->high),
1779                                             unsignedp),
1780                                            LT, NULL_RTX, mode, unsignedp,
1781                                            default_label,
1782                                            probability);
1783                   default_prob /= 2;
1784                 }
1785
1786               emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1787             }
1788           else
1789             {
1790               probability = conditional_probability (
1791                   node->right->subtree_prob,
1792                   subtree_prob + default_prob);
1793               /* We cannot process node->right normally
1794                  since we haven't ruled out the numbers less than
1795                  this node's value.  So handle node->right explicitly.  */
1796               do_jump_if_equal (mode, index,
1797                                 convert_modes
1798                                 (mode, imode,
1799                                  expand_normal (node->right->low),
1800                                  unsignedp),
1801                                 label_rtx (node->right->code_label), unsignedp, probability);
1802             }
1803           }
1804
1805       else if (node->right == 0 && node->left != 0)
1806         {
1807           /* Just one subtree, on the left.  */
1808           if (node->left->left || node->left->right
1809               || !tree_int_cst_equal (node->left->low, node->left->high))
1810             {
1811               if (!node_has_high_bound (node, index_type))
1812                 {
1813                   probability = conditional_probability (
1814                       default_prob/2,
1815                       subtree_prob + default_prob);
1816                   emit_cmp_and_jump_insns (index,
1817                                            convert_modes
1818                                            (mode, imode,
1819                                             expand_normal (node->high),
1820                                             unsignedp),
1821                                            GT, NULL_RTX, mode, unsignedp,
1822                                            default_label,
1823                                            probability);
1824                   default_prob /= 2;
1825                 }
1826
1827               emit_case_nodes (index, node->left, default_label,
1828                                default_prob, index_type);
1829             }
1830           else
1831             {
1832               probability = conditional_probability (
1833                   node->left->subtree_prob,
1834                   subtree_prob + default_prob);
1835               /* We cannot process node->left normally
1836                  since we haven't ruled out the numbers less than
1837                  this node's value.  So handle node->left explicitly.  */
1838               do_jump_if_equal (mode, index,
1839                                 convert_modes
1840                                 (mode, imode,
1841                                  expand_normal (node->left->low),
1842                                  unsignedp),
1843                                 label_rtx (node->left->code_label), unsignedp, probability);
1844             }
1845         }
1846     }
1847   else
1848     {
1849       /* Node is a range.  These cases are very similar to those for a single
1850          value, except that we do not start by testing whether this node
1851          is the one to branch to.  */
1852
1853       if (node->right != 0 && node->left != 0)
1854         {
1855           /* Node has subtrees on both sides.
1856              If the right-hand subtree is bounded,
1857              test for it first, since we can go straight there.
1858              Otherwise, we need to make a branch in the control structure,
1859              then handle the two subtrees.  */
1860           tree test_label = 0;
1861
1862           if (node_is_bounded (node->right, index_type))
1863             {
1864               /* Right hand node is fully bounded so we can eliminate any
1865                  testing and branch directly to the target code.  */
1866               probability = conditional_probability (
1867                   node->right->subtree_prob,
1868                   subtree_prob + default_prob);
1869               emit_cmp_and_jump_insns (index,
1870                                        convert_modes
1871                                        (mode, imode,
1872                                         expand_normal (node->high),
1873                                         unsignedp),
1874                                        GT, NULL_RTX, mode, unsignedp,
1875                                        label_rtx (node->right->code_label),
1876                                        probability);
1877             }
1878           else
1879             {
1880               /* Right hand node requires testing.
1881                  Branch to a label where we will handle it later.  */
1882
1883               test_label = build_decl (curr_insn_location (),
1884                                        LABEL_DECL, NULL_TREE, NULL_TREE);
1885               probability = conditional_probability (
1886                   node->right->subtree_prob + default_prob/2,
1887                   subtree_prob + default_prob);
1888               emit_cmp_and_jump_insns (index,
1889                                        convert_modes
1890                                        (mode, imode,
1891                                         expand_normal (node->high),
1892                                         unsignedp),
1893                                        GT, NULL_RTX, mode, unsignedp,
1894                                        label_rtx (test_label),
1895                                        probability);
1896               default_prob /= 2;
1897             }
1898
1899           /* Value belongs to this node or to the left-hand subtree.  */
1900
1901           probability = conditional_probability (
1902               prob,
1903               subtree_prob + default_prob);
1904           emit_cmp_and_jump_insns (index,
1905                                    convert_modes
1906                                    (mode, imode,
1907                                     expand_normal (node->low),
1908                                     unsignedp),
1909                                    GE, NULL_RTX, mode, unsignedp,
1910                                    label_rtx (node->code_label),
1911                                    probability);
1912
1913           /* Handle the left-hand subtree.  */
1914           emit_case_nodes (index, node->left, default_label, default_prob, index_type);
1915
1916           /* If right node had to be handled later, do that now.  */
1917
1918           if (test_label)
1919             {
1920               /* If the left-hand subtree fell through,
1921                  don't let it fall into the right-hand subtree.  */
1922               if (default_label)
1923                 emit_jump (default_label);
1924
1925               expand_label (test_label);
1926               emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1927             }
1928         }
1929
1930       else if (node->right != 0 && node->left == 0)
1931         {
1932           /* Deal with values to the left of this node,
1933              if they are possible.  */
1934           if (!node_has_low_bound (node, index_type))
1935             {
1936               probability = conditional_probability (
1937                   default_prob/2,
1938                   subtree_prob + default_prob);
1939               emit_cmp_and_jump_insns (index,
1940                                        convert_modes
1941                                        (mode, imode,
1942                                         expand_normal (node->low),
1943                                         unsignedp),
1944                                        LT, NULL_RTX, mode, unsignedp,
1945                                        default_label,
1946                                        probability);
1947               default_prob /= 2;
1948             }
1949
1950           /* Value belongs to this node or to the right-hand subtree.  */
1951
1952           probability = conditional_probability (
1953               prob,
1954               subtree_prob + default_prob);
1955           emit_cmp_and_jump_insns (index,
1956                                    convert_modes
1957                                    (mode, imode,
1958                                     expand_normal (node->high),
1959                                     unsignedp),
1960                                    LE, NULL_RTX, mode, unsignedp,
1961                                    label_rtx (node->code_label),
1962                                    probability);
1963
1964           emit_case_nodes (index, node->right, default_label, default_prob, index_type);
1965         }
1966
1967       else if (node->right == 0 && node->left != 0)
1968         {
1969           /* Deal with values to the right of this node,
1970              if they are possible.  */
1971           if (!node_has_high_bound (node, index_type))
1972             {
1973               probability = conditional_probability (
1974                   default_prob/2,
1975                   subtree_prob + default_prob);
1976               emit_cmp_and_jump_insns (index,
1977                                        convert_modes
1978                                        (mode, imode,
1979                                         expand_normal (node->high),
1980                                         unsignedp),
1981                                        GT, NULL_RTX, mode, unsignedp,
1982                                        default_label,
1983                                        probability);
1984               default_prob /= 2;
1985             }
1986
1987           /* Value belongs to this node or to the left-hand subtree.  */
1988
1989           probability = conditional_probability (
1990               prob,
1991               subtree_prob + default_prob);
1992           emit_cmp_and_jump_insns (index,
1993                                    convert_modes
1994                                    (mode, imode,
1995                                     expand_normal (node->low),
1996                                     unsignedp),
1997                                    GE, NULL_RTX, mode, unsignedp,
1998                                    label_rtx (node->code_label),
1999                                    probability);
2000
2001           emit_case_nodes (index, node->left, default_label, default_prob, index_type);
2002         }
2003
2004       else
2005         {
2006           /* Node has no children so we check low and high bounds to remove
2007              redundant tests.  Only one of the bounds can exist,
2008              since otherwise this node is bounded--a case tested already.  */
2009           int high_bound = node_has_high_bound (node, index_type);
2010           int low_bound = node_has_low_bound (node, index_type);
2011
2012           if (!high_bound && low_bound)
2013             {
2014               probability = conditional_probability (
2015                   default_prob,
2016                   subtree_prob + default_prob);
2017               emit_cmp_and_jump_insns (index,
2018                                        convert_modes
2019                                        (mode, imode,
2020                                         expand_normal (node->high),
2021                                         unsignedp),
2022                                        GT, NULL_RTX, mode, unsignedp,
2023                                        default_label,
2024                                        probability);
2025             }
2026
2027           else if (!low_bound && high_bound)
2028             {
2029               probability = conditional_probability (
2030                   default_prob,
2031                   subtree_prob + default_prob);
2032               emit_cmp_and_jump_insns (index,
2033                                        convert_modes
2034                                        (mode, imode,
2035                                         expand_normal (node->low),
2036                                         unsignedp),
2037                                        LT, NULL_RTX, mode, unsignedp,
2038                                        default_label,
2039                                        probability);
2040             }
2041           else if (!low_bound && !high_bound)
2042             {
2043               /* Widen LOW and HIGH to the same width as INDEX.  */
2044               tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
2045               tree low = build1 (CONVERT_EXPR, type, node->low);
2046               tree high = build1 (CONVERT_EXPR, type, node->high);
2047               rtx low_rtx, new_index, new_bound;
2048
2049               /* Instead of doing two branches, emit one unsigned branch for
2050                  (index-low) > (high-low).  */
2051               low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL);
2052               new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
2053                                                NULL_RTX, unsignedp,
2054                                                OPTAB_WIDEN);
2055               new_bound = expand_expr (fold_build2 (MINUS_EXPR, type,
2056                                                     high, low),
2057                                        NULL_RTX, mode, EXPAND_NORMAL);
2058
2059               probability = conditional_probability (
2060                   default_prob,
2061                   subtree_prob + default_prob);
2062               emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
2063                                        mode, 1, default_label, probability);
2064             }
2065
2066           emit_jump (label_rtx (node->code_label));
2067         }
2068     }
2069 }