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