gcc/tree-switch-conversion.c

   1 /* Switch Conversion converts variable initializations based on switch
   2    statements to initializations from a static array.
   3    Copyright (C) 2006, 2008, 2009, 2010 Free Software Foundation, Inc.
   4    Contributed by Martin Jambor <jamborm@suse.cz>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it
   9 under the terms of the GNU General Public License as published by the
  10 Free Software Foundation; either version 3, or (at your option) any
  11 later version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT
  14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not, write to the Free
  20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  21 02110-1301, USA.  */
  22
  23 /*
  24      Switch initialization conversion
  25
  26 The following pass changes simple initializations of scalars in a switch
  27 statement into initializations from a static array.  Obviously, the values must
  28 be constant and known at compile time and a default branch must be
  29 provided.  For example, the following code:
  30
  31         int a,b;
  32
  33         switch (argc)
  34         {
  35          case 1:
  36          case 2:
  37                 a_1 = 8;
  38                 b_1 = 6;
  39                 break;
  40          case 3:
  41                 a_2 = 9;
  42                 b_2 = 5;
  43                 break;
  44          case 12:
  45                 a_3 = 10;
  46                 b_3 = 4;
  47                 break;
  48          default:
  49                 a_4 = 16;
  50                 b_4 = 1;
  51         }
  52         a_5 = PHI <a_1, a_2, a_3, a_4>
  53         b_5 = PHI <b_1, b_2, b_3, b_4>
  54
  55
  56 is changed into:
  57
  58         static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
  59         static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
  60                                  16, 16, 10};
  61
  62         if (((unsigned) argc) - 1 < 11)
  63           {
  64             a_6 = CSWTCH02[argc - 1];
  65             b_6 = CSWTCH01[argc - 1];
  66           }
  67         else
  68           {
  69             a_7 = 16;
  70             b_7 = 1;
  71           }
  72           a_5 = PHI <a_6, a_7>
  73           b_b = PHI <b_6, b_7>
  74
  75 There are further constraints.  Specifically, the range of values across all
  76 case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
  77 eight) times the number of the actual switch branches. */
  78
  79 #include "config.h"
  80 #include "system.h"
  81 #include "coretypes.h"
  82 #include "tm.h"
  83 #include <signal.h>
  84
  85 #include "line-map.h"
  86 #include "params.h"
  87 #include "flags.h"
  88 #include "tree.h"
  89 #include "basic-block.h"
  90 #include "tree-flow.h"
  91 #include "tree-flow-inline.h"
  92 #include "tree-ssa-operands.h"
  93 #include "output.h"
  94 #include "input.h"
  95 #include "tree-pass.h"
  96 #include "gimple-pretty-print.h"
  97 #include "tree-dump.h"
  98 #include "timevar.h"
  99 #include "langhooks.h"
 100
 101 /* The main structure of the pass.  */
 102 struct switch_conv_info
 103 {
 104   /* The expression used to decide the switch branch.  (It is subsequently used
 105      as the index to the created array.) */
 106   tree index_expr;
 107
 108   /* The following integer constants store the minimum value covered by the
 109      cases.  */
 110   tree range_min;
 111
 112   /* The difference between the above two numbers, i.e. The size of the array
 113      that would have to be created by the transformation.  */
 114   tree range_size;
 115
 116   /* Basic block that contains the actual SWITCH_EXPR.  */
 117   basic_block switch_bb;
 118
 119   /* All branches of the switch statement must have a single successor stored in
 120      the following variable.  */
 121   basic_block final_bb;
 122
 123   /* Number of phi nodes in the final bb (that we'll be replacing).  */
 124   int phi_count;
 125
 126   /* Array of default values, in the same order as phi nodes.  */
 127   tree *default_values;
 128
 129   /* Constructors of new static arrays.  */
 130   VEC (constructor_elt, gc) **constructors;
 131
 132   /* Array of ssa names that are initialized with a value from a new static
 133      array.  */
 134   tree *target_inbound_names;
 135
 136   /* Array of ssa names that are initialized with the default value if the
 137      switch expression is out of range.  */
 138   tree *target_outbound_names;
 139
 140   /* The probability of the default edge in the replaced switch.  */
 141   int default_prob;
 142
 143   /* The count of the default edge in the replaced switch.  */
 144   gcov_type default_count;
 145
 146   /* Combined count of all other (non-default) edges in the replaced switch.  */
 147   gcov_type other_count;
 148
 149   /* The first load statement that loads a temporary from a new static array.
 150    */
 151   gimple arr_ref_first;
 152
 153   /* The last load statement that loads a temporary from a new static array.  */
 154   gimple arr_ref_last;
 155
 156   /* String reason why the case wasn't a good candidate that is written to the
 157      dump file, if there is one.  */
 158   const char *reason;
 159 };
 160
 161 /* Global pass info.  */
 162 static struct switch_conv_info info;
 163
 164
 165 /* Checks whether the range given by individual case statements of the SWTCH
 166    switch statement isn't too big and whether the number of branches actually
 167    satisfies the size of the new array.  */
 168
 169 static bool
 170 check_range (gimple swtch)
 171 {
 172   tree min_case, max_case;
 173   unsigned int branch_num = gimple_switch_num_labels (swtch);
 174   tree range_max;
 175
 176   /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
 177      is a default label which is the last in the vector.  */
 178
 179   min_case = gimple_switch_label (swtch, 1);
 180   info.range_min = CASE_LOW (min_case);
 181
 182   gcc_assert (branch_num > 1);
 183   gcc_assert (CASE_LOW (gimple_switch_label (swtch, 0)) == NULL_TREE);
 184   max_case = gimple_switch_label (swtch, branch_num - 1);
 185   if (CASE_HIGH (max_case) != NULL_TREE)
 186     range_max = CASE_HIGH (max_case);
 187   else
 188     range_max = CASE_LOW (max_case);
 189
 190   gcc_assert (info.range_min);
 191   gcc_assert (range_max);
 192
 193   info.range_size = int_const_binop (MINUS_EXPR, range_max, info.range_min, 0);
 194
 195   gcc_assert (info.range_size);
 196   if (!host_integerp (info.range_size, 1))
 197     {
 198       info.reason = "index range way too large or otherwise unusable.\n";
 199       return false;
 200     }
 201
 202   if ((unsigned HOST_WIDE_INT) tree_low_cst (info.range_size, 1)
 203       > ((unsigned) branch_num * SWITCH_CONVERSION_BRANCH_RATIO))
 204     {
 205       info.reason = "the maximum range-branch ratio exceeded.\n";
 206       return false;
 207     }
 208
 209   return true;
 210 }
 211
 212 /* Checks the given CS switch case whether it is suitable for conversion
 213    (whether all but the default basic blocks are empty and so on).  If it is,
 214    adds the case to the branch list along with values for the defined variables
 215    and returns true.  Otherwise returns false.  */
 216
 217 static bool
 218 check_process_case (tree cs)
 219 {
 220   tree ldecl;
 221   basic_block label_bb, following_bb;
 222   edge e;
 223
 224   ldecl = CASE_LABEL (cs);
 225   label_bb = label_to_block (ldecl);
 226
 227   e = find_edge (info.switch_bb, label_bb);
 228   gcc_assert (e);
 229
 230   if (CASE_LOW (cs) == NULL_TREE)
 231     {
 232       /* Default branch.  */
 233       info.default_prob = e->probability;
 234       info.default_count = e->count;
 235     }
 236   else
 237     info.other_count += e->count;
 238
 239   if (!label_bb)
 240     {
 241       info.reason = "  Bad case - cs BB  label is NULL\n";
 242       return false;
 243     }
 244
 245   if (!single_pred_p (label_bb))
 246     {
 247       if (info.final_bb && info.final_bb != label_bb)
 248         {
 249           info.reason = "  Bad case - a non-final BB has two predecessors\n";
 250           return false; /* sth complex going on in this branch  */
 251         }
 252
 253       following_bb = label_bb;
 254     }
 255   else
 256     {
 257       if (!empty_block_p (label_bb))
 258         {
 259           info.reason = "  Bad case - a non-final BB not empty\n";
 260           return false;
 261         }
 262
 263       e = single_succ_edge (label_bb);
 264       following_bb = single_succ (label_bb);
 265     }
 266
 267   if (!info.final_bb)
 268     info.final_bb = following_bb;
 269   else if (info.final_bb != following_bb)
 270     {
 271       info.reason = "  Bad case - different final BB\n";
 272       return false; /* the only successor is not common for all the branches */
 273     }
 274
 275   return true;
 276 }
 277
 278 /* This function checks whether all required values in phi nodes in final_bb
 279    are constants.  Required values are those that correspond to a basic block
 280    which is a part of the examined switch statement.  It returns true if the
 281    phi nodes are OK, otherwise false.  */
 282
 283 static bool
 284 check_final_bb (void)
 285 {
 286   gimple_stmt_iterator gsi;
 287
 288   info.phi_count = 0;
 289   for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
 290     {
 291       gimple phi = gsi_stmt (gsi);
 292       unsigned int i;
 293
 294       info.phi_count++;
 295
 296       for (i = 0; i < gimple_phi_num_args (phi); i++)
 297         {
 298           basic_block bb = gimple_phi_arg_edge (phi, i)->src;
 299
 300           if (bb == info.switch_bb
 301               || (single_pred_p (bb) && single_pred (bb) == info.switch_bb))
 302             {
 303               tree reloc, val;
 304
 305               val = gimple_phi_arg_def (phi, i);
 306               if (!is_gimple_ip_invariant (val))
 307                 {
 308                   info.reason = "   Non-invariant value from a case\n";
 309                   return false; /* Non-invariant argument.  */
 310                 }
 311               reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
 312               if ((flag_pic && reloc != null_pointer_node)
 313                   || (!flag_pic && reloc == NULL_TREE))
 314                 {
 315                   if (reloc)
 316                     info.reason
 317                       = "   Value from a case would need runtime relocations\n";
 318                   else
 319                     info.reason
 320                       = "   Value from a case is not a valid initializer\n";
 321                   return false;
 322                 }
 323             }
 324         }
 325     }
 326
 327   return true;
 328 }
 329
 330 /* The following function allocates default_values, target_{in,out}_names and
 331    constructors arrays.  The last one is also populated with pointers to
 332    vectors that will become constructors of new arrays.  */
 333
 334 static void
 335 create_temp_arrays (void)
 336 {
 337   int i;
 338
 339   info.default_values = (tree *) xcalloc (info.phi_count, sizeof (tree));
 340   info.constructors = (VEC (constructor_elt, gc) **) xcalloc (info.phi_count,
 341                                                               sizeof (tree));
 342   info.target_inbound_names = (tree *) xcalloc (info.phi_count, sizeof (tree));
 343   info.target_outbound_names = (tree *) xcalloc (info.phi_count,
 344                                                  sizeof (tree));
 345
 346   for (i = 0; i < info.phi_count; i++)
 347     info.constructors[i]
 348       = VEC_alloc (constructor_elt, gc, tree_low_cst (info.range_size, 1) + 1);
 349 }
 350
 351 /* Free the arrays created by create_temp_arrays().  The vectors that are
 352    created by that function are not freed here, however, because they have
 353    already become constructors and must be preserved.  */
 354
 355 static void
 356 free_temp_arrays (void)
 357 {
 358   free (info.constructors);
 359   free (info.default_values);
 360   free (info.target_inbound_names);
 361   free (info.target_outbound_names);
 362 }
 363
 364 /* Populate the array of default values in the order of phi nodes.
 365    DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch.  */
 366
 367 static void
 368 gather_default_values (tree default_case)
 369 {
 370   gimple_stmt_iterator gsi;
 371   basic_block bb = label_to_block (CASE_LABEL (default_case));
 372   edge e;
 373   int i = 0;
 374
 375   gcc_assert (CASE_LOW (default_case) == NULL_TREE);
 376
 377   if (bb == info.final_bb)
 378     e = find_edge (info.switch_bb, bb);
 379   else
 380     e = single_succ_edge (bb);
 381
 382   for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
 383     {
 384       gimple phi = gsi_stmt (gsi);
 385       tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
 386       gcc_assert (val);
 387       info.default_values[i++] = val;
 388     }
 389 }
 390
 391 /* The following function populates the vectors in the constructors array with
 392    future contents of the static arrays.  The vectors are populated in the
 393    order of phi nodes.  SWTCH is the switch statement being converted.  */
 394
 395 static void
 396 build_constructors (gimple swtch)
 397 {
 398   unsigned i, branch_num = gimple_switch_num_labels (swtch);
 399   tree pos = info.range_min;
 400
 401   for (i = 1; i < branch_num; i++)
 402     {
 403       tree cs = gimple_switch_label (swtch, i);
 404       basic_block bb = label_to_block (CASE_LABEL (cs));
 405       edge e;
 406       tree high;
 407       gimple_stmt_iterator gsi;
 408       int j;
 409
 410       if (bb == info.final_bb)
 411         e = find_edge (info.switch_bb, bb);
 412       else
 413         e = single_succ_edge (bb);
 414       gcc_assert (e);
 415
 416       while (tree_int_cst_lt (pos, CASE_LOW (cs)))
 417         {
 418           int k;
 419           for (k = 0; k < info.phi_count; k++)
 420             {
 421               constructor_elt *elt;
 422
 423               elt = VEC_quick_push (constructor_elt,
 424                                     info.constructors[k], NULL);
 425               elt->index = int_const_binop (MINUS_EXPR, pos,
 426                                             info.range_min, 0);
 427               elt->value = info.default_values[k];
 428             }
 429
 430           pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
 431         }
 432       gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
 433
 434       j = 0;
 435       if (CASE_HIGH (cs))
 436         high = CASE_HIGH (cs);
 437       else
 438         high = CASE_LOW (cs);
 439       for (gsi = gsi_start_phis (info.final_bb);
 440            !gsi_end_p (gsi); gsi_next (&gsi))
 441         {
 442           gimple phi = gsi_stmt (gsi);
 443           tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
 444           tree low = CASE_LOW (cs);
 445           pos = CASE_LOW (cs);
 446
 447           do
 448             {
 449               constructor_elt *elt;
 450
 451               elt = VEC_quick_push (constructor_elt,
 452                                     info.constructors[j], NULL);
 453               elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min, 0);
 454               elt->value = val;
 455
 456               pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
 457             } while (!tree_int_cst_lt (high, pos)
 458                      && tree_int_cst_lt (low, pos));
 459           j++;
 460         }
 461     }
 462 }
 463
 464 /* If all values in the constructor vector are the same, return the value.
 465    Otherwise return NULL_TREE.  Not supposed to be called for empty
 466    vectors.  */
 467
 468 static tree
 469 constructor_contains_same_values_p (VEC (constructor_elt, gc) *vec)
 470 {
 471   int i, len = VEC_length (constructor_elt, vec);
 472   tree prev = NULL_TREE;
 473
 474   for (i = 0; i < len; i++)
 475     {
 476       constructor_elt *elt = VEC_index (constructor_elt, vec, i);
 477
 478       if (!prev)
 479         prev = elt->value;
 480       else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
 481         return NULL_TREE;
 482     }
 483   return prev;
 484 }
 485
 486 /* Create an appropriate array type and declaration and assemble a static array
 487    variable.  Also create a load statement that initializes the variable in
 488    question with a value from the static array.  SWTCH is the switch statement
 489    being converted, NUM is the index to arrays of constructors, default values
 490    and target SSA names for this particular array.  ARR_INDEX_TYPE is the type
 491    of the index of the new array, PHI is the phi node of the final BB that
 492    corresponds to the value that will be loaded from the created array.  TIDX
 493    is an ssa name of a temporary variable holding the index for loads from the
 494    new array.  */
 495
 496 static void
 497 build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi,
 498                  tree tidx)
 499 {
 500   tree name, cst;
 501   gimple load;
 502   gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
 503   location_t loc = gimple_location (swtch);
 504
 505   gcc_assert (info.default_values[num]);
 506
 507   name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL);
 508   info.target_inbound_names[num] = name;
 509
 510   cst = constructor_contains_same_values_p (info.constructors[num]);
 511   if (cst)
 512     load = gimple_build_assign (name, cst);
 513   else
 514     {
 515       tree array_type, ctor, decl, value_type, fetch;
 516
 517       value_type = TREE_TYPE (info.default_values[num]);
 518       array_type = build_array_type (value_type, arr_index_type);
 519       ctor = build_constructor (array_type, info.constructors[num]);
 520       TREE_CONSTANT (ctor) = true;
 521       TREE_STATIC (ctor) = true;
 522
 523       decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
 524       TREE_STATIC (decl) = 1;
 525       DECL_INITIAL (decl) = ctor;
 526
 527       DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
 528       DECL_ARTIFICIAL (decl) = 1;
 529       TREE_CONSTANT (decl) = 1;
 530       TREE_READONLY (decl) = 1;
 531       add_referenced_var (decl);
 532       varpool_mark_needed_node (varpool_node (decl));
 533       varpool_finalize_decl (decl);
 534
 535       fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
 536                       NULL_TREE);
 537       load = gimple_build_assign (name, fetch);
 538     }
 539
 540   SSA_NAME_DEF_STMT (name) = load;
 541   gsi_insert_before (&gsi, load, GSI_SAME_STMT);
 542   update_stmt (load);
 543   info.arr_ref_last = load;
 544 }
 545
 546 /* Builds and initializes static arrays initialized with values gathered from
 547    the SWTCH switch statement.  Also creates statements that load values from
 548    them.  */
 549
 550 static void
 551 build_arrays (gimple swtch)
 552 {
 553   tree arr_index_type;
 554   tree tidx, sub, tmp;
 555   gimple stmt;
 556   gimple_stmt_iterator gsi;
 557   int i;
 558   location_t loc = gimple_location (swtch);
 559
 560   gsi = gsi_for_stmt (swtch);
 561
 562   arr_index_type = build_index_type (info.range_size);
 563   tmp = create_tmp_var (TREE_TYPE (info.index_expr), "csti");
 564   add_referenced_var (tmp);
 565   tidx = make_ssa_name (tmp, NULL);
 566   sub = fold_build2_loc (loc, MINUS_EXPR,
 567                      TREE_TYPE (info.index_expr), info.index_expr,
 568                      fold_convert_loc (loc, TREE_TYPE (info.index_expr),
 569                                        info.range_min));
 570   sub = force_gimple_operand_gsi (&gsi, sub,
 571                                   false, NULL, true, GSI_SAME_STMT);
 572   stmt = gimple_build_assign (tidx, sub);
 573   SSA_NAME_DEF_STMT (tidx) = stmt;
 574
 575   gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
 576   update_stmt (stmt);
 577   info.arr_ref_first = stmt;
 578
 579   for (gsi = gsi_start_phis (info.final_bb), i = 0;
 580        !gsi_end_p (gsi); gsi_next (&gsi), i++)
 581     build_one_array (swtch, i, arr_index_type, gsi_stmt (gsi), tidx);
 582 }
 583
 584 /* Generates and appropriately inserts loads of default values at the position
 585    given by BSI.  Returns the last inserted statement.  */
 586
 587 static gimple
 588 gen_def_assigns (gimple_stmt_iterator *gsi)
 589 {
 590   int i;
 591   gimple assign = NULL;
 592
 593   for (i = 0; i < info.phi_count; i++)
 594     {
 595       tree name
 596         = make_ssa_name (SSA_NAME_VAR (info.target_inbound_names[i]), NULL);
 597
 598       info.target_outbound_names[i] = name;
 599       assign = gimple_build_assign (name, info.default_values[i]);
 600       SSA_NAME_DEF_STMT (name) = assign;
 601       gsi_insert_before (gsi, assign, GSI_SAME_STMT);
 602       update_stmt (assign);
 603     }
 604   return assign;
 605 }
 606
 607 /* Deletes the unused bbs and edges that now contain the switch statement and
 608    its empty branch bbs.  BBD is the now dead BB containing the original switch
 609    statement, FINAL is the last BB of the converted switch statement (in terms
 610    of succession).  */
 611
 612 static void
 613 prune_bbs (basic_block bbd, basic_block final)
 614 {
 615   edge_iterator ei;
 616   edge e;
 617
 618   for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
 619     {
 620       basic_block bb;
 621       bb = e->dest;
 622       remove_edge (e);
 623       if (bb != final)
 624         delete_basic_block (bb);
 625     }
 626   delete_basic_block (bbd);
 627 }
 628
 629 /* Add values to phi nodes in final_bb for the two new edges.  E1F is the edge
 630    from the basic block loading values from an array and E2F from the basic
 631    block loading default values.  BBF is the last switch basic block (see the
 632    bbf description in the comment below).  */
 633
 634 static void
 635 fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
 636 {
 637   gimple_stmt_iterator gsi;
 638   int i;
 639
 640   for (gsi = gsi_start_phis (bbf), i = 0;
 641        !gsi_end_p (gsi); gsi_next (&gsi), i++)
 642     {
 643       gimple phi = gsi_stmt (gsi);
 644       add_phi_arg (phi, info.target_inbound_names[i], e1f, UNKNOWN_LOCATION);
 645       add_phi_arg (phi, info.target_outbound_names[i], e2f, UNKNOWN_LOCATION);
 646     }
 647
 648 }
 649
 650 /* Creates a check whether the switch expression value actually falls into the
 651    range given by all the cases.  If it does not, the temporaries are loaded
 652    with default values instead.  SWTCH is the switch statement being converted.
 653
 654    bb0 is the bb with the switch statement, however, we'll end it with a
 655        condition instead.
 656
 657    bb1 is the bb to be used when the range check went ok.  It is derived from
 658        the switch BB
 659
 660    bb2 is the bb taken when the expression evaluated outside of the range
 661        covered by the created arrays.  It is populated by loads of default
 662        values.
 663
 664    bbF is a fall through for both bb1 and bb2 and contains exactly what
 665        originally followed the switch statement.
 666
 667    bbD contains the switch statement (in the end).  It is unreachable but we
 668        still need to strip off its edges.
 669 */
 670
 671 static void
 672 gen_inbound_check (gimple swtch)
 673 {
 674   tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
 675   tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
 676   tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
 677   gimple label1, label2, label3;
 678
 679   tree utype;
 680   tree tmp_u_1, tmp_u_2, tmp_u_var;
 681   tree cast;
 682   gimple cast_assign, minus_assign;
 683   tree ulb, minus;
 684   tree bound;
 685
 686   gimple cond_stmt;
 687
 688   gimple last_assign;
 689   gimple_stmt_iterator gsi;
 690   basic_block bb0, bb1, bb2, bbf, bbd;
 691   edge e01, e02, e21, e1d, e1f, e2f;
 692   location_t loc = gimple_location (swtch);
 693
 694   gcc_assert (info.default_values);
 695   bb0 = gimple_bb (swtch);
 696
 697   /* Make sure we do not generate arithmetics in a subrange.  */
 698   if (TREE_TYPE (TREE_TYPE (info.index_expr)))
 699     utype = lang_hooks.types.type_for_mode
 700       (TYPE_MODE (TREE_TYPE (TREE_TYPE (info.index_expr))), 1);
 701   else
 702     utype = lang_hooks.types.type_for_mode
 703       (TYPE_MODE (TREE_TYPE (info.index_expr)), 1);
 704
 705   /* (end of) block 0 */
 706   gsi = gsi_for_stmt (info.arr_ref_first);
 707   tmp_u_var = create_tmp_var (utype, "csui");
 708   add_referenced_var (tmp_u_var);
 709   tmp_u_1 = make_ssa_name (tmp_u_var, NULL);
 710
 711   cast = fold_convert_loc (loc, utype, info.index_expr);
 712   cast_assign = gimple_build_assign (tmp_u_1, cast);
 713   SSA_NAME_DEF_STMT (tmp_u_1) = cast_assign;
 714   gsi_insert_before (&gsi, cast_assign, GSI_SAME_STMT);
 715   update_stmt (cast_assign);
 716
 717   ulb = fold_convert_loc (loc, utype, info.range_min);
 718   minus = fold_build2_loc (loc, MINUS_EXPR, utype, tmp_u_1, ulb);
 719   minus = force_gimple_operand_gsi (&gsi, minus, false, NULL, true,
 720                                     GSI_SAME_STMT);
 721   tmp_u_2 = make_ssa_name (tmp_u_var, NULL);
 722   minus_assign = gimple_build_assign (tmp_u_2, minus);
 723   SSA_NAME_DEF_STMT (tmp_u_2) = minus_assign;
 724   gsi_insert_before (&gsi, minus_assign, GSI_SAME_STMT);
 725   update_stmt (minus_assign);
 726
 727   bound = fold_convert_loc (loc, utype, info.range_size);
 728   cond_stmt = gimple_build_cond (LE_EXPR, tmp_u_2, bound, NULL_TREE, NULL_TREE);
 729   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
 730   update_stmt (cond_stmt);
 731
 732   /* block 2 */
 733   gsi = gsi_for_stmt (info.arr_ref_first);
 734   label2 = gimple_build_label (label_decl2);
 735   gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
 736   last_assign = gen_def_assigns (&gsi);
 737
 738   /* block 1 */
 739   gsi = gsi_for_stmt (info.arr_ref_first);
 740   label1 = gimple_build_label (label_decl1);
 741   gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
 742
 743   /* block F */
 744   gsi = gsi_start_bb (info.final_bb);
 745   label3 = gimple_build_label (label_decl3);
 746   gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
 747
 748   /* cfg fix */
 749   e02 = split_block (bb0, cond_stmt);
 750   bb2 = e02->dest;
 751
 752   e21 = split_block (bb2, last_assign);
 753   bb1 = e21->dest;
 754   remove_edge (e21);
 755
 756   e1d = split_block (bb1, info.arr_ref_last);
 757   bbd = e1d->dest;
 758   remove_edge (e1d);
 759
 760   /* flags and profiles of the edge for in-range values */
 761   e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
 762   e01->probability = REG_BR_PROB_BASE - info.default_prob;
 763   e01->count = info.other_count;
 764
 765   /* flags and profiles of the edge taking care of out-of-range values */
 766   e02->flags &= ~EDGE_FALLTHRU;
 767   e02->flags |= EDGE_FALSE_VALUE;
 768   e02->probability = info.default_prob;
 769   e02->count = info.default_count;
 770
 771   bbf = info.final_bb;
 772
 773   e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
 774   e1f->probability = REG_BR_PROB_BASE;
 775   e1f->count = info.other_count;
 776
 777   e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
 778   e2f->probability = REG_BR_PROB_BASE;
 779   e2f->count = info.default_count;
 780
 781   /* frequencies of the new BBs */
 782   bb1->frequency = EDGE_FREQUENCY (e01);
 783   bb2->frequency = EDGE_FREQUENCY (e02);
 784   bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
 785
 786   prune_bbs (bbd, info.final_bb); /* To keep calc_dfs_tree() in dominance.c
 787                                      happy.  */
 788
 789   fix_phi_nodes (e1f, e2f, bbf);
 790
 791   free_dominance_info (CDI_DOMINATORS);
 792   free_dominance_info (CDI_POST_DOMINATORS);
 793 }
 794
 795 /* The following function is invoked on every switch statement (the current one
 796    is given in SWTCH) and runs the individual phases of switch conversion on it
 797    one after another until one fails or the conversion is completed.  */
 798
 799 static bool
 800 process_switch (gimple swtch)
 801 {
 802   unsigned int i, branch_num = gimple_switch_num_labels (swtch);
 803   tree index_type;
 804
 805   /* Operand 2 is either NULL_TREE or a vector of cases (stmt.c).  */
 806   if (branch_num < 2)
 807     {
 808       info.reason = "switch has no labels\n";
 809       return false;
 810     }
 811
 812   info.final_bb = NULL;
 813   info.switch_bb = gimple_bb (swtch);
 814   info.index_expr = gimple_switch_index (swtch);
 815   index_type = TREE_TYPE (info.index_expr);
 816   info.arr_ref_first = NULL;
 817   info.arr_ref_last = NULL;
 818   info.default_prob = 0;
 819   info.default_count = 0;
 820   info.other_count = 0;
 821
 822   /* An ERROR_MARK occurs for various reasons including invalid data type.
 823      (comment from stmt.c) */
 824   if (index_type == error_mark_node)
 825     {
 826       info.reason = "index error.\n";
 827       return false;
 828     }
 829
 830   /* Check the case label values are within reasonable range:  */
 831   if (!check_range (swtch))
 832     return false;
 833
 834   /* For all the cases, see whether they are empty, the assignments they
 835      represent constant and so on...  */
 836   for (i = 0; i < branch_num; i++)
 837     if (!check_process_case (gimple_switch_label (swtch, i)))
 838       {
 839         if (dump_file)
 840           fprintf (dump_file, "Processing of case %i failed\n", i);
 841         return false;
 842       }
 843
 844   if (!check_final_bb ())
 845     return false;
 846
 847   /* At this point all checks have passed and we can proceed with the
 848      transformation.  */
 849
 850   create_temp_arrays ();
 851   gather_default_values (gimple_switch_label (swtch, 0));
 852   build_constructors (swtch);
 853
 854   build_arrays (swtch); /* Build the static arrays and assignments.   */
 855   gen_inbound_check (swtch);    /* Build the bounds check.  */
 856
 857   /* Cleanup:  */
 858   free_temp_arrays ();
 859   return true;
 860 }
 861
 862 /* The main function of the pass scans statements for switches and invokes
 863    process_switch on them.  */
 864
 865 static unsigned int
 866 do_switchconv (void)
 867 {
 868   basic_block bb;
 869
 870   FOR_EACH_BB (bb)
 871   {
 872     gimple stmt = last_stmt (bb);
 873     if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
 874       {
 875         if (dump_file)
 876           {
 877             expanded_location loc = expand_location (gimple_location (stmt));
 878
 879             fprintf (dump_file, "beginning to process the following "
 880                      "SWITCH statement (%s:%d) : ------- \n",
 881                      loc.file, loc.line);
 882             print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 883             putc ('\n', dump_file);
 884           }
 885
 886         info.reason = NULL;
 887         if (process_switch (stmt))
 888           {
 889             if (dump_file)
 890               {
 891                 fputs ("Switch converted\n", dump_file);
 892                 fputs ("--------------------------------\n", dump_file);
 893               }
 894           }
 895         else
 896           {
 897             if (dump_file)
 898               {
 899                 gcc_assert (info.reason);
 900                 fputs ("Bailing out - ", dump_file);
 901                 fputs (info.reason, dump_file);
 902                 fputs ("--------------------------------\n", dump_file);
 903               }
 904           }
 905       }
 906   }
 907
 908   return 0;
 909 }
 910
 911 /* The pass gate. */
 912
 913 static bool
 914 switchconv_gate (void)
 915 {
 916   return flag_tree_switch_conversion != 0;
 917 }
 918
 919 struct gimple_opt_pass pass_convert_switch =
 920 {
 921  {
 922   GIMPLE_PASS,
 923   "switchconv",                         /* name */
 924   switchconv_gate,                      /* gate */
 925   do_switchconv,                        /* execute */
 926   NULL,                                 /* sub */
 927   NULL,                                 /* next */
 928   0,                                    /* static_pass_number */
 929   TV_TREE_SWITCH_CONVERSION,            /* tv_id */
 930   PROP_cfg | PROP_ssa,                  /* properties_required */
 931   0,                                    /* properties_provided */
 932   0,                                    /* properties_destroyed */
 933   0,                                    /* todo_flags_start */
 934   TODO_update_ssa | TODO_dump_func
 935   | TODO_ggc_collect | TODO_verify_ssa  /* todo_flags_finish */
 936  }
 937 };