Branch data Line data Source code
1 : : /* Lower GIMPLE_SWITCH expressions to something more efficient than
2 : : a jump table.
3 : : Copyright (C) 2006-2024 Free Software Foundation, Inc.
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify it
8 : : under the terms of the GNU General Public License as published by the
9 : : Free Software Foundation; either version 3, or (at your option) any
10 : : later version.
11 : :
12 : : GCC is distributed in the hope that it will be useful, but WITHOUT
13 : : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : : for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not, write to the Free
19 : : Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 : : 02110-1301, USA. */
21 : :
22 : : /* This file handles the lowering of GIMPLE_SWITCH to an indexed
23 : : load, or a series of bit-test-and-branch expressions. */
24 : :
25 : : #include "config.h"
26 : : #include "system.h"
27 : : #include "coretypes.h"
28 : : #include "backend.h"
29 : : #include "insn-codes.h"
30 : : #include "rtl.h"
31 : : #include "tree.h"
32 : : #include "gimple.h"
33 : : #include "cfghooks.h"
34 : : #include "tree-pass.h"
35 : : #include "ssa.h"
36 : : #include "optabs-tree.h"
37 : : #include "cgraph.h"
38 : : #include "gimple-pretty-print.h"
39 : : #include "fold-const.h"
40 : : #include "varasm.h"
41 : : #include "stor-layout.h"
42 : : #include "cfganal.h"
43 : : #include "gimplify.h"
44 : : #include "gimple-iterator.h"
45 : : #include "gimplify-me.h"
46 : : #include "gimple-fold.h"
47 : : #include "tree-cfg.h"
48 : : #include "cfgloop.h"
49 : : #include "alloc-pool.h"
50 : : #include "target.h"
51 : : #include "tree-into-ssa.h"
52 : : #include "omp-general.h"
53 : : #include "gimple-range.h"
54 : : #include "tree-cfgcleanup.h"
55 : :
56 : : /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
57 : : type in the GIMPLE type system that is language-independent? */
58 : : #include "langhooks.h"
59 : :
60 : : #include "tree-switch-conversion.h"
61 : :
62 : : using namespace tree_switch_conversion;
63 : :
64 : : /* Constructor. */
65 : :
66 : 26135 : switch_conversion::switch_conversion (): m_final_bb (NULL),
67 : 26135 : m_constructors (NULL), m_default_values (NULL),
68 : 26135 : m_arr_ref_first (NULL), m_arr_ref_last (NULL),
69 : 26135 : m_reason (NULL), m_default_case_nonstandard (false), m_cfg_altered (false)
70 : : {
71 : 26135 : }
72 : :
73 : : /* Collection information about SWTCH statement. */
74 : :
75 : : void
76 : 26135 : switch_conversion::collect (gswitch *swtch)
77 : : {
78 : 26135 : unsigned int branch_num = gimple_switch_num_labels (swtch);
79 : 26135 : tree min_case, max_case;
80 : 26135 : unsigned int i;
81 : 26135 : edge e, e_default, e_first;
82 : 26135 : edge_iterator ei;
83 : :
84 : 26135 : m_switch = swtch;
85 : :
86 : : /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
87 : : is a default label which is the first in the vector.
88 : : Collect the bits we can deduce from the CFG. */
89 : 26135 : m_index_expr = gimple_switch_index (swtch);
90 : 26135 : m_switch_bb = gimple_bb (swtch);
91 : 26135 : e_default = gimple_switch_default_edge (cfun, swtch);
92 : 26135 : m_default_bb = e_default->dest;
93 : 26135 : m_default_prob = e_default->probability;
94 : :
95 : : /* Get upper and lower bounds of case values, and the covered range. */
96 : 26135 : min_case = gimple_switch_label (swtch, 1);
97 : 26135 : max_case = gimple_switch_label (swtch, branch_num - 1);
98 : :
99 : 26135 : m_range_min = CASE_LOW (min_case);
100 : 26135 : if (CASE_HIGH (max_case) != NULL_TREE)
101 : 1939 : m_range_max = CASE_HIGH (max_case);
102 : : else
103 : 24196 : m_range_max = CASE_LOW (max_case);
104 : :
105 : 26135 : m_contiguous_range = true;
106 : 26135 : tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : m_range_min;
107 : 87398 : for (i = 2; i < branch_num; i++)
108 : : {
109 : 73687 : tree elt = gimple_switch_label (swtch, i);
110 : 73688 : if (wi::to_wide (last) + 1 != wi::to_wide (CASE_LOW (elt)))
111 : : {
112 : 12424 : m_contiguous_range = false;
113 : 12424 : break;
114 : : }
115 : 61263 : last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt);
116 : : }
117 : :
118 : 26135 : if (m_contiguous_range)
119 : 13711 : e_first = gimple_switch_edge (cfun, swtch, 1);
120 : : else
121 : : e_first = e_default;
122 : :
123 : : /* See if there is one common successor block for all branch
124 : : targets. If it exists, record it in FINAL_BB.
125 : : Start with the destination of the first non-default case
126 : : if the range is contiguous and default case otherwise as
127 : : guess or its destination in case it is a forwarder block. */
128 : 52270 : if (! single_pred_p (e_first->dest))
129 : 6343 : m_final_bb = e_first->dest;
130 : 19792 : else if (single_succ_p (e_first->dest)
131 : 28729 : && ! single_pred_p (single_succ (e_first->dest)))
132 : 11749 : m_final_bb = single_succ (e_first->dest);
133 : : /* Require that all switch destinations are either that common
134 : : FINAL_BB or a forwarder to it, except for the default
135 : : case if contiguous range. */
136 : 26135 : auto_vec<edge, 10> fw_edges;
137 : 26135 : m_uniq = 0;
138 : 26135 : if (m_final_bb)
139 : 90699 : FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
140 : : {
141 : 80512 : edge phi_e = nullptr;
142 : 80512 : if (e->dest == m_final_bb)
143 : 11000 : phi_e = e;
144 : 69512 : else if (single_pred_p (e->dest)
145 : 140974 : && single_succ_p (e->dest)
146 : 129974 : && single_succ (e->dest) == m_final_bb)
147 : 58484 : phi_e = single_succ_edge (e->dest);
148 : 80512 : if (phi_e)
149 : : {
150 : 69484 : if (e == e_default)
151 : : ;
152 : 54877 : else if (phi_e == e || empty_block_p (e->dest))
153 : : {
154 : : /* For empty blocks consider forwarders with equal
155 : : PHI arguments in m_final_bb as unique. */
156 : : unsigned i;
157 : 214372 : for (i = 0; i < fw_edges.length (); ++i)
158 : 92354 : if (phi_alternatives_equal (m_final_bb, fw_edges[i], phi_e))
159 : : break;
160 : 29740 : if (i == fw_edges.length ())
161 : : {
162 : : /* But limit the above possibly quadratic search. */
163 : 14832 : if (fw_edges.length () < 10)
164 : 6472 : fw_edges.quick_push (phi_e);
165 : 14832 : m_uniq++;
166 : : }
167 : : }
168 : : else
169 : 40007 : m_uniq++;
170 : 72607 : continue;
171 : 69484 : }
172 : :
173 : 11028 : if (e == e_default && m_contiguous_range)
174 : : {
175 : 3123 : m_default_case_nonstandard = true;
176 : 3123 : continue;
177 : : }
178 : :
179 : 7905 : m_final_bb = NULL;
180 : 7905 : break;
181 : : }
182 : :
183 : : /* When there's not a single common successor block conservatively
184 : : approximate the number of unique non-default targets. */
185 : 26135 : if (!m_final_bb)
186 : 31896 : m_uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
187 : :
188 : 26135 : m_range_size
189 : 26135 : = int_const_binop (MINUS_EXPR, m_range_max, m_range_min);
190 : :
191 : : /* Get a count of the number of case labels. Single-valued case labels
192 : : simply count as one, but a case range counts double, since it may
193 : : require two compares if it gets lowered as a branching tree. */
194 : 26135 : m_count = 0;
195 : 173518 : for (i = 1; i < branch_num; i++)
196 : : {
197 : 147383 : tree elt = gimple_switch_label (swtch, i);
198 : 147383 : m_count++;
199 : 147383 : if (CASE_HIGH (elt)
200 : 147383 : && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
201 : 10676 : m_count++;
202 : : }
203 : 26135 : }
204 : :
205 : : /* Checks whether the range given by individual case statements of the switch
206 : : switch statement isn't too big and whether the number of branches actually
207 : : satisfies the size of the new array. */
208 : :
209 : : bool
210 : 5907 : switch_conversion::check_range ()
211 : : {
212 : 5907 : gcc_assert (m_range_size);
213 : 5907 : if (!tree_fits_uhwi_p (m_range_size))
214 : : {
215 : 19 : m_reason = "index range way too large or otherwise unusable";
216 : 19 : return false;
217 : : }
218 : :
219 : 5888 : if (tree_to_uhwi (m_range_size)
220 : 5888 : > ((unsigned) m_count * param_switch_conversion_branch_ratio))
221 : : {
222 : 259 : m_reason = "the maximum range-branch ratio exceeded";
223 : 259 : return false;
224 : : }
225 : :
226 : : return true;
227 : : }
228 : :
229 : : /* Checks whether all but the final BB basic blocks are empty. */
230 : :
231 : : bool
232 : 5629 : switch_conversion::check_all_empty_except_final ()
233 : : {
234 : 5629 : edge e, e_default = find_edge (m_switch_bb, m_default_bb);
235 : 5629 : edge_iterator ei;
236 : :
237 : 19022 : FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
238 : : {
239 : 18319 : if (e->dest == m_final_bb)
240 : 4138 : continue;
241 : :
242 : 14181 : if (!empty_block_p (e->dest))
243 : : {
244 : 5863 : if (m_contiguous_range && e == e_default)
245 : : {
246 : 937 : m_default_case_nonstandard = true;
247 : 937 : continue;
248 : : }
249 : :
250 : 4926 : m_reason = "bad case - a non-final BB not empty";
251 : 4926 : return false;
252 : : }
253 : : }
254 : :
255 : : return true;
256 : : }
257 : :
258 : : /* This function checks whether all required values in phi nodes in final_bb
259 : : are constants. Required values are those that correspond to a basic block
260 : : which is a part of the examined switch statement. It returns true if the
261 : : phi nodes are OK, otherwise false. */
262 : :
263 : : bool
264 : 703 : switch_conversion::check_final_bb ()
265 : : {
266 : 703 : gphi_iterator gsi;
267 : :
268 : 703 : m_phi_count = 0;
269 : 1389 : for (gsi = gsi_start_phis (m_final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
270 : : {
271 : 773 : gphi *phi = gsi.phi ();
272 : 773 : unsigned int i;
273 : :
274 : 1546 : if (virtual_operand_p (gimple_phi_result (phi)))
275 : 17 : continue;
276 : :
277 : 756 : m_phi_count++;
278 : :
279 : 9483 : for (i = 0; i < gimple_phi_num_args (phi); i++)
280 : : {
281 : 8814 : basic_block bb = gimple_phi_arg_edge (phi, i)->src;
282 : :
283 : 8814 : if (bb == m_switch_bb
284 : 25584 : || (single_pred_p (bb)
285 : 8043 : && single_pred (bb) == m_switch_bb
286 : 7819 : && (!m_default_case_nonstandard
287 : 476 : || empty_block_p (bb))))
288 : : {
289 : 8549 : tree reloc, val;
290 : 8549 : const char *reason = NULL;
291 : :
292 : 8549 : val = gimple_phi_arg_def (phi, i);
293 : 8549 : if (!is_gimple_ip_invariant (val))
294 : : reason = "non-invariant value from a case";
295 : : else
296 : : {
297 : 8506 : reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
298 : 8506 : if ((flag_pic && reloc != null_pointer_node)
299 : 8445 : || (!flag_pic && reloc == NULL_TREE))
300 : : {
301 : 61 : if (reloc)
302 : : reason
303 : : = "value from a case would need runtime relocations";
304 : : else
305 : : reason
306 : : = "value from a case is not a valid initializer";
307 : : }
308 : : }
309 : : if (reason)
310 : : {
311 : : /* For contiguous range, we can allow non-constant
312 : : or one that needs relocation, as long as it is
313 : : only reachable from the default case. */
314 : 104 : if (bb == m_switch_bb)
315 : 88 : bb = m_final_bb;
316 : 104 : if (!m_contiguous_range || bb != m_default_bb)
317 : : {
318 : 87 : m_reason = reason;
319 : 87 : return false;
320 : : }
321 : :
322 : 17 : unsigned int branch_num = gimple_switch_num_labels (m_switch);
323 : 116 : for (unsigned int i = 1; i < branch_num; i++)
324 : : {
325 : 99 : if (gimple_switch_label_bb (cfun, m_switch, i) == bb)
326 : : {
327 : 0 : m_reason = reason;
328 : 0 : return false;
329 : : }
330 : : }
331 : 17 : m_default_case_nonstandard = true;
332 : : }
333 : : }
334 : : }
335 : : }
336 : :
337 : : return true;
338 : : }
339 : :
340 : : /* The following function allocates default_values, target_{in,out}_names and
341 : : constructors arrays. The last one is also populated with pointers to
342 : : vectors that will become constructors of new arrays. */
343 : :
344 : : void
345 : 616 : switch_conversion::create_temp_arrays ()
346 : : {
347 : 616 : int i;
348 : :
349 : 616 : m_default_values = XCNEWVEC (tree, m_phi_count * 3);
350 : : /* ??? Macros do not support multi argument templates in their
351 : : argument list. We create a typedef to work around that problem. */
352 : 616 : typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc;
353 : 616 : m_constructors = XCNEWVEC (vec_constructor_elt_gc, m_phi_count);
354 : 616 : m_target_inbound_names = m_default_values + m_phi_count;
355 : 616 : m_target_outbound_names = m_target_inbound_names + m_phi_count;
356 : 1283 : for (i = 0; i < m_phi_count; i++)
357 : 667 : vec_alloc (m_constructors[i], tree_to_uhwi (m_range_size) + 1);
358 : 616 : }
359 : :
360 : : /* Populate the array of default values in the order of phi nodes.
361 : : DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
362 : : if the range is non-contiguous or the default case has standard
363 : : structure, otherwise it is the first non-default case instead. */
364 : :
365 : : void
366 : 616 : switch_conversion::gather_default_values (tree default_case)
367 : : {
368 : 616 : gphi_iterator gsi;
369 : 616 : basic_block bb = label_to_block (cfun, CASE_LABEL (default_case));
370 : 616 : edge e;
371 : 616 : int i = 0;
372 : :
373 : 616 : gcc_assert (CASE_LOW (default_case) == NULL_TREE
374 : : || m_default_case_nonstandard);
375 : :
376 : 616 : if (bb == m_final_bb)
377 : 197 : e = find_edge (m_switch_bb, bb);
378 : : else
379 : 419 : e = single_succ_edge (bb);
380 : :
381 : 1300 : for (gsi = gsi_start_phis (m_final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
382 : : {
383 : 684 : gphi *phi = gsi.phi ();
384 : 1368 : if (virtual_operand_p (gimple_phi_result (phi)))
385 : 17 : continue;
386 : 667 : tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
387 : 667 : gcc_assert (val);
388 : 667 : m_default_values[i++] = val;
389 : : }
390 : 616 : }
391 : :
392 : : /* The following function populates the vectors in the constructors array with
393 : : future contents of the static arrays. The vectors are populated in the
394 : : order of phi nodes. */
395 : :
396 : : void
397 : 616 : switch_conversion::build_constructors ()
398 : : {
399 : 616 : unsigned i, branch_num = gimple_switch_num_labels (m_switch);
400 : 616 : tree pos = m_range_min;
401 : 616 : tree pos_one = build_int_cst (TREE_TYPE (pos), 1);
402 : :
403 : 8447 : for (i = 1; i < branch_num; i++)
404 : : {
405 : 7831 : tree cs = gimple_switch_label (m_switch, i);
406 : 7831 : basic_block bb = label_to_block (cfun, CASE_LABEL (cs));
407 : 7831 : edge e;
408 : 7831 : tree high;
409 : 7831 : gphi_iterator gsi;
410 : 7831 : int j;
411 : :
412 : 7831 : if (bb == m_final_bb)
413 : 492 : e = find_edge (m_switch_bb, bb);
414 : : else
415 : 7339 : e = single_succ_edge (bb);
416 : 7831 : gcc_assert (e);
417 : :
418 : 10541 : while (tree_int_cst_lt (pos, CASE_LOW (cs)))
419 : : {
420 : : int k;
421 : 6852 : for (k = 0; k < m_phi_count; k++)
422 : : {
423 : 4142 : constructor_elt elt;
424 : :
425 : 4142 : elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min);
426 : 4142 : if (TYPE_PRECISION (TREE_TYPE (elt.index))
427 : 4142 : > TYPE_PRECISION (sizetype))
428 : 18 : elt.index = fold_convert (sizetype, elt.index);
429 : 4142 : elt.value
430 : 4142 : = unshare_expr_without_location (m_default_values[k]);
431 : 4142 : m_constructors[k]->quick_push (elt);
432 : : }
433 : :
434 : 2710 : pos = int_const_binop (PLUS_EXPR, pos, pos_one);
435 : : }
436 : 7831 : gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
437 : :
438 : 7831 : j = 0;
439 : 7831 : if (CASE_HIGH (cs))
440 : 108 : high = CASE_HIGH (cs);
441 : : else
442 : 7723 : high = CASE_LOW (cs);
443 : 7831 : for (gsi = gsi_start_phis (m_final_bb);
444 : 16158 : !gsi_end_p (gsi); gsi_next (&gsi))
445 : : {
446 : 8327 : gphi *phi = gsi.phi ();
447 : 16654 : if (virtual_operand_p (gimple_phi_result (phi)))
448 : 72 : continue;
449 : 8255 : tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
450 : 8255 : tree low = CASE_LOW (cs);
451 : 8255 : pos = CASE_LOW (cs);
452 : :
453 : 8582 : do
454 : : {
455 : 8582 : constructor_elt elt;
456 : :
457 : 8582 : elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min);
458 : 8582 : if (TYPE_PRECISION (TREE_TYPE (elt.index))
459 : 8582 : > TYPE_PRECISION (sizetype))
460 : 3 : elt.index = fold_convert (sizetype, elt.index);
461 : 8582 : elt.value = unshare_expr_without_location (val);
462 : 8582 : m_constructors[j]->quick_push (elt);
463 : :
464 : 8582 : pos = int_const_binop (PLUS_EXPR, pos, pos_one);
465 : 8582 : } while (!tree_int_cst_lt (high, pos)
466 : 16837 : && tree_int_cst_lt (low, pos));
467 : 8255 : j++;
468 : : }
469 : : }
470 : 616 : }
471 : :
472 : : /* If all values in the constructor vector are products of a linear function
473 : : a * x + b, then return true. When true, COEFF_A and COEFF_B and
474 : : coefficients of the linear function. Note that equal values are special
475 : : case of a linear function with a and b equal to zero. */
476 : :
477 : : bool
478 : 667 : switch_conversion::contains_linear_function_p (vec<constructor_elt, va_gc> *vec,
479 : : wide_int *coeff_a,
480 : : wide_int *coeff_b)
481 : : {
482 : 667 : unsigned int i;
483 : 667 : constructor_elt *elt;
484 : :
485 : 667 : gcc_assert (vec->length () >= 2);
486 : :
487 : : /* Let's try to find any linear function a * x + y that can apply to
488 : : given values. 'a' can be calculated as follows:
489 : :
490 : : a = (y2 - y1) / (x2 - x1) where x2 - x1 = 1 (consecutive case indices)
491 : : a = y2 - y1
492 : :
493 : : and
494 : :
495 : : b = y2 - a * x2
496 : :
497 : : */
498 : :
499 : 667 : tree elt0 = (*vec)[0].value;
500 : 667 : tree elt1 = (*vec)[1].value;
501 : :
502 : 667 : if (TREE_CODE (elt0) != INTEGER_CST || TREE_CODE (elt1) != INTEGER_CST)
503 : : return false;
504 : :
505 : 460 : wide_int range_min
506 : 460 : = wide_int::from (wi::to_wide (m_range_min),
507 : 460 : TYPE_PRECISION (TREE_TYPE (elt0)),
508 : 1380 : TYPE_SIGN (TREE_TYPE (m_range_min)));
509 : 460 : wide_int y1 = wi::to_wide (elt0);
510 : 460 : wide_int y2 = wi::to_wide (elt1);
511 : 460 : wide_int a = y2 - y1;
512 : 460 : wide_int b = y2 - a * (range_min + 1);
513 : :
514 : : /* Verify that all values fulfill the linear function. */
515 : 1811 : FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
516 : : {
517 : 1735 : if (TREE_CODE (elt->value) != INTEGER_CST)
518 : 384 : return false;
519 : :
520 : 1735 : wide_int value = wi::to_wide (elt->value);
521 : 1735 : if (a * range_min + b != value)
522 : 384 : return false;
523 : :
524 : 1351 : ++range_min;
525 : 1735 : }
526 : :
527 : 76 : *coeff_a = a;
528 : 76 : *coeff_b = b;
529 : :
530 : 76 : return true;
531 : 460 : }
532 : :
533 : : /* Return type which should be used for array elements, either TYPE's
534 : : main variant or, for integral types, some smaller integral type
535 : : that can still hold all the constants. */
536 : :
537 : : tree
538 : 591 : switch_conversion::array_value_type (tree type, int num)
539 : : {
540 : 591 : unsigned int i, len = vec_safe_length (m_constructors[num]);
541 : 591 : constructor_elt *elt;
542 : 591 : int sign = 0;
543 : 591 : tree smaller_type;
544 : :
545 : : /* Types with alignments greater than their size can reach here, e.g. out of
546 : : SRA. We couldn't use these as an array component type so get back to the
547 : : main variant first, which, for our purposes, is fine for other types as
548 : : well. */
549 : :
550 : 591 : type = TYPE_MAIN_VARIANT (type);
551 : :
552 : 591 : if (!INTEGRAL_TYPE_P (type)
553 : 591 : || (TREE_CODE (type) == BITINT_TYPE
554 : 0 : && (TYPE_PRECISION (type) > MAX_FIXED_MODE_SIZE
555 : 0 : || TYPE_MODE (type) == BLKmode)))
556 : 207 : return type;
557 : :
558 : 384 : scalar_int_mode type_mode = SCALAR_INT_TYPE_MODE (type);
559 : 384 : scalar_int_mode mode = get_narrowest_mode (type_mode);
560 : 1152 : if (GET_MODE_SIZE (type_mode) <= GET_MODE_SIZE (mode))
561 : : return type;
562 : :
563 : 716 : if (len < (optimize_bb_for_size_p (gimple_bb (m_switch)) ? 2 : 32))
564 : : return type;
565 : :
566 : 2642 : FOR_EACH_VEC_SAFE_ELT (m_constructors[num], i, elt)
567 : : {
568 : 2589 : wide_int cst;
569 : :
570 : 2589 : if (TREE_CODE (elt->value) != INTEGER_CST)
571 : : return type;
572 : :
573 : 2589 : cst = wi::to_wide (elt->value);
574 : 2610 : while (1)
575 : : {
576 : 2610 : unsigned int prec = GET_MODE_BITSIZE (mode);
577 : 2610 : if (prec > HOST_BITS_PER_WIDE_INT)
578 : : return type;
579 : :
580 : 2610 : if (sign >= 0 && cst == wi::zext (cst, prec))
581 : : {
582 : 1411 : if (sign == 0 && cst == wi::sext (cst, prec))
583 : : break;
584 : 457 : sign = 1;
585 : 457 : break;
586 : : }
587 : 1199 : if (sign <= 0 && cst == wi::sext (cst, prec))
588 : : {
589 : : sign = -1;
590 : : break;
591 : : }
592 : :
593 : 23 : if (sign == 1)
594 : 6 : sign = 0;
595 : :
596 : 46 : if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
597 : 69 : || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (type_mode))
598 : : return type;
599 : : }
600 : 2589 : }
601 : :
602 : 53 : if (sign == 0)
603 : 28 : sign = TYPE_UNSIGNED (type) ? 1 : -1;
604 : 53 : smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
605 : 53 : if (GET_MODE_SIZE (type_mode)
606 : 106 : <= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (smaller_type)))
607 : : return type;
608 : :
609 : : return smaller_type;
610 : : }
611 : :
612 : : /* Create an appropriate array type and declaration and assemble a static
613 : : array variable. Also create a load statement that initializes
614 : : the variable in question with a value from the static array. SWTCH is
615 : : the switch statement being converted, NUM is the index to
616 : : arrays of constructors, default values and target SSA names
617 : : for this particular array. ARR_INDEX_TYPE is the type of the index
618 : : of the new array, PHI is the phi node of the final BB that corresponds
619 : : to the value that will be loaded from the created array. TIDX
620 : : is an ssa name of a temporary variable holding the index for loads from the
621 : : new array. */
622 : :
623 : : void
624 : 667 : switch_conversion::build_one_array (int num, tree arr_index_type,
625 : : gphi *phi, tree tidx)
626 : : {
627 : 667 : tree name;
628 : 667 : gimple *load;
629 : 667 : gimple_stmt_iterator gsi = gsi_for_stmt (m_switch);
630 : 667 : location_t loc = gimple_location (m_switch);
631 : :
632 : 667 : gcc_assert (m_default_values[num]);
633 : :
634 : 667 : name = copy_ssa_name (PHI_RESULT (phi));
635 : 667 : m_target_inbound_names[num] = name;
636 : :
637 : 667 : vec<constructor_elt, va_gc> *constructor = m_constructors[num];
638 : 667 : wide_int coeff_a, coeff_b;
639 : 667 : bool linear_p = contains_linear_function_p (constructor, &coeff_a, &coeff_b);
640 : 667 : tree type;
641 : 667 : if (linear_p
642 : 667 : && (type = range_check_type (TREE_TYPE ((*constructor)[0].value))))
643 : : {
644 : 83 : if (dump_file && coeff_a.to_uhwi () > 0)
645 : 6 : fprintf (dump_file, "Linear transformation with A = %" PRId64
646 : : " and B = %" PRId64 "\n", coeff_a.to_shwi (),
647 : : coeff_b.to_shwi ());
648 : :
649 : : /* We must use type of constructor values. */
650 : 76 : gimple_seq seq = NULL;
651 : 76 : tree tmp = gimple_convert (&seq, type, m_index_expr);
652 : 76 : tree tmp2 = gimple_build (&seq, MULT_EXPR, type,
653 : : wide_int_to_tree (type, coeff_a), tmp);
654 : 76 : tree tmp3 = gimple_build (&seq, PLUS_EXPR, type, tmp2,
655 : : wide_int_to_tree (type, coeff_b));
656 : 76 : tree tmp4 = gimple_convert (&seq, TREE_TYPE (name), tmp3);
657 : 76 : gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
658 : 76 : load = gimple_build_assign (name, tmp4);
659 : : }
660 : : else
661 : : {
662 : 591 : tree array_type, ctor, decl, value_type, fetch, default_type;
663 : :
664 : 591 : default_type = TREE_TYPE (m_default_values[num]);
665 : 591 : value_type = array_value_type (default_type, num);
666 : 591 : array_type = build_array_type (value_type, arr_index_type);
667 : 591 : if (default_type != value_type)
668 : : {
669 : : unsigned int i;
670 : : constructor_elt *elt;
671 : :
672 : 3254 : FOR_EACH_VEC_SAFE_ELT (constructor, i, elt)
673 : 3144 : elt->value = fold_convert (value_type, elt->value);
674 : : }
675 : 591 : ctor = build_constructor (array_type, constructor);
676 : 591 : TREE_CONSTANT (ctor) = true;
677 : 591 : TREE_STATIC (ctor) = true;
678 : :
679 : 591 : decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
680 : 591 : TREE_STATIC (decl) = 1;
681 : 591 : DECL_INITIAL (decl) = ctor;
682 : :
683 : 591 : DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
684 : 591 : DECL_ARTIFICIAL (decl) = 1;
685 : 591 : DECL_IGNORED_P (decl) = 1;
686 : 591 : TREE_CONSTANT (decl) = 1;
687 : 591 : TREE_READONLY (decl) = 1;
688 : 591 : DECL_IGNORED_P (decl) = 1;
689 : 591 : if (offloading_function_p (cfun->decl))
690 : 0 : DECL_ATTRIBUTES (decl)
691 : 0 : = tree_cons (get_identifier ("omp declare target"), NULL_TREE,
692 : : NULL_TREE);
693 : 591 : varpool_node::finalize_decl (decl);
694 : :
695 : 591 : fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
696 : : NULL_TREE);
697 : 591 : if (default_type != value_type)
698 : : {
699 : 110 : fetch = fold_convert (default_type, fetch);
700 : 110 : fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
701 : : true, GSI_SAME_STMT);
702 : : }
703 : 591 : load = gimple_build_assign (name, fetch);
704 : : }
705 : :
706 : 667 : gsi_insert_before (&gsi, load, GSI_SAME_STMT);
707 : 667 : update_stmt (load);
708 : 667 : m_arr_ref_last = load;
709 : 667 : }
710 : :
711 : : /* Builds and initializes static arrays initialized with values gathered from
712 : : the switch statement. Also creates statements that load values from
713 : : them. */
714 : :
715 : : void
716 : 616 : switch_conversion::build_arrays ()
717 : : {
718 : 616 : tree arr_index_type;
719 : 616 : tree tidx, sub, utype, tidxtype;
720 : 616 : gimple *stmt;
721 : 616 : gimple_stmt_iterator gsi;
722 : 616 : gphi_iterator gpi;
723 : 616 : int i;
724 : 616 : location_t loc = gimple_location (m_switch);
725 : :
726 : 616 : gsi = gsi_for_stmt (m_switch);
727 : :
728 : : /* Make sure we do not generate arithmetics in a subrange. */
729 : 616 : utype = TREE_TYPE (m_index_expr);
730 : 616 : if (TREE_TYPE (utype))
731 : 48 : utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
732 : 568 : else if (TREE_CODE (utype) == BITINT_TYPE
733 : 569 : && (TYPE_PRECISION (utype) > MAX_FIXED_MODE_SIZE
734 : 0 : || TYPE_MODE (utype) == BLKmode))
735 : 1 : utype = unsigned_type_for (utype);
736 : : else
737 : 567 : utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
738 : 616 : if (TYPE_PRECISION (utype) > TYPE_PRECISION (sizetype))
739 : 1 : tidxtype = sizetype;
740 : : else
741 : : tidxtype = utype;
742 : :
743 : 616 : arr_index_type = build_index_type (m_range_size);
744 : 616 : tidx = make_ssa_name (tidxtype);
745 : 616 : sub = fold_build2_loc (loc, MINUS_EXPR, utype,
746 : : fold_convert_loc (loc, utype, m_index_expr),
747 : : fold_convert_loc (loc, utype, m_range_min));
748 : 616 : sub = fold_convert (tidxtype, sub);
749 : 616 : sub = force_gimple_operand_gsi (&gsi, sub,
750 : : false, NULL, true, GSI_SAME_STMT);
751 : 616 : stmt = gimple_build_assign (tidx, sub);
752 : :
753 : 616 : gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
754 : 616 : update_stmt (stmt);
755 : 616 : m_arr_ref_first = stmt;
756 : :
757 : 616 : for (gpi = gsi_start_phis (m_final_bb), i = 0;
758 : 1300 : !gsi_end_p (gpi); gsi_next (&gpi))
759 : : {
760 : 684 : gphi *phi = gpi.phi ();
761 : 1368 : if (!virtual_operand_p (gimple_phi_result (phi)))
762 : 667 : build_one_array (i++, arr_index_type, phi, tidx);
763 : : else
764 : : {
765 : 17 : edge e;
766 : 17 : edge_iterator ei;
767 : 21 : FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
768 : : {
769 : 21 : if (e->dest == m_final_bb)
770 : : break;
771 : 11 : if (!m_default_case_nonstandard
772 : 4 : || e->dest != m_default_bb)
773 : : {
774 : 7 : e = single_succ_edge (e->dest);
775 : 7 : break;
776 : : }
777 : : }
778 : 17 : gcc_assert (e && e->dest == m_final_bb);
779 : 17 : m_target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e);
780 : : }
781 : : }
782 : 616 : }
783 : :
784 : : /* Generates and appropriately inserts loads of default values at the position
785 : : given by GSI. Returns the last inserted statement. */
786 : :
787 : : gassign *
788 : 513 : switch_conversion::gen_def_assigns (gimple_stmt_iterator *gsi)
789 : : {
790 : 513 : int i;
791 : 513 : gassign *assign = NULL;
792 : :
793 : 1067 : for (i = 0; i < m_phi_count; i++)
794 : : {
795 : 554 : tree name = copy_ssa_name (m_target_inbound_names[i]);
796 : 554 : m_target_outbound_names[i] = name;
797 : 554 : assign = gimple_build_assign (name, m_default_values[i]);
798 : 554 : gsi_insert_before (gsi, assign, GSI_SAME_STMT);
799 : 554 : update_stmt (assign);
800 : : }
801 : 513 : return assign;
802 : : }
803 : :
804 : : /* Deletes the unused bbs and edges that now contain the switch statement and
805 : : its empty branch bbs. BBD is the now dead BB containing
806 : : the original switch statement, FINAL is the last BB of the converted
807 : : switch statement (in terms of succession). */
808 : :
809 : : void
810 : 616 : switch_conversion::prune_bbs (basic_block bbd, basic_block final,
811 : : basic_block default_bb)
812 : : {
813 : 616 : edge_iterator ei;
814 : 616 : edge e;
815 : :
816 : 9538 : for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
817 : : {
818 : 8306 : basic_block bb;
819 : 8306 : bb = e->dest;
820 : 8306 : remove_edge (e);
821 : 8306 : if (bb != final && bb != default_bb)
822 : 7607 : delete_basic_block (bb);
823 : : }
824 : 616 : delete_basic_block (bbd);
825 : 616 : }
826 : :
827 : : /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
828 : : from the basic block loading values from an array and E2F from the basic
829 : : block loading default values. BBF is the last switch basic block (see the
830 : : bbf description in the comment below). */
831 : :
832 : : void
833 : 616 : switch_conversion::fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
834 : : {
835 : 616 : gphi_iterator gsi;
836 : 616 : int i;
837 : :
838 : 616 : for (gsi = gsi_start_phis (bbf), i = 0;
839 : 1300 : !gsi_end_p (gsi); gsi_next (&gsi))
840 : : {
841 : 684 : gphi *phi = gsi.phi ();
842 : 684 : tree inbound, outbound;
843 : 1368 : if (virtual_operand_p (gimple_phi_result (phi)))
844 : 17 : inbound = outbound = m_target_vop;
845 : : else
846 : : {
847 : 667 : inbound = m_target_inbound_names[i];
848 : 667 : outbound = m_target_outbound_names[i++];
849 : : }
850 : 684 : add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION);
851 : 684 : if (!m_default_case_nonstandard)
852 : 567 : add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION);
853 : : }
854 : 616 : }
855 : :
856 : : /* Creates a check whether the switch expression value actually falls into the
857 : : range given by all the cases. If it does not, the temporaries are loaded
858 : : with default values instead. */
859 : :
860 : : void
861 : 616 : switch_conversion::gen_inbound_check ()
862 : : {
863 : 616 : tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
864 : 616 : tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
865 : 616 : tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
866 : 616 : glabel *label1, *label2, *label3;
867 : 616 : tree utype, tidx;
868 : 616 : tree bound;
869 : :
870 : 616 : gcond *cond_stmt;
871 : :
872 : 616 : gassign *last_assign = NULL;
873 : 616 : gimple_stmt_iterator gsi;
874 : 616 : basic_block bb0, bb1, bb2, bbf, bbd;
875 : 616 : edge e01 = NULL, e02, e21, e1d, e1f, e2f;
876 : 616 : location_t loc = gimple_location (m_switch);
877 : :
878 : 616 : gcc_assert (m_default_values);
879 : :
880 : 616 : bb0 = gimple_bb (m_switch);
881 : :
882 : 616 : tidx = gimple_assign_lhs (m_arr_ref_first);
883 : 616 : utype = TREE_TYPE (tidx);
884 : :
885 : : /* (end of) block 0 */
886 : 616 : gsi = gsi_for_stmt (m_arr_ref_first);
887 : 616 : gsi_next (&gsi);
888 : :
889 : 616 : bound = fold_convert_loc (loc, utype, m_range_size);
890 : 616 : cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
891 : 616 : gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
892 : 616 : update_stmt (cond_stmt);
893 : :
894 : : /* block 2 */
895 : 616 : if (!m_default_case_nonstandard)
896 : : {
897 : 513 : label2 = gimple_build_label (label_decl2);
898 : 513 : gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
899 : 513 : last_assign = gen_def_assigns (&gsi);
900 : : }
901 : :
902 : : /* block 1 */
903 : 616 : label1 = gimple_build_label (label_decl1);
904 : 616 : gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
905 : :
906 : : /* block F */
907 : 616 : gsi = gsi_start_bb (m_final_bb);
908 : 616 : label3 = gimple_build_label (label_decl3);
909 : 616 : gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
910 : :
911 : : /* cfg fix */
912 : 616 : e02 = split_block (bb0, cond_stmt);
913 : 616 : bb2 = e02->dest;
914 : :
915 : 616 : if (m_default_case_nonstandard)
916 : : {
917 : 103 : bb1 = bb2;
918 : 103 : bb2 = m_default_bb;
919 : 103 : e01 = e02;
920 : 103 : e01->flags = EDGE_TRUE_VALUE;
921 : 103 : e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE);
922 : 103 : edge e_default = find_edge (bb1, bb2);
923 : 103 : for (gphi_iterator gsi = gsi_start_phis (bb2);
924 : 130 : !gsi_end_p (gsi); gsi_next (&gsi))
925 : : {
926 : 27 : gphi *phi = gsi.phi ();
927 : 27 : tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_default);
928 : 27 : add_phi_arg (phi, arg, e02,
929 : : gimple_phi_arg_location_from_edge (phi, e_default));
930 : : }
931 : : /* Partially fix the dominator tree, if it is available. */
932 : 103 : if (dom_info_available_p (CDI_DOMINATORS))
933 : 103 : redirect_immediate_dominators (CDI_DOMINATORS, bb1, bb0);
934 : : }
935 : : else
936 : : {
937 : 513 : e21 = split_block (bb2, last_assign);
938 : 513 : bb1 = e21->dest;
939 : 513 : remove_edge (e21);
940 : : }
941 : :
942 : 616 : e1d = split_block (bb1, m_arr_ref_last);
943 : 616 : bbd = e1d->dest;
944 : 616 : remove_edge (e1d);
945 : :
946 : : /* Flags and profiles of the edge for in-range values. */
947 : 616 : if (!m_default_case_nonstandard)
948 : 513 : e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
949 : 616 : e01->probability = m_default_prob.invert ();
950 : :
951 : : /* Flags and profiles of the edge taking care of out-of-range values. */
952 : 616 : e02->flags &= ~EDGE_FALLTHRU;
953 : 616 : e02->flags |= EDGE_FALSE_VALUE;
954 : 616 : e02->probability = m_default_prob;
955 : :
956 : 616 : bbf = m_final_bb;
957 : :
958 : 616 : e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
959 : 616 : e1f->probability = profile_probability::always ();
960 : :
961 : 616 : if (m_default_case_nonstandard)
962 : : e2f = NULL;
963 : : else
964 : : {
965 : 513 : e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
966 : 513 : e2f->probability = profile_probability::always ();
967 : : }
968 : :
969 : : /* frequencies of the new BBs */
970 : 616 : bb1->count = e01->count ();
971 : 616 : bb2->count = e02->count ();
972 : 616 : if (!m_default_case_nonstandard)
973 : 513 : bbf->count = e1f->count () + e2f->count ();
974 : :
975 : : /* Tidy blocks that have become unreachable. */
976 : 616 : prune_bbs (bbd, m_final_bb,
977 : 616 : m_default_case_nonstandard ? m_default_bb : NULL);
978 : :
979 : : /* Fixup the PHI nodes in bbF. */
980 : 616 : fix_phi_nodes (e1f, e2f, bbf);
981 : :
982 : : /* Fix the dominator tree, if it is available. */
983 : 616 : if (dom_info_available_p (CDI_DOMINATORS))
984 : : {
985 : 616 : vec<basic_block> bbs_to_fix_dom;
986 : :
987 : 616 : set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
988 : 616 : if (!m_default_case_nonstandard)
989 : 513 : set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
990 : 616 : if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
991 : : /* If bbD was the immediate dominator ... */
992 : 361 : set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
993 : :
994 : 631 : bbs_to_fix_dom.create (3 + (bb2 != bbf));
995 : 616 : bbs_to_fix_dom.quick_push (bb0);
996 : 616 : bbs_to_fix_dom.quick_push (bb1);
997 : 616 : if (bb2 != bbf)
998 : 601 : bbs_to_fix_dom.quick_push (bb2);
999 : 616 : bbs_to_fix_dom.quick_push (bbf);
1000 : :
1001 : 616 : iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
1002 : 616 : bbs_to_fix_dom.release ();
1003 : : }
1004 : 616 : }
1005 : :
1006 : : /* The following function is invoked on every switch statement (the current
1007 : : one is given in SWTCH) and runs the individual phases of switch
1008 : : conversion on it one after another until one fails or the conversion
1009 : : is completed. On success, NULL is in m_reason, otherwise points
1010 : : to a string with the reason why the conversion failed. */
1011 : :
1012 : : void
1013 : 26135 : switch_conversion::expand (gswitch *swtch)
1014 : : {
1015 : : /* Group case labels so that we get the right results from the heuristics
1016 : : that decide on the code generation approach for this switch. */
1017 : 26135 : m_cfg_altered |= group_case_labels_stmt (swtch);
1018 : :
1019 : : /* If this switch is now a degenerate case with only a default label,
1020 : : there is nothing left for us to do. */
1021 : 26135 : if (gimple_switch_num_labels (swtch) < 2)
1022 : : {
1023 : 0 : m_reason = "switch is a degenerate case";
1024 : 0 : return;
1025 : : }
1026 : :
1027 : 26135 : collect (swtch);
1028 : :
1029 : : /* No error markers should reach here (they should be filtered out
1030 : : during gimplification). */
1031 : 26135 : gcc_checking_assert (TREE_TYPE (m_index_expr) != error_mark_node);
1032 : :
1033 : : /* Prefer bit test if possible. */
1034 : 26135 : if (tree_fits_uhwi_p (m_range_size)
1035 : 26064 : && bit_test_cluster::can_be_handled (tree_to_uhwi (m_range_size), m_uniq)
1036 : 39862 : && bit_test_cluster::is_beneficial (m_count, m_uniq))
1037 : : {
1038 : 2127 : m_reason = "expanding as bit test is preferable";
1039 : 2127 : return;
1040 : : }
1041 : :
1042 : 24008 : if (m_uniq <= 2)
1043 : : {
1044 : : /* This will be expanded as a decision tree . */
1045 : 7773 : m_reason = "expanding as jumps is preferable";
1046 : 7773 : return;
1047 : : }
1048 : :
1049 : : /* If there is no common successor, we cannot do the transformation. */
1050 : 16235 : if (!m_final_bb)
1051 : : {
1052 : 10328 : m_reason = "no common successor to all case label target blocks found";
1053 : 10328 : return;
1054 : : }
1055 : :
1056 : : /* Check the case label values are within reasonable range: */
1057 : 5907 : if (!check_range ())
1058 : : {
1059 : 278 : gcc_assert (m_reason);
1060 : : return;
1061 : : }
1062 : :
1063 : : /* For all the cases, see whether they are empty, the assignments they
1064 : : represent constant and so on... */
1065 : 5629 : if (!check_all_empty_except_final ())
1066 : : {
1067 : 4926 : gcc_assert (m_reason);
1068 : : return;
1069 : : }
1070 : 703 : if (!check_final_bb ())
1071 : : {
1072 : 87 : gcc_assert (m_reason);
1073 : : return;
1074 : : }
1075 : :
1076 : : /* At this point all checks have passed and we can proceed with the
1077 : : transformation. */
1078 : :
1079 : 616 : create_temp_arrays ();
1080 : 1232 : gather_default_values (m_default_case_nonstandard
1081 : 103 : ? gimple_switch_label (swtch, 1)
1082 : 513 : : gimple_switch_default_label (swtch));
1083 : 616 : build_constructors ();
1084 : :
1085 : 616 : build_arrays (); /* Build the static arrays and assignments. */
1086 : 616 : gen_inbound_check (); /* Build the bounds check. */
1087 : :
1088 : 616 : m_cfg_altered = true;
1089 : : }
1090 : :
1091 : : /* Destructor. */
1092 : :
1093 : 26135 : switch_conversion::~switch_conversion ()
1094 : : {
1095 : 26135 : XDELETEVEC (m_constructors);
1096 : 26135 : XDELETEVEC (m_default_values);
1097 : 26135 : }
1098 : :
1099 : : /* Constructor. */
1100 : :
1101 : 20457 : group_cluster::group_cluster (vec<cluster *> &clusters,
1102 : 20457 : unsigned start, unsigned end)
1103 : : {
1104 : 20457 : gcc_checking_assert (end - start + 1 >= 1);
1105 : 20457 : m_prob = profile_probability::never ();
1106 : 20457 : m_cases.create (end - start + 1);
1107 : 193204 : for (unsigned i = start; i <= end; i++)
1108 : : {
1109 : 172747 : m_cases.quick_push (static_cast<simple_cluster *> (clusters[i]));
1110 : 172747 : m_prob += clusters[i]->m_prob;
1111 : : }
1112 : 20457 : m_subtree_prob = m_prob;
1113 : 20457 : }
1114 : :
1115 : : /* Destructor. */
1116 : :
1117 : 20457 : group_cluster::~group_cluster ()
1118 : : {
1119 : 386408 : for (unsigned i = 0; i < m_cases.length (); i++)
1120 : 172747 : delete m_cases[i];
1121 : :
1122 : 20457 : m_cases.release ();
1123 : 20457 : }
1124 : :
1125 : : /* Dump content of a cluster. */
1126 : :
1127 : : void
1128 : 29 : group_cluster::dump (FILE *f, bool details)
1129 : : {
1130 : 29 : unsigned total_values = 0;
1131 : 340 : for (unsigned i = 0; i < m_cases.length (); i++)
1132 : 282 : total_values += m_cases[i]->get_range (m_cases[i]->get_low (),
1133 : 141 : m_cases[i]->get_high ());
1134 : :
1135 : : unsigned comparison_count = 0;
1136 : 170 : for (unsigned i = 0; i < m_cases.length (); i++)
1137 : : {
1138 : 141 : simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
1139 : 224 : comparison_count += sc->get_comparison_count ();
1140 : : }
1141 : :
1142 : 29 : unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ());
1143 : 44 : fprintf (f, "%s", get_type () == JUMP_TABLE ? "JT" : "BT");
1144 : :
1145 : 29 : if (details)
1146 : 0 : fprintf (f, "(values:%d comparisons:%d range:" HOST_WIDE_INT_PRINT_DEC
1147 : : " density: %.2f%%)", total_values, comparison_count, range,
1148 : 0 : 100.0f * comparison_count / range);
1149 : :
1150 : 29 : fprintf (f, ":");
1151 : 29 : PRINT_CASE (f, get_low ());
1152 : 29 : fprintf (f, "-");
1153 : 29 : PRINT_CASE (f, get_high ());
1154 : 29 : fprintf (f, " ");
1155 : 29 : }
1156 : :
1157 : : /* Emit GIMPLE code to handle the cluster. */
1158 : :
1159 : : void
1160 : 15790 : jump_table_cluster::emit (tree index_expr, tree,
1161 : : tree default_label_expr, basic_block default_bb,
1162 : : location_t loc)
1163 : : {
1164 : 15790 : tree low = get_low ();
1165 : 15790 : unsigned HOST_WIDE_INT range = get_range (low, get_high ());
1166 : 15790 : unsigned HOST_WIDE_INT nondefault_range = 0;
1167 : 15790 : bool bitint = false;
1168 : 15790 : gimple_stmt_iterator gsi = gsi_start_bb (m_case_bb);
1169 : :
1170 : : /* For large/huge _BitInt, subtract low from index_expr, cast to unsigned
1171 : : DImode type (get_range doesn't support ranges larger than 64-bits)
1172 : : and subtract low from all case values as well. */
1173 : 15790 : if (TREE_CODE (TREE_TYPE (index_expr)) == BITINT_TYPE
1174 : 15790 : && TYPE_PRECISION (TREE_TYPE (index_expr)) > GET_MODE_PRECISION (DImode))
1175 : : {
1176 : 4 : bitint = true;
1177 : 4 : tree this_low = low, type;
1178 : 4 : gimple *g;
1179 : 4 : gimple_seq seq = NULL;
1180 : 4 : if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (index_expr)))
1181 : : {
1182 : 2 : type = unsigned_type_for (TREE_TYPE (index_expr));
1183 : 2 : index_expr = gimple_convert (&seq, type, index_expr);
1184 : 2 : this_low = fold_convert (type, this_low);
1185 : : }
1186 : 4 : this_low = const_unop (NEGATE_EXPR, TREE_TYPE (this_low), this_low);
1187 : 4 : index_expr = gimple_build (&seq, PLUS_EXPR, TREE_TYPE (index_expr),
1188 : : index_expr, this_low);
1189 : 4 : type = build_nonstandard_integer_type (GET_MODE_PRECISION (DImode), 1);
1190 : 4 : g = gimple_build_cond (GT_EXPR, index_expr,
1191 : 4 : fold_convert (TREE_TYPE (index_expr),
1192 : : TYPE_MAX_VALUE (type)),
1193 : : NULL_TREE, NULL_TREE);
1194 : 4 : gimple_seq_add_stmt (&seq, g);
1195 : 4 : gimple_seq_set_location (seq, loc);
1196 : 4 : gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
1197 : 4 : edge e1 = split_block (m_case_bb, g);
1198 : 4 : e1->flags = EDGE_FALSE_VALUE;
1199 : 4 : e1->probability = profile_probability::likely ();
1200 : 4 : edge e2 = make_edge (e1->src, default_bb, EDGE_TRUE_VALUE);
1201 : 4 : e2->probability = e1->probability.invert ();
1202 : 4 : gsi = gsi_start_bb (e1->dest);
1203 : 4 : seq = NULL;
1204 : 4 : index_expr = gimple_convert (&seq, type, index_expr);
1205 : 4 : gimple_seq_set_location (seq, loc);
1206 : 4 : gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
1207 : : }
1208 : :
1209 : : /* For jump table we just emit a new gswitch statement that will
1210 : : be latter lowered to jump table. */
1211 : 15790 : auto_vec <tree> labels;
1212 : 31580 : labels.create (m_cases.length ());
1213 : :
1214 : 15790 : basic_block case_bb = gsi_bb (gsi);
1215 : 15790 : make_edge (case_bb, default_bb, 0);
1216 : 335688 : for (unsigned i = 0; i < m_cases.length (); i++)
1217 : : {
1218 : 152054 : tree lab = unshare_expr (m_cases[i]->m_case_label_expr);
1219 : 152054 : if (bitint)
1220 : : {
1221 : 26 : CASE_LOW (lab)
1222 : 26 : = fold_convert (TREE_TYPE (index_expr),
1223 : : const_binop (MINUS_EXPR,
1224 : : TREE_TYPE (CASE_LOW (lab)),
1225 : : CASE_LOW (lab), low));
1226 : 26 : if (CASE_HIGH (lab))
1227 : 0 : CASE_HIGH (lab)
1228 : 0 : = fold_convert (TREE_TYPE (index_expr),
1229 : : const_binop (MINUS_EXPR,
1230 : : TREE_TYPE (CASE_HIGH (lab)),
1231 : : CASE_HIGH (lab), low));
1232 : : }
1233 : 152054 : labels.quick_push (lab);
1234 : 152054 : make_edge (case_bb, m_cases[i]->m_case_bb, 0);
1235 : : }
1236 : :
1237 : 15790 : gswitch *s = gimple_build_switch (index_expr,
1238 : : unshare_expr (default_label_expr), labels);
1239 : 15790 : gimple_set_location (s, loc);
1240 : 15790 : gsi_insert_after (&gsi, s, GSI_NEW_STMT);
1241 : :
1242 : : /* Set up even probabilities for all cases. */
1243 : 335688 : for (unsigned i = 0; i < m_cases.length (); i++)
1244 : : {
1245 : 152054 : simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
1246 : 152054 : edge case_edge = find_edge (case_bb, sc->m_case_bb);
1247 : 152054 : unsigned HOST_WIDE_INT case_range
1248 : 152054 : = sc->get_range (sc->get_low (), sc->get_high ());
1249 : 152054 : nondefault_range += case_range;
1250 : :
1251 : : /* case_edge->aux is number of values in a jump-table that are covered
1252 : : by the case_edge. */
1253 : 152054 : case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + case_range);
1254 : : }
1255 : :
1256 : 15790 : edge default_edge = gimple_switch_default_edge (cfun, s);
1257 : 15790 : default_edge->probability = profile_probability::never ();
1258 : :
1259 : 335688 : for (unsigned i = 0; i < m_cases.length (); i++)
1260 : : {
1261 : 152054 : simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
1262 : 152054 : edge case_edge = find_edge (case_bb, sc->m_case_bb);
1263 : 152054 : case_edge->probability
1264 : 152054 : = profile_probability::always ().apply_scale ((intptr_t)case_edge->aux,
1265 : : range);
1266 : : }
1267 : :
1268 : : /* Number of non-default values is probability of default edge. */
1269 : 15790 : default_edge->probability
1270 : 15790 : += profile_probability::always ().apply_scale (nondefault_range,
1271 : 15790 : range).invert ();
1272 : :
1273 : 15790 : switch_decision_tree::reset_out_edges_aux (s);
1274 : 15790 : }
1275 : :
1276 : : /* Find jump tables of given CLUSTERS, where all members of the vector
1277 : : are of type simple_cluster. New clusters are returned. */
1278 : :
1279 : : vec<cluster *>
1280 : 64396 : jump_table_cluster::find_jump_tables (vec<cluster *> &clusters)
1281 : : {
1282 : 64396 : if (!is_enabled ())
1283 : 2 : return clusters.copy ();
1284 : :
1285 : 64394 : unsigned l = clusters.length ();
1286 : 64394 : auto_vec<min_cluster_item> min;
1287 : 64394 : min.reserve (l + 1);
1288 : :
1289 : 64394 : min.quick_push (min_cluster_item (0, 0, 0));
1290 : :
1291 : 64394 : unsigned HOST_WIDE_INT max_ratio
1292 : 64394 : = (optimize_insn_for_size_p ()
1293 : 64394 : ? param_jump_table_max_growth_ratio_for_size
1294 : 63419 : : param_jump_table_max_growth_ratio_for_speed);
1295 : :
1296 : 342134 : for (unsigned i = 1; i <= l; i++)
1297 : : {
1298 : : /* Set minimal # of clusters with i-th item to infinite. */
1299 : 277740 : min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
1300 : :
1301 : : /* Pre-calculate number of comparisons for the clusters. */
1302 : 277740 : HOST_WIDE_INT comparison_count = 0;
1303 : 9131006 : for (unsigned k = 0; k <= i - 1; k++)
1304 : : {
1305 : 8853266 : simple_cluster *sc = static_cast<simple_cluster *> (clusters[k]);
1306 : 17449603 : comparison_count += sc->get_comparison_count ();
1307 : : }
1308 : :
1309 : 9131006 : for (unsigned j = 0; j < i; j++)
1310 : : {
1311 : 8853266 : unsigned HOST_WIDE_INT s = min[j].m_non_jt_cases;
1312 : 17706186 : if (i - j < case_values_threshold ())
1313 : 761517 : s += i - j;
1314 : :
1315 : : /* Prefer clusters with smaller number of numbers covered. */
1316 : 8853266 : if ((min[j].m_count + 1 < min[i].m_count
1317 : 3796758 : || (min[j].m_count + 1 == min[i].m_count
1318 : 1074 : && s < min[i].m_non_jt_cases))
1319 : 8853307 : && can_be_handled (clusters, j, i - 1, max_ratio,
1320 : : comparison_count))
1321 : 277769 : min[i] = min_cluster_item (min[j].m_count + 1, j, s);
1322 : :
1323 : 8853266 : simple_cluster *sc = static_cast<simple_cluster *> (clusters[j]);
1324 : 17449603 : comparison_count -= sc->get_comparison_count ();
1325 : : }
1326 : :
1327 : 277740 : gcc_checking_assert (comparison_count == 0);
1328 : 277740 : gcc_checking_assert (min[i].m_count != INT_MAX);
1329 : : }
1330 : :
1331 : : /* No result. */
1332 : 64394 : if (min[l].m_count == l)
1333 : 8076 : return clusters.copy ();
1334 : :
1335 : 56318 : vec<cluster *> output;
1336 : 56318 : output.create (4);
1337 : :
1338 : : /* Find and build the clusters. */
1339 : 56318 : for (unsigned int end = l;;)
1340 : : {
1341 : 60596 : int start = min[end].m_start;
1342 : :
1343 : : /* Do not allow clusters with small number of cases. */
1344 : 60596 : if (is_beneficial (clusters, start, end - 1))
1345 : 16411 : output.safe_push (new jump_table_cluster (clusters, start, end - 1));
1346 : : else
1347 : 145750 : for (int i = end - 1; i >= start; i--)
1348 : 101565 : output.safe_push (clusters[i]);
1349 : :
1350 : 60596 : end = start;
1351 : :
1352 : 60596 : if (start <= 0)
1353 : : break;
1354 : : }
1355 : :
1356 : 56318 : output.reverse ();
1357 : 56318 : return output;
1358 : 64394 : }
1359 : :
1360 : : /* Return true when cluster starting at START and ending at END (inclusive)
1361 : : can build a jump-table. */
1362 : :
1363 : : bool
1364 : 5056549 : jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
1365 : : unsigned start, unsigned end,
1366 : : unsigned HOST_WIDE_INT max_ratio,
1367 : : unsigned HOST_WIDE_INT comparison_count)
1368 : : {
1369 : : /* If the switch is relatively small such that the cost of one
1370 : : indirect jump on the target are higher than the cost of a
1371 : : decision tree, go with the decision tree.
1372 : :
1373 : : If range of values is much bigger than number of values,
1374 : : or if it is too large to represent in a HOST_WIDE_INT,
1375 : : make a sequence of conditional branches instead of a dispatch.
1376 : :
1377 : : The definition of "much bigger" depends on whether we are
1378 : : optimizing for size or for speed.
1379 : :
1380 : : For algorithm correctness, jump table for a single case must return
1381 : : true. We bail out in is_beneficial if it's called just for
1382 : : a single case. */
1383 : 5056549 : if (start == end)
1384 : : return true;
1385 : :
1386 : 9951066 : unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
1387 : 4975533 : clusters[end]->get_high ());
1388 : : /* Check overflow. */
1389 : 4975533 : if (range == 0)
1390 : : return false;
1391 : :
1392 : 4971242 : if (range > HOST_WIDE_INT_M1U / 100)
1393 : : return false;
1394 : :
1395 : 761086 : unsigned HOST_WIDE_INT lhs = 100 * range;
1396 : 761086 : if (lhs < range)
1397 : : return false;
1398 : :
1399 : 761086 : return lhs <= max_ratio * comparison_count;
1400 : : }
1401 : :
1402 : : /* Return true if cluster starting at START and ending at END (inclusive)
1403 : : is profitable transformation. */
1404 : :
1405 : : bool
1406 : 60596 : jump_table_cluster::is_beneficial (const vec<cluster *> &,
1407 : : unsigned start, unsigned end)
1408 : : {
1409 : : /* Single case bail out. */
1410 : 60596 : if (start == end)
1411 : : return false;
1412 : :
1413 : 114016 : return end - start + 1 >= case_values_threshold ();
1414 : : }
1415 : :
1416 : : /* Find bit tests of given CLUSTERS, where all members of the vector
1417 : : are of type simple_cluster. New clusters are returned. */
1418 : :
1419 : : vec<cluster *>
1420 : 65602 : bit_test_cluster::find_bit_tests (vec<cluster *> &clusters)
1421 : : {
1422 : 65602 : if (!is_enabled ())
1423 : 2 : return clusters.copy ();
1424 : :
1425 : 65600 : unsigned l = clusters.length ();
1426 : 65600 : auto_vec<min_cluster_item> min;
1427 : 65600 : min.reserve (l + 1);
1428 : :
1429 : 65600 : min.quick_push (min_cluster_item (0, 0, 0));
1430 : :
1431 : 351898 : for (unsigned i = 1; i <= l; i++)
1432 : : {
1433 : : /* Set minimal # of clusters with i-th item to infinite. */
1434 : 286298 : min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
1435 : :
1436 : 9249702 : for (unsigned j = 0; j < i; j++)
1437 : : {
1438 : 8963404 : if (min[j].m_count + 1 < min[i].m_count
1439 : 8963404 : && can_be_handled (clusters, j, i - 1))
1440 : 286298 : min[i] = min_cluster_item (min[j].m_count + 1, j, INT_MAX);
1441 : : }
1442 : :
1443 : 286298 : gcc_checking_assert (min[i].m_count != INT_MAX);
1444 : : }
1445 : :
1446 : : /* No result. */
1447 : 65600 : if (min[l].m_count == l)
1448 : 6124 : return clusters.copy ();
1449 : :
1450 : 59476 : vec<cluster *> output;
1451 : 59476 : output.create (4);
1452 : :
1453 : : /* Find and build the clusters. */
1454 : 59476 : for (unsigned end = l;;)
1455 : : {
1456 : 98306 : int start = min[end].m_start;
1457 : :
1458 : 98306 : if (is_beneficial (clusters, start, end - 1))
1459 : : {
1460 : 7143 : bool entire = start == 0 && end == clusters.length ();
1461 : 4046 : output.safe_push (new bit_test_cluster (clusters, start, end - 1,
1462 : 4046 : entire));
1463 : : }
1464 : : else
1465 : 349744 : for (int i = end - 1; i >= start; i--)
1466 : 255484 : output.safe_push (clusters[i]);
1467 : :
1468 : 98306 : end = start;
1469 : :
1470 : 98306 : if (start <= 0)
1471 : : break;
1472 : : }
1473 : :
1474 : 59476 : output.reverse ();
1475 : 59476 : return output;
1476 : 65600 : }
1477 : :
1478 : : /* Return true when RANGE of case values with UNIQ labels
1479 : : can build a bit test. */
1480 : :
1481 : : bool
1482 : 8499468 : bit_test_cluster::can_be_handled (unsigned HOST_WIDE_INT range,
1483 : : unsigned int uniq)
1484 : : {
1485 : : /* Check overflow. */
1486 : 8499468 : if (range == 0)
1487 : : return false;
1488 : :
1489 : 16990430 : if (range >= GET_MODE_BITSIZE (word_mode))
1490 : : return false;
1491 : :
1492 : 1178210 : return uniq <= m_max_case_bit_tests;
1493 : : }
1494 : :
1495 : : /* Return true when cluster starting at START and ending at END (inclusive)
1496 : : can build a bit test. */
1497 : :
1498 : : bool
1499 : 8550676 : bit_test_cluster::can_be_handled (const vec<cluster *> &clusters,
1500 : : unsigned start, unsigned end)
1501 : : {
1502 : 8550676 : auto_vec<int, m_max_case_bit_tests> dest_bbs;
1503 : : /* For algorithm correctness, bit test for a single case must return
1504 : : true. We bail out in is_beneficial if it's called just for
1505 : : a single case. */
1506 : 8550676 : if (start == end)
1507 : : return true;
1508 : :
1509 : 16946808 : unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
1510 : 8473404 : clusters[end]->get_high ());
1511 : :
1512 : : /* Make a guess first. */
1513 : 8473404 : if (!can_be_handled (range, m_max_case_bit_tests))
1514 : : return false;
1515 : :
1516 : 4713125 : for (unsigned i = start; i <= end; i++)
1517 : : {
1518 : 4504099 : simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
1519 : : /* m_max_case_bit_tests is very small integer, thus the operation
1520 : : is constant. */
1521 : 4504099 : if (!dest_bbs.contains (sc->m_case_bb->index))
1522 : : {
1523 : 4327522 : if (dest_bbs.length () >= m_max_case_bit_tests)
1524 : : return false;
1525 : 3381683 : dest_bbs.quick_push (sc->m_case_bb->index);
1526 : : }
1527 : : }
1528 : :
1529 : : return true;
1530 : 8550676 : }
1531 : :
1532 : : /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test
1533 : : transformation. */
1534 : :
1535 : : bool
1536 : 103828 : bit_test_cluster::is_beneficial (unsigned count, unsigned uniq)
1537 : : {
1538 : 103828 : return (((uniq == 1 && count >= 3)
1539 : 98727 : || (uniq == 2 && count >= 5)
1540 : 202142 : || (uniq == 3 && count >= 6)));
1541 : : }
1542 : :
1543 : : /* Return true if cluster starting at START and ending at END (inclusive)
1544 : : is profitable transformation. */
1545 : :
1546 : : bool
1547 : 98306 : bit_test_cluster::is_beneficial (const vec<cluster *> &clusters,
1548 : : unsigned start, unsigned end)
1549 : : {
1550 : : /* Single case bail out. */
1551 : 98306 : if (start == end)
1552 : : return false;
1553 : :
1554 : 90101 : auto_bitmap dest_bbs;
1555 : :
1556 : 353573 : for (unsigned i = start; i <= end; i++)
1557 : : {
1558 : 263472 : simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
1559 : 263472 : bitmap_set_bit (dest_bbs, sc->m_case_bb->index);
1560 : : }
1561 : :
1562 : 90101 : unsigned uniq = bitmap_count_bits (dest_bbs);
1563 : 90101 : unsigned count = end - start + 1;
1564 : 90101 : return is_beneficial (count, uniq);
1565 : 90101 : }
1566 : :
1567 : : /* Comparison function for qsort to order bit tests by decreasing
1568 : : probability of execution. */
1569 : :
1570 : : int
1571 : 6607 : case_bit_test::cmp (const void *p1, const void *p2)
1572 : : {
1573 : 6607 : const case_bit_test *const d1 = (const case_bit_test *) p1;
1574 : 6607 : const case_bit_test *const d2 = (const case_bit_test *) p2;
1575 : :
1576 : 6607 : if (d2->bits != d1->bits)
1577 : 5424 : return d2->bits - d1->bits;
1578 : :
1579 : : /* Stabilize the sort. */
1580 : 1183 : return (LABEL_DECL_UID (CASE_LABEL (d2->label))
1581 : 1183 : - LABEL_DECL_UID (CASE_LABEL (d1->label)));
1582 : : }
1583 : :
1584 : : /* Expand a switch statement by a short sequence of bit-wise
1585 : : comparisons. "switch(x)" is effectively converted into
1586 : : "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
1587 : : integer constants.
1588 : :
1589 : : INDEX_EXPR is the value being switched on.
1590 : :
1591 : : MINVAL is the lowest case value of in the case nodes,
1592 : : and RANGE is highest value minus MINVAL. MINVAL and RANGE
1593 : : are not guaranteed to be of the same type as INDEX_EXPR
1594 : : (the gimplifier doesn't change the type of case label values,
1595 : : and MINVAL and RANGE are derived from those values).
1596 : : MAXVAL is MINVAL + RANGE.
1597 : :
1598 : : There *MUST* be max_case_bit_tests or less unique case
1599 : : node targets. */
1600 : :
1601 : : void
1602 : 3314 : bit_test_cluster::emit (tree index_expr, tree index_type,
1603 : : tree, basic_block default_bb, location_t loc)
1604 : : {
1605 : 19884 : case_bit_test test[m_max_case_bit_tests] = { {} };
1606 : 3314 : unsigned int i, j, k;
1607 : 3314 : unsigned int count;
1608 : :
1609 : 3314 : tree unsigned_index_type = range_check_type (index_type);
1610 : :
1611 : 3314 : gimple_stmt_iterator gsi;
1612 : 3314 : gassign *shift_stmt;
1613 : :
1614 : 3314 : tree idx, tmp, csui;
1615 : 3314 : tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
1616 : 3314 : tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
1617 : 3314 : tree word_mode_one = fold_convert (word_type_node, integer_one_node);
1618 : 3314 : int prec = TYPE_PRECISION (word_type_node);
1619 : 3314 : wide_int wone = wi::one (prec);
1620 : :
1621 : 3314 : tree minval = get_low ();
1622 : 3314 : tree maxval = get_high ();
1623 : :
1624 : : /* Go through all case labels, and collect the case labels, profile
1625 : : counts, and other information we need to build the branch tests. */
1626 : 3314 : count = 0;
1627 : 34514 : for (i = 0; i < m_cases.length (); i++)
1628 : : {
1629 : 13943 : unsigned int lo, hi;
1630 : 13943 : simple_cluster *n = static_cast<simple_cluster *> (m_cases[i]);
1631 : 17492 : for (k = 0; k < count; k++)
1632 : 12908 : if (n->m_case_bb == test[k].target_bb)
1633 : : break;
1634 : :
1635 : 13943 : if (k == count)
1636 : : {
1637 : 4584 : gcc_checking_assert (count < m_max_case_bit_tests);
1638 : 4584 : test[k].mask = wi::zero (prec);
1639 : 4584 : test[k].target_bb = n->m_case_bb;
1640 : 4584 : test[k].label = n->m_case_label_expr;
1641 : 4584 : test[k].bits = 0;
1642 : 4584 : test[k].prob = profile_probability::never ();
1643 : 4584 : count++;
1644 : : }
1645 : :
1646 : 13943 : test[k].bits += n->get_range (n->get_low (), n->get_high ());
1647 : 13943 : test[k].prob += n->m_prob;
1648 : :
1649 : 13943 : lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval));
1650 : 13943 : if (n->get_high () == NULL_TREE)
1651 : : hi = lo;
1652 : : else
1653 : 13943 : hi = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_high (),
1654 : : minval));
1655 : :
1656 : 33499 : for (j = lo; j <= hi; j++)
1657 : 19556 : test[k].mask |= wi::lshift (wone, j);
1658 : : }
1659 : :
1660 : 3314 : qsort (test, count, sizeof (*test), case_bit_test::cmp);
1661 : :
1662 : : /* If every possible relative value of the index expression is a valid shift
1663 : : amount, then we can merge the entry test in the bit test. */
1664 : 3314 : bool entry_test_needed;
1665 : 3314 : value_range r;
1666 : 6628 : if (TREE_CODE (index_expr) == SSA_NAME
1667 : 6628 : && get_range_query (cfun)->range_of_expr (r, index_expr)
1668 : 3314 : && !r.undefined_p ()
1669 : 3313 : && !r.varying_p ()
1670 : 8631 : && wi::leu_p (r.upper_bound () - r.lower_bound (), prec - 1))
1671 : : {
1672 : 57 : wide_int min = r.lower_bound ();
1673 : 57 : wide_int max = r.upper_bound ();
1674 : 57 : tree index_type = TREE_TYPE (index_expr);
1675 : 57 : minval = fold_convert (index_type, minval);
1676 : 57 : wide_int iminval = wi::to_wide (minval);
1677 : 57 : if (wi::lt_p (min, iminval, TYPE_SIGN (index_type)))
1678 : : {
1679 : 52 : minval = wide_int_to_tree (index_type, min);
1680 : 163 : for (i = 0; i < count; i++)
1681 : 111 : test[i].mask = wi::lshift (test[i].mask, iminval - min);
1682 : : }
1683 : 5 : else if (wi::gt_p (min, iminval, TYPE_SIGN (index_type)))
1684 : : {
1685 : 0 : minval = wide_int_to_tree (index_type, min);
1686 : 0 : for (i = 0; i < count; i++)
1687 : 0 : test[i].mask = wi::lrshift (test[i].mask, min - iminval);
1688 : : }
1689 : 57 : maxval = wide_int_to_tree (index_type, max);
1690 : 57 : entry_test_needed = false;
1691 : 57 : }
1692 : : else
1693 : : entry_test_needed = true;
1694 : :
1695 : : /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
1696 : : the minval subtractions, but it might make the mask constants more
1697 : : expensive. So, compare the costs. */
1698 : 3314 : if (compare_tree_int (minval, 0) > 0 && compare_tree_int (maxval, prec) < 0)
1699 : : {
1700 : 1919 : int cost_diff;
1701 : 1919 : HOST_WIDE_INT m = tree_to_uhwi (minval);
1702 : 1919 : rtx reg = gen_raw_REG (word_mode, 10000);
1703 : 1919 : bool speed_p = optimize_insn_for_speed_p ();
1704 : 1919 : cost_diff = set_src_cost (gen_rtx_PLUS (word_mode, reg,
1705 : : GEN_INT (-m)),
1706 : : word_mode, speed_p);
1707 : 4151 : for (i = 0; i < count; i++)
1708 : : {
1709 : 2232 : rtx r = immed_wide_int_const (test[i].mask, word_mode);
1710 : 2232 : cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r),
1711 : : word_mode, speed_p);
1712 : 2232 : r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode);
1713 : 2232 : cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r),
1714 : : word_mode, speed_p);
1715 : : }
1716 : 1919 : if (cost_diff > 0)
1717 : : {
1718 : 4151 : for (i = 0; i < count; i++)
1719 : 2232 : test[i].mask = wi::lshift (test[i].mask, m);
1720 : 1919 : minval = build_zero_cst (TREE_TYPE (minval));
1721 : : }
1722 : : }
1723 : :
1724 : : /* Now build the test-and-branch code. */
1725 : :
1726 : 3314 : gsi = gsi_last_bb (m_case_bb);
1727 : :
1728 : : /* idx = (unsigned)x - minval. */
1729 : 3314 : idx = fold_convert_loc (loc, unsigned_index_type, index_expr);
1730 : 3314 : idx = fold_build2_loc (loc, MINUS_EXPR, unsigned_index_type, idx,
1731 : : fold_convert_loc (loc, unsigned_index_type, minval));
1732 : 3314 : idx = force_gimple_operand_gsi (&gsi, idx,
1733 : : /*simple=*/true, NULL_TREE,
1734 : : /*before=*/true, GSI_SAME_STMT);
1735 : :
1736 : 3314 : profile_probability subtree_prob = m_subtree_prob;
1737 : 3314 : profile_probability default_prob = m_default_prob;
1738 : 3314 : if (!default_prob.initialized_p ())
1739 : 2189 : default_prob = m_subtree_prob.invert ();
1740 : :
1741 : 3314 : if (m_handles_entire_switch && entry_test_needed)
1742 : : {
1743 : 2133 : tree range = int_const_binop (MINUS_EXPR, maxval, minval);
1744 : : /* if (idx > range) goto default */
1745 : 2133 : range
1746 : 2133 : = force_gimple_operand_gsi (&gsi,
1747 : : fold_convert (unsigned_index_type, range),
1748 : : /*simple=*/true, NULL_TREE,
1749 : : /*before=*/true, GSI_SAME_STMT);
1750 : 2133 : tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
1751 : 2133 : default_prob = default_prob / 2;
1752 : 2133 : basic_block new_bb
1753 : 2133 : = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb,
1754 : : default_prob, loc);
1755 : 4266 : gsi = gsi_last_bb (new_bb);
1756 : : }
1757 : :
1758 : 3314 : tmp = fold_build2_loc (loc, LSHIFT_EXPR, word_type_node, word_mode_one,
1759 : : fold_convert_loc (loc, word_type_node, idx));
1760 : :
1761 : : /* csui = (1 << (word_mode) idx) */
1762 : 3314 : if (count > 1)
1763 : : {
1764 : 761 : csui = make_ssa_name (word_type_node);
1765 : 761 : tmp = force_gimple_operand_gsi (&gsi, tmp,
1766 : : /*simple=*/false, NULL_TREE,
1767 : : /*before=*/true, GSI_SAME_STMT);
1768 : 761 : shift_stmt = gimple_build_assign (csui, tmp);
1769 : 761 : gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
1770 : 761 : update_stmt (shift_stmt);
1771 : : }
1772 : : else
1773 : : csui = tmp;
1774 : :
1775 : : /* for each unique set of cases:
1776 : : if (const & csui) goto target */
1777 : 7898 : for (k = 0; k < count; k++)
1778 : : {
1779 : 4584 : profile_probability prob = test[k].prob / (subtree_prob + default_prob);
1780 : 4584 : subtree_prob -= test[k].prob;
1781 : 4584 : tmp = wide_int_to_tree (word_type_node, test[k].mask);
1782 : 4584 : tmp = fold_build2_loc (loc, BIT_AND_EXPR, word_type_node, csui, tmp);
1783 : 4584 : tmp = fold_build2_loc (loc, NE_EXPR, boolean_type_node,
1784 : : tmp, word_mode_zero);
1785 : 4584 : tmp = force_gimple_operand_gsi (&gsi, tmp,
1786 : : /*simple=*/true, NULL_TREE,
1787 : : /*before=*/true, GSI_SAME_STMT);
1788 : 4584 : basic_block new_bb
1789 : 4584 : = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_bb,
1790 : : prob, loc);
1791 : 9168 : gsi = gsi_last_bb (new_bb);
1792 : : }
1793 : :
1794 : : /* We should have removed all edges now. */
1795 : 3314 : gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
1796 : :
1797 : : /* If nothing matched, go to the default label. */
1798 : 3314 : edge e = make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU);
1799 : 3314 : e->probability = profile_probability::always ();
1800 : 13256 : }
1801 : :
1802 : : /* Split the basic block at the statement pointed to by GSIP, and insert
1803 : : a branch to the target basic block of E_TRUE conditional on tree
1804 : : expression COND.
1805 : :
1806 : : It is assumed that there is already an edge from the to-be-split
1807 : : basic block to E_TRUE->dest block. This edge is removed, and the
1808 : : profile information on the edge is re-used for the new conditional
1809 : : jump.
1810 : :
1811 : : The CFG is updated. The dominator tree will not be valid after
1812 : : this transformation, but the immediate dominators are updated if
1813 : : UPDATE_DOMINATORS is true.
1814 : :
1815 : : Returns the newly created basic block. */
1816 : :
1817 : : basic_block
1818 : 6717 : bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
1819 : : tree cond, basic_block case_bb,
1820 : : profile_probability prob,
1821 : : location_t loc)
1822 : : {
1823 : 6717 : tree tmp;
1824 : 6717 : gcond *cond_stmt;
1825 : 6717 : edge e_false;
1826 : 6717 : basic_block new_bb, split_bb = gsi_bb (*gsip);
1827 : :
1828 : 6717 : edge e_true = make_edge (split_bb, case_bb, EDGE_TRUE_VALUE);
1829 : 6717 : e_true->probability = prob;
1830 : 6717 : gcc_assert (e_true->src == split_bb);
1831 : :
1832 : 6717 : tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
1833 : : /*before=*/true, GSI_SAME_STMT);
1834 : 6717 : cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
1835 : 6717 : gimple_set_location (cond_stmt, loc);
1836 : 6717 : gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
1837 : :
1838 : 6717 : e_false = split_block (split_bb, cond_stmt);
1839 : 6717 : new_bb = e_false->dest;
1840 : 6717 : redirect_edge_pred (e_true, split_bb);
1841 : :
1842 : 6717 : e_false->flags &= ~EDGE_FALLTHRU;
1843 : 6717 : e_false->flags |= EDGE_FALSE_VALUE;
1844 : 6717 : e_false->probability = e_true->probability.invert ();
1845 : 6717 : new_bb->count = e_false->count ();
1846 : :
1847 : 6717 : return new_bb;
1848 : : }
1849 : :
1850 : : /* Compute the number of case labels that correspond to each outgoing edge of
1851 : : switch statement. Record this information in the aux field of the edge. */
1852 : :
1853 : : void
1854 : 42929 : switch_decision_tree::compute_cases_per_edge ()
1855 : : {
1856 : 42929 : reset_out_edges_aux (m_switch);
1857 : 42929 : int ncases = gimple_switch_num_labels (m_switch);
1858 : 280323 : for (int i = ncases - 1; i >= 1; --i)
1859 : : {
1860 : 237394 : edge case_edge = gimple_switch_edge (cfun, m_switch, i);
1861 : 237394 : case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1);
1862 : : }
1863 : 42929 : }
1864 : :
1865 : : /* Analyze switch statement and return true when the statement is expanded
1866 : : as decision tree. */
1867 : :
1868 : : bool
1869 : 42929 : switch_decision_tree::analyze_switch_statement ()
1870 : : {
1871 : 42929 : unsigned l = gimple_switch_num_labels (m_switch);
1872 : 42929 : basic_block bb = gimple_bb (m_switch);
1873 : 42929 : auto_vec<cluster *> clusters;
1874 : 42929 : clusters.create (l - 1);
1875 : :
1876 : 42929 : basic_block default_bb = gimple_switch_default_bb (cfun, m_switch);
1877 : 42929 : m_case_bbs.reserve (l);
1878 : 42929 : m_case_bbs.quick_push (default_bb);
1879 : :
1880 : 42929 : compute_cases_per_edge ();
1881 : :
1882 : 280323 : for (unsigned i = 1; i < l; i++)
1883 : : {
1884 : 237394 : tree elt = gimple_switch_label (m_switch, i);
1885 : 237394 : tree lab = CASE_LABEL (elt);
1886 : 237394 : basic_block case_bb = label_to_block (cfun, lab);
1887 : 237394 : edge case_edge = find_edge (bb, case_bb);
1888 : 237394 : tree low = CASE_LOW (elt);
1889 : 237394 : tree high = CASE_HIGH (elt);
1890 : :
1891 : 237394 : profile_probability p
1892 : 237394 : = case_edge->probability / ((intptr_t) (case_edge->aux));
1893 : 237394 : clusters.quick_push (new simple_cluster (low, high, elt, case_edge->dest,
1894 : 237394 : p));
1895 : 237394 : m_case_bbs.quick_push (case_edge->dest);
1896 : : }
1897 : :
1898 : 42929 : reset_out_edges_aux (m_switch);
1899 : :
1900 : : /* Find bit-test clusters. */
1901 : 42929 : vec<cluster *> output = bit_test_cluster::find_bit_tests (clusters);
1902 : :
1903 : : /* Find jump table clusters. */
1904 : 42929 : vec<cluster *> output2;
1905 : 42929 : auto_vec<cluster *> tmp;
1906 : 42929 : output2.create (1);
1907 : 42929 : tmp.create (1);
1908 : :
1909 : 539388 : for (unsigned i = 0; i < output.length (); i++)
1910 : : {
1911 : 226765 : cluster *c = output[i];
1912 : 226765 : if (c->get_type () != SIMPLE_CASE)
1913 : : {
1914 : 3314 : if (!tmp.is_empty ())
1915 : : {
1916 : 816 : vec<cluster *> n = jump_table_cluster::find_jump_tables (tmp);
1917 : 816 : output2.safe_splice (n);
1918 : 816 : n.release ();
1919 : 816 : tmp.truncate (0);
1920 : : }
1921 : 3314 : output2.safe_push (c);
1922 : : }
1923 : : else
1924 : 223451 : tmp.safe_push (c);
1925 : : }
1926 : :
1927 : : /* We still can have a temporary vector to test. */
1928 : 42929 : if (!tmp.is_empty ())
1929 : : {
1930 : 40292 : vec<cluster *> n = jump_table_cluster::find_jump_tables (tmp);
1931 : 40292 : output2.safe_splice (n);
1932 : 40292 : n.release ();
1933 : : }
1934 : :
1935 : 42929 : if (dump_file)
1936 : : {
1937 : 22 : fprintf (dump_file, ";; GIMPLE switch case clusters: ");
1938 : 178 : for (unsigned i = 0; i < output2.length (); i++)
1939 : 67 : output2[i]->dump (dump_file, dump_flags & TDF_DETAILS);
1940 : 22 : fprintf (dump_file, "\n");
1941 : : }
1942 : :
1943 : 42929 : output.release ();
1944 : :
1945 : 42929 : bool expanded = try_switch_expansion (output2);
1946 : 42929 : release_clusters (output2);
1947 : 42929 : return expanded;
1948 : 42929 : }
1949 : :
1950 : : /* Attempt to expand CLUSTERS as a decision tree. Return true when
1951 : : expanded. */
1952 : :
1953 : : bool
1954 : 42929 : switch_decision_tree::try_switch_expansion (vec<cluster *> &clusters)
1955 : : {
1956 : 42929 : tree index_expr = gimple_switch_index (m_switch);
1957 : 42929 : tree index_type = TREE_TYPE (index_expr);
1958 : 42929 : basic_block bb = gimple_bb (m_switch);
1959 : :
1960 : 42929 : if (gimple_switch_num_labels (m_switch) == 1
1961 : 42929 : || range_check_type (index_type) == NULL_TREE)
1962 : 0 : return false;
1963 : :
1964 : : /* Find the default case target label. */
1965 : 42929 : edge default_edge = gimple_switch_default_edge (cfun, m_switch);
1966 : 42929 : m_default_bb = default_edge->dest;
1967 : :
1968 : : /* Do the insertion of a case label into m_case_list. The labels are
1969 : : fed to us in descending order from the sorted vector of case labels used
1970 : : in the tree part of the middle end. So the list we construct is
1971 : : sorted in ascending order. */
1972 : :
1973 : 176359 : for (int i = clusters.length () - 1; i >= 0; i--)
1974 : : {
1975 : 90501 : case_tree_node *r = m_case_list;
1976 : 90501 : m_case_list = m_case_node_pool.allocate ();
1977 : 90501 : m_case_list->m_right = r;
1978 : 90501 : m_case_list->m_c = clusters[i];
1979 : : }
1980 : :
1981 : 42929 : record_phi_operand_mapping ();
1982 : :
1983 : : /* Split basic block that contains the gswitch statement. */
1984 : 42929 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
1985 : 42929 : edge e;
1986 : 42929 : if (gsi_end_p (gsi))
1987 : 0 : e = split_block_after_labels (bb);
1988 : : else
1989 : : {
1990 : 42929 : gsi_prev (&gsi);
1991 : 42929 : e = split_block (bb, gsi_stmt (gsi));
1992 : : }
1993 : 42929 : bb = split_edge (e);
1994 : :
1995 : : /* Create new basic blocks for non-case clusters where specific expansion
1996 : : needs to happen. */
1997 : 266860 : for (unsigned i = 0; i < clusters.length (); i++)
1998 : 90501 : if (clusters[i]->get_type () != SIMPLE_CASE)
1999 : : {
2000 : 19104 : clusters[i]->m_case_bb = create_empty_bb (bb);
2001 : 19104 : clusters[i]->m_case_bb->count = bb->count;
2002 : 19104 : clusters[i]->m_case_bb->loop_father = bb->loop_father;
2003 : : }
2004 : :
2005 : : /* Do not do an extra work for a single cluster. */
2006 : 42929 : if (clusters.length () == 1
2007 : 61527 : && clusters[0]->get_type () != SIMPLE_CASE)
2008 : : {
2009 : 17321 : cluster *c = clusters[0];
2010 : 17321 : c->emit (index_expr, index_type,
2011 : : gimple_switch_default_label (m_switch), m_default_bb,
2012 : 17321 : gimple_location (m_switch));
2013 : 17321 : redirect_edge_succ (single_succ_edge (bb), c->m_case_bb);
2014 : : }
2015 : : else
2016 : : {
2017 : 25608 : emit (bb, index_expr, default_edge->probability, index_type);
2018 : :
2019 : : /* Emit cluster-specific switch handling. */
2020 : 197576 : for (unsigned i = 0; i < clusters.length (); i++)
2021 : 73180 : if (clusters[i]->get_type () != SIMPLE_CASE)
2022 : : {
2023 : 1783 : edge e = single_pred_edge (clusters[i]->m_case_bb);
2024 : 1783 : e->dest->count = e->src->count.apply_probability (e->probability);
2025 : 3566 : clusters[i]->emit (index_expr, index_type,
2026 : : gimple_switch_default_label (m_switch),
2027 : 1783 : m_default_bb, gimple_location (m_switch));
2028 : : }
2029 : : }
2030 : :
2031 : 42929 : fix_phi_operands_for_edges ();
2032 : :
2033 : 42929 : return true;
2034 : : }
2035 : :
2036 : : /* Before switch transformation, record all SSA_NAMEs defined in switch BB
2037 : : and used in a label basic block. */
2038 : :
2039 : : void
2040 : 42929 : switch_decision_tree::record_phi_operand_mapping ()
2041 : : {
2042 : 42929 : basic_block switch_bb = gimple_bb (m_switch);
2043 : : /* Record all PHI nodes that have to be fixed after conversion. */
2044 : 646504 : for (unsigned i = 0; i < m_case_bbs.length (); i++)
2045 : : {
2046 : 280323 : gphi_iterator gsi;
2047 : 280323 : basic_block bb = m_case_bbs[i];
2048 : 332124 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2049 : : {
2050 : 51801 : gphi *phi = gsi.phi ();
2051 : :
2052 : 167640 : for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
2053 : : {
2054 : 167640 : basic_block phi_src_bb = gimple_phi_arg_edge (phi, i)->src;
2055 : 167640 : if (phi_src_bb == switch_bb)
2056 : : {
2057 : 51801 : tree def = gimple_phi_arg_def (phi, i);
2058 : 51801 : tree result = gimple_phi_result (phi);
2059 : 51801 : m_phi_mapping.put (result, def);
2060 : 51801 : break;
2061 : : }
2062 : : }
2063 : : }
2064 : : }
2065 : 42929 : }
2066 : :
2067 : : /* Append new operands to PHI statements that were introduced due to
2068 : : addition of new edges to case labels. */
2069 : :
2070 : : void
2071 : 42929 : switch_decision_tree::fix_phi_operands_for_edges ()
2072 : : {
2073 : 42929 : gphi_iterator gsi;
2074 : :
2075 : 646504 : for (unsigned i = 0; i < m_case_bbs.length (); i++)
2076 : : {
2077 : 280323 : basic_block bb = m_case_bbs[i];
2078 : 332124 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2079 : : {
2080 : 51801 : gphi *phi = gsi.phi ();
2081 : 411894 : for (unsigned j = 0; j < gimple_phi_num_args (phi); j++)
2082 : : {
2083 : 360093 : tree def = gimple_phi_arg_def (phi, j);
2084 : 360093 : if (def == NULL_TREE)
2085 : : {
2086 : 52851 : edge e = gimple_phi_arg_edge (phi, j);
2087 : 52851 : tree *definition
2088 : 52851 : = m_phi_mapping.get (gimple_phi_result (phi));
2089 : 52851 : gcc_assert (definition);
2090 : 52851 : add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
2091 : : }
2092 : : }
2093 : : }
2094 : : }
2095 : 42929 : }
2096 : :
2097 : : /* Generate a decision tree, switching on INDEX_EXPR and jumping to
2098 : : one of the labels in CASE_LIST or to the DEFAULT_LABEL.
2099 : :
2100 : : We generate a binary decision tree to select the appropriate target
2101 : : code. */
2102 : :
2103 : : void
2104 : 25608 : switch_decision_tree::emit (basic_block bb, tree index_expr,
2105 : : profile_probability default_prob, tree index_type)
2106 : : {
2107 : 25608 : balance_case_nodes (&m_case_list, NULL);
2108 : :
2109 : 25608 : if (dump_file)
2110 : 11 : dump_function_to_file (current_function_decl, dump_file, dump_flags);
2111 : 25608 : if (dump_file && (dump_flags & TDF_DETAILS))
2112 : : {
2113 : 0 : int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
2114 : 0 : fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
2115 : 0 : gcc_assert (m_case_list != NULL);
2116 : 0 : dump_case_nodes (dump_file, m_case_list, indent_step, 0);
2117 : : }
2118 : :
2119 : 51216 : bb = emit_case_nodes (bb, index_expr, m_case_list, default_prob, index_type,
2120 : 25608 : gimple_location (m_switch));
2121 : :
2122 : 25608 : if (bb)
2123 : 23388 : emit_jump (bb, m_default_bb);
2124 : :
2125 : : /* Remove all edges and do just an edge that will reach default_bb. */
2126 : 25608 : bb = gimple_bb (m_switch);
2127 : 25608 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
2128 : 25608 : gsi_remove (&gsi, true);
2129 : :
2130 : 25608 : delete_basic_block (bb);
2131 : 25608 : }
2132 : :
2133 : : /* Take an ordered list of case nodes
2134 : : and transform them into a near optimal binary tree,
2135 : : on the assumption that any target code selection value is as
2136 : : likely as any other.
2137 : :
2138 : : The transformation is performed by splitting the ordered
2139 : : list into two equal sections plus a pivot. The parts are
2140 : : then attached to the pivot as left and right branches. Each
2141 : : branch is then transformed recursively. */
2142 : :
2143 : : void
2144 : 56374 : switch_decision_tree::balance_case_nodes (case_tree_node **head,
2145 : : case_tree_node *parent)
2146 : : {
2147 : 56374 : case_tree_node *np;
2148 : :
2149 : 56374 : np = *head;
2150 : 56374 : if (np)
2151 : : {
2152 : 52571 : int i = 0;
2153 : 52571 : case_tree_node **npp;
2154 : 52571 : case_tree_node *left;
2155 : 52571 : profile_probability prob = profile_probability::never ();
2156 : :
2157 : : /* Count the number of entries on branch. */
2158 : :
2159 : 194464 : while (np)
2160 : : {
2161 : 141893 : i++;
2162 : 141893 : prob += np->m_c->m_prob;
2163 : 141893 : np = np->m_right;
2164 : : }
2165 : :
2166 : 52571 : if (i > 2)
2167 : : {
2168 : : /* Split this list if it is long enough for that to help. */
2169 : 15383 : npp = head;
2170 : 15383 : left = *npp;
2171 : 15383 : profile_probability pivot_prob = prob / 2;
2172 : :
2173 : : /* Find the place in the list that bisects the list's total cost
2174 : : by probability. */
2175 : 96099 : while (1)
2176 : : {
2177 : : /* Skip nodes while their probability does not reach
2178 : : that amount. */
2179 : 55741 : prob -= (*npp)->m_c->m_prob;
2180 : 55741 : if ((prob.initialized_p () && prob < pivot_prob)
2181 : 88360 : || ! (*npp)->m_right)
2182 : : break;
2183 : 40358 : npp = &(*npp)->m_right;
2184 : : }
2185 : :
2186 : 15383 : np = *npp;
2187 : 15383 : *npp = 0;
2188 : 15383 : *head = np;
2189 : 15383 : np->m_parent = parent;
2190 : 15383 : np->m_left = left == np ? NULL : left;
2191 : :
2192 : : /* Optimize each of the two split parts. */
2193 : 15383 : balance_case_nodes (&np->m_left, np);
2194 : 15383 : balance_case_nodes (&np->m_right, np);
2195 : 15383 : np->m_c->m_subtree_prob = np->m_c->m_prob;
2196 : 15383 : if (np->m_left)
2197 : 15078 : np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob;
2198 : 15383 : if (np->m_right)
2199 : 11885 : np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
2200 : : }
2201 : : else
2202 : : {
2203 : : /* Else leave this branch as one level,
2204 : : but fill in `parent' fields. */
2205 : 37188 : np = *head;
2206 : 37188 : np->m_parent = parent;
2207 : 37188 : np->m_c->m_subtree_prob = np->m_c->m_prob;
2208 : 57797 : for (; np->m_right; np = np->m_right)
2209 : : {
2210 : 20609 : np->m_right->m_parent = np;
2211 : 20609 : (*head)->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
2212 : : }
2213 : : }
2214 : : }
2215 : 56374 : }
2216 : :
2217 : : /* Dump ROOT, a list or tree of case nodes, to file. */
2218 : :
2219 : : void
2220 : 0 : switch_decision_tree::dump_case_nodes (FILE *f, case_tree_node *root,
2221 : : int indent_step, int indent_level)
2222 : : {
2223 : 0 : if (root == 0)
2224 : 0 : return;
2225 : 0 : indent_level++;
2226 : :
2227 : 0 : dump_case_nodes (f, root->m_left, indent_step, indent_level);
2228 : :
2229 : 0 : fputs (";; ", f);
2230 : 0 : fprintf (f, "%*s", indent_step * indent_level, "");
2231 : 0 : root->m_c->dump (f);
2232 : 0 : root->m_c->m_prob.dump (f);
2233 : 0 : fputs (" subtree: ", f);
2234 : 0 : root->m_c->m_subtree_prob.dump (f);
2235 : 0 : fputs (")\n", f);
2236 : :
2237 : 0 : dump_case_nodes (f, root->m_right, indent_step, indent_level);
2238 : : }
2239 : :
2240 : :
2241 : : /* Add an unconditional jump to CASE_BB that happens in basic block BB. */
2242 : :
2243 : : void
2244 : 36553 : switch_decision_tree::emit_jump (basic_block bb, basic_block case_bb)
2245 : : {
2246 : 36553 : edge e = single_succ_edge (bb);
2247 : 36553 : redirect_edge_succ (e, case_bb);
2248 : 36553 : }
2249 : :
2250 : : /* Generate code to compare OP0 with OP1 so that the condition codes are
2251 : : set and to jump to LABEL_BB if the condition is true.
2252 : : COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
2253 : : PROB is the probability of jumping to LABEL_BB. */
2254 : :
2255 : : basic_block
2256 : 24119 : switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0,
2257 : : tree op1, tree_code comparison,
2258 : : basic_block label_bb,
2259 : : profile_probability prob,
2260 : : location_t loc)
2261 : : {
2262 : : // TODO: it's once called with lhs != index.
2263 : 24119 : op1 = fold_convert (TREE_TYPE (op0), op1);
2264 : :
2265 : 24119 : gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE);
2266 : 24119 : gimple_set_location (cond, loc);
2267 : 24119 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
2268 : 24119 : gsi_insert_after (&gsi, cond, GSI_NEW_STMT);
2269 : :
2270 : 48238 : gcc_assert (single_succ_p (bb));
2271 : :
2272 : : /* Make a new basic block where false branch will take place. */
2273 : 24119 : edge false_edge = split_block (bb, cond);
2274 : 24119 : false_edge->flags = EDGE_FALSE_VALUE;
2275 : 24119 : false_edge->probability = prob.invert ();
2276 : 24119 : false_edge->dest->count = bb->count.apply_probability (prob.invert ());
2277 : :
2278 : 24119 : edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
2279 : 24119 : true_edge->probability = prob;
2280 : :
2281 : 24119 : return false_edge->dest;
2282 : : }
2283 : :
2284 : : /* Generate code to jump to LABEL if OP0 and OP1 are equal.
2285 : : PROB is the probability of jumping to LABEL_BB.
2286 : : BB is a basic block where the new condition will be placed. */
2287 : :
2288 : : basic_block
2289 : 64064 : switch_decision_tree::do_jump_if_equal (basic_block bb, tree op0, tree op1,
2290 : : basic_block label_bb,
2291 : : profile_probability prob,
2292 : : location_t loc)
2293 : : {
2294 : 64064 : op1 = fold_convert (TREE_TYPE (op0), op1);
2295 : :
2296 : 64064 : gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE);
2297 : 64064 : gimple_set_location (cond, loc);
2298 : 64064 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
2299 : 64064 : gsi_insert_before (&gsi, cond, GSI_SAME_STMT);
2300 : :
2301 : 128128 : gcc_assert (single_succ_p (bb));
2302 : :
2303 : : /* Make a new basic block where false branch will take place. */
2304 : 64064 : edge false_edge = split_block (bb, cond);
2305 : 64064 : false_edge->flags = EDGE_FALSE_VALUE;
2306 : 64064 : false_edge->probability = prob.invert ();
2307 : 64064 : false_edge->dest->count = bb->count.apply_probability (prob.invert ());
2308 : :
2309 : 64064 : edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
2310 : 64064 : true_edge->probability = prob;
2311 : :
2312 : 64064 : return false_edge->dest;
2313 : : }
2314 : :
2315 : : /* Emit step-by-step code to select a case for the value of INDEX.
2316 : : The thus generated decision tree follows the form of the
2317 : : case-node binary tree NODE, whose nodes represent test conditions.
2318 : : DEFAULT_PROB is probability of cases leading to default BB.
2319 : : INDEX_TYPE is the type of the index of the switch. */
2320 : :
2321 : : basic_block
2322 : 36553 : switch_decision_tree::emit_case_nodes (basic_block bb, tree index,
2323 : : case_tree_node *node,
2324 : : profile_probability default_prob,
2325 : : tree index_type, location_t loc)
2326 : : {
2327 : 51556 : profile_probability p;
2328 : :
2329 : : /* If node is null, we are done. */
2330 : 51556 : if (node == NULL)
2331 : : return bb;
2332 : :
2333 : : /* Single value case. */
2334 : 46814 : if (node->m_c->is_single_value_p ())
2335 : : {
2336 : : /* Node is single valued. First see if the index expression matches
2337 : : this node and then check our children, if any. */
2338 : 37698 : p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
2339 : 37698 : bb = do_jump_if_equal (bb, index, node->m_c->get_low (),
2340 : : node->m_c->m_case_bb, p, loc);
2341 : : /* Since this case is taken at this point, reduce its weight from
2342 : : subtree_weight. */
2343 : 37698 : node->m_c->m_subtree_prob -= node->m_c->m_prob;
2344 : :
2345 : 37698 : if (node->m_left != NULL && node->m_right != NULL)
2346 : : {
2347 : : /* 1) the node has both children
2348 : :
2349 : : If both children are single-valued cases with no
2350 : : children, finish up all the work. This way, we can save
2351 : : one ordered comparison. */
2352 : :
2353 : 10914 : if (!node->m_left->has_child ()
2354 : 5575 : && node->m_left->m_c->is_single_value_p ()
2355 : 4944 : && !node->m_right->has_child ()
2356 : 4757 : && node->m_right->m_c->is_single_value_p ())
2357 : : {
2358 : 4683 : p = (node->m_right->m_c->m_prob
2359 : 4683 : / (node->m_c->m_subtree_prob + default_prob));
2360 : 4683 : bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
2361 : : node->m_right->m_c->m_case_bb, p, loc);
2362 : 4683 : node->m_c->m_subtree_prob -= node->m_right->m_c->m_prob;
2363 : :
2364 : 4683 : p = (node->m_left->m_c->m_prob
2365 : 4683 : / (node->m_c->m_subtree_prob + default_prob));
2366 : 4683 : bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
2367 : : node->m_left->m_c->m_case_bb, p, loc);
2368 : : }
2369 : : else
2370 : : {
2371 : : /* Branch to a label where we will handle it later. */
2372 : 6231 : basic_block test_bb = split_edge (single_succ_edge (bb));
2373 : 6231 : redirect_edge_succ (single_pred_edge (test_bb),
2374 : 6231 : single_succ_edge (bb)->dest);
2375 : :
2376 : 18693 : p = ((node->m_right->m_c->m_subtree_prob + default_prob / 2)
2377 : 6231 : / (node->m_c->m_subtree_prob + default_prob));
2378 : 6231 : test_bb->count = bb->count.apply_probability (p);
2379 : 6231 : bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
2380 : : GT_EXPR, test_bb, p, loc);
2381 : 6231 : default_prob /= 2;
2382 : :
2383 : : /* Handle the left-hand subtree. */
2384 : 6231 : bb = emit_case_nodes (bb, index, node->m_left,
2385 : : default_prob, index_type, loc);
2386 : :
2387 : : /* If the left-hand subtree fell through,
2388 : : don't let it fall into the right-hand subtree. */
2389 : 6231 : if (bb && m_default_bb)
2390 : 4344 : emit_jump (bb, m_default_bb);
2391 : :
2392 : 6231 : bb = emit_case_nodes (test_bb, index, node->m_right,
2393 : : default_prob, index_type, loc);
2394 : : }
2395 : : }
2396 : 26784 : else if (node->m_left == NULL && node->m_right != NULL)
2397 : : {
2398 : : /* 2) the node has only right child. */
2399 : :
2400 : : /* Here we have a right child but no left so we issue a conditional
2401 : : branch to default and process the right child.
2402 : :
2403 : : Omit the conditional branch to default if the right child
2404 : : does not have any children and is single valued; it would
2405 : : cost too much space to save so little time. */
2406 : :
2407 : 17942 : if (node->m_right->has_child ()
2408 : 17729 : || !node->m_right->m_c->is_single_value_p ())
2409 : : {
2410 : 2826 : p = ((default_prob / 2)
2411 : 942 : / (node->m_c->m_subtree_prob + default_prob));
2412 : 942 : bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
2413 : : LT_EXPR, m_default_bb, p, loc);
2414 : 942 : default_prob /= 2;
2415 : :
2416 : 942 : bb = emit_case_nodes (bb, index, node->m_right, default_prob,
2417 : : index_type, loc);
2418 : : }
2419 : : else
2420 : : {
2421 : : /* We cannot process node->right normally
2422 : : since we haven't ruled out the numbers less than
2423 : : this node's value. So handle node->right explicitly. */
2424 : 17000 : p = (node->m_right->m_c->m_subtree_prob
2425 : 17000 : / (node->m_c->m_subtree_prob + default_prob));
2426 : 17000 : bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
2427 : : node->m_right->m_c->m_case_bb, p, loc);
2428 : : }
2429 : : }
2430 : 8842 : else if (node->m_left != NULL && node->m_right == NULL)
2431 : : {
2432 : : /* 3) just one subtree, on the left. Similar case as previous. */
2433 : :
2434 : 3116 : if (node->m_left->has_child ()
2435 : 0 : || !node->m_left->m_c->is_single_value_p ())
2436 : : {
2437 : 9348 : p = ((default_prob / 2)
2438 : 3116 : / (node->m_c->m_subtree_prob + default_prob));
2439 : 3116 : bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
2440 : : GT_EXPR, m_default_bb, p, loc);
2441 : 3116 : default_prob /= 2;
2442 : :
2443 : 3116 : bb = emit_case_nodes (bb, index, node->m_left, default_prob,
2444 : : index_type, loc);
2445 : : }
2446 : : else
2447 : : {
2448 : : /* We cannot process node->left normally
2449 : : since we haven't ruled out the numbers less than
2450 : : this node's value. So handle node->left explicitly. */
2451 : 0 : p = (node->m_left->m_c->m_subtree_prob
2452 : 0 : / (node->m_c->m_subtree_prob + default_prob));
2453 : 0 : bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
2454 : : node->m_left->m_c->m_case_bb, p, loc);
2455 : : }
2456 : : }
2457 : : }
2458 : : else
2459 : : {
2460 : : /* Node is a range. These cases are very similar to those for a single
2461 : : value, except that we do not start by testing whether this node
2462 : : is the one to branch to. */
2463 : 14212 : if (node->has_child () || node->m_c->get_type () != SIMPLE_CASE)
2464 : : {
2465 : 4714 : bool is_bt = node->m_c->get_type () == BIT_TEST;
2466 : 4714 : int parts = is_bt ? 3 : 2;
2467 : :
2468 : : /* Branch to a label where we will handle it later. */
2469 : 4714 : basic_block test_bb = split_edge (single_succ_edge (bb));
2470 : 4714 : redirect_edge_succ (single_pred_edge (test_bb),
2471 : 4714 : single_succ_edge (bb)->dest);
2472 : :
2473 : 4714 : profile_probability right_prob = profile_probability::never ();
2474 : 4714 : if (node->m_right)
2475 : 3638 : right_prob = node->m_right->m_c->m_subtree_prob;
2476 : 14142 : p = ((right_prob + default_prob / parts)
2477 : 4714 : / (node->m_c->m_subtree_prob + default_prob));
2478 : 4714 : test_bb->count = bb->count.apply_probability (p);
2479 : :
2480 : 4714 : bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
2481 : : GT_EXPR, test_bb, p, loc);
2482 : :
2483 : 4714 : default_prob /= parts;
2484 : 4714 : node->m_c->m_subtree_prob -= right_prob;
2485 : 4714 : if (is_bt)
2486 : 1140 : node->m_c->m_default_prob = default_prob;
2487 : :
2488 : : /* Value belongs to this node or to the left-hand subtree. */
2489 : 4714 : p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
2490 : 4714 : bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
2491 : : GE_EXPR, node->m_c->m_case_bb, p, loc);
2492 : :
2493 : : /* Handle the left-hand subtree. */
2494 : 4714 : bb = emit_case_nodes (bb, index, node->m_left, default_prob,
2495 : : index_type, loc);
2496 : :
2497 : : /* If the left-hand subtree fell through,
2498 : : don't let it fall into the right-hand subtree. */
2499 : 4714 : if (bb && m_default_bb)
2500 : 4419 : emit_jump (bb, m_default_bb);
2501 : :
2502 : 4714 : bb = emit_case_nodes (test_bb, index, node->m_right, default_prob,
2503 : : index_type, loc);
2504 : : }
2505 : : else
2506 : : {
2507 : : /* Node has no children so we check low and high bounds to remove
2508 : : redundant tests. Only one of the bounds can exist,
2509 : : since otherwise this node is bounded--a case tested already. */
2510 : 4402 : tree lhs, rhs;
2511 : 4402 : generate_range_test (bb, index, node->m_c->get_low (),
2512 : 4402 : node->m_c->get_high (), &lhs, &rhs);
2513 : 4402 : p = default_prob / (node->m_c->m_subtree_prob + default_prob);
2514 : :
2515 : 4402 : bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,
2516 : : m_default_bb, p, loc);
2517 : :
2518 : 4402 : emit_jump (bb, node->m_c->m_case_bb);
2519 : 4402 : return NULL;
2520 : : }
2521 : : }
2522 : :
2523 : : return bb;
2524 : : }
2525 : :
2526 : : /* The main function of the pass scans statements for switches and invokes
2527 : : process_switch on them. */
2528 : :
2529 : : namespace {
2530 : :
2531 : : const pass_data pass_data_convert_switch =
2532 : : {
2533 : : GIMPLE_PASS, /* type */
2534 : : "switchconv", /* name */
2535 : : OPTGROUP_NONE, /* optinfo_flags */
2536 : : TV_TREE_SWITCH_CONVERSION, /* tv_id */
2537 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
2538 : : 0, /* properties_provided */
2539 : : 0, /* properties_destroyed */
2540 : : 0, /* todo_flags_start */
2541 : : TODO_update_ssa, /* todo_flags_finish */
2542 : : };
2543 : :
2544 : : class pass_convert_switch : public gimple_opt_pass
2545 : : {
2546 : : public:
2547 : 281914 : pass_convert_switch (gcc::context *ctxt)
2548 : 563828 : : gimple_opt_pass (pass_data_convert_switch, ctxt)
2549 : : {}
2550 : :
2551 : : /* opt_pass methods: */
2552 : 2225453 : bool gate (function *) final override
2553 : : {
2554 : 2225453 : return flag_tree_switch_conversion != 0;
2555 : : }
2556 : : unsigned int execute (function *) final override;
2557 : :
2558 : : }; // class pass_convert_switch
2559 : :
2560 : : unsigned int
2561 : 2128376 : pass_convert_switch::execute (function *fun)
2562 : : {
2563 : 2128376 : basic_block bb;
2564 : 2128376 : bool cfg_altered = false;
2565 : :
2566 : 12849795 : FOR_EACH_BB_FN (bb, fun)
2567 : : {
2568 : 31894784 : if (gswitch *stmt = safe_dyn_cast <gswitch *> (*gsi_last_bb (bb)))
2569 : : {
2570 : 26135 : if (dump_file)
2571 : : {
2572 : 31 : expanded_location loc = expand_location (gimple_location (stmt));
2573 : :
2574 : 31 : fprintf (dump_file, "beginning to process the following "
2575 : : "SWITCH statement (%s:%d) : ------- \n",
2576 : : loc.file, loc.line);
2577 : 31 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2578 : 31 : putc ('\n', dump_file);
2579 : : }
2580 : :
2581 : 26135 : switch_conversion sconv;
2582 : 26135 : sconv.expand (stmt);
2583 : 26135 : cfg_altered |= sconv.m_cfg_altered;
2584 : 26135 : if (!sconv.m_reason)
2585 : : {
2586 : 616 : if (dump_file)
2587 : : {
2588 : 28 : fputs ("Switch converted\n", dump_file);
2589 : 28 : fputs ("--------------------------------\n", dump_file);
2590 : : }
2591 : :
2592 : : /* Make no effort to update the post-dominator tree.
2593 : : It is actually not that hard for the transformations
2594 : : we have performed, but it is not supported
2595 : : by iterate_fix_dominators. */
2596 : 616 : free_dominance_info (CDI_POST_DOMINATORS);
2597 : : }
2598 : : else
2599 : : {
2600 : 25519 : if (dump_file)
2601 : : {
2602 : 3 : fputs ("Bailing out - ", dump_file);
2603 : 3 : fputs (sconv.m_reason, dump_file);
2604 : 3 : fputs ("\n--------------------------------\n", dump_file);
2605 : : }
2606 : : }
2607 : 26135 : }
2608 : : }
2609 : :
2610 : 2128376 : return cfg_altered ? TODO_cleanup_cfg : 0;;
2611 : : }
2612 : :
2613 : : } // anon namespace
2614 : :
2615 : : gimple_opt_pass *
2616 : 281914 : make_pass_convert_switch (gcc::context *ctxt)
2617 : : {
2618 : 281914 : return new pass_convert_switch (ctxt);
2619 : : }
2620 : :
2621 : : /* The main function of the pass scans statements for switches and invokes
2622 : : process_switch on them. */
2623 : :
2624 : : namespace {
2625 : :
2626 : : template <bool O0> class pass_lower_switch: public gimple_opt_pass
2627 : : {
2628 : : public:
2629 : 1691484 : pass_lower_switch (gcc::context *ctxt) : gimple_opt_pass (data, ctxt) {}
2630 : :
2631 : : static const pass_data data;
2632 : : opt_pass *
2633 : 281914 : clone () final override
2634 : : {
2635 : 281914 : return new pass_lower_switch<O0> (m_ctxt);
2636 : : }
2637 : :
2638 : : bool
2639 : 2415436 : gate (function *) final override
2640 : : {
2641 : 2415436 : return !O0 || !optimize;
2642 : : }
2643 : :
2644 : : unsigned int execute (function *fun) final override;
2645 : : }; // class pass_lower_switch
2646 : :
2647 : : template <bool O0>
2648 : : const pass_data pass_lower_switch<O0>::data = {
2649 : : GIMPLE_PASS, /* type */
2650 : : O0 ? "switchlower_O0" : "switchlower", /* name */
2651 : : OPTGROUP_NONE, /* optinfo_flags */
2652 : : TV_TREE_SWITCH_LOWERING, /* tv_id */
2653 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
2654 : : 0, /* properties_provided */
2655 : : 0, /* properties_destroyed */
2656 : : 0, /* todo_flags_start */
2657 : : TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
2658 : : };
2659 : :
2660 : : template <bool O0>
2661 : : unsigned int
2662 : 1427461 : pass_lower_switch<O0>::execute (function *fun)
2663 : : {
2664 : : basic_block bb;
2665 : 1427461 : bool expanded = false;
2666 : :
2667 : 1427461 : auto_vec<gimple *> switch_statements;
2668 : 1427461 : switch_statements.create (1);
2669 : :
2670 : 14025569 : FOR_EACH_BB_FN (bb, fun)
2671 : : {
2672 : 24872727 : if (gswitch *swtch = safe_dyn_cast <gswitch *> (*gsi_last_bb (bb)))
2673 : : {
2674 : : if (!O0)
2675 : 27397 : group_case_labels_stmt (swtch);
2676 : 42919 : switch_statements.safe_push (swtch);
2677 : : }
2678 : : }
2679 : :
2680 : 2940760 : for (unsigned i = 0; i < switch_statements.length (); i++)
2681 : : {
2682 : 42919 : gimple *stmt = switch_statements[i];
2683 : 42919 : if (dump_file)
2684 : : {
2685 : 22 : expanded_location loc = expand_location (gimple_location (stmt));
2686 : :
2687 : 22 : fprintf (dump_file, "beginning to process the following "
2688 : : "SWITCH statement (%s:%d) : ------- \n",
2689 : : loc.file, loc.line);
2690 : 22 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2691 : 22 : putc ('\n', dump_file);
2692 : : }
2693 : :
2694 : 42919 : gswitch *swtch = dyn_cast<gswitch *> (stmt);
2695 : : if (swtch)
2696 : : {
2697 : 42919 : switch_decision_tree dt (swtch);
2698 : 42919 : expanded |= dt.analyze_switch_statement ();
2699 : 42919 : }
2700 : : }
2701 : :
2702 : 1427461 : if (expanded)
2703 : : {
2704 : 32261 : free_dominance_info (CDI_DOMINATORS);
2705 : 32261 : free_dominance_info (CDI_POST_DOMINATORS);
2706 : 32261 : mark_virtual_operands_for_renaming (cfun);
2707 : : }
2708 : :
2709 : 1427461 : return 0;
2710 : 1427461 : }
2711 : :
2712 : : } // anon namespace
2713 : :
2714 : : gimple_opt_pass *
2715 : 281914 : make_pass_lower_switch_O0 (gcc::context *ctxt)
2716 : : {
2717 : 281914 : return new pass_lower_switch<true> (ctxt);
2718 : : }
2719 : : gimple_opt_pass *
2720 : 281914 : make_pass_lower_switch (gcc::context *ctxt)
2721 : : {
2722 : 281914 : return new pass_lower_switch<false> (ctxt);
2723 : : }
|
