1/* Lower GIMPLE_SWITCH expressions to something more efficient than 2 a jump table. 3 Copyright (C) 2006-2015 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it 8under the terms of the GNU General Public License as published by the 9Free Software Foundation; either version 3, or (at your option) any 10later version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT 13ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22/* This file handles the lowering of GIMPLE_SWITCH to an indexed 23 load, or a series of bit-test-and-branch expressions. */ 24 25#include "config.h" 26#include "system.h" 27#include "coretypes.h" 28#include "tm.h" 29#include "line-map.h" 30#include "params.h" 31#include "flags.h" 32#include "hash-set.h" 33#include "machmode.h" 34#include "vec.h" 35#include "double-int.h" 36#include "input.h" 37#include "alias.h" 38#include "symtab.h" 39#include "wide-int.h" 40#include "inchash.h" 41#include "tree.h" 42#include "fold-const.h" 43#include "varasm.h" 44#include "stor-layout.h" 45#include "predict.h" 46#include "hard-reg-set.h" 47#include "function.h" 48#include "dominance.h" 49#include "cfg.h" 50#include "cfganal.h" 51#include "basic-block.h" 52#include "tree-ssa-alias.h" 53#include "internal-fn.h" 54#include "gimple-expr.h" 55#include "is-a.h" 56#include "gimple.h" 57#include "gimplify.h" 58#include "gimple-iterator.h" 59#include "gimplify-me.h" 60#include "gimple-ssa.h" 61#include "hash-map.h" 62#include "plugin-api.h" 63#include "ipa-ref.h" 64#include "cgraph.h" 65#include "tree-cfg.h" 66#include "tree-phinodes.h" 67#include "stringpool.h" 68#include "tree-ssanames.h" 69#include "tree-pass.h" 70#include "gimple-pretty-print.h" 71#include "cfgloop.h" 72 73/* ??? For lang_hooks.types.type_for_mode, but is there a word_mode 74 type in the GIMPLE type system that is language-independent? */ 75#include "langhooks.h" 76 77/* Need to include expr.h and optabs.h for lshift_cheap_p. */ 78#include "hashtab.h" 79#include "rtl.h" 80#include "statistics.h" 81#include "real.h" 82#include "fixed-value.h" 83#include "insn-config.h" 84#include "expmed.h" 85#include "dojump.h" 86#include "explow.h" 87#include "calls.h" 88#include "emit-rtl.h" 89#include "stmt.h" 90#include "expr.h" 91#include "insn-codes.h" 92#include "optabs.h" 93 94/* Maximum number of case bit tests. 95 FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and 96 targetm.case_values_threshold(), or be its own param. */ 97#define MAX_CASE_BIT_TESTS 3 98 99/* Split the basic block at the statement pointed to by GSIP, and insert 100 a branch to the target basic block of E_TRUE conditional on tree 101 expression COND. 102 103 It is assumed that there is already an edge from the to-be-split 104 basic block to E_TRUE->dest block. This edge is removed, and the 105 profile information on the edge is re-used for the new conditional 106 jump. 107 108 The CFG is updated. The dominator tree will not be valid after 109 this transformation, but the immediate dominators are updated if 110 UPDATE_DOMINATORS is true. 111 112 Returns the newly created basic block. */ 113 114static basic_block 115hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, 116 tree cond, edge e_true, 117 bool update_dominators) 118{ 119 tree tmp; 120 gcond *cond_stmt; 121 edge e_false; 122 basic_block new_bb, split_bb = gsi_bb (*gsip); 123 bool dominated_e_true = false; 124 125 gcc_assert (e_true->src == split_bb); 126 127 if (update_dominators 128 && get_immediate_dominator (CDI_DOMINATORS, e_true->dest) == split_bb) 129 dominated_e_true = true; 130 131 tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL, 132 /*before=*/true, GSI_SAME_STMT); 133 cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE); 134 gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT); 135 136 e_false = split_block (split_bb, cond_stmt); 137 new_bb = e_false->dest; 138 redirect_edge_pred (e_true, split_bb); 139 140 e_true->flags &= ~EDGE_FALLTHRU; 141 e_true->flags |= EDGE_TRUE_VALUE; 142 143 e_false->flags &= ~EDGE_FALLTHRU; 144 e_false->flags |= EDGE_FALSE_VALUE; 145 e_false->probability = REG_BR_PROB_BASE - e_true->probability; 146 e_false->count = split_bb->count - e_true->count; 147 new_bb->count = e_false->count; 148 149 if (update_dominators) 150 { 151 if (dominated_e_true) 152 set_immediate_dominator (CDI_DOMINATORS, e_true->dest, split_bb); 153 set_immediate_dominator (CDI_DOMINATORS, e_false->dest, split_bb); 154 } 155 156 return new_bb; 157} 158 159 160/* Return true if a switch should be expanded as a bit test. 161 RANGE is the difference between highest and lowest case. 162 UNIQ is number of unique case node targets, not counting the default case. 163 COUNT is the number of comparisons needed, not counting the default case. */ 164 165static bool 166expand_switch_using_bit_tests_p (tree range, 167 unsigned int uniq, 168 unsigned int count, bool speed_p) 169{ 170 return (((uniq == 1 && count >= 3) 171 || (uniq == 2 && count >= 5) 172 || (uniq == 3 && count >= 6)) 173 && lshift_cheap_p (speed_p) 174 && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0 175 && compare_tree_int (range, 0) > 0); 176} 177 178/* Implement switch statements with bit tests 179 180A GIMPLE switch statement can be expanded to a short sequence of bit-wise 181comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)" 182where CST and MINVAL are integer constants. This is better than a series 183of compare-and-banch insns in some cases, e.g. we can implement: 184 185 if ((x==4) || (x==6) || (x==9) || (x==11)) 186 187as a single bit test: 188 189 if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11))) 190 191This transformation is only applied if the number of case targets is small, 192if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are 193performed in "word_mode". 194 195The following example shows the code the transformation generates: 196 197 int bar(int x) 198 { 199 switch (x) 200 { 201 case '0': case '1': case '2': case '3': case '4': 202 case '5': case '6': case '7': case '8': case '9': 203 case 'A': case 'B': case 'C': case 'D': case 'E': 204 case 'F': 205 return 1; 206 } 207 return 0; 208 } 209 210==> 211 212 bar (int x) 213 { 214 tmp1 = x - 48; 215 if (tmp1 > (70 - 48)) goto L2; 216 tmp2 = 1 << tmp1; 217 tmp3 = 0b11111100000001111111111; 218 if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2; 219 L1: 220 return 1; 221 L2: 222 return 0; 223 } 224 225TODO: There are still some improvements to this transformation that could 226be implemented: 227 228* A narrower mode than word_mode could be used if that is cheaper, e.g. 229 for x86_64 where a narrower-mode shift may result in smaller code. 230 231* The compounded constant could be shifted rather than the one. The 232 test would be either on the sign bit or on the least significant bit, 233 depending on the direction of the shift. On some machines, the test 234 for the branch would be free if the bit to test is already set by the 235 shift operation. 236 237This transformation was contributed by Roger Sayle, see this e-mail: 238 http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html 239*/ 240 241/* A case_bit_test represents a set of case nodes that may be 242 selected from using a bit-wise comparison. HI and LO hold 243 the integer to be tested against, TARGET_EDGE contains the 244 edge to the basic block to jump to upon success and BITS 245 counts the number of case nodes handled by this test, 246 typically the number of bits set in HI:LO. The LABEL field 247 is used to quickly identify all cases in this set without 248 looking at label_to_block for every case label. */ 249 250struct case_bit_test 251{ 252 wide_int mask; 253 edge target_edge; 254 tree label; 255 int bits; 256}; 257 258/* Comparison function for qsort to order bit tests by decreasing 259 probability of execution. Our best guess comes from a measured 260 profile. If the profile counts are equal, break even on the 261 number of case nodes, i.e. the node with the most cases gets 262 tested first. 263 264 TODO: Actually this currently runs before a profile is available. 265 Therefore the case-as-bit-tests transformation should be done 266 later in the pass pipeline, or something along the lines of 267 "Efficient and effective branch reordering using profile data" 268 (Yang et. al., 2002) should be implemented (although, how good 269 is a paper is called "Efficient and effective ..." when the 270 latter is implied by the former, but oh well...). */ 271 272static int 273case_bit_test_cmp (const void *p1, const void *p2) 274{ 275 const struct case_bit_test *const d1 = (const struct case_bit_test *) p1; 276 const struct case_bit_test *const d2 = (const struct case_bit_test *) p2; 277 278 if (d2->target_edge->count != d1->target_edge->count) 279 return d2->target_edge->count - d1->target_edge->count; 280 if (d2->bits != d1->bits) 281 return d2->bits - d1->bits; 282 283 /* Stabilize the sort. */ 284 return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (d1->label); 285} 286 287/* Expand a switch statement by a short sequence of bit-wise 288 comparisons. "switch(x)" is effectively converted into 289 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are 290 integer constants. 291 292 INDEX_EXPR is the value being switched on. 293 294 MINVAL is the lowest case value of in the case nodes, 295 and RANGE is highest value minus MINVAL. MINVAL and RANGE 296 are not guaranteed to be of the same type as INDEX_EXPR 297 (the gimplifier doesn't change the type of case label values, 298 and MINVAL and RANGE are derived from those values). 299 MAXVAL is MINVAL + RANGE. 300 301 There *MUST* be MAX_CASE_BIT_TESTS or less unique case 302 node targets. */ 303 304static void 305emit_case_bit_tests (gswitch *swtch, tree index_expr, 306 tree minval, tree range, tree maxval) 307{ 308 struct case_bit_test test[MAX_CASE_BIT_TESTS]; 309 unsigned int i, j, k; 310 unsigned int count; 311 312 basic_block switch_bb = gimple_bb (swtch); 313 basic_block default_bb, new_default_bb, new_bb; 314 edge default_edge; 315 bool update_dom = dom_info_available_p (CDI_DOMINATORS); 316 317 vec<basic_block> bbs_to_fix_dom = vNULL; 318 319 tree index_type = TREE_TYPE (index_expr); 320 tree unsigned_index_type = unsigned_type_for (index_type); 321 unsigned int branch_num = gimple_switch_num_labels (swtch); 322 323 gimple_stmt_iterator gsi; 324 gassign *shift_stmt; 325 326 tree idx, tmp, csui; 327 tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1); 328 tree word_mode_zero = fold_convert (word_type_node, integer_zero_node); 329 tree word_mode_one = fold_convert (word_type_node, integer_one_node); 330 int prec = TYPE_PRECISION (word_type_node); 331 wide_int wone = wi::one (prec); 332 333 memset (&test, 0, sizeof (test)); 334 335 /* Get the edge for the default case. */ 336 tmp = gimple_switch_default_label (swtch); 337 default_bb = label_to_block (CASE_LABEL (tmp)); 338 default_edge = find_edge (switch_bb, default_bb); 339 340 /* Go through all case labels, and collect the case labels, profile 341 counts, and other information we need to build the branch tests. */ 342 count = 0; 343 for (i = 1; i < branch_num; i++) 344 { 345 unsigned int lo, hi; 346 tree cs = gimple_switch_label (swtch, i); 347 tree label = CASE_LABEL (cs); 348 edge e = find_edge (switch_bb, label_to_block (label)); 349 for (k = 0; k < count; k++) 350 if (e == test[k].target_edge) 351 break; 352 353 if (k == count) 354 { 355 gcc_checking_assert (count < MAX_CASE_BIT_TESTS); 356 test[k].mask = wi::zero (prec); 357 test[k].target_edge = e; 358 test[k].label = label; 359 test[k].bits = 1; 360 count++; 361 } 362 else 363 test[k].bits++; 364 365 lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, 366 CASE_LOW (cs), minval)); 367 if (CASE_HIGH (cs) == NULL_TREE) 368 hi = lo; 369 else 370 hi = tree_to_uhwi (int_const_binop (MINUS_EXPR, 371 CASE_HIGH (cs), minval)); 372 373 for (j = lo; j <= hi; j++) 374 test[k].mask |= wi::lshift (wone, j); 375 } 376 377 qsort (test, count, sizeof (*test), case_bit_test_cmp); 378 379 /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of 380 the minval subtractions, but it might make the mask constants more 381 expensive. So, compare the costs. */ 382 if (compare_tree_int (minval, 0) > 0 383 && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0) 384 { 385 int cost_diff; 386 HOST_WIDE_INT m = tree_to_uhwi (minval); 387 rtx reg = gen_raw_REG (word_mode, 10000); 388 bool speed_p = optimize_bb_for_speed_p (gimple_bb (swtch)); 389 cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg, 390 GEN_INT (-m)), speed_p); 391 for (i = 0; i < count; i++) 392 { 393 rtx r = immed_wide_int_const (test[i].mask, word_mode); 394 cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r), speed_p); 395 r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode); 396 cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r), speed_p); 397 } 398 if (cost_diff > 0) 399 { 400 for (i = 0; i < count; i++) 401 test[i].mask = wi::lshift (test[i].mask, m); 402 minval = build_zero_cst (TREE_TYPE (minval)); 403 range = maxval; 404 } 405 } 406 407 /* We generate two jumps to the default case label. 408 Split the default edge, so that we don't have to do any PHI node 409 updating. */ 410 new_default_bb = split_edge (default_edge); 411 412 if (update_dom) 413 { 414 bbs_to_fix_dom.create (10); 415 bbs_to_fix_dom.quick_push (switch_bb); 416 bbs_to_fix_dom.quick_push (default_bb); 417 bbs_to_fix_dom.quick_push (new_default_bb); 418 } 419 420 /* Now build the test-and-branch code. */ 421 422 gsi = gsi_last_bb (switch_bb); 423 424 /* idx = (unsigned)x - minval. */ 425 idx = fold_convert (unsigned_index_type, index_expr); 426 idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx, 427 fold_convert (unsigned_index_type, minval)); 428 idx = force_gimple_operand_gsi (&gsi, idx, 429 /*simple=*/true, NULL_TREE, 430 /*before=*/true, GSI_SAME_STMT); 431 432 /* if (idx > range) goto default */ 433 range = force_gimple_operand_gsi (&gsi, 434 fold_convert (unsigned_index_type, range), 435 /*simple=*/true, NULL_TREE, 436 /*before=*/true, GSI_SAME_STMT); 437 tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range); 438 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_edge, update_dom); 439 if (update_dom) 440 bbs_to_fix_dom.quick_push (new_bb); 441 gcc_assert (gimple_bb (swtch) == new_bb); 442 gsi = gsi_last_bb (new_bb); 443 444 /* Any blocks dominated by the GIMPLE_SWITCH, but that are not successors 445 of NEW_BB, are still immediately dominated by SWITCH_BB. Make it so. */ 446 if (update_dom) 447 { 448 vec<basic_block> dom_bbs; 449 basic_block dom_son; 450 451 dom_bbs = get_dominated_by (CDI_DOMINATORS, new_bb); 452 FOR_EACH_VEC_ELT (dom_bbs, i, dom_son) 453 { 454 edge e = find_edge (new_bb, dom_son); 455 if (e && single_pred_p (e->dest)) 456 continue; 457 set_immediate_dominator (CDI_DOMINATORS, dom_son, switch_bb); 458 bbs_to_fix_dom.safe_push (dom_son); 459 } 460 dom_bbs.release (); 461 } 462 463 /* csui = (1 << (word_mode) idx) */ 464 csui = make_ssa_name (word_type_node); 465 tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one, 466 fold_convert (word_type_node, idx)); 467 tmp = force_gimple_operand_gsi (&gsi, tmp, 468 /*simple=*/false, NULL_TREE, 469 /*before=*/true, GSI_SAME_STMT); 470 shift_stmt = gimple_build_assign (csui, tmp); 471 gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT); 472 update_stmt (shift_stmt); 473 474 /* for each unique set of cases: 475 if (const & csui) goto target */ 476 for (k = 0; k < count; k++) 477 { 478 tmp = wide_int_to_tree (word_type_node, test[k].mask); 479 tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp); 480 tmp = force_gimple_operand_gsi (&gsi, tmp, 481 /*simple=*/true, NULL_TREE, 482 /*before=*/true, GSI_SAME_STMT); 483 tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero); 484 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_edge, 485 update_dom); 486 if (update_dom) 487 bbs_to_fix_dom.safe_push (new_bb); 488 gcc_assert (gimple_bb (swtch) == new_bb); 489 gsi = gsi_last_bb (new_bb); 490 } 491 492 /* We should have removed all edges now. */ 493 gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0); 494 495 /* If nothing matched, go to the default label. */ 496 make_edge (gsi_bb (gsi), new_default_bb, EDGE_FALLTHRU); 497 498 /* The GIMPLE_SWITCH is now redundant. */ 499 gsi_remove (&gsi, true); 500 501 if (update_dom) 502 { 503 /* Fix up the dominator tree. */ 504 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true); 505 bbs_to_fix_dom.release (); 506 } 507} 508 509/* 510 Switch initialization conversion 511 512The following pass changes simple initializations of scalars in a switch 513statement into initializations from a static array. Obviously, the values 514must be constant and known at compile time and a default branch must be 515provided. For example, the following code: 516 517 int a,b; 518 519 switch (argc) 520 { 521 case 1: 522 case 2: 523 a_1 = 8; 524 b_1 = 6; 525 break; 526 case 3: 527 a_2 = 9; 528 b_2 = 5; 529 break; 530 case 12: 531 a_3 = 10; 532 b_3 = 4; 533 break; 534 default: 535 a_4 = 16; 536 b_4 = 1; 537 break; 538 } 539 a_5 = PHI <a_1, a_2, a_3, a_4> 540 b_5 = PHI <b_1, b_2, b_3, b_4> 541 542 543is changed into: 544 545 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4}; 546 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16, 547 16, 16, 10}; 548 549 if (((unsigned) argc) - 1 < 11) 550 { 551 a_6 = CSWTCH02[argc - 1]; 552 b_6 = CSWTCH01[argc - 1]; 553 } 554 else 555 { 556 a_7 = 16; 557 b_7 = 1; 558 } 559 a_5 = PHI <a_6, a_7> 560 b_b = PHI <b_6, b_7> 561 562There are further constraints. Specifically, the range of values across all 563case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default 564eight) times the number of the actual switch branches. 565 566This transformation was contributed by Martin Jambor, see this e-mail: 567 http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */ 568 569/* The main structure of the pass. */ 570struct switch_conv_info 571{ 572 /* The expression used to decide the switch branch. */ 573 tree index_expr; 574 575 /* The following integer constants store the minimum and maximum value 576 covered by the case labels. */ 577 tree range_min; 578 tree range_max; 579 580 /* The difference between the above two numbers. Stored here because it 581 is used in all the conversion heuristics, as well as for some of the 582 transformation, and it is expensive to re-compute it all the time. */ 583 tree range_size; 584 585 /* Basic block that contains the actual GIMPLE_SWITCH. */ 586 basic_block switch_bb; 587 588 /* Basic block that is the target of the default case. */ 589 basic_block default_bb; 590 591 /* The single successor block of all branches out of the GIMPLE_SWITCH, 592 if such a block exists. Otherwise NULL. */ 593 basic_block final_bb; 594 595 /* The probability of the default edge in the replaced switch. */ 596 int default_prob; 597 598 /* The count of the default edge in the replaced switch. */ 599 gcov_type default_count; 600 601 /* Combined count of all other (non-default) edges in the replaced switch. */ 602 gcov_type other_count; 603 604 /* Number of phi nodes in the final bb (that we'll be replacing). */ 605 int phi_count; 606 607 /* Array of default values, in the same order as phi nodes. */ 608 tree *default_values; 609 610 /* Constructors of new static arrays. */ 611 vec<constructor_elt, va_gc> **constructors; 612 613 /* Array of ssa names that are initialized with a value from a new static 614 array. */ 615 tree *target_inbound_names; 616 617 /* Array of ssa names that are initialized with the default value if the 618 switch expression is out of range. */ 619 tree *target_outbound_names; 620 621 /* The first load statement that loads a temporary from a new static array. 622 */ 623 gimple arr_ref_first; 624 625 /* The last load statement that loads a temporary from a new static array. */ 626 gimple arr_ref_last; 627 628 /* String reason why the case wasn't a good candidate that is written to the 629 dump file, if there is one. */ 630 const char *reason; 631 632 /* Parameters for expand_switch_using_bit_tests. Should be computed 633 the same way as in expand_case. */ 634 unsigned int uniq; 635 unsigned int count; 636}; 637 638/* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */ 639 640static void 641collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info) 642{ 643 unsigned int branch_num = gimple_switch_num_labels (swtch); 644 tree min_case, max_case; 645 unsigned int count, i; 646 edge e, e_default; 647 edge_iterator ei; 648 649 memset (info, 0, sizeof (*info)); 650 651 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there 652 is a default label which is the first in the vector. 653 Collect the bits we can deduce from the CFG. */ 654 info->index_expr = gimple_switch_index (swtch); 655 info->switch_bb = gimple_bb (swtch); 656 info->default_bb = 657 label_to_block (CASE_LABEL (gimple_switch_default_label (swtch))); 658 e_default = find_edge (info->switch_bb, info->default_bb); 659 info->default_prob = e_default->probability; 660 info->default_count = e_default->count; 661 FOR_EACH_EDGE (e, ei, info->switch_bb->succs) 662 if (e != e_default) 663 info->other_count += e->count; 664 665 /* See if there is one common successor block for all branch 666 targets. If it exists, record it in FINAL_BB. 667 Start with the destination of the default case as guess 668 or its destination in case it is a forwarder block. */ 669 if (! single_pred_p (e_default->dest)) 670 info->final_bb = e_default->dest; 671 else if (single_succ_p (e_default->dest) 672 && ! single_pred_p (single_succ (e_default->dest))) 673 info->final_bb = single_succ (e_default->dest); 674 /* Require that all switch destinations are either that common 675 FINAL_BB or a forwarder to it. */ 676 if (info->final_bb) 677 FOR_EACH_EDGE (e, ei, info->switch_bb->succs) 678 { 679 if (e->dest == info->final_bb) 680 continue; 681 682 if (single_pred_p (e->dest) 683 && single_succ_p (e->dest) 684 && single_succ (e->dest) == info->final_bb) 685 continue; 686 687 info->final_bb = NULL; 688 break; 689 } 690 691 /* Get upper and lower bounds of case values, and the covered range. */ 692 min_case = gimple_switch_label (swtch, 1); 693 max_case = gimple_switch_label (swtch, branch_num - 1); 694 695 info->range_min = CASE_LOW (min_case); 696 if (CASE_HIGH (max_case) != NULL_TREE) 697 info->range_max = CASE_HIGH (max_case); 698 else 699 info->range_max = CASE_LOW (max_case); 700 701 info->range_size = 702 int_const_binop (MINUS_EXPR, info->range_max, info->range_min); 703 704 /* Get a count of the number of case labels. Single-valued case labels 705 simply count as one, but a case range counts double, since it may 706 require two compares if it gets lowered as a branching tree. */ 707 count = 0; 708 for (i = 1; i < branch_num; i++) 709 { 710 tree elt = gimple_switch_label (swtch, i); 711 count++; 712 if (CASE_HIGH (elt) 713 && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt))) 714 count++; 715 } 716 info->count = count; 717 718 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH 719 block. Assume a CFG cleanup would have already removed degenerate 720 switch statements, this allows us to just use EDGE_COUNT. */ 721 info->uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1; 722} 723 724/* Checks whether the range given by individual case statements of the SWTCH 725 switch statement isn't too big and whether the number of branches actually 726 satisfies the size of the new array. */ 727 728static bool 729check_range (struct switch_conv_info *info) 730{ 731 gcc_assert (info->range_size); 732 if (!tree_fits_uhwi_p (info->range_size)) 733 { 734 info->reason = "index range way too large or otherwise unusable"; 735 return false; 736 } 737 738 if (tree_to_uhwi (info->range_size) 739 > ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO)) 740 { 741 info->reason = "the maximum range-branch ratio exceeded"; 742 return false; 743 } 744 745 return true; 746} 747 748/* Checks whether all but the FINAL_BB basic blocks are empty. */ 749 750static bool 751check_all_empty_except_final (struct switch_conv_info *info) 752{ 753 edge e; 754 edge_iterator ei; 755 756 FOR_EACH_EDGE (e, ei, info->switch_bb->succs) 757 { 758 if (e->dest == info->final_bb) 759 continue; 760 761 if (!empty_block_p (e->dest)) 762 { 763 info->reason = "bad case - a non-final BB not empty"; 764 return false; 765 } 766 } 767 768 return true; 769} 770 771/* This function checks whether all required values in phi nodes in final_bb 772 are constants. Required values are those that correspond to a basic block 773 which is a part of the examined switch statement. It returns true if the 774 phi nodes are OK, otherwise false. */ 775 776static bool 777check_final_bb (struct switch_conv_info *info) 778{ 779 gphi_iterator gsi; 780 781 info->phi_count = 0; 782 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) 783 { 784 gphi *phi = gsi.phi (); 785 unsigned int i; 786 787 info->phi_count++; 788 789 for (i = 0; i < gimple_phi_num_args (phi); i++) 790 { 791 basic_block bb = gimple_phi_arg_edge (phi, i)->src; 792 793 if (bb == info->switch_bb 794 || (single_pred_p (bb) && single_pred (bb) == info->switch_bb)) 795 { 796 tree reloc, val; 797 798 val = gimple_phi_arg_def (phi, i); 799 if (!is_gimple_ip_invariant (val)) 800 { 801 info->reason = "non-invariant value from a case"; 802 return false; /* Non-invariant argument. */ 803 } 804 reloc = initializer_constant_valid_p (val, TREE_TYPE (val)); 805 if ((flag_pic && reloc != null_pointer_node) 806 || (!flag_pic && reloc == NULL_TREE)) 807 { 808 if (reloc) 809 info->reason 810 = "value from a case would need runtime relocations"; 811 else 812 info->reason 813 = "value from a case is not a valid initializer"; 814 return false; 815 } 816 } 817 } 818 } 819 820 return true; 821} 822 823/* The following function allocates default_values, target_{in,out}_names and 824 constructors arrays. The last one is also populated with pointers to 825 vectors that will become constructors of new arrays. */ 826 827static void 828create_temp_arrays (struct switch_conv_info *info) 829{ 830 int i; 831 832 info->default_values = XCNEWVEC (tree, info->phi_count * 3); 833 /* ??? Macros do not support multi argument templates in their 834 argument list. We create a typedef to work around that problem. */ 835 typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc; 836 info->constructors = XCNEWVEC (vec_constructor_elt_gc, info->phi_count); 837 info->target_inbound_names = info->default_values + info->phi_count; 838 info->target_outbound_names = info->target_inbound_names + info->phi_count; 839 for (i = 0; i < info->phi_count; i++) 840 vec_alloc (info->constructors[i], tree_to_uhwi (info->range_size) + 1); 841} 842 843/* Free the arrays created by create_temp_arrays(). The vectors that are 844 created by that function are not freed here, however, because they have 845 already become constructors and must be preserved. */ 846 847static void 848free_temp_arrays (struct switch_conv_info *info) 849{ 850 XDELETEVEC (info->constructors); 851 XDELETEVEC (info->default_values); 852} 853 854/* Populate the array of default values in the order of phi nodes. 855 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */ 856 857static void 858gather_default_values (tree default_case, struct switch_conv_info *info) 859{ 860 gphi_iterator gsi; 861 basic_block bb = label_to_block (CASE_LABEL (default_case)); 862 edge e; 863 int i = 0; 864 865 gcc_assert (CASE_LOW (default_case) == NULL_TREE); 866 867 if (bb == info->final_bb) 868 e = find_edge (info->switch_bb, bb); 869 else 870 e = single_succ_edge (bb); 871 872 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) 873 { 874 gphi *phi = gsi.phi (); 875 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); 876 gcc_assert (val); 877 info->default_values[i++] = val; 878 } 879} 880 881/* The following function populates the vectors in the constructors array with 882 future contents of the static arrays. The vectors are populated in the 883 order of phi nodes. SWTCH is the switch statement being converted. */ 884 885static void 886build_constructors (gswitch *swtch, struct switch_conv_info *info) 887{ 888 unsigned i, branch_num = gimple_switch_num_labels (swtch); 889 tree pos = info->range_min; 890 891 for (i = 1; i < branch_num; i++) 892 { 893 tree cs = gimple_switch_label (swtch, i); 894 basic_block bb = label_to_block (CASE_LABEL (cs)); 895 edge e; 896 tree high; 897 gphi_iterator gsi; 898 int j; 899 900 if (bb == info->final_bb) 901 e = find_edge (info->switch_bb, bb); 902 else 903 e = single_succ_edge (bb); 904 gcc_assert (e); 905 906 while (tree_int_cst_lt (pos, CASE_LOW (cs))) 907 { 908 int k; 909 for (k = 0; k < info->phi_count; k++) 910 { 911 constructor_elt elt; 912 913 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min); 914 elt.value 915 = unshare_expr_without_location (info->default_values[k]); 916 info->constructors[k]->quick_push (elt); 917 } 918 919 pos = int_const_binop (PLUS_EXPR, pos, 920 build_int_cst (TREE_TYPE (pos), 1)); 921 } 922 gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs))); 923 924 j = 0; 925 if (CASE_HIGH (cs)) 926 high = CASE_HIGH (cs); 927 else 928 high = CASE_LOW (cs); 929 for (gsi = gsi_start_phis (info->final_bb); 930 !gsi_end_p (gsi); gsi_next (&gsi)) 931 { 932 gphi *phi = gsi.phi (); 933 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); 934 tree low = CASE_LOW (cs); 935 pos = CASE_LOW (cs); 936 937 do 938 { 939 constructor_elt elt; 940 941 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min); 942 elt.value = unshare_expr_without_location (val); 943 info->constructors[j]->quick_push (elt); 944 945 pos = int_const_binop (PLUS_EXPR, pos, 946 build_int_cst (TREE_TYPE (pos), 1)); 947 } while (!tree_int_cst_lt (high, pos) 948 && tree_int_cst_lt (low, pos)); 949 j++; 950 } 951 } 952} 953 954/* If all values in the constructor vector are the same, return the value. 955 Otherwise return NULL_TREE. Not supposed to be called for empty 956 vectors. */ 957 958static tree 959constructor_contains_same_values_p (vec<constructor_elt, va_gc> *vec) 960{ 961 unsigned int i; 962 tree prev = NULL_TREE; 963 constructor_elt *elt; 964 965 FOR_EACH_VEC_SAFE_ELT (vec, i, elt) 966 { 967 if (!prev) 968 prev = elt->value; 969 else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST)) 970 return NULL_TREE; 971 } 972 return prev; 973} 974 975/* Return type which should be used for array elements, either TYPE, 976 or for integral type some smaller integral type that can still hold 977 all the constants. */ 978 979static tree 980array_value_type (gswitch *swtch, tree type, int num, 981 struct switch_conv_info *info) 982{ 983 unsigned int i, len = vec_safe_length (info->constructors[num]); 984 constructor_elt *elt; 985 machine_mode mode; 986 int sign = 0; 987 tree smaller_type; 988 989 if (!INTEGRAL_TYPE_P (type)) 990 return type; 991 992 mode = GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type))); 993 if (GET_MODE_SIZE (TYPE_MODE (type)) <= GET_MODE_SIZE (mode)) 994 return type; 995 996 if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32)) 997 return type; 998 999 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt) 1000 { 1001 wide_int cst; 1002 1003 if (TREE_CODE (elt->value) != INTEGER_CST) 1004 return type; 1005 1006 cst = elt->value; 1007 while (1) 1008 { 1009 unsigned int prec = GET_MODE_BITSIZE (mode); 1010 if (prec > HOST_BITS_PER_WIDE_INT) 1011 return type; 1012 1013 if (sign >= 0 && cst == wi::zext (cst, prec)) 1014 { 1015 if (sign == 0 && cst == wi::sext (cst, prec)) 1016 break; 1017 sign = 1; 1018 break; 1019 } 1020 if (sign <= 0 && cst == wi::sext (cst, prec)) 1021 { 1022 sign = -1; 1023 break; 1024 } 1025 1026 if (sign == 1) 1027 sign = 0; 1028 1029 mode = GET_MODE_WIDER_MODE (mode); 1030 if (mode == VOIDmode 1031 || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (TYPE_MODE (type))) 1032 return type; 1033 } 1034 } 1035 1036 if (sign == 0) 1037 sign = TYPE_UNSIGNED (type) ? 1 : -1; 1038 smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0); 1039 if (GET_MODE_SIZE (TYPE_MODE (type)) 1040 <= GET_MODE_SIZE (TYPE_MODE (smaller_type))) 1041 return type; 1042 1043 return smaller_type; 1044} 1045 1046/* Create an appropriate array type and declaration and assemble a static array 1047 variable. Also create a load statement that initializes the variable in 1048 question with a value from the static array. SWTCH is the switch statement 1049 being converted, NUM is the index to arrays of constructors, default values 1050 and target SSA names for this particular array. ARR_INDEX_TYPE is the type 1051 of the index of the new array, PHI is the phi node of the final BB that 1052 corresponds to the value that will be loaded from the created array. TIDX 1053 is an ssa name of a temporary variable holding the index for loads from the 1054 new array. */ 1055 1056static void 1057build_one_array (gswitch *swtch, int num, tree arr_index_type, 1058 gphi *phi, tree tidx, struct switch_conv_info *info) 1059{ 1060 tree name, cst; 1061 gimple load; 1062 gimple_stmt_iterator gsi = gsi_for_stmt (swtch); 1063 location_t loc = gimple_location (swtch); 1064 1065 gcc_assert (info->default_values[num]); 1066 1067 name = copy_ssa_name (PHI_RESULT (phi)); 1068 info->target_inbound_names[num] = name; 1069 1070 cst = constructor_contains_same_values_p (info->constructors[num]); 1071 if (cst) 1072 load = gimple_build_assign (name, cst); 1073 else 1074 { 1075 tree array_type, ctor, decl, value_type, fetch, default_type; 1076 1077 default_type = TREE_TYPE (info->default_values[num]); 1078 value_type = array_value_type (swtch, default_type, num, info); 1079 array_type = build_array_type (value_type, arr_index_type); 1080 if (default_type != value_type) 1081 { 1082 unsigned int i; 1083 constructor_elt *elt; 1084 1085 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt) 1086 elt->value = fold_convert (value_type, elt->value); 1087 } 1088 ctor = build_constructor (array_type, info->constructors[num]); 1089 TREE_CONSTANT (ctor) = true; 1090 TREE_STATIC (ctor) = true; 1091 1092 decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type); 1093 TREE_STATIC (decl) = 1; 1094 DECL_INITIAL (decl) = ctor; 1095 1096 DECL_NAME (decl) = create_tmp_var_name ("CSWTCH"); 1097 DECL_ARTIFICIAL (decl) = 1; 1098 TREE_CONSTANT (decl) = 1; 1099 TREE_READONLY (decl) = 1; 1100 varpool_node::finalize_decl (decl); 1101 1102 fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE, 1103 NULL_TREE); 1104 if (default_type != value_type) 1105 { 1106 fetch = fold_convert (default_type, fetch); 1107 fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE, 1108 true, GSI_SAME_STMT); 1109 } 1110 load = gimple_build_assign (name, fetch); 1111 } 1112 1113 gsi_insert_before (&gsi, load, GSI_SAME_STMT); 1114 update_stmt (load); 1115 info->arr_ref_last = load; 1116} 1117 1118/* Builds and initializes static arrays initialized with values gathered from 1119 the SWTCH switch statement. Also creates statements that load values from 1120 them. */ 1121 1122static void 1123build_arrays (gswitch *swtch, struct switch_conv_info *info) 1124{ 1125 tree arr_index_type; 1126 tree tidx, sub, utype; 1127 gimple stmt; 1128 gimple_stmt_iterator gsi; 1129 gphi_iterator gpi; 1130 int i; 1131 location_t loc = gimple_location (swtch); 1132 1133 gsi = gsi_for_stmt (swtch); 1134 1135 /* Make sure we do not generate arithmetics in a subrange. */ 1136 utype = TREE_TYPE (info->index_expr); 1137 if (TREE_TYPE (utype)) 1138 utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1); 1139 else 1140 utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1); 1141 1142 arr_index_type = build_index_type (info->range_size); 1143 tidx = make_ssa_name (utype); 1144 sub = fold_build2_loc (loc, MINUS_EXPR, utype, 1145 fold_convert_loc (loc, utype, info->index_expr), 1146 fold_convert_loc (loc, utype, info->range_min)); 1147 sub = force_gimple_operand_gsi (&gsi, sub, 1148 false, NULL, true, GSI_SAME_STMT); 1149 stmt = gimple_build_assign (tidx, sub); 1150 1151 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); 1152 update_stmt (stmt); 1153 info->arr_ref_first = stmt; 1154 1155 for (gpi = gsi_start_phis (info->final_bb), i = 0; 1156 !gsi_end_p (gpi); gsi_next (&gpi), i++) 1157 build_one_array (swtch, i, arr_index_type, gpi.phi (), tidx, info); 1158} 1159 1160/* Generates and appropriately inserts loads of default values at the position 1161 given by BSI. Returns the last inserted statement. */ 1162 1163static gassign * 1164gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info) 1165{ 1166 int i; 1167 gassign *assign = NULL; 1168 1169 for (i = 0; i < info->phi_count; i++) 1170 { 1171 tree name = copy_ssa_name (info->target_inbound_names[i]); 1172 info->target_outbound_names[i] = name; 1173 assign = gimple_build_assign (name, info->default_values[i]); 1174 gsi_insert_before (gsi, assign, GSI_SAME_STMT); 1175 update_stmt (assign); 1176 } 1177 return assign; 1178} 1179 1180/* Deletes the unused bbs and edges that now contain the switch statement and 1181 its empty branch bbs. BBD is the now dead BB containing the original switch 1182 statement, FINAL is the last BB of the converted switch statement (in terms 1183 of succession). */ 1184 1185static void 1186prune_bbs (basic_block bbd, basic_block final) 1187{ 1188 edge_iterator ei; 1189 edge e; 1190 1191 for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); ) 1192 { 1193 basic_block bb; 1194 bb = e->dest; 1195 remove_edge (e); 1196 if (bb != final) 1197 delete_basic_block (bb); 1198 } 1199 delete_basic_block (bbd); 1200} 1201 1202/* Add values to phi nodes in final_bb for the two new edges. E1F is the edge 1203 from the basic block loading values from an array and E2F from the basic 1204 block loading default values. BBF is the last switch basic block (see the 1205 bbf description in the comment below). */ 1206 1207static void 1208fix_phi_nodes (edge e1f, edge e2f, basic_block bbf, 1209 struct switch_conv_info *info) 1210{ 1211 gphi_iterator gsi; 1212 int i; 1213 1214 for (gsi = gsi_start_phis (bbf), i = 0; 1215 !gsi_end_p (gsi); gsi_next (&gsi), i++) 1216 { 1217 gphi *phi = gsi.phi (); 1218 add_phi_arg (phi, info->target_inbound_names[i], e1f, UNKNOWN_LOCATION); 1219 add_phi_arg (phi, info->target_outbound_names[i], e2f, UNKNOWN_LOCATION); 1220 } 1221} 1222 1223/* Creates a check whether the switch expression value actually falls into the 1224 range given by all the cases. If it does not, the temporaries are loaded 1225 with default values instead. SWTCH is the switch statement being converted. 1226 1227 bb0 is the bb with the switch statement, however, we'll end it with a 1228 condition instead. 1229 1230 bb1 is the bb to be used when the range check went ok. It is derived from 1231 the switch BB 1232 1233 bb2 is the bb taken when the expression evaluated outside of the range 1234 covered by the created arrays. It is populated by loads of default 1235 values. 1236 1237 bbF is a fall through for both bb1 and bb2 and contains exactly what 1238 originally followed the switch statement. 1239 1240 bbD contains the switch statement (in the end). It is unreachable but we 1241 still need to strip off its edges. 1242*/ 1243 1244static void 1245gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) 1246{ 1247 tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION); 1248 tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION); 1249 tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION); 1250 glabel *label1, *label2, *label3; 1251 tree utype, tidx; 1252 tree bound; 1253 1254 gcond *cond_stmt; 1255 1256 gassign *last_assign; 1257 gimple_stmt_iterator gsi; 1258 basic_block bb0, bb1, bb2, bbf, bbd; 1259 edge e01, e02, e21, e1d, e1f, e2f; 1260 location_t loc = gimple_location (swtch); 1261 1262 gcc_assert (info->default_values); 1263 1264 bb0 = gimple_bb (swtch); 1265 1266 tidx = gimple_assign_lhs (info->arr_ref_first); 1267 utype = TREE_TYPE (tidx); 1268 1269 /* (end of) block 0 */ 1270 gsi = gsi_for_stmt (info->arr_ref_first); 1271 gsi_next (&gsi); 1272 1273 bound = fold_convert_loc (loc, utype, info->range_size); 1274 cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE); 1275 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT); 1276 update_stmt (cond_stmt); 1277 1278 /* block 2 */ 1279 label2 = gimple_build_label (label_decl2); 1280 gsi_insert_before (&gsi, label2, GSI_SAME_STMT); 1281 last_assign = gen_def_assigns (&gsi, info); 1282 1283 /* block 1 */ 1284 label1 = gimple_build_label (label_decl1); 1285 gsi_insert_before (&gsi, label1, GSI_SAME_STMT); 1286 1287 /* block F */ 1288 gsi = gsi_start_bb (info->final_bb); 1289 label3 = gimple_build_label (label_decl3); 1290 gsi_insert_before (&gsi, label3, GSI_SAME_STMT); 1291 1292 /* cfg fix */ 1293 e02 = split_block (bb0, cond_stmt); 1294 bb2 = e02->dest; 1295 1296 e21 = split_block (bb2, last_assign); 1297 bb1 = e21->dest; 1298 remove_edge (e21); 1299 1300 e1d = split_block (bb1, info->arr_ref_last); 1301 bbd = e1d->dest; 1302 remove_edge (e1d); 1303 1304 /* flags and profiles of the edge for in-range values */ 1305 e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE); 1306 e01->probability = REG_BR_PROB_BASE - info->default_prob; 1307 e01->count = info->other_count; 1308 1309 /* flags and profiles of the edge taking care of out-of-range values */ 1310 e02->flags &= ~EDGE_FALLTHRU; 1311 e02->flags |= EDGE_FALSE_VALUE; 1312 e02->probability = info->default_prob; 1313 e02->count = info->default_count; 1314 1315 bbf = info->final_bb; 1316 1317 e1f = make_edge (bb1, bbf, EDGE_FALLTHRU); 1318 e1f->probability = REG_BR_PROB_BASE; 1319 e1f->count = info->other_count; 1320 1321 e2f = make_edge (bb2, bbf, EDGE_FALLTHRU); 1322 e2f->probability = REG_BR_PROB_BASE; 1323 e2f->count = info->default_count; 1324 1325 /* frequencies of the new BBs */ 1326 bb1->frequency = EDGE_FREQUENCY (e01); 1327 bb2->frequency = EDGE_FREQUENCY (e02); 1328 bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f); 1329 1330 /* Tidy blocks that have become unreachable. */ 1331 prune_bbs (bbd, info->final_bb); 1332 1333 /* Fixup the PHI nodes in bbF. */ 1334 fix_phi_nodes (e1f, e2f, bbf, info); 1335 1336 /* Fix the dominator tree, if it is available. */ 1337 if (dom_info_available_p (CDI_DOMINATORS)) 1338 { 1339 vec<basic_block> bbs_to_fix_dom; 1340 1341 set_immediate_dominator (CDI_DOMINATORS, bb1, bb0); 1342 set_immediate_dominator (CDI_DOMINATORS, bb2, bb0); 1343 if (! get_immediate_dominator (CDI_DOMINATORS, bbf)) 1344 /* If bbD was the immediate dominator ... */ 1345 set_immediate_dominator (CDI_DOMINATORS, bbf, bb0); 1346 1347 bbs_to_fix_dom.create (4); 1348 bbs_to_fix_dom.quick_push (bb0); 1349 bbs_to_fix_dom.quick_push (bb1); 1350 bbs_to_fix_dom.quick_push (bb2); 1351 bbs_to_fix_dom.quick_push (bbf); 1352 1353 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true); 1354 bbs_to_fix_dom.release (); 1355 } 1356} 1357 1358/* The following function is invoked on every switch statement (the current one 1359 is given in SWTCH) and runs the individual phases of switch conversion on it 1360 one after another until one fails or the conversion is completed. 1361 Returns NULL on success, or a pointer to a string with the reason why the 1362 conversion failed. */ 1363 1364static const char * 1365process_switch (gswitch *swtch) 1366{ 1367 struct switch_conv_info info; 1368 1369 /* Group case labels so that we get the right results from the heuristics 1370 that decide on the code generation approach for this switch. */ 1371 group_case_labels_stmt (swtch); 1372 1373 /* If this switch is now a degenerate case with only a default label, 1374 there is nothing left for us to do. */ 1375 if (gimple_switch_num_labels (swtch) < 2) 1376 return "switch is a degenerate case"; 1377 1378 collect_switch_conv_info (swtch, &info); 1379 1380 /* No error markers should reach here (they should be filtered out 1381 during gimplification). */ 1382 gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node); 1383 1384 /* A switch on a constant should have been optimized in tree-cfg-cleanup. */ 1385 gcc_checking_assert (! TREE_CONSTANT (info.index_expr)); 1386 1387 if (info.uniq <= MAX_CASE_BIT_TESTS) 1388 { 1389 if (expand_switch_using_bit_tests_p (info.range_size, 1390 info.uniq, info.count, 1391 optimize_bb_for_speed_p 1392 (gimple_bb (swtch)))) 1393 { 1394 if (dump_file) 1395 fputs (" expanding as bit test is preferable\n", dump_file); 1396 emit_case_bit_tests (swtch, info.index_expr, info.range_min, 1397 info.range_size, info.range_max); 1398 loops_state_set (LOOPS_NEED_FIXUP); 1399 return NULL; 1400 } 1401 1402 if (info.uniq <= 2) 1403 /* This will be expanded as a decision tree in stmt.c:expand_case. */ 1404 return " expanding as jumps is preferable"; 1405 } 1406 1407 /* If there is no common successor, we cannot do the transformation. */ 1408 if (! info.final_bb) 1409 return "no common successor to all case label target blocks found"; 1410 1411 /* Check the case label values are within reasonable range: */ 1412 if (!check_range (&info)) 1413 { 1414 gcc_assert (info.reason); 1415 return info.reason; 1416 } 1417 1418 /* For all the cases, see whether they are empty, the assignments they 1419 represent constant and so on... */ 1420 if (! check_all_empty_except_final (&info)) 1421 { 1422 gcc_assert (info.reason); 1423 return info.reason; 1424 } 1425 if (!check_final_bb (&info)) 1426 { 1427 gcc_assert (info.reason); 1428 return info.reason; 1429 } 1430 1431 /* At this point all checks have passed and we can proceed with the 1432 transformation. */ 1433 1434 create_temp_arrays (&info); 1435 gather_default_values (gimple_switch_default_label (swtch), &info); 1436 build_constructors (swtch, &info); 1437 1438 build_arrays (swtch, &info); /* Build the static arrays and assignments. */ 1439 gen_inbound_check (swtch, &info); /* Build the bounds check. */ 1440 1441 /* Cleanup: */ 1442 free_temp_arrays (&info); 1443 return NULL; 1444} 1445 1446/* The main function of the pass scans statements for switches and invokes 1447 process_switch on them. */ 1448 1449namespace { 1450 1451const pass_data pass_data_convert_switch = 1452{ 1453 GIMPLE_PASS, /* type */ 1454 "switchconv", /* name */ 1455 OPTGROUP_NONE, /* optinfo_flags */ 1456 TV_TREE_SWITCH_CONVERSION, /* tv_id */ 1457 ( PROP_cfg | PROP_ssa ), /* properties_required */ 1458 0, /* properties_provided */ 1459 0, /* properties_destroyed */ 1460 0, /* todo_flags_start */ 1461 TODO_update_ssa, /* todo_flags_finish */ 1462}; 1463 1464class pass_convert_switch : public gimple_opt_pass 1465{ 1466public: 1467 pass_convert_switch (gcc::context *ctxt) 1468 : gimple_opt_pass (pass_data_convert_switch, ctxt) 1469 {} 1470 1471 /* opt_pass methods: */ 1472 virtual bool gate (function *) { return flag_tree_switch_conversion != 0; } 1473 virtual unsigned int execute (function *); 1474 1475}; // class pass_convert_switch 1476 1477unsigned int 1478pass_convert_switch::execute (function *fun) 1479{ 1480 basic_block bb; 1481 1482 FOR_EACH_BB_FN (bb, fun) 1483 { 1484 const char *failure_reason; 1485 gimple stmt = last_stmt (bb); 1486 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) 1487 { 1488 if (dump_file) 1489 { 1490 expanded_location loc = expand_location (gimple_location (stmt)); 1491 1492 fprintf (dump_file, "beginning to process the following " 1493 "SWITCH statement (%s:%d) : ------- \n", 1494 loc.file, loc.line); 1495 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1496 putc ('\n', dump_file); 1497 } 1498 1499 failure_reason = process_switch (as_a <gswitch *> (stmt)); 1500 if (! failure_reason) 1501 { 1502 if (dump_file) 1503 { 1504 fputs ("Switch converted\n", dump_file); 1505 fputs ("--------------------------------\n", dump_file); 1506 } 1507 1508 /* Make no effort to update the post-dominator tree. It is actually not 1509 that hard for the transformations we have performed, but it is not 1510 supported by iterate_fix_dominators. */ 1511 free_dominance_info (CDI_POST_DOMINATORS); 1512 } 1513 else 1514 { 1515 if (dump_file) 1516 { 1517 fputs ("Bailing out - ", dump_file); 1518 fputs (failure_reason, dump_file); 1519 fputs ("\n--------------------------------\n", dump_file); 1520 } 1521 } 1522 } 1523 } 1524 1525 return 0; 1526} 1527 1528} // anon namespace 1529 1530gimple_opt_pass * 1531make_pass_convert_switch (gcc::context *ctxt) 1532{ 1533 return new pass_convert_switch (ctxt); 1534} 1535