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