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 e = single_succ_edge (label_bb); 287 following_bb = single_succ (label_bb); 288 } 289 290 if (!info.final_bb) 291 info.final_bb = following_bb; 292 else if (info.final_bb != following_bb) 293 { 294 info.reason = " Bad case - different final BB\n"; 295 return false; /* the only successor is not common for all the branches */ 296 } 297 298 return true; 299 } 300 301 /* This function checks whether all required values in phi nodes in final_bb 302 are constants. Required values are those that correspond to a basic block 303 which is a part of the examined switch statement. It returns true if the 304 phi nodes are OK, otherwise false. */ 305 306 static bool 307 check_final_bb (void) 308 { 309 gimple_stmt_iterator gsi; 310 311 info.phi_count = 0; 312 for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) 313 { 314 gimple phi = gsi_stmt (gsi); 315 unsigned int i; 316 317 info.phi_count++; 318 319 for (i = 0; i < gimple_phi_num_args (phi); i++) 320 { 321 basic_block bb = gimple_phi_arg_edge (phi, i)->src; 322 323 if (bb == info.switch_bb 324 || (single_pred_p (bb) && single_pred (bb) == info.switch_bb)) 325 { 326 tree reloc, val; 327 328 val = gimple_phi_arg_def (phi, i); 329 if (!is_gimple_ip_invariant (val)) 330 { 331 info.reason = " Non-invariant value from a case\n"; 332 return false; /* Non-invariant argument. */ 333 } 334 reloc = initializer_constant_valid_p (val, TREE_TYPE (val)); 335 if ((flag_pic && reloc != null_pointer_node) 336 || (!flag_pic && reloc == NULL_TREE)) 337 { 338 if (reloc) 339 info.reason 340 = " Value from a case would need runtime relocations\n"; 341 else 342 info.reason 343 = " Value from a case is not a valid initializer\n"; 344 return false; 345 } 346 } 347 } 348 } 349 350 return true; 351 } 352 353 /* The following function allocates default_values, target_{in,out}_names and 354 constructors arrays. The last one is also populated with pointers to 355 vectors that will become constructors of new arrays. */ 356 357 static void 358 create_temp_arrays (void) 359 { 360 int i; 361 362 info.default_values = XCNEWVEC (tree, info.phi_count * 3); 363 info.constructors = XCNEWVEC (VEC (constructor_elt, gc) *, info.phi_count); 364 info.target_inbound_names = info.default_values + info.phi_count; 365 info.target_outbound_names = info.target_inbound_names + info.phi_count; 366 for (i = 0; i < info.phi_count; i++) 367 info.constructors[i] 368 = VEC_alloc (constructor_elt, gc, tree_low_cst (info.range_size, 1) + 1); 369 } 370 371 /* Free the arrays created by create_temp_arrays(). The vectors that are 372 created by that function are not freed here, however, because they have 373 already become constructors and must be preserved. */ 374 375 static void 376 free_temp_arrays (void) 377 { 378 XDELETEVEC (info.constructors); 379 XDELETEVEC (info.default_values); 380 } 381 382 /* Populate the array of default values in the order of phi nodes. 383 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */ 384 385 static void 386 gather_default_values (tree default_case) 387 { 388 gimple_stmt_iterator gsi; 389 basic_block bb = label_to_block (CASE_LABEL (default_case)); 390 edge e; 391 int i = 0; 392 393 gcc_assert (CASE_LOW (default_case) == NULL_TREE); 394 395 if (bb == info.final_bb) 396 e = find_edge (info.switch_bb, bb); 397 else 398 e = single_succ_edge (bb); 399 400 for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) 401 { 402 gimple phi = gsi_stmt (gsi); 403 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); 404 gcc_assert (val); 405 info.default_values[i++] = val; 406 } 407 } 408 409 /* The following function populates the vectors in the constructors array with 410 future contents of the static arrays. The vectors are populated in the 411 order of phi nodes. SWTCH is the switch statement being converted. */ 412 413 static void 414 build_constructors (gimple swtch) 415 { 416 unsigned i, branch_num = gimple_switch_num_labels (swtch); 417 tree pos = info.range_min; 418 419 for (i = 1; i < branch_num; i++) 420 { 421 tree cs = gimple_switch_label (swtch, i); 422 basic_block bb = label_to_block (CASE_LABEL (cs)); 423 edge e; 424 tree high; 425 gimple_stmt_iterator gsi; 426 int j; 427 428 if (bb == info.final_bb) 429 e = find_edge (info.switch_bb, bb); 430 else 431 e = single_succ_edge (bb); 432 gcc_assert (e); 433 434 while (tree_int_cst_lt (pos, CASE_LOW (cs))) 435 { 436 int k; 437 for (k = 0; k < info.phi_count; k++) 438 { 439 constructor_elt *elt; 440 441 elt = VEC_quick_push (constructor_elt, 442 info.constructors[k], NULL); 443 elt->index = int_const_binop (MINUS_EXPR, pos, 444 info.range_min); 445 elt->value = info.default_values[k]; 446 } 447 448 pos = int_const_binop (PLUS_EXPR, pos, integer_one_node); 449 } 450 gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs))); 451 452 j = 0; 453 if (CASE_HIGH (cs)) 454 high = CASE_HIGH (cs); 455 else 456 high = CASE_LOW (cs); 457 for (gsi = gsi_start_phis (info.final_bb); 458 !gsi_end_p (gsi); gsi_next (&gsi)) 459 { 460 gimple phi = gsi_stmt (gsi); 461 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); 462 tree low = CASE_LOW (cs); 463 pos = CASE_LOW (cs); 464 465 do 466 { 467 constructor_elt *elt; 468 469 elt = VEC_quick_push (constructor_elt, 470 info.constructors[j], NULL); 471 elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min); 472 elt->value = val; 473 474 pos = int_const_binop (PLUS_EXPR, pos, integer_one_node); 475 } while (!tree_int_cst_lt (high, pos) 476 && tree_int_cst_lt (low, pos)); 477 j++; 478 } 479 } 480 } 481 482 /* If all values in the constructor vector are the same, return the value. 483 Otherwise return NULL_TREE. Not supposed to be called for empty 484 vectors. */ 485 486 static tree 487 constructor_contains_same_values_p (VEC (constructor_elt, gc) *vec) 488 { 489 unsigned int i; 490 tree prev = NULL_TREE; 491 constructor_elt *elt; 492 493 FOR_EACH_VEC_ELT (constructor_elt, vec, i, elt) 494 { 495 if (!prev) 496 prev = elt->value; 497 else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST)) 498 return NULL_TREE; 499 } 500 return prev; 501 } 502 503 /* Return type which should be used for array elements, either TYPE, 504 or for integral type some smaller integral type that can still hold 505 all the constants. */ 506 507 static tree 508 array_value_type (gimple swtch, tree type, int num) 509 { 510 unsigned int i, len = VEC_length (constructor_elt, info.constructors[num]); 511 constructor_elt *elt; 512 enum machine_mode mode; 513 int sign = 0; 514 tree smaller_type; 515 516 if (!INTEGRAL_TYPE_P (type)) 517 return type; 518 519 mode = GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type))); 520 if (GET_MODE_SIZE (TYPE_MODE (type)) <= GET_MODE_SIZE (mode)) 521 return type; 522 523 if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32)) 524 return type; 525 526 FOR_EACH_VEC_ELT (constructor_elt, info.constructors[num], i, elt) 527 { 528 double_int cst; 529 530 if (TREE_CODE (elt->value) != INTEGER_CST) 531 return type; 532 533 cst = TREE_INT_CST (elt->value); 534 while (1) 535 { 536 unsigned int prec = GET_MODE_BITSIZE (mode); 537 if (prec > HOST_BITS_PER_WIDE_INT) 538 return type; 539 540 if (sign >= 0 541 && double_int_equal_p (cst, double_int_zext (cst, prec))) 542 { 543 if (sign == 0 544 && double_int_equal_p (cst, double_int_sext (cst, prec))) 545 break; 546 sign = 1; 547 break; 548 } 549 if (sign <= 0 550 && double_int_equal_p (cst, double_int_sext (cst, prec))) 551 { 552 sign = -1; 553 break; 554 } 555 556 if (sign == 1) 557 sign = 0; 558 559 mode = GET_MODE_WIDER_MODE (mode); 560 if (mode == VOIDmode 561 || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (TYPE_MODE (type))) 562 return type; 563 } 564 } 565 566 if (sign == 0) 567 sign = TYPE_UNSIGNED (type) ? 1 : -1; 568 smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0); 569 if (GET_MODE_SIZE (TYPE_MODE (type)) 570 <= GET_MODE_SIZE (TYPE_MODE (smaller_type))) 571 return type; 572 573 return smaller_type; 574 } 575 576 /* Create an appropriate array type and declaration and assemble a static array 577 variable. Also create a load statement that initializes the variable in 578 question with a value from the static array. SWTCH is the switch statement 579 being converted, NUM is the index to arrays of constructors, default values 580 and target SSA names for this particular array. ARR_INDEX_TYPE is the type 581 of the index of the new array, PHI is the phi node of the final BB that 582 corresponds to the value that will be loaded from the created array. TIDX 583 is an ssa name of a temporary variable holding the index for loads from the 584 new array. */ 585 586 static void 587 build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi, 588 tree tidx) 589 { 590 tree name, cst; 591 gimple load; 592 gimple_stmt_iterator gsi = gsi_for_stmt (swtch); 593 location_t loc = gimple_location (swtch); 594 595 gcc_assert (info.default_values[num]); 596 597 name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL); 598 info.target_inbound_names[num] = name; 599 600 cst = constructor_contains_same_values_p (info.constructors[num]); 601 if (cst) 602 load = gimple_build_assign (name, cst); 603 else 604 { 605 tree array_type, ctor, decl, value_type, fetch, default_type; 606 607 default_type = TREE_TYPE (info.default_values[num]); 608 value_type = array_value_type (swtch, default_type, num); 609 array_type = build_array_type (value_type, arr_index_type); 610 if (default_type != value_type) 611 { 612 unsigned int i; 613 constructor_elt *elt; 614 615 FOR_EACH_VEC_ELT (constructor_elt, info.constructors[num], i, elt) 616 elt->value = fold_convert (value_type, elt->value); 617 } 618 ctor = build_constructor (array_type, info.constructors[num]); 619 TREE_CONSTANT (ctor) = true; 620 TREE_STATIC (ctor) = true; 621 622 decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type); 623 TREE_STATIC (decl) = 1; 624 DECL_INITIAL (decl) = ctor; 625 626 DECL_NAME (decl) = create_tmp_var_name ("CSWTCH"); 627 DECL_ARTIFICIAL (decl) = 1; 628 TREE_CONSTANT (decl) = 1; 629 TREE_READONLY (decl) = 1; 630 add_referenced_var (decl); 631 varpool_mark_needed_node (varpool_node (decl)); 632 varpool_finalize_decl (decl); 633 634 fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE, 635 NULL_TREE); 636 if (default_type != value_type) 637 { 638 fetch = fold_convert (default_type, fetch); 639 fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE, 640 true, GSI_SAME_STMT); 641 } 642 load = gimple_build_assign (name, fetch); 643 } 644 645 SSA_NAME_DEF_STMT (name) = load; 646 gsi_insert_before (&gsi, load, GSI_SAME_STMT); 647 update_stmt (load); 648 info.arr_ref_last = load; 649 } 650 651 /* Builds and initializes static arrays initialized with values gathered from 652 the SWTCH switch statement. Also creates statements that load values from 653 them. */ 654 655 static void 656 build_arrays (gimple swtch) 657 { 658 tree arr_index_type; 659 tree tidx, sub, tmp, utype; 660 gimple stmt; 661 gimple_stmt_iterator gsi; 662 int i; 663 location_t loc = gimple_location (swtch); 664 665 gsi = gsi_for_stmt (swtch); 666 667 /* Make sure we do not generate arithmetics in a subrange. */ 668 utype = TREE_TYPE (info.index_expr); 669 if (TREE_TYPE (utype)) 670 utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1); 671 else 672 utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1); 673 674 arr_index_type = build_index_type (info.range_size); 675 tmp = create_tmp_var (utype, "csui"); 676 add_referenced_var (tmp); 677 tidx = make_ssa_name (tmp, NULL); 678 sub = fold_build2_loc (loc, MINUS_EXPR, utype, 679 fold_convert_loc (loc, utype, info.index_expr), 680 fold_convert_loc (loc, utype, info.range_min)); 681 sub = force_gimple_operand_gsi (&gsi, sub, 682 false, NULL, true, GSI_SAME_STMT); 683 stmt = gimple_build_assign (tidx, sub); 684 SSA_NAME_DEF_STMT (tidx) = stmt; 685 686 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); 687 update_stmt (stmt); 688 info.arr_ref_first = stmt; 689 690 for (gsi = gsi_start_phis (info.final_bb), i = 0; 691 !gsi_end_p (gsi); gsi_next (&gsi), i++) 692 build_one_array (swtch, i, arr_index_type, gsi_stmt (gsi), tidx); 693 } 694 695 /* Generates and appropriately inserts loads of default values at the position 696 given by BSI. Returns the last inserted statement. */ 697 698 static gimple 699 gen_def_assigns (gimple_stmt_iterator *gsi) 700 { 701 int i; 702 gimple assign = NULL; 703 704 for (i = 0; i < info.phi_count; i++) 705 { 706 tree name 707 = make_ssa_name (SSA_NAME_VAR (info.target_inbound_names[i]), NULL); 708 709 info.target_outbound_names[i] = name; 710 assign = gimple_build_assign (name, info.default_values[i]); 711 SSA_NAME_DEF_STMT (name) = assign; 712 gsi_insert_before (gsi, assign, GSI_SAME_STMT); 713 update_stmt (assign); 714 } 715 return assign; 716 } 717 718 /* Deletes the unused bbs and edges that now contain the switch statement and 719 its empty branch bbs. BBD is the now dead BB containing the original switch 720 statement, FINAL is the last BB of the converted switch statement (in terms 721 of succession). */ 722 723 static void 724 prune_bbs (basic_block bbd, basic_block final) 725 { 726 edge_iterator ei; 727 edge e; 728 729 for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); ) 730 { 731 basic_block bb; 732 bb = e->dest; 733 remove_edge (e); 734 if (bb != final) 735 delete_basic_block (bb); 736 } 737 delete_basic_block (bbd); 738 } 739 740 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge 741 from the basic block loading values from an array and E2F from the basic 742 block loading default values. BBF is the last switch basic block (see the 743 bbf description in the comment below). */ 744 745 static void 746 fix_phi_nodes (edge e1f, edge e2f, basic_block bbf) 747 { 748 gimple_stmt_iterator gsi; 749 int i; 750 751 for (gsi = gsi_start_phis (bbf), i = 0; 752 !gsi_end_p (gsi); gsi_next (&gsi), i++) 753 { 754 gimple phi = gsi_stmt (gsi); 755 add_phi_arg (phi, info.target_inbound_names[i], e1f, UNKNOWN_LOCATION); 756 add_phi_arg (phi, info.target_outbound_names[i], e2f, UNKNOWN_LOCATION); 757 } 758 759 } 760 761 /* Creates a check whether the switch expression value actually falls into the 762 range given by all the cases. If it does not, the temporaries are loaded 763 with default values instead. SWTCH is the switch statement being converted. 764 765 bb0 is the bb with the switch statement, however, we'll end it with a 766 condition instead. 767 768 bb1 is the bb to be used when the range check went ok. It is derived from 769 the switch BB 770 771 bb2 is the bb taken when the expression evaluated outside of the range 772 covered by the created arrays. It is populated by loads of default 773 values. 774 775 bbF is a fall through for both bb1 and bb2 and contains exactly what 776 originally followed the switch statement. 777 778 bbD contains the switch statement (in the end). It is unreachable but we 779 still need to strip off its edges. 780 */ 781 782 static void 783 gen_inbound_check (gimple swtch) 784 { 785 tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION); 786 tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION); 787 tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION); 788 gimple label1, label2, label3; 789 tree utype, tidx; 790 tree bound; 791 792 gimple cond_stmt; 793 794 gimple last_assign; 795 gimple_stmt_iterator gsi; 796 basic_block bb0, bb1, bb2, bbf, bbd; 797 edge e01, e02, e21, e1d, e1f, e2f; 798 location_t loc = gimple_location (swtch); 799 800 gcc_assert (info.default_values); 801 bb0 = gimple_bb (swtch); 802 803 tidx = gimple_assign_lhs (info.arr_ref_first); 804 utype = TREE_TYPE (tidx); 805 806 /* (end of) block 0 */ 807 gsi = gsi_for_stmt (info.arr_ref_first); 808 gsi_next (&gsi); 809 810 bound = fold_convert_loc (loc, utype, info.range_size); 811 cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE); 812 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT); 813 update_stmt (cond_stmt); 814 815 /* block 2 */ 816 label2 = gimple_build_label (label_decl2); 817 gsi_insert_before (&gsi, label2, GSI_SAME_STMT); 818 last_assign = gen_def_assigns (&gsi); 819 820 /* block 1 */ 821 label1 = gimple_build_label (label_decl1); 822 gsi_insert_before (&gsi, label1, GSI_SAME_STMT); 823 824 /* block F */ 825 gsi = gsi_start_bb (info.final_bb); 826 label3 = gimple_build_label (label_decl3); 827 gsi_insert_before (&gsi, label3, GSI_SAME_STMT); 828 829 /* cfg fix */ 830 e02 = split_block (bb0, cond_stmt); 831 bb2 = e02->dest; 832 833 e21 = split_block (bb2, last_assign); 834 bb1 = e21->dest; 835 remove_edge (e21); 836 837 e1d = split_block (bb1, info.arr_ref_last); 838 bbd = e1d->dest; 839 remove_edge (e1d); 840 841 /* flags and profiles of the edge for in-range values */ 842 e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE); 843 e01->probability = REG_BR_PROB_BASE - info.default_prob; 844 e01->count = info.other_count; 845 846 /* flags and profiles of the edge taking care of out-of-range values */ 847 e02->flags &= ~EDGE_FALLTHRU; 848 e02->flags |= EDGE_FALSE_VALUE; 849 e02->probability = info.default_prob; 850 e02->count = info.default_count; 851 852 bbf = info.final_bb; 853 854 e1f = make_edge (bb1, bbf, EDGE_FALLTHRU); 855 e1f->probability = REG_BR_PROB_BASE; 856 e1f->count = info.other_count; 857 858 e2f = make_edge (bb2, bbf, EDGE_FALLTHRU); 859 e2f->probability = REG_BR_PROB_BASE; 860 e2f->count = info.default_count; 861 862 /* frequencies of the new BBs */ 863 bb1->frequency = EDGE_FREQUENCY (e01); 864 bb2->frequency = EDGE_FREQUENCY (e02); 865 bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f); 866 867 prune_bbs (bbd, info.final_bb); /* To keep calc_dfs_tree() in dominance.c 868 happy. */ 869 870 fix_phi_nodes (e1f, e2f, bbf); 871 872 free_dominance_info (CDI_DOMINATORS); 873 free_dominance_info (CDI_POST_DOMINATORS); 874 } 875 876 /* The following function is invoked on every switch statement (the current one 877 is given in SWTCH) and runs the individual phases of switch conversion on it 878 one after another until one fails or the conversion is completed. */ 879 880 static bool 881 process_switch (gimple swtch) 882 { 883 unsigned int i, branch_num = gimple_switch_num_labels (swtch); 884 tree index_type; 885 886 /* Operand 2 is either NULL_TREE or a vector of cases (stmt.c). */ 887 if (branch_num < 2) 888 { 889 info.reason = "switch has no labels\n"; 890 return false; 891 } 892 893 info.final_bb = NULL; 894 info.switch_bb = gimple_bb (swtch); 895 info.index_expr = gimple_switch_index (swtch); 896 index_type = TREE_TYPE (info.index_expr); 897 info.arr_ref_first = NULL; 898 info.arr_ref_last = NULL; 899 info.default_prob = 0; 900 info.default_count = 0; 901 info.other_count = 0; 902 info.bit_test_uniq = 0; 903 info.bit_test_count = 0; 904 info.bit_test_bb[0] = NULL; 905 info.bit_test_bb[1] = NULL; 906 907 /* An ERROR_MARK occurs for various reasons including invalid data type. 908 (comment from stmt.c) */ 909 if (index_type == error_mark_node) 910 { 911 info.reason = "index error.\n"; 912 return false; 913 } 914 915 /* Check the case label values are within reasonable range: */ 916 if (!check_range (swtch)) 917 return false; 918 919 /* For all the cases, see whether they are empty, the assignments they 920 represent constant and so on... */ 921 for (i = 0; i < branch_num; i++) 922 if (!check_process_case (gimple_switch_label (swtch, i))) 923 { 924 if (dump_file) 925 fprintf (dump_file, "Processing of case %i failed\n", i); 926 return false; 927 } 928 929 if (info.bit_test_uniq <= 2) 930 { 931 rtl_profile_for_bb (gimple_bb (swtch)); 932 if (expand_switch_using_bit_tests_p (gimple_switch_index (swtch), 933 info.range_size, info.bit_test_uniq, 934 info.bit_test_count)) 935 { 936 info.reason = " Expanding as bit test is preferable\n"; 937 return false; 938 } 939 } 940 941 if (!check_final_bb ()) 942 return false; 943 944 /* At this point all checks have passed and we can proceed with the 945 transformation. */ 946 947 create_temp_arrays (); 948 gather_default_values (gimple_switch_label (swtch, 0)); 949 build_constructors (swtch); 950 951 build_arrays (swtch); /* Build the static arrays and assignments. */ 952 gen_inbound_check (swtch); /* Build the bounds check. */ 953 954 /* Cleanup: */ 955 free_temp_arrays (); 956 return true; 957 } 958 959 /* The main function of the pass scans statements for switches and invokes 960 process_switch on them. */ 961 962 static unsigned int 963 do_switchconv (void) 964 { 965 basic_block bb; 966 967 FOR_EACH_BB (bb) 968 { 969 gimple stmt = last_stmt (bb); 970 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) 971 { 972 if (dump_file) 973 { 974 expanded_location loc = expand_location (gimple_location (stmt)); 975 976 fprintf (dump_file, "beginning to process the following " 977 "SWITCH statement (%s:%d) : ------- \n", 978 loc.file, loc.line); 979 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 980 putc ('\n', dump_file); 981 } 982 983 info.reason = NULL; 984 if (process_switch (stmt)) 985 { 986 if (dump_file) 987 { 988 fputs ("Switch converted\n", dump_file); 989 fputs ("--------------------------------\n", dump_file); 990 } 991 } 992 else 993 { 994 if (dump_file) 995 { 996 gcc_assert (info.reason); 997 fputs ("Bailing out - ", dump_file); 998 fputs (info.reason, dump_file); 999 fputs ("--------------------------------\n", dump_file); 1000 } 1001 } 1002 } 1003 } 1004 1005 return 0; 1006 } 1007 1008 /* The pass gate. */ 1009 1010 static bool 1011 switchconv_gate (void) 1012 { 1013 return flag_tree_switch_conversion != 0; 1014 } 1015 1016 struct gimple_opt_pass pass_convert_switch = 1017 { 1018 { 1019 GIMPLE_PASS, 1020 "switchconv", /* name */ 1021 switchconv_gate, /* gate */ 1022 do_switchconv, /* execute */ 1023 NULL, /* sub */ 1024 NULL, /* next */ 1025 0, /* static_pass_number */ 1026 TV_TREE_SWITCH_CONVERSION, /* tv_id */ 1027 PROP_cfg | PROP_ssa, /* properties_required */ 1028 0, /* properties_provided */ 1029 0, /* properties_destroyed */ 1030 0, /* todo_flags_start */ 1031 TODO_update_ssa 1032 | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ 1033 } 1034 }; 1035