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> *, location_t); 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 gimple_location (s)); 2001 2002 if (bb) 2003 emit_jump (bb, default_bb, phi_mapping); 2004 2005 /* Remove all edges and do just an edge that will reach default_bb. */ 2006 gsi = gsi_last_bb (gimple_bb (s)); 2007 gsi_remove (&gsi, true); 2008 } 2009 2010 static void 2011 record_phi_operand_mapping (const vec<basic_block> bbs, basic_block switch_bb, 2012 hash_map <tree, tree> *map) 2013 { 2014 /* Record all PHI nodes that have to be fixed after conversion. */ 2015 for (unsigned i = 0; i < bbs.length (); i++) 2016 { 2017 basic_block bb = bbs[i]; 2018 2019 gphi_iterator gsi; 2020 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2021 { 2022 gphi *phi = gsi.phi (); 2023 2024 for (unsigned i = 0; i < gimple_phi_num_args (phi); i++) 2025 { 2026 basic_block phi_src_bb = gimple_phi_arg_edge (phi, i)->src; 2027 if (phi_src_bb == switch_bb) 2028 { 2029 tree def = gimple_phi_arg_def (phi, i); 2030 tree result = gimple_phi_result (phi); 2031 map->put (result, def); 2032 break; 2033 } 2034 } 2035 } 2036 } 2037 } 2038 2039 /* Attempt to expand gimple switch STMT to a decision tree. */ 2040 2041 static bool 2042 try_switch_expansion (gswitch *stmt) 2043 { 2044 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE; 2045 basic_block default_bb; 2046 unsigned int count, uniq; 2047 int i; 2048 int ncases = gimple_switch_num_labels (stmt); 2049 tree index_expr = gimple_switch_index (stmt); 2050 tree index_type = TREE_TYPE (index_expr); 2051 tree elt; 2052 basic_block bb = gimple_bb (stmt); 2053 2054 hash_map<tree, tree> phi_mapping; 2055 auto_vec<basic_block> case_bbs; 2056 2057 /* A list of case labels; it is first built as a list and it may then 2058 be rearranged into a nearly balanced binary tree. */ 2059 case_node *case_list = 0; 2060 2061 /* A pool for case nodes. */ 2062 object_allocator<case_node> case_node_pool ("struct case_node pool"); 2063 2064 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index 2065 expressions being INTEGER_CST. */ 2066 gcc_assert (TREE_CODE (index_expr) != INTEGER_CST); 2067 2068 if (ncases == 1) 2069 return false; 2070 2071 /* Find the default case target label. */ 2072 tree default_label = CASE_LABEL (gimple_switch_default_label (stmt)); 2073 default_bb = label_to_block_fn (cfun, default_label); 2074 edge default_edge = find_edge (bb, default_bb); 2075 profile_probability default_prob = default_edge->probability; 2076 case_bbs.safe_push (default_bb); 2077 2078 /* Get upper and lower bounds of case values. */ 2079 elt = gimple_switch_label (stmt, 1); 2080 minval = fold_convert (index_type, CASE_LOW (elt)); 2081 elt = gimple_switch_label (stmt, ncases - 1); 2082 if (CASE_HIGH (elt)) 2083 maxval = fold_convert (index_type, CASE_HIGH (elt)); 2084 else 2085 maxval = fold_convert (index_type, CASE_LOW (elt)); 2086 2087 /* Compute span of values. */ 2088 range = fold_build2 (MINUS_EXPR, index_type, maxval, minval); 2089 2090 /* Listify the labels queue and gather some numbers to decide 2091 how to expand this switch. */ 2092 uniq = 0; 2093 count = 0; 2094 hash_set<tree> seen_labels; 2095 compute_cases_per_edge (stmt); 2096 2097 for (i = ncases - 1; i >= 1; --i) 2098 { 2099 elt = gimple_switch_label (stmt, i); 2100 tree low = CASE_LOW (elt); 2101 gcc_assert (low); 2102 tree high = CASE_HIGH (elt); 2103 gcc_assert (!high || tree_int_cst_lt (low, high)); 2104 tree lab = CASE_LABEL (elt); 2105 2106 /* Count the elements. 2107 A range counts double, since it requires two compares. */ 2108 count++; 2109 if (high) 2110 count++; 2111 2112 /* If we have not seen this label yet, then increase the 2113 number of unique case node targets seen. */ 2114 if (!seen_labels.add (lab)) 2115 uniq++; 2116 2117 /* The bounds on the case range, LOW and HIGH, have to be converted 2118 to case's index type TYPE. Note that the original type of the 2119 case index in the source code is usually "lost" during 2120 gimplification due to type promotion, but the case labels retain the 2121 original type. Make sure to drop overflow flags. */ 2122 low = fold_convert (index_type, low); 2123 if (TREE_OVERFLOW (low)) 2124 low = wide_int_to_tree (index_type, wi::to_wide (low)); 2125 2126 /* The canonical from of a case label in GIMPLE is that a simple case 2127 has an empty CASE_HIGH. For the casesi and tablejump expanders, 2128 the back ends want simple cases to have high == low. */ 2129 if (!high) 2130 high = low; 2131 high = fold_convert (index_type, high); 2132 if (TREE_OVERFLOW (high)) 2133 high = wide_int_to_tree (index_type, wi::to_wide (high)); 2134 2135 basic_block case_bb = label_to_block_fn (cfun, lab); 2136 edge case_edge = find_edge (bb, case_bb); 2137 case_list = add_case_node ( 2138 case_list, low, high, case_bb, lab, 2139 case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux)), 2140 case_node_pool); 2141 2142 case_bbs.safe_push (case_bb); 2143 } 2144 reset_out_edges_aux (bb); 2145 record_phi_operand_mapping (case_bbs, bb, &phi_mapping); 2146 2147 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single 2148 destination, such as one with a default case only. 2149 It also removes cases that are out of range for the switch 2150 type, so we should never get a zero here. */ 2151 gcc_assert (count > 0); 2152 2153 /* Decide how to expand this switch. 2154 The two options at this point are a dispatch table (casesi or 2155 tablejump) or a decision tree. */ 2156 2157 if (expand_switch_as_decision_tree_p (range, uniq, count)) 2158 { 2159 emit_case_decision_tree (stmt, index_expr, index_type, case_list, 2160 default_bb, default_label, default_prob, 2161 &phi_mapping); 2162 return true; 2163 } 2164 2165 return false; 2166 } 2167 2168 /* The main function of the pass scans statements for switches and invokes 2169 process_switch on them. */ 2170 2171 namespace { 2172 2173 const pass_data pass_data_lower_switch = 2174 { 2175 GIMPLE_PASS, /* type */ 2176 "switchlower", /* name */ 2177 OPTGROUP_NONE, /* optinfo_flags */ 2178 TV_TREE_SWITCH_LOWERING, /* tv_id */ 2179 ( PROP_cfg | PROP_ssa ), /* properties_required */ 2180 0, /* properties_provided */ 2181 0, /* properties_destroyed */ 2182 0, /* todo_flags_start */ 2183 TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */ 2184 }; 2185 2186 class pass_lower_switch : public gimple_opt_pass 2187 { 2188 public: 2189 pass_lower_switch (gcc::context *ctxt) 2190 : gimple_opt_pass (pass_data_lower_switch, ctxt) 2191 {} 2192 2193 /* opt_pass methods: */ 2194 virtual bool gate (function *) { return true; } 2195 virtual unsigned int execute (function *); 2196 2197 }; // class pass_lower_switch 2198 2199 unsigned int 2200 pass_lower_switch::execute (function *fun) 2201 { 2202 basic_block bb; 2203 bool expanded = false; 2204 2205 FOR_EACH_BB_FN (bb, fun) 2206 { 2207 gimple *stmt = last_stmt (bb); 2208 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) 2209 { 2210 if (dump_file) 2211 { 2212 expanded_location loc = expand_location (gimple_location (stmt)); 2213 2214 fprintf (dump_file, "beginning to process the following " 2215 "SWITCH statement (%s:%d) : ------- \n", 2216 loc.file, loc.line); 2217 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 2218 putc ('\n', dump_file); 2219 } 2220 2221 expanded |= try_switch_expansion (as_a<gswitch *> (stmt)); 2222 } 2223 } 2224 2225 if (expanded) 2226 { 2227 free_dominance_info (CDI_DOMINATORS); 2228 free_dominance_info (CDI_POST_DOMINATORS); 2229 mark_virtual_operands_for_renaming (cfun); 2230 } 2231 2232 return 0; 2233 } 2234 2235 } // anon namespace 2236 2237 gimple_opt_pass * 2238 make_pass_lower_switch (gcc::context *ctxt) 2239 { 2240 return new pass_lower_switch (ctxt); 2241 } 2242 2243 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. 2244 PROB is the probability of jumping to LABEL. */ 2245 static basic_block 2246 do_jump_if_equal (basic_block bb, tree op0, tree op1, basic_block label_bb, 2247 profile_probability prob, hash_map<tree, tree> *phi_mapping, 2248 location_t loc) 2249 { 2250 gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE); 2251 gimple_set_location (cond, loc); 2252 gimple_stmt_iterator gsi = gsi_last_bb (bb); 2253 gsi_insert_before (&gsi, cond, GSI_SAME_STMT); 2254 2255 gcc_assert (single_succ_p (bb)); 2256 2257 /* Make a new basic block where false branch will take place. */ 2258 edge false_edge = split_block (bb, cond); 2259 false_edge->flags = EDGE_FALSE_VALUE; 2260 false_edge->probability = prob.invert (); 2261 2262 edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); 2263 fix_phi_operands_for_edge (true_edge, phi_mapping); 2264 true_edge->probability = prob; 2265 2266 return false_edge->dest; 2267 } 2268 2269 /* Generate code to compare X with Y so that the condition codes are 2270 set and to jump to LABEL if the condition is true. If X is a 2271 constant and Y is not a constant, then the comparison is swapped to 2272 ensure that the comparison RTL has the canonical form. 2273 2274 UNSIGNEDP nonzero says that X and Y are unsigned; this matters if they 2275 need to be widened. UNSIGNEDP is also used to select the proper 2276 branch condition code. 2277 2278 If X and Y have mode BLKmode, then SIZE specifies the size of both X and Y. 2279 2280 MODE is the mode of the inputs (in case they are const_int). 2281 2282 COMPARISON is the rtl operator to compare with (EQ, NE, GT, etc.). 2283 It will be potentially converted into an unsigned variant based on 2284 UNSIGNEDP to select a proper jump instruction. 2285 2286 PROB is the probability of jumping to LABEL. */ 2287 2288 static basic_block 2289 emit_cmp_and_jump_insns (basic_block bb, tree op0, tree op1, 2290 tree_code comparison, basic_block label_bb, 2291 profile_probability prob, 2292 hash_map<tree, tree> *phi_mapping, 2293 location_t loc) 2294 { 2295 gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE); 2296 gimple_set_location (cond, loc); 2297 gimple_stmt_iterator gsi = gsi_last_bb (bb); 2298 gsi_insert_after (&gsi, cond, GSI_NEW_STMT); 2299 2300 gcc_assert (single_succ_p (bb)); 2301 2302 /* Make a new basic block where false branch will take place. */ 2303 edge false_edge = split_block (bb, cond); 2304 false_edge->flags = EDGE_FALSE_VALUE; 2305 false_edge->probability = prob.invert (); 2306 2307 edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE); 2308 fix_phi_operands_for_edge (true_edge, phi_mapping); 2309 true_edge->probability = prob; 2310 2311 return false_edge->dest; 2312 } 2313 2314 /* Computes the conditional probability of jumping to a target if the branch 2315 instruction is executed. 2316 TARGET_PROB is the estimated probability of jumping to a target relative 2317 to some basic block BB. 2318 BASE_PROB is the probability of reaching the branch instruction relative 2319 to the same basic block BB. */ 2320 2321 static inline profile_probability 2322 conditional_probability (profile_probability target_prob, 2323 profile_probability base_prob) 2324 { 2325 return target_prob / base_prob; 2326 } 2327 2328 /* Emit step-by-step code to select a case for the value of INDEX. 2329 The thus generated decision tree follows the form of the 2330 case-node binary tree NODE, whose nodes represent test conditions. 2331 INDEX_TYPE is the type of the index of the switch. 2332 2333 Care is taken to prune redundant tests from the decision tree 2334 by detecting any boundary conditions already checked by 2335 emitted rtx. (See node_has_high_bound, node_has_low_bound 2336 and node_is_bounded, above.) 2337 2338 Where the test conditions can be shown to be redundant we emit 2339 an unconditional jump to the target code. As a further 2340 optimization, the subordinates of a tree node are examined to 2341 check for bounded nodes. In this case conditional and/or 2342 unconditional jumps as a result of the boundary check for the 2343 current node are arranged to target the subordinates associated 2344 code for out of bound conditions on the current node. 2345 2346 We can assume that when control reaches the code generated here, 2347 the index value has already been compared with the parents 2348 of this node, and determined to be on the same side of each parent 2349 as this node is. Thus, if this node tests for the value 51, 2350 and a parent tested for 52, we don't need to consider 2351 the possibility of a value greater than 51. If another parent 2352 tests for the value 50, then this node need not test anything. */ 2353 2354 static basic_block 2355 emit_case_nodes (basic_block bb, tree index, case_node_ptr node, 2356 basic_block default_bb, tree default_label, 2357 profile_probability default_prob, tree index_type, 2358 hash_map<tree, tree> *phi_mapping, 2359 location_t loc) 2360 { 2361 /* If INDEX has an unsigned type, we must make unsigned branches. */ 2362 profile_probability probability; 2363 profile_probability prob = node->prob, subtree_prob = node->subtree_prob; 2364 2365 /* See if our parents have already tested everything for us. 2366 If they have, emit an unconditional jump for this node. */ 2367 if (node_is_bounded (node, index_type)) 2368 { 2369 emit_jump (bb, node->case_bb, phi_mapping); 2370 return NULL; 2371 } 2372 2373 else if (tree_int_cst_equal (node->low, node->high)) 2374 { 2375 probability = conditional_probability (prob, subtree_prob + default_prob); 2376 /* Node is single valued. First see if the index expression matches 2377 this node and then check our children, if any. */ 2378 bb = do_jump_if_equal (bb, index, node->low, node->case_bb, probability, 2379 phi_mapping, loc); 2380 /* Since this case is taken at this point, reduce its weight from 2381 subtree_weight. */ 2382 subtree_prob -= prob; 2383 if (node->right != 0 && node->left != 0) 2384 { 2385 /* This node has children on both sides. 2386 Dispatch to one side or the other 2387 by comparing the index value with this node's value. 2388 If one subtree is bounded, check that one first, 2389 so we can avoid real branches in the tree. */ 2390 2391 if (node_is_bounded (node->right, index_type)) 2392 { 2393 probability 2394 = conditional_probability (node->right->prob, 2395 subtree_prob + default_prob); 2396 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, 2397 node->right->case_bb, probability, 2398 phi_mapping, loc); 2399 bb = emit_case_nodes (bb, index, node->left, default_bb, 2400 default_label, default_prob, index_type, 2401 phi_mapping, loc); 2402 } 2403 2404 else if (node_is_bounded (node->left, index_type)) 2405 { 2406 probability 2407 = conditional_probability (node->left->prob, 2408 subtree_prob + default_prob); 2409 bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR, 2410 node->left->case_bb, probability, 2411 phi_mapping, loc); 2412 bb = emit_case_nodes (bb, index, node->right, default_bb, 2413 default_label, default_prob, index_type, 2414 phi_mapping, loc); 2415 } 2416 2417 /* If both children are single-valued cases with no 2418 children, finish up all the work. This way, we can save 2419 one ordered comparison. */ 2420 else if (tree_int_cst_equal (node->right->low, node->right->high) 2421 && node->right->left == 0 && node->right->right == 0 2422 && tree_int_cst_equal (node->left->low, node->left->high) 2423 && node->left->left == 0 && node->left->right == 0) 2424 { 2425 /* Neither node is bounded. First distinguish the two sides; 2426 then emit the code for one side at a time. */ 2427 2428 /* See if the value matches what the right hand side 2429 wants. */ 2430 probability 2431 = conditional_probability (node->right->prob, 2432 subtree_prob + default_prob); 2433 bb = do_jump_if_equal (bb, index, node->right->low, 2434 node->right->case_bb, probability, 2435 phi_mapping, loc); 2436 2437 /* See if the value matches what the left hand side 2438 wants. */ 2439 probability 2440 = conditional_probability (node->left->prob, 2441 subtree_prob + default_prob); 2442 bb = do_jump_if_equal (bb, index, node->left->low, 2443 node->left->case_bb, probability, 2444 phi_mapping, loc); 2445 } 2446 2447 else 2448 { 2449 /* Neither node is bounded. First distinguish the two sides; 2450 then emit the code for one side at a time. */ 2451 2452 basic_block test_bb = split_edge (single_succ_edge (bb)); 2453 redirect_edge_succ (single_pred_edge (test_bb), 2454 single_succ_edge (bb)->dest); 2455 2456 /* The default label could be reached either through the right 2457 subtree or the left subtree. Divide the probability 2458 equally. */ 2459 probability 2460 = conditional_probability (node->right->subtree_prob 2461 + default_prob.apply_scale (1, 2), 2462 subtree_prob + default_prob); 2463 /* See if the value is on the right. */ 2464 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, 2465 test_bb, probability, phi_mapping, 2466 loc); 2467 default_prob = default_prob.apply_scale (1, 2); 2468 2469 /* Value must be on the left. 2470 Handle the left-hand subtree. */ 2471 bb = emit_case_nodes (bb, index, node->left, default_bb, 2472 default_label, default_prob, index_type, 2473 phi_mapping, loc); 2474 /* If left-hand subtree does nothing, 2475 go to default. */ 2476 2477 if (bb && default_bb) 2478 emit_jump (bb, default_bb, phi_mapping); 2479 2480 /* Code branches here for the right-hand subtree. */ 2481 bb = emit_case_nodes (test_bb, index, node->right, default_bb, 2482 default_label, default_prob, index_type, 2483 phi_mapping, loc); 2484 } 2485 } 2486 else if (node->right != 0 && node->left == 0) 2487 { 2488 /* Here we have a right child but no left so we issue a conditional 2489 branch to default and process the right child. 2490 2491 Omit the conditional branch to default if the right child 2492 does not have any children and is single valued; it would 2493 cost too much space to save so little time. */ 2494 2495 if (node->right->right || node->right->left 2496 || !tree_int_cst_equal (node->right->low, node->right->high)) 2497 { 2498 if (!node_has_low_bound (node, index_type)) 2499 { 2500 probability 2501 = conditional_probability (default_prob.apply_scale (1, 2), 2502 subtree_prob + default_prob); 2503 bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR, 2504 default_bb, probability, 2505 phi_mapping, loc); 2506 default_prob = default_prob.apply_scale (1, 2); 2507 } 2508 2509 bb = emit_case_nodes (bb, index, node->right, default_bb, 2510 default_label, default_prob, index_type, 2511 phi_mapping, loc); 2512 } 2513 else 2514 { 2515 probability 2516 = conditional_probability (node->right->subtree_prob, 2517 subtree_prob + default_prob); 2518 /* We cannot process node->right normally 2519 since we haven't ruled out the numbers less than 2520 this node's value. So handle node->right explicitly. */ 2521 bb = do_jump_if_equal (bb, index, node->right->low, 2522 node->right->case_bb, probability, 2523 phi_mapping, loc); 2524 } 2525 } 2526 2527 else if (node->right == 0 && node->left != 0) 2528 { 2529 /* Just one subtree, on the left. */ 2530 if (node->left->left || node->left->right 2531 || !tree_int_cst_equal (node->left->low, node->left->high)) 2532 { 2533 if (!node_has_high_bound (node, index_type)) 2534 { 2535 probability 2536 = conditional_probability (default_prob.apply_scale (1, 2), 2537 subtree_prob + default_prob); 2538 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, 2539 default_bb, probability, 2540 phi_mapping, loc); 2541 default_prob = default_prob.apply_scale (1, 2); 2542 } 2543 2544 bb = emit_case_nodes (bb, index, node->left, default_bb, 2545 default_label, default_prob, index_type, 2546 phi_mapping, loc); 2547 } 2548 else 2549 { 2550 probability 2551 = conditional_probability (node->left->subtree_prob, 2552 subtree_prob + default_prob); 2553 /* We cannot process node->left normally 2554 since we haven't ruled out the numbers less than 2555 this node's value. So handle node->left explicitly. */ 2556 do_jump_if_equal (bb, index, node->left->low, node->left->case_bb, 2557 probability, phi_mapping, loc); 2558 } 2559 } 2560 } 2561 else 2562 { 2563 /* Node is a range. These cases are very similar to those for a single 2564 value, except that we do not start by testing whether this node 2565 is the one to branch to. */ 2566 2567 if (node->right != 0 && node->left != 0) 2568 { 2569 /* Node has subtrees on both sides. 2570 If the right-hand subtree is bounded, 2571 test for it first, since we can go straight there. 2572 Otherwise, we need to make a branch in the control structure, 2573 then handle the two subtrees. */ 2574 basic_block test_bb = NULL; 2575 2576 if (node_is_bounded (node->right, index_type)) 2577 { 2578 /* Right hand node is fully bounded so we can eliminate any 2579 testing and branch directly to the target code. */ 2580 probability 2581 = conditional_probability (node->right->subtree_prob, 2582 subtree_prob + default_prob); 2583 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, 2584 node->right->case_bb, probability, 2585 phi_mapping, loc); 2586 } 2587 else 2588 { 2589 /* Right hand node requires testing. 2590 Branch to a label where we will handle it later. */ 2591 2592 test_bb = split_edge (single_succ_edge (bb)); 2593 redirect_edge_succ (single_pred_edge (test_bb), 2594 single_succ_edge (bb)->dest); 2595 2596 probability 2597 = conditional_probability (node->right->subtree_prob 2598 + default_prob.apply_scale (1, 2), 2599 subtree_prob + default_prob); 2600 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, 2601 test_bb, probability, phi_mapping, 2602 loc); 2603 default_prob = default_prob.apply_scale (1, 2); 2604 } 2605 2606 /* Value belongs to this node or to the left-hand subtree. */ 2607 2608 probability 2609 = conditional_probability (prob, subtree_prob + default_prob); 2610 bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR, 2611 node->case_bb, probability, 2612 phi_mapping, loc); 2613 2614 /* Handle the left-hand subtree. */ 2615 bb = emit_case_nodes (bb, index, node->left, default_bb, 2616 default_label, default_prob, index_type, 2617 phi_mapping, loc); 2618 2619 /* If right node had to be handled later, do that now. */ 2620 if (test_bb) 2621 { 2622 /* If the left-hand subtree fell through, 2623 don't let it fall into the right-hand subtree. */ 2624 if (bb && default_bb) 2625 emit_jump (bb, default_bb, phi_mapping); 2626 2627 bb = emit_case_nodes (test_bb, index, node->right, default_bb, 2628 default_label, default_prob, index_type, 2629 phi_mapping, loc); 2630 } 2631 } 2632 2633 else if (node->right != 0 && node->left == 0) 2634 { 2635 /* Deal with values to the left of this node, 2636 if they are possible. */ 2637 if (!node_has_low_bound (node, index_type)) 2638 { 2639 probability 2640 = conditional_probability (default_prob.apply_scale (1, 2), 2641 subtree_prob + default_prob); 2642 bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR, 2643 default_bb, probability, 2644 phi_mapping, loc); 2645 default_prob = default_prob.apply_scale (1, 2); 2646 } 2647 2648 /* Value belongs to this node or to the right-hand subtree. */ 2649 2650 probability 2651 = conditional_probability (prob, subtree_prob + default_prob); 2652 bb = emit_cmp_and_jump_insns (bb, index, node->high, LE_EXPR, 2653 node->case_bb, probability, 2654 phi_mapping, loc); 2655 2656 bb = emit_case_nodes (bb, index, node->right, default_bb, 2657 default_label, default_prob, index_type, 2658 phi_mapping, loc); 2659 } 2660 2661 else if (node->right == 0 && node->left != 0) 2662 { 2663 /* Deal with values to the right of this node, 2664 if they are possible. */ 2665 if (!node_has_high_bound (node, index_type)) 2666 { 2667 probability 2668 = conditional_probability (default_prob.apply_scale (1, 2), 2669 subtree_prob + default_prob); 2670 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, 2671 default_bb, probability, 2672 phi_mapping, loc); 2673 default_prob = default_prob.apply_scale (1, 2); 2674 } 2675 2676 /* Value belongs to this node or to the left-hand subtree. */ 2677 2678 probability 2679 = conditional_probability (prob, subtree_prob + default_prob); 2680 bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR, 2681 node->case_bb, probability, 2682 phi_mapping, loc); 2683 2684 bb = emit_case_nodes (bb, index, node->left, default_bb, 2685 default_label, default_prob, index_type, 2686 phi_mapping, loc); 2687 } 2688 2689 else 2690 { 2691 /* Node has no children so we check low and high bounds to remove 2692 redundant tests. Only one of the bounds can exist, 2693 since otherwise this node is bounded--a case tested already. */ 2694 bool high_bound = node_has_high_bound (node, index_type); 2695 bool low_bound = node_has_low_bound (node, index_type); 2696 2697 if (!high_bound && low_bound) 2698 { 2699 probability 2700 = conditional_probability (default_prob, 2701 subtree_prob + default_prob); 2702 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR, 2703 default_bb, probability, 2704 phi_mapping, loc); 2705 } 2706 2707 else if (!low_bound && high_bound) 2708 { 2709 probability 2710 = conditional_probability (default_prob, 2711 subtree_prob + default_prob); 2712 bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR, 2713 default_bb, probability, 2714 phi_mapping, loc); 2715 } 2716 else if (!low_bound && !high_bound) 2717 { 2718 tree lhs, rhs; 2719 generate_range_test (bb, index, node->low, node->high, 2720 &lhs, &rhs); 2721 probability 2722 = conditional_probability (default_prob, 2723 subtree_prob + default_prob); 2724 bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR, 2725 default_bb, probability, 2726 phi_mapping, loc); 2727 } 2728 2729 emit_jump (bb, node->case_bb, phi_mapping); 2730 return NULL; 2731 } 2732 } 2733 2734 return bb; 2735 } 2736 2737 /* Search the parent sections of the case node tree 2738 to see if a test for the lower bound of NODE would be redundant. 2739 INDEX_TYPE is the type of the index expression. 2740 2741 The instructions to generate the case decision tree are 2742 output in the same order as nodes are processed so it is 2743 known that if a parent node checks the range of the current 2744 node minus one that the current node is bounded at its lower 2745 span. Thus the test would be redundant. */ 2746 2747 static bool 2748 node_has_low_bound (case_node_ptr node, tree index_type) 2749 { 2750 tree low_minus_one; 2751 case_node_ptr pnode; 2752 2753 /* If the lower bound of this node is the lowest value in the index type, 2754 we need not test it. */ 2755 2756 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type))) 2757 return true; 2758 2759 /* If this node has a left branch, the value at the left must be less 2760 than that at this node, so it cannot be bounded at the bottom and 2761 we need not bother testing any further. */ 2762 2763 if (node->left) 2764 return false; 2765 2766 low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), node->low, 2767 build_int_cst (TREE_TYPE (node->low), 1)); 2768 2769 /* If the subtraction above overflowed, we can't verify anything. 2770 Otherwise, look for a parent that tests our value - 1. */ 2771 2772 if (!tree_int_cst_lt (low_minus_one, node->low)) 2773 return false; 2774 2775 for (pnode = node->parent; pnode; pnode = pnode->parent) 2776 if (tree_int_cst_equal (low_minus_one, pnode->high)) 2777 return true; 2778 2779 return false; 2780 } 2781 2782 /* Search the parent sections of the case node tree 2783 to see if a test for the upper bound of NODE would be redundant. 2784 INDEX_TYPE is the type of the index expression. 2785 2786 The instructions to generate the case decision tree are 2787 output in the same order as nodes are processed so it is 2788 known that if a parent node checks the range of the current 2789 node plus one that the current node is bounded at its upper 2790 span. Thus the test would be redundant. */ 2791 2792 static bool 2793 node_has_high_bound (case_node_ptr node, tree index_type) 2794 { 2795 tree high_plus_one; 2796 case_node_ptr pnode; 2797 2798 /* If there is no upper bound, obviously no test is needed. */ 2799 2800 if (TYPE_MAX_VALUE (index_type) == NULL) 2801 return true; 2802 2803 /* If the upper bound of this node is the highest value in the type 2804 of the index expression, we need not test against it. */ 2805 2806 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type))) 2807 return true; 2808 2809 /* If this node has a right branch, the value at the right must be greater 2810 than that at this node, so it cannot be bounded at the top and 2811 we need not bother testing any further. */ 2812 2813 if (node->right) 2814 return false; 2815 2816 high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), node->high, 2817 build_int_cst (TREE_TYPE (node->high), 1)); 2818 2819 /* If the addition above overflowed, we can't verify anything. 2820 Otherwise, look for a parent that tests our value + 1. */ 2821 2822 if (!tree_int_cst_lt (node->high, high_plus_one)) 2823 return false; 2824 2825 for (pnode = node->parent; pnode; pnode = pnode->parent) 2826 if (tree_int_cst_equal (high_plus_one, pnode->low)) 2827 return true; 2828 2829 return false; 2830 } 2831 2832 /* Search the parent sections of the 2833 case node tree to see if both tests for the upper and lower 2834 bounds of NODE would be redundant. */ 2835 2836 static bool 2837 node_is_bounded (case_node_ptr node, tree index_type) 2838 { 2839 return (node_has_low_bound (node, index_type) 2840 && node_has_high_bound (node, index_type)); 2841 } 2842