gcc/tree-switch-conversion.c

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