Merge branch 'vendor/GCC44'
[dragonfly.git] / contrib / gcc-4.4 / 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 #include "langhooks.h"
100
101 /* The main structure of the pass.  */
102 struct switch_conv_info
103 {
104   /* The expression used to decide the switch branch.  (It is subsequently used
105      as the index to the created array.) */
106   tree index_expr;
107
108   /* The following integer constants store the minimum value covered by the
109      cases.  */
110   tree range_min;
111
112   /* The difference between the above two numbers, i.e. The size of the array
113      that would have to be created by the transformation.  */
114   tree range_size;
115
116   /* Basic block that contains the actual SWITCH_EXPR.  */
117   basic_block switch_bb;
118
119   /* All branches of the switch statement must have a single successor stored in
120      the following variable.  */
121   basic_block final_bb;
122
123   /* Number of phi nodes in the final bb (that we'll be replacing).  */
124   int phi_count;
125
126   /* Array of default values, in the same order as phi nodes.  */
127   tree *default_values;
128
129   /* Constructors of new static arrays.  */
130   VEC (constructor_elt, gc) **constructors;
131
132   /* Array of ssa names that are initialized with a value from a new static
133      array.  */
134   tree *target_inbound_names;
135
136   /* Array of ssa names that are initialized with the default value if the
137      switch expression is out of range.  */
138   tree *target_outbound_names;
139
140   /* The probability of the default edge in the replaced switch.  */
141   int default_prob;
142
143   /* The count of the default edge in the replaced switch.  */
144   gcov_type default_count;
145
146   /* Combined count of all other (non-default) edges in the replaced switch.  */
147   gcov_type other_count;
148
149   /* The first load statement that loads a temporary from a new static array.
150    */
151   gimple arr_ref_first;
152
153   /* The last load statement that loads a temporary from a new static array.  */
154   gimple arr_ref_last;
155
156   /* String reason why the case wasn't a good candidate that is written to the
157      dump file, if there is one.  */
158   const char *reason;
159 };
160
161 /* Global pass info.  */
162 static struct switch_conv_info info;
163
164
165 /* Checks whether the range given by individual case statements of the SWTCH
166    switch statement isn't too big and whether the number of branches actually
167    satisfies the size of the new array.  */
168
169 static bool
170 check_range (gimple swtch)
171 {
172   tree min_case, max_case;
173   unsigned int branch_num = gimple_switch_num_labels (swtch);
174   tree range_max;
175
176   /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
177      is a default label which is the last in the vector.  */
178
179   min_case = gimple_switch_label (swtch, 1);
180   info.range_min = CASE_LOW (min_case);
181
182   gcc_assert (branch_num > 1);
183   gcc_assert (CASE_LOW (gimple_switch_label (swtch, 0)) == NULL_TREE);
184   max_case = gimple_switch_label (swtch, branch_num - 1);
185   if (CASE_HIGH (max_case) != NULL_TREE)
186     range_max = CASE_HIGH (max_case);
187   else
188     range_max = CASE_LOW (max_case);
189
190   gcc_assert (info.range_min);
191   gcc_assert (range_max);
192
193   info.range_size = int_const_binop (MINUS_EXPR, range_max, info.range_min, 0);
194
195   gcc_assert (info.range_size);
196   if (!host_integerp (info.range_size, 1))
197     {
198       info.reason = "index range way too large or otherwise unusable.\n";
199       return false;
200     }
201
202   if ((unsigned HOST_WIDE_INT) tree_low_cst (info.range_size, 1)
203       > ((unsigned) branch_num * SWITCH_CONVERSION_BRANCH_RATIO))
204     {
205       info.reason = "the maximum range-branch ratio exceeded.\n";
206       return false;
207     }
208
209   return true;
210 }
211
212 /* Checks the given CS switch case whether it is suitable for conversion
213    (whether all but the default basic blocks are empty and so on).  If it is,
214    adds the case to the branch list along with values for the defined variables
215    and returns true.  Otherwise returns false.  */
216
217 static bool
218 check_process_case (tree cs)
219 {
220   tree ldecl;
221   basic_block label_bb, following_bb;
222   edge e;
223
224   ldecl = CASE_LABEL (cs);
225   label_bb = label_to_block (ldecl);
226
227   e = find_edge (info.switch_bb, label_bb);
228   gcc_assert (e);
229
230   if (CASE_LOW (cs) == NULL_TREE)
231     {
232       /* Default branch.  */
233       info.default_prob = e->probability;
234       info.default_count = e->count;
235     }
236   else
237     info.other_count += e->count;
238
239   if (!label_bb)
240     {
241       info.reason = "  Bad case - cs BB  label is NULL\n";
242       return false;
243     }
244
245   if (!single_pred_p (label_bb))
246     {
247       if (info.final_bb && info.final_bb != label_bb)
248         {
249           info.reason = "  Bad case - a non-final BB has two predecessors\n";
250           return false; /* sth complex going on in this branch  */
251         }
252
253       following_bb = label_bb;
254     }
255   else
256     {
257       if (!empty_block_p (label_bb))
258         {
259           info.reason = "  Bad case - a non-final BB not empty\n";
260           return false;
261         }
262
263       e = single_succ_edge (label_bb);
264       following_bb = single_succ (label_bb);
265     }
266
267   if (!info.final_bb)
268     info.final_bb = following_bb;
269   else if (info.final_bb != following_bb)
270     {
271       info.reason = "  Bad case - different final BB\n";
272       return false; /* the only successor is not common for all the branches */
273     }
274
275   return true;
276 }
277
278 /* This function checks whether all required values in phi nodes in final_bb
279    are constants.  Required values are those that correspond to a basic block
280    which is a part of the examined switch statement.  It returns true if the
281    phi nodes are OK, otherwise false.  */
282
283 static bool
284 check_final_bb (void)
285 {
286   gimple_stmt_iterator gsi;
287
288   info.phi_count = 0;
289   for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
290     {
291       gimple phi = gsi_stmt (gsi);
292       unsigned int i;
293
294       info.phi_count++;
295
296       for (i = 0; i < gimple_phi_num_args (phi); i++)
297         {
298           basic_block bb = gimple_phi_arg_edge (phi, i)->src;
299
300           if (bb == info.switch_bb
301               || (single_pred_p (bb) && single_pred (bb) == info.switch_bb))
302             {
303               tree reloc, val;
304
305               val = gimple_phi_arg_def (phi, i);
306               if (!is_gimple_ip_invariant (val))
307                 {
308                   info.reason = "   Non-invariant value from a case\n";
309                   return false; /* Non-invariant argument.  */
310                 }
311               reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
312               if ((flag_pic && reloc != null_pointer_node)
313                   || (!flag_pic && reloc == NULL_TREE))
314                 {
315                   if (reloc)
316                     info.reason
317                       = "   Value from a case would need runtime relocations\n";
318                   else
319                     info.reason
320                       = "   Value from a case is not a valid initializer\n";
321                   return false;
322                 }
323             }
324         }
325     }
326
327   return true;
328 }
329
330 /* The following function allocates default_values, target_{in,out}_names and
331    constructors arrays.  The last one is also populated with pointers to
332    vectors that will become constructors of new arrays.  */
333
334 static void
335 create_temp_arrays (void)
336 {
337   int i;
338
339   info.default_values = (tree *) xcalloc (info.phi_count, sizeof (tree));
340   info.constructors = (VEC (constructor_elt, gc) **) xcalloc (info.phi_count,
341                                                               sizeof (tree));
342   info.target_inbound_names = (tree *) xcalloc (info.phi_count, sizeof (tree));
343   info.target_outbound_names = (tree *) xcalloc (info.phi_count,
344                                                  sizeof (tree));
345
346   for (i = 0; i < info.phi_count; i++)
347     info.constructors[i]
348       = VEC_alloc (constructor_elt, gc, tree_low_cst (info.range_size, 1) + 1);
349 }
350
351 /* Free the arrays created by create_temp_arrays().  The vectors that are
352    created by that function are not freed here, however, because they have
353    already become constructors and must be preserved.  */
354
355 static void
356 free_temp_arrays (void)
357 {
358   free (info.constructors);
359   free (info.default_values);
360   free (info.target_inbound_names);
361   free (info.target_outbound_names);
362 }
363
364 /* Populate the array of default values in the order of phi nodes.
365    DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch.  */
366
367 static void
368 gather_default_values (tree default_case)
369 {
370   gimple_stmt_iterator gsi;
371   basic_block bb = label_to_block (CASE_LABEL (default_case));
372   edge e;
373   int i = 0;
374
375   gcc_assert (CASE_LOW (default_case) == NULL_TREE);
376
377   if (bb == info.final_bb)
378     e = find_edge (info.switch_bb, bb);
379   else
380     e = single_succ_edge (bb);
381
382   for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
383     {
384       gimple phi = gsi_stmt (gsi);
385       tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
386       gcc_assert (val);
387       info.default_values[i++] = val;
388     }
389 }
390
391 /* The following function populates the vectors in the constructors array with
392    future contents of the static arrays.  The vectors are populated in the
393    order of phi nodes.  SWTCH is the switch statement being converted.  */
394
395 static void
396 build_constructors (gimple swtch)
397 {
398   unsigned i, branch_num = gimple_switch_num_labels (swtch);
399   tree pos = info.range_min;
400
401   for (i = 1; i < branch_num; i++)
402     {
403       tree cs = gimple_switch_label (swtch, i);
404       basic_block bb = label_to_block (CASE_LABEL (cs));
405       edge e;
406       tree high;
407       gimple_stmt_iterator gsi;
408       int j;
409
410       if (bb == info.final_bb)
411         e = find_edge (info.switch_bb, bb);
412       else
413         e = single_succ_edge (bb);
414       gcc_assert (e);
415
416       while (tree_int_cst_lt (pos, CASE_LOW (cs)))
417         {
418           int k;
419           for (k = 0; k < info.phi_count; k++)
420             {
421               constructor_elt *elt;
422
423               elt = VEC_quick_push (constructor_elt,
424                                     info.constructors[k], NULL);
425               elt->index = int_const_binop (MINUS_EXPR, pos,
426                                             info.range_min, 0);
427               elt->value = info.default_values[k];
428             }
429
430           pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
431         }
432       gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
433
434       j = 0;
435       if (CASE_HIGH (cs))
436         high = CASE_HIGH (cs);
437       else
438         high = CASE_LOW (cs);
439       for (gsi = gsi_start_phis (info.final_bb);
440            !gsi_end_p (gsi); gsi_next (&gsi))
441         {
442           gimple phi = gsi_stmt (gsi);
443           tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
444           tree low = CASE_LOW (cs);
445           pos = CASE_LOW (cs);
446
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
472 static void
473 build_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
518 static void
519 build_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
550 static gimple
551 gen_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
576 static void
577 prune_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
598 static void
599 fix_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
635 static void
636 gen_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)))
662     utype = lang_hooks.types.type_for_mode
663       (TYPE_MODE (TREE_TYPE (TREE_TYPE (info.index_expr))), 1);
664   else
665     utype = lang_hooks.types.type_for_mode
666       (TYPE_MODE (TREE_TYPE (info.index_expr)), 1);
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
762 static bool
763 process_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
828 static unsigned int
829 do_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
876 static bool
877 switchconv_gate (void)
878 {
879   return flag_tree_switch_conversion != 0;
880 }
881
882 struct 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 };