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