Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-switch-conversion.c @ 63:b7f97abdc517 gcc-4.6-20100522
update gcc from gcc-4.5.0 to gcc-4.6
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 24 May 2010 12:47:05 +0900 |
| parents | 77e2b8dfacca |
| children | f6334be47118 |
| rev | line source |
|---|---|
| 0 | 1 /* Switch Conversion converts variable initializations based on switch |
| 2 statements to initializations from a static array. | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
3 Copyright (C) 2006, 2008, 2009, 2010 Free Software Foundation, Inc. |
| 0 | 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 <signal.h> | |
| 84 | |
| 85 #include "line-map.h" | |
| 86 #include "params.h" | |
| 87 #include "flags.h" | |
| 88 #include "tree.h" | |
| 89 #include "basic-block.h" | |
| 90 #include "tree-flow.h" | |
| 91 #include "tree-flow-inline.h" | |
| 92 #include "tree-ssa-operands.h" | |
| 93 #include "output.h" | |
| 94 #include "input.h" | |
| 95 #include "tree-pass.h" | |
| 96 #include "diagnostic.h" | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
97 #include "gimple-pretty-print.h" |
| 0 | 98 #include "tree-dump.h" |
| 99 #include "timevar.h" | |
| 100 | |
| 101 /* The main structure of the pass. */ | |
| 102 struct switch_conv_info | |
| 103 { | |
| 104 /* The expression used to decide the switch branch. (It is subsequently used | |
| 105 as the index to the created array.) */ | |
| 106 tree index_expr; | |
| 107 | |
| 108 /* The following integer constants store the minimum value covered by the | |
| 109 cases. */ | |
| 110 tree range_min; | |
| 111 | |
| 112 /* The difference between the above two numbers, i.e. The size of the array | |
| 113 that would have to be created by the transformation. */ | |
| 114 tree range_size; | |
| 115 | |
| 116 /* Basic block that contains the actual SWITCH_EXPR. */ | |
| 117 basic_block switch_bb; | |
| 118 | |
| 119 /* All branches of the switch statement must have a single successor stored in | |
| 120 the following variable. */ | |
| 121 basic_block final_bb; | |
| 122 | |
| 123 /* Number of phi nodes in the final bb (that we'll be replacing). */ | |
| 124 int phi_count; | |
| 125 | |
| 126 /* Array of default values, in the same order as phi nodes. */ | |
| 127 tree *default_values; | |
| 128 | |
| 129 /* Constructors of new static arrays. */ | |
| 130 VEC (constructor_elt, gc) **constructors; | |
| 131 | |
| 132 /* Array of ssa names that are initialized with a value from a new static | |
| 133 array. */ | |
| 134 tree *target_inbound_names; | |
| 135 | |
| 136 /* Array of ssa names that are initialized with the default value if the | |
| 137 switch expression is out of range. */ | |
| 138 tree *target_outbound_names; | |
| 139 | |
| 140 /* The probability of the default edge in the replaced switch. */ | |
| 141 int default_prob; | |
| 142 | |
| 143 /* The count of the default edge in the replaced switch. */ | |
| 144 gcov_type default_count; | |
| 145 | |
| 146 /* Combined count of all other (non-default) edges in the replaced switch. */ | |
| 147 gcov_type other_count; | |
| 148 | |
| 149 /* The first load statement that loads a temporary from a new static array. | |
| 150 */ | |
| 151 gimple arr_ref_first; | |
| 152 | |
| 153 /* The last load statement that loads a temporary from a new static array. */ | |
| 154 gimple arr_ref_last; | |
| 155 | |
| 156 /* String reason why the case wasn't a good candidate that is written to the | |
| 157 dump file, if there is one. */ | |
| 158 const char *reason; | |
| 159 }; | |
| 160 | |
| 161 /* Global pass info. */ | |
| 162 static struct switch_conv_info info; | |
| 163 | |
| 164 | |
| 165 /* Checks whether the range given by individual case statements of the SWTCH | |
| 166 switch statement isn't too big and whether the number of branches actually | |
| 167 satisfies the size of the new array. */ | |
| 168 | |
| 169 static bool | |
| 170 check_range (gimple swtch) | |
| 171 { | |
| 172 tree min_case, max_case; | |
| 173 unsigned int branch_num = gimple_switch_num_labels (swtch); | |
| 174 tree range_max; | |
| 175 | |
| 176 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there | |
| 177 is a default label which is the last in the vector. */ | |
| 178 | |
| 179 min_case = gimple_switch_label (swtch, 1); | |
| 180 info.range_min = CASE_LOW (min_case); | |
| 181 | |
| 182 gcc_assert (branch_num > 1); | |
| 183 gcc_assert (CASE_LOW (gimple_switch_label (swtch, 0)) == NULL_TREE); | |
| 184 max_case = gimple_switch_label (swtch, branch_num - 1); | |
| 185 if (CASE_HIGH (max_case) != NULL_TREE) | |
| 186 range_max = CASE_HIGH (max_case); | |
| 187 else | |
| 188 range_max = CASE_LOW (max_case); | |
| 189 | |
| 190 gcc_assert (info.range_min); | |
| 191 gcc_assert (range_max); | |
| 192 | |
| 193 info.range_size = int_const_binop (MINUS_EXPR, range_max, info.range_min, 0); | |
| 194 | |
| 195 gcc_assert (info.range_size); | |
| 196 if (!host_integerp (info.range_size, 1)) | |
| 197 { | |
| 198 info.reason = "index range way too large or otherwise unusable.\n"; | |
| 199 return false; | |
| 200 } | |
| 201 | |
| 202 if ((unsigned HOST_WIDE_INT) tree_low_cst (info.range_size, 1) | |
| 203 > ((unsigned) branch_num * SWITCH_CONVERSION_BRANCH_RATIO)) | |
| 204 { | |
| 205 info.reason = "the maximum range-branch ratio exceeded.\n"; | |
| 206 return false; | |
| 207 } | |
| 208 | |
| 209 return true; | |
| 210 } | |
| 211 | |
| 212 /* Checks the given CS switch case whether it is suitable for conversion | |
| 213 (whether all but the default basic blocks are empty and so on). If it is, | |
| 214 adds the case to the branch list along with values for the defined variables | |
| 215 and returns true. Otherwise returns false. */ | |
| 216 | |
| 217 static bool | |
| 218 check_process_case (tree cs) | |
| 219 { | |
| 220 tree ldecl; | |
| 221 basic_block label_bb, following_bb; | |
| 222 edge e; | |
| 223 | |
| 224 ldecl = CASE_LABEL (cs); | |
| 225 label_bb = label_to_block (ldecl); | |
| 226 | |
| 227 e = find_edge (info.switch_bb, label_bb); | |
| 228 gcc_assert (e); | |
| 229 | |
| 230 if (CASE_LOW (cs) == NULL_TREE) | |
| 231 { | |
| 232 /* Default branch. */ | |
| 233 info.default_prob = e->probability; | |
| 234 info.default_count = e->count; | |
| 235 } | |
| 236 else | |
| 237 info.other_count += e->count; | |
| 238 | |
| 239 if (!label_bb) | |
| 240 { | |
| 241 info.reason = " Bad case - cs BB label is NULL\n"; | |
| 242 return false; | |
| 243 } | |
| 244 | |
| 245 if (!single_pred_p (label_bb)) | |
| 246 { | |
| 247 if (info.final_bb && info.final_bb != label_bb) | |
| 248 { | |
| 249 info.reason = " Bad case - a non-final BB has two predecessors\n"; | |
| 250 return false; /* sth complex going on in this branch */ | |
| 251 } | |
| 252 | |
| 253 following_bb = label_bb; | |
| 254 } | |
| 255 else | |
| 256 { | |
| 257 if (!empty_block_p (label_bb)) | |
| 258 { | |
| 259 info.reason = " Bad case - a non-final BB not empty\n"; | |
| 260 return false; | |
| 261 } | |
| 262 | |
| 263 e = single_succ_edge (label_bb); | |
| 264 following_bb = single_succ (label_bb); | |
| 265 } | |
| 266 | |
| 267 if (!info.final_bb) | |
| 268 info.final_bb = following_bb; | |
| 269 else if (info.final_bb != following_bb) | |
| 270 { | |
| 271 info.reason = " Bad case - different final BB\n"; | |
| 272 return false; /* the only successor is not common for all the branches */ | |
| 273 } | |
| 274 | |
| 275 return true; | |
| 276 } | |
| 277 | |
| 278 /* This function checks whether all required values in phi nodes in final_bb | |
| 279 are constants. Required values are those that correspond to a basic block | |
| 280 which is a part of the examined switch statement. It returns true if the | |
| 281 phi nodes are OK, otherwise false. */ | |
| 282 | |
| 283 static bool | |
| 284 check_final_bb (void) | |
| 285 { | |
| 286 gimple_stmt_iterator gsi; | |
| 287 | |
| 288 info.phi_count = 0; | |
| 289 for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 290 { | |
| 291 gimple phi = gsi_stmt (gsi); | |
| 292 unsigned int i; | |
| 293 | |
| 294 info.phi_count++; | |
| 295 | |
| 296 for (i = 0; i < gimple_phi_num_args (phi); i++) | |
| 297 { | |
| 298 basic_block bb = gimple_phi_arg_edge (phi, i)->src; | |
| 299 | |
| 300 if (bb == info.switch_bb | |
| 301 || (single_pred_p (bb) && single_pred (bb) == info.switch_bb)) | |
| 302 { | |
| 303 tree reloc, val; | |
| 304 | |
| 305 val = gimple_phi_arg_def (phi, i); | |
| 306 if (!is_gimple_ip_invariant (val)) | |
| 307 { | |
| 308 info.reason = " Non-invariant value from a case\n"; | |
| 309 return false; /* Non-invariant argument. */ | |
| 310 } | |
| 311 reloc = initializer_constant_valid_p (val, TREE_TYPE (val)); | |
| 312 if ((flag_pic && reloc != null_pointer_node) | |
| 313 || (!flag_pic && reloc == NULL_TREE)) | |
| 314 { | |
| 315 if (reloc) | |
| 316 info.reason | |
| 317 = " Value from a case would need runtime relocations\n"; | |
| 318 else | |
| 319 info.reason | |
| 320 = " Value from a case is not a valid initializer\n"; | |
| 321 return false; | |
| 322 } | |
| 323 } | |
| 324 } | |
| 325 } | |
| 326 | |
| 327 return true; | |
| 328 } | |
| 329 | |
| 330 /* The following function allocates default_values, target_{in,out}_names and | |
| 331 constructors arrays. The last one is also populated with pointers to | |
| 332 vectors that will become constructors of new arrays. */ | |
| 333 | |
| 334 static void | |
| 335 create_temp_arrays (void) | |
| 336 { | |
| 337 int i; | |
| 338 | |
| 339 info.default_values = (tree *) xcalloc (info.phi_count, sizeof (tree)); | |
| 340 info.constructors = (VEC (constructor_elt, gc) **) xcalloc (info.phi_count, | |
| 341 sizeof (tree)); | |
| 342 info.target_inbound_names = (tree *) xcalloc (info.phi_count, sizeof (tree)); | |
| 343 info.target_outbound_names = (tree *) xcalloc (info.phi_count, | |
| 344 sizeof (tree)); | |
| 345 | |
| 346 for (i = 0; i < info.phi_count; i++) | |
| 347 info.constructors[i] | |
| 348 = VEC_alloc (constructor_elt, gc, tree_low_cst (info.range_size, 1) + 1); | |
| 349 } | |
| 350 | |
| 351 /* Free the arrays created by create_temp_arrays(). The vectors that are | |
| 352 created by that function are not freed here, however, because they have | |
| 353 already become constructors and must be preserved. */ | |
| 354 | |
| 355 static void | |
| 356 free_temp_arrays (void) | |
| 357 { | |
| 358 free (info.constructors); | |
| 359 free (info.default_values); | |
| 360 free (info.target_inbound_names); | |
| 361 free (info.target_outbound_names); | |
| 362 } | |
| 363 | |
| 364 /* Populate the array of default values in the order of phi nodes. | |
| 365 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */ | |
| 366 | |
| 367 static void | |
| 368 gather_default_values (tree default_case) | |
| 369 { | |
| 370 gimple_stmt_iterator gsi; | |
| 371 basic_block bb = label_to_block (CASE_LABEL (default_case)); | |
| 372 edge e; | |
| 373 int i = 0; | |
| 374 | |
| 375 gcc_assert (CASE_LOW (default_case) == NULL_TREE); | |
| 376 | |
| 377 if (bb == info.final_bb) | |
| 378 e = find_edge (info.switch_bb, bb); | |
| 379 else | |
| 380 e = single_succ_edge (bb); | |
| 381 | |
| 382 for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 383 { | |
| 384 gimple phi = gsi_stmt (gsi); | |
| 385 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); | |
| 386 gcc_assert (val); | |
| 387 info.default_values[i++] = val; | |
| 388 } | |
| 389 } | |
| 390 | |
| 391 /* The following function populates the vectors in the constructors array with | |
| 392 future contents of the static arrays. The vectors are populated in the | |
| 393 order of phi nodes. SWTCH is the switch statement being converted. */ | |
| 394 | |
| 395 static void | |
| 396 build_constructors (gimple swtch) | |
| 397 { | |
| 398 unsigned i, branch_num = gimple_switch_num_labels (swtch); | |
| 399 tree pos = info.range_min; | |
| 400 | |
| 401 for (i = 1; i < branch_num; i++) | |
| 402 { | |
| 403 tree cs = gimple_switch_label (swtch, i); | |
| 404 basic_block bb = label_to_block (CASE_LABEL (cs)); | |
| 405 edge e; | |
| 406 tree high; | |
| 407 gimple_stmt_iterator gsi; | |
| 408 int j; | |
| 409 | |
| 410 if (bb == info.final_bb) | |
| 411 e = find_edge (info.switch_bb, bb); | |
| 412 else | |
| 413 e = single_succ_edge (bb); | |
| 414 gcc_assert (e); | |
| 415 | |
| 416 while (tree_int_cst_lt (pos, CASE_LOW (cs))) | |
| 417 { | |
| 418 int k; | |
| 419 for (k = 0; k < info.phi_count; k++) | |
| 420 { | |
| 421 constructor_elt *elt; | |
| 422 | |
| 423 elt = VEC_quick_push (constructor_elt, | |
| 424 info.constructors[k], NULL); | |
| 425 elt->index = int_const_binop (MINUS_EXPR, pos, | |
| 426 info.range_min, 0); | |
| 427 elt->value = info.default_values[k]; | |
| 428 } | |
| 429 | |
| 430 pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0); | |
| 431 } | |
| 432 gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs))); | |
| 433 | |
| 434 j = 0; | |
| 435 if (CASE_HIGH (cs)) | |
| 436 high = CASE_HIGH (cs); | |
| 437 else | |
| 438 high = CASE_LOW (cs); | |
| 439 for (gsi = gsi_start_phis (info.final_bb); | |
| 440 !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 441 { | |
| 442 gimple phi = gsi_stmt (gsi); | |
| 443 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); | |
| 444 tree low = CASE_LOW (cs); | |
| 445 pos = CASE_LOW (cs); | |
| 446 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
447 do |
| 0 | 448 { |
| 449 constructor_elt *elt; | |
| 450 | |
| 451 elt = VEC_quick_push (constructor_elt, | |
| 452 info.constructors[j], NULL); | |
| 453 elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min, 0); | |
| 454 elt->value = val; | |
| 455 | |
| 456 pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
457 } while (!tree_int_cst_lt (high, pos) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
458 && tree_int_cst_lt (low, pos)); |
| 0 | 459 j++; |
| 460 } | |
| 461 } | |
| 462 } | |
| 463 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
464 /* If all values in the constructor vector are the same, return the value. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
465 Otherwise return NULL_TREE. Not supposed to be called for empty |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
466 vectors. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
467 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
468 static tree |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
469 constructor_contains_same_values_p (VEC (constructor_elt, gc) *vec) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
470 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
471 int i, len = VEC_length (constructor_elt, vec); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
472 tree prev = NULL_TREE; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
473 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
474 for (i = 0; i < len; i++) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
475 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
476 constructor_elt *elt = VEC_index (constructor_elt, vec, i); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
477 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
478 if (!prev) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
479 prev = elt->value; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
480 else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
481 return NULL_TREE; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
482 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
483 return prev; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
484 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
485 |
| 0 | 486 /* Create an appropriate array type and declaration and assemble a static array |
| 487 variable. Also create a load statement that initializes the variable in | |
| 488 question with a value from the static array. SWTCH is the switch statement | |
| 489 being converted, NUM is the index to arrays of constructors, default values | |
| 490 and target SSA names for this particular array. ARR_INDEX_TYPE is the type | |
| 491 of the index of the new array, PHI is the phi node of the final BB that | |
| 492 corresponds to the value that will be loaded from the created array. TIDX | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
493 is an ssa name of a temporary variable holding the index for loads from the |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
494 new array. */ |
| 0 | 495 |
| 496 static void | |
| 497 build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi, | |
| 498 tree tidx) | |
| 499 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
500 tree name, cst; |
| 0 | 501 gimple load; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
502 gimple_stmt_iterator gsi = gsi_for_stmt (swtch); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
503 location_t loc = gimple_location (swtch); |
| 0 | 504 |
| 505 gcc_assert (info.default_values[num]); | |
| 506 | |
| 507 name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL); | |
| 508 info.target_inbound_names[num] = name; | |
| 509 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
510 cst = constructor_contains_same_values_p (info.constructors[num]); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
511 if (cst) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
512 load = gimple_build_assign (name, cst); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
513 else |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
514 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
515 tree array_type, ctor, decl, value_type, fetch; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
516 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
517 value_type = TREE_TYPE (info.default_values[num]); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
518 array_type = build_array_type (value_type, arr_index_type); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
519 ctor = build_constructor (array_type, info.constructors[num]); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
520 TREE_CONSTANT (ctor) = true; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
521 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
522 decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
523 TREE_STATIC (decl) = 1; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
524 DECL_INITIAL (decl) = ctor; |
| 0 | 525 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
526 DECL_NAME (decl) = create_tmp_var_name ("CSWTCH"); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
527 DECL_ARTIFICIAL (decl) = 1; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
528 TREE_CONSTANT (decl) = 1; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
529 add_referenced_var (decl); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
530 varpool_mark_needed_node (varpool_node (decl)); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
531 varpool_finalize_decl (decl); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
532 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
533 fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
534 NULL_TREE); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
535 load = gimple_build_assign (name, fetch); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
536 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
537 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
538 SSA_NAME_DEF_STMT (name) = load; |
| 0 | 539 gsi_insert_before (&gsi, load, GSI_SAME_STMT); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
540 update_stmt (load); |
| 0 | 541 info.arr_ref_last = load; |
| 542 } | |
| 543 | |
| 544 /* Builds and initializes static arrays initialized with values gathered from | |
| 545 the SWTCH switch statement. Also creates statements that load values from | |
| 546 them. */ | |
| 547 | |
| 548 static void | |
| 549 build_arrays (gimple swtch) | |
| 550 { | |
| 551 tree arr_index_type; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
552 tree tidx, sub, tmp; |
| 0 | 553 gimple stmt; |
| 554 gimple_stmt_iterator gsi; | |
| 555 int i; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
556 location_t loc = gimple_location (swtch); |
| 0 | 557 |
| 558 gsi = gsi_for_stmt (swtch); | |
| 559 | |
| 560 arr_index_type = build_index_type (info.range_size); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
561 tmp = create_tmp_var (TREE_TYPE (info.index_expr), "csti"); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
562 add_referenced_var (tmp); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
563 tidx = make_ssa_name (tmp, NULL); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
564 sub = fold_build2_loc (loc, MINUS_EXPR, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
565 TREE_TYPE (info.index_expr), info.index_expr, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
566 fold_convert_loc (loc, TREE_TYPE (info.index_expr), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
567 info.range_min)); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
568 sub = force_gimple_operand_gsi (&gsi, sub, |
| 0 | 569 false, NULL, true, GSI_SAME_STMT); |
| 570 stmt = gimple_build_assign (tidx, sub); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
571 SSA_NAME_DEF_STMT (tidx) = stmt; |
| 0 | 572 |
| 573 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
574 update_stmt (stmt); |
| 0 | 575 info.arr_ref_first = stmt; |
| 576 | |
| 577 for (gsi = gsi_start_phis (info.final_bb), i = 0; | |
| 578 !gsi_end_p (gsi); gsi_next (&gsi), i++) | |
| 579 build_one_array (swtch, i, arr_index_type, gsi_stmt (gsi), tidx); | |
| 580 } | |
| 581 | |
| 582 /* Generates and appropriately inserts loads of default values at the position | |
| 583 given by BSI. Returns the last inserted statement. */ | |
| 584 | |
| 585 static gimple | |
| 586 gen_def_assigns (gimple_stmt_iterator *gsi) | |
| 587 { | |
| 588 int i; | |
| 589 gimple assign = NULL; | |
| 590 | |
| 591 for (i = 0; i < info.phi_count; i++) | |
| 592 { | |
| 593 tree name | |
| 594 = make_ssa_name (SSA_NAME_VAR (info.target_inbound_names[i]), NULL); | |
| 595 | |
| 596 info.target_outbound_names[i] = name; | |
| 597 assign = gimple_build_assign (name, info.default_values[i]); | |
| 598 SSA_NAME_DEF_STMT (name) = assign; | |
| 599 gsi_insert_before (gsi, assign, GSI_SAME_STMT); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
600 update_stmt (assign); |
| 0 | 601 } |
| 602 return assign; | |
| 603 } | |
| 604 | |
| 605 /* Deletes the unused bbs and edges that now contain the switch statement and | |
| 606 its empty branch bbs. BBD is the now dead BB containing the original switch | |
| 607 statement, FINAL is the last BB of the converted switch statement (in terms | |
| 608 of succession). */ | |
| 609 | |
| 610 static void | |
| 611 prune_bbs (basic_block bbd, basic_block final) | |
| 612 { | |
| 613 edge_iterator ei; | |
| 614 edge e; | |
| 615 | |
| 616 for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); ) | |
| 617 { | |
| 618 basic_block bb; | |
| 619 bb = e->dest; | |
| 620 remove_edge (e); | |
| 621 if (bb != final) | |
| 622 delete_basic_block (bb); | |
| 623 } | |
| 624 delete_basic_block (bbd); | |
| 625 } | |
| 626 | |
| 627 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge | |
| 628 from the basic block loading values from an array and E2F from the basic | |
| 629 block loading default values. BBF is the last switch basic block (see the | |
| 630 bbf description in the comment below). */ | |
| 631 | |
| 632 static void | |
| 633 fix_phi_nodes (edge e1f, edge e2f, basic_block bbf) | |
| 634 { | |
| 635 gimple_stmt_iterator gsi; | |
| 636 int i; | |
| 637 | |
| 638 for (gsi = gsi_start_phis (bbf), i = 0; | |
| 639 !gsi_end_p (gsi); gsi_next (&gsi), i++) | |
| 640 { | |
| 641 gimple phi = gsi_stmt (gsi); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
642 add_phi_arg (phi, info.target_inbound_names[i], e1f, UNKNOWN_LOCATION); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
643 add_phi_arg (phi, info.target_outbound_names[i], e2f, UNKNOWN_LOCATION); |
| 0 | 644 } |
| 645 | |
| 646 } | |
| 647 | |
| 648 /* Creates a check whether the switch expression value actually falls into the | |
| 649 range given by all the cases. If it does not, the temporaries are loaded | |
| 650 with default values instead. SWTCH is the switch statement being converted. | |
| 651 | |
| 652 bb0 is the bb with the switch statement, however, we'll end it with a | |
| 653 condition instead. | |
| 654 | |
| 655 bb1 is the bb to be used when the range check went ok. It is derived from | |
| 656 the switch BB | |
| 657 | |
| 658 bb2 is the bb taken when the expression evaluated outside of the range | |
| 659 covered by the created arrays. It is populated by loads of default | |
| 660 values. | |
| 661 | |
| 662 bbF is a fall through for both bb1 and bb2 and contains exactly what | |
| 663 originally followed the switch statement. | |
| 664 | |
| 665 bbD contains the switch statement (in the end). It is unreachable but we | |
| 666 still need to strip off its edges. | |
| 667 */ | |
| 668 | |
| 669 static void | |
| 670 gen_inbound_check (gimple swtch) | |
| 671 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
672 tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
673 tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
674 tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION); |
| 0 | 675 gimple label1, label2, label3; |
| 676 | |
| 677 tree utype; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
678 tree tmp_u_1, tmp_u_2, tmp_u_var; |
| 0 | 679 tree cast; |
| 680 gimple cast_assign, minus_assign; | |
| 681 tree ulb, minus; | |
| 682 tree bound; | |
| 683 | |
| 684 gimple cond_stmt; | |
| 685 | |
| 686 gimple last_assign; | |
| 687 gimple_stmt_iterator gsi; | |
| 688 basic_block bb0, bb1, bb2, bbf, bbd; | |
| 689 edge e01, e02, e21, e1d, e1f, e2f; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
690 location_t loc = gimple_location (swtch); |
| 0 | 691 |
| 692 gcc_assert (info.default_values); | |
| 693 bb0 = gimple_bb (swtch); | |
| 694 | |
| 695 /* Make sure we do not generate arithmetics in a subrange. */ | |
| 696 if (TREE_TYPE (TREE_TYPE (info.index_expr))) | |
| 697 utype = unsigned_type_for (TREE_TYPE (TREE_TYPE (info.index_expr))); | |
| 698 else | |
| 699 utype = unsigned_type_for (TREE_TYPE (info.index_expr)); | |
| 700 | |
| 701 /* (end of) block 0 */ | |
| 702 gsi = gsi_for_stmt (info.arr_ref_first); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
703 tmp_u_var = create_tmp_var (utype, "csui"); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
704 add_referenced_var (tmp_u_var); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
705 tmp_u_1 = make_ssa_name (tmp_u_var, NULL); |
| 0 | 706 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
707 cast = fold_convert_loc (loc, utype, info.index_expr); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
708 cast_assign = gimple_build_assign (tmp_u_1, cast); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
709 SSA_NAME_DEF_STMT (tmp_u_1) = cast_assign; |
| 0 | 710 gsi_insert_before (&gsi, cast_assign, GSI_SAME_STMT); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
711 update_stmt (cast_assign); |
| 0 | 712 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
713 ulb = fold_convert_loc (loc, utype, info.range_min); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
714 minus = fold_build2_loc (loc, MINUS_EXPR, utype, tmp_u_1, ulb); |
| 0 | 715 minus = force_gimple_operand_gsi (&gsi, minus, false, NULL, true, |
| 716 GSI_SAME_STMT); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
717 tmp_u_2 = make_ssa_name (tmp_u_var, NULL); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
718 minus_assign = gimple_build_assign (tmp_u_2, minus); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
719 SSA_NAME_DEF_STMT (tmp_u_2) = minus_assign; |
| 0 | 720 gsi_insert_before (&gsi, minus_assign, GSI_SAME_STMT); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
721 update_stmt (minus_assign); |
| 0 | 722 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
723 bound = fold_convert_loc (loc, utype, info.range_size); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
724 cond_stmt = gimple_build_cond (LE_EXPR, tmp_u_2, bound, NULL_TREE, NULL_TREE); |
| 0 | 725 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
726 update_stmt (cond_stmt); |
| 0 | 727 |
| 728 /* block 2 */ | |
| 729 gsi = gsi_for_stmt (info.arr_ref_first); | |
| 730 label2 = gimple_build_label (label_decl2); | |
| 731 gsi_insert_before (&gsi, label2, GSI_SAME_STMT); | |
| 732 last_assign = gen_def_assigns (&gsi); | |
| 733 | |
| 734 /* block 1 */ | |
| 735 gsi = gsi_for_stmt (info.arr_ref_first); | |
| 736 label1 = gimple_build_label (label_decl1); | |
| 737 gsi_insert_before (&gsi, label1, GSI_SAME_STMT); | |
| 738 | |
| 739 /* block F */ | |
| 740 gsi = gsi_start_bb (info.final_bb); | |
| 741 label3 = gimple_build_label (label_decl3); | |
| 742 gsi_insert_before (&gsi, label3, GSI_SAME_STMT); | |
| 743 | |
| 744 /* cfg fix */ | |
| 745 e02 = split_block (bb0, cond_stmt); | |
| 746 bb2 = e02->dest; | |
| 747 | |
| 748 e21 = split_block (bb2, last_assign); | |
| 749 bb1 = e21->dest; | |
| 750 remove_edge (e21); | |
| 751 | |
| 752 e1d = split_block (bb1, info.arr_ref_last); | |
| 753 bbd = e1d->dest; | |
| 754 remove_edge (e1d); | |
| 755 | |
| 756 /* flags and profiles of the edge for in-range values */ | |
| 757 e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE); | |
| 758 e01->probability = REG_BR_PROB_BASE - info.default_prob; | |
| 759 e01->count = info.other_count; | |
| 760 | |
| 761 /* flags and profiles of the edge taking care of out-of-range values */ | |
| 762 e02->flags &= ~EDGE_FALLTHRU; | |
| 763 e02->flags |= EDGE_FALSE_VALUE; | |
| 764 e02->probability = info.default_prob; | |
| 765 e02->count = info.default_count; | |
| 766 | |
| 767 bbf = info.final_bb; | |
| 768 | |
| 769 e1f = make_edge (bb1, bbf, EDGE_FALLTHRU); | |
| 770 e1f->probability = REG_BR_PROB_BASE; | |
| 771 e1f->count = info.other_count; | |
| 772 | |
| 773 e2f = make_edge (bb2, bbf, EDGE_FALLTHRU); | |
| 774 e2f->probability = REG_BR_PROB_BASE; | |
| 775 e2f->count = info.default_count; | |
| 776 | |
| 777 /* frequencies of the new BBs */ | |
| 778 bb1->frequency = EDGE_FREQUENCY (e01); | |
| 779 bb2->frequency = EDGE_FREQUENCY (e02); | |
| 780 bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f); | |
| 781 | |
| 782 prune_bbs (bbd, info.final_bb); /* To keep calc_dfs_tree() in dominance.c | |
| 783 happy. */ | |
| 784 | |
| 785 fix_phi_nodes (e1f, e2f, bbf); | |
| 786 | |
| 787 free_dominance_info (CDI_DOMINATORS); | |
| 788 free_dominance_info (CDI_POST_DOMINATORS); | |
| 789 } | |
| 790 | |
| 791 /* The following function is invoked on every switch statement (the current one | |
| 792 is given in SWTCH) and runs the individual phases of switch conversion on it | |
| 793 one after another until one fails or the conversion is completed. */ | |
| 794 | |
| 795 static bool | |
| 796 process_switch (gimple swtch) | |
| 797 { | |
| 798 unsigned int i, branch_num = gimple_switch_num_labels (swtch); | |
| 799 tree index_type; | |
| 800 | |
| 801 /* Operand 2 is either NULL_TREE or a vector of cases (stmt.c). */ | |
| 802 if (branch_num < 2) | |
| 803 { | |
| 804 info.reason = "switch has no labels\n"; | |
| 805 return false; | |
| 806 } | |
| 807 | |
| 808 info.final_bb = NULL; | |
| 809 info.switch_bb = gimple_bb (swtch); | |
| 810 info.index_expr = gimple_switch_index (swtch); | |
| 811 index_type = TREE_TYPE (info.index_expr); | |
| 812 info.arr_ref_first = NULL; | |
| 813 info.arr_ref_last = NULL; | |
| 814 info.default_prob = 0; | |
| 815 info.default_count = 0; | |
| 816 info.other_count = 0; | |
| 817 | |
| 818 /* An ERROR_MARK occurs for various reasons including invalid data type. | |
| 819 (comment from stmt.c) */ | |
| 820 if (index_type == error_mark_node) | |
| 821 { | |
| 822 info.reason = "index error.\n"; | |
| 823 return false; | |
| 824 } | |
| 825 | |
| 826 /* Check the case label values are within reasonable range: */ | |
| 827 if (!check_range (swtch)) | |
| 828 return false; | |
| 829 | |
| 830 /* For all the cases, see whether they are empty, the assignments they | |
| 831 represent constant and so on... */ | |
| 832 for (i = 0; i < branch_num; i++) | |
| 833 if (!check_process_case (gimple_switch_label (swtch, i))) | |
| 834 { | |
| 835 if (dump_file) | |
| 836 fprintf (dump_file, "Processing of case %i failed\n", i); | |
| 837 return false; | |
| 838 } | |
| 839 | |
| 840 if (!check_final_bb ()) | |
| 841 return false; | |
| 842 | |
| 843 /* At this point all checks have passed and we can proceed with the | |
| 844 transformation. */ | |
| 845 | |
| 846 create_temp_arrays (); | |
| 847 gather_default_values (gimple_switch_label (swtch, 0)); | |
| 848 build_constructors (swtch); | |
| 849 | |
| 850 build_arrays (swtch); /* Build the static arrays and assignments. */ | |
| 851 gen_inbound_check (swtch); /* Build the bounds check. */ | |
| 852 | |
| 853 /* Cleanup: */ | |
| 854 free_temp_arrays (); | |
| 855 return true; | |
| 856 } | |
| 857 | |
| 858 /* The main function of the pass scans statements for switches and invokes | |
| 859 process_switch on them. */ | |
| 860 | |
| 861 static unsigned int | |
| 862 do_switchconv (void) | |
| 863 { | |
| 864 basic_block bb; | |
| 865 | |
| 866 FOR_EACH_BB (bb) | |
| 867 { | |
| 868 gimple stmt = last_stmt (bb); | |
| 869 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) | |
| 870 { | |
| 871 if (dump_file) | |
| 872 { | |
| 873 expanded_location loc = expand_location (gimple_location (stmt)); | |
| 874 | |
| 875 fprintf (dump_file, "beginning to process the following " | |
| 876 "SWITCH statement (%s:%d) : ------- \n", | |
| 877 loc.file, loc.line); | |
| 878 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
879 putc ('\n', dump_file); |
| 0 | 880 } |
| 881 | |
| 882 info.reason = NULL; | |
| 883 if (process_switch (stmt)) | |
| 884 { | |
| 885 if (dump_file) | |
| 886 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
887 fputs ("Switch converted\n", dump_file); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
888 fputs ("--------------------------------\n", dump_file); |
| 0 | 889 } |
| 890 } | |
| 891 else | |
| 892 { | |
| 893 if (dump_file) | |
| 894 { | |
| 895 gcc_assert (info.reason); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
896 fputs ("Bailing out - ", dump_file); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
897 fputs (info.reason, dump_file); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
898 fputs ("--------------------------------\n", dump_file); |
| 0 | 899 } |
| 900 } | |
| 901 } | |
| 902 } | |
| 903 | |
| 904 return 0; | |
| 905 } | |
| 906 | |
| 907 /* The pass gate. */ | |
| 908 | |
| 909 static bool | |
| 910 switchconv_gate (void) | |
| 911 { | |
| 912 return flag_tree_switch_conversion != 0; | |
| 913 } | |
| 914 | |
| 915 struct gimple_opt_pass pass_convert_switch = | |
| 916 { | |
| 917 { | |
| 918 GIMPLE_PASS, | |
| 919 "switchconv", /* name */ | |
| 920 switchconv_gate, /* gate */ | |
| 921 do_switchconv, /* execute */ | |
| 922 NULL, /* sub */ | |
| 923 NULL, /* next */ | |
| 924 0, /* static_pass_number */ | |
| 925 TV_TREE_SWITCH_CONVERSION, /* tv_id */ | |
| 926 PROP_cfg | PROP_ssa, /* properties_required */ | |
| 927 0, /* properties_provided */ | |
| 928 0, /* properties_destroyed */ | |
| 929 0, /* todo_flags_start */ | |
| 930 TODO_update_ssa | TODO_dump_func | |
| 931 | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ | |
| 932 } | |
| 933 }; |