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