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