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 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, 0);
 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, 0);
 445               elt->value = info.default_values[k];
 446             }
 447
 448           pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
 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, 0);
 472               elt->value = val;
 473
 474               pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
 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;
 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   arr_index_type = build_index_type (info.range_size);
 668   tmp = create_tmp_var (TREE_TYPE (info.index_expr), "csti");
 669   add_referenced_var (tmp);
 670   tidx = make_ssa_name (tmp, NULL);
 671   sub = fold_build2_loc (loc, MINUS_EXPR,
 672                      TREE_TYPE (info.index_expr), info.index_expr,
 673                      fold_convert_loc (loc, TREE_TYPE (info.index_expr),
 674                                        info.range_min));
 675   sub = force_gimple_operand_gsi (&gsi, sub,
 676                                   false, NULL, true, GSI_SAME_STMT);
 677   stmt = gimple_build_assign (tidx, sub);
 678   SSA_NAME_DEF_STMT (tidx) = stmt;
 679
 680   gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
 681   update_stmt (stmt);
 682   info.arr_ref_first = stmt;
 683
 684   for (gsi = gsi_start_phis (info.final_bb), i = 0;
 685        !gsi_end_p (gsi); gsi_next (&gsi), i++)
 686     build_one_array (swtch, i, arr_index_type, gsi_stmt (gsi), tidx);
 687 }
 688
 689 /* Generates and appropriately inserts loads of default values at the position
 690    given by BSI.  Returns the last inserted statement.  */
 691
 692 static gimple
 693 gen_def_assigns (gimple_stmt_iterator *gsi)
 694 {
 695   int i;
 696   gimple assign = NULL;
 697
 698   for (i = 0; i < info.phi_count; i++)
 699     {
 700       tree name
 701         = make_ssa_name (SSA_NAME_VAR (info.target_inbound_names[i]), NULL);
 702
 703       info.target_outbound_names[i] = name;
 704       assign = gimple_build_assign (name, info.default_values[i]);
 705       SSA_NAME_DEF_STMT (name) = assign;
 706       gsi_insert_before (gsi, assign, GSI_SAME_STMT);
 707       update_stmt (assign);
 708     }
 709   return assign;
 710 }
 711
 712 /* Deletes the unused bbs and edges that now contain the switch statement and
 713    its empty branch bbs.  BBD is the now dead BB containing the original switch
 714    statement, FINAL is the last BB of the converted switch statement (in terms
 715    of succession).  */
 716
 717 static void
 718 prune_bbs (basic_block bbd, basic_block final)
 719 {
 720   edge_iterator ei;
 721   edge e;
 722
 723   for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
 724     {
 725       basic_block bb;
 726       bb = e->dest;
 727       remove_edge (e);
 728       if (bb != final)
 729         delete_basic_block (bb);
 730     }
 731   delete_basic_block (bbd);
 732 }
 733
 734 /* Add values to phi nodes in final_bb for the two new edges.  E1F is the edge
 735    from the basic block loading values from an array and E2F from the basic
 736    block loading default values.  BBF is the last switch basic block (see the
 737    bbf description in the comment below).  */
 738
 739 static void
 740 fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
 741 {
 742   gimple_stmt_iterator gsi;
 743   int i;
 744
 745   for (gsi = gsi_start_phis (bbf), i = 0;
 746        !gsi_end_p (gsi); gsi_next (&gsi), i++)
 747     {
 748       gimple phi = gsi_stmt (gsi);
 749       add_phi_arg (phi, info.target_inbound_names[i], e1f, UNKNOWN_LOCATION);
 750       add_phi_arg (phi, info.target_outbound_names[i], e2f, UNKNOWN_LOCATION);
 751     }
 752
 753 }
 754
 755 /* Creates a check whether the switch expression value actually falls into the
 756    range given by all the cases.  If it does not, the temporaries are loaded
 757    with default values instead.  SWTCH is the switch statement being converted.
 758
 759    bb0 is the bb with the switch statement, however, we'll end it with a
 760        condition instead.
 761
 762    bb1 is the bb to be used when the range check went ok.  It is derived from
 763        the switch BB
 764
 765    bb2 is the bb taken when the expression evaluated outside of the range
 766        covered by the created arrays.  It is populated by loads of default
 767        values.
 768
 769    bbF is a fall through for both bb1 and bb2 and contains exactly what
 770        originally followed the switch statement.
 771
 772    bbD contains the switch statement (in the end).  It is unreachable but we
 773        still need to strip off its edges.
 774 */
 775
 776 static void
 777 gen_inbound_check (gimple swtch)
 778 {
 779   tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
 780   tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
 781   tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
 782   gimple label1, label2, label3;
 783
 784   tree utype;
 785   tree tmp_u_1, tmp_u_2, tmp_u_var;
 786   tree cast;
 787   gimple cast_assign, minus_assign;
 788   tree ulb, minus;
 789   tree bound;
 790
 791   gimple cond_stmt;
 792
 793   gimple last_assign;
 794   gimple_stmt_iterator gsi;
 795   basic_block bb0, bb1, bb2, bbf, bbd;
 796   edge e01, e02, e21, e1d, e1f, e2f;
 797   location_t loc = gimple_location (swtch);
 798
 799   gcc_assert (info.default_values);
 800   bb0 = gimple_bb (swtch);
 801
 802   /* Make sure we do not generate arithmetics in a subrange.  */
 803   if (TREE_TYPE (TREE_TYPE (info.index_expr)))
 804     utype = lang_hooks.types.type_for_mode
 805       (TYPE_MODE (TREE_TYPE (TREE_TYPE (info.index_expr))), 1);
 806   else
 807     utype = lang_hooks.types.type_for_mode
 808       (TYPE_MODE (TREE_TYPE (info.index_expr)), 1);
 809
 810   /* (end of) block 0 */
 811   gsi = gsi_for_stmt (info.arr_ref_first);
 812   tmp_u_var = create_tmp_var (utype, "csui");
 813   add_referenced_var (tmp_u_var);
 814   tmp_u_1 = make_ssa_name (tmp_u_var, NULL);
 815
 816   cast = fold_convert_loc (loc, utype, info.index_expr);
 817   cast_assign = gimple_build_assign (tmp_u_1, cast);
 818   SSA_NAME_DEF_STMT (tmp_u_1) = cast_assign;
 819   gsi_insert_before (&gsi, cast_assign, GSI_SAME_STMT);
 820   update_stmt (cast_assign);
 821
 822   ulb = fold_convert_loc (loc, utype, info.range_min);
 823   minus = fold_build2_loc (loc, MINUS_EXPR, utype, tmp_u_1, ulb);
 824   minus = force_gimple_operand_gsi (&gsi, minus, false, NULL, true,
 825                                     GSI_SAME_STMT);
 826   tmp_u_2 = make_ssa_name (tmp_u_var, NULL);
 827   minus_assign = gimple_build_assign (tmp_u_2, minus);
 828   SSA_NAME_DEF_STMT (tmp_u_2) = minus_assign;
 829   gsi_insert_before (&gsi, minus_assign, GSI_SAME_STMT);
 830   update_stmt (minus_assign);
 831
 832   bound = fold_convert_loc (loc, utype, info.range_size);
 833   cond_stmt = gimple_build_cond (LE_EXPR, tmp_u_2, bound, NULL_TREE, NULL_TREE);
 834   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
 835   update_stmt (cond_stmt);
 836
 837   /* block 2 */
 838   gsi = gsi_for_stmt (info.arr_ref_first);
 839   label2 = gimple_build_label (label_decl2);
 840   gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
 841   last_assign = gen_def_assigns (&gsi);
 842
 843   /* block 1 */
 844   gsi = gsi_for_stmt (info.arr_ref_first);
 845   label1 = gimple_build_label (label_decl1);
 846   gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
 847
 848   /* block F */
 849   gsi = gsi_start_bb (info.final_bb);
 850   label3 = gimple_build_label (label_decl3);
 851   gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
 852
 853   /* cfg fix */
 854   e02 = split_block (bb0, cond_stmt);
 855   bb2 = e02->dest;
 856
 857   e21 = split_block (bb2, last_assign);
 858   bb1 = e21->dest;
 859   remove_edge (e21);
 860
 861   e1d = split_block (bb1, info.arr_ref_last);
 862   bbd = e1d->dest;
 863   remove_edge (e1d);
 864
 865   /* flags and profiles of the edge for in-range values */
 866   e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
 867   e01->probability = REG_BR_PROB_BASE - info.default_prob;
 868   e01->count = info.other_count;
 869
 870   /* flags and profiles of the edge taking care of out-of-range values */
 871   e02->flags &= ~EDGE_FALLTHRU;
 872   e02->flags |= EDGE_FALSE_VALUE;
 873   e02->probability = info.default_prob;
 874   e02->count = info.default_count;
 875
 876   bbf = info.final_bb;
 877
 878   e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
 879   e1f->probability = REG_BR_PROB_BASE;
 880   e1f->count = info.other_count;
 881
 882   e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
 883   e2f->probability = REG_BR_PROB_BASE;
 884   e2f->count = info.default_count;
 885
 886   /* frequencies of the new BBs */
 887   bb1->frequency = EDGE_FREQUENCY (e01);
 888   bb2->frequency = EDGE_FREQUENCY (e02);
 889   bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
 890
 891   prune_bbs (bbd, info.final_bb); /* To keep calc_dfs_tree() in dominance.c
 892                                      happy.  */
 893
 894   fix_phi_nodes (e1f, e2f, bbf);
 895
 896   free_dominance_info (CDI_DOMINATORS);
 897   free_dominance_info (CDI_POST_DOMINATORS);
 898 }
 899
 900 /* The following function is invoked on every switch statement (the current one
 901    is given in SWTCH) and runs the individual phases of switch conversion on it
 902    one after another until one fails or the conversion is completed.  */
 903
 904 static bool
 905 process_switch (gimple swtch)
 906 {
 907   unsigned int i, branch_num = gimple_switch_num_labels (swtch);
 908   tree index_type;
 909
 910   /* Operand 2 is either NULL_TREE or a vector of cases (stmt.c).  */
 911   if (branch_num < 2)
 912     {
 913       info.reason = "switch has no labels\n";
 914       return false;
 915     }
 916
 917   info.final_bb = NULL;
 918   info.switch_bb = gimple_bb (swtch);
 919   info.index_expr = gimple_switch_index (swtch);
 920   index_type = TREE_TYPE (info.index_expr);
 921   info.arr_ref_first = NULL;
 922   info.arr_ref_last = NULL;
 923   info.default_prob = 0;
 924   info.default_count = 0;
 925   info.other_count = 0;
 926   info.bit_test_uniq = 0;
 927   info.bit_test_count = 0;
 928   info.bit_test_bb[0] = NULL;
 929   info.bit_test_bb[1] = NULL;
 930
 931   /* An ERROR_MARK occurs for various reasons including invalid data type.
 932      (comment from stmt.c) */
 933   if (index_type == error_mark_node)
 934     {
 935       info.reason = "index error.\n";
 936       return false;
 937     }
 938
 939   /* Check the case label values are within reasonable range:  */
 940   if (!check_range (swtch))
 941     return false;
 942
 943   /* For all the cases, see whether they are empty, the assignments they
 944      represent constant and so on...  */
 945   for (i = 0; i < branch_num; i++)
 946     if (!check_process_case (gimple_switch_label (swtch, i)))
 947       {
 948         if (dump_file)
 949           fprintf (dump_file, "Processing of case %i failed\n", i);
 950         return false;
 951       }
 952
 953   if (info.bit_test_uniq <= 2)
 954     {
 955       rtl_profile_for_bb (gimple_bb (swtch));
 956       if (expand_switch_using_bit_tests_p (gimple_switch_index (swtch),
 957                                            info.range_size, info.bit_test_uniq,
 958                                            info.bit_test_count))
 959         {
 960           info.reason = "  Expanding as bit test is preferable\n";
 961           return false;
 962         }
 963     }
 964
 965   if (!check_final_bb ())
 966     return false;
 967
 968   /* At this point all checks have passed and we can proceed with the
 969      transformation.  */
 970
 971   create_temp_arrays ();
 972   gather_default_values (gimple_switch_label (swtch, 0));
 973   build_constructors (swtch);
 974
 975   build_arrays (swtch); /* Build the static arrays and assignments.   */
 976   gen_inbound_check (swtch);    /* Build the bounds check.  */
 977
 978   /* Cleanup:  */
 979   free_temp_arrays ();
 980   return true;
 981 }
 982
 983 /* The main function of the pass scans statements for switches and invokes
 984    process_switch on them.  */
 985
 986 static unsigned int
 987 do_switchconv (void)
 988 {
 989   basic_block bb;
 990
 991   FOR_EACH_BB (bb)
 992   {
 993     gimple stmt = last_stmt (bb);
 994     if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
 995       {
 996         if (dump_file)
 997           {
 998             expanded_location loc = expand_location (gimple_location (stmt));
 999
1000             fprintf (dump_file, "beginning to process the following "
1001                      "SWITCH statement (%s:%d) : ------- \n",
1002                      loc.file, loc.line);
1003             print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1004             putc ('\n', dump_file);
1005           }
1006
1007         info.reason = NULL;
1008         if (process_switch (stmt))
1009           {
1010             if (dump_file)
1011               {
1012                 fputs ("Switch converted\n", dump_file);
1013                 fputs ("--------------------------------\n", dump_file);
1014               }
1015           }
1016         else
1017           {
1018             if (dump_file)
1019               {
1020                 gcc_assert (info.reason);
1021                 fputs ("Bailing out - ", dump_file);
1022                 fputs (info.reason, dump_file);
1023                 fputs ("--------------------------------\n", dump_file);
1024               }
1025           }
1026       }
1027   }
1028
1029   return 0;
1030 }
1031
1032 /* The pass gate. */
1033
1034 static bool
1035 switchconv_gate (void)
1036 {
1037   return flag_tree_switch_conversion != 0;
1038 }
1039
1040 struct gimple_opt_pass pass_convert_switch =
1041 {
1042  {
1043   GIMPLE_PASS,
1044   "switchconv",                         /* name */
1045   switchconv_gate,                      /* gate */
1046   do_switchconv,                        /* execute */
1047   NULL,                                 /* sub */
1048   NULL,                                 /* next */
1049   0,                                    /* static_pass_number */
1050   TV_TREE_SWITCH_CONVERSION,            /* tv_id */
1051   PROP_cfg | PROP_ssa,                  /* properties_required */
1052   0,                                    /* properties_provided */
1053   0,                                    /* properties_destroyed */
1054   0,                                    /* todo_flags_start */
1055   TODO_update_ssa | TODO_dump_func
1056   | TODO_ggc_collect | TODO_verify_ssa  /* todo_flags_finish */
1057  }
1058 };