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