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               && !is_gimple_ip_invariant (gimple_phi_arg_def (phi, i)))
 302             {
 303               info.reason = "   Non-invariant value from a case\n";
 304               return false; /* Non-invariant argument.  */
 305             }
 306         }
 307     }
 308
 309   return true;
 310 }
 311
 312 /* The following function allocates default_values, target_{in,out}_names and
 313    constructors arrays.  The last one is also populated with pointers to
 314    vectors that will become constructors of new arrays.  */
 315
 316 static void
 317 create_temp_arrays (void)
 318 {
 319   int i;
 320
 321   info.default_values = (tree *) xcalloc (info.phi_count, sizeof (tree));
 322   info.constructors = (VEC (constructor_elt, gc) **) xcalloc (info.phi_count,
 323                                                               sizeof (tree));
 324   info.target_inbound_names = (tree *) xcalloc (info.phi_count, sizeof (tree));
 325   info.target_outbound_names = (tree *) xcalloc (info.phi_count,
 326                                                  sizeof (tree));
 327
 328   for (i = 0; i < info.phi_count; i++)
 329     info.constructors[i]
 330       = VEC_alloc (constructor_elt, gc, tree_low_cst (info.range_size, 1) + 1);
 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   gimple_stmt_iterator gsi;
 353   basic_block bb = label_to_block (CASE_LABEL (default_case));
 354   edge e;
 355   int i = 0;
 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 (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
 365     {
 366       gimple phi = gsi_stmt (gsi);
 367       tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
 368       gcc_assert (val);
 369       info.default_values[i++] = val;
 370     }
 371 }
 372
 373 /* The following function populates the vectors in the constructors array with
 374    future contents of the static arrays.  The vectors are populated in the
 375    order of phi nodes.  SWTCH is the switch statement being converted.  */
 376
 377 static void
 378 build_constructors (gimple swtch)
 379 {
 380   unsigned i, branch_num = gimple_switch_num_labels (swtch);
 381   tree pos = info.range_min;
 382
 383   for (i = 1; i < branch_num; i++)
 384     {
 385       tree cs = gimple_switch_label (swtch, i);
 386       basic_block bb = label_to_block (CASE_LABEL (cs));
 387       edge e;
 388       tree high;
 389       gimple_stmt_iterator gsi;
 390       int j;
 391
 392       if (bb == info.final_bb)
 393         e = find_edge (info.switch_bb, bb);
 394       else
 395         e = single_succ_edge (bb);
 396       gcc_assert (e);
 397
 398       while (tree_int_cst_lt (pos, CASE_LOW (cs)))
 399         {
 400           int k;
 401           for (k = 0; k < info.phi_count; k++)
 402             {
 403               constructor_elt *elt;
 404
 405               elt = VEC_quick_push (constructor_elt,
 406                                     info.constructors[k], NULL);
 407               elt->index = int_const_binop (MINUS_EXPR, pos,
 408                                             info.range_min, 0);
 409               elt->value = info.default_values[k];
 410             }
 411
 412           pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
 413         }
 414       gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
 415
 416       j = 0;
 417       if (CASE_HIGH (cs))
 418         high = CASE_HIGH (cs);
 419       else
 420         high = CASE_LOW (cs);
 421       for (gsi = gsi_start_phis (info.final_bb);
 422            !gsi_end_p (gsi); gsi_next (&gsi))
 423         {
 424           gimple phi = gsi_stmt (gsi);
 425           tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
 426           pos = CASE_LOW (cs);
 427
 428           while (!tree_int_cst_lt (high, pos))
 429             {
 430               constructor_elt *elt;
 431
 432               elt = VEC_quick_push (constructor_elt,
 433                                     info.constructors[j], NULL);
 434               elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min, 0);
 435               elt->value = val;
 436
 437               pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
 438             }
 439           j++;
 440         }
 441     }
 442 }
 443
 444 /* Create an appropriate array type and declaration and assemble a static array
 445    variable.  Also create a load statement that initializes the variable in
 446    question with a value from the static array.  SWTCH is the switch statement
 447    being converted, NUM is the index to arrays of constructors, default values
 448    and target SSA names for this particular array.  ARR_INDEX_TYPE is the type
 449    of the index of the new array, PHI is the phi node of the final BB that
 450    corresponds to the value that will be loaded from the created array.  TIDX
 451    is a temporary variable holding the index for loads from the new array.  */
 452
 453 static void
 454 build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi,
 455                  tree tidx)
 456 {
 457   tree array_type, ctor, decl, value_type, name, fetch;
 458   gimple load;
 459   gimple_stmt_iterator gsi;
 460
 461   gcc_assert (info.default_values[num]);
 462   value_type = TREE_TYPE (info.default_values[num]);
 463   array_type = build_array_type (value_type, arr_index_type);
 464
 465   ctor = build_constructor (array_type, info.constructors[num]);
 466   TREE_CONSTANT (ctor) = true;
 467
 468   decl = build_decl (VAR_DECL, NULL_TREE, array_type);
 469   TREE_STATIC (decl) = 1;
 470   DECL_INITIAL (decl) = ctor;
 471
 472   DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
 473   DECL_ARTIFICIAL (decl) = 1;
 474   TREE_CONSTANT (decl) = 1;
 475   add_referenced_var (decl);
 476   varpool_mark_needed_node (varpool_node (decl));
 477   varpool_finalize_decl (decl);
 478   mark_sym_for_renaming (decl);
 479
 480   name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL);
 481   info.target_inbound_names[num] = name;
 482
 483   fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
 484                   NULL_TREE);
 485   load = gimple_build_assign (name, fetch);
 486   SSA_NAME_DEF_STMT (name) = load;
 487
 488   gsi = gsi_for_stmt (swtch);
 489   gsi_insert_before (&gsi, load, GSI_SAME_STMT);
 490   mark_symbols_for_renaming (load);
 491
 492   info.arr_ref_last = load;
 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 (gimple swtch)
 501 {
 502   tree arr_index_type;
 503   tree tidx, sub;
 504   gimple stmt;
 505   gimple_stmt_iterator gsi;
 506   int i;
 507
 508   gsi = gsi_for_stmt (swtch);
 509
 510   arr_index_type = build_index_type (info.range_size);
 511   tidx = make_rename_temp (arr_index_type, "csti");
 512   sub = fold_build2 (MINUS_EXPR, TREE_TYPE (info.index_expr), info.index_expr,
 513                      fold_convert (TREE_TYPE (info.index_expr),
 514                                    info.range_min));
 515   sub = force_gimple_operand_gsi (&gsi, fold_convert (arr_index_type, sub),
 516                                   false, NULL, true, GSI_SAME_STMT);
 517   stmt = gimple_build_assign (tidx, sub);
 518
 519   gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
 520   mark_symbols_for_renaming (stmt);
 521   info.arr_ref_first = stmt;
 522
 523   for (gsi = gsi_start_phis (info.final_bb), i = 0;
 524        !gsi_end_p (gsi); gsi_next (&gsi), i++)
 525     build_one_array (swtch, i, arr_index_type, gsi_stmt (gsi), tidx);
 526 }
 527
 528 /* Generates and appropriately inserts loads of default values at the position
 529    given by BSI.  Returns the last inserted statement.  */
 530
 531 static gimple
 532 gen_def_assigns (gimple_stmt_iterator *gsi)
 533 {
 534   int i;
 535   gimple assign = NULL;
 536
 537   for (i = 0; i < info.phi_count; i++)
 538     {
 539       tree name
 540         = make_ssa_name (SSA_NAME_VAR (info.target_inbound_names[i]), NULL);
 541
 542       info.target_outbound_names[i] = name;
 543       assign = gimple_build_assign (name, info.default_values[i]);
 544       SSA_NAME_DEF_STMT (name) = assign;
 545       gsi_insert_before (gsi, assign, GSI_SAME_STMT);
 546       find_new_referenced_vars (assign);
 547       mark_symbols_for_renaming (assign);
 548     }
 549   return assign;
 550 }
 551
 552 /* Deletes the unused bbs and edges that now contain the switch statement and
 553    its empty branch bbs.  BBD is the now dead BB containing the original switch
 554    statement, FINAL is the last BB of the converted switch statement (in terms
 555    of succession).  */
 556
 557 static void
 558 prune_bbs (basic_block bbd, basic_block final)
 559 {
 560   edge_iterator ei;
 561   edge e;
 562
 563   for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
 564     {
 565       basic_block bb;
 566       bb = e->dest;
 567       remove_edge (e);
 568       if (bb != final)
 569         delete_basic_block (bb);
 570     }
 571   delete_basic_block (bbd);
 572 }
 573
 574 /* Add values to phi nodes in final_bb for the two new edges.  E1F is the edge
 575    from the basic block loading values from an array and E2F from the basic
 576    block loading default values.  BBF is the last switch basic block (see the
 577    bbf description in the comment below).  */
 578
 579 static void
 580 fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
 581 {
 582   gimple_stmt_iterator gsi;
 583   int i;
 584
 585   for (gsi = gsi_start_phis (bbf), i = 0;
 586        !gsi_end_p (gsi); gsi_next (&gsi), i++)
 587     {
 588       gimple phi = gsi_stmt (gsi);
 589       add_phi_arg (phi, info.target_inbound_names[i], e1f);
 590       add_phi_arg (phi, info.target_outbound_names[i], e2f);
 591     }
 592
 593 }
 594
 595 /* Creates a check whether the switch expression value actually falls into the
 596    range given by all the cases.  If it does not, the temporaries are loaded
 597    with default values instead.  SWTCH is the switch statement being converted.
 598
 599    bb0 is the bb with the switch statement, however, we'll end it with a
 600        condition instead.
 601
 602    bb1 is the bb to be used when the range check went ok.  It is derived from
 603        the switch BB
 604
 605    bb2 is the bb taken when the expression evaluated outside of the range
 606        covered by the created arrays.  It is populated by loads of default
 607        values.
 608
 609    bbF is a fall through for both bb1 and bb2 and contains exactly what
 610        originally followed the switch statement.
 611
 612    bbD contains the switch statement (in the end).  It is unreachable but we
 613        still need to strip off its edges.
 614 */
 615
 616 static void
 617 gen_inbound_check (gimple swtch)
 618 {
 619   tree label_decl1 = create_artificial_label ();
 620   tree label_decl2 = create_artificial_label ();
 621   tree label_decl3 = create_artificial_label ();
 622   gimple label1, label2, label3;
 623
 624   tree utype;
 625   tree tmp_u;
 626   tree cast;
 627   gimple cast_assign, minus_assign;
 628   tree ulb, minus;
 629   tree bound;
 630
 631   gimple cond_stmt;
 632
 633   gimple last_assign;
 634   gimple_stmt_iterator gsi;
 635   basic_block bb0, bb1, bb2, bbf, bbd;
 636   edge e01, e02, e21, e1d, e1f, e2f;
 637
 638   gcc_assert (info.default_values);
 639   bb0 = gimple_bb (swtch);
 640
 641   /* Make sure we do not generate arithmetics in a subrange.  */
 642   if (TREE_TYPE (TREE_TYPE (info.index_expr)))
 643     utype = unsigned_type_for (TREE_TYPE (TREE_TYPE (info.index_expr)));
 644   else
 645     utype = unsigned_type_for (TREE_TYPE (info.index_expr));
 646
 647   /* (end of) block 0 */
 648   gsi = gsi_for_stmt (info.arr_ref_first);
 649   tmp_u = make_rename_temp (utype, "csui");
 650
 651   cast = fold_convert (utype, info.index_expr);
 652   cast_assign = gimple_build_assign (tmp_u, cast);
 653   find_new_referenced_vars (cast_assign);
 654   gsi_insert_before (&gsi, cast_assign, GSI_SAME_STMT);
 655   mark_symbols_for_renaming (cast_assign);
 656
 657   ulb = fold_convert (utype, info.range_min);
 658   minus = fold_build2 (MINUS_EXPR, utype, tmp_u, ulb);
 659   minus = force_gimple_operand_gsi (&gsi, minus, false, NULL, true,
 660                                     GSI_SAME_STMT);
 661   minus_assign = gimple_build_assign (tmp_u, minus);
 662   find_new_referenced_vars (minus_assign);
 663   gsi_insert_before (&gsi, minus_assign, GSI_SAME_STMT);
 664   mark_symbols_for_renaming (minus_assign);
 665
 666   bound = fold_convert (utype, info.range_size);
 667
 668   cond_stmt = gimple_build_cond (LE_EXPR, tmp_u, bound, NULL_TREE, NULL_TREE);
 669
 670   find_new_referenced_vars (cond_stmt);
 671   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
 672   mark_symbols_for_renaming (cond_stmt);
 673
 674   /* block 2 */
 675   gsi = gsi_for_stmt (info.arr_ref_first);
 676   label2 = gimple_build_label (label_decl2);
 677   gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
 678   last_assign = gen_def_assigns (&gsi);
 679
 680   /* block 1 */
 681   gsi = gsi_for_stmt (info.arr_ref_first);
 682   label1 = gimple_build_label (label_decl1);
 683   gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
 684
 685   /* block F */
 686   gsi = gsi_start_bb (info.final_bb);
 687   label3 = gimple_build_label (label_decl3);
 688   gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
 689
 690   /* cfg fix */
 691   e02 = split_block (bb0, cond_stmt);
 692   bb2 = e02->dest;
 693
 694   e21 = split_block (bb2, last_assign);
 695   bb1 = e21->dest;
 696   remove_edge (e21);
 697
 698   e1d = split_block (bb1, info.arr_ref_last);
 699   bbd = e1d->dest;
 700   remove_edge (e1d);
 701
 702   /* flags and profiles of the edge for in-range values */
 703   e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
 704   e01->probability = REG_BR_PROB_BASE - info.default_prob;
 705   e01->count = info.other_count;
 706
 707   /* flags and profiles of the edge taking care of out-of-range values */
 708   e02->flags &= ~EDGE_FALLTHRU;
 709   e02->flags |= EDGE_FALSE_VALUE;
 710   e02->probability = info.default_prob;
 711   e02->count = info.default_count;
 712
 713   bbf = info.final_bb;
 714
 715   e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
 716   e1f->probability = REG_BR_PROB_BASE;
 717   e1f->count = info.other_count;
 718
 719   e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
 720   e2f->probability = REG_BR_PROB_BASE;
 721   e2f->count = info.default_count;
 722
 723   /* frequencies of the new BBs */
 724   bb1->frequency = EDGE_FREQUENCY (e01);
 725   bb2->frequency = EDGE_FREQUENCY (e02);
 726   bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
 727
 728   prune_bbs (bbd, info.final_bb); /* To keep calc_dfs_tree() in dominance.c
 729                                      happy.  */
 730
 731   fix_phi_nodes (e1f, e2f, bbf);
 732
 733   free_dominance_info (CDI_DOMINATORS);
 734   free_dominance_info (CDI_POST_DOMINATORS);
 735 }
 736
 737 /* The following function is invoked on every switch statement (the current one
 738    is given in SWTCH) and runs the individual phases of switch conversion on it
 739    one after another until one fails or the conversion is completed.  */
 740
 741 static bool
 742 process_switch (gimple swtch)
 743 {
 744   unsigned int i, branch_num = gimple_switch_num_labels (swtch);
 745   tree index_type;
 746
 747   /* Operand 2 is either NULL_TREE or a vector of cases (stmt.c).  */
 748   if (branch_num < 2)
 749     {
 750       info.reason = "switch has no labels\n";
 751       return false;
 752     }
 753
 754   info.final_bb = NULL;
 755   info.switch_bb = gimple_bb (swtch);
 756   info.index_expr = gimple_switch_index (swtch);
 757   index_type = TREE_TYPE (info.index_expr);
 758   info.arr_ref_first = NULL;
 759   info.arr_ref_last = NULL;
 760   info.default_prob = 0;
 761   info.default_count = 0;
 762   info.other_count = 0;
 763
 764   /* An ERROR_MARK occurs for various reasons including invalid data type.
 765      (comment from stmt.c) */
 766   if (index_type == error_mark_node)
 767     {
 768       info.reason = "index error.\n";
 769       return false;
 770     }
 771
 772   /* Check the case label values are within reasonable range:  */
 773   if (!check_range (swtch))
 774     return false;
 775
 776   /* For all the cases, see whether they are empty, the assignments they
 777      represent constant and so on...  */
 778   for (i = 0; i < branch_num; i++)
 779     if (!check_process_case (gimple_switch_label (swtch, i)))
 780       {
 781         if (dump_file)
 782           fprintf (dump_file, "Processing of case %i failed\n", i);
 783         return false;
 784       }
 785
 786   if (!check_final_bb ())
 787     return false;
 788
 789   /* At this point all checks have passed and we can proceed with the
 790      transformation.  */
 791
 792   create_temp_arrays ();
 793   gather_default_values (gimple_switch_label (swtch, 0));
 794   build_constructors (swtch);
 795
 796   build_arrays (swtch); /* Build the static arrays and assignments.   */
 797   gen_inbound_check (swtch);    /* Build the bounds check.  */
 798
 799   /* Cleanup:  */
 800   free_temp_arrays ();
 801   return true;
 802 }
 803
 804 /* The main function of the pass scans statements for switches and invokes
 805    process_switch on them.  */
 806
 807 static unsigned int
 808 do_switchconv (void)
 809 {
 810   basic_block bb;
 811
 812   FOR_EACH_BB (bb)
 813   {
 814     gimple stmt = last_stmt (bb);
 815     if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
 816       {
 817         if (dump_file)
 818           {
 819             expanded_location loc = expand_location (gimple_location (stmt));
 820
 821             fprintf (dump_file, "beginning to process the following "
 822                      "SWITCH statement (%s:%d) : ------- \n",
 823                      loc.file, loc.line);
 824             print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 825             fprintf (dump_file, "\n");
 826           }
 827
 828         info.reason = NULL;
 829         if (process_switch (stmt))
 830           {
 831             if (dump_file)
 832               {
 833                 fprintf (dump_file, "Switch converted\n");
 834                 fprintf (dump_file, "--------------------------------\n");
 835               }
 836           }
 837         else
 838           {
 839             if (dump_file)
 840               {
 841                 gcc_assert (info.reason);
 842                 fprintf (dump_file, "Bailing out - ");
 843                 fprintf (dump_file, info.reason);
 844                 fprintf (dump_file, "--------------------------------\n");
 845               }
 846           }
 847       }
 848   }
 849
 850   return 0;
 851 }
 852
 853 /* The pass gate. */
 854
 855 static bool
 856 switchconv_gate (void)
 857 {
 858   return flag_tree_switch_conversion != 0;
 859 }
 860
 861 struct gimple_opt_pass pass_convert_switch =
 862 {
 863  {
 864   GIMPLE_PASS,
 865   "switchconv",                         /* name */
 866   switchconv_gate,                      /* gate */
 867   do_switchconv,                        /* execute */
 868   NULL,                                 /* sub */
 869   NULL,                                 /* next */
 870   0,                                    /* static_pass_number */
 871   TV_TREE_SWITCH_CONVERSION,            /* tv_id */
 872   PROP_cfg | PROP_ssa,                  /* properties_required */
 873   0,                                    /* properties_provided */
 874   0,                                    /* properties_destroyed */
 875   0,                                    /* todo_flags_start */
 876   TODO_update_ssa | TODO_dump_func
 877   | TODO_ggc_collect | TODO_verify_ssa  /* todo_flags_finish */
 878  }
 879 };