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