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
check_range(gimple swtch)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
check_process_case(tree cs)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
check_final_bb(void)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
create_temp_arrays(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
free_temp_arrays(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
gather_default_values(tree default_case)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
build_constructors(gimple swtch)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
constructor_contains_same_values_p(VEC (constructor_elt,gc)* vec)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
array_value_type(gimple swtch,tree type,int num)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
build_one_array(gimple swtch,int num,tree arr_index_type,gimple phi,tree tidx)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
build_arrays(gimple swtch)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
gen_def_assigns(gimple_stmt_iterator * gsi)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
prune_bbs(basic_block bbd,basic_block final)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
fix_phi_nodes(edge e1f,edge e2f,basic_block bbf)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
gen_inbound_check(gimple swtch)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
process_switch(gimple swtch)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
do_switchconv(void)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
switchconv_gate(void)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