OSDN Git Service

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