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