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