1 /* Lower GIMPLE_SWITCH expressions to something more efficient than 2 a jump table. 3 Copyright (C) 2006-2018 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it 8 under the terms of the GNU General Public License as published by the 9 Free Software Foundation; either version 3, or (at your option) any 10 later version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not, write to the Free 19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20 02110-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 "backend.h" 29 #include "insn-codes.h" 30 #include "rtl.h" 31 #include "tree.h" 32 #include "gimple.h" 33 #include "cfghooks.h" 34 #include "tree-pass.h" 35 #include "ssa.h" 36 #include "optabs-tree.h" 37 #include "cgraph.h" 38 #include "gimple-pretty-print.h" 39 #include "params.h" 40 #include "fold-const.h" 41 #include "varasm.h" 42 #include "stor-layout.h" 43 #include "cfganal.h" 44 #include "gimplify.h" 45 #include "gimple-iterator.h" 46 #include "gimplify-me.h" 47 #include "tree-cfg.h" 48 #include "cfgloop.h" 49 #include "alloc-pool.h" 50 #include "target.h" 51 #include "tree-into-ssa.h" 52 #include "omp-general.h" 53 54 /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode 55 type in the GIMPLE type system that is language-independent? */ 56 #include "langhooks.h" 57 58 59 /* Maximum number of case bit tests. 60 FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and 61 targetm.case_values_threshold(), or be its own param. */ 62 #define MAX_CASE_BIT_TESTS 3 63 64 /* Track whether or not we have altered the CFG and thus may need to 65 cleanup the CFG when complete. */ 66 bool cfg_altered; 67 68 /* Split the basic block at the statement pointed to by GSIP, and insert 69 a branch to the target basic block of E_TRUE conditional on tree 70 expression COND. 71 72 It is assumed that there is already an edge from the to-be-split 73 basic block to E_TRUE->dest block. This edge is removed, and the 74 profile information on the edge is re-used for the new conditional 75 jump. 76 77 The CFG is updated. The dominator tree will not be valid after 78 this transformation, but the immediate dominators are updated if 79 UPDATE_DOMINATORS is true. 80 81 Returns the newly created basic block. */ 82 83 static basic_block 84 hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, 85 tree cond, edge e_true, 86 bool update_dominators) 87 { 88 tree tmp; 89 gcond *cond_stmt; 90 edge e_false; 91 basic_block new_bb, split_bb = gsi_bb (*gsip); 92 bool dominated_e_true = false; 93 94 gcc_assert (e_true->src == split_bb); 95 96 if (update_dominators 97 && get_immediate_dominator (CDI_DOMINATORS, e_true->dest) == split_bb) 98 dominated_e_true = true; 99 100 tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL, 101 /*before=*/true, GSI_SAME_STMT); 102 cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE); 103 gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT); 104 105 e_false = split_block (split_bb, cond_stmt); 106 new_bb = e_false->dest; 107 redirect_edge_pred (e_true, split_bb); 108 109 e_true->flags &= ~EDGE_FALLTHRU; 110 e_true->flags |= EDGE_TRUE_VALUE; 111 112 e_false->flags &= ~EDGE_FALLTHRU; 113 e_false->flags |= EDGE_FALSE_VALUE; 114 e_false->probability = e_true->probability.invert (); 115 new_bb->count = e_false->count (); 116 117 if (update_dominators) 118 { 119 if (dominated_e_true) 120 set_immediate_dominator (CDI_DOMINATORS, e_true->dest, split_bb); 121 set_immediate_dominator (CDI_DOMINATORS, e_false->dest, split_bb); 122 } 123 124 return new_bb; 125 } 126 127 128 /* Return true if a switch should be expanded as a bit test. 129 RANGE is the difference between highest and lowest case. 130 UNIQ is number of unique case node targets, not counting the default case. 131 COUNT is the number of comparisons needed, not counting the default case. */ 132 133 static bool 134 expand_switch_using_bit_tests_p (tree range, 135 unsigned int uniq, 136 unsigned int count, bool speed_p) 137 { 138 return (((uniq == 1 && count >= 3) 139 || (uniq == 2 && count >= 5) 140 || (uniq == 3 && count >= 6)) 141 && lshift_cheap_p (speed_p) 142 && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0 143 && compare_tree_int (range, 0) > 0); 144 } 145 146 /* Implement switch statements with bit tests 147 148 A GIMPLE switch statement can be expanded to a short sequence of bit-wise 149 comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)" 150 where CST and MINVAL are integer constants. This is better than a series 151 of compare-and-banch insns in some cases, e.g. we can implement: 152 153 if ((x==4) || (x==6) || (x==9) || (x==11)) 154 155 as a single bit test: 156 157 if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11))) 158 159 This transformation is only applied if the number of case targets is small, 160 if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are 161 performed in "word_mode". 162 163 The following example shows the code the transformation generates: 164 165 int bar(int x) 166 { 167 switch (x) 168 { 169 case '0': case '1': case '2': case '3': case '4': 170 case '5': case '6': case '7': case '8': case '9': 171 case 'A': case 'B': case 'C': case 'D': case 'E': 172 case 'F': 173 return 1; 174 } 175 return 0; 176 } 177 178 ==> 179 180 bar (int x) 181 { 182 tmp1 = x - 48; 183 if (tmp1 > (70 - 48)) goto L2; 184 tmp2 = 1 << tmp1; 185 tmp3 = 0b11111100000001111111111; 186 if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2; 187 L1: 188 return 1; 189 L2: 190 return 0; 191 } 192 193 TODO: There are still some improvements to this transformation that could 194 be implemented: 195 196 * A narrower mode than word_mode could be used if that is cheaper, e.g. 197 for x86_64 where a narrower-mode shift may result in smaller code. 198 199 * The compounded constant could be shifted rather than the one. The 200 test would be either on the sign bit or on the least significant bit, 201 depending on the direction of the shift. On some machines, the test 202 for the branch would be free if the bit to test is already set by the 203 shift operation. 204 205 This transformation was contributed by Roger Sayle, see this e-mail: 206 http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html 207 */ 208 209 /* A case_bit_test represents a set of case nodes that may be 210 selected from using a bit-wise comparison. HI and LO hold 211 the integer to be tested against, TARGET_EDGE contains the 212 edge to the basic block to jump to upon success and BITS 213 counts the number of case nodes handled by this test, 214 typically the number of bits set in HI:LO. The LABEL field 215 is used to quickly identify all cases in this set without 216 looking at label_to_block for every case label. */ 217 218 struct case_bit_test 219 { 220 wide_int mask; 221 edge target_edge; 222 tree label; 223 int bits; 224 }; 225 226 /* Comparison function for qsort to order bit tests by decreasing 227 probability of execution. Our best guess comes from a measured 228 profile. If the profile counts are equal, break even on the 229 number of case nodes, i.e. the node with the most cases gets 230 tested first. 231 232 TODO: Actually this currently runs before a profile is available. 233 Therefore the case-as-bit-tests transformation should be done 234 later in the pass pipeline, or something along the lines of 235 "Efficient and effective branch reordering using profile data" 236 (Yang et. al., 2002) should be implemented (although, how good 237 is a paper is called "Efficient and effective ..." when the 238 latter is implied by the former, but oh well...). */ 239 240 static int 241 case_bit_test_cmp (const void *p1, const void *p2) 242 { 243 const struct case_bit_test *const d1 = (const struct case_bit_test *) p1; 244 const struct case_bit_test *const d2 = (const struct case_bit_test *) p2; 245 246 if (d2->target_edge->count () < d1->target_edge->count ()) 247 return -1; 248 if (d2->target_edge->count () > d1->target_edge->count ()) 249 return 1; 250 if (d2->bits != d1->bits) 251 return d2->bits - d1->bits; 252 253 /* Stabilize the sort. */ 254 return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (d1->label); 255 } 256 257 /* Expand a switch statement by a short sequence of bit-wise 258 comparisons. "switch(x)" is effectively converted into 259 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are 260 integer constants. 261 262 INDEX_EXPR is the value being switched on. 263 264 MINVAL is the lowest case value of in the case nodes, 265 and RANGE is highest value minus MINVAL. MINVAL and RANGE 266 are not guaranteed to be of the same type as INDEX_EXPR 267 (the gimplifier doesn't change the type of case label values, 268 and MINVAL and RANGE are derived from those values). 269 MAXVAL is MINVAL + RANGE. 270 271 There *MUST* be MAX_CASE_BIT_TESTS or less unique case 272 node targets. */ 273 274 static void 275 emit_case_bit_tests (gswitch *swtch, tree index_expr, 276 tree minval, tree range, tree maxval) 277 { 278 struct case_bit_test test[MAX_CASE_BIT_TESTS] = { {} }; 279 unsigned int i, j, k; 280 unsigned int count; 281 282 basic_block switch_bb = gimple_bb (swtch); 283 basic_block default_bb, new_default_bb, new_bb; 284 edge default_edge; 285 bool update_dom = dom_info_available_p (CDI_DOMINATORS); 286 287 vec<basic_block> bbs_to_fix_dom = vNULL; 288 289 tree index_type = TREE_TYPE (index_expr); 290 tree unsigned_index_type = unsigned_type_for (index_type); 291 unsigned int branch_num = gimple_switch_num_labels (swtch); 292 293 gimple_stmt_iterator gsi; 294 gassign *shift_stmt; 295 296 tree idx, tmp, csui; 297 tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1); 298 tree word_mode_zero = fold_convert (word_type_node, integer_zero_node); 299 tree word_mode_one = fold_convert (word_type_node, integer_one_node); 300 int prec = TYPE_PRECISION (word_type_node); 301 wide_int wone = wi::one (prec); 302 303 /* Get the edge for the default case. */ 304 tmp = gimple_switch_default_label (swtch); 305 default_bb = label_to_block (CASE_LABEL (tmp)); 306 default_edge = find_edge (switch_bb, default_bb); 307 308 /* Go through all case labels, and collect the case labels, profile 309 counts, and other information we need to build the branch tests. */ 310 count = 0; 311 for (i = 1; i < branch_num; i++) 312 { 313 unsigned int lo, hi; 314 tree cs = gimple_switch_label (swtch, i); 315 tree label = CASE_LABEL (cs); 316 edge e = find_edge (switch_bb, label_to_block (label)); 317 for (k = 0; k < count; k++) 318 if (e == test[k].target_edge) 319 break; 320 321 if (k == count) 322 { 323 gcc_checking_assert (count < MAX_CASE_BIT_TESTS); 324 test[k].mask = wi::zero (prec); 325 test[k].target_edge = e; 326 test[k].label = label; 327 test[k].bits = 1; 328 count++; 329 } 330 else 331 test[k].bits++; 332 333 lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, 334 CASE_LOW (cs), minval)); 335 if (CASE_HIGH (cs) == NULL_TREE) 336 hi = lo; 337 else 338 hi = tree_to_uhwi (int_const_binop (MINUS_EXPR, 339 CASE_HIGH (cs), minval)); 340 341 for (j = lo; j <= hi; j++) 342 test[k].mask |= wi::lshift (wone, j); 343 } 344 345 qsort (test, count, sizeof (*test), case_bit_test_cmp); 346 347 /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of 348 the minval subtractions, but it might make the mask constants more 349 expensive. So, compare the costs. */ 350 if (compare_tree_int (minval, 0) > 0 351 && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0) 352 { 353 int cost_diff; 354 HOST_WIDE_INT m = tree_to_uhwi (minval); 355 rtx reg = gen_raw_REG (word_mode, 10000); 356 bool speed_p = optimize_bb_for_speed_p (gimple_bb (swtch)); 357 cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg, 358 GEN_INT (-m)), speed_p); 359 for (i = 0; i < count; i++) 360 { 361 rtx r = immed_wide_int_const (test[i].mask, word_mode); 362 cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r), 363 word_mode, speed_p); 364 r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode); 365 cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r), 366 word_mode, speed_p); 367 } 368 if (cost_diff > 0) 369 { 370 for (i = 0; i < count; i++) 371 test[i].mask = wi::lshift (test[i].mask, m); 372 minval = build_zero_cst (TREE_TYPE (minval)); 373 range = maxval; 374 } 375 } 376 377 /* We generate two jumps to the default case label. 378 Split the default edge, so that we don't have to do any PHI node 379 updating. */ 380 new_default_bb = split_edge (default_edge); 381 382 if (update_dom) 383 { 384 bbs_to_fix_dom.create (10); 385 bbs_to_fix_dom.quick_push (switch_bb); 386 bbs_to_fix_dom.quick_push (default_bb); 387 bbs_to_fix_dom.quick_push (new_default_bb); 388 } 389 390 /* Now build the test-and-branch code. */ 391 392 gsi = gsi_last_bb (switch_bb); 393 394 /* idx = (unsigned)x - minval. */ 395 idx = fold_convert (unsigned_index_type, index_expr); 396 idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx, 397 fold_convert (unsigned_index_type, minval)); 398 idx = force_gimple_operand_gsi (&gsi, idx, 399 /*simple=*/true, NULL_TREE, 400 /*before=*/true, GSI_SAME_STMT); 401 402 /* if (idx > range) goto default */ 403 range = force_gimple_operand_gsi (&gsi, 404 fold_convert (unsigned_index_type, range), 405 /*simple=*/true, NULL_TREE, 406 /*before=*/true, GSI_SAME_STMT); 407 tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range); 408 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_edge, update_dom); 409 if (update_dom) 410 bbs_to_fix_dom.quick_push (new_bb); 411 gcc_assert (gimple_bb (swtch) == new_bb); 412 gsi = gsi_last_bb (new_bb); 413 414 /* Any blocks dominated by the GIMPLE_SWITCH, but that are not successors 415 of NEW_BB, are still immediately dominated by SWITCH_BB. Make it so. */ 416 if (update_dom) 417 { 418 vec<basic_block> dom_bbs; 419 basic_block dom_son; 420 421 dom_bbs = get_dominated_by (CDI_DOMINATORS, new_bb); 422 FOR_EACH_VEC_ELT (dom_bbs, i, dom_son) 423 { 424 edge e = find_edge (new_bb, dom_son); 425 if (e && single_pred_p (e->dest)) 426 continue; 427 set_immediate_dominator (CDI_DOMINATORS, dom_son, switch_bb); 428 bbs_to_fix_dom.safe_push (dom_son); 429 } 430 dom_bbs.release (); 431 } 432 433 /* csui = (1 << (word_mode) idx) */ 434 csui = make_ssa_name (word_type_node); 435 tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one, 436 fold_convert (word_type_node, idx)); 437 tmp = force_gimple_operand_gsi (&gsi, tmp, 438 /*simple=*/false, NULL_TREE, 439 /*before=*/true, GSI_SAME_STMT); 440 shift_stmt = gimple_build_assign (csui, tmp); 441 gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT); 442 update_stmt (shift_stmt); 443 444 /* for each unique set of cases: 445 if (const & csui) goto target */ 446 for (k = 0; k < count; k++) 447 { 448 tmp = wide_int_to_tree (word_type_node, test[k].mask); 449 tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp); 450 tmp = force_gimple_operand_gsi (&gsi, tmp, 451 /*simple=*/true, NULL_TREE, 452 /*before=*/true, GSI_SAME_STMT); 453 tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero); 454 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_edge, 455 update_dom); 456 if (update_dom) 457 bbs_to_fix_dom.safe_push (new_bb); 458 gcc_assert (gimple_bb (swtch) == new_bb); 459 gsi = gsi_last_bb (new_bb); 460 } 461 462 /* We should have removed all edges now. */ 463 gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0); 464 465 /* If nothing matched, go to the default label. */ 466 make_edge (gsi_bb (gsi), new_default_bb, EDGE_FALLTHRU); 467 468 /* The GIMPLE_SWITCH is now redundant. */ 469 gsi_remove (&gsi, true); 470 471 if (update_dom) 472 { 473 /* Fix up the dominator tree. */ 474 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true); 475 bbs_to_fix_dom.release (); 476 } 477 } 478 479 /* 480 Switch initialization conversion 481 482 The following pass changes simple initializations of scalars in a switch 483 statement into initializations from a static array. Obviously, the values 484 must be constant and known at compile time and a default branch must be 485 provided. For example, the following code: 486 487 int a,b; 488 489 switch (argc) 490 { 491 case 1: 492 case 2: 493 a_1 = 8; 494 b_1 = 6; 495 break; 496 case 3: 497 a_2 = 9; 498 b_2 = 5; 499 break; 500 case 12: 501 a_3 = 10; 502 b_3 = 4; 503 break; 504 default: 505 a_4 = 16; 506 b_4 = 1; 507 break; 508 } 509 a_5 = PHI <a_1, a_2, a_3, a_4> 510 b_5 = PHI <b_1, b_2, b_3, b_4> 511 512 513 is changed into: 514 515 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4}; 516 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16, 517 16, 16, 10}; 518 519 if (((unsigned) argc) - 1 < 11) 520 { 521 a_6 = CSWTCH02[argc - 1]; 522 b_6 = CSWTCH01[argc - 1]; 523 } 524 else 525 { 526 a_7 = 16; 527 b_7 = 1; 528 } 529 a_5 = PHI <a_6, a_7> 530 b_b = PHI <b_6, b_7> 531 532 There are further constraints. Specifically, the range of values across all 533 case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default 534 eight) times the number of the actual switch branches. 535 536 This transformation was contributed by Martin Jambor, see this e-mail: 537 http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */ 538 539 /* The main structure of the pass. */ 540 struct switch_conv_info 541 { 542 /* The expression used to decide the switch branch. */ 543 tree index_expr; 544 545 /* The following integer constants store the minimum and maximum value 546 covered by the case labels. */ 547 tree range_min; 548 tree range_max; 549 550 /* The difference between the above two numbers. Stored here because it 551 is used in all the conversion heuristics, as well as for some of the 552 transformation, and it is expensive to re-compute it all the time. */ 553 tree range_size; 554 555 /* Basic block that contains the actual GIMPLE_SWITCH. */ 556 basic_block switch_bb; 557 558 /* Basic block that is the target of the default case. */ 559 basic_block default_bb; 560 561 /* The single successor block of all branches out of the GIMPLE_SWITCH, 562 if such a block exists. Otherwise NULL. */ 563 basic_block final_bb; 564 565 /* The probability of the default edge in the replaced switch. */ 566 profile_probability default_prob; 567 568 /* The count of the default edge in the replaced switch. */ 569 profile_count default_count; 570 571 /* Combined count of all other (non-default) edges in the replaced switch. */ 572 profile_count other_count; 573 574 /* Number of phi nodes in the final bb (that we'll be replacing). */ 575 int phi_count; 576 577 /* Array of default values, in the same order as phi nodes. */ 578 tree *default_values; 579 580 /* Constructors of new static arrays. */ 581 vec<constructor_elt, va_gc> **constructors; 582 583 /* Array of ssa names that are initialized with a value from a new static 584 array. */ 585 tree *target_inbound_names; 586 587 /* Array of ssa names that are initialized with the default value if the 588 switch expression is out of range. */ 589 tree *target_outbound_names; 590 591 /* VOP SSA_NAME. */ 592 tree target_vop; 593 594 /* The first load statement that loads a temporary from a new static array. 595 */ 596 gimple *arr_ref_first; 597 598 /* The last load statement that loads a temporary from a new static array. */ 599 gimple *arr_ref_last; 600 601 /* String reason why the case wasn't a good candidate that is written to the 602 dump file, if there is one. */ 603 const char *reason; 604 605 /* True if default case is not used for any value between range_min and 606 range_max inclusive. */ 607 bool contiguous_range; 608 609 /* True if default case does not have the required shape for other case 610 labels. */ 611 bool default_case_nonstandard; 612 613 /* Parameters for expand_switch_using_bit_tests. Should be computed 614 the same way as in expand_case. */ 615 unsigned int uniq; 616 unsigned int count; 617 }; 618 619 /* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */ 620 621 static void 622 collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info) 623 { 624 unsigned int branch_num = gimple_switch_num_labels (swtch); 625 tree min_case, max_case; 626 unsigned int count, i; 627 edge e, e_default, e_first; 628 edge_iterator ei; 629 basic_block first; 630 631 memset (info, 0, sizeof (*info)); 632 633 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there 634 is a default label which is the first in the vector. 635 Collect the bits we can deduce from the CFG. */ 636 info->index_expr = gimple_switch_index (swtch); 637 info->switch_bb = gimple_bb (swtch); 638 info->default_bb 639 = label_to_block (CASE_LABEL (gimple_switch_default_label (swtch))); 640 e_default = find_edge (info->switch_bb, info->default_bb); 641 info->default_prob = e_default->probability; 642 info->default_count = e_default->count (); 643 FOR_EACH_EDGE (e, ei, info->switch_bb->succs) 644 if (e != e_default) 645 info->other_count += e->count (); 646 647 /* Get upper and lower bounds of case values, and the covered range. */ 648 min_case = gimple_switch_label (swtch, 1); 649 max_case = gimple_switch_label (swtch, branch_num - 1); 650 651 info->range_min = CASE_LOW (min_case); 652 if (CASE_HIGH (max_case) != NULL_TREE) 653 info->range_max = CASE_HIGH (max_case); 654 else 655 info->range_max = CASE_LOW (max_case); 656 657 info->contiguous_range = true; 658 tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : info->range_min; 659 for (i = 2; i < branch_num; i++) 660 { 661 tree elt = gimple_switch_label (swtch, i); 662 if (wi::to_wide (last) + 1 != wi::to_wide (CASE_LOW (elt))) 663 { 664 info->contiguous_range = false; 665 break; 666 } 667 last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt); 668 } 669 670 if (info->contiguous_range) 671 { 672 first = label_to_block (CASE_LABEL (gimple_switch_label (swtch, 1))); 673 e_first = find_edge (info->switch_bb, first); 674 } 675 else 676 { 677 first = info->default_bb; 678 e_first = e_default; 679 } 680 681 /* See if there is one common successor block for all branch 682 targets. If it exists, record it in FINAL_BB. 683 Start with the destination of the first non-default case 684 if the range is contiguous and default case otherwise as 685 guess or its destination in case it is a forwarder block. */ 686 if (! single_pred_p (e_first->dest)) 687 info->final_bb = e_first->dest; 688 else if (single_succ_p (e_first->dest) 689 && ! single_pred_p (single_succ (e_first->dest))) 690 info->final_bb = single_succ (e_first->dest); 691 /* Require that all switch destinations are either that common 692 FINAL_BB or a forwarder to it, except for the default 693 case if contiguous range. */ 694 if (info->final_bb) 695 FOR_EACH_EDGE (e, ei, info->switch_bb->succs) 696 { 697 if (e->dest == info->final_bb) 698 continue; 699 700 if (single_pred_p (e->dest) 701 && single_succ_p (e->dest) 702 && single_succ (e->dest) == info->final_bb) 703 continue; 704 705 if (e == e_default && info->contiguous_range) 706 { 707 info->default_case_nonstandard = true; 708 continue; 709 } 710 711 info->final_bb = NULL; 712 break; 713 } 714 715 info->range_size 716 = int_const_binop (MINUS_EXPR, info->range_max, info->range_min); 717 718 /* Get a count of the number of case labels. Single-valued case labels 719 simply count as one, but a case range counts double, since it may 720 require two compares if it gets lowered as a branching tree. */ 721 count = 0; 722 for (i = 1; i < branch_num; i++) 723 { 724 tree elt = gimple_switch_label (swtch, i); 725 count++; 726 if (CASE_HIGH (elt) 727 && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt))) 728 count++; 729 } 730 info->count = count; 731 732 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH 733 block. Assume a CFG cleanup would have already removed degenerate 734 switch statements, this allows us to just use EDGE_COUNT. */ 735 info->uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1; 736 } 737 738 /* Checks whether the range given by individual case statements of the SWTCH 739 switch statement isn't too big and whether the number of branches actually 740 satisfies the size of the new array. */ 741 742 static bool 743 check_range (struct switch_conv_info *info) 744 { 745 gcc_assert (info->range_size); 746 if (!tree_fits_uhwi_p (info->range_size)) 747 { 748 info->reason = "index range way too large or otherwise unusable"; 749 return false; 750 } 751 752 if (tree_to_uhwi (info->range_size) 753 > ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO)) 754 { 755 info->reason = "the maximum range-branch ratio exceeded"; 756 return false; 757 } 758 759 return true; 760 } 761 762 /* Checks whether all but the FINAL_BB basic blocks are empty. */ 763 764 static bool 765 check_all_empty_except_final (struct switch_conv_info *info) 766 { 767 edge e, e_default = find_edge (info->switch_bb, info->default_bb); 768 edge_iterator ei; 769 770 FOR_EACH_EDGE (e, ei, info->switch_bb->succs) 771 { 772 if (e->dest == info->final_bb) 773 continue; 774 775 if (!empty_block_p (e->dest)) 776 { 777 if (info->contiguous_range && e == e_default) 778 { 779 info->default_case_nonstandard = true; 780 continue; 781 } 782 783 info->reason = "bad case - a non-final BB not empty"; 784 return false; 785 } 786 } 787 788 return true; 789 } 790 791 /* This function checks whether all required values in phi nodes in final_bb 792 are constants. Required values are those that correspond to a basic block 793 which is a part of the examined switch statement. It returns true if the 794 phi nodes are OK, otherwise false. */ 795 796 static bool 797 check_final_bb (gswitch *swtch, struct switch_conv_info *info) 798 { 799 gphi_iterator gsi; 800 801 info->phi_count = 0; 802 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) 803 { 804 gphi *phi = gsi.phi (); 805 unsigned int i; 806 807 if (virtual_operand_p (gimple_phi_result (phi))) 808 continue; 809 810 info->phi_count++; 811 812 for (i = 0; i < gimple_phi_num_args (phi); i++) 813 { 814 basic_block bb = gimple_phi_arg_edge (phi, i)->src; 815 816 if (bb == info->switch_bb 817 || (single_pred_p (bb) 818 && single_pred (bb) == info->switch_bb 819 && (!info->default_case_nonstandard 820 || empty_block_p (bb)))) 821 { 822 tree reloc, val; 823 const char *reason = NULL; 824 825 val = gimple_phi_arg_def (phi, i); 826 if (!is_gimple_ip_invariant (val)) 827 reason = "non-invariant value from a case"; 828 else 829 { 830 reloc = initializer_constant_valid_p (val, TREE_TYPE (val)); 831 if ((flag_pic && reloc != null_pointer_node) 832 || (!flag_pic && reloc == NULL_TREE)) 833 { 834 if (reloc) 835 reason 836 = "value from a case would need runtime relocations"; 837 else 838 reason 839 = "value from a case is not a valid initializer"; 840 } 841 } 842 if (reason) 843 { 844 /* For contiguous range, we can allow non-constant 845 or one that needs relocation, as long as it is 846 only reachable from the default case. */ 847 if (bb == info->switch_bb) 848 bb = info->final_bb; 849 if (!info->contiguous_range || bb != info->default_bb) 850 { 851 info->reason = reason; 852 return false; 853 } 854 855 unsigned int branch_num = gimple_switch_num_labels (swtch); 856 for (unsigned int i = 1; i < branch_num; i++) 857 { 858 tree lab = CASE_LABEL (gimple_switch_label (swtch, i)); 859 if (label_to_block (lab) == bb) 860 { 861 info->reason = reason; 862 return false; 863 } 864 } 865 info->default_case_nonstandard = true; 866 } 867 } 868 } 869 } 870 871 return true; 872 } 873 874 /* The following function allocates default_values, target_{in,out}_names and 875 constructors arrays. The last one is also populated with pointers to 876 vectors that will become constructors of new arrays. */ 877 878 static void 879 create_temp_arrays (struct switch_conv_info *info) 880 { 881 int i; 882 883 info->default_values = XCNEWVEC (tree, info->phi_count * 3); 884 /* ??? Macros do not support multi argument templates in their 885 argument list. We create a typedef to work around that problem. */ 886 typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc; 887 info->constructors = XCNEWVEC (vec_constructor_elt_gc, info->phi_count); 888 info->target_inbound_names = info->default_values + info->phi_count; 889 info->target_outbound_names = info->target_inbound_names + info->phi_count; 890 for (i = 0; i < info->phi_count; i++) 891 vec_alloc (info->constructors[i], tree_to_uhwi (info->range_size) + 1); 892 } 893 894 /* Free the arrays created by create_temp_arrays(). The vectors that are 895 created by that function are not freed here, however, because they have 896 already become constructors and must be preserved. */ 897 898 static void 899 free_temp_arrays (struct switch_conv_info *info) 900 { 901 XDELETEVEC (info->constructors); 902 XDELETEVEC (info->default_values); 903 } 904 905 /* Populate the array of default values in the order of phi nodes. 906 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch 907 if the range is non-contiguous or the default case has standard 908 structure, otherwise it is the first non-default case instead. */ 909 910 static void 911 gather_default_values (tree default_case, struct switch_conv_info *info) 912 { 913 gphi_iterator gsi; 914 basic_block bb = label_to_block (CASE_LABEL (default_case)); 915 edge e; 916 int i = 0; 917 918 gcc_assert (CASE_LOW (default_case) == NULL_TREE 919 || info->default_case_nonstandard); 920 921 if (bb == info->final_bb) 922 e = find_edge (info->switch_bb, bb); 923 else 924 e = single_succ_edge (bb); 925 926 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) 927 { 928 gphi *phi = gsi.phi (); 929 if (virtual_operand_p (gimple_phi_result (phi))) 930 continue; 931 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); 932 gcc_assert (val); 933 info->default_values[i++] = val; 934 } 935 } 936 937 /* The following function populates the vectors in the constructors array with 938 future contents of the static arrays. The vectors are populated in the 939 order of phi nodes. SWTCH is the switch statement being converted. */ 940 941 static void 942 build_constructors (gswitch *swtch, struct switch_conv_info *info) 943 { 944 unsigned i, branch_num = gimple_switch_num_labels (swtch); 945 tree pos = info->range_min; 946 tree pos_one = build_int_cst (TREE_TYPE (pos), 1); 947 948 for (i = 1; i < branch_num; i++) 949 { 950 tree cs = gimple_switch_label (swtch, i); 951 basic_block bb = label_to_block (CASE_LABEL (cs)); 952 edge e; 953 tree high; 954 gphi_iterator gsi; 955 int j; 956 957 if (bb == info->final_bb) 958 e = find_edge (info->switch_bb, bb); 959 else 960 e = single_succ_edge (bb); 961 gcc_assert (e); 962 963 while (tree_int_cst_lt (pos, CASE_LOW (cs))) 964 { 965 int k; 966 gcc_assert (!info->contiguous_range); 967 for (k = 0; k < info->phi_count; k++) 968 { 969 constructor_elt elt; 970 971 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min); 972 elt.value 973 = unshare_expr_without_location (info->default_values[k]); 974 info->constructors[k]->quick_push (elt); 975 } 976 977 pos = int_const_binop (PLUS_EXPR, pos, pos_one); 978 } 979 gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs))); 980 981 j = 0; 982 if (CASE_HIGH (cs)) 983 high = CASE_HIGH (cs); 984 else 985 high = CASE_LOW (cs); 986 for (gsi = gsi_start_phis (info->final_bb); 987 !gsi_end_p (gsi); gsi_next (&gsi)) 988 { 989 gphi *phi = gsi.phi (); 990 if (virtual_operand_p (gimple_phi_result (phi))) 991 continue; 992 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); 993 tree low = CASE_LOW (cs); 994 pos = CASE_LOW (cs); 995 996 do 997 { 998 constructor_elt elt; 999 1000 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min); 1001 elt.value = unshare_expr_without_location (val); 1002 info->constructors[j]->quick_push (elt); 1003 1004 pos = int_const_binop (PLUS_EXPR, pos, pos_one); 1005 } while (!tree_int_cst_lt (high, pos) 1006 && tree_int_cst_lt (low, pos)); 1007 j++; 1008 } 1009 } 1010 } 1011 1012 /* If all values in the constructor vector are the same, return the value. 1013 Otherwise return NULL_TREE. Not supposed to be called for empty 1014 vectors. */ 1015 1016 static tree 1017 constructor_contains_same_values_p (vec<constructor_elt, va_gc> *vec) 1018 { 1019 unsigned int i; 1020 tree prev = NULL_TREE; 1021 constructor_elt *elt; 1022 1023 FOR_EACH_VEC_SAFE_ELT (vec, i, elt) 1024 { 1025 if (!prev) 1026 prev = elt->value; 1027 else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST)) 1028 return NULL_TREE; 1029 } 1030 return prev; 1031 } 1032 1033 /* Return type which should be used for array elements, either TYPE's 1034 main variant or, for integral types, some smaller integral type 1035 that can still hold all the constants. */ 1036 1037 static tree 1038 array_value_type (gswitch *swtch, tree type, int num, 1039 struct switch_conv_info *info) 1040 { 1041 unsigned int i, len = vec_safe_length (info->constructors[num]); 1042 constructor_elt *elt; 1043 int sign = 0; 1044 tree smaller_type; 1045 1046 /* Types with alignments greater than their size can reach here, e.g. out of 1047 SRA. We couldn't use these as an array component type so get back to the 1048 main variant first, which, for our purposes, is fine for other types as 1049 well. */ 1050 1051 type = TYPE_MAIN_VARIANT (type); 1052 1053 if (!INTEGRAL_TYPE_P (type)) 1054 return type; 1055 1056 scalar_int_mode type_mode = SCALAR_INT_TYPE_MODE (type); 1057 scalar_int_mode mode = get_narrowest_mode (type_mode); 1058 if (GET_MODE_SIZE (type_mode) <= GET_MODE_SIZE (mode)) 1059 return type; 1060 1061 if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32)) 1062 return type; 1063 1064 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt) 1065 { 1066 wide_int cst; 1067 1068 if (TREE_CODE (elt->value) != INTEGER_CST) 1069 return type; 1070 1071 cst = wi::to_wide (elt->value); 1072 while (1) 1073 { 1074 unsigned int prec = GET_MODE_BITSIZE (mode); 1075 if (prec > HOST_BITS_PER_WIDE_INT) 1076 return type; 1077 1078 if (sign >= 0 && cst == wi::zext (cst, prec)) 1079 { 1080 if (sign == 0 && cst == wi::sext (cst, prec)) 1081 break; 1082 sign = 1; 1083 break; 1084 } 1085 if (sign <= 0 && cst == wi::sext (cst, prec)) 1086 { 1087 sign = -1; 1088 break; 1089 } 1090 1091 if (sign == 1) 1092 sign = 0; 1093 1094 if (!GET_MODE_WIDER_MODE (mode).exists (&mode) 1095 || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (type_mode)) 1096 return type; 1097 } 1098 } 1099 1100 if (sign == 0) 1101 sign = TYPE_UNSIGNED (type) ? 1 : -1; 1102 smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0); 1103 if (GET_MODE_SIZE (type_mode) 1104 <= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (smaller_type))) 1105 return type; 1106 1107 return smaller_type; 1108 } 1109 1110 /* Create an appropriate array type and declaration and assemble a static array 1111 variable. Also create a load statement that initializes the variable in 1112 question with a value from the static array. SWTCH is the switch statement 1113 being converted, NUM is the index to arrays of constructors, default values 1114 and target SSA names for this particular array. ARR_INDEX_TYPE is the type 1115 of the index of the new array, PHI is the phi node of the final BB that 1116 corresponds to the value that will be loaded from the created array. TIDX 1117 is an ssa name of a temporary variable holding the index for loads from the 1118 new array. */ 1119 1120 static void 1121 build_one_array (gswitch *swtch, int num, tree arr_index_type, 1122 gphi *phi, tree tidx, struct switch_conv_info *info) 1123 { 1124 tree name, cst; 1125 gimple *load; 1126 gimple_stmt_iterator gsi = gsi_for_stmt (swtch); 1127 location_t loc = gimple_location (swtch); 1128 1129 gcc_assert (info->default_values[num]); 1130 1131 name = copy_ssa_name (PHI_RESULT (phi)); 1132 info->target_inbound_names[num] = name; 1133 1134 cst = constructor_contains_same_values_p (info->constructors[num]); 1135 if (cst) 1136 load = gimple_build_assign (name, cst); 1137 else 1138 { 1139 tree array_type, ctor, decl, value_type, fetch, default_type; 1140 1141 default_type = TREE_TYPE (info->default_values[num]); 1142 value_type = array_value_type (swtch, default_type, num, info); 1143 array_type = build_array_type (value_type, arr_index_type); 1144 if (default_type != value_type) 1145 { 1146 unsigned int i; 1147 constructor_elt *elt; 1148 1149 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt) 1150 elt->value = fold_convert (value_type, elt->value); 1151 } 1152 ctor = build_constructor (array_type, info->constructors[num]); 1153 TREE_CONSTANT (ctor) = true; 1154 TREE_STATIC (ctor) = true; 1155 1156 decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type); 1157 TREE_STATIC (decl) = 1; 1158 DECL_INITIAL (decl) = ctor; 1159 1160 DECL_NAME (decl) = create_tmp_var_name ("CSWTCH"); 1161 DECL_ARTIFICIAL (decl) = 1; 1162 DECL_IGNORED_P (decl) = 1; 1163 TREE_CONSTANT (decl) = 1; 1164 TREE_READONLY (decl) = 1; 1165 DECL_IGNORED_P (decl) = 1; 1166 if (offloading_function_p (cfun->decl)) 1167 DECL_ATTRIBUTES (decl) 1168 = tree_cons (get_identifier ("omp declare target"), NULL_TREE, 1169 NULL_TREE); 1170 varpool_node::finalize_decl (decl); 1171 1172 fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE, 1173 NULL_TREE); 1174 if (default_type != value_type) 1175 { 1176 fetch = fold_convert (default_type, fetch); 1177 fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE, 1178 true, GSI_SAME_STMT); 1179 } 1180 load = gimple_build_assign (name, fetch); 1181 } 1182 1183 gsi_insert_before (&gsi, load, GSI_SAME_STMT); 1184 update_stmt (load); 1185 info->arr_ref_last = load; 1186 } 1187 1188 /* Builds and initializes static arrays initialized with values gathered from 1189 the SWTCH switch statement. Also creates statements that load values from 1190 them. */ 1191 1192 static void 1193 build_arrays (gswitch *swtch, struct switch_conv_info *info) 1194 { 1195 tree arr_index_type; 1196 tree tidx, sub, utype; 1197 gimple *stmt; 1198 gimple_stmt_iterator gsi; 1199 gphi_iterator gpi; 1200 int i; 1201 location_t loc = gimple_location (swtch); 1202 1203 gsi = gsi_for_stmt (swtch); 1204 1205 /* Make sure we do not generate arithmetics in a subrange. */ 1206 utype = TREE_TYPE (info->index_expr); 1207 if (TREE_TYPE (utype)) 1208 utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1); 1209 else 1210 utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1); 1211 1212 arr_index_type = build_index_type (info->range_size); 1213 tidx = make_ssa_name (utype); 1214 sub = fold_build2_loc (loc, MINUS_EXPR, utype, 1215 fold_convert_loc (loc, utype, info->index_expr), 1216 fold_convert_loc (loc, utype, info->range_min)); 1217 sub = force_gimple_operand_gsi (&gsi, sub, 1218 false, NULL, true, GSI_SAME_STMT); 1219 stmt = gimple_build_assign (tidx, sub); 1220 1221 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); 1222 update_stmt (stmt); 1223 info->arr_ref_first = stmt; 1224 1225 for (gpi = gsi_start_phis (info->final_bb), i = 0; 1226 !gsi_end_p (gpi); gsi_next (&gpi)) 1227 { 1228 gphi *phi = gpi.phi (); 1229 if (!virtual_operand_p (gimple_phi_result (phi))) 1230 build_one_array (swtch, i++, arr_index_type, phi, tidx, info); 1231 else 1232 { 1233 edge e; 1234 edge_iterator ei; 1235 FOR_EACH_EDGE (e, ei, info->switch_bb->succs) 1236 { 1237 if (e->dest == info->final_bb) 1238 break; 1239 if (!info->default_case_nonstandard 1240 || e->dest != info->default_bb) 1241 { 1242 e = single_succ_edge (e->dest); 1243 break; 1244 } 1245 } 1246 gcc_assert (e && e->dest == info->final_bb); 1247 info->target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e); 1248 } 1249 } 1250 } 1251 1252 /* Generates and appropriately inserts loads of default values at the position 1253 given by BSI. Returns the last inserted statement. */ 1254 1255 static gassign * 1256 gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info) 1257 { 1258 int i; 1259 gassign *assign = NULL; 1260 1261 for (i = 0; i < info->phi_count; i++) 1262 { 1263 tree name = copy_ssa_name (info->target_inbound_names[i]); 1264 info->target_outbound_names[i] = name; 1265 assign = gimple_build_assign (name, info->default_values[i]); 1266 gsi_insert_before (gsi, assign, GSI_SAME_STMT); 1267 update_stmt (assign); 1268 } 1269 return assign; 1270 } 1271 1272 /* Deletes the unused bbs and edges that now contain the switch statement and 1273 its empty branch bbs. BBD is the now dead BB containing the original switch 1274 statement, FINAL is the last BB of the converted switch statement (in terms 1275 of succession). */ 1276 1277 static void 1278 prune_bbs (basic_block bbd, basic_block final, basic_block default_bb) 1279 { 1280 edge_iterator ei; 1281 edge e; 1282 1283 for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); ) 1284 { 1285 basic_block bb; 1286 bb = e->dest; 1287 remove_edge (e); 1288 if (bb != final && bb != default_bb) 1289 delete_basic_block (bb); 1290 } 1291 delete_basic_block (bbd); 1292 } 1293 1294 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge 1295 from the basic block loading values from an array and E2F from the basic 1296 block loading default values. BBF is the last switch basic block (see the 1297 bbf description in the comment below). */ 1298 1299 static void 1300 fix_phi_nodes (edge e1f, edge e2f, basic_block bbf, 1301 struct switch_conv_info *info) 1302 { 1303 gphi_iterator gsi; 1304 int i; 1305 1306 for (gsi = gsi_start_phis (bbf), i = 0; 1307 !gsi_end_p (gsi); gsi_next (&gsi)) 1308 { 1309 gphi *phi = gsi.phi (); 1310 tree inbound, outbound; 1311 if (virtual_operand_p (gimple_phi_result (phi))) 1312 inbound = outbound = info->target_vop; 1313 else 1314 { 1315 inbound = info->target_inbound_names[i]; 1316 outbound = info->target_outbound_names[i++]; 1317 } 1318 add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION); 1319 if (!info->default_case_nonstandard) 1320 add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION); 1321 } 1322 } 1323 1324 /* Creates a check whether the switch expression value actually falls into the 1325 range given by all the cases. If it does not, the temporaries are loaded 1326 with default values instead. SWTCH is the switch statement being converted. 1327 1328 bb0 is the bb with the switch statement, however, we'll end it with a 1329 condition instead. 1330 1331 bb1 is the bb to be used when the range check went ok. It is derived from 1332 the switch BB 1333 1334 bb2 is the bb taken when the expression evaluated outside of the range 1335 covered by the created arrays. It is populated by loads of default 1336 values. 1337 1338 bbF is a fall through for both bb1 and bb2 and contains exactly what 1339 originally followed the switch statement. 1340 1341 bbD contains the switch statement (in the end). It is unreachable but we 1342 still need to strip off its edges. 1343 */ 1344 1345 static void 1346 gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) 1347 { 1348 tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION); 1349 tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION); 1350 tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION); 1351 glabel *label1, *label2, *label3; 1352 tree utype, tidx; 1353 tree bound; 1354 1355 gcond *cond_stmt; 1356 1357 gassign *last_assign = NULL; 1358 gimple_stmt_iterator gsi; 1359 basic_block bb0, bb1, bb2, bbf, bbd; 1360 edge e01 = NULL, e02, e21, e1d, e1f, e2f; 1361 location_t loc = gimple_location (swtch); 1362 1363 gcc_assert (info->default_values); 1364 1365 bb0 = gimple_bb (swtch); 1366 1367 tidx = gimple_assign_lhs (info->arr_ref_first); 1368 utype = TREE_TYPE (tidx); 1369 1370 /* (end of) block 0 */ 1371 gsi = gsi_for_stmt (info->arr_ref_first); 1372 gsi_next (&gsi); 1373 1374 bound = fold_convert_loc (loc, utype, info->range_size); 1375 cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE); 1376 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT); 1377 update_stmt (cond_stmt); 1378 1379 /* block 2 */ 1380 if (!info->default_case_nonstandard) 1381 { 1382 label2 = gimple_build_label (label_decl2); 1383 gsi_insert_before (&gsi, label2, GSI_SAME_STMT); 1384 last_assign = gen_def_assigns (&gsi, info); 1385 } 1386 1387 /* block 1 */ 1388 label1 = gimple_build_label (label_decl1); 1389 gsi_insert_before (&gsi, label1, GSI_SAME_STMT); 1390 1391 /* block F */ 1392 gsi = gsi_start_bb (info->final_bb); 1393 label3 = gimple_build_label (label_decl3); 1394 gsi_insert_before (&gsi, label3, GSI_SAME_STMT); 1395 1396 /* cfg fix */ 1397 e02 = split_block (bb0, cond_stmt); 1398 bb2 = e02->dest; 1399 1400 if (info->default_case_nonstandard) 1401 { 1402 bb1 = bb2; 1403 bb2 = info->default_bb; 1404 e01 = e02; 1405 e01->flags = EDGE_TRUE_VALUE; 1406 e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE); 1407 edge e_default = find_edge (bb1, bb2); 1408 for (gphi_iterator gsi = gsi_start_phis (bb2); 1409 !gsi_end_p (gsi); gsi_next (&gsi)) 1410 { 1411 gphi *phi = gsi.phi (); 1412 tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_default); 1413 add_phi_arg (phi, arg, e02, 1414 gimple_phi_arg_location_from_edge (phi, e_default)); 1415 } 1416 /* Partially fix the dominator tree, if it is available. */ 1417 if (dom_info_available_p (CDI_DOMINATORS)) 1418 redirect_immediate_dominators (CDI_DOMINATORS, bb1, bb0); 1419 } 1420 else 1421 { 1422 e21 = split_block (bb2, last_assign); 1423 bb1 = e21->dest; 1424 remove_edge (e21); 1425 } 1426 1427 e1d = split_block (bb1, info->arr_ref_last); 1428 bbd = e1d->dest; 1429 remove_edge (e1d); 1430 1431 /* flags and profiles of the edge for in-range values */ 1432 if (!info->default_case_nonstandard) 1433 e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE); 1434 e01->probability = info->default_prob.invert (); 1435 1436 /* flags and profiles of the edge taking care of out-of-range values */ 1437 e02->flags &= ~EDGE_FALLTHRU; 1438 e02->flags |= EDGE_FALSE_VALUE; 1439 e02->probability = info->default_prob; 1440 1441 bbf = info->final_bb; 1442 1443 e1f = make_edge (bb1, bbf, EDGE_FALLTHRU); 1444 e1f->probability = profile_probability::always (); 1445 1446 if (info->default_case_nonstandard) 1447 e2f = NULL; 1448 else 1449 { 1450 e2f = make_edge (bb2, bbf, EDGE_FALLTHRU); 1451 e2f->probability = profile_probability::always (); 1452 } 1453 1454 /* frequencies of the new BBs */ 1455 bb1->count = e01->count (); 1456 bb2->count = e02->count (); 1457 if (!info->default_case_nonstandard) 1458 bbf->count = e1f->count () + e2f->count (); 1459 1460 /* Tidy blocks that have become unreachable. */ 1461 prune_bbs (bbd, info->final_bb, 1462 info->default_case_nonstandard ? info->default_bb : NULL); 1463 1464 /* Fixup the PHI nodes in bbF. */ 1465 fix_phi_nodes (e1f, e2f, bbf, info); 1466 1467 /* Fix the dominator tree, if it is available. */ 1468 if (dom_info_available_p (CDI_DOMINATORS)) 1469 { 1470 vec<basic_block> bbs_to_fix_dom; 1471 1472 set_immediate_dominator (CDI_DOMINATORS, bb1, bb0); 1473 if (!info->default_case_nonstandard) 1474 set_immediate_dominator (CDI_DOMINATORS, bb2, bb0); 1475 if (! get_immediate_dominator (CDI_DOMINATORS, bbf)) 1476 /* If bbD was the immediate dominator ... */ 1477 set_immediate_dominator (CDI_DOMINATORS, bbf, bb0); 1478 1479 bbs_to_fix_dom.create (3 + (bb2 != bbf)); 1480 bbs_to_fix_dom.quick_push (bb0); 1481 bbs_to_fix_dom.quick_push (bb1); 1482 if (bb2 != bbf) 1483 bbs_to_fix_dom.quick_push (bb2); 1484 bbs_to_fix_dom.quick_push (bbf); 1485 1486 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true); 1487 bbs_to_fix_dom.release (); 1488 } 1489 } 1490 1491 /* The following function is invoked on every switch statement (the current one 1492 is given in SWTCH) and runs the individual phases of switch conversion on it 1493 one after another until one fails or the conversion is completed. 1494 Returns NULL on success, or a pointer to a string with the reason why the 1495 conversion failed. */ 1496 1497 static const char * 1498 process_switch (gswitch *swtch) 1499 { 1500 struct switch_conv_info info; 1501 1502 /* Group case labels so that we get the right results from the heuristics 1503 that decide on the code generation approach for this switch. */ 1504 cfg_altered |= group_case_labels_stmt (swtch); 1505 1506 /* If this switch is now a degenerate case with only a default label, 1507 there is nothing left for us to do. */ 1508 if (gimple_switch_num_labels (swtch) < 2) 1509 return "switch is a degenerate case"; 1510 1511 collect_switch_conv_info (swtch, &info); 1512 1513 /* No error markers should reach here (they should be filtered out 1514 during gimplification). */ 1515 gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node); 1516 1517 /* A switch on a constant should have been optimized in tree-cfg-cleanup. */ 1518 gcc_checking_assert (! TREE_CONSTANT (info.index_expr)); 1519 1520 if (info.uniq <= MAX_CASE_BIT_TESTS) 1521 { 1522 if (expand_switch_using_bit_tests_p (info.range_size, 1523 info.uniq, info.count, 1524 optimize_bb_for_speed_p 1525 (gimple_bb (swtch)))) 1526 { 1527 if (dump_file) 1528 fputs (" expanding as bit test is preferable\n", dump_file); 1529 emit_case_bit_tests (swtch, info.index_expr, info.range_min, 1530 info.range_size, info.range_max); 1531 loops_state_set (LOOPS_NEED_FIXUP); 1532 return NULL; 1533 } 1534 1535 if (info.uniq <= 2) 1536 /* This will be expanded as a decision tree in stmt.c:expand_case. */ 1537 return " expanding as jumps is preferable"; 1538 } 1539 1540 /* If there is no common successor, we cannot do the transformation. */ 1541 if (! info.final_bb) 1542 return "no common successor to all case label target blocks found"; 1543 1544 /* Check the case label values are within reasonable range: */ 1545 if (!check_range (&info)) 1546 { 1547 gcc_assert (info.reason); 1548 return info.reason; 1549 } 1550 1551 /* For all the cases, see whether they are empty, the assignments they 1552 represent constant and so on... */ 1553 if (! check_all_empty_except_final (&info)) 1554 { 1555 gcc_assert (info.reason); 1556 return info.reason; 1557 } 1558 if (!check_final_bb (swtch, &info)) 1559 { 1560 gcc_assert (info.reason); 1561 return info.reason; 1562 } 1563 1564 /* At this point all checks have passed and we can proceed with the 1565 transformation. */ 1566 1567 create_temp_arrays (&info); 1568 gather_default_values (info.default_case_nonstandard 1569 ? gimple_switch_label (swtch, 1) 1570 : gimple_switch_default_label (swtch), &info); 1571 if (info.phi_count) 1572 build_constructors (swtch, &info); 1573 1574 build_arrays (swtch, &info); /* Build the static arrays and assignments. */ 1575 gen_inbound_check (swtch, &info); /* Build the bounds check. */ 1576 1577 /* Cleanup: */ 1578 free_temp_arrays (&info); 1579 return NULL; 1580 } 1581 1582 /* The main function of the pass scans statements for switches and invokes 1583 process_switch on them. */ 1584 1585 namespace { 1586 1587 const pass_data pass_data_convert_switch = 1588 { 1589 GIMPLE_PASS, /* type */ 1590 "switchconv", /* name */ 1591 OPTGROUP_NONE, /* optinfo_flags */ 1592 TV_TREE_SWITCH_CONVERSION, /* tv_id */ 1593 ( PROP_cfg | PROP_ssa ), /* properties_required */ 1594 0, /* properties_provided */ 1595 0, /* properties_destroyed */ 1596 0, /* todo_flags_start */ 1597 TODO_update_ssa, /* todo_flags_finish */ 1598 }; 1599 1600 class pass_convert_switch : public gimple_opt_pass 1601 { 1602 public: 1603 pass_convert_switch (gcc::context *ctxt) 1604 : gimple_opt_pass (pass_data_convert_switch, ctxt) 1605 {} 1606 1607 /* opt_pass methods: */ 1608 virtual bool gate (function *) { return flag_tree_switch_conversion != 0; } 1609 virtual unsigned int execute (function *); 1610 1611 }; // class pass_convert_switch 1612 1613 unsigned int 1614 pass_convert_switch::execute (function *fun) 1615 { 1616 basic_block bb; 1617 1618 cfg_altered = false; 1619 FOR_EACH_BB_FN (bb, fun) 1620 { 1621 const char *failure_reason; 1622 gimple *stmt = last_stmt (bb); 1623 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) 1624 { 1625 if (dump_file) 1626 { 1627 expanded_location loc = expand_location (gimple_location (stmt)); 1628 1629 fprintf (dump_file, "beginning to process the following " 1630 "SWITCH statement (%s:%d) : ------- \n", 1631 loc.file, loc.line); 1632 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1633 putc ('\n', dump_file); 1634 } 1635 1636 failure_reason = process_switch (as_a <gswitch *> (stmt)); 1637 if (! failure_reason) 1638 { 1639 cfg_altered = true; 1640 if (dump_file) 1641 { 1642 fputs ("Switch converted\n", dump_file); 1643 fputs ("--------------------------------\n", dump_file); 1644 } 1645 1646 /* Make no effort to update the post-dominator tree. It is actually not 1647 that hard for the transformations we have performed, but it is not 1648 supported by iterate_fix_dominators. */ 1649 free_dominance_info (CDI_POST_DOMINATORS); 1650 } 1651 else 1652 { 1653 if (dump_file) 1654 { 1655 fputs ("Bailing out - ", dump_file); 1656 fputs (failure_reason, dump_file); 1657 fputs ("\n--------------------------------\n", dump_file); 1658 } 1659 } 1660 } 1661 } 1662 1663 return cfg_altered ? TODO_cleanup_cfg : 0; 1664 } 1665 1666 } // anon namespace 1667 1668 gimple_opt_pass * 1669 make_pass_convert_switch (gcc::context *ctxt) 1670 { 1671 return new pass_convert_switch (ctxt); 1672 } 1673 1674 struct case_node 1675 { 1676 case_node *left; /* Left son in binary tree. */ 1677 case_node *right; /* Right son in binary tree; 1678 also node chain. */ 1679 case_node *parent; /* Parent of node in binary tree. */ 1680 tree low; /* Lowest index value for this label. */ 1681 tree high; /* Highest index value for this label. */ 1682 basic_block case_bb; /* Label to jump to when node matches. */ 1683 tree case_label; /* Label to jump to when node matches. */ 1684 profile_probability prob; /* Probability of taking this case. */ 1685 profile_probability subtree_prob; /* Probability of reaching subtree 1686 rooted at this node. */ 1687 }; 1688 1689 typedef case_node *case_node_ptr; 1690 1691 static basic_block emit_case_nodes (basic_block, tree, case_node_ptr, 1692 basic_block, tree, profile_probability, 1693 tree, hash_map<tree, tree> *); 1694 static bool node_has_low_bound (case_node_ptr, tree); 1695 static bool node_has_high_bound (case_node_ptr, tree); 1696 static bool node_is_bounded (case_node_ptr, tree); 1697 1698 /* Return the smallest number of different values for which it is best to use a 1699 jump-table instead of a tree of conditional branches. */ 1700 1701 static unsigned int 1702 case_values_threshold (void) 1703 { 1704 unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD); 1705 1706 if (threshold == 0) 1707 threshold = targetm.case_values_threshold (); 1708 1709 return threshold; 1710 } 1711 1712 /* Reset the aux field of all outgoing edges of basic block BB. */ 1713 1714 static inline void 1715 reset_out_edges_aux (basic_block bb) 1716 { 1717 edge e; 1718 edge_iterator ei; 1719 FOR_EACH_EDGE (e, ei, bb->succs) 1720 e->aux = (void *) 0; 1721 } 1722 1723 /* Compute the number of case labels that correspond to each outgoing edge of 1724 STMT. Record this information in the aux field of the edge. */ 1725 1726 static inline void 1727 compute_cases_per_edge (gswitch *stmt) 1728 { 1729 basic_block bb = gimple_bb (stmt); 1730 reset_out_edges_aux (bb); 1731 int ncases = gimple_switch_num_labels (stmt); 1732 for (int i = ncases - 1; i >= 1; --i) 1733 { 1734 tree elt = gimple_switch_label (stmt, i); 1735 tree lab = CASE_LABEL (elt); 1736 basic_block case_bb = label_to_block_fn (cfun, lab); 1737 edge case_edge = find_edge (bb, case_bb); 1738 case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1); 1739 } 1740 } 1741 1742 /* Do the insertion of a case label into case_list. The labels are 1743 fed to us in descending order from the sorted vector of case labels used 1744 in the tree part of the middle end. So the list we construct is 1745 sorted in ascending order. 1746 1747 LABEL is the case label to be inserted. LOW and HIGH are the bounds 1748 against which the index is compared to jump to LABEL and PROB is the 1749 estimated probability LABEL is reached from the switch statement. */ 1750 1751 static case_node * 1752 add_case_node (case_node *head, tree low, tree high, basic_block case_bb, 1753 tree case_label, profile_probability prob, 1754 object_allocator<case_node> &case_node_pool) 1755 { 1756 case_node *r; 1757 1758 gcc_checking_assert (low); 1759 gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high))); 1760 1761 /* Add this label to the chain. */ 1762 r = case_node_pool.allocate (); 1763 r->low = low; 1764 r->high = high; 1765 r->case_bb = case_bb; 1766 r->case_label = case_label; 1767 r->parent = r->left = NULL; 1768 r->prob = prob; 1769 r->subtree_prob = prob; 1770 r->right = head; 1771 return r; 1772 } 1773 1774 /* Dump ROOT, a list or tree of case nodes, to file. */ 1775 1776 static void 1777 dump_case_nodes (FILE *f, case_node *root, int indent_step, int indent_level) 1778 { 1779 if (root == 0) 1780 return; 1781 indent_level++; 1782 1783 dump_case_nodes (f, root->left, indent_step, indent_level); 1784 1785 fputs (";; ", f); 1786 fprintf (f, "%*s", indent_step * indent_level, ""); 1787 print_dec (wi::to_wide (root->low), f, TYPE_SIGN (TREE_TYPE (root->low))); 1788 if (!tree_int_cst_equal (root->low, root->high)) 1789 { 1790 fprintf (f, " ... "); 1791 print_dec (wi::to_wide (root->high), f, 1792 TYPE_SIGN (TREE_TYPE (root->high))); 1793 } 1794 fputs ("\n", f); 1795 1796 dump_case_nodes (f, root->right, indent_step, indent_level); 1797 } 1798 1799 /* Take an ordered list of case nodes 1800 and transform them into a near optimal binary tree, 1801 on the assumption that any target code selection value is as 1802 likely as any other. 1803 1804 The transformation is performed by splitting the ordered 1805 list into two equal sections plus a pivot. The parts are 1806 then attached to the pivot as left and right branches. Each 1807 branch is then transformed recursively. */ 1808 1809 static void 1810 balance_case_nodes (case_node_ptr *head, case_node_ptr parent) 1811 { 1812 case_node_ptr np; 1813 1814 np = *head; 1815 if (np) 1816 { 1817 int i = 0; 1818 int ranges = 0; 1819 case_node_ptr *npp; 1820 case_node_ptr left; 1821 1822 /* Count the number of entries on branch. Also count the ranges. */ 1823 1824 while (np) 1825 { 1826 if (!tree_int_cst_equal (np->low, np->high)) 1827 ranges++; 1828 1829 i++; 1830 np = np->right; 1831 } 1832 1833 if (i > 2) 1834 { 1835 /* Split this list if it is long enough for that to help. */ 1836 npp = head; 1837 left = *npp; 1838 1839 /* If there are just three nodes, split at the middle one. */ 1840 if (i == 3) 1841 npp = &(*npp)->right; 1842 else 1843 { 1844 /* Find the place in the list that bisects the list's total cost, 1845 where ranges count as 2. 1846 Here I gets half the total cost. */ 1847 i = (i + ranges + 1) / 2; 1848 while (1) 1849 { 1850 /* Skip nodes while their cost does not reach that amount. */ 1851 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high)) 1852 i--; 1853 i--; 1854 if (i <= 0) 1855 break; 1856 npp = &(*npp)->right; 1857 } 1858 } 1859 *head = np = *npp; 1860 *npp = 0; 1861 np->parent = parent; 1862 np->left = left; 1863 1864 /* Optimize each of the two split parts. */ 1865 balance_case_nodes (&np->left, np); 1866 balance_case_nodes (&np->right, np); 1867 np->subtree_prob = np->prob; 1868 np->subtree_prob += np->left->subtree_prob; 1869 np->subtree_prob += np->right->subtree_prob; 1870 } 1871 else 1872 { 1873 /* Else leave this branch as one level, 1874 but fill in `parent' fields. */ 1875 np = *head; 1876 np->parent = parent; 1877 np->subtree_prob = np->prob; 1878 for (; np->right; np = np->right) 1879 { 1880 np->right->parent = np; 1881 (*head)->subtree_prob += np->right->subtree_prob; 1882 } 1883 } 1884 } 1885 } 1886 1887 /* Return true if a switch should be expanded as a decision tree. 1888 RANGE is the difference between highest and lowest case. 1889 UNIQ is number of unique case node targets, not counting the default case. 1890 COUNT is the number of comparisons needed, not counting the default case. */ 1891 1892 static bool 1893 expand_switch_as_decision_tree_p (tree range, 1894 unsigned int uniq ATTRIBUTE_UNUSED, 1895 unsigned int count) 1896 { 1897 int max_ratio; 1898 1899 /* If neither casesi or tablejump is available, or flag_jump_tables 1900 over-ruled us, we really have no choice. */ 1901 if (!targetm.have_casesi () && !targetm.have_tablejump ()) 1902 return true; 1903 if (!flag_jump_tables) 1904 return true; 1905 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT 1906 if (flag_pic) 1907 return true; 1908 #endif 1909 1910 /* If the switch is relatively small such that the cost of one 1911 indirect jump on the target are higher than the cost of a 1912 decision tree, go with the decision tree. 1913 1914 If range of values is much bigger than number of values, 1915 or if it is too large to represent in a HOST_WIDE_INT, 1916 make a sequence of conditional branches instead of a dispatch. 1917 1918 The definition of "much bigger" depends on whether we are 1919 optimizing for size or for speed. If the former, the maximum 1920 ratio range/count = 3, because this was found to be the optimal 1921 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio 1922 10 is much older, and was probably selected after an extensive 1923 benchmarking investigation on numerous platforms. Or maybe it 1924 just made sense to someone at some point in the history of GCC, 1925 who knows... */ 1926 max_ratio = optimize_insn_for_size_p () ? 3 : 10; 1927 if (count < case_values_threshold () || !tree_fits_uhwi_p (range) 1928 || compare_tree_int (range, max_ratio * count) > 0) 1929 return true; 1930 1931 return false; 1932 } 1933 1934 static void 1935 fix_phi_operands_for_edge (edge e, hash_map<tree, tree> *phi_mapping) 1936 { 1937 basic_block bb = e->dest; 1938 gphi_iterator gsi; 1939 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1940 { 1941 gphi *phi = gsi.phi (); 1942 1943 tree *definition = phi_mapping->get (gimple_phi_result (phi)); 1944 if (definition) 1945 add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION); 1946 } 1947 } 1948 1949 1950 /* Add an unconditional jump to CASE_BB that happens in basic block BB. */ 1951 1952 static void 1953 emit_jump (basic_block bb, basic_block case_bb, 1954 hash_map<tree, tree> *phi_mapping) 1955 { 1956 edge e = single_succ_edge (bb); 1957 redirect_edge_succ (e, case_bb); 1958 fix_phi_operands_for_edge (e, phi_mapping); 1959 } 1960 1961 /* Generate a decision tree, switching on INDEX_EXPR and jumping to 1962 one of the labels in CASE_LIST or to the DEFAULT_LABEL. 1963 DEFAULT_PROB is the estimated probability that it jumps to 1964 DEFAULT_LABEL. 1965 1966 We generate a binary decision tree to select the appropriate target 1967 code. */ 1968 1969 static void 1970 emit_case_decision_tree (gswitch *s, tree index_expr, tree index_type, 1971 case_node_ptr case_list, basic_block default_bb, 1972 tree default_label, profile_probability default_prob, 1973 hash_map<tree, tree> *phi_mapping) 1974 { 1975 balance_case_nodes (&case_list, NULL); 1976 1977 if (dump_file) 1978 dump_function_to_file (current_function_decl, dump_file, dump_flags); 1979 if (dump_file && (dump_flags & TDF_DETAILS)) 1980 { 1981 int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2; 1982 fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n"); 1983 dump_case_nodes (dump_file, case_list, indent_step, 0); 1984 } 1985 1986 basic_block bb = gimple_bb (s); 1987 gimple_stmt_iterator gsi = gsi_last_bb (bb); 1988 edge e; 1989 if (gsi_end_p (gsi)) 1990 e = split_block_after_labels (bb); 1991 else 1992 { 1993 gsi_prev (&gsi); 1994 e = split_block (bb, gsi_stmt (gsi)); 1995 } 1996 bb = split_edge (e); 1997 1998 bb = emit_case_nodes (bb, index_expr, case_list, default_bb, default_label, 1999 default_prob, index_type, phi_mapping); 2000 2001 if (bb) 2002 emit_jump (bb, default_bb, phi_mapping); 2003 2004 /* Remove all edges and do just an edge that will reach default_bb. */ 2005 gsi = gsi_last_bb (gimple_bb (s)); 2006 gsi_remove (&gsi, true); 2007 } 2008 2009 static void 2010 record_phi_operand_mapping (const vec<basic_block> bbs, basic_block switch_bb, 2011 hash_map <tree, tree> *map) 2012 { 2013 /* Record all PHI nodes that have to be fixed after conversion. */ 2014 for (unsigned i = 0; i < bbs.length (); i++) 2015 { 2016 basic_block bb = bbs[i]; 2017 2018 gphi_iterator gsi; 2019 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2020 { 2021 gphi *phi = gsi.phi (); 2022 2023 for (unsigned i = 0; i < gimple_phi_num_args (phi); i++) 2024 { 2025 basic_block phi_src_bb = gimple_phi_arg_edge (phi, i)->src; 2026 if (phi_src_bb == switch_bb) 2027 { 2028 tree def = gimple_phi_arg_def (phi, i); 2029 tree result = gimple_phi_result (phi); 2030 map->put (result, def); 2031 break; 2032 } 2033 } 2034 } 2035 } 2036 } 2037 2038 /* Attempt to expand gimple switch STMT to a decision tree. */ 2039 2040 static bool 2041 try_switch_expansion (gswitch *stmt) 2042 { 2043 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE; 2044 basic_block default_bb; 2045 unsigned int count, uniq; 2046 int i; 2047 int ncases = gimple_switch_num_labels (stmt); 2048 tree index_expr = gimple_switch_index (stmt); 2049 tree index_type = TREE_TYPE (index_expr); 2050 tree elt; 2051 basic_block bb = gimple_bb (stmt); 2052 2053 hash_map<tree, tree> phi_mapping; 2054 auto_vec<basic_block> case_bbs; 2055 2056 /* A list of case labels; it is first built as a list and it may then 2057 be rearranged into a nearly balanced binary tree. */ 2058 case_node *case_list = 0; 2059 2060 /* A pool for case nodes. */ 2061 object_allocator<case_node> case_node_pool ("struct case_node pool"); 2062 2063 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index 2064 expressions being INTEGER_CST. */ 2065 gcc_assert (TREE_CODE (index_expr) != INTEGER_CST); 2066 2067 if (ncases == 1) 2068 return false; 2069 2070 /* Find the default case target label. */ 2071 tree default_label = CASE_LABEL (gimple_switch_default_label (stmt)); 2072 default_bb = label_to_block_fn (cfun, default_label); 2073 edge default_edge = find_edge (bb, default_bb); 2074 profile_probability default_prob = default_edge->probability; 2075 case_bbs.safe_push (default_bb); 2076 2077 /* Get upper and lower bounds of case values. */ 2078 elt = gimple_switch_label (stmt, 1); 2079 minval = fold_convert (index_type, CASE_LOW (elt)); 2080 elt = gimple_switch_label (stmt, ncases - 1); 2081 if (CASE_HIGH (elt)) 2082 maxval = fold_convert (index_type, CASE_HIGH (elt)); 2083 else 2084 maxval = fold_convert (index_type, CASE_LOW (elt)); 2085 2086 /* Compute span of values. */ 2087 range = fold_build2 (MINUS_EXPR, index_type, maxval, minval); 2088 2089 /* Listify the labels queue and gather some numbers to decide 2090 how to expand this switch. */ 2091 uniq = 0; 2092 count = 0; 2093 hash_set<tree> seen_labels; 2094 compute_cases_per_edge (stmt); 2095 2096 for (i = ncases - 1; i >= 1; --i) 2097 { 2098 elt = gimple_switch_label (stmt, i); 2099 tree low = CASE_LOW (elt); 2100 gcc_assert (low); 2101 tree high = CASE_HIGH (elt); 2102 gcc_assert (!high || tree_int_cst_lt (low, high)); 2103 tree lab = CASE_LABEL (elt); 2104 2105 /* Count the elements. 2106 A range counts double, since it requires two compares. */ 2107 count++; 2108 if (high) 2109 count++; 2110 2111 /* If we have not seen this label yet, then increase the 2112 number of unique case node targets seen. */ 2113 if (!seen_labels.add (lab)) 2114 uniq++; 2115 2116 /* The bounds on the case range, LOW and HIGH, have to be converted 2117 to case's index type TYPE. Note that the original type of the 2118 case index in the source code is usually "lost" during 2119 gimplification due to type promotion, but the case labels retain the 2120 original type. Make sure to drop overflow flags. */ 2121 low = fold_convert (index_type, low); 2122 if (TREE_OVERFLOW (low)) 2123 low = wide_int_to_tree (index_type, wi::to_wide (low)); 2124 2125 /* The canonical from of a case label in GIMPLE is that a simple case 2126 has an empty CASE_HIGH. For the casesi and tablejump expanders, 2127 the back ends want simple cases to have high == low. */ 2128 if (!high) 2129 high = low; 2130 high = fold_convert (index_type, high); 2131 if (TREE_OVERFLOW (high)) 2132 high = wide_int_to_tree (index_type, wi::to_wide (high)); 2133 2134 basic_block case_bb = label_to_block_fn (cfun, lab); 2135 edge case_edge = find_edge (bb, case_bb); 2136 case_list = add_case_node ( 2137 case_list, low, high, case_bb, lab, 2138 case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux)), 2139 case_node_pool); 2140 2141 case_bbs.safe_push (case_bb); 2142 } 2143 reset_out_edges_aux (bb); 2144 record_phi_operand_mapping (case_bbs, bb, &phi_mapping); 2145 2146 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single 2147 destination, such as one with a default case only. 2148 It also removes cases that are out of range for the switch 2149 type, so we should never get a zero here. */ 2150 gcc_assert (count > 0); 2151 2152 /* Decide how to expand this switch. 2153 The two options at this point are a dispatch table (casesi or 2154 tablejump) or a decision tree. */ 2155 2156 if (expand_switch_as_decision_tree_p (range, uniq, count)) 2157 { 2158 emit_case_decision_tree (stmt, index_expr, index_type, case_list, 2159 default_bb, default_label, default_prob, 2160 &phi_mapping); 2161 return true; 2162 } 2163 2164 return false; 2165 } 2166 2167 /* The main function of the pass scans statements for switches and invokes 2168 process_switch on them. */ 2169 2170 namespace { 2171 2172 const pass_data pass_data_lower_switch = 2173 { 2174 GIMPLE_PASS, /* type */ 2175 "switchlower", /* name */ 2176 OPTGROUP_NONE, /* optinfo_flags */ 2177 TV_TREE_SWITCH_LOWERING, /* tv_id */ 2178 ( PROP_cfg | PROP_ssa ), /* properties_required */ 2179 0, /* properties_provided */ 2180 0, /* properties_destroyed */ 2181 0, /* todo_flags_start */ 2182 TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */ 2183 }; 2184 2185 class pass_lower_switch : public gimple_opt_pass 2186 { 2187 public: 2188 pass_lower_switch (gcc::context *ctxt) 2189 : gimple_opt_pass (pass_data_lower_switch, ctxt) 2190 {} 2191 2192 /* opt_pass methods: */ 2193 virtual bool gate (function *) { return true; } 2194 virtual unsigned int execute (function *); 2195 2196 }; // class pass_lower_switch 2197 2198 unsigned int 2199 pass_lower_switch::execute (function *fun) 2200 { 2201 basic_block bb; 2202 bool expanded = false; 2203 2204 FOR_EACH_BB_FN (bb, fun) 2205 { 2206 gimple *stmt = last_stmt (bb); 2207 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) 2208 { 2209 if (dump_file) 2210 { 2211 expanded_location loc = expand_location (gimple_location (stmt)); 2212 2213 fprintf (dump_file, "beginning to process the following " 2214 "SWITCH statement (%s:%d) : ------- \n", 2215 loc.file, loc.line); 2216 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 2217 putc ('\n', dump_file); 2218 } 2219 2220 expanded |= try_switch_expansion (as_a<gswitch *> (stmt)); 2221 } 2222 } 2223 2224 if (expanded) 2225 { 2226 free_dominance_info (CDI_DOMINATORS); 2227 free_dominance_info (CDI_POST_DOMINATORS); 2228 mark_virtual_operands_for_renaming (cfun); 2229 } 2230 2231 return 0; 2232 } 2233 2234 } // anon namespace 2235 2236 gimple_opt_pass * 2237 make_pass_lower_switch (gcc::context *ctxt) 2238 { 2239 return new pass_lower_switch (ctxt); 2240 } 2241 2242 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. 2243 PROB is the probability of jumping to LABEL. */ 2244 static basic_block 2245 do_jump_if_equal (basic_block bb, tree op0, tree op1, basic_block label_bb, 2246 profile_probability prob, hash_map<tree, tree> *phi_mapping) 2247 { 2248 gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE); 2249 gimple_stmt_iterator gsi = gsi_last_bb (bb); 2250 gsi_insert_before (&gsi, cond, GSI_SAME_STMT); 2251 2252 gcc_assert (single_succ_p (bb)); 2253 2254 /* Make a new basic block where false branch will take place. */ 2255 edge false_edge = split_block (bb, cond); 2256 false_edge->flags = EDGE_FALSE_VALUE; 2257 false_edge->probability = prob.invert (); 2258 2259 edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); 2260 fix_phi_operands_for_edge (true_edge, phi_mapping); 2261 true_edge->probability = prob; 2262 2263 return false_edge->dest; 2264 } 2265 2266 /* Generate code to compare X with Y so that the condition codes are 2267 set and to jump to LABEL if the condition is true. If X is a 2268 constant and Y is not a constant, then the comparison is swapped to 2269 ensure that the comparison RTL has the canonical form. 2270 2271 UNSIGNEDP nonzero says that X and Y are unsigned; this matters if they 2272 need to be widened. UNSIGNEDP is also used to select the proper 2273 branch condition code. 2274 2275 If X and Y have mode BLKmode, then SIZE specifies the size of both X and Y. 2276 2277 MODE is the mode of the inputs (in case they are const_int). 2278 2279 COMPARISON is the rtl operator to compare with (EQ, NE, GT, etc.). 2280 It will be potentially converted into an unsigned variant based on 2281 UNSIGNEDP to select a proper jump instruction. 2282 2283 PROB is the probability of jumping to LABEL. */ 2284 2285 static basic_block 2286 emit_cmp_and_jump_insns (basic_block bb, tree op0, tree op1, 2287 tree_code comparison, basic_block label_bb, 2288 profile_probability prob, 2289 hash_map<tree, tree> *phi_mapping) 2290 { 2291 gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE); 2292 gimple_stmt_iterator gsi = gsi_last_bb (bb); 2293 gsi_insert_after (&gsi, cond, GSI_NEW_STMT); 2294 2295 gcc_assert (single_succ_p (bb)); 2296 2297 /* Make a new basic block where false branch will take place. */ 2298 edge false_edge = split_block (bb, cond); 2299 false_edge->flags = EDGE_FALSE_VALUE; 2300 false_edge->probability = prob.invert (); 2301 2302 edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); 2303 fix_phi_operands_for_edge (true_edge, phi_mapping); 2304 true_edge->probability = prob; 2305 2306 return false_edge->dest; 2307 } 2308 2309 /* Computes the conditional probability of jumping to a target if the branch 2310 instruction is executed. 2311 TARGET_PROB is the estimated probability of jumping to a target relative 2312 to some basic block BB. 2313 BASE_PROB is the probability of reaching the branch instruction relative 2314 to the same basic block BB. */ 2315 2316 static inline profile_probability 2317 conditional_probability (profile_probability target_prob, 2318 profile_probability base_prob) 2319 { 2320 return target_prob / base_prob; 2321 } 2322 2323 /* Emit step-by-step code to select a case for the value of INDEX. 2324 The thus generated decision tree follows the form of the 2325 case-node binary tree NODE, whose nodes represent test conditions. 2326 INDEX_TYPE is the type of the index of the switch. 2327 2328 Care is taken to prune redundant tests from the decision tree 2329 by detecting any boundary conditions already checked by 2330 emitted rtx. (See node_has_high_bound, node_has_low_bound 2331 and node_is_bounded, above.) 2332 2333 Where the test conditions can be shown to be redundant we emit 2334 an unconditional jump to the target code. As a further 2335 optimization, the subordinates of a tree node are examined to 2336 check for bounded nodes. In this case conditional and/or 2337 unconditional jumps as a result of the boundary check for the 2338 current node are arranged to target the subordinates associated 2339 code for out of bound conditions on the current node. 2340 2341 We can assume that when control reaches the code generated here, 2342 the index value has already been compared with the parents 2343 of this node, and determined to be on the same side of each parent 2344 as this node is. Thus, if this node tests for the value 51, 2345 and a parent tested for 52, we don't need to consider 2346 the possibility of a value greater than 51. If another parent 2347 tests for the value 50, then this node need not test anything. */ 2348 2349 static basic_block 2350 emit_case_nodes (basic_block bb, tree index, case_node_ptr node, 2351 basic_block default_bb, tree default_label, 2352 profile_probability default_prob, tree index_type, 2353 hash_map<tree, tree> *phi_mapping) 2354 { 2355 /* If INDEX has an unsigned type, we must make unsigned branches. */ 2356 profile_probability probability; 2357 profile_probability prob = node->prob, subtree_prob = node->subtree_prob; 2358 2359 /* See if our parents have already tested everything for us. 2360 If they have, emit an unconditional jump for this node. */ 2361 if (node_is_bounded (node, index_type)) 2362 { 2363 emit_jump (bb, node->case_bb, phi_mapping); 2364 return NULL; 2365 } 2366 2367 else if (tree_int_cst_equal (node->low, node->high)) 2368 { 2369 probability = conditional_probability (prob, subtree_prob + default_prob); 2370 /* Node is single valued. First see if the index expression matches 2371 this node and then check our children, if any. */ 2372 bb = do_jump_if_equal (bb, index, node->low, node->case_bb, probability, 2373 phi_mapping); 2374 /* Since this case is taken at this point, reduce its weight from 2375 subtree_weight. */ 2376 subtree_prob -= prob; 2377 if (node->right != 0 && node->left != 0) 2378 { 2379 /* This node has children on both sides. 2380 Dispatch to one side or the other 2381 by comparing the index value with this node's value. 2382 If one subtree is bounded, check that one first, 2383 so we can avoid real branches in the tree. */ 2384 2385 if (node_is_bounded (node->right, index_type)) 2386 { 2387 probability 2388 = conditional_probability (node->right->prob, 2389 subtree_prob + default_prob); 2390 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, 2391 node->right->case_bb, probability, 2392 phi_mapping); 2393 bb = emit_case_nodes (bb, index, node->left, default_bb, 2394 default_label, default_prob, index_type, 2395 phi_mapping); 2396 } 2397 2398 else if (node_is_bounded (node->left, index_type)) 2399 { 2400 probability 2401 = conditional_probability (node->left->prob, 2402 subtree_prob + default_prob); 2403 bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR, 2404 node->left->case_bb, probability, 2405 phi_mapping); 2406 bb = emit_case_nodes (bb, index, node->right, default_bb, 2407 default_label, default_prob, index_type, 2408 phi_mapping); 2409 } 2410 2411 /* If both children are single-valued cases with no 2412 children, finish up all the work. This way, we can save 2413 one ordered comparison. */ 2414 else if (tree_int_cst_equal (node->right->low, node->right->high) 2415 && node->right->left == 0 && node->right->right == 0 2416 && tree_int_cst_equal (node->left->low, node->left->high) 2417 && node->left->left == 0 && node->left->right == 0) 2418 { 2419 /* Neither node is bounded. First distinguish the two sides; 2420 then emit the code for one side at a time. */ 2421 2422 /* See if the value matches what the right hand side 2423 wants. */ 2424 probability 2425 = conditional_probability (node->right->prob, 2426 subtree_prob + default_prob); 2427 bb = do_jump_if_equal (bb, index, node->right->low, 2428 node->right->case_bb, probability, 2429 phi_mapping); 2430 2431 /* See if the value matches what the left hand side 2432 wants. */ 2433 probability 2434 = conditional_probability (node->left->prob, 2435 subtree_prob + default_prob); 2436 bb = do_jump_if_equal (bb, index, node->left->low, 2437 node->left->case_bb, probability, 2438 phi_mapping); 2439 } 2440 2441 else 2442 { 2443 /* Neither node is bounded. First distinguish the two sides; 2444 then emit the code for one side at a time. */ 2445 2446 basic_block test_bb = split_edge (single_succ_edge (bb)); 2447 redirect_edge_succ (single_pred_edge (test_bb), 2448 single_succ_edge (bb)->dest); 2449 2450 /* The default label could be reached either through the right 2451 subtree or the left subtree. Divide the probability 2452 equally. */ 2453 probability 2454 = conditional_probability (node->right->subtree_prob 2455 + default_prob.apply_scale (1, 2), 2456 subtree_prob + default_prob); 2457 /* See if the value is on the right. */ 2458 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, 2459 test_bb, probability, phi_mapping); 2460 default_prob = default_prob.apply_scale (1, 2); 2461 2462 /* Value must be on the left. 2463 Handle the left-hand subtree. */ 2464 bb = emit_case_nodes (bb, index, node->left, default_bb, 2465 default_label, default_prob, index_type, 2466 phi_mapping); 2467 /* If left-hand subtree does nothing, 2468 go to default. */ 2469 2470 if (bb && default_bb) 2471 emit_jump (bb, default_bb, phi_mapping); 2472 2473 /* Code branches here for the right-hand subtree. */ 2474 bb = emit_case_nodes (test_bb, index, node->right, default_bb, 2475 default_label, default_prob, index_type, 2476 phi_mapping); 2477 } 2478 } 2479 else if (node->right != 0 && node->left == 0) 2480 { 2481 /* Here we have a right child but no left so we issue a conditional 2482 branch to default and process the right child. 2483 2484 Omit the conditional branch to default if the right child 2485 does not have any children and is single valued; it would 2486 cost too much space to save so little time. */ 2487 2488 if (node->right->right || node->right->left 2489 || !tree_int_cst_equal (node->right->low, node->right->high)) 2490 { 2491 if (!node_has_low_bound (node, index_type)) 2492 { 2493 probability 2494 = conditional_probability (default_prob.apply_scale (1, 2), 2495 subtree_prob + default_prob); 2496 bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR, 2497 default_bb, probability, 2498 phi_mapping); 2499 default_prob = default_prob.apply_scale (1, 2); 2500 } 2501 2502 bb = emit_case_nodes (bb, index, node->right, default_bb, 2503 default_label, default_prob, index_type, 2504 phi_mapping); 2505 } 2506 else 2507 { 2508 probability 2509 = conditional_probability (node->right->subtree_prob, 2510 subtree_prob + default_prob); 2511 /* We cannot process node->right normally 2512 since we haven't ruled out the numbers less than 2513 this node's value. So handle node->right explicitly. */ 2514 bb = do_jump_if_equal (bb, index, node->right->low, 2515 node->right->case_bb, probability, 2516 phi_mapping); 2517 } 2518 } 2519 2520 else if (node->right == 0 && node->left != 0) 2521 { 2522 /* Just one subtree, on the left. */ 2523 if (node->left->left || node->left->right 2524 || !tree_int_cst_equal (node->left->low, node->left->high)) 2525 { 2526 if (!node_has_high_bound (node, index_type)) 2527 { 2528 probability 2529 = conditional_probability (default_prob.apply_scale (1, 2), 2530 subtree_prob + default_prob); 2531 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, 2532 default_bb, probability, 2533 phi_mapping); 2534 default_prob = default_prob.apply_scale (1, 2); 2535 } 2536 2537 bb = emit_case_nodes (bb, index, node->left, default_bb, 2538 default_label, default_prob, index_type, 2539 phi_mapping); 2540 } 2541 else 2542 { 2543 probability 2544 = conditional_probability (node->left->subtree_prob, 2545 subtree_prob + default_prob); 2546 /* We cannot process node->left normally 2547 since we haven't ruled out the numbers less than 2548 this node's value. So handle node->left explicitly. */ 2549 do_jump_if_equal (bb, index, node->left->low, node->left->case_bb, 2550 probability, phi_mapping); 2551 } 2552 } 2553 } 2554 else 2555 { 2556 /* Node is a range. These cases are very similar to those for a single 2557 value, except that we do not start by testing whether this node 2558 is the one to branch to. */ 2559 2560 if (node->right != 0 && node->left != 0) 2561 { 2562 /* Node has subtrees on both sides. 2563 If the right-hand subtree is bounded, 2564 test for it first, since we can go straight there. 2565 Otherwise, we need to make a branch in the control structure, 2566 then handle the two subtrees. */ 2567 basic_block test_bb = NULL; 2568 2569 if (node_is_bounded (node->right, index_type)) 2570 { 2571 /* Right hand node is fully bounded so we can eliminate any 2572 testing and branch directly to the target code. */ 2573 probability 2574 = conditional_probability (node->right->subtree_prob, 2575 subtree_prob + default_prob); 2576 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, 2577 node->right->case_bb, probability, 2578 phi_mapping); 2579 } 2580 else 2581 { 2582 /* Right hand node requires testing. 2583 Branch to a label where we will handle it later. */ 2584 2585 test_bb = split_edge (single_succ_edge (bb)); 2586 redirect_edge_succ (single_pred_edge (test_bb), 2587 single_succ_edge (bb)->dest); 2588 2589 probability 2590 = conditional_probability (node->right->subtree_prob 2591 + default_prob.apply_scale (1, 2), 2592 subtree_prob + default_prob); 2593 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, 2594 test_bb, probability, phi_mapping); 2595 default_prob = default_prob.apply_scale (1, 2); 2596 } 2597 2598 /* Value belongs to this node or to the left-hand subtree. */ 2599 2600 probability 2601 = conditional_probability (prob, subtree_prob + default_prob); 2602 bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR, 2603 node->case_bb, probability, 2604 phi_mapping); 2605 2606 /* Handle the left-hand subtree. */ 2607 bb = emit_case_nodes (bb, index, node->left, default_bb, 2608 default_label, default_prob, index_type, 2609 phi_mapping); 2610 2611 /* If right node had to be handled later, do that now. */ 2612 if (test_bb) 2613 { 2614 /* If the left-hand subtree fell through, 2615 don't let it fall into the right-hand subtree. */ 2616 if (bb && default_bb) 2617 emit_jump (bb, default_bb, phi_mapping); 2618 2619 bb = emit_case_nodes (test_bb, index, node->right, default_bb, 2620 default_label, default_prob, index_type, 2621 phi_mapping); 2622 } 2623 } 2624 2625 else if (node->right != 0 && node->left == 0) 2626 { 2627 /* Deal with values to the left of this node, 2628 if they are possible. */ 2629 if (!node_has_low_bound (node, index_type)) 2630 { 2631 probability 2632 = conditional_probability (default_prob.apply_scale (1, 2), 2633 subtree_prob + default_prob); 2634 bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR, 2635 default_bb, probability, 2636 phi_mapping); 2637 default_prob = default_prob.apply_scale (1, 2); 2638 } 2639 2640 /* Value belongs to this node or to the right-hand subtree. */ 2641 2642 probability 2643 = conditional_probability (prob, subtree_prob + default_prob); 2644 bb = emit_cmp_and_jump_insns (bb, index, node->high, LE_EXPR, 2645 node->case_bb, probability, 2646 phi_mapping); 2647 2648 bb = emit_case_nodes (bb, index, node->right, default_bb, 2649 default_label, default_prob, index_type, 2650 phi_mapping); 2651 } 2652 2653 else if (node->right == 0 && node->left != 0) 2654 { 2655 /* Deal with values to the right of this node, 2656 if they are possible. */ 2657 if (!node_has_high_bound (node, index_type)) 2658 { 2659 probability 2660 = conditional_probability (default_prob.apply_scale (1, 2), 2661 subtree_prob + default_prob); 2662 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, 2663 default_bb, probability, 2664 phi_mapping); 2665 default_prob = default_prob.apply_scale (1, 2); 2666 } 2667 2668 /* Value belongs to this node or to the left-hand subtree. */ 2669 2670 probability 2671 = conditional_probability (prob, subtree_prob + default_prob); 2672 bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR, 2673 node->case_bb, probability, 2674 phi_mapping); 2675 2676 bb = emit_case_nodes (bb, index, node->left, default_bb, 2677 default_label, default_prob, index_type, 2678 phi_mapping); 2679 } 2680 2681 else 2682 { 2683 /* Node has no children so we check low and high bounds to remove 2684 redundant tests. Only one of the bounds can exist, 2685 since otherwise this node is bounded--a case tested already. */ 2686 bool high_bound = node_has_high_bound (node, index_type); 2687 bool low_bound = node_has_low_bound (node, index_type); 2688 2689 if (!high_bound && low_bound) 2690 { 2691 probability 2692 = conditional_probability (default_prob, 2693 subtree_prob + default_prob); 2694 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, 2695 default_bb, probability, 2696 phi_mapping); 2697 } 2698 2699 else if (!low_bound && high_bound) 2700 { 2701 probability 2702 = conditional_probability (default_prob, 2703 subtree_prob + default_prob); 2704 bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR, 2705 default_bb, probability, 2706 phi_mapping); 2707 } 2708 else if (!low_bound && !high_bound) 2709 { 2710 tree lhs, rhs; 2711 generate_range_test (bb, index, node->low, node->high, 2712 &lhs, &rhs); 2713 probability 2714 = conditional_probability (default_prob, 2715 subtree_prob + default_prob); 2716 bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR, 2717 default_bb, probability, 2718 phi_mapping); 2719 } 2720 2721 emit_jump (bb, node->case_bb, phi_mapping); 2722 return NULL; 2723 } 2724 } 2725 2726 return bb; 2727 } 2728 2729 /* Search the parent sections of the case node tree 2730 to see if a test for the lower bound of NODE would be redundant. 2731 INDEX_TYPE is the type of the index expression. 2732 2733 The instructions to generate the case decision tree are 2734 output in the same order as nodes are processed so it is 2735 known that if a parent node checks the range of the current 2736 node minus one that the current node is bounded at its lower 2737 span. Thus the test would be redundant. */ 2738 2739 static bool 2740 node_has_low_bound (case_node_ptr node, tree index_type) 2741 { 2742 tree low_minus_one; 2743 case_node_ptr pnode; 2744 2745 /* If the lower bound of this node is the lowest value in the index type, 2746 we need not test it. */ 2747 2748 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type))) 2749 return true; 2750 2751 /* If this node has a left branch, the value at the left must be less 2752 than that at this node, so it cannot be bounded at the bottom and 2753 we need not bother testing any further. */ 2754 2755 if (node->left) 2756 return false; 2757 2758 low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), node->low, 2759 build_int_cst (TREE_TYPE (node->low), 1)); 2760 2761 /* If the subtraction above overflowed, we can't verify anything. 2762 Otherwise, look for a parent that tests our value - 1. */ 2763 2764 if (!tree_int_cst_lt (low_minus_one, node->low)) 2765 return false; 2766 2767 for (pnode = node->parent; pnode; pnode = pnode->parent) 2768 if (tree_int_cst_equal (low_minus_one, pnode->high)) 2769 return true; 2770 2771 return false; 2772 } 2773 2774 /* Search the parent sections of the case node tree 2775 to see if a test for the upper bound of NODE would be redundant. 2776 INDEX_TYPE is the type of the index expression. 2777 2778 The instructions to generate the case decision tree are 2779 output in the same order as nodes are processed so it is 2780 known that if a parent node checks the range of the current 2781 node plus one that the current node is bounded at its upper 2782 span. Thus the test would be redundant. */ 2783 2784 static bool 2785 node_has_high_bound (case_node_ptr node, tree index_type) 2786 { 2787 tree high_plus_one; 2788 case_node_ptr pnode; 2789 2790 /* If there is no upper bound, obviously no test is needed. */ 2791 2792 if (TYPE_MAX_VALUE (index_type) == NULL) 2793 return true; 2794 2795 /* If the upper bound of this node is the highest value in the type 2796 of the index expression, we need not test against it. */ 2797 2798 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type))) 2799 return true; 2800 2801 /* If this node has a right branch, the value at the right must be greater 2802 than that at this node, so it cannot be bounded at the top and 2803 we need not bother testing any further. */ 2804 2805 if (node->right) 2806 return false; 2807 2808 high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), node->high, 2809 build_int_cst (TREE_TYPE (node->high), 1)); 2810 2811 /* If the addition above overflowed, we can't verify anything. 2812 Otherwise, look for a parent that tests our value + 1. */ 2813 2814 if (!tree_int_cst_lt (node->high, high_plus_one)) 2815 return false; 2816 2817 for (pnode = node->parent; pnode; pnode = pnode->parent) 2818 if (tree_int_cst_equal (high_plus_one, pnode->low)) 2819 return true; 2820 2821 return false; 2822 } 2823 2824 /* Search the parent sections of the 2825 case node tree to see if both tests for the upper and lower 2826 bounds of NODE would be redundant. */ 2827 2828 static bool 2829 node_is_bounded (case_node_ptr node, tree index_type) 2830 { 2831 return (node_has_low_bound (node, index_type) 2832 && node_has_high_bound (node, index_type)); 2833 } 2834