xref: /dflybsd-src/contrib/gcc-4.7/gcc/tree-switch-conversion.c (revision 81fc95a5293ee307c688a350a3feb4734aaddbb4)
1e4b17023SJohn Marino /* Switch Conversion converts variable initializations based on switch
2e4b17023SJohn Marino    statements to initializations from a static array.
3e4b17023SJohn Marino    Copyright (C) 2006, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
4e4b17023SJohn Marino    Contributed by Martin Jambor <jamborm@suse.cz>
5e4b17023SJohn Marino 
6e4b17023SJohn Marino This file is part of GCC.
7e4b17023SJohn Marino 
8e4b17023SJohn Marino GCC is free software; you can redistribute it and/or modify it
9e4b17023SJohn Marino under the terms of the GNU General Public License as published by the
10e4b17023SJohn Marino Free Software Foundation; either version 3, or (at your option) any
11e4b17023SJohn Marino later version.
12e4b17023SJohn Marino 
13e4b17023SJohn Marino GCC is distributed in the hope that it will be useful, but WITHOUT
14e4b17023SJohn Marino ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15e4b17023SJohn Marino FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16e4b17023SJohn Marino for more details.
17e4b17023SJohn Marino 
18e4b17023SJohn Marino You should have received a copy of the GNU General Public License
19e4b17023SJohn Marino along with GCC; see the file COPYING3.  If not, write to the Free
20e4b17023SJohn Marino Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
21e4b17023SJohn Marino 02110-1301, USA.  */
22e4b17023SJohn Marino 
23e4b17023SJohn Marino /*
24e4b17023SJohn Marino      Switch initialization conversion
25e4b17023SJohn Marino 
26e4b17023SJohn Marino The following pass changes simple initializations of scalars in a switch
27e4b17023SJohn Marino statement into initializations from a static array.  Obviously, the values must
28e4b17023SJohn Marino be constant and known at compile time and a default branch must be
29e4b17023SJohn Marino provided.  For example, the following code:
30e4b17023SJohn Marino 
31e4b17023SJohn Marino         int a,b;
32e4b17023SJohn Marino 
33e4b17023SJohn Marino         switch (argc)
34e4b17023SJohn Marino 	{
35e4b17023SJohn Marino          case 1:
36e4b17023SJohn Marino          case 2:
37e4b17023SJohn Marino                 a_1 = 8;
38e4b17023SJohn Marino                 b_1 = 6;
39e4b17023SJohn Marino                 break;
40e4b17023SJohn Marino          case 3:
41e4b17023SJohn Marino                 a_2 = 9;
42e4b17023SJohn Marino                 b_2 = 5;
43e4b17023SJohn Marino                 break;
44e4b17023SJohn Marino          case 12:
45e4b17023SJohn Marino                 a_3 = 10;
46e4b17023SJohn Marino                 b_3 = 4;
47e4b17023SJohn Marino                 break;
48e4b17023SJohn Marino          default:
49e4b17023SJohn Marino                 a_4 = 16;
50e4b17023SJohn Marino                 b_4 = 1;
51e4b17023SJohn Marino         }
52e4b17023SJohn Marino 	a_5 = PHI <a_1, a_2, a_3, a_4>
53e4b17023SJohn Marino 	b_5 = PHI <b_1, b_2, b_3, b_4>
54e4b17023SJohn Marino 
55e4b17023SJohn Marino 
56e4b17023SJohn Marino is changed into:
57e4b17023SJohn Marino 
58e4b17023SJohn Marino         static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
59e4b17023SJohn Marino         static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
60e4b17023SJohn Marino                                  16, 16, 10};
61e4b17023SJohn Marino 
62e4b17023SJohn Marino         if (((unsigned) argc) - 1 < 11)
63e4b17023SJohn Marino           {
64e4b17023SJohn Marino 	    a_6 = CSWTCH02[argc - 1];
65e4b17023SJohn Marino             b_6 = CSWTCH01[argc - 1];
66e4b17023SJohn Marino 	  }
67e4b17023SJohn Marino 	else
68e4b17023SJohn Marino 	  {
69e4b17023SJohn Marino 	    a_7 = 16;
70e4b17023SJohn Marino 	    b_7 = 1;
71e4b17023SJohn Marino           }
72e4b17023SJohn Marino 	  a_5 = PHI <a_6, a_7>
73e4b17023SJohn Marino 	  b_b = PHI <b_6, b_7>
74e4b17023SJohn Marino 
75e4b17023SJohn Marino There are further constraints.  Specifically, the range of values across all
76e4b17023SJohn Marino case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
77e4b17023SJohn Marino eight) times the number of the actual switch branches. */
78e4b17023SJohn Marino 
79e4b17023SJohn Marino #include "config.h"
80e4b17023SJohn Marino #include "system.h"
81e4b17023SJohn Marino #include "coretypes.h"
82e4b17023SJohn Marino #include "tm.h"
83e4b17023SJohn Marino #include "line-map.h"
84e4b17023SJohn Marino #include "params.h"
85e4b17023SJohn Marino #include "flags.h"
86e4b17023SJohn Marino #include "tree.h"
87e4b17023SJohn Marino #include "basic-block.h"
88e4b17023SJohn Marino #include "tree-flow.h"
89e4b17023SJohn Marino #include "tree-flow-inline.h"
90e4b17023SJohn Marino #include "tree-ssa-operands.h"
91e4b17023SJohn Marino #include "output.h"
92e4b17023SJohn Marino #include "input.h"
93e4b17023SJohn Marino #include "tree-pass.h"
94e4b17023SJohn Marino #include "gimple-pretty-print.h"
95e4b17023SJohn Marino #include "tree-dump.h"
96e4b17023SJohn Marino #include "timevar.h"
97e4b17023SJohn Marino #include "langhooks.h"
98e4b17023SJohn Marino 
99e4b17023SJohn Marino /* The main structure of the pass.  */
100e4b17023SJohn Marino struct switch_conv_info
101e4b17023SJohn Marino {
102e4b17023SJohn Marino   /* The expression used to decide the switch branch.  (It is subsequently used
103e4b17023SJohn Marino      as the index to the created array.) */
104e4b17023SJohn Marino   tree index_expr;
105e4b17023SJohn Marino 
106e4b17023SJohn Marino   /* The following integer constants store the minimum value covered by the
107e4b17023SJohn Marino      cases.  */
108e4b17023SJohn Marino   tree range_min;
109e4b17023SJohn Marino 
110e4b17023SJohn Marino   /* The difference between the above two numbers, i.e. The size of the array
111e4b17023SJohn Marino      that would have to be created by the transformation.  */
112e4b17023SJohn Marino   tree range_size;
113e4b17023SJohn Marino 
114e4b17023SJohn Marino   /* Basic block that contains the actual SWITCH_EXPR.  */
115e4b17023SJohn Marino   basic_block switch_bb;
116e4b17023SJohn Marino 
117e4b17023SJohn Marino   /* All branches of the switch statement must have a single successor stored in
118e4b17023SJohn Marino      the following variable.  */
119e4b17023SJohn Marino   basic_block final_bb;
120e4b17023SJohn Marino 
121e4b17023SJohn Marino   /* Number of phi nodes in the final bb (that we'll be replacing).  */
122e4b17023SJohn Marino   int phi_count;
123e4b17023SJohn Marino 
124e4b17023SJohn Marino   /* Array of default values, in the same order as phi nodes.  */
125e4b17023SJohn Marino   tree *default_values;
126e4b17023SJohn Marino 
127e4b17023SJohn Marino   /* Constructors of new static arrays.  */
128e4b17023SJohn Marino   VEC (constructor_elt, gc) **constructors;
129e4b17023SJohn Marino 
130e4b17023SJohn Marino   /* Array of ssa names that are initialized with a value from a new static
131e4b17023SJohn Marino      array.  */
132e4b17023SJohn Marino   tree *target_inbound_names;
133e4b17023SJohn Marino 
134e4b17023SJohn Marino   /* Array of ssa names that are initialized with the default value if the
135e4b17023SJohn Marino      switch expression is out of range.  */
136e4b17023SJohn Marino   tree *target_outbound_names;
137e4b17023SJohn Marino 
138e4b17023SJohn Marino   /* The probability of the default edge in the replaced switch.  */
139e4b17023SJohn Marino   int default_prob;
140e4b17023SJohn Marino 
141e4b17023SJohn Marino   /* The count of the default edge in the replaced switch.  */
142e4b17023SJohn Marino   gcov_type default_count;
143e4b17023SJohn Marino 
144e4b17023SJohn Marino   /* Combined count of all other (non-default) edges in the replaced switch.  */
145e4b17023SJohn Marino   gcov_type other_count;
146e4b17023SJohn Marino 
147e4b17023SJohn Marino   /* The first load statement that loads a temporary from a new static array.
148e4b17023SJohn Marino    */
149e4b17023SJohn Marino   gimple arr_ref_first;
150e4b17023SJohn Marino 
151e4b17023SJohn Marino   /* The last load statement that loads a temporary from a new static array.  */
152e4b17023SJohn Marino   gimple arr_ref_last;
153e4b17023SJohn Marino 
154e4b17023SJohn Marino   /* String reason why the case wasn't a good candidate that is written to the
155e4b17023SJohn Marino      dump file, if there is one.  */
156e4b17023SJohn Marino   const char *reason;
157e4b17023SJohn Marino 
158e4b17023SJohn Marino   /* Parameters for expand_switch_using_bit_tests.  Should be computed
159e4b17023SJohn Marino      the same way as in expand_case.  */
160e4b17023SJohn Marino   unsigned int bit_test_uniq;
161e4b17023SJohn Marino   unsigned int bit_test_count;
162e4b17023SJohn Marino   basic_block bit_test_bb[2];
163e4b17023SJohn Marino };
164e4b17023SJohn Marino 
165e4b17023SJohn Marino /* Global pass info.  */
166e4b17023SJohn Marino static struct switch_conv_info info;
167e4b17023SJohn Marino 
168e4b17023SJohn Marino 
169e4b17023SJohn Marino /* Checks whether the range given by individual case statements of the SWTCH
170e4b17023SJohn Marino    switch statement isn't too big and whether the number of branches actually
171e4b17023SJohn Marino    satisfies the size of the new array.  */
172e4b17023SJohn Marino 
173e4b17023SJohn Marino static bool
check_range(gimple swtch)174e4b17023SJohn Marino check_range (gimple swtch)
175e4b17023SJohn Marino {
176e4b17023SJohn Marino   tree min_case, max_case;
177e4b17023SJohn Marino   unsigned int branch_num = gimple_switch_num_labels (swtch);
178e4b17023SJohn Marino   tree range_max;
179e4b17023SJohn Marino 
180e4b17023SJohn Marino   /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
181e4b17023SJohn Marino      is a default label which is the first in the vector.  */
182e4b17023SJohn Marino 
183e4b17023SJohn Marino   min_case = gimple_switch_label (swtch, 1);
184e4b17023SJohn Marino   info.range_min = CASE_LOW (min_case);
185e4b17023SJohn Marino 
186e4b17023SJohn Marino   gcc_assert (branch_num > 1);
187e4b17023SJohn Marino   gcc_assert (CASE_LOW (gimple_switch_label (swtch, 0)) == NULL_TREE);
188e4b17023SJohn Marino   max_case = gimple_switch_label (swtch, branch_num - 1);
189e4b17023SJohn Marino   if (CASE_HIGH (max_case) != NULL_TREE)
190e4b17023SJohn Marino     range_max = CASE_HIGH (max_case);
191e4b17023SJohn Marino   else
192e4b17023SJohn Marino     range_max = CASE_LOW (max_case);
193e4b17023SJohn Marino 
194e4b17023SJohn Marino   gcc_assert (info.range_min);
195e4b17023SJohn Marino   gcc_assert (range_max);
196e4b17023SJohn Marino 
197e4b17023SJohn Marino   info.range_size = int_const_binop (MINUS_EXPR, range_max, info.range_min);
198e4b17023SJohn Marino 
199e4b17023SJohn Marino   gcc_assert (info.range_size);
200e4b17023SJohn Marino   if (!host_integerp (info.range_size, 1))
201e4b17023SJohn Marino     {
202e4b17023SJohn Marino       info.reason = "index range way too large or otherwise unusable.\n";
203e4b17023SJohn Marino       return false;
204e4b17023SJohn Marino     }
205e4b17023SJohn Marino 
206e4b17023SJohn Marino   if ((unsigned HOST_WIDE_INT) tree_low_cst (info.range_size, 1)
207e4b17023SJohn Marino       > ((unsigned) branch_num * SWITCH_CONVERSION_BRANCH_RATIO))
208e4b17023SJohn Marino     {
209e4b17023SJohn Marino       info.reason = "the maximum range-branch ratio exceeded.\n";
210e4b17023SJohn Marino       return false;
211e4b17023SJohn Marino     }
212e4b17023SJohn Marino 
213e4b17023SJohn Marino   return true;
214e4b17023SJohn Marino }
215e4b17023SJohn Marino 
216e4b17023SJohn Marino /* Checks the given CS switch case whether it is suitable for conversion
217e4b17023SJohn Marino    (whether all but the default basic blocks are empty and so on).  If it is,
218e4b17023SJohn Marino    adds the case to the branch list along with values for the defined variables
219e4b17023SJohn Marino    and returns true.  Otherwise returns false.  */
220e4b17023SJohn Marino 
221e4b17023SJohn Marino static bool
check_process_case(tree cs)222e4b17023SJohn Marino check_process_case (tree cs)
223e4b17023SJohn Marino {
224e4b17023SJohn Marino   tree ldecl;
225e4b17023SJohn Marino   basic_block label_bb, following_bb;
226e4b17023SJohn Marino   edge e;
227e4b17023SJohn Marino 
228e4b17023SJohn Marino   ldecl = CASE_LABEL (cs);
229e4b17023SJohn Marino   label_bb = label_to_block (ldecl);
230e4b17023SJohn Marino 
231e4b17023SJohn Marino   e = find_edge (info.switch_bb, label_bb);
232e4b17023SJohn Marino   gcc_assert (e);
233e4b17023SJohn Marino 
234e4b17023SJohn Marino   if (CASE_LOW (cs) == NULL_TREE)
235e4b17023SJohn Marino     {
236e4b17023SJohn Marino       /* Default branch.  */
237e4b17023SJohn Marino       info.default_prob = e->probability;
238e4b17023SJohn Marino       info.default_count = e->count;
239e4b17023SJohn Marino     }
240e4b17023SJohn Marino   else
241e4b17023SJohn Marino     {
242e4b17023SJohn Marino       int i;
243e4b17023SJohn Marino       info.other_count += e->count;
244e4b17023SJohn Marino       for (i = 0; i < 2; i++)
245e4b17023SJohn Marino 	if (info.bit_test_bb[i] == label_bb)
246e4b17023SJohn Marino 	  break;
247e4b17023SJohn Marino 	else if (info.bit_test_bb[i] == NULL)
248e4b17023SJohn Marino 	  {
249e4b17023SJohn Marino 	    info.bit_test_bb[i] = label_bb;
250e4b17023SJohn Marino 	    info.bit_test_uniq++;
251e4b17023SJohn Marino 	    break;
252e4b17023SJohn Marino 	  }
253e4b17023SJohn Marino       if (i == 2)
254e4b17023SJohn Marino 	info.bit_test_uniq = 3;
255e4b17023SJohn Marino       if (CASE_HIGH (cs) != NULL_TREE
256e4b17023SJohn Marino 	  && ! tree_int_cst_equal (CASE_LOW (cs), CASE_HIGH (cs)))
257e4b17023SJohn Marino 	info.bit_test_count += 2;
258e4b17023SJohn Marino       else
259e4b17023SJohn Marino 	info.bit_test_count++;
260e4b17023SJohn Marino     }
261e4b17023SJohn Marino 
262e4b17023SJohn Marino   if (!label_bb)
263e4b17023SJohn Marino     {
264e4b17023SJohn Marino       info.reason = "  Bad case - cs BB  label is NULL\n";
265e4b17023SJohn Marino       return false;
266e4b17023SJohn Marino     }
267e4b17023SJohn Marino 
268e4b17023SJohn Marino   if (!single_pred_p (label_bb))
269e4b17023SJohn Marino     {
270e4b17023SJohn Marino       if (info.final_bb && info.final_bb != label_bb)
271e4b17023SJohn Marino 	{
272e4b17023SJohn Marino 	  info.reason = "  Bad case - a non-final BB has two predecessors\n";
273e4b17023SJohn Marino 	  return false; /* sth complex going on in this branch  */
274e4b17023SJohn Marino 	}
275e4b17023SJohn Marino 
276e4b17023SJohn Marino       following_bb = label_bb;
277e4b17023SJohn Marino     }
278e4b17023SJohn Marino   else
279e4b17023SJohn Marino     {
280e4b17023SJohn Marino       if (!empty_block_p (label_bb))
281e4b17023SJohn Marino 	{
282e4b17023SJohn Marino 	  info.reason = "  Bad case - a non-final BB not empty\n";
283e4b17023SJohn Marino 	  return false;
284e4b17023SJohn Marino 	}
285e4b17023SJohn Marino 
286*5ce9237cSJohn Marino       if (!single_succ_p (label_bb))
287*5ce9237cSJohn Marino 	{
288*5ce9237cSJohn Marino 	  info.reason
289*5ce9237cSJohn Marino 	    = "  Bad case - a non-final BB without a single successor\n";
290*5ce9237cSJohn Marino 	  return false;
291*5ce9237cSJohn Marino 	}
292e4b17023SJohn Marino       following_bb = single_succ (label_bb);
293e4b17023SJohn Marino     }
294e4b17023SJohn Marino 
295e4b17023SJohn Marino   if (!info.final_bb)
296e4b17023SJohn Marino     info.final_bb = following_bb;
297e4b17023SJohn Marino   else if (info.final_bb != following_bb)
298e4b17023SJohn Marino     {
299e4b17023SJohn Marino       info.reason = "  Bad case - different final BB\n";
300e4b17023SJohn Marino       return false; /* the only successor is not common for all the branches */
301e4b17023SJohn Marino     }
302e4b17023SJohn Marino 
303e4b17023SJohn Marino   return true;
304e4b17023SJohn Marino }
305e4b17023SJohn Marino 
306e4b17023SJohn Marino /* This function checks whether all required values in phi nodes in final_bb
307e4b17023SJohn Marino    are constants.  Required values are those that correspond to a basic block
308e4b17023SJohn Marino    which is a part of the examined switch statement.  It returns true if the
309e4b17023SJohn Marino    phi nodes are OK, otherwise false.  */
310e4b17023SJohn Marino 
311e4b17023SJohn Marino static bool
check_final_bb(void)312e4b17023SJohn Marino check_final_bb (void)
313e4b17023SJohn Marino {
314e4b17023SJohn Marino   gimple_stmt_iterator gsi;
315e4b17023SJohn Marino 
316e4b17023SJohn Marino   info.phi_count = 0;
317e4b17023SJohn Marino   for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
318e4b17023SJohn Marino     {
319e4b17023SJohn Marino       gimple phi = gsi_stmt (gsi);
320e4b17023SJohn Marino       unsigned int i;
321e4b17023SJohn Marino 
322e4b17023SJohn Marino       info.phi_count++;
323e4b17023SJohn Marino 
324e4b17023SJohn Marino       for (i = 0; i < gimple_phi_num_args (phi); i++)
325e4b17023SJohn Marino 	{
326e4b17023SJohn Marino 	  basic_block bb = gimple_phi_arg_edge (phi, i)->src;
327e4b17023SJohn Marino 
328e4b17023SJohn Marino 	  if (bb == info.switch_bb
329e4b17023SJohn Marino 	      || (single_pred_p (bb) && single_pred (bb) == info.switch_bb))
330e4b17023SJohn Marino 	    {
331e4b17023SJohn Marino 	      tree reloc, val;
332e4b17023SJohn Marino 
333e4b17023SJohn Marino 	      val = gimple_phi_arg_def (phi, i);
334e4b17023SJohn Marino 	      if (!is_gimple_ip_invariant (val))
335e4b17023SJohn Marino 		{
336e4b17023SJohn Marino 		  info.reason = "   Non-invariant value from a case\n";
337e4b17023SJohn Marino 		  return false; /* Non-invariant argument.  */
338e4b17023SJohn Marino 		}
339e4b17023SJohn Marino 	      reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
340e4b17023SJohn Marino 	      if ((flag_pic && reloc != null_pointer_node)
341e4b17023SJohn Marino 		  || (!flag_pic && reloc == NULL_TREE))
342e4b17023SJohn Marino 		{
343e4b17023SJohn Marino 		  if (reloc)
344e4b17023SJohn Marino 		    info.reason
345e4b17023SJohn Marino 		      = "   Value from a case would need runtime relocations\n";
346e4b17023SJohn Marino 		  else
347e4b17023SJohn Marino 		    info.reason
348e4b17023SJohn Marino 		      = "   Value from a case is not a valid initializer\n";
349e4b17023SJohn Marino 		  return false;
350e4b17023SJohn Marino 		}
351e4b17023SJohn Marino 	    }
352e4b17023SJohn Marino 	}
353e4b17023SJohn Marino     }
354e4b17023SJohn Marino 
355e4b17023SJohn Marino   return true;
356e4b17023SJohn Marino }
357e4b17023SJohn Marino 
358e4b17023SJohn Marino /* The following function allocates default_values, target_{in,out}_names and
359e4b17023SJohn Marino    constructors arrays.  The last one is also populated with pointers to
360e4b17023SJohn Marino    vectors that will become constructors of new arrays.  */
361e4b17023SJohn Marino 
362e4b17023SJohn Marino static void
create_temp_arrays(void)363e4b17023SJohn Marino create_temp_arrays (void)
364e4b17023SJohn Marino {
365e4b17023SJohn Marino   int i;
366e4b17023SJohn Marino 
367e4b17023SJohn Marino   info.default_values = XCNEWVEC (tree, info.phi_count * 3);
368e4b17023SJohn Marino   info.constructors = XCNEWVEC (VEC (constructor_elt, gc) *, info.phi_count);
369e4b17023SJohn Marino   info.target_inbound_names = info.default_values + info.phi_count;
370e4b17023SJohn Marino   info.target_outbound_names = info.target_inbound_names + info.phi_count;
371e4b17023SJohn Marino   for (i = 0; i < info.phi_count; i++)
372e4b17023SJohn Marino     info.constructors[i]
373e4b17023SJohn Marino       = VEC_alloc (constructor_elt, gc, tree_low_cst (info.range_size, 1) + 1);
374e4b17023SJohn Marino }
375e4b17023SJohn Marino 
376e4b17023SJohn Marino /* Free the arrays created by create_temp_arrays().  The vectors that are
377e4b17023SJohn Marino    created by that function are not freed here, however, because they have
378e4b17023SJohn Marino    already become constructors and must be preserved.  */
379e4b17023SJohn Marino 
380e4b17023SJohn Marino static void
free_temp_arrays(void)381e4b17023SJohn Marino free_temp_arrays (void)
382e4b17023SJohn Marino {
383e4b17023SJohn Marino   XDELETEVEC (info.constructors);
384e4b17023SJohn Marino   XDELETEVEC (info.default_values);
385e4b17023SJohn Marino }
386e4b17023SJohn Marino 
387e4b17023SJohn Marino /* Populate the array of default values in the order of phi nodes.
388e4b17023SJohn Marino    DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch.  */
389e4b17023SJohn Marino 
390e4b17023SJohn Marino static void
gather_default_values(tree default_case)391e4b17023SJohn Marino gather_default_values (tree default_case)
392e4b17023SJohn Marino {
393e4b17023SJohn Marino   gimple_stmt_iterator gsi;
394e4b17023SJohn Marino   basic_block bb = label_to_block (CASE_LABEL (default_case));
395e4b17023SJohn Marino   edge e;
396e4b17023SJohn Marino   int i = 0;
397e4b17023SJohn Marino 
398e4b17023SJohn Marino   gcc_assert (CASE_LOW (default_case) == NULL_TREE);
399e4b17023SJohn Marino 
400e4b17023SJohn Marino   if (bb == info.final_bb)
401e4b17023SJohn Marino     e = find_edge (info.switch_bb, bb);
402e4b17023SJohn Marino   else
403e4b17023SJohn Marino     e = single_succ_edge (bb);
404e4b17023SJohn Marino 
405e4b17023SJohn Marino   for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
406e4b17023SJohn Marino     {
407e4b17023SJohn Marino       gimple phi = gsi_stmt (gsi);
408e4b17023SJohn Marino       tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
409e4b17023SJohn Marino       gcc_assert (val);
410e4b17023SJohn Marino       info.default_values[i++] = val;
411e4b17023SJohn Marino     }
412e4b17023SJohn Marino }
413e4b17023SJohn Marino 
414e4b17023SJohn Marino /* The following function populates the vectors in the constructors array with
415e4b17023SJohn Marino    future contents of the static arrays.  The vectors are populated in the
416e4b17023SJohn Marino    order of phi nodes.  SWTCH is the switch statement being converted.  */
417e4b17023SJohn Marino 
418e4b17023SJohn Marino static void
build_constructors(gimple swtch)419e4b17023SJohn Marino build_constructors (gimple swtch)
420e4b17023SJohn Marino {
421e4b17023SJohn Marino   unsigned i, branch_num = gimple_switch_num_labels (swtch);
422e4b17023SJohn Marino   tree pos = info.range_min;
423e4b17023SJohn Marino 
424e4b17023SJohn Marino   for (i = 1; i < branch_num; i++)
425e4b17023SJohn Marino     {
426e4b17023SJohn Marino       tree cs = gimple_switch_label (swtch, i);
427e4b17023SJohn Marino       basic_block bb = label_to_block (CASE_LABEL (cs));
428e4b17023SJohn Marino       edge e;
429e4b17023SJohn Marino       tree high;
430e4b17023SJohn Marino       gimple_stmt_iterator gsi;
431e4b17023SJohn Marino       int j;
432e4b17023SJohn Marino 
433e4b17023SJohn Marino       if (bb == info.final_bb)
434e4b17023SJohn Marino 	e = find_edge (info.switch_bb, bb);
435e4b17023SJohn Marino       else
436e4b17023SJohn Marino 	e = single_succ_edge (bb);
437e4b17023SJohn Marino       gcc_assert (e);
438e4b17023SJohn Marino 
439e4b17023SJohn Marino       while (tree_int_cst_lt (pos, CASE_LOW (cs)))
440e4b17023SJohn Marino 	{
441e4b17023SJohn Marino 	  int k;
442e4b17023SJohn Marino 	  for (k = 0; k < info.phi_count; k++)
443e4b17023SJohn Marino 	    {
444e4b17023SJohn Marino 	      constructor_elt *elt;
445e4b17023SJohn Marino 
446e4b17023SJohn Marino 	      elt = VEC_quick_push (constructor_elt,
447e4b17023SJohn Marino 				    info.constructors[k], NULL);
448e4b17023SJohn Marino 	      elt->index = int_const_binop (MINUS_EXPR, pos,
449e4b17023SJohn Marino 					    info.range_min);
450e4b17023SJohn Marino 	      elt->value = info.default_values[k];
451e4b17023SJohn Marino 	    }
452e4b17023SJohn Marino 
453e4b17023SJohn Marino 	  pos = int_const_binop (PLUS_EXPR, pos, integer_one_node);
454e4b17023SJohn Marino 	}
455e4b17023SJohn Marino       gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
456e4b17023SJohn Marino 
457e4b17023SJohn Marino       j = 0;
458e4b17023SJohn Marino       if (CASE_HIGH (cs))
459e4b17023SJohn Marino 	high = CASE_HIGH (cs);
460e4b17023SJohn Marino       else
461e4b17023SJohn Marino 	high = CASE_LOW (cs);
462e4b17023SJohn Marino       for (gsi = gsi_start_phis (info.final_bb);
463e4b17023SJohn Marino 	   !gsi_end_p (gsi); gsi_next (&gsi))
464e4b17023SJohn Marino 	{
465e4b17023SJohn Marino 	  gimple phi = gsi_stmt (gsi);
466e4b17023SJohn Marino 	  tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
467e4b17023SJohn Marino 	  tree low = CASE_LOW (cs);
468e4b17023SJohn Marino 	  pos = CASE_LOW (cs);
469e4b17023SJohn Marino 
470e4b17023SJohn Marino 	  do
471e4b17023SJohn Marino 	    {
472e4b17023SJohn Marino 	      constructor_elt *elt;
473e4b17023SJohn Marino 
474e4b17023SJohn Marino 	      elt = VEC_quick_push (constructor_elt,
475e4b17023SJohn Marino 				    info.constructors[j], NULL);
476e4b17023SJohn Marino 	      elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min);
477e4b17023SJohn Marino 	      elt->value = val;
478e4b17023SJohn Marino 
479e4b17023SJohn Marino 	      pos = int_const_binop (PLUS_EXPR, pos, integer_one_node);
480e4b17023SJohn Marino 	    } while (!tree_int_cst_lt (high, pos)
481e4b17023SJohn Marino 		     && tree_int_cst_lt (low, pos));
482e4b17023SJohn Marino 	  j++;
483e4b17023SJohn Marino 	}
484e4b17023SJohn Marino     }
485e4b17023SJohn Marino }
486e4b17023SJohn Marino 
487e4b17023SJohn Marino /* If all values in the constructor vector are the same, return the value.
488e4b17023SJohn Marino    Otherwise return NULL_TREE.  Not supposed to be called for empty
489e4b17023SJohn Marino    vectors.  */
490e4b17023SJohn Marino 
491e4b17023SJohn Marino static tree
constructor_contains_same_values_p(VEC (constructor_elt,gc)* vec)492e4b17023SJohn Marino constructor_contains_same_values_p (VEC (constructor_elt, gc) *vec)
493e4b17023SJohn Marino {
494e4b17023SJohn Marino   unsigned int i;
495e4b17023SJohn Marino   tree prev = NULL_TREE;
496e4b17023SJohn Marino   constructor_elt *elt;
497e4b17023SJohn Marino 
498e4b17023SJohn Marino   FOR_EACH_VEC_ELT (constructor_elt, vec, i, elt)
499e4b17023SJohn Marino     {
500e4b17023SJohn Marino       if (!prev)
501e4b17023SJohn Marino 	prev = elt->value;
502e4b17023SJohn Marino       else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
503e4b17023SJohn Marino 	return NULL_TREE;
504e4b17023SJohn Marino     }
505e4b17023SJohn Marino   return prev;
506e4b17023SJohn Marino }
507e4b17023SJohn Marino 
508e4b17023SJohn Marino /* Return type which should be used for array elements, either TYPE,
509e4b17023SJohn Marino    or for integral type some smaller integral type that can still hold
510e4b17023SJohn Marino    all the constants.  */
511e4b17023SJohn Marino 
512e4b17023SJohn Marino static tree
array_value_type(gimple swtch,tree type,int num)513e4b17023SJohn Marino array_value_type (gimple swtch, tree type, int num)
514e4b17023SJohn Marino {
515e4b17023SJohn Marino   unsigned int i, len = VEC_length (constructor_elt, info.constructors[num]);
516e4b17023SJohn Marino   constructor_elt *elt;
517e4b17023SJohn Marino   enum machine_mode mode;
518e4b17023SJohn Marino   int sign = 0;
519e4b17023SJohn Marino   tree smaller_type;
520e4b17023SJohn Marino 
521e4b17023SJohn Marino   if (!INTEGRAL_TYPE_P (type))
522e4b17023SJohn Marino     return type;
523e4b17023SJohn Marino 
524e4b17023SJohn Marino   mode = GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type)));
525e4b17023SJohn Marino   if (GET_MODE_SIZE (TYPE_MODE (type)) <= GET_MODE_SIZE (mode))
526e4b17023SJohn Marino     return type;
527e4b17023SJohn Marino 
528e4b17023SJohn Marino   if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32))
529e4b17023SJohn Marino     return type;
530e4b17023SJohn Marino 
531e4b17023SJohn Marino   FOR_EACH_VEC_ELT (constructor_elt, info.constructors[num], i, elt)
532e4b17023SJohn Marino     {
533e4b17023SJohn Marino       double_int cst;
534e4b17023SJohn Marino 
535e4b17023SJohn Marino       if (TREE_CODE (elt->value) != INTEGER_CST)
536e4b17023SJohn Marino 	return type;
537e4b17023SJohn Marino 
538e4b17023SJohn Marino       cst = TREE_INT_CST (elt->value);
539e4b17023SJohn Marino       while (1)
540e4b17023SJohn Marino 	{
541e4b17023SJohn Marino 	  unsigned int prec = GET_MODE_BITSIZE (mode);
542e4b17023SJohn Marino 	  if (prec > HOST_BITS_PER_WIDE_INT)
543e4b17023SJohn Marino 	    return type;
544e4b17023SJohn Marino 
545e4b17023SJohn Marino 	  if (sign >= 0
546e4b17023SJohn Marino 	      && double_int_equal_p (cst, double_int_zext (cst, prec)))
547e4b17023SJohn Marino 	    {
548e4b17023SJohn Marino 	      if (sign == 0
549e4b17023SJohn Marino 		  && double_int_equal_p (cst, double_int_sext (cst, prec)))
550e4b17023SJohn Marino 		break;
551e4b17023SJohn Marino 	      sign = 1;
552e4b17023SJohn Marino 	      break;
553e4b17023SJohn Marino 	    }
554e4b17023SJohn Marino 	  if (sign <= 0
555e4b17023SJohn Marino 	      && double_int_equal_p (cst, double_int_sext (cst, prec)))
556e4b17023SJohn Marino 	    {
557e4b17023SJohn Marino 	      sign = -1;
558e4b17023SJohn Marino 	      break;
559e4b17023SJohn Marino 	    }
560e4b17023SJohn Marino 
561e4b17023SJohn Marino 	  if (sign == 1)
562e4b17023SJohn Marino 	    sign = 0;
563e4b17023SJohn Marino 
564e4b17023SJohn Marino 	  mode = GET_MODE_WIDER_MODE (mode);
565e4b17023SJohn Marino 	  if (mode == VOIDmode
566e4b17023SJohn Marino 	      || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (TYPE_MODE (type)))
567e4b17023SJohn Marino 	    return type;
568e4b17023SJohn Marino 	}
569e4b17023SJohn Marino     }
570e4b17023SJohn Marino 
571e4b17023SJohn Marino   if (sign == 0)
572e4b17023SJohn Marino     sign = TYPE_UNSIGNED (type) ? 1 : -1;
573e4b17023SJohn Marino   smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
574e4b17023SJohn Marino   if (GET_MODE_SIZE (TYPE_MODE (type))
575e4b17023SJohn Marino       <= GET_MODE_SIZE (TYPE_MODE (smaller_type)))
576e4b17023SJohn Marino     return type;
577e4b17023SJohn Marino 
578e4b17023SJohn Marino   return smaller_type;
579e4b17023SJohn Marino }
580e4b17023SJohn Marino 
581e4b17023SJohn Marino /* Create an appropriate array type and declaration and assemble a static array
582e4b17023SJohn Marino    variable.  Also create a load statement that initializes the variable in
583e4b17023SJohn Marino    question with a value from the static array.  SWTCH is the switch statement
584e4b17023SJohn Marino    being converted, NUM is the index to arrays of constructors, default values
585e4b17023SJohn Marino    and target SSA names for this particular array.  ARR_INDEX_TYPE is the type
586e4b17023SJohn Marino    of the index of the new array, PHI is the phi node of the final BB that
587e4b17023SJohn Marino    corresponds to the value that will be loaded from the created array.  TIDX
588e4b17023SJohn Marino    is an ssa name of a temporary variable holding the index for loads from the
589e4b17023SJohn Marino    new array.  */
590e4b17023SJohn Marino 
591e4b17023SJohn Marino static void
build_one_array(gimple swtch,int num,tree arr_index_type,gimple phi,tree tidx)592e4b17023SJohn Marino build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi,
593e4b17023SJohn Marino 		 tree tidx)
594e4b17023SJohn Marino {
595e4b17023SJohn Marino   tree name, cst;
596e4b17023SJohn Marino   gimple load;
597e4b17023SJohn Marino   gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
598e4b17023SJohn Marino   location_t loc = gimple_location (swtch);
599e4b17023SJohn Marino 
600e4b17023SJohn Marino   gcc_assert (info.default_values[num]);
601e4b17023SJohn Marino 
602e4b17023SJohn Marino   name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL);
603e4b17023SJohn Marino   info.target_inbound_names[num] = name;
604e4b17023SJohn Marino 
605e4b17023SJohn Marino   cst = constructor_contains_same_values_p (info.constructors[num]);
606e4b17023SJohn Marino   if (cst)
607e4b17023SJohn Marino     load = gimple_build_assign (name, cst);
608e4b17023SJohn Marino   else
609e4b17023SJohn Marino     {
610e4b17023SJohn Marino       tree array_type, ctor, decl, value_type, fetch, default_type;
611e4b17023SJohn Marino 
612e4b17023SJohn Marino       default_type = TREE_TYPE (info.default_values[num]);
613e4b17023SJohn Marino       value_type = array_value_type (swtch, default_type, num);
614e4b17023SJohn Marino       array_type = build_array_type (value_type, arr_index_type);
615e4b17023SJohn Marino       if (default_type != value_type)
616e4b17023SJohn Marino 	{
617e4b17023SJohn Marino 	  unsigned int i;
618e4b17023SJohn Marino 	  constructor_elt *elt;
619e4b17023SJohn Marino 
620e4b17023SJohn Marino 	  FOR_EACH_VEC_ELT (constructor_elt, info.constructors[num], i, elt)
621e4b17023SJohn Marino 	    elt->value = fold_convert (value_type, elt->value);
622e4b17023SJohn Marino 	}
623e4b17023SJohn Marino       ctor = build_constructor (array_type, info.constructors[num]);
624e4b17023SJohn Marino       TREE_CONSTANT (ctor) = true;
625e4b17023SJohn Marino       TREE_STATIC (ctor) = true;
626e4b17023SJohn Marino 
627e4b17023SJohn Marino       decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
628e4b17023SJohn Marino       TREE_STATIC (decl) = 1;
629e4b17023SJohn Marino       DECL_INITIAL (decl) = ctor;
630e4b17023SJohn Marino 
631e4b17023SJohn Marino       DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
632e4b17023SJohn Marino       DECL_ARTIFICIAL (decl) = 1;
633e4b17023SJohn Marino       TREE_CONSTANT (decl) = 1;
634e4b17023SJohn Marino       TREE_READONLY (decl) = 1;
635e4b17023SJohn Marino       add_referenced_var (decl);
636e4b17023SJohn Marino       varpool_mark_needed_node (varpool_node (decl));
637e4b17023SJohn Marino       varpool_finalize_decl (decl);
638e4b17023SJohn Marino 
639e4b17023SJohn Marino       fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
640e4b17023SJohn Marino 		      NULL_TREE);
641e4b17023SJohn Marino       if (default_type != value_type)
642e4b17023SJohn Marino 	{
643e4b17023SJohn Marino 	  fetch = fold_convert (default_type, fetch);
644e4b17023SJohn Marino 	  fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
645e4b17023SJohn Marino 					    true, GSI_SAME_STMT);
646e4b17023SJohn Marino 	}
647e4b17023SJohn Marino       load = gimple_build_assign (name, fetch);
648e4b17023SJohn Marino     }
649e4b17023SJohn Marino 
650e4b17023SJohn Marino   SSA_NAME_DEF_STMT (name) = load;
651e4b17023SJohn Marino   gsi_insert_before (&gsi, load, GSI_SAME_STMT);
652e4b17023SJohn Marino   update_stmt (load);
653e4b17023SJohn Marino   info.arr_ref_last = load;
654e4b17023SJohn Marino }
655e4b17023SJohn Marino 
656e4b17023SJohn Marino /* Builds and initializes static arrays initialized with values gathered from
657e4b17023SJohn Marino    the SWTCH switch statement.  Also creates statements that load values from
658e4b17023SJohn Marino    them.  */
659e4b17023SJohn Marino 
660e4b17023SJohn Marino static void
build_arrays(gimple swtch)661e4b17023SJohn Marino build_arrays (gimple swtch)
662e4b17023SJohn Marino {
663e4b17023SJohn Marino   tree arr_index_type;
664e4b17023SJohn Marino   tree tidx, sub, tmp, utype;
665e4b17023SJohn Marino   gimple stmt;
666e4b17023SJohn Marino   gimple_stmt_iterator gsi;
667e4b17023SJohn Marino   int i;
668e4b17023SJohn Marino   location_t loc = gimple_location (swtch);
669e4b17023SJohn Marino 
670e4b17023SJohn Marino   gsi = gsi_for_stmt (swtch);
671e4b17023SJohn Marino 
672e4b17023SJohn Marino   /* Make sure we do not generate arithmetics in a subrange.  */
673e4b17023SJohn Marino   utype = TREE_TYPE (info.index_expr);
674e4b17023SJohn Marino   if (TREE_TYPE (utype))
675e4b17023SJohn Marino     utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
676e4b17023SJohn Marino   else
677e4b17023SJohn Marino     utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
678e4b17023SJohn Marino 
679e4b17023SJohn Marino   arr_index_type = build_index_type (info.range_size);
680e4b17023SJohn Marino   tmp = create_tmp_var (utype, "csui");
681e4b17023SJohn Marino   add_referenced_var (tmp);
682e4b17023SJohn Marino   tidx = make_ssa_name (tmp, NULL);
683e4b17023SJohn Marino   sub = fold_build2_loc (loc, MINUS_EXPR, utype,
684e4b17023SJohn Marino 			 fold_convert_loc (loc, utype, info.index_expr),
685e4b17023SJohn Marino 			 fold_convert_loc (loc, utype, info.range_min));
686e4b17023SJohn Marino   sub = force_gimple_operand_gsi (&gsi, sub,
687e4b17023SJohn Marino 				  false, NULL, true, GSI_SAME_STMT);
688e4b17023SJohn Marino   stmt = gimple_build_assign (tidx, sub);
689e4b17023SJohn Marino   SSA_NAME_DEF_STMT (tidx) = stmt;
690e4b17023SJohn Marino 
691e4b17023SJohn Marino   gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
692e4b17023SJohn Marino   update_stmt (stmt);
693e4b17023SJohn Marino   info.arr_ref_first = stmt;
694e4b17023SJohn Marino 
695e4b17023SJohn Marino   for (gsi = gsi_start_phis (info.final_bb), i = 0;
696e4b17023SJohn Marino        !gsi_end_p (gsi); gsi_next (&gsi), i++)
697e4b17023SJohn Marino     build_one_array (swtch, i, arr_index_type, gsi_stmt (gsi), tidx);
698e4b17023SJohn Marino }
699e4b17023SJohn Marino 
700e4b17023SJohn Marino /* Generates and appropriately inserts loads of default values at the position
701e4b17023SJohn Marino    given by BSI.  Returns the last inserted statement.  */
702e4b17023SJohn Marino 
703e4b17023SJohn Marino static gimple
gen_def_assigns(gimple_stmt_iterator * gsi)704e4b17023SJohn Marino gen_def_assigns (gimple_stmt_iterator *gsi)
705e4b17023SJohn Marino {
706e4b17023SJohn Marino   int i;
707e4b17023SJohn Marino   gimple assign = NULL;
708e4b17023SJohn Marino 
709e4b17023SJohn Marino   for (i = 0; i < info.phi_count; i++)
710e4b17023SJohn Marino     {
711e4b17023SJohn Marino       tree name
712e4b17023SJohn Marino 	= make_ssa_name (SSA_NAME_VAR (info.target_inbound_names[i]), NULL);
713e4b17023SJohn Marino 
714e4b17023SJohn Marino       info.target_outbound_names[i] = name;
715e4b17023SJohn Marino       assign = gimple_build_assign (name, info.default_values[i]);
716e4b17023SJohn Marino       SSA_NAME_DEF_STMT (name) = assign;
717e4b17023SJohn Marino       gsi_insert_before (gsi, assign, GSI_SAME_STMT);
718e4b17023SJohn Marino       update_stmt (assign);
719e4b17023SJohn Marino     }
720e4b17023SJohn Marino   return assign;
721e4b17023SJohn Marino }
722e4b17023SJohn Marino 
723e4b17023SJohn Marino /* Deletes the unused bbs and edges that now contain the switch statement and
724e4b17023SJohn Marino    its empty branch bbs.  BBD is the now dead BB containing the original switch
725e4b17023SJohn Marino    statement, FINAL is the last BB of the converted switch statement (in terms
726e4b17023SJohn Marino    of succession).  */
727e4b17023SJohn Marino 
728e4b17023SJohn Marino static void
prune_bbs(basic_block bbd,basic_block final)729e4b17023SJohn Marino prune_bbs (basic_block bbd, basic_block final)
730e4b17023SJohn Marino {
731e4b17023SJohn Marino   edge_iterator ei;
732e4b17023SJohn Marino   edge e;
733e4b17023SJohn Marino 
734e4b17023SJohn Marino   for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
735e4b17023SJohn Marino     {
736e4b17023SJohn Marino       basic_block bb;
737e4b17023SJohn Marino       bb = e->dest;
738e4b17023SJohn Marino       remove_edge (e);
739e4b17023SJohn Marino       if (bb != final)
740e4b17023SJohn Marino 	delete_basic_block (bb);
741e4b17023SJohn Marino     }
742e4b17023SJohn Marino   delete_basic_block (bbd);
743e4b17023SJohn Marino }
744e4b17023SJohn Marino 
745e4b17023SJohn Marino /* Add values to phi nodes in final_bb for the two new edges.  E1F is the edge
746e4b17023SJohn Marino    from the basic block loading values from an array and E2F from the basic
747e4b17023SJohn Marino    block loading default values.  BBF is the last switch basic block (see the
748e4b17023SJohn Marino    bbf description in the comment below).  */
749e4b17023SJohn Marino 
750e4b17023SJohn Marino static void
fix_phi_nodes(edge e1f,edge e2f,basic_block bbf)751e4b17023SJohn Marino fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
752e4b17023SJohn Marino {
753e4b17023SJohn Marino   gimple_stmt_iterator gsi;
754e4b17023SJohn Marino   int i;
755e4b17023SJohn Marino 
756e4b17023SJohn Marino   for (gsi = gsi_start_phis (bbf), i = 0;
757e4b17023SJohn Marino        !gsi_end_p (gsi); gsi_next (&gsi), i++)
758e4b17023SJohn Marino     {
759e4b17023SJohn Marino       gimple phi = gsi_stmt (gsi);
760e4b17023SJohn Marino       add_phi_arg (phi, info.target_inbound_names[i], e1f, UNKNOWN_LOCATION);
761e4b17023SJohn Marino       add_phi_arg (phi, info.target_outbound_names[i], e2f, UNKNOWN_LOCATION);
762e4b17023SJohn Marino     }
763e4b17023SJohn Marino 
764e4b17023SJohn Marino }
765e4b17023SJohn Marino 
766e4b17023SJohn Marino /* Creates a check whether the switch expression value actually falls into the
767e4b17023SJohn Marino    range given by all the cases.  If it does not, the temporaries are loaded
768e4b17023SJohn Marino    with default values instead.  SWTCH is the switch statement being converted.
769e4b17023SJohn Marino 
770e4b17023SJohn Marino    bb0 is the bb with the switch statement, however, we'll end it with a
771e4b17023SJohn Marino        condition instead.
772e4b17023SJohn Marino 
773e4b17023SJohn Marino    bb1 is the bb to be used when the range check went ok.  It is derived from
774e4b17023SJohn Marino        the switch BB
775e4b17023SJohn Marino 
776e4b17023SJohn Marino    bb2 is the bb taken when the expression evaluated outside of the range
777e4b17023SJohn Marino        covered by the created arrays.  It is populated by loads of default
778e4b17023SJohn Marino        values.
779e4b17023SJohn Marino 
780e4b17023SJohn Marino    bbF is a fall through for both bb1 and bb2 and contains exactly what
781e4b17023SJohn Marino        originally followed the switch statement.
782e4b17023SJohn Marino 
783e4b17023SJohn Marino    bbD contains the switch statement (in the end).  It is unreachable but we
784e4b17023SJohn Marino        still need to strip off its edges.
785e4b17023SJohn Marino */
786e4b17023SJohn Marino 
787e4b17023SJohn Marino static void
gen_inbound_check(gimple swtch)788e4b17023SJohn Marino gen_inbound_check (gimple swtch)
789e4b17023SJohn Marino {
790e4b17023SJohn Marino   tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
791e4b17023SJohn Marino   tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
792e4b17023SJohn Marino   tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
793e4b17023SJohn Marino   gimple label1, label2, label3;
794e4b17023SJohn Marino   tree utype, tidx;
795e4b17023SJohn Marino   tree bound;
796e4b17023SJohn Marino 
797e4b17023SJohn Marino   gimple cond_stmt;
798e4b17023SJohn Marino 
799e4b17023SJohn Marino   gimple last_assign;
800e4b17023SJohn Marino   gimple_stmt_iterator gsi;
801e4b17023SJohn Marino   basic_block bb0, bb1, bb2, bbf, bbd;
802e4b17023SJohn Marino   edge e01, e02, e21, e1d, e1f, e2f;
803e4b17023SJohn Marino   location_t loc = gimple_location (swtch);
804e4b17023SJohn Marino 
805e4b17023SJohn Marino   gcc_assert (info.default_values);
806e4b17023SJohn Marino   bb0 = gimple_bb (swtch);
807e4b17023SJohn Marino 
808e4b17023SJohn Marino   tidx = gimple_assign_lhs (info.arr_ref_first);
809e4b17023SJohn Marino   utype = TREE_TYPE (tidx);
810e4b17023SJohn Marino 
811e4b17023SJohn Marino   /* (end of) block 0 */
812e4b17023SJohn Marino   gsi = gsi_for_stmt (info.arr_ref_first);
813e4b17023SJohn Marino   gsi_next (&gsi);
814e4b17023SJohn Marino 
815e4b17023SJohn Marino   bound = fold_convert_loc (loc, utype, info.range_size);
816e4b17023SJohn Marino   cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
817e4b17023SJohn Marino   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
818e4b17023SJohn Marino   update_stmt (cond_stmt);
819e4b17023SJohn Marino 
820e4b17023SJohn Marino   /* block 2 */
821e4b17023SJohn Marino   label2 = gimple_build_label (label_decl2);
822e4b17023SJohn Marino   gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
823e4b17023SJohn Marino   last_assign = gen_def_assigns (&gsi);
824e4b17023SJohn Marino 
825e4b17023SJohn Marino   /* block 1 */
826e4b17023SJohn Marino   label1 = gimple_build_label (label_decl1);
827e4b17023SJohn Marino   gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
828e4b17023SJohn Marino 
829e4b17023SJohn Marino   /* block F */
830e4b17023SJohn Marino   gsi = gsi_start_bb (info.final_bb);
831e4b17023SJohn Marino   label3 = gimple_build_label (label_decl3);
832e4b17023SJohn Marino   gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
833e4b17023SJohn Marino 
834e4b17023SJohn Marino   /* cfg fix */
835e4b17023SJohn Marino   e02 = split_block (bb0, cond_stmt);
836e4b17023SJohn Marino   bb2 = e02->dest;
837e4b17023SJohn Marino 
838e4b17023SJohn Marino   e21 = split_block (bb2, last_assign);
839e4b17023SJohn Marino   bb1 = e21->dest;
840e4b17023SJohn Marino   remove_edge (e21);
841e4b17023SJohn Marino 
842e4b17023SJohn Marino   e1d = split_block (bb1, info.arr_ref_last);
843e4b17023SJohn Marino   bbd = e1d->dest;
844e4b17023SJohn Marino   remove_edge (e1d);
845e4b17023SJohn Marino 
846e4b17023SJohn Marino   /* flags and profiles of the edge for in-range values */
847e4b17023SJohn Marino   e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
848e4b17023SJohn Marino   e01->probability = REG_BR_PROB_BASE - info.default_prob;
849e4b17023SJohn Marino   e01->count = info.other_count;
850e4b17023SJohn Marino 
851e4b17023SJohn Marino   /* flags and profiles of the edge taking care of out-of-range values */
852e4b17023SJohn Marino   e02->flags &= ~EDGE_FALLTHRU;
853e4b17023SJohn Marino   e02->flags |= EDGE_FALSE_VALUE;
854e4b17023SJohn Marino   e02->probability = info.default_prob;
855e4b17023SJohn Marino   e02->count = info.default_count;
856e4b17023SJohn Marino 
857e4b17023SJohn Marino   bbf = info.final_bb;
858e4b17023SJohn Marino 
859e4b17023SJohn Marino   e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
860e4b17023SJohn Marino   e1f->probability = REG_BR_PROB_BASE;
861e4b17023SJohn Marino   e1f->count = info.other_count;
862e4b17023SJohn Marino 
863e4b17023SJohn Marino   e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
864e4b17023SJohn Marino   e2f->probability = REG_BR_PROB_BASE;
865e4b17023SJohn Marino   e2f->count = info.default_count;
866e4b17023SJohn Marino 
867e4b17023SJohn Marino   /* frequencies of the new BBs */
868e4b17023SJohn Marino   bb1->frequency = EDGE_FREQUENCY (e01);
869e4b17023SJohn Marino   bb2->frequency = EDGE_FREQUENCY (e02);
870e4b17023SJohn Marino   bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
871e4b17023SJohn Marino 
872e4b17023SJohn Marino   prune_bbs (bbd, info.final_bb); /* To keep calc_dfs_tree() in dominance.c
873e4b17023SJohn Marino 				     happy.  */
874e4b17023SJohn Marino 
875e4b17023SJohn Marino   fix_phi_nodes (e1f, e2f, bbf);
876e4b17023SJohn Marino 
877e4b17023SJohn Marino   free_dominance_info (CDI_DOMINATORS);
878e4b17023SJohn Marino   free_dominance_info (CDI_POST_DOMINATORS);
879e4b17023SJohn Marino }
880e4b17023SJohn Marino 
881e4b17023SJohn Marino /* The following function is invoked on every switch statement (the current one
882e4b17023SJohn Marino    is given in SWTCH) and runs the individual phases of switch conversion on it
883e4b17023SJohn Marino    one after another until one fails or the conversion is completed.  */
884e4b17023SJohn Marino 
885e4b17023SJohn Marino static bool
process_switch(gimple swtch)886e4b17023SJohn Marino process_switch (gimple swtch)
887e4b17023SJohn Marino {
888e4b17023SJohn Marino   unsigned int i, branch_num = gimple_switch_num_labels (swtch);
889e4b17023SJohn Marino   tree index_type;
890e4b17023SJohn Marino 
891e4b17023SJohn Marino   /* Operand 2 is either NULL_TREE or a vector of cases (stmt.c).  */
892e4b17023SJohn Marino   if (branch_num < 2)
893e4b17023SJohn Marino     {
894e4b17023SJohn Marino       info.reason = "switch has no labels\n";
895e4b17023SJohn Marino       return false;
896e4b17023SJohn Marino     }
897e4b17023SJohn Marino 
898e4b17023SJohn Marino   info.final_bb = NULL;
899e4b17023SJohn Marino   info.switch_bb = gimple_bb (swtch);
900e4b17023SJohn Marino   info.index_expr = gimple_switch_index (swtch);
901e4b17023SJohn Marino   index_type = TREE_TYPE (info.index_expr);
902e4b17023SJohn Marino   info.arr_ref_first = NULL;
903e4b17023SJohn Marino   info.arr_ref_last = NULL;
904e4b17023SJohn Marino   info.default_prob = 0;
905e4b17023SJohn Marino   info.default_count = 0;
906e4b17023SJohn Marino   info.other_count = 0;
907e4b17023SJohn Marino   info.bit_test_uniq = 0;
908e4b17023SJohn Marino   info.bit_test_count = 0;
909e4b17023SJohn Marino   info.bit_test_bb[0] = NULL;
910e4b17023SJohn Marino   info.bit_test_bb[1] = NULL;
911e4b17023SJohn Marino 
912e4b17023SJohn Marino   /* An ERROR_MARK occurs for various reasons including invalid data type.
913e4b17023SJohn Marino      (comment from stmt.c) */
914e4b17023SJohn Marino   if (index_type == error_mark_node)
915e4b17023SJohn Marino     {
916e4b17023SJohn Marino       info.reason = "index error.\n";
917e4b17023SJohn Marino       return false;
918e4b17023SJohn Marino     }
919e4b17023SJohn Marino 
920e4b17023SJohn Marino   /* Check the case label values are within reasonable range:  */
921e4b17023SJohn Marino   if (!check_range (swtch))
922e4b17023SJohn Marino     return false;
923e4b17023SJohn Marino 
924e4b17023SJohn Marino   /* For all the cases, see whether they are empty, the assignments they
925e4b17023SJohn Marino      represent constant and so on...  */
926e4b17023SJohn Marino   for (i = 0; i < branch_num; i++)
927e4b17023SJohn Marino     if (!check_process_case (gimple_switch_label (swtch, i)))
928e4b17023SJohn Marino       {
929e4b17023SJohn Marino 	if (dump_file)
930e4b17023SJohn Marino 	  fprintf (dump_file, "Processing of case %i failed\n", i);
931e4b17023SJohn Marino 	return false;
932e4b17023SJohn Marino       }
933e4b17023SJohn Marino 
934e4b17023SJohn Marino   if (info.bit_test_uniq <= 2)
935e4b17023SJohn Marino     {
936e4b17023SJohn Marino       rtl_profile_for_bb (gimple_bb (swtch));
937e4b17023SJohn Marino       if (expand_switch_using_bit_tests_p (gimple_switch_index (swtch),
938e4b17023SJohn Marino 					   info.range_size, info.bit_test_uniq,
939e4b17023SJohn Marino 					   info.bit_test_count))
940e4b17023SJohn Marino 	{
941e4b17023SJohn Marino 	  info.reason = "  Expanding as bit test is preferable\n";
942e4b17023SJohn Marino 	  return false;
943e4b17023SJohn Marino 	}
944e4b17023SJohn Marino     }
945e4b17023SJohn Marino 
946e4b17023SJohn Marino   if (!check_final_bb ())
947e4b17023SJohn Marino     return false;
948e4b17023SJohn Marino 
949e4b17023SJohn Marino   /* At this point all checks have passed and we can proceed with the
950e4b17023SJohn Marino      transformation.  */
951e4b17023SJohn Marino 
952e4b17023SJohn Marino   create_temp_arrays ();
953e4b17023SJohn Marino   gather_default_values (gimple_switch_label (swtch, 0));
954e4b17023SJohn Marino   build_constructors (swtch);
955e4b17023SJohn Marino 
956e4b17023SJohn Marino   build_arrays (swtch); /* Build the static arrays and assignments.   */
957e4b17023SJohn Marino   gen_inbound_check (swtch);	/* Build the bounds check.  */
958e4b17023SJohn Marino 
959e4b17023SJohn Marino   /* Cleanup:  */
960e4b17023SJohn Marino   free_temp_arrays ();
961e4b17023SJohn Marino   return true;
962e4b17023SJohn Marino }
963e4b17023SJohn Marino 
964e4b17023SJohn Marino /* The main function of the pass scans statements for switches and invokes
965e4b17023SJohn Marino    process_switch on them.  */
966e4b17023SJohn Marino 
967e4b17023SJohn Marino static unsigned int
do_switchconv(void)968e4b17023SJohn Marino do_switchconv (void)
969e4b17023SJohn Marino {
970e4b17023SJohn Marino   basic_block bb;
971e4b17023SJohn Marino 
972e4b17023SJohn Marino   FOR_EACH_BB (bb)
973e4b17023SJohn Marino   {
974e4b17023SJohn Marino     gimple stmt = last_stmt (bb);
975e4b17023SJohn Marino     if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
976e4b17023SJohn Marino       {
977e4b17023SJohn Marino 	if (dump_file)
978e4b17023SJohn Marino 	  {
979e4b17023SJohn Marino 	    expanded_location loc = expand_location (gimple_location (stmt));
980e4b17023SJohn Marino 
981e4b17023SJohn Marino 	    fprintf (dump_file, "beginning to process the following "
982e4b17023SJohn Marino 		     "SWITCH statement (%s:%d) : ------- \n",
983e4b17023SJohn Marino 		     loc.file, loc.line);
984e4b17023SJohn Marino 	    print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
985e4b17023SJohn Marino 	    putc ('\n', dump_file);
986e4b17023SJohn Marino 	  }
987e4b17023SJohn Marino 
988e4b17023SJohn Marino 	info.reason = NULL;
989e4b17023SJohn Marino 	if (process_switch (stmt))
990e4b17023SJohn Marino 	  {
991e4b17023SJohn Marino 	    if (dump_file)
992e4b17023SJohn Marino 	      {
993e4b17023SJohn Marino 		fputs ("Switch converted\n", dump_file);
994e4b17023SJohn Marino 		fputs ("--------------------------------\n", dump_file);
995e4b17023SJohn Marino 	      }
996e4b17023SJohn Marino 	  }
997e4b17023SJohn Marino 	else
998e4b17023SJohn Marino 	  {
999e4b17023SJohn Marino 	    if (dump_file)
1000e4b17023SJohn Marino 	      {
1001e4b17023SJohn Marino 		gcc_assert (info.reason);
1002e4b17023SJohn Marino 		fputs ("Bailing out - ", dump_file);
1003e4b17023SJohn Marino 		fputs (info.reason, dump_file);
1004e4b17023SJohn Marino 		fputs ("--------------------------------\n", dump_file);
1005e4b17023SJohn Marino 	      }
1006e4b17023SJohn Marino 	  }
1007e4b17023SJohn Marino       }
1008e4b17023SJohn Marino   }
1009e4b17023SJohn Marino 
1010e4b17023SJohn Marino   return 0;
1011e4b17023SJohn Marino }
1012e4b17023SJohn Marino 
1013e4b17023SJohn Marino /* The pass gate. */
1014e4b17023SJohn Marino 
1015e4b17023SJohn Marino static bool
switchconv_gate(void)1016e4b17023SJohn Marino switchconv_gate (void)
1017e4b17023SJohn Marino {
1018e4b17023SJohn Marino   return flag_tree_switch_conversion != 0;
1019e4b17023SJohn Marino }
1020e4b17023SJohn Marino 
1021e4b17023SJohn Marino struct gimple_opt_pass pass_convert_switch =
1022e4b17023SJohn Marino {
1023e4b17023SJohn Marino  {
1024e4b17023SJohn Marino   GIMPLE_PASS,
1025e4b17023SJohn Marino   "switchconv",				/* name */
1026e4b17023SJohn Marino   switchconv_gate,			/* gate */
1027e4b17023SJohn Marino   do_switchconv,			/* execute */
1028e4b17023SJohn Marino   NULL,					/* sub */
1029e4b17023SJohn Marino   NULL,					/* next */
1030e4b17023SJohn Marino   0,					/* static_pass_number */
1031e4b17023SJohn Marino   TV_TREE_SWITCH_CONVERSION,		/* tv_id */
1032e4b17023SJohn Marino   PROP_cfg | PROP_ssa,	                /* properties_required */
1033e4b17023SJohn Marino   0,					/* properties_provided */
1034e4b17023SJohn Marino   0,					/* properties_destroyed */
1035e4b17023SJohn Marino   0,					/* todo_flags_start */
1036e4b17023SJohn Marino   TODO_update_ssa
1037e4b17023SJohn Marino   | TODO_ggc_collect | TODO_verify_ssa  /* todo_flags_finish */
1038e4b17023SJohn Marino  }
1039e4b17023SJohn Marino };
1040