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