Merge branch 'vendor/GCC44'
[dragonfly.git] / contrib / gcc-4.4 / gcc / tree-switch-conversion.c
CommitLineData
c251ad9e
SS
1/* Switch Conversion converts variable initializations based on switch
2 statements to initializations from a static array.
3 Copyright (C) 2006, 2008 Free Software Foundation, Inc.
4 Contributed by Martin Jambor <jamborm@suse.cz>
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it
9under the terms of the GNU General Public License as published by the
10Free Software Foundation; either version 3, or (at your option) any
11later version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT
14ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not, write to the Free
20Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
2102110-1301, USA. */
22
23/*
24 Switch initialization conversion
25
26The following pass changes simple initializations of scalars in a switch
27statement into initializations from a static array. Obviously, the values must
28be constant and known at compile time and a default branch must be
29provided. 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
56is 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
75There are further constraints. Specifically, the range of values across all
76case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
77eight) 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"
97#include "tree-dump.h"
98#include "timevar.h"
4b1e227d 99#include "langhooks.h"
c251ad9e
SS
100
101/* The main structure of the pass. */
102struct 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. */
162static 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
169static bool
170check_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
217static bool
218check_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
283static bool
284check_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
334static void
335create_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
355static void
356free_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
367static void
368gather_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
395static void
396build_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
447 do
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);
457 } while (!tree_int_cst_lt (high, pos) && tree_int_cst_lt (low, pos));
458 j++;
459 }
460 }
461}
462
463/* Create an appropriate array type and declaration and assemble a static array
464 variable. Also create a load statement that initializes the variable in
465 question with a value from the static array. SWTCH is the switch statement
466 being converted, NUM is the index to arrays of constructors, default values
467 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
468 of the index of the new array, PHI is the phi node of the final BB that
469 corresponds to the value that will be loaded from the created array. TIDX
470 is a temporary variable holding the index for loads from the new array. */
471
472static void
473build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi,
474 tree tidx)
475{
476 tree array_type, ctor, decl, value_type, name, fetch;
477 gimple load;
478 gimple_stmt_iterator gsi;
479
480 gcc_assert (info.default_values[num]);
481 value_type = TREE_TYPE (info.default_values[num]);
482 array_type = build_array_type (value_type, arr_index_type);
483
484 ctor = build_constructor (array_type, info.constructors[num]);
485 TREE_CONSTANT (ctor) = true;
486
487 decl = build_decl (VAR_DECL, NULL_TREE, array_type);
488 TREE_STATIC (decl) = 1;
489 DECL_INITIAL (decl) = ctor;
490
491 DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
492 DECL_ARTIFICIAL (decl) = 1;
493 TREE_CONSTANT (decl) = 1;
494 add_referenced_var (decl);
495 varpool_mark_needed_node (varpool_node (decl));
496 varpool_finalize_decl (decl);
497 mark_sym_for_renaming (decl);
498
499 name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL);
500 info.target_inbound_names[num] = name;
501
502 fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
503 NULL_TREE);
504 load = gimple_build_assign (name, fetch);
505 SSA_NAME_DEF_STMT (name) = load;
506
507 gsi = gsi_for_stmt (swtch);
508 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
509 mark_symbols_for_renaming (load);
510
511 info.arr_ref_last = load;
512}
513
514/* Builds and initializes static arrays initialized with values gathered from
515 the SWTCH switch statement. Also creates statements that load values from
516 them. */
517
518static void
519build_arrays (gimple swtch)
520{
521 tree arr_index_type;
522 tree tidx, sub;
523 gimple stmt;
524 gimple_stmt_iterator gsi;
525 int i;
526
527 gsi = gsi_for_stmt (swtch);
528
529 arr_index_type = build_index_type (info.range_size);
530 tidx = make_rename_temp (arr_index_type, "csti");
531 sub = fold_build2 (MINUS_EXPR, TREE_TYPE (info.index_expr), info.index_expr,
532 fold_convert (TREE_TYPE (info.index_expr),
533 info.range_min));
534 sub = force_gimple_operand_gsi (&gsi, fold_convert (arr_index_type, sub),
535 false, NULL, true, GSI_SAME_STMT);
536 stmt = gimple_build_assign (tidx, sub);
537
538 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
539 mark_symbols_for_renaming (stmt);
540 info.arr_ref_first = stmt;
541
542 for (gsi = gsi_start_phis (info.final_bb), i = 0;
543 !gsi_end_p (gsi); gsi_next (&gsi), i++)
544 build_one_array (swtch, i, arr_index_type, gsi_stmt (gsi), tidx);
545}
546
547/* Generates and appropriately inserts loads of default values at the position
548 given by BSI. Returns the last inserted statement. */
549
550static gimple
551gen_def_assigns (gimple_stmt_iterator *gsi)
552{
553 int i;
554 gimple assign = NULL;
555
556 for (i = 0; i < info.phi_count; i++)
557 {
558 tree name
559 = make_ssa_name (SSA_NAME_VAR (info.target_inbound_names[i]), NULL);
560
561 info.target_outbound_names[i] = name;
562 assign = gimple_build_assign (name, info.default_values[i]);
563 SSA_NAME_DEF_STMT (name) = assign;
564 gsi_insert_before (gsi, assign, GSI_SAME_STMT);
565 find_new_referenced_vars (assign);
566 mark_symbols_for_renaming (assign);
567 }
568 return assign;
569}
570
571/* Deletes the unused bbs and edges that now contain the switch statement and
572 its empty branch bbs. BBD is the now dead BB containing the original switch
573 statement, FINAL is the last BB of the converted switch statement (in terms
574 of succession). */
575
576static void
577prune_bbs (basic_block bbd, basic_block final)
578{
579 edge_iterator ei;
580 edge e;
581
582 for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
583 {
584 basic_block bb;
585 bb = e->dest;
586 remove_edge (e);
587 if (bb != final)
588 delete_basic_block (bb);
589 }
590 delete_basic_block (bbd);
591}
592
593/* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
594 from the basic block loading values from an array and E2F from the basic
595 block loading default values. BBF is the last switch basic block (see the
596 bbf description in the comment below). */
597
598static void
599fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
600{
601 gimple_stmt_iterator gsi;
602 int i;
603
604 for (gsi = gsi_start_phis (bbf), i = 0;
605 !gsi_end_p (gsi); gsi_next (&gsi), i++)
606 {
607 gimple phi = gsi_stmt (gsi);
608 add_phi_arg (phi, info.target_inbound_names[i], e1f);
609 add_phi_arg (phi, info.target_outbound_names[i], e2f);
610 }
611
612}
613
614/* Creates a check whether the switch expression value actually falls into the
615 range given by all the cases. If it does not, the temporaries are loaded
616 with default values instead. SWTCH is the switch statement being converted.
617
618 bb0 is the bb with the switch statement, however, we'll end it with a
619 condition instead.
620
621 bb1 is the bb to be used when the range check went ok. It is derived from
622 the switch BB
623
624 bb2 is the bb taken when the expression evaluated outside of the range
625 covered by the created arrays. It is populated by loads of default
626 values.
627
628 bbF is a fall through for both bb1 and bb2 and contains exactly what
629 originally followed the switch statement.
630
631 bbD contains the switch statement (in the end). It is unreachable but we
632 still need to strip off its edges.
633*/
634
635static void
636gen_inbound_check (gimple swtch)
637{
638 tree label_decl1 = create_artificial_label ();
639 tree label_decl2 = create_artificial_label ();
640 tree label_decl3 = create_artificial_label ();
641 gimple label1, label2, label3;
642
643 tree utype;
644 tree tmp_u;
645 tree cast;
646 gimple cast_assign, minus_assign;
647 tree ulb, minus;
648 tree bound;
649
650 gimple cond_stmt;
651
652 gimple last_assign;
653 gimple_stmt_iterator gsi;
654 basic_block bb0, bb1, bb2, bbf, bbd;
655 edge e01, e02, e21, e1d, e1f, e2f;
656
657 gcc_assert (info.default_values);
658 bb0 = gimple_bb (swtch);
659
660 /* Make sure we do not generate arithmetics in a subrange. */
661 if (TREE_TYPE (TREE_TYPE (info.index_expr)))
4b1e227d
SW
662 utype = lang_hooks.types.type_for_mode
663 (TYPE_MODE (TREE_TYPE (TREE_TYPE (info.index_expr))), 1);
c251ad9e 664 else
4b1e227d
SW
665 utype = lang_hooks.types.type_for_mode
666 (TYPE_MODE (TREE_TYPE (info.index_expr)), 1);
c251ad9e
SS
667
668 /* (end of) block 0 */
669 gsi = gsi_for_stmt (info.arr_ref_first);
670 tmp_u = make_rename_temp (utype, "csui");
671
672 cast = fold_convert (utype, info.index_expr);
673 cast_assign = gimple_build_assign (tmp_u, cast);
674 find_new_referenced_vars (cast_assign);
675 gsi_insert_before (&gsi, cast_assign, GSI_SAME_STMT);
676 mark_symbols_for_renaming (cast_assign);
677
678 ulb = fold_convert (utype, info.range_min);
679 minus = fold_build2 (MINUS_EXPR, utype, tmp_u, ulb);
680 minus = force_gimple_operand_gsi (&gsi, minus, false, NULL, true,
681 GSI_SAME_STMT);
682 minus_assign = gimple_build_assign (tmp_u, minus);
683 find_new_referenced_vars (minus_assign);
684 gsi_insert_before (&gsi, minus_assign, GSI_SAME_STMT);
685 mark_symbols_for_renaming (minus_assign);
686
687 bound = fold_convert (utype, info.range_size);
688
689 cond_stmt = gimple_build_cond (LE_EXPR, tmp_u, bound, NULL_TREE, NULL_TREE);
690
691 find_new_referenced_vars (cond_stmt);
692 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
693 mark_symbols_for_renaming (cond_stmt);
694
695 /* block 2 */
696 gsi = gsi_for_stmt (info.arr_ref_first);
697 label2 = gimple_build_label (label_decl2);
698 gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
699 last_assign = gen_def_assigns (&gsi);
700
701 /* block 1 */
702 gsi = gsi_for_stmt (info.arr_ref_first);
703 label1 = gimple_build_label (label_decl1);
704 gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
705
706 /* block F */
707 gsi = gsi_start_bb (info.final_bb);
708 label3 = gimple_build_label (label_decl3);
709 gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
710
711 /* cfg fix */
712 e02 = split_block (bb0, cond_stmt);
713 bb2 = e02->dest;
714
715 e21 = split_block (bb2, last_assign);
716 bb1 = e21->dest;
717 remove_edge (e21);
718
719 e1d = split_block (bb1, info.arr_ref_last);
720 bbd = e1d->dest;
721 remove_edge (e1d);
722
723 /* flags and profiles of the edge for in-range values */
724 e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
725 e01->probability = REG_BR_PROB_BASE - info.default_prob;
726 e01->count = info.other_count;
727
728 /* flags and profiles of the edge taking care of out-of-range values */
729 e02->flags &= ~EDGE_FALLTHRU;
730 e02->flags |= EDGE_FALSE_VALUE;
731 e02->probability = info.default_prob;
732 e02->count = info.default_count;
733
734 bbf = info.final_bb;
735
736 e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
737 e1f->probability = REG_BR_PROB_BASE;
738 e1f->count = info.other_count;
739
740 e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
741 e2f->probability = REG_BR_PROB_BASE;
742 e2f->count = info.default_count;
743
744 /* frequencies of the new BBs */
745 bb1->frequency = EDGE_FREQUENCY (e01);
746 bb2->frequency = EDGE_FREQUENCY (e02);
747 bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
748
749 prune_bbs (bbd, info.final_bb); /* To keep calc_dfs_tree() in dominance.c
750 happy. */
751
752 fix_phi_nodes (e1f, e2f, bbf);
753
754 free_dominance_info (CDI_DOMINATORS);
755 free_dominance_info (CDI_POST_DOMINATORS);
756}
757
758/* The following function is invoked on every switch statement (the current one
759 is given in SWTCH) and runs the individual phases of switch conversion on it
760 one after another until one fails or the conversion is completed. */
761
762static bool
763process_switch (gimple swtch)
764{
765 unsigned int i, branch_num = gimple_switch_num_labels (swtch);
766 tree index_type;
767
768 /* Operand 2 is either NULL_TREE or a vector of cases (stmt.c). */
769 if (branch_num < 2)
770 {
771 info.reason = "switch has no labels\n";
772 return false;
773 }
774
775 info.final_bb = NULL;
776 info.switch_bb = gimple_bb (swtch);
777 info.index_expr = gimple_switch_index (swtch);
778 index_type = TREE_TYPE (info.index_expr);
779 info.arr_ref_first = NULL;
780 info.arr_ref_last = NULL;
781 info.default_prob = 0;
782 info.default_count = 0;
783 info.other_count = 0;
784
785 /* An ERROR_MARK occurs for various reasons including invalid data type.
786 (comment from stmt.c) */
787 if (index_type == error_mark_node)
788 {
789 info.reason = "index error.\n";
790 return false;
791 }
792
793 /* Check the case label values are within reasonable range: */
794 if (!check_range (swtch))
795 return false;
796
797 /* For all the cases, see whether they are empty, the assignments they
798 represent constant and so on... */
799 for (i = 0; i < branch_num; i++)
800 if (!check_process_case (gimple_switch_label (swtch, i)))
801 {
802 if (dump_file)
803 fprintf (dump_file, "Processing of case %i failed\n", i);
804 return false;
805 }
806
807 if (!check_final_bb ())
808 return false;
809
810 /* At this point all checks have passed and we can proceed with the
811 transformation. */
812
813 create_temp_arrays ();
814 gather_default_values (gimple_switch_label (swtch, 0));
815 build_constructors (swtch);
816
817 build_arrays (swtch); /* Build the static arrays and assignments. */
818 gen_inbound_check (swtch); /* Build the bounds check. */
819
820 /* Cleanup: */
821 free_temp_arrays ();
822 return true;
823}
824
825/* The main function of the pass scans statements for switches and invokes
826 process_switch on them. */
827
828static unsigned int
829do_switchconv (void)
830{
831 basic_block bb;
832
833 FOR_EACH_BB (bb)
834 {
835 gimple stmt = last_stmt (bb);
836 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
837 {
838 if (dump_file)
839 {
840 expanded_location loc = expand_location (gimple_location (stmt));
841
842 fprintf (dump_file, "beginning to process the following "
843 "SWITCH statement (%s:%d) : ------- \n",
844 loc.file, loc.line);
845 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
846 fprintf (dump_file, "\n");
847 }
848
849 info.reason = NULL;
850 if (process_switch (stmt))
851 {
852 if (dump_file)
853 {
854 fprintf (dump_file, "Switch converted\n");
855 fprintf (dump_file, "--------------------------------\n");
856 }
857 }
858 else
859 {
860 if (dump_file)
861 {
862 gcc_assert (info.reason);
863 fprintf (dump_file, "Bailing out - ");
864 fprintf (dump_file, info.reason);
865 fprintf (dump_file, "--------------------------------\n");
866 }
867 }
868 }
869 }
870
871 return 0;
872}
873
874/* The pass gate. */
875
876static bool
877switchconv_gate (void)
878{
879 return flag_tree_switch_conversion != 0;
880}
881
882struct gimple_opt_pass pass_convert_switch =
883{
884 {
885 GIMPLE_PASS,
886 "switchconv", /* name */
887 switchconv_gate, /* gate */
888 do_switchconv, /* execute */
889 NULL, /* sub */
890 NULL, /* next */
891 0, /* static_pass_number */
892 TV_TREE_SWITCH_CONVERSION, /* tv_id */
893 PROP_cfg | PROP_ssa, /* properties_required */
894 0, /* properties_provided */
895 0, /* properties_destroyed */
896 0, /* todo_flags_start */
897 TODO_update_ssa | TODO_dump_func
898 | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
899 }
900};