Line data Source code
1 : /* Lower GIMPLE_SWITCH expressions to something more efficient than
2 : a jump table.
3 : Copyright (C) 2006-2026 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 : #include "hwint.h"
56 : #include "internal-fn.h"
57 : #include "diagnostic-core.h"
58 :
59 : /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
60 : type in the GIMPLE type system that is language-independent? */
61 : #include "langhooks.h"
62 :
63 : #include "tree-switch-conversion.h"
64 :
65 : using namespace tree_switch_conversion;
66 :
67 : /* Does the target have optabs needed to efficiently compute exact base two
68 : logarithm of a variable with type TYPE?
69 :
70 : If yes, returns TYPE. If no, returns NULL_TREE. May also return another
71 : type. This indicates that logarithm of the variable can be computed but
72 : only after it is converted to this type.
73 :
74 : Also see gen_log2. */
75 :
76 : static tree
77 7016 : can_log2 (tree type, optimization_type opt_type)
78 : {
79 : /* Check if target supports FFS for given type. */
80 7016 : if (direct_internal_fn_supported_p (IFN_FFS, type, opt_type))
81 : return type;
82 :
83 : /* Check if target supports FFS for some type we could convert to. */
84 1869 : int prec = TYPE_PRECISION (type);
85 1869 : int i_prec = TYPE_PRECISION (integer_type_node);
86 1869 : int li_prec = TYPE_PRECISION (long_integer_type_node);
87 1869 : int lli_prec = TYPE_PRECISION (long_long_integer_type_node);
88 1869 : tree new_type;
89 1869 : if (prec <= i_prec
90 1869 : && direct_internal_fn_supported_p (IFN_FFS, integer_type_node, opt_type))
91 1849 : new_type = integer_type_node;
92 20 : else if (prec <= li_prec
93 20 : && direct_internal_fn_supported_p (IFN_FFS, long_integer_type_node,
94 : opt_type))
95 0 : new_type = long_integer_type_node;
96 20 : else if (prec <= lli_prec
97 20 : && direct_internal_fn_supported_p (IFN_FFS,
98 : long_long_integer_type_node,
99 : opt_type))
100 0 : new_type = long_long_integer_type_node;
101 : else
102 20 : return NULL_TREE;
103 : return new_type;
104 : }
105 :
106 : /* Assume that OP is a power of two. Build a sequence of gimple statements
107 : efficiently computing the base two logarithm of OP using special optabs.
108 : Return the ssa name representing the result of the logarithm through RESULT.
109 :
110 : Before computing the logarithm, OP may have to be converted to another type.
111 : This should be specified in TYPE. Use can_log2 to decide what this type
112 : should be.
113 :
114 : Should only be used if can_log2 doesn't reject the type of OP. */
115 :
116 : static gimple_seq
117 21 : gen_log2 (tree op, location_t loc, tree *result, tree type)
118 : {
119 21 : gimple_seq stmts = NULL;
120 :
121 21 : tree orig_type = TREE_TYPE (op);
122 21 : tree tmp1;
123 21 : if (type != orig_type)
124 4 : tmp1 = gimple_convert (&stmts, loc, type, op);
125 : else
126 : tmp1 = op;
127 : /* Build FFS (op) - 1. */
128 21 : tree tmp2 = gimple_build (&stmts, loc, IFN_FFS, orig_type, tmp1);
129 21 : tree tmp3 = gimple_build (&stmts, loc, MINUS_EXPR,
130 : orig_type, tmp2, build_one_cst (orig_type));
131 21 : *result = tmp3;
132 21 : return stmts;
133 : }
134 :
135 : /* Build a sequence of gimple statements checking that OP is a power of 2.
136 : Return the result as a boolean_type_node ssa name through RESULT. Assumes
137 : that OP's value will be non-negative. The generated check may give
138 : arbitrary answer for negative values. */
139 :
140 : static gimple_seq
141 21 : gen_pow2p (tree op, location_t loc, tree *result)
142 : {
143 21 : gimple_seq stmts = NULL;
144 :
145 21 : tree type = TREE_TYPE (op);
146 21 : tree utype = unsigned_type_for (type);
147 :
148 : /* Build (op ^ (op - 1)) > (op - 1). */
149 21 : tree tmp1;
150 21 : if (types_compatible_p (type, utype))
151 : tmp1 = op;
152 : else
153 13 : tmp1 = gimple_convert (&stmts, loc, utype, op);
154 21 : tree tmp2 = gimple_build (&stmts, loc, MINUS_EXPR, utype,
155 : tmp1, build_one_cst (utype));
156 21 : tree tmp3 = gimple_build (&stmts, loc, BIT_XOR_EXPR, utype, tmp1, tmp2);
157 21 : *result = gimple_build (&stmts, loc, GT_EXPR, boolean_type_node, tmp3, tmp2);
158 :
159 21 : return stmts;
160 : }
161 :
162 :
163 : /* Constructor. */
164 :
165 27019 : switch_conversion::switch_conversion (): m_final_bb (NULL),
166 27019 : m_constructors (NULL), m_default_values (NULL),
167 27019 : m_arr_ref_first (NULL), m_arr_ref_last (NULL),
168 27019 : m_reason (NULL), m_default_case_nonstandard (false), m_cfg_altered (false),
169 27019 : m_exp_index_transform_applied (false)
170 : {
171 27019 : }
172 :
173 : /* Collection information about SWTCH statement. */
174 :
175 : void
176 27019 : switch_conversion::collect (gswitch *swtch)
177 : {
178 27019 : unsigned int branch_num = gimple_switch_num_labels (swtch);
179 27019 : tree min_case, max_case;
180 27019 : unsigned int i;
181 27019 : edge e, e_default, e_first;
182 27019 : edge_iterator ei;
183 :
184 27019 : m_switch = swtch;
185 :
186 : /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
187 : is a default label which is the first in the vector.
188 : Collect the bits we can deduce from the CFG. */
189 27019 : m_index_expr = gimple_switch_index (swtch);
190 27019 : m_switch_bb = gimple_bb (swtch);
191 27019 : e_default = gimple_switch_default_edge (cfun, swtch);
192 27019 : m_default_bb = e_default->dest;
193 27019 : m_default_prob = e_default->probability;
194 :
195 : /* Get upper and lower bounds of case values, and the covered range. */
196 27019 : min_case = gimple_switch_label (swtch, 1);
197 27019 : max_case = gimple_switch_label (swtch, branch_num - 1);
198 :
199 27019 : m_range_min = CASE_LOW (min_case);
200 27019 : if (CASE_HIGH (max_case) != NULL_TREE)
201 1740 : m_range_max = CASE_HIGH (max_case);
202 : else
203 25279 : m_range_max = CASE_LOW (max_case);
204 :
205 27019 : m_contiguous_range = true;
206 27019 : tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : m_range_min;
207 90188 : for (i = 2; i < branch_num; i++)
208 : {
209 77824 : tree elt = gimple_switch_label (swtch, i);
210 77825 : if (wi::to_wide (last) + 1 != wi::to_wide (CASE_LOW (elt)))
211 : {
212 14655 : m_contiguous_range = false;
213 14655 : break;
214 : }
215 63169 : last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt);
216 : }
217 :
218 27019 : if (m_contiguous_range)
219 12364 : e_first = gimple_switch_edge (cfun, swtch, 1);
220 : else
221 : e_first = e_default;
222 :
223 : /* See if there is one common successor block for all branch
224 : targets. If it exists, record it in FINAL_BB.
225 : Start with the destination of the first non-default case
226 : if the range is contiguous and default case otherwise as
227 : guess or its destination in case it is a forwarder block. */
228 27019 : if (! single_pred_p (e_first->dest))
229 8369 : m_final_bb = e_first->dest;
230 18650 : else if (single_succ_p (e_first->dest)
231 17226 : && ! single_pred_p (single_succ (e_first->dest)))
232 13037 : m_final_bb = single_succ (e_first->dest);
233 : /* Require that all switch destinations are either that common
234 : FINAL_BB or a forwarder to it, except for the default
235 : case if contiguous range. */
236 27019 : auto_vec<edge, 10> fw_edges;
237 27019 : m_uniq = 0;
238 27019 : if (m_final_bb)
239 108542 : FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
240 : {
241 96657 : edge phi_e = nullptr;
242 96657 : if (e->dest == m_final_bb)
243 14271 : phi_e = e;
244 82386 : else if (single_pred_p (e->dest)
245 169853 : && single_succ_p (e->dest)
246 155582 : && single_succ (e->dest) == m_final_bb)
247 70509 : phi_e = single_succ_edge (e->dest);
248 96657 : if (phi_e)
249 : {
250 84780 : if (e == e_default)
251 : ;
252 66071 : else if (phi_e == e || empty_block_p (e->dest))
253 : {
254 : /* For empty blocks consider forwarders with equal
255 : PHI arguments in m_final_bb as unique. */
256 : unsigned i;
257 161077 : for (i = 0; i < fw_edges.length (); ++i)
258 136141 : if (phi_alternatives_equal (m_final_bb, fw_edges[i], phi_e))
259 : break;
260 50104 : if (i == fw_edges.length ())
261 : {
262 : /* But limit the above possibly quadratic search. */
263 24936 : if (fw_edges.length () < 10)
264 16432 : fw_edges.quick_push (phi_e);
265 24936 : m_uniq++;
266 : }
267 : }
268 : else
269 41019 : m_uniq++;
270 87136 : continue;
271 84780 : }
272 :
273 11877 : if (e == e_default && m_contiguous_range)
274 : {
275 2356 : m_default_case_nonstandard = true;
276 2356 : continue;
277 : }
278 :
279 9521 : m_final_bb = NULL;
280 9521 : break;
281 : }
282 :
283 : /* When there's not a single common successor block conservatively
284 : approximate the number of unique non-default targets. */
285 27019 : if (!m_final_bb)
286 30268 : m_uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
287 :
288 27019 : m_range_size
289 27019 : = int_const_binop (MINUS_EXPR, m_range_max, m_range_min);
290 :
291 : /* Get a count of the number of case labels. Single-valued case labels
292 : simply count as one, but a case range counts double, since it may
293 : require two compares if it gets lowered as a branching tree. */
294 27019 : m_count = 0;
295 177729 : for (i = 1; i < branch_num; i++)
296 : {
297 150710 : tree elt = gimple_switch_label (swtch, i);
298 150710 : m_count++;
299 150710 : if (CASE_HIGH (elt)
300 150710 : && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
301 9027 : m_count++;
302 : }
303 27019 : }
304 :
305 : /* Check that the "exponential index transform" can be applied to this switch.
306 :
307 : See comment of the exp_index_transform function for details about this
308 : transformation.
309 :
310 : We want:
311 : - This form of the switch is more efficient
312 : - Cases are powers of 2
313 :
314 : Expects that SWTCH has at least one case. */
315 :
316 : bool
317 7016 : switch_conversion::is_exp_index_transform_viable (gswitch *swtch)
318 : {
319 7016 : tree index = gimple_switch_index (swtch);
320 7016 : tree index_type = TREE_TYPE (index);
321 7016 : basic_block swtch_bb = gimple_bb (swtch);
322 7016 : unsigned num_labels = gimple_switch_num_labels (swtch);
323 :
324 7016 : optimization_type opt_type = bb_optimization_type (swtch_bb);
325 7016 : m_exp_index_transform_log2_type = can_log2 (index_type, opt_type);
326 7016 : if (!m_exp_index_transform_log2_type)
327 : return false;
328 :
329 : /* Check that each case label corresponds only to one value
330 : (no case 1..3). */
331 : unsigned i;
332 57585 : for (i = 1; i < num_labels; i++)
333 : {
334 50993 : tree label = gimple_switch_label (swtch, i);
335 50993 : if (CASE_HIGH (label))
336 : return false;
337 : }
338 :
339 : /* Check that each label is nonnegative and a power of 2. */
340 8755 : for (i = 1; i < num_labels; i++)
341 : {
342 8653 : tree label = gimple_switch_label (swtch, i);
343 8653 : wide_int label_wi = wi::to_wide (CASE_LOW (label));
344 8653 : if (!wi::ge_p (label_wi, 0, TYPE_SIGN (index_type)))
345 : return false;
346 8528 : if (wi::exact_log2 (label_wi) == -1)
347 : return false;
348 8653 : }
349 :
350 102 : if (dump_file)
351 12 : fprintf (dump_file, "Exponential index transform viable\n");
352 :
353 : return true;
354 : }
355 :
356 : /* Perform the "exponential index transform".
357 :
358 : Assume that cases of SWTCH are powers of 2. The transformation replaces the
359 : cases by their exponents (2^k -> k). It also inserts a statement that
360 : computes the exponent of the original index variable (basically taking the
361 : logarithm) and then sets the result as the new index variable.
362 :
363 : The transformation also inserts a conditional statement checking that the
364 : incoming original index variable is a power of 2 with the false edge leading
365 : to the default case.
366 :
367 : The exponential index transform shrinks the range of case numbers which
368 : helps switch conversion convert switches it otherwise could not.
369 :
370 : Consider for example:
371 :
372 : switch (i)
373 : {
374 : case (1 << 0): return 0;
375 : case (1 << 1): return 1;
376 : case (1 << 2): return 2;
377 : ...
378 : case (1 << 30): return 30;
379 : default: return 31;
380 : }
381 :
382 : First, exponential index transform gets applied. Since each case becomes
383 : case x: return x;, the rest of switch conversion is then able to get rid of
384 : the switch statement.
385 :
386 : if (i is power of 2)
387 : return log2 (i);
388 : else
389 : return 31;
390 :
391 : */
392 :
393 : void
394 21 : switch_conversion::exp_index_transform (gswitch *swtch)
395 : {
396 21 : if (dump_file)
397 11 : fprintf (dump_file, "Applying exponential index transform\n");
398 :
399 21 : tree index = gimple_switch_index (swtch);
400 21 : tree index_type = TREE_TYPE (index);
401 21 : basic_block swtch_bb = gimple_bb (swtch);
402 21 : unsigned num_labels = gimple_switch_num_labels (swtch);
403 :
404 : /* Insert a cond stmt that checks if the index variable is a power of 2. */
405 21 : gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
406 21 : gsi_prev (&gsi);
407 21 : gimple *foo = gsi_stmt (gsi);
408 21 : edge new_edge1 = split_block (swtch_bb, foo);
409 :
410 21 : swtch_bb = new_edge1->dest;
411 21 : basic_block cond_bb = new_edge1->src;
412 21 : new_edge1->flags |= EDGE_TRUE_VALUE;
413 21 : new_edge1->flags &= ~EDGE_FALLTHRU;
414 21 : new_edge1->probability = profile_probability::even ();
415 :
416 21 : basic_block default_bb = gimple_switch_default_bb (cfun, swtch);
417 21 : edge new_edge2 = make_edge (cond_bb, default_bb, EDGE_FALSE_VALUE);
418 21 : new_edge2->probability = profile_probability::even ();
419 :
420 21 : tree tmp;
421 21 : gimple_seq stmts = gen_pow2p (index, UNKNOWN_LOCATION, &tmp);
422 21 : gsi = gsi_last_bb (cond_bb);
423 21 : gsi_insert_seq_after (&gsi, stmts, GSI_LAST_NEW_STMT);
424 21 : gcond *stmt_cond = gimple_build_cond (NE_EXPR, tmp, boolean_false_node,
425 : NULL, NULL);
426 21 : gsi_insert_after (&gsi, stmt_cond, GSI_NEW_STMT);
427 :
428 : /* We just added an edge going to default bb so fix PHI nodes in that bb:
429 : For each PHI add new PHI arg. It will be the same arg as when coming to
430 : the default bb from the switch bb. */
431 21 : edge default_edge = find_edge (swtch_bb, default_bb);
432 21 : for (gphi_iterator gsi = gsi_start_phis (default_bb);
433 33 : !gsi_end_p (gsi); gsi_next (&gsi))
434 : {
435 12 : gphi *phi = gsi.phi ();
436 12 : tree arg = PHI_ARG_DEF_FROM_EDGE (phi, default_edge);
437 12 : location_t loc = gimple_phi_arg_location_from_edge (phi, default_edge);
438 12 : add_phi_arg (phi, arg, new_edge2, loc);
439 : }
440 :
441 : /* Insert a sequence of stmts that takes the log of the index variable. */
442 21 : stmts = gen_log2 (index, UNKNOWN_LOCATION, &tmp,
443 : m_exp_index_transform_log2_type);
444 21 : gsi = gsi_after_labels (swtch_bb);
445 21 : gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
446 :
447 : /* Use the result of the logarithm as the new index variable. */
448 21 : gimple_switch_set_index (swtch, tmp);
449 21 : update_stmt (swtch);
450 :
451 : /* Replace each case number with its logarithm. */
452 21 : unsigned i;
453 134 : for (i = 1; i < num_labels; i++)
454 : {
455 113 : tree label = gimple_switch_label (swtch, i);
456 226 : CASE_LOW (label) = build_int_cst (index_type,
457 113 : tree_log2 (CASE_LOW (label)));
458 : }
459 :
460 : /* Fix the dominator tree, if it is available. */
461 21 : if (dom_info_available_p (CDI_DOMINATORS))
462 : {
463 : /* Analysis of how dominators should look after we add the edge E going
464 : from the cond block to the default block.
465 :
466 : 1 For the blocks between the switch block and the final block
467 : (excluding the final block itself): They had the switch block as
468 : their immediate dominator. That shouldn't change.
469 :
470 : 2 The final block may now have the switch block or the cond block as
471 : its immediate dominator. There's no easy way of knowing (consider
472 : two cases where in both m_default_case_nonstandard = true, in one a
473 : path through default intersects the final block and in one all paths
474 : through default avoid the final block but intersect a successor of the
475 : final block).
476 :
477 : 3 Other blocks that had the switch block as their immediate dominator
478 : should now have the cond block as their immediate dominator.
479 :
480 : 4 Immediate dominators of the rest of the blocks shouldn't change.
481 :
482 : Reasoning for 3 and 4:
483 :
484 : We'll only consider blocks that do not fall into 1 or 2.
485 :
486 : Consider a block X whose original imm dom was the switch block. All
487 : paths to X must also intersect the cond block since it's the only
488 : pred of the switch block. The final block doesn't dominate X so at
489 : least one path P must lead through the default block. Let P' be P but
490 : instead of going through the switch block, take E. The switch block
491 : doesn't dominate X so its imm dom must now be the cond block.
492 :
493 : Consider a block X whose original imm dom was Y != the switch block.
494 : We only added an edge so all original paths to X are still present.
495 : So X gained no new dominators. Observe that Y still dominates X.
496 : There would have to be a path that avoids Y otherwise. But any block
497 : we can avoid now except for the switch block we were able to avoid
498 : before adding E. */
499 :
500 21 : redirect_immediate_dominators (CDI_DOMINATORS, swtch_bb, cond_bb);
501 :
502 21 : edge e;
503 21 : edge_iterator ei;
504 155 : FOR_EACH_EDGE (e, ei, swtch_bb->succs)
505 : {
506 134 : basic_block bb = e->dest;
507 134 : if (bb == m_final_bb || bb == default_bb)
508 30 : continue;
509 104 : set_immediate_dominator (CDI_DOMINATORS, bb, swtch_bb);
510 : }
511 :
512 21 : vec<basic_block> v;
513 21 : v.create (1);
514 21 : v.quick_push (m_final_bb);
515 21 : iterate_fix_dominators (CDI_DOMINATORS, v, true);
516 : }
517 :
518 : /* Update information about the switch statement. */
519 21 : tree first_label = gimple_switch_label (swtch, 1);
520 21 : tree last_label = gimple_switch_label (swtch, num_labels - 1);
521 :
522 21 : m_range_min = CASE_LOW (first_label);
523 21 : m_range_max = CASE_LOW (last_label);
524 21 : m_index_expr = gimple_switch_index (swtch);
525 21 : m_switch_bb = swtch_bb;
526 :
527 21 : m_range_size = int_const_binop (MINUS_EXPR, m_range_max, m_range_min);
528 :
529 21 : m_cfg_altered = true;
530 :
531 21 : m_contiguous_range = true;
532 21 : wide_int last_wi = wi::to_wide (CASE_LOW (first_label));
533 113 : for (i = 2; i < num_labels; i++)
534 : {
535 92 : tree label = gimple_switch_label (swtch, i);
536 92 : wide_int label_wi = wi::to_wide (CASE_LOW (label));
537 92 : m_contiguous_range &= wi::eq_p (wi::add (last_wi, 1), label_wi);
538 92 : last_wi = label_wi;
539 92 : }
540 :
541 21 : m_exp_index_transform_applied = true;
542 21 : }
543 :
544 : /* Checks whether the range given by individual case statements of the switch
545 : switch statement isn't too big and whether the number of branches actually
546 : satisfies the size of the new array. */
547 :
548 : bool
549 6914 : switch_conversion::check_range ()
550 : {
551 6914 : gcc_assert (m_range_size);
552 6914 : if (!tree_fits_uhwi_p (m_range_size))
553 : {
554 18 : m_reason = "index range way too large or otherwise unusable";
555 18 : return false;
556 : }
557 :
558 6896 : if (tree_to_uhwi (m_range_size)
559 6896 : > ((unsigned) m_count * param_switch_conversion_branch_ratio))
560 : {
561 430 : m_reason = "the maximum range-branch ratio exceeded";
562 430 : return false;
563 : }
564 :
565 : return true;
566 : }
567 :
568 : /* Checks whether all but the final BB basic blocks are empty. */
569 :
570 : bool
571 6568 : switch_conversion::check_all_empty_except_final ()
572 : {
573 6568 : edge e, e_default = find_edge (m_switch_bb, m_default_bb);
574 6568 : edge_iterator ei;
575 :
576 30331 : FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
577 : {
578 28758 : if (e->dest == m_final_bb)
579 4969 : continue;
580 :
581 23789 : if (!empty_block_p (e->dest))
582 : {
583 6206 : if (m_contiguous_range && e == e_default)
584 : {
585 1211 : m_default_case_nonstandard = true;
586 1211 : continue;
587 : }
588 :
589 4995 : m_reason = "bad case - a non-final BB not empty";
590 4995 : return false;
591 : }
592 : }
593 :
594 : return true;
595 : }
596 :
597 : /* This function checks whether all required values in phi nodes in final_bb
598 : are constants. Required values are those that correspond to a basic block
599 : which is a part of the examined switch statement. It returns true if the
600 : phi nodes are OK, otherwise false. */
601 :
602 : bool
603 1573 : switch_conversion::check_final_bb ()
604 : {
605 1573 : gphi_iterator gsi;
606 :
607 1573 : m_phi_count = 0;
608 2217 : for (gsi = gsi_start_phis (m_final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
609 : {
610 1650 : gphi *phi = gsi.phi ();
611 1650 : unsigned int i;
612 :
613 3300 : if (virtual_operand_p (gimple_phi_result (phi)))
614 20 : continue;
615 :
616 1630 : m_phi_count++;
617 :
618 19444 : for (i = 0; i < gimple_phi_num_args (phi); i++)
619 : {
620 18820 : basic_block bb = gimple_phi_arg_edge (phi, i)->src;
621 :
622 18820 : if (bb == m_switch_bb
623 53809 : || (single_pred_p (bb)
624 17175 : && single_pred (bb) == m_switch_bb
625 16985 : && (!m_default_case_nonstandard
626 491 : || empty_block_p (bb))))
627 : {
628 18589 : tree reloc, val;
629 18589 : const char *reason = NULL;
630 :
631 18589 : val = gimple_phi_arg_def (phi, i);
632 18589 : if (!is_gimple_ip_invariant (val))
633 : reason = "non-invariant value from a case";
634 : else
635 : {
636 17635 : reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
637 17635 : if ((flag_pic && reloc != null_pointer_node)
638 17566 : || (!flag_pic && reloc == NULL_TREE))
639 : {
640 69 : if (reloc)
641 : reason
642 : = "value from a case would need runtime relocations";
643 : else
644 : reason
645 : = "value from a case is not a valid initializer";
646 : }
647 : }
648 : if (reason)
649 : {
650 : /* For contiguous range, we can allow non-constant
651 : or one that needs relocation, as long as it is
652 : only reachable from the default case. */
653 1023 : if (bb == m_switch_bb)
654 90 : bb = m_final_bb;
655 1023 : if (!m_contiguous_range || bb != m_default_bb)
656 : {
657 1006 : m_reason = reason;
658 1006 : return false;
659 : }
660 :
661 17 : unsigned int branch_num = gimple_switch_num_labels (m_switch);
662 116 : for (unsigned int i = 1; i < branch_num; i++)
663 : {
664 99 : if (gimple_switch_label_bb (cfun, m_switch, i) == bb)
665 : {
666 0 : m_reason = reason;
667 0 : return false;
668 : }
669 : }
670 17 : m_default_case_nonstandard = true;
671 : }
672 : }
673 : }
674 : }
675 :
676 : return true;
677 : }
678 :
679 : /* The following function allocates default_values, target_{in,out}_names and
680 : constructors arrays. The last one is also populated with pointers to
681 : vectors that will become constructors of new arrays. */
682 :
683 : void
684 567 : switch_conversion::create_temp_arrays ()
685 : {
686 567 : int i;
687 :
688 567 : m_default_values = XCNEWVEC (tree, m_phi_count * 3);
689 : /* ??? Macros do not support multi argument templates in their
690 : argument list. We create a typedef to work around that problem. */
691 567 : typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc;
692 567 : m_constructors = XCNEWVEC (vec_constructor_elt_gc, m_phi_count);
693 567 : m_target_inbound_names = m_default_values + m_phi_count;
694 567 : m_target_outbound_names = m_target_inbound_names + m_phi_count;
695 1189 : for (i = 0; i < m_phi_count; i++)
696 622 : vec_alloc (m_constructors[i], tree_to_uhwi (m_range_size) + 1);
697 567 : }
698 :
699 : /* Populate the array of default values in the order of phi nodes.
700 : DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
701 : if the range is non-contiguous or the default case has standard
702 : structure, otherwise it is the first non-default case instead. */
703 :
704 : void
705 567 : switch_conversion::gather_default_values (tree default_case)
706 : {
707 567 : gphi_iterator gsi;
708 567 : basic_block bb = label_to_block (cfun, CASE_LABEL (default_case));
709 567 : edge e;
710 567 : int i = 0;
711 :
712 567 : gcc_assert (CASE_LOW (default_case) == NULL_TREE
713 : || m_default_case_nonstandard);
714 :
715 567 : if (bb == m_final_bb)
716 236 : e = find_edge (m_switch_bb, bb);
717 : else
718 331 : e = single_succ_edge (bb);
719 :
720 1209 : for (gsi = gsi_start_phis (m_final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
721 : {
722 642 : gphi *phi = gsi.phi ();
723 1284 : if (virtual_operand_p (gimple_phi_result (phi)))
724 20 : continue;
725 622 : tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
726 622 : gcc_assert (val);
727 622 : m_default_values[i++] = val;
728 : }
729 567 : }
730 :
731 : /* The following function populates the vectors in the constructors array with
732 : future contents of the static arrays. The vectors are populated in the
733 : order of phi nodes. */
734 :
735 : void
736 567 : switch_conversion::build_constructors ()
737 : {
738 567 : unsigned i, branch_num = gimple_switch_num_labels (m_switch);
739 567 : tree pos = m_range_min;
740 567 : tree pos_one = build_int_cst (TREE_TYPE (pos), 1);
741 :
742 8366 : for (i = 1; i < branch_num; i++)
743 : {
744 7799 : tree cs = gimple_switch_label (m_switch, i);
745 7799 : basic_block bb = label_to_block (cfun, CASE_LABEL (cs));
746 7799 : edge e;
747 7799 : tree high;
748 7799 : gphi_iterator gsi;
749 7799 : int j;
750 :
751 7799 : if (bb == m_final_bb)
752 407 : e = find_edge (m_switch_bb, bb);
753 : else
754 7392 : e = single_succ_edge (bb);
755 7799 : gcc_assert (e);
756 :
757 10246 : while (tree_int_cst_lt (pos, CASE_LOW (cs)))
758 : {
759 : int k;
760 6326 : for (k = 0; k < m_phi_count; k++)
761 : {
762 3879 : constructor_elt elt;
763 :
764 3879 : elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min);
765 3879 : if (TYPE_PRECISION (TREE_TYPE (elt.index))
766 3879 : > TYPE_PRECISION (sizetype))
767 18 : elt.index = fold_convert (sizetype, elt.index);
768 3879 : elt.value
769 3879 : = unshare_expr_without_location (m_default_values[k]);
770 3879 : m_constructors[k]->quick_push (elt);
771 : }
772 :
773 2447 : pos = int_const_binop (PLUS_EXPR, pos, pos_one);
774 : }
775 7799 : gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
776 :
777 7799 : j = 0;
778 7799 : if (CASE_HIGH (cs))
779 108 : high = CASE_HIGH (cs);
780 : else
781 7691 : high = CASE_LOW (cs);
782 7799 : for (gsi = gsi_start_phis (m_final_bb);
783 16157 : !gsi_end_p (gsi); gsi_next (&gsi))
784 : {
785 8358 : gphi *phi = gsi.phi ();
786 16716 : if (virtual_operand_p (gimple_phi_result (phi)))
787 102 : continue;
788 8256 : tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
789 8256 : tree low = CASE_LOW (cs);
790 8256 : pos = CASE_LOW (cs);
791 :
792 8583 : do
793 : {
794 8583 : constructor_elt elt;
795 :
796 8583 : elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min);
797 8583 : if (TYPE_PRECISION (TREE_TYPE (elt.index))
798 8583 : > TYPE_PRECISION (sizetype))
799 33 : elt.index = fold_convert (sizetype, elt.index);
800 8583 : elt.value = unshare_expr_without_location (val);
801 8583 : m_constructors[j]->quick_push (elt);
802 :
803 8583 : pos = int_const_binop (PLUS_EXPR, pos, pos_one);
804 8583 : } while (!tree_int_cst_lt (high, pos)
805 16839 : && tree_int_cst_lt (low, pos));
806 8256 : j++;
807 : }
808 : }
809 567 : }
810 :
811 : /* If all values in the constructor vector are products of a linear function
812 : a * x + b, then return true. When true, COEFF_A and COEFF_B and
813 : coefficients of the linear function. Note that equal values are special
814 : case of a linear function with a and b equal to zero. */
815 :
816 : bool
817 622 : switch_conversion::contains_linear_function_p (vec<constructor_elt, va_gc> *vec,
818 : wide_int *coeff_a,
819 : wide_int *coeff_b)
820 : {
821 622 : unsigned int i;
822 622 : constructor_elt *elt;
823 :
824 622 : gcc_assert (vec->length () >= 2);
825 :
826 : /* Let's try to find any linear function a * x + y that can apply to
827 : given values. 'a' can be calculated as follows:
828 :
829 : a = (y2 - y1) / (x2 - x1) where x2 - x1 = 1 (consecutive case indices)
830 : a = y2 - y1
831 :
832 : and
833 :
834 : b = y2 - a * x2
835 :
836 : */
837 :
838 622 : tree elt0 = (*vec)[0].value;
839 622 : tree elt1 = (*vec)[1].value;
840 :
841 622 : if (TREE_CODE (elt0) != INTEGER_CST || TREE_CODE (elt1) != INTEGER_CST)
842 : return false;
843 :
844 452 : wide_int range_min
845 452 : = wide_int::from (wi::to_wide (m_range_min),
846 452 : TYPE_PRECISION (TREE_TYPE (elt0)),
847 1356 : TYPE_SIGN (TREE_TYPE (m_range_min)));
848 452 : wide_int y1 = wi::to_wide (elt0);
849 452 : wide_int y2 = wi::to_wide (elt1);
850 452 : wide_int a = y2 - y1;
851 452 : wide_int b = y2 - a * (range_min + 1);
852 :
853 : /* Verify that all values fulfill the linear function. */
854 1863 : FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
855 : {
856 1762 : if (TREE_CODE (elt->value) != INTEGER_CST)
857 351 : return false;
858 :
859 1762 : wide_int value = wi::to_wide (elt->value);
860 1762 : if (a * range_min + b != value)
861 351 : return false;
862 :
863 1411 : ++range_min;
864 1762 : }
865 :
866 101 : *coeff_a = a;
867 101 : *coeff_b = b;
868 :
869 101 : return true;
870 452 : }
871 :
872 : /* Return type which should be used for array elements, either TYPE's
873 : main variant or, for integral types, some smaller integral type
874 : that can still hold all the constants. */
875 :
876 : tree
877 521 : switch_conversion::array_value_type (tree type, int num)
878 : {
879 521 : unsigned int i, len = vec_safe_length (m_constructors[num]);
880 521 : constructor_elt *elt;
881 521 : int sign = 0;
882 521 : tree smaller_type;
883 :
884 : /* Types with alignments greater than their size can reach here, e.g. out of
885 : SRA. We couldn't use these as an array component type so get back to the
886 : main variant first, which, for our purposes, is fine for other types as
887 : well. */
888 :
889 521 : type = TYPE_MAIN_VARIANT (type);
890 :
891 521 : if (!INTEGRAL_TYPE_P (type)
892 521 : || (BITINT_TYPE_P (type)
893 0 : && (TYPE_PRECISION (type) > MAX_FIXED_MODE_SIZE
894 0 : || TYPE_MODE (type) == BLKmode)))
895 170 : return type;
896 :
897 351 : scalar_int_mode type_mode = SCALAR_INT_TYPE_MODE (type);
898 351 : scalar_int_mode mode = get_narrowest_mode (type_mode);
899 1053 : if (GET_MODE_SIZE (type_mode) <= GET_MODE_SIZE (mode))
900 : return type;
901 :
902 474 : if (len < (optimize_bb_for_size_p (gimple_bb (m_switch)) ? 2 : 32))
903 : return type;
904 :
905 2642 : FOR_EACH_VEC_SAFE_ELT (m_constructors[num], i, elt)
906 : {
907 2589 : wide_int cst;
908 :
909 2589 : if (TREE_CODE (elt->value) != INTEGER_CST)
910 : return type;
911 :
912 2589 : cst = wi::to_wide (elt->value);
913 2610 : while (1)
914 : {
915 2612 : unsigned int prec = GET_MODE_BITSIZE (mode);
916 2610 : if (prec > HOST_BITS_PER_WIDE_INT)
917 : return type;
918 :
919 2610 : if (sign >= 0 && cst == wi::zext (cst, prec))
920 : {
921 1411 : if (sign == 0 && cst == wi::sext (cst, prec))
922 : break;
923 457 : sign = 1;
924 457 : break;
925 : }
926 1199 : if (sign <= 0 && cst == wi::sext (cst, prec))
927 : {
928 : sign = -1;
929 : break;
930 : }
931 :
932 23 : if (sign == 1)
933 : sign = 0;
934 :
935 46 : if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
936 48 : || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (type_mode))
937 : return type;
938 : }
939 2589 : }
940 :
941 53 : if (sign == 0)
942 28 : sign = TYPE_UNSIGNED (type) ? 1 : -1;
943 53 : smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
944 53 : if (GET_MODE_SIZE (type_mode)
945 106 : <= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (smaller_type)))
946 : return type;
947 :
948 : return smaller_type;
949 : }
950 :
951 : /* Create an appropriate array type and declaration and assemble a static
952 : array variable. Also create a load statement that initializes
953 : the variable in question with a value from the static array. SWTCH is
954 : the switch statement being converted, NUM is the index to
955 : arrays of constructors, default values and target SSA names
956 : for this particular array. ARR_INDEX_TYPE is the type of the index
957 : of the new array, PHI is the phi node of the final BB that corresponds
958 : to the value that will be loaded from the created array. TIDX
959 : is an ssa name of a temporary variable holding the index for loads from the
960 : new array. */
961 :
962 : void
963 622 : switch_conversion::build_one_array (int num, tree arr_index_type,
964 : gphi *phi, tree tidx)
965 : {
966 622 : tree name;
967 622 : gimple *load;
968 622 : gimple_stmt_iterator gsi = gsi_for_stmt (m_switch);
969 :
970 622 : gcc_assert (m_default_values[num]);
971 :
972 622 : name = copy_ssa_name (PHI_RESULT (phi));
973 622 : m_target_inbound_names[num] = name;
974 :
975 622 : vec<constructor_elt, va_gc> *constructor = m_constructors[num];
976 622 : wide_int coeff_a, coeff_b;
977 622 : bool linear_p = contains_linear_function_p (constructor, &coeff_a, &coeff_b);
978 622 : tree type;
979 622 : if (linear_p
980 622 : && (type = range_check_type (TREE_TYPE ((*constructor)[0].value))))
981 : {
982 118 : if (dump_file && coeff_a.to_uhwi () > 0)
983 16 : fprintf (dump_file, "Linear transformation with A = %" PRId64
984 : " and B = %" PRId64 "\n", coeff_a.to_shwi (),
985 : coeff_b.to_shwi ());
986 :
987 : /* We must use type of constructor values. */
988 101 : gimple_seq seq = NULL;
989 101 : tree tmp = gimple_convert (&seq, type, m_index_expr);
990 202 : tree tmp2 = gimple_build (&seq, MULT_EXPR, type,
991 101 : wide_int_to_tree (type, coeff_a), tmp);
992 202 : tree tmp3 = gimple_build (&seq, PLUS_EXPR, type, tmp2,
993 101 : wide_int_to_tree (type, coeff_b));
994 101 : tree tmp4 = gimple_convert (&seq, TREE_TYPE (name), tmp3);
995 101 : gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
996 101 : load = gimple_build_assign (name, tmp4);
997 : }
998 : else
999 : {
1000 521 : tree array_type, ctor, decl, value_type, fetch, default_type;
1001 :
1002 521 : default_type = TREE_TYPE (m_default_values[num]);
1003 521 : value_type = array_value_type (default_type, num);
1004 521 : array_type = build_array_type (value_type, arr_index_type);
1005 521 : addr_space_t as
1006 521 : = targetm.addr_space.for_artificial_rodata (array_type,
1007 : ARTIFICIAL_RODATA_CSWITCH);
1008 521 : if (!ADDR_SPACE_GENERIC_P (as))
1009 : {
1010 0 : int quals = (TYPE_QUALS_NO_ADDR_SPACE (value_type)
1011 0 : | ENCODE_QUAL_ADDR_SPACE (as));
1012 0 : value_type = build_qualified_type (value_type, quals);
1013 0 : array_type = build_array_type (value_type, arr_index_type);
1014 : }
1015 521 : if (default_type != value_type)
1016 : {
1017 : unsigned int i;
1018 : constructor_elt *elt;
1019 :
1020 3386 : FOR_EACH_VEC_SAFE_ELT (constructor, i, elt)
1021 3272 : elt->value = fold_convert (value_type, elt->value);
1022 : }
1023 521 : ctor = build_constructor (array_type, constructor);
1024 521 : TREE_CONSTANT (ctor) = true;
1025 521 : TREE_STATIC (ctor) = true;
1026 :
1027 521 : decl = build_decl (UNKNOWN_LOCATION, VAR_DECL, NULL_TREE, array_type);
1028 521 : TREE_STATIC (decl) = 1;
1029 521 : DECL_INITIAL (decl) = ctor;
1030 :
1031 521 : DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
1032 521 : DECL_ARTIFICIAL (decl) = 1;
1033 521 : DECL_IGNORED_P (decl) = 1;
1034 521 : TREE_CONSTANT (decl) = 1;
1035 521 : TREE_READONLY (decl) = 1;
1036 521 : DECL_IGNORED_P (decl) = 1;
1037 : /* The decl is mergeable since we don't take the address ever and
1038 : just reading from it. */
1039 521 : DECL_MERGEABLE (decl) = 1;
1040 :
1041 521 : if (offloading_function_p (cfun->decl))
1042 0 : DECL_ATTRIBUTES (decl)
1043 0 : = tree_cons (get_identifier ("omp declare target"), NULL_TREE,
1044 : NULL_TREE);
1045 521 : varpool_node::finalize_decl (decl);
1046 :
1047 521 : fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
1048 : NULL_TREE);
1049 521 : if (default_type != value_type)
1050 : {
1051 114 : fetch = fold_convert (default_type, fetch);
1052 114 : fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
1053 : true, GSI_SAME_STMT);
1054 : }
1055 521 : load = gimple_build_assign (name, fetch);
1056 : }
1057 :
1058 622 : gsi_insert_before (&gsi, load, GSI_SAME_STMT);
1059 622 : update_stmt (load);
1060 622 : m_arr_ref_last = load;
1061 622 : }
1062 :
1063 : /* Builds and initializes static arrays initialized with values gathered from
1064 : the switch statement. Also creates statements that load values from
1065 : them. */
1066 :
1067 : void
1068 567 : switch_conversion::build_arrays ()
1069 : {
1070 567 : tree arr_index_type;
1071 567 : tree tidx, uidx, sub, utype, tidxtype;
1072 567 : gimple *stmt;
1073 567 : gimple_stmt_iterator gsi;
1074 567 : gphi_iterator gpi;
1075 567 : int i;
1076 567 : location_t loc = gimple_location (m_switch);
1077 :
1078 567 : gsi = gsi_for_stmt (m_switch);
1079 :
1080 : /* Make sure we do not generate arithmetics in a subrange. */
1081 567 : utype = TREE_TYPE (m_index_expr);
1082 567 : if (TREE_TYPE (utype))
1083 48 : utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
1084 518 : else if (BITINT_TYPE_P (utype)
1085 520 : && (TYPE_PRECISION (utype) > MAX_FIXED_MODE_SIZE
1086 0 : || TYPE_MODE (utype) == BLKmode))
1087 1 : utype = unsigned_type_for (utype);
1088 : else
1089 518 : utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
1090 567 : if (TYPE_PRECISION (utype) > TYPE_PRECISION (sizetype))
1091 11 : tidxtype = sizetype;
1092 : else
1093 : tidxtype = utype;
1094 :
1095 567 : arr_index_type = build_index_type (m_range_size);
1096 567 : uidx = make_ssa_name (utype);
1097 567 : sub = fold_build2_loc (loc, MINUS_EXPR, utype,
1098 : fold_convert_loc (loc, utype, m_index_expr),
1099 : fold_convert_loc (loc, utype, m_range_min));
1100 567 : sub = force_gimple_operand_gsi (&gsi, sub,
1101 : false, NULL, true, GSI_SAME_STMT);
1102 567 : stmt = gimple_build_assign (uidx, sub);
1103 :
1104 567 : gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1105 567 : m_arr_ref_first = stmt;
1106 :
1107 567 : tidx = uidx;
1108 567 : if (tidxtype != utype)
1109 : {
1110 11 : tidx = make_ssa_name (tidxtype);
1111 11 : stmt = gimple_build_assign (tidx, NOP_EXPR, uidx);
1112 11 : gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1113 : }
1114 :
1115 567 : for (gpi = gsi_start_phis (m_final_bb), i = 0;
1116 1209 : !gsi_end_p (gpi); gsi_next (&gpi))
1117 : {
1118 642 : gphi *phi = gpi.phi ();
1119 1284 : if (!virtual_operand_p (gimple_phi_result (phi)))
1120 622 : build_one_array (i++, arr_index_type, phi, tidx);
1121 : else
1122 : {
1123 20 : edge e;
1124 20 : edge_iterator ei;
1125 24 : FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
1126 : {
1127 24 : if (e->dest == m_final_bb)
1128 : break;
1129 14 : if (!m_default_case_nonstandard
1130 4 : || e->dest != m_default_bb)
1131 : {
1132 10 : e = single_succ_edge (e->dest);
1133 10 : break;
1134 : }
1135 : }
1136 20 : gcc_assert (e && e->dest == m_final_bb);
1137 20 : m_target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e);
1138 : }
1139 : }
1140 567 : }
1141 :
1142 : /* Generates and appropriately inserts loads of default values at the position
1143 : given by GSI. Returns the last inserted statement. */
1144 :
1145 : gassign *
1146 461 : switch_conversion::gen_def_assigns (gimple_stmt_iterator *gsi)
1147 : {
1148 461 : int i;
1149 461 : gassign *assign = NULL;
1150 :
1151 965 : for (i = 0; i < m_phi_count; i++)
1152 : {
1153 504 : tree name = copy_ssa_name (m_target_inbound_names[i]);
1154 504 : m_target_outbound_names[i] = name;
1155 504 : assign = gimple_build_assign (name, m_default_values[i]);
1156 504 : gsi_insert_before (gsi, assign, GSI_SAME_STMT);
1157 504 : update_stmt (assign);
1158 : }
1159 461 : return assign;
1160 : }
1161 :
1162 : /* Deletes the unused bbs and edges that now contain the switch statement and
1163 : its empty branch bbs. BBD is the now dead BB containing
1164 : the original switch statement, FINAL is the last BB of the converted
1165 : switch statement (in terms of succession). */
1166 :
1167 : void
1168 567 : switch_conversion::prune_bbs (basic_block bbd, basic_block final,
1169 : basic_block default_bb)
1170 : {
1171 567 : edge_iterator ei;
1172 567 : edge e;
1173 :
1174 9359 : for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
1175 : {
1176 8225 : basic_block bb;
1177 8225 : bb = e->dest;
1178 8225 : remove_edge (e);
1179 8225 : if (bb != final && bb != default_bb)
1180 7563 : delete_basic_block (bb);
1181 : }
1182 567 : delete_basic_block (bbd);
1183 567 : }
1184 :
1185 : /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
1186 : from the basic block loading values from an array and E2F from the basic
1187 : block loading default values. BBF is the last switch basic block (see the
1188 : bbf description in the comment below). */
1189 :
1190 : void
1191 567 : switch_conversion::fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
1192 : {
1193 567 : gphi_iterator gsi;
1194 567 : int i;
1195 :
1196 567 : for (gsi = gsi_start_phis (bbf), i = 0;
1197 1209 : !gsi_end_p (gsi); gsi_next (&gsi))
1198 : {
1199 642 : gphi *phi = gsi.phi ();
1200 642 : tree inbound, outbound;
1201 1284 : if (virtual_operand_p (gimple_phi_result (phi)))
1202 20 : inbound = outbound = m_target_vop;
1203 : else
1204 : {
1205 622 : inbound = m_target_inbound_names[i];
1206 622 : outbound = m_target_outbound_names[i++];
1207 : }
1208 642 : add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION);
1209 642 : if (!m_default_case_nonstandard)
1210 520 : add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION);
1211 : }
1212 567 : }
1213 :
1214 : /* Creates a check whether the switch expression value actually falls into the
1215 : range given by all the cases. If it does not, the temporaries are loaded
1216 : with default values instead. */
1217 :
1218 : void
1219 567 : switch_conversion::gen_inbound_check ()
1220 : {
1221 567 : tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
1222 567 : tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
1223 567 : tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
1224 567 : glabel *label1, *label2, *label3;
1225 567 : tree utype, tidx;
1226 567 : tree bound;
1227 :
1228 567 : gcond *cond_stmt;
1229 :
1230 567 : gassign *last_assign = NULL;
1231 567 : gimple_stmt_iterator gsi;
1232 567 : basic_block bb0, bb1, bb2, bbf, bbd;
1233 567 : edge e01 = NULL, e02, e21, e1d, e1f, e2f;
1234 567 : location_t loc = gimple_location (m_switch);
1235 :
1236 567 : gcc_assert (m_default_values);
1237 :
1238 567 : bb0 = gimple_bb (m_switch);
1239 :
1240 567 : tidx = gimple_assign_lhs (m_arr_ref_first);
1241 567 : utype = TREE_TYPE (tidx);
1242 :
1243 : /* (end of) block 0 */
1244 567 : gsi = gsi_for_stmt (m_arr_ref_first);
1245 567 : gsi_next (&gsi);
1246 :
1247 567 : bound = fold_convert_loc (loc, utype, m_range_size);
1248 567 : cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
1249 567 : gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1250 567 : update_stmt (cond_stmt);
1251 :
1252 : /* block 2 */
1253 567 : if (!m_default_case_nonstandard)
1254 : {
1255 461 : label2 = gimple_build_label (label_decl2);
1256 461 : gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
1257 461 : last_assign = gen_def_assigns (&gsi);
1258 : }
1259 :
1260 : /* block 1 */
1261 567 : label1 = gimple_build_label (label_decl1);
1262 567 : gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
1263 :
1264 : /* block F */
1265 567 : gsi = gsi_start_bb (m_final_bb);
1266 567 : label3 = gimple_build_label (label_decl3);
1267 567 : gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
1268 :
1269 : /* cfg fix */
1270 567 : e02 = split_block (bb0, cond_stmt);
1271 567 : bb2 = e02->dest;
1272 :
1273 567 : if (m_default_case_nonstandard)
1274 : {
1275 106 : bb1 = bb2;
1276 106 : bb2 = m_default_bb;
1277 106 : e01 = e02;
1278 106 : e01->flags = EDGE_TRUE_VALUE;
1279 106 : e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE);
1280 106 : edge e_default = find_edge (bb1, bb2);
1281 106 : for (gphi_iterator gsi = gsi_start_phis (bb2);
1282 143 : !gsi_end_p (gsi); gsi_next (&gsi))
1283 : {
1284 37 : gphi *phi = gsi.phi ();
1285 37 : tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_default);
1286 37 : add_phi_arg (phi, arg, e02,
1287 : gimple_phi_arg_location_from_edge (phi, e_default));
1288 : }
1289 : /* Partially fix the dominator tree, if it is available. */
1290 106 : if (dom_info_available_p (CDI_DOMINATORS))
1291 106 : redirect_immediate_dominators (CDI_DOMINATORS, bb1, bb0);
1292 : }
1293 : else
1294 : {
1295 461 : e21 = split_block (bb2, last_assign);
1296 461 : bb1 = e21->dest;
1297 461 : remove_edge (e21);
1298 : }
1299 :
1300 567 : e1d = split_block (bb1, m_arr_ref_last);
1301 567 : bbd = e1d->dest;
1302 567 : remove_edge (e1d);
1303 :
1304 : /* Flags and profiles of the edge for in-range values. */
1305 567 : if (!m_default_case_nonstandard)
1306 461 : e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
1307 567 : e01->probability = m_default_prob.invert ();
1308 :
1309 : /* Flags and profiles of the edge taking care of out-of-range values. */
1310 567 : e02->flags &= ~EDGE_FALLTHRU;
1311 567 : e02->flags |= EDGE_FALSE_VALUE;
1312 567 : e02->probability = m_default_prob;
1313 :
1314 567 : bbf = m_final_bb;
1315 :
1316 567 : e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
1317 567 : e1f->probability = profile_probability::always ();
1318 :
1319 567 : if (m_default_case_nonstandard)
1320 : e2f = NULL;
1321 : else
1322 : {
1323 461 : e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
1324 461 : e2f->probability = profile_probability::always ();
1325 : }
1326 :
1327 : /* frequencies of the new BBs */
1328 567 : bb1->count = e01->count ();
1329 567 : bb2->count = e02->count ();
1330 567 : if (!m_default_case_nonstandard)
1331 461 : bbf->count = e1f->count () + e2f->count ();
1332 :
1333 : /* Tidy blocks that have become unreachable. */
1334 1261 : bool prune_default_bb = !m_default_case_nonstandard
1335 567 : && !m_exp_index_transform_applied;
1336 567 : prune_bbs (bbd, m_final_bb, prune_default_bb ? NULL : m_default_bb);
1337 :
1338 : /* Fixup the PHI nodes in bbF. */
1339 567 : fix_phi_nodes (e1f, e2f, bbf);
1340 :
1341 : /* Fix the dominator tree, if it is available. */
1342 567 : if (dom_info_available_p (CDI_DOMINATORS))
1343 : {
1344 567 : vec<basic_block> bbs_to_fix_dom;
1345 :
1346 567 : set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
1347 567 : if (!m_default_case_nonstandard)
1348 461 : set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
1349 567 : if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
1350 : /* If bbD was the immediate dominator ... */
1351 330 : set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
1352 :
1353 582 : bbs_to_fix_dom.create (3 + (bb2 != bbf));
1354 567 : bbs_to_fix_dom.quick_push (bb0);
1355 567 : bbs_to_fix_dom.quick_push (bb1);
1356 567 : if (bb2 != bbf)
1357 552 : bbs_to_fix_dom.quick_push (bb2);
1358 567 : bbs_to_fix_dom.quick_push (bbf);
1359 :
1360 567 : iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
1361 567 : bbs_to_fix_dom.release ();
1362 : }
1363 567 : }
1364 :
1365 : /* The following function is invoked on every switch statement (the current
1366 : one is given in SWTCH) and runs the individual phases of switch
1367 : conversion on it one after another until one fails or the conversion
1368 : is completed. On success, NULL is in m_reason, otherwise points
1369 : to a string with the reason why the conversion failed. */
1370 :
1371 : void
1372 27019 : switch_conversion::expand (gswitch *swtch)
1373 : {
1374 : /* Group case labels so that we get the right results from the heuristics
1375 : that decide on the code generation approach for this switch. */
1376 27019 : m_cfg_altered |= group_case_labels_stmt (swtch);
1377 :
1378 : /* If this switch is now a degenerate case with only a default label,
1379 : there is nothing left for us to do. */
1380 27019 : if (gimple_switch_num_labels (swtch) < 2)
1381 : {
1382 0 : m_reason = "switch is a degenerate case";
1383 0 : return;
1384 : }
1385 :
1386 27019 : collect (swtch);
1387 :
1388 : /* No error markers should reach here (they should be filtered out
1389 : during gimplification). */
1390 27019 : gcc_checking_assert (TREE_TYPE (m_index_expr) != error_mark_node);
1391 :
1392 : /* Prefer bit test if possible. */
1393 27019 : if (tree_fits_uhwi_p (m_range_size)
1394 26949 : && bit_test_cluster::can_be_handled (tree_to_uhwi (m_range_size), m_uniq)
1395 41798 : && bit_test_cluster::is_beneficial (m_count, m_uniq))
1396 : {
1397 2508 : m_reason = "expanding as bit test is preferable";
1398 2508 : return;
1399 : }
1400 :
1401 24511 : if (m_uniq <= 2)
1402 : {
1403 : /* This will be expanded as a decision tree . */
1404 8087 : m_reason = "expanding as jumps is preferable";
1405 8087 : return;
1406 : }
1407 :
1408 : /* If there is no common successor, we cannot do the transformation. */
1409 16424 : if (!m_final_bb)
1410 : {
1411 9408 : m_reason = "no common successor to all case label target blocks found";
1412 9408 : return;
1413 : }
1414 :
1415 : /* Sometimes it is possible to use the "exponential index transform" to help
1416 : switch conversion convert switches which it otherwise could not convert.
1417 : However, we want to do this transform only when we know that switch
1418 : conversion will then really be able to convert the switch. So we first
1419 : check if the transformation is applicable and then maybe later do the
1420 : transformation. */
1421 7016 : bool exp_transform_viable = is_exp_index_transform_viable (swtch);
1422 :
1423 : /* Check the case label values are within reasonable range.
1424 :
1425 : If we will be doing exponential index transform, the range will be always
1426 : reasonable. */
1427 7016 : if (!exp_transform_viable && !check_range ())
1428 : {
1429 448 : gcc_assert (m_reason);
1430 : return;
1431 : }
1432 :
1433 : /* For all the cases, see whether they are empty, the assignments they
1434 : represent constant and so on... */
1435 6568 : if (!check_all_empty_except_final ())
1436 : {
1437 4995 : gcc_assert (m_reason);
1438 : return;
1439 : }
1440 1573 : if (!check_final_bb ())
1441 : {
1442 1006 : gcc_assert (m_reason);
1443 : return;
1444 : }
1445 :
1446 : /* At this point all checks have passed and we can proceed with the
1447 : transformation. */
1448 :
1449 567 : if (exp_transform_viable)
1450 21 : exp_index_transform (swtch);
1451 :
1452 567 : create_temp_arrays ();
1453 1134 : gather_default_values (m_default_case_nonstandard
1454 106 : ? gimple_switch_label (swtch, 1)
1455 461 : : gimple_switch_default_label (swtch));
1456 567 : build_constructors ();
1457 :
1458 567 : build_arrays (); /* Build the static arrays and assignments. */
1459 567 : gen_inbound_check (); /* Build the bounds check. */
1460 :
1461 567 : m_cfg_altered = true;
1462 : }
1463 :
1464 : /* Destructor. */
1465 :
1466 27019 : switch_conversion::~switch_conversion ()
1467 : {
1468 27019 : XDELETEVEC (m_constructors);
1469 27019 : XDELETEVEC (m_default_values);
1470 27019 : }
1471 :
1472 : /* Constructor. */
1473 :
1474 11334 : group_cluster::group_cluster (vec<cluster *> &clusters,
1475 11334 : unsigned start, unsigned end)
1476 : {
1477 11334 : gcc_checking_assert (end - start + 1 >= 1);
1478 11334 : m_prob = profile_probability::never ();
1479 11334 : m_cases.create (end - start + 1);
1480 102784 : for (unsigned i = start; i <= end; i++)
1481 : {
1482 91450 : m_cases.quick_push (static_cast<simple_cluster *> (clusters[i]));
1483 91450 : m_prob += clusters[i]->m_prob;
1484 : }
1485 11334 : m_subtree_prob = m_prob;
1486 11334 : }
1487 :
1488 : /* Destructor. */
1489 :
1490 11334 : group_cluster::~group_cluster ()
1491 : {
1492 102784 : for (unsigned i = 0; i < m_cases.length (); i++)
1493 91450 : delete m_cases[i];
1494 :
1495 11334 : m_cases.release ();
1496 11334 : }
1497 :
1498 : /* Dump content of a cluster. */
1499 :
1500 : void
1501 30 : group_cluster::dump (FILE *f, bool details)
1502 : {
1503 30 : unsigned total_values = 0;
1504 414 : for (unsigned i = 0; i < m_cases.length (); i++)
1505 354 : total_values += m_cases[i]->get_range (m_cases[i]->get_low (),
1506 177 : m_cases[i]->get_high ());
1507 :
1508 : unsigned comparison_count = 0;
1509 207 : for (unsigned i = 0; i < m_cases.length (); i++)
1510 : {
1511 177 : simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
1512 299 : comparison_count += sc->get_comparison_count ();
1513 : }
1514 :
1515 30 : unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ());
1516 48 : fprintf (f, "%s", get_type () == JUMP_TABLE ? "JT" : "BT");
1517 :
1518 30 : if (details)
1519 0 : fprintf (f, "(values:%d comparisons:%d range:" HOST_WIDE_INT_PRINT_DEC
1520 : " density: %.2f%%)", total_values, comparison_count, range,
1521 0 : 100.0f * comparison_count / range);
1522 :
1523 30 : fprintf (f, ":");
1524 30 : PRINT_CASE (f, get_low ());
1525 30 : fprintf (f, "-");
1526 30 : PRINT_CASE (f, get_high ());
1527 30 : fprintf (f, " ");
1528 30 : }
1529 :
1530 : /* Emit GIMPLE code to handle the cluster. */
1531 :
1532 : void
1533 6062 : jump_table_cluster::emit (tree index_expr, tree,
1534 : tree default_label_expr, basic_block default_bb,
1535 : location_t loc)
1536 : {
1537 6062 : tree low = get_low ();
1538 6062 : unsigned HOST_WIDE_INT range = get_range (low, get_high ());
1539 6062 : unsigned HOST_WIDE_INT nondefault_range = 0;
1540 6062 : bool bitint = false;
1541 6062 : gimple_stmt_iterator gsi = gsi_start_bb (m_case_bb);
1542 :
1543 : /* For large/huge _BitInt, subtract low from index_expr, cast to unsigned
1544 : DImode type (get_range doesn't support ranges larger than 64-bits)
1545 : and subtract low from all case values as well. */
1546 12122 : if (BITINT_TYPE_P (TREE_TYPE (index_expr))
1547 6062 : && TYPE_PRECISION (TREE_TYPE (index_expr)) > GET_MODE_PRECISION (DImode))
1548 : {
1549 2 : bitint = true;
1550 2 : tree this_low = low, type;
1551 2 : gimple *g;
1552 2 : gimple_seq seq = NULL;
1553 2 : if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (index_expr)))
1554 : {
1555 1 : type = unsigned_type_for (TREE_TYPE (index_expr));
1556 1 : index_expr = gimple_convert (&seq, type, index_expr);
1557 1 : this_low = fold_convert (type, this_low);
1558 : }
1559 2 : this_low = const_unop (NEGATE_EXPR, TREE_TYPE (this_low), this_low);
1560 2 : index_expr = gimple_build (&seq, PLUS_EXPR, TREE_TYPE (index_expr),
1561 : index_expr, this_low);
1562 2 : type = build_nonstandard_integer_type (GET_MODE_PRECISION (DImode), 1);
1563 2 : g = gimple_build_cond (GT_EXPR, index_expr,
1564 2 : fold_convert (TREE_TYPE (index_expr),
1565 : TYPE_MAX_VALUE (type)),
1566 : NULL_TREE, NULL_TREE);
1567 2 : gimple_seq_add_stmt (&seq, g);
1568 2 : gimple_seq_set_location (seq, loc);
1569 2 : gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
1570 2 : edge e1 = split_block (m_case_bb, g);
1571 2 : e1->flags = EDGE_FALSE_VALUE;
1572 2 : e1->probability = profile_probability::likely ();
1573 2 : edge e2 = make_edge (e1->src, default_bb, EDGE_TRUE_VALUE);
1574 2 : e2->probability = e1->probability.invert ();
1575 2 : gsi = gsi_start_bb (e1->dest);
1576 2 : seq = NULL;
1577 2 : index_expr = gimple_convert (&seq, type, index_expr);
1578 2 : gimple_seq_set_location (seq, loc);
1579 2 : gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
1580 : }
1581 :
1582 : /* For jump table we just emit a new gswitch statement that will
1583 : be latter lowered to jump table. */
1584 6062 : auto_vec <tree> labels;
1585 12124 : labels.create (m_cases.length ());
1586 :
1587 6062 : basic_block case_bb = gsi_bb (gsi);
1588 6062 : make_edge (case_bb, default_bb, 0);
1589 74084 : for (unsigned i = 0; i < m_cases.length (); i++)
1590 : {
1591 68022 : tree lab = unshare_expr (m_cases[i]->m_case_label_expr);
1592 68022 : if (bitint)
1593 : {
1594 13 : CASE_LOW (lab)
1595 13 : = fold_convert (TREE_TYPE (index_expr),
1596 : const_binop (MINUS_EXPR,
1597 : TREE_TYPE (CASE_LOW (lab)),
1598 : CASE_LOW (lab), low));
1599 13 : if (CASE_HIGH (lab))
1600 0 : CASE_HIGH (lab)
1601 0 : = fold_convert (TREE_TYPE (index_expr),
1602 : const_binop (MINUS_EXPR,
1603 : TREE_TYPE (CASE_HIGH (lab)),
1604 : CASE_HIGH (lab), low));
1605 : }
1606 68022 : labels.quick_push (lab);
1607 68022 : make_edge (case_bb, m_cases[i]->m_case_bb, 0);
1608 : }
1609 :
1610 6062 : gswitch *s = gimple_build_switch (index_expr,
1611 : unshare_expr (default_label_expr), labels);
1612 6062 : gimple_set_location (s, loc);
1613 6062 : gsi_insert_after (&gsi, s, GSI_NEW_STMT);
1614 :
1615 : /* Set up even probabilities for all cases. */
1616 74084 : for (unsigned i = 0; i < m_cases.length (); i++)
1617 : {
1618 68022 : simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
1619 68022 : edge case_edge = find_edge (case_bb, sc->m_case_bb);
1620 68022 : unsigned HOST_WIDE_INT case_range
1621 68022 : = sc->get_range (sc->get_low (), sc->get_high ());
1622 68022 : nondefault_range += case_range;
1623 :
1624 : /* case_edge->aux is number of values in a jump-table that are covered
1625 : by the case_edge. */
1626 68022 : case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + case_range);
1627 : }
1628 :
1629 6062 : edge default_edge = gimple_switch_default_edge (cfun, s);
1630 6062 : default_edge->probability = profile_probability::never ();
1631 :
1632 74084 : for (unsigned i = 0; i < m_cases.length (); i++)
1633 : {
1634 68022 : simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
1635 68022 : edge case_edge = find_edge (case_bb, sc->m_case_bb);
1636 68022 : case_edge->probability
1637 68022 : = profile_probability::always ().apply_scale ((intptr_t)case_edge->aux,
1638 : range);
1639 : }
1640 :
1641 : /* Number of non-default values is probability of default edge. */
1642 6062 : default_edge->probability
1643 6062 : += profile_probability::always ().apply_scale (nondefault_range,
1644 6062 : range).invert ();
1645 :
1646 6062 : switch_decision_tree::reset_out_edges_aux (s);
1647 6062 : }
1648 :
1649 : /* Find jump tables of given CLUSTERS, where all members of the vector
1650 : are of type simple_cluster. New clusters are returned. */
1651 :
1652 : vec<cluster *>
1653 69202 : jump_table_cluster::find_jump_tables (vec<cluster *> &clusters)
1654 : {
1655 69202 : if (!is_enabled ())
1656 15537 : return clusters.copy ();
1657 :
1658 53665 : unsigned l = clusters.length ();
1659 :
1660 53665 : auto_vec<min_cluster_item> min;
1661 53665 : min.reserve (l + 1);
1662 :
1663 53665 : min.quick_push (min_cluster_item (0, 0, 0));
1664 :
1665 53665 : unsigned HOST_WIDE_INT max_ratio
1666 53665 : = (optimize_insn_for_size_p ()
1667 53665 : ? param_jump_table_max_growth_ratio_for_size
1668 53665 : : param_jump_table_max_growth_ratio_for_speed);
1669 :
1670 242303 : for (unsigned i = 1; i <= l; i++)
1671 : {
1672 : /* Set minimal # of clusters with i-th item to infinite. */
1673 188638 : min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
1674 :
1675 : /* Pre-calculate number of comparisons for the clusters. */
1676 188638 : HOST_WIDE_INT comparison_count = 0;
1677 6843776 : for (unsigned k = 0; k <= i - 1; k++)
1678 : {
1679 6655138 : simple_cluster *sc = static_cast<simple_cluster *> (clusters[k]);
1680 13146386 : comparison_count += sc->get_comparison_count ();
1681 : }
1682 :
1683 6843776 : for (unsigned j = 0; j < i; j++)
1684 : {
1685 6655138 : unsigned HOST_WIDE_INT s = min[j].m_non_jt_cases;
1686 13309912 : if (i - j < case_values_threshold ())
1687 469154 : s += i - j;
1688 :
1689 : /* Prefer clusters with smaller number of numbers covered. */
1690 6655138 : if ((min[j].m_count + 1 < min[i].m_count
1691 1733997 : || (min[j].m_count + 1 == min[i].m_count
1692 976 : && s < min[i].m_non_jt_cases))
1693 6655175 : && can_be_handled (clusters, j, i - 1, max_ratio,
1694 : comparison_count))
1695 188664 : min[i] = min_cluster_item (min[j].m_count + 1, j, s);
1696 :
1697 6655138 : simple_cluster *sc = static_cast<simple_cluster *> (clusters[j]);
1698 13146386 : comparison_count -= sc->get_comparison_count ();
1699 : }
1700 :
1701 188638 : gcc_checking_assert (comparison_count == 0);
1702 188638 : gcc_checking_assert (min[i].m_count != INT_MAX);
1703 : }
1704 :
1705 : /* No result. */
1706 53665 : if (min[l].m_count == l)
1707 7475 : return clusters.copy ();
1708 :
1709 46190 : vec<cluster *> output;
1710 46190 : output.create (4);
1711 :
1712 : /* Find and build the clusters. */
1713 46190 : for (unsigned int end = l;;)
1714 : {
1715 51252 : int start = min[end].m_start;
1716 :
1717 : /* Do not allow clusters with small number of cases. */
1718 51252 : if (is_beneficial (clusters, start, end - 1))
1719 6718 : output.safe_push (new jump_table_cluster (clusters, start, end - 1));
1720 : else
1721 141193 : for (int i = end - 1; i >= start; i--)
1722 96659 : output.safe_push (clusters[i]);
1723 :
1724 51252 : end = start;
1725 :
1726 51252 : if (start <= 0)
1727 : break;
1728 : }
1729 :
1730 46190 : output.reverse ();
1731 46190 : return output;
1732 53665 : }
1733 :
1734 : /* Return true when cluster starting at START and ending at END (inclusive)
1735 : can build a jump-table. */
1736 :
1737 : bool
1738 4921178 : jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
1739 : unsigned start, unsigned end,
1740 : unsigned HOST_WIDE_INT max_ratio,
1741 : unsigned HOST_WIDE_INT comparison_count)
1742 : {
1743 : /* If the switch is relatively small such that the cost of one
1744 : indirect jump on the target are higher than the cost of a
1745 : decision tree, go with the decision tree.
1746 :
1747 : If range of values is much bigger than number of values,
1748 : or if it is too large to represent in a HOST_WIDE_INT,
1749 : make a sequence of conditional branches instead of a dispatch.
1750 :
1751 : The definition of "much bigger" depends on whether we are
1752 : optimizing for size or for speed.
1753 :
1754 : For algorithm correctness, jump table for a single case must return
1755 : true. We bail out in is_beneficial if it's called just for
1756 : a single case. */
1757 4921178 : if (start == end)
1758 : return true;
1759 :
1760 9700528 : unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
1761 4850264 : clusters[end]->get_high ());
1762 : /* Check overflow. */
1763 4850264 : if (range == 0)
1764 : return false;
1765 :
1766 4847032 : if (range > HOST_WIDE_INT_M1U / 100)
1767 : return false;
1768 :
1769 636823 : unsigned HOST_WIDE_INT lhs = 100 * range;
1770 636823 : if (lhs < range)
1771 : return false;
1772 :
1773 636823 : return lhs <= max_ratio * comparison_count;
1774 : }
1775 :
1776 : /* Return true if cluster starting at START and ending at END (inclusive)
1777 : is profitable transformation. */
1778 :
1779 : bool
1780 51252 : jump_table_cluster::is_beneficial (const vec<cluster *> &,
1781 : unsigned start, unsigned end)
1782 : {
1783 : /* Single case bail out. */
1784 51252 : if (start == end)
1785 : return false;
1786 :
1787 93718 : return end - start + 1 >= case_values_threshold ();
1788 : }
1789 :
1790 : /* Find bit tests of given CLUSTERS, where all members of the vector
1791 : are of type simple_cluster. MAX_C is the approx max number of cases per
1792 : label. New clusters are returned. */
1793 :
1794 : vec<cluster *>
1795 70679 : bit_test_cluster::find_bit_tests (vec<cluster *> &clusters, int max_c)
1796 : {
1797 70679 : if (!is_enabled () || max_c == 1)
1798 36201 : return clusters.copy ();
1799 :
1800 : /* Dynamic programming algorithm.
1801 :
1802 : In: List of simple clusters
1803 : Out: List of simple clusters and bit test clusters such that each bit test
1804 : cluster can_be_handled() and is_beneficial()
1805 :
1806 : Tries to merge consecutive clusters into bigger (bit test) ones. Tries to
1807 : end up with as few clusters as possible. */
1808 :
1809 34478 : unsigned l = clusters.length ();
1810 :
1811 34478 : if (l == 0)
1812 0 : return clusters.copy ();
1813 34478 : gcc_checking_assert (l <= INT_MAX);
1814 :
1815 34478 : auto_vec<min_cluster_item> min;
1816 34478 : min.reserve (l + 1);
1817 :
1818 34478 : int bits_in_word = GET_MODE_BITSIZE (word_mode);
1819 :
1820 : /* First phase: Compute the minimum number of clusters for each prefix of the
1821 : input list incrementally
1822 :
1823 : min[i] = (count, j, _) means that the prefix ending with the (i-1)-th
1824 : element can be made to contain as few as count clusters and that in such
1825 : clustering the last cluster is made up of input clusters [j, i-1]
1826 : (inclusive). */
1827 34478 : min.quick_push (min_cluster_item (0, 0, INT_MAX));
1828 34478 : min.quick_push (min_cluster_item (1, 0, INT_MAX));
1829 109683 : for (int i = 2; i <= (int) l; i++)
1830 : {
1831 75205 : auto_vec<unsigned, m_max_case_bit_tests> unique_labels;
1832 :
1833 : /* Since each cluster contains at least one case number and one bit test
1834 : cluster can cover at most bits_in_word case numbers, we don't need to
1835 : look farther than bits_in_word clusters back. */
1836 308979 : for (int j = i - 1; j >= 0 && j >= i - bits_in_word; j--)
1837 : {
1838 : /* Consider creating a bit test cluster from input clusters [j, i-1]
1839 : (inclusive) */
1840 :
1841 256059 : simple_cluster *sc = static_cast<simple_cluster *> (clusters[j]);
1842 256059 : unsigned label = sc->m_case_bb->index;
1843 256059 : if (!unique_labels.contains (label))
1844 : {
1845 185800 : if (unique_labels.length () >= m_max_case_bit_tests)
1846 : /* is_beneficial() will be false for this and the following
1847 : iterations. */
1848 : break;
1849 163515 : unique_labels.quick_push (label);
1850 : }
1851 :
1852 233774 : unsigned new_count = min[j].m_count + 1;
1853 :
1854 233774 : if (j == i - 1)
1855 : {
1856 75205 : min.quick_push (min_cluster_item (new_count, j, INT_MAX));
1857 75205 : continue;
1858 : }
1859 :
1860 158569 : unsigned HOST_WIDE_INT range
1861 158569 : = get_range (clusters[j]->get_low (), clusters[i-1]->get_high ());
1862 158569 : if (new_count < min[i].m_count
1863 139161 : && can_be_handled (range, unique_labels.length ())
1864 267580 : && is_beneficial (i - j, unique_labels.length ()))
1865 8159 : min[i] = min_cluster_item (new_count, j, INT_MAX);
1866 : }
1867 75205 : }
1868 :
1869 34478 : if (min[l].m_count == l)
1870 : /* No bit test clustering opportunities. */
1871 30281 : return clusters.copy ();
1872 :
1873 4197 : vec<cluster *> output;
1874 4197 : output.create (4);
1875 :
1876 : /* Second phase: Find and build the bit test clusters by traversing min
1877 : array backwards. */
1878 4197 : for (unsigned end = l;;)
1879 : {
1880 8499 : unsigned start = min[end].m_start;
1881 8499 : gcc_checking_assert (start < end);
1882 :
1883 : /* This cluster will be made out of input clusters [start, end - 1]. */
1884 :
1885 8499 : if (start == end - 1)
1886 : /* Let the cluster be a simple cluster. */
1887 3883 : output.safe_push (clusters[start]);
1888 : else
1889 : {
1890 4616 : bool entire = start == 0 && end == l;
1891 4616 : output.safe_push (new bit_test_cluster (clusters, start, end - 1,
1892 4616 : entire));
1893 : }
1894 :
1895 8499 : end = start;
1896 :
1897 8499 : if (start <= 0)
1898 : break;
1899 : }
1900 :
1901 4197 : output.reverse ();
1902 4197 : return output;
1903 34478 : }
1904 :
1905 : /* Return true when RANGE of case values with UNIQ labels
1906 : can build a bit test. */
1907 :
1908 : bool
1909 166110 : bit_test_cluster::can_be_handled (unsigned HOST_WIDE_INT range,
1910 : unsigned int uniq)
1911 : {
1912 : /* Check overflow. */
1913 166110 : if (range == 0)
1914 : return false;
1915 :
1916 328342 : if (range > GET_MODE_BITSIZE (word_mode))
1917 : return false;
1918 :
1919 133130 : return uniq <= m_max_case_bit_tests;
1920 : }
1921 :
1922 : /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test
1923 : transformation. */
1924 :
1925 : bool
1926 123790 : bit_test_cluster::is_beneficial (unsigned count, unsigned uniq)
1927 : {
1928 : /* NOTE: When modifying this, keep in mind the value of
1929 : m_max_case_bit_tests. */
1930 123790 : return (((uniq == 1 && count >= 3)
1931 115738 : || (uniq == 2 && count >= 5)
1932 238249 : || (uniq == 3 && count >= 6)));
1933 : }
1934 :
1935 : /* Comparison function for qsort to order bit tests by decreasing
1936 : probability of execution. */
1937 :
1938 : int
1939 7065 : case_bit_test::cmp (const void *p1, const void *p2)
1940 : {
1941 7065 : const case_bit_test *const d1 = (const case_bit_test *) p1;
1942 7065 : const case_bit_test *const d2 = (const case_bit_test *) p2;
1943 :
1944 7065 : if (d2->bits != d1->bits)
1945 5966 : return d2->bits - d1->bits;
1946 :
1947 : /* Stabilize the sort. */
1948 1099 : return (d2->target_bb->index
1949 1099 : - d1->target_bb->index);
1950 : }
1951 :
1952 : /* Expand a switch statement by a short sequence of bit-wise
1953 : comparisons. "switch(x)" is effectively converted into
1954 : "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
1955 : integer constants.
1956 :
1957 : INDEX_EXPR is the value being switched on.
1958 :
1959 : MINVAL is the lowest case value of in the case nodes,
1960 : and RANGE is highest value minus MINVAL. MINVAL and RANGE
1961 : are not guaranteed to be of the same type as INDEX_EXPR
1962 : (the gimplifier doesn't change the type of case label values,
1963 : and MINVAL and RANGE are derived from those values).
1964 : MAXVAL is MINVAL + RANGE.
1965 :
1966 : There *MUST* be max_case_bit_tests or less unique case
1967 : node targets. */
1968 :
1969 : void
1970 3801 : bit_test_cluster::emit (tree index_expr, tree index_type,
1971 : tree, basic_block default_bb, location_t loc)
1972 : {
1973 22806 : case_bit_test test[m_max_case_bit_tests] = { {} };
1974 3801 : unsigned int i, j, k;
1975 3801 : unsigned int count;
1976 :
1977 3801 : tree unsigned_index_type = range_check_type (index_type);
1978 :
1979 3801 : gimple_stmt_iterator gsi;
1980 3801 : gassign *shift_stmt;
1981 :
1982 3801 : tree idx, tmp, csui;
1983 3801 : tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
1984 3801 : tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
1985 3801 : tree word_mode_one = fold_convert (word_type_node, integer_one_node);
1986 3801 : int prec = TYPE_PRECISION (word_type_node);
1987 3801 : wide_int wone = wi::one (prec);
1988 :
1989 3801 : tree minval = get_low ();
1990 3801 : tree maxval = get_high ();
1991 :
1992 : /* Go through all case labels, and collect the case labels, profile
1993 : counts, and other information we need to build the branch tests. */
1994 3801 : count = 0;
1995 19842 : for (i = 0; i < m_cases.length (); i++)
1996 : {
1997 16041 : unsigned int lo, hi;
1998 16041 : simple_cluster *n = static_cast<simple_cluster *> (m_cases[i]);
1999 19857 : for (k = 0; k < count; k++)
2000 14670 : if (n->m_case_bb == test[k].target_bb)
2001 : break;
2002 :
2003 16041 : if (k == count)
2004 : {
2005 5187 : gcc_checking_assert (count < m_max_case_bit_tests);
2006 5187 : test[k].mask = wi::zero (prec);
2007 5187 : test[k].target_bb = n->m_case_bb;
2008 5187 : test[k].bits = 0;
2009 5187 : test[k].prob = profile_probability::never ();
2010 5187 : count++;
2011 : }
2012 :
2013 16041 : test[k].bits += n->get_range (n->get_low (), n->get_high ());
2014 16041 : test[k].prob += n->m_prob;
2015 :
2016 16041 : lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval));
2017 16041 : if (n->get_high () == NULL_TREE)
2018 : hi = lo;
2019 : else
2020 16041 : hi = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_high (),
2021 : minval));
2022 :
2023 38528 : for (j = lo; j <= hi; j++)
2024 22487 : test[k].mask |= wi::lshift (wone, j);
2025 : }
2026 :
2027 3801 : qsort (test, count, sizeof (*test), case_bit_test::cmp);
2028 :
2029 : /* If every possible relative value of the index expression is a valid shift
2030 : amount, then we can merge the entry test in the bit test. */
2031 3801 : bool entry_test_needed;
2032 3801 : int_range_max r;
2033 7602 : if (TREE_CODE (index_expr) == SSA_NAME
2034 7602 : && get_range_query (cfun)->range_of_expr (r, index_expr)
2035 3801 : && !r.undefined_p ()
2036 3800 : && !r.varying_p ()
2037 8898 : && wi::leu_p (r.upper_bound () - r.lower_bound (), prec - 1))
2038 : {
2039 62 : wide_int min = r.lower_bound ();
2040 62 : wide_int max = r.upper_bound ();
2041 62 : tree index_type = TREE_TYPE (index_expr);
2042 62 : minval = fold_convert (index_type, minval);
2043 62 : wide_int iminval = wi::to_wide (minval);
2044 62 : if (wi::lt_p (min, iminval, TYPE_SIGN (index_type)))
2045 : {
2046 57 : minval = wide_int_to_tree (index_type, min);
2047 181 : for (i = 0; i < count; i++)
2048 124 : test[i].mask = wi::lshift (test[i].mask, iminval - min);
2049 : }
2050 5 : else if (wi::gt_p (min, iminval, TYPE_SIGN (index_type)))
2051 : {
2052 0 : minval = wide_int_to_tree (index_type, min);
2053 0 : for (i = 0; i < count; i++)
2054 0 : test[i].mask = wi::lrshift (test[i].mask, min - iminval);
2055 : }
2056 62 : maxval = wide_int_to_tree (index_type, max);
2057 62 : entry_test_needed = false;
2058 62 : }
2059 : else
2060 : entry_test_needed = true;
2061 :
2062 : /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
2063 : the minval subtractions, but it might make the mask constants more
2064 : expensive. So, compare the costs. */
2065 3801 : if (compare_tree_int (minval, 0) > 0 && compare_tree_int (maxval, prec) < 0)
2066 : {
2067 2077 : int cost_diff;
2068 2077 : HOST_WIDE_INT m = tree_to_uhwi (minval);
2069 2077 : rtx reg = gen_raw_REG (word_mode, 10000);
2070 2077 : bool speed_p = optimize_insn_for_speed_p ();
2071 2077 : cost_diff = set_src_cost (gen_rtx_PLUS (word_mode, reg,
2072 : GEN_INT (-m)),
2073 : word_mode, speed_p);
2074 4512 : for (i = 0; i < count; i++)
2075 : {
2076 2435 : rtx r = immed_wide_int_const (test[i].mask, word_mode);
2077 2435 : cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r),
2078 : word_mode, speed_p);
2079 2435 : r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode);
2080 2435 : cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r),
2081 : word_mode, speed_p);
2082 : }
2083 2077 : if (cost_diff > 0)
2084 : {
2085 4156 : for (i = 0; i < count; i++)
2086 2223 : test[i].mask = wi::lshift (test[i].mask, m);
2087 1933 : minval = build_zero_cst (TREE_TYPE (minval));
2088 : }
2089 : }
2090 :
2091 : /* Now build the test-and-branch code. */
2092 :
2093 3801 : gsi = gsi_last_bb (m_case_bb);
2094 :
2095 : /* idx = (unsigned)x - minval. */
2096 3801 : idx = fold_convert_loc (loc, unsigned_index_type, index_expr);
2097 3801 : idx = fold_build2_loc (loc, MINUS_EXPR, unsigned_index_type, idx,
2098 : fold_convert_loc (loc, unsigned_index_type, minval));
2099 3801 : idx = force_gimple_operand_gsi (&gsi, idx,
2100 : /*simple=*/true, NULL_TREE,
2101 : /*before=*/true, GSI_SAME_STMT);
2102 :
2103 3801 : profile_probability subtree_prob = m_subtree_prob;
2104 3801 : profile_probability default_prob = m_default_prob;
2105 3801 : if (!default_prob.initialized_p ())
2106 2486 : default_prob = m_subtree_prob.invert ();
2107 :
2108 3801 : if (m_handles_entire_switch && entry_test_needed)
2109 : {
2110 2444 : tree range = int_const_binop (MINUS_EXPR, maxval, minval);
2111 : /* if (idx > range) goto default */
2112 2444 : range
2113 2444 : = force_gimple_operand_gsi (&gsi,
2114 : fold_convert (unsigned_index_type, range),
2115 : /*simple=*/true, NULL_TREE,
2116 : /*before=*/true, GSI_SAME_STMT);
2117 2444 : tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
2118 2444 : default_prob = default_prob / 2;
2119 2444 : basic_block new_bb
2120 2444 : = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb,
2121 : default_prob, loc);
2122 4888 : gsi = gsi_last_bb (new_bb);
2123 : }
2124 :
2125 3801 : tmp = fold_build2_loc (loc, LSHIFT_EXPR, word_type_node, word_mode_one,
2126 : fold_convert_loc (loc, word_type_node, idx));
2127 :
2128 : /* csui = (1 << (word_mode) idx) */
2129 3801 : if (count > 1)
2130 : {
2131 879 : csui = make_ssa_name (word_type_node);
2132 879 : tmp = force_gimple_operand_gsi (&gsi, tmp,
2133 : /*simple=*/false, NULL_TREE,
2134 : /*before=*/true, GSI_SAME_STMT);
2135 879 : shift_stmt = gimple_build_assign (csui, tmp);
2136 879 : gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
2137 879 : update_stmt (shift_stmt);
2138 : }
2139 : else
2140 : csui = tmp;
2141 :
2142 : /* for each unique set of cases:
2143 : if (const & csui) goto target */
2144 8988 : for (k = 0; k < count; k++)
2145 : {
2146 5187 : profile_probability prob = test[k].prob / (subtree_prob + default_prob);
2147 5187 : subtree_prob -= test[k].prob;
2148 5187 : tmp = wide_int_to_tree (word_type_node, test[k].mask);
2149 5187 : tmp = fold_build2_loc (loc, BIT_AND_EXPR, word_type_node, csui, tmp);
2150 5187 : tmp = fold_build2_loc (loc, NE_EXPR, boolean_type_node,
2151 : tmp, word_mode_zero);
2152 5187 : tmp = force_gimple_operand_gsi (&gsi, tmp,
2153 : /*simple=*/true, NULL_TREE,
2154 : /*before=*/true, GSI_SAME_STMT);
2155 5187 : basic_block new_bb
2156 5187 : = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_bb,
2157 : prob, loc);
2158 10374 : gsi = gsi_last_bb (new_bb);
2159 : }
2160 :
2161 : /* We should have removed all edges now. */
2162 3801 : gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
2163 :
2164 : /* If nothing matched, go to the default label. */
2165 3801 : edge e = make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU);
2166 3801 : e->probability = profile_probability::always ();
2167 15204 : }
2168 :
2169 : /* Split the basic block at the statement pointed to by GSIP, and insert
2170 : a branch to the target basic block of E_TRUE conditional on tree
2171 : expression COND.
2172 :
2173 : It is assumed that there is already an edge from the to-be-split
2174 : basic block to E_TRUE->dest block. This edge is removed, and the
2175 : profile information on the edge is re-used for the new conditional
2176 : jump.
2177 :
2178 : The CFG is updated. The dominator tree will not be valid after
2179 : this transformation, but the immediate dominators are updated if
2180 : UPDATE_DOMINATORS is true.
2181 :
2182 : Returns the newly created basic block. */
2183 :
2184 : basic_block
2185 7631 : bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
2186 : tree cond, basic_block case_bb,
2187 : profile_probability prob,
2188 : location_t loc)
2189 : {
2190 7631 : tree tmp;
2191 7631 : gcond *cond_stmt;
2192 7631 : edge e_false;
2193 7631 : basic_block new_bb, split_bb = gsi_bb (*gsip);
2194 :
2195 7631 : edge e_true = make_edge (split_bb, case_bb, EDGE_TRUE_VALUE);
2196 7631 : e_true->probability = prob;
2197 7631 : gcc_assert (e_true->src == split_bb);
2198 :
2199 7631 : tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
2200 : /*before=*/true, GSI_SAME_STMT);
2201 7631 : cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
2202 7631 : gimple_set_location (cond_stmt, loc);
2203 7631 : gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
2204 :
2205 7631 : e_false = split_block (split_bb, cond_stmt);
2206 7631 : new_bb = e_false->dest;
2207 7631 : redirect_edge_pred (e_true, split_bb);
2208 :
2209 7631 : e_false->flags &= ~EDGE_FALLTHRU;
2210 7631 : e_false->flags |= EDGE_FALSE_VALUE;
2211 7631 : e_false->probability = e_true->probability.invert ();
2212 7631 : new_bb->count = e_false->count ();
2213 :
2214 7631 : return new_bb;
2215 : }
2216 :
2217 : /* Compute the number of case labels that correspond to each outgoing edge of
2218 : switch statement. Record this information in the aux field of the edge.
2219 : Return the approx max number of cases per edge. */
2220 :
2221 : int
2222 44474 : switch_decision_tree::compute_cases_per_edge ()
2223 : {
2224 44474 : int max_c = 0;
2225 44474 : reset_out_edges_aux (m_switch);
2226 44474 : int ncases = gimple_switch_num_labels (m_switch);
2227 287083 : for (int i = ncases - 1; i >= 1; --i)
2228 : {
2229 242609 : edge case_edge = gimple_switch_edge (cfun, m_switch, i);
2230 242609 : case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1);
2231 : /* For a range case add one extra. That's enough for the bit
2232 : cluster heuristic. */
2233 242609 : if ((intptr_t)case_edge->aux > max_c)
2234 137252 : max_c = (intptr_t)case_edge->aux +
2235 68626 : !!CASE_HIGH (gimple_switch_label (m_switch, i));
2236 : }
2237 44474 : return max_c;
2238 : }
2239 :
2240 : /* Analyze switch statement and return true when the statement is expanded
2241 : as decision tree. */
2242 :
2243 : bool
2244 44474 : switch_decision_tree::analyze_switch_statement ()
2245 : {
2246 44474 : unsigned l = gimple_switch_num_labels (m_switch);
2247 44474 : basic_block bb = gimple_bb (m_switch);
2248 44474 : auto_vec<cluster *> clusters;
2249 44474 : clusters.create (l - 1);
2250 :
2251 44474 : basic_block default_bb = gimple_switch_default_bb (cfun, m_switch);
2252 44474 : m_case_bbs.reserve (l);
2253 44474 : m_case_bbs.quick_push (default_bb);
2254 :
2255 44474 : int max_c = compute_cases_per_edge ();
2256 :
2257 287083 : for (unsigned i = 1; i < l; i++)
2258 : {
2259 242609 : tree elt = gimple_switch_label (m_switch, i);
2260 242609 : tree lab = CASE_LABEL (elt);
2261 242609 : basic_block case_bb = label_to_block (cfun, lab);
2262 242609 : edge case_edge = find_edge (bb, case_bb);
2263 242609 : tree low = CASE_LOW (elt);
2264 242609 : tree high = CASE_HIGH (elt);
2265 :
2266 242609 : profile_probability p
2267 242609 : = case_edge->probability / ((intptr_t) (case_edge->aux));
2268 242609 : clusters.quick_push (new simple_cluster (low, high, elt, case_edge->dest,
2269 242609 : p));
2270 242609 : m_case_bbs.quick_push (case_edge->dest);
2271 : }
2272 :
2273 44474 : reset_out_edges_aux (m_switch);
2274 :
2275 : /* Find bit-test clusters. */
2276 44474 : vec<cluster *> output = bit_test_cluster::find_bit_tests (clusters, max_c);
2277 :
2278 : /* Find jump table clusters. We are looking for these in the sequences of
2279 : simple clusters which we didn't manage to convert into bit-test
2280 : clusters. */
2281 44474 : vec<cluster *> output2;
2282 44474 : auto_vec<cluster *> tmp;
2283 44474 : output2.create (1);
2284 44474 : tmp.create (1);
2285 :
2286 274843 : for (unsigned i = 0; i < output.length (); i++)
2287 : {
2288 230369 : cluster *c = output[i];
2289 230369 : if (c->get_type () != SIMPLE_CASE)
2290 : {
2291 3801 : if (!tmp.is_empty ())
2292 : {
2293 744 : vec<cluster *> n = jump_table_cluster::find_jump_tables (tmp);
2294 744 : output2.safe_splice (n);
2295 744 : n.release ();
2296 744 : tmp.truncate (0);
2297 : }
2298 3801 : output2.safe_push (c);
2299 : }
2300 : else
2301 226568 : tmp.safe_push (c);
2302 : }
2303 :
2304 : /* We still can have a temporary vector to test. */
2305 44474 : if (!tmp.is_empty ())
2306 : {
2307 41603 : vec<cluster *> n = jump_table_cluster::find_jump_tables (tmp);
2308 41603 : output2.safe_splice (n);
2309 41603 : n.release ();
2310 : }
2311 :
2312 44474 : if (dump_file)
2313 : {
2314 24 : fprintf (dump_file, ";; GIMPLE switch case clusters: ");
2315 103 : for (unsigned i = 0; i < output2.length (); i++)
2316 79 : output2[i]->dump (dump_file, dump_flags & TDF_DETAILS);
2317 24 : fprintf (dump_file, "\n");
2318 : }
2319 :
2320 44474 : output.release ();
2321 :
2322 44474 : bool expanded = try_switch_expansion (output2);
2323 44474 : release_clusters (output2);
2324 44474 : return expanded;
2325 44474 : }
2326 :
2327 : /* Attempt to expand CLUSTERS as a decision tree. Return true when
2328 : expanded. */
2329 :
2330 : bool
2331 44474 : switch_decision_tree::try_switch_expansion (vec<cluster *> &clusters)
2332 : {
2333 44474 : tree index_expr = gimple_switch_index (m_switch);
2334 44474 : tree index_type = TREE_TYPE (index_expr);
2335 44474 : basic_block bb = gimple_bb (m_switch);
2336 :
2337 44474 : if (gimple_switch_num_labels (m_switch) == 1
2338 44474 : || range_check_type (index_type) == NULL_TREE)
2339 72 : return false;
2340 :
2341 : /* Find the default case target label. */
2342 44402 : edge default_edge = gimple_switch_default_edge (cfun, m_switch);
2343 44402 : m_default_bb = default_edge->dest;
2344 :
2345 : /* Do the insertion of a case label into m_case_list. The labels are
2346 : fed to us in descending order from the sorted vector of case labels used
2347 : in the tree part of the middle end. So the list we construct is
2348 : sorted in ascending order. */
2349 :
2350 257049 : for (int i = clusters.length () - 1; i >= 0; i--)
2351 : {
2352 168245 : case_tree_node *r = m_case_list;
2353 168245 : m_case_list = m_case_node_pool.allocate ();
2354 168245 : m_case_list->m_right = r;
2355 168245 : m_case_list->m_c = clusters[i];
2356 : }
2357 :
2358 44402 : record_phi_operand_mapping ();
2359 :
2360 : /* Split basic block that contains the gswitch statement. */
2361 44402 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
2362 44402 : edge e;
2363 44402 : if (gsi_end_p (gsi))
2364 0 : e = split_block_after_labels (bb);
2365 : else
2366 : {
2367 44402 : gsi_prev (&gsi);
2368 44402 : e = split_block (bb, gsi_stmt (gsi));
2369 : }
2370 44402 : bb = split_edge (e);
2371 :
2372 : /* Create new basic blocks for non-case clusters where specific expansion
2373 : needs to happen. */
2374 212647 : for (unsigned i = 0; i < clusters.length (); i++)
2375 168245 : if (clusters[i]->get_type () != SIMPLE_CASE)
2376 : {
2377 9863 : clusters[i]->m_case_bb = create_empty_bb (bb);
2378 9863 : clusters[i]->m_case_bb->count = bb->count;
2379 9863 : clusters[i]->m_case_bb->loop_father = bb->loop_father;
2380 : }
2381 :
2382 : /* Do not do an extra work for a single cluster. */
2383 44402 : if (clusters.length () == 1
2384 53531 : && clusters[0]->get_type () != SIMPLE_CASE)
2385 : {
2386 8004 : cluster *c = clusters[0];
2387 8004 : c->emit (index_expr, index_type,
2388 : gimple_switch_default_label (m_switch), m_default_bb,
2389 8004 : gimple_location (m_switch));
2390 8004 : redirect_edge_succ (single_succ_edge (bb), c->m_case_bb);
2391 : }
2392 : else
2393 : {
2394 36398 : emit (bb, index_expr, default_edge->probability, index_type);
2395 :
2396 : /* Emit cluster-specific switch handling. */
2397 196639 : for (unsigned i = 0; i < clusters.length (); i++)
2398 160241 : if (clusters[i]->get_type () != SIMPLE_CASE)
2399 : {
2400 1859 : edge e = single_pred_edge (clusters[i]->m_case_bb);
2401 1859 : e->dest->count = e->src->count.apply_probability (e->probability);
2402 3718 : clusters[i]->emit (index_expr, index_type,
2403 : gimple_switch_default_label (m_switch),
2404 1859 : m_default_bb, gimple_location (m_switch));
2405 : }
2406 : }
2407 :
2408 44402 : fix_phi_operands_for_edges ();
2409 :
2410 44402 : return true;
2411 : }
2412 :
2413 : /* Before switch transformation, record all SSA_NAMEs defined in switch BB
2414 : and used in a label basic block. */
2415 :
2416 : void
2417 44402 : switch_decision_tree::record_phi_operand_mapping ()
2418 : {
2419 44402 : basic_block switch_bb = gimple_bb (m_switch);
2420 : /* Record all PHI nodes that have to be fixed after conversion. */
2421 331249 : for (unsigned i = 0; i < m_case_bbs.length (); i++)
2422 : {
2423 286847 : gphi_iterator gsi;
2424 286847 : basic_block bb = m_case_bbs[i];
2425 349821 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2426 : {
2427 62974 : gphi *phi = gsi.phi ();
2428 :
2429 206284 : for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
2430 : {
2431 206284 : basic_block phi_src_bb = gimple_phi_arg_edge (phi, i)->src;
2432 206284 : if (phi_src_bb == switch_bb)
2433 : {
2434 62974 : tree def = gimple_phi_arg_def (phi, i);
2435 62974 : tree result = gimple_phi_result (phi);
2436 62974 : m_phi_mapping.put (result, def);
2437 62974 : break;
2438 : }
2439 : }
2440 : }
2441 : }
2442 44402 : }
2443 :
2444 : /* Append new operands to PHI statements that were introduced due to
2445 : addition of new edges to case labels. */
2446 :
2447 : void
2448 44402 : switch_decision_tree::fix_phi_operands_for_edges ()
2449 : {
2450 44402 : gphi_iterator gsi;
2451 :
2452 331249 : for (unsigned i = 0; i < m_case_bbs.length (); i++)
2453 : {
2454 286847 : basic_block bb = m_case_bbs[i];
2455 349821 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2456 : {
2457 62974 : gphi *phi = gsi.phi ();
2458 529320 : for (unsigned j = 0; j < gimple_phi_num_args (phi); j++)
2459 : {
2460 466346 : tree def = gimple_phi_arg_def (phi, j);
2461 466346 : if (def == NULL_TREE)
2462 : {
2463 67577 : edge e = gimple_phi_arg_edge (phi, j);
2464 67577 : tree *definition
2465 67577 : = m_phi_mapping.get (gimple_phi_result (phi));
2466 67577 : gcc_assert (definition);
2467 67577 : add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
2468 : }
2469 : }
2470 : }
2471 : }
2472 44402 : }
2473 :
2474 : /* Generate a decision tree, switching on INDEX_EXPR and jumping to
2475 : one of the labels in CASE_LIST or to the DEFAULT_LABEL.
2476 :
2477 : We generate a binary decision tree to select the appropriate target
2478 : code. */
2479 :
2480 : void
2481 36398 : switch_decision_tree::emit (basic_block bb, tree index_expr,
2482 : profile_probability default_prob, tree index_type)
2483 : {
2484 36398 : balance_case_nodes (&m_case_list, NULL);
2485 :
2486 36398 : if (dump_file)
2487 15 : dump_function_to_file (current_function_decl, dump_file, dump_flags);
2488 36398 : if (dump_file && (dump_flags & TDF_DETAILS))
2489 : {
2490 0 : int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
2491 0 : fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
2492 0 : gcc_assert (m_case_list != NULL);
2493 0 : dump_case_nodes (dump_file, m_case_list, indent_step, 0);
2494 : }
2495 :
2496 72796 : bb = emit_case_nodes (bb, index_expr, m_case_list, default_prob, index_type,
2497 36398 : gimple_location (m_switch));
2498 :
2499 36398 : if (bb)
2500 34617 : emit_jump (bb, m_default_bb);
2501 :
2502 : /* Remove all edges and do just an edge that will reach default_bb. */
2503 36398 : bb = gimple_bb (m_switch);
2504 36398 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
2505 36398 : gsi_remove (&gsi, true);
2506 :
2507 36398 : delete_basic_block (bb);
2508 36398 : }
2509 :
2510 : /* Take an ordered list of case nodes
2511 : and transform them into a near optimal binary tree,
2512 : on the assumption that any target code selection value is as
2513 : likely as any other.
2514 :
2515 : The transformation is performed by splitting the ordered
2516 : list into two equal sections plus a pivot. The parts are
2517 : then attached to the pivot as left and right branches. Each
2518 : branch is then transformed recursively. */
2519 :
2520 : void
2521 200268 : switch_decision_tree::balance_case_nodes (case_tree_node **head,
2522 : case_tree_node *parent)
2523 : {
2524 200268 : case_tree_node *np;
2525 :
2526 200268 : np = *head;
2527 200268 : if (np)
2528 : {
2529 129739 : int i = 0;
2530 129739 : case_tree_node **npp;
2531 129739 : case_tree_node *left;
2532 129739 : profile_probability prob = profile_probability::never ();
2533 :
2534 : /* Count the number of entries on branch. */
2535 :
2536 2353790 : while (np)
2537 : {
2538 2224051 : i++;
2539 2224051 : prob += np->m_c->m_prob;
2540 2224051 : np = np->m_right;
2541 : }
2542 :
2543 129739 : if (i > 2)
2544 : {
2545 : /* Split this list if it is long enough for that to help. */
2546 81935 : npp = head;
2547 81935 : left = *npp;
2548 81935 : profile_probability pivot_prob = prob / 2;
2549 :
2550 : /* Find the place in the list that bisects the list's total cost
2551 : by probability. */
2552 4152965 : while (1)
2553 : {
2554 : /* Skip nodes while their probability does not reach
2555 : that amount. */
2556 2117450 : prob -= (*npp)->m_c->m_prob;
2557 2117450 : if ((prob.initialized_p () && prob < pivot_prob)
2558 2148222 : || ! (*npp)->m_right)
2559 : break;
2560 2035515 : npp = &(*npp)->m_right;
2561 : }
2562 :
2563 81935 : np = *npp;
2564 81935 : *npp = 0;
2565 81935 : *head = np;
2566 81935 : np->m_parent = parent;
2567 81935 : np->m_left = left == np ? NULL : left;
2568 :
2569 : /* Optimize each of the two split parts. */
2570 81935 : balance_case_nodes (&np->m_left, np);
2571 81935 : balance_case_nodes (&np->m_right, np);
2572 81935 : np->m_c->m_subtree_prob = np->m_c->m_prob;
2573 81935 : if (np->m_left)
2574 81443 : np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob;
2575 81935 : if (np->m_right)
2576 11898 : np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
2577 : }
2578 : else
2579 : {
2580 : /* Else leave this branch as one level,
2581 : but fill in `parent' fields. */
2582 47804 : np = *head;
2583 47804 : np->m_parent = parent;
2584 47804 : np->m_c->m_subtree_prob = np->m_c->m_prob;
2585 78306 : for (; np->m_right; np = np->m_right)
2586 : {
2587 30502 : np->m_right->m_parent = np;
2588 30502 : (*head)->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
2589 : }
2590 : }
2591 : }
2592 200268 : }
2593 :
2594 : /* Dump ROOT, a list or tree of case nodes, to file. */
2595 :
2596 : void
2597 0 : switch_decision_tree::dump_case_nodes (FILE *f, case_tree_node *root,
2598 : int indent_step, int indent_level)
2599 : {
2600 0 : if (root == 0)
2601 0 : return;
2602 0 : indent_level++;
2603 :
2604 0 : dump_case_nodes (f, root->m_left, indent_step, indent_level);
2605 :
2606 0 : fputs (";; ", f);
2607 0 : fprintf (f, "%*s", indent_step * indent_level, "");
2608 0 : root->m_c->dump (f);
2609 0 : root->m_c->m_prob.dump (f);
2610 0 : fputs (" subtree: ", f);
2611 0 : root->m_c->m_subtree_prob.dump (f);
2612 0 : fputs (")\n", f);
2613 :
2614 0 : dump_case_nodes (f, root->m_right, indent_step, indent_level);
2615 : }
2616 :
2617 :
2618 : /* Add an unconditional jump to CASE_BB that happens in basic block BB. */
2619 :
2620 : void
2621 63885 : switch_decision_tree::emit_jump (basic_block bb, basic_block case_bb)
2622 : {
2623 63885 : edge e = single_succ_edge (bb);
2624 63885 : redirect_edge_succ (e, case_bb);
2625 63885 : }
2626 :
2627 : /* Generate code to compare OP0 with OP1 so that the condition codes are
2628 : set and to jump to LABEL_BB if the condition is true.
2629 : COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
2630 : PROB is the probability of jumping to LABEL_BB. */
2631 :
2632 : basic_block
2633 105439 : switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0,
2634 : tree op1, tree_code comparison,
2635 : basic_block label_bb,
2636 : profile_probability prob,
2637 : location_t loc)
2638 : {
2639 : // TODO: it's once called with lhs != index.
2640 105439 : op1 = fold_convert (TREE_TYPE (op0), op1);
2641 :
2642 105439 : gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE);
2643 105439 : gimple_set_location (cond, loc);
2644 105439 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
2645 105439 : gsi_insert_after (&gsi, cond, GSI_NEW_STMT);
2646 :
2647 105439 : gcc_assert (single_succ_p (bb));
2648 :
2649 : /* Make a new basic block where false branch will take place. */
2650 105439 : edge false_edge = split_block (bb, cond);
2651 105439 : false_edge->flags = EDGE_FALSE_VALUE;
2652 105439 : false_edge->probability = prob.invert ();
2653 105439 : false_edge->dest->count = bb->count.apply_probability (prob.invert ());
2654 :
2655 105439 : edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
2656 105439 : true_edge->probability = prob;
2657 :
2658 105439 : return false_edge->dest;
2659 : }
2660 :
2661 : /* Generate code to jump to LABEL if OP0 and OP1 are equal.
2662 : PROB is the probability of jumping to LABEL_BB.
2663 : BB is a basic block where the new condition will be placed. */
2664 :
2665 : basic_block
2666 135009 : switch_decision_tree::do_jump_if_equal (basic_block bb, tree op0, tree op1,
2667 : basic_block label_bb,
2668 : profile_probability prob,
2669 : location_t loc)
2670 : {
2671 135009 : op1 = fold_convert (TREE_TYPE (op0), op1);
2672 :
2673 135009 : gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE);
2674 135009 : gimple_set_location (cond, loc);
2675 135009 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
2676 135009 : gsi_insert_before (&gsi, cond, GSI_SAME_STMT);
2677 :
2678 135009 : gcc_assert (single_succ_p (bb));
2679 :
2680 : /* Make a new basic block where false branch will take place. */
2681 135009 : edge false_edge = split_block (bb, cond);
2682 135009 : false_edge->flags = EDGE_FALSE_VALUE;
2683 135009 : false_edge->probability = prob.invert ();
2684 135009 : false_edge->dest->count = bb->count.apply_probability (prob.invert ());
2685 :
2686 135009 : edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
2687 135009 : true_edge->probability = prob;
2688 :
2689 135009 : return false_edge->dest;
2690 : }
2691 :
2692 : /* Emit step-by-step code to select a case for the value of INDEX.
2693 : The thus generated decision tree follows the form of the
2694 : case-node binary tree NODE, whose nodes represent test conditions.
2695 : DEFAULT_PROB is probability of cases leading to default BB.
2696 : INDEX_TYPE is the type of the index of the switch. */
2697 :
2698 : basic_block
2699 63885 : switch_decision_tree::emit_case_nodes (basic_block bb, tree index,
2700 : case_tree_node *node,
2701 : profile_probability default_prob,
2702 : tree index_type, location_t loc)
2703 : {
2704 144092 : profile_probability p;
2705 :
2706 : /* If node is null, we are done. */
2707 144092 : if (node == NULL)
2708 : return bb;
2709 :
2710 : /* Single value case. */
2711 122353 : if (node->m_c->is_single_value_p ())
2712 : {
2713 : /* Node is single valued. First see if the index expression matches
2714 : this node and then check our children, if any. */
2715 97121 : p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
2716 97121 : bb = do_jump_if_equal (bb, index, node->m_c->get_low (),
2717 : node->m_c->m_case_bb, p, loc);
2718 : /* Since this case is taken at this point, reduce its weight from
2719 : subtree_weight. */
2720 97121 : node->m_c->m_subtree_prob -= node->m_c->m_prob;
2721 :
2722 97121 : if (node->m_left != NULL && node->m_right != NULL)
2723 : {
2724 : /* 1) the node has both children
2725 :
2726 : If both children are single-valued cases with no
2727 : children, finish up all the work. This way, we can save
2728 : one ordered comparison. */
2729 :
2730 10748 : if (!node->m_left->has_child ()
2731 6680 : && node->m_left->m_c->is_single_value_p ()
2732 5284 : && !node->m_right->has_child ()
2733 5105 : && node->m_right->m_c->is_single_value_p ())
2734 : {
2735 10056 : p = (node->m_right->m_c->m_prob
2736 5028 : / (node->m_c->m_subtree_prob + default_prob));
2737 5028 : bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
2738 : node->m_right->m_c->m_case_bb, p, loc);
2739 5028 : node->m_c->m_subtree_prob -= node->m_right->m_c->m_prob;
2740 :
2741 10056 : p = (node->m_left->m_c->m_prob
2742 5028 : / (node->m_c->m_subtree_prob + default_prob));
2743 5028 : bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
2744 : node->m_left->m_c->m_case_bb, p, loc);
2745 : }
2746 : else
2747 : {
2748 : /* Branch to a label where we will handle it later. */
2749 5720 : basic_block test_bb = split_edge (single_succ_edge (bb));
2750 5720 : redirect_edge_succ (single_pred_edge (test_bb),
2751 5720 : single_succ_edge (bb)->dest);
2752 :
2753 5720 : p = ((node->m_right->m_c->m_subtree_prob + default_prob / 2)
2754 11440 : / (node->m_c->m_subtree_prob + default_prob));
2755 5720 : test_bb->count = bb->count.apply_probability (p);
2756 5720 : bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
2757 : GT_EXPR, test_bb, p, loc);
2758 5720 : default_prob /= 2;
2759 :
2760 : /* Handle the left-hand subtree. */
2761 5720 : bb = emit_case_nodes (bb, index, node->m_left,
2762 : default_prob, index_type, loc);
2763 :
2764 : /* If the left-hand subtree fell through,
2765 : don't let it fall into the right-hand subtree. */
2766 5720 : if (bb && m_default_bb)
2767 4325 : emit_jump (bb, m_default_bb);
2768 :
2769 5720 : bb = emit_case_nodes (test_bb, index, node->m_right,
2770 : default_prob, index_type, loc);
2771 : }
2772 : }
2773 86373 : else if (node->m_left == NULL && node->m_right != NULL)
2774 : {
2775 : /* 2) the node has only right child. */
2776 :
2777 : /* Here we have a right child but no left so we issue a conditional
2778 : branch to default and process the right child.
2779 :
2780 : Omit the conditional branch to default if the right child
2781 : does not have any children and is single valued; it would
2782 : cost too much space to save so little time. */
2783 :
2784 28909 : if (node->m_right->has_child ()
2785 28590 : || !node->m_right->m_c->is_single_value_p ())
2786 : {
2787 3231 : p = ((default_prob / 2)
2788 1077 : / (node->m_c->m_subtree_prob + default_prob));
2789 1077 : bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
2790 : LT_EXPR, m_default_bb, p, loc);
2791 1077 : default_prob /= 2;
2792 :
2793 1077 : bb = emit_case_nodes (bb, index, node->m_right, default_prob,
2794 : index_type, loc);
2795 : }
2796 : else
2797 : {
2798 : /* We cannot process node->right normally
2799 : since we haven't ruled out the numbers less than
2800 : this node's value. So handle node->right explicitly. */
2801 55664 : p = (node->m_right->m_c->m_subtree_prob
2802 27832 : / (node->m_c->m_subtree_prob + default_prob));
2803 27832 : bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
2804 : node->m_right->m_c->m_case_bb, p, loc);
2805 : }
2806 : }
2807 57464 : else if (node->m_left != NULL && node->m_right == NULL)
2808 : {
2809 : /* 3) just one subtree, on the left. Similar case as previous. */
2810 :
2811 51643 : if (node->m_left->has_child ()
2812 0 : || !node->m_left->m_c->is_single_value_p ())
2813 : {
2814 154929 : p = ((default_prob / 2)
2815 51643 : / (node->m_c->m_subtree_prob + default_prob));
2816 51643 : bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
2817 : GT_EXPR, m_default_bb, p, loc);
2818 51643 : default_prob /= 2;
2819 :
2820 51643 : bb = emit_case_nodes (bb, index, node->m_left, default_prob,
2821 : index_type, loc);
2822 : }
2823 : else
2824 : {
2825 : /* We cannot process node->left normally
2826 : since we haven't ruled out the numbers less than
2827 : this node's value. So handle node->left explicitly. */
2828 0 : p = (node->m_left->m_c->m_subtree_prob
2829 0 : / (node->m_c->m_subtree_prob + default_prob));
2830 0 : bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
2831 : node->m_left->m_c->m_case_bb, p, loc);
2832 : }
2833 : }
2834 : }
2835 : else
2836 : {
2837 : /* Node is a range. These cases are very similar to those for a single
2838 : value, except that we do not start by testing whether this node
2839 : is the one to branch to. */
2840 29327 : if (node->has_child () || node->m_c->get_type () != SIMPLE_CASE)
2841 : {
2842 21767 : bool is_bt = node->m_c->get_type () == BIT_TEST;
2843 21767 : int parts = is_bt ? 3 : 2;
2844 :
2845 : /* Branch to a label where we will handle it later. */
2846 21767 : basic_block test_bb = split_edge (single_succ_edge (bb));
2847 21767 : redirect_edge_succ (single_pred_edge (test_bb),
2848 21767 : single_succ_edge (bb)->dest);
2849 :
2850 21767 : profile_probability right_prob = profile_probability::never ();
2851 21767 : if (node->m_right)
2852 2743 : right_prob = node->m_right->m_c->m_subtree_prob;
2853 21767 : p = ((right_prob + default_prob / parts)
2854 43534 : / (node->m_c->m_subtree_prob + default_prob));
2855 21767 : test_bb->count = bb->count.apply_probability (p);
2856 :
2857 21767 : bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
2858 : GT_EXPR, test_bb, p, loc);
2859 :
2860 21767 : default_prob /= parts;
2861 21767 : node->m_c->m_subtree_prob -= right_prob;
2862 21767 : if (is_bt)
2863 1315 : node->m_c->m_default_prob = default_prob;
2864 :
2865 : /* Value belongs to this node or to the left-hand subtree. */
2866 21767 : p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
2867 21767 : bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
2868 : GE_EXPR, node->m_c->m_case_bb, p, loc);
2869 :
2870 : /* Handle the left-hand subtree. */
2871 21767 : bb = emit_case_nodes (bb, index, node->m_left, default_prob,
2872 : index_type, loc);
2873 :
2874 : /* If the left-hand subtree fell through,
2875 : don't let it fall into the right-hand subtree. */
2876 21767 : if (bb && m_default_bb)
2877 21478 : emit_jump (bb, m_default_bb);
2878 :
2879 21767 : bb = emit_case_nodes (test_bb, index, node->m_right, default_prob,
2880 : index_type, loc);
2881 : }
2882 : else
2883 : {
2884 : /* Node has no children so we check low and high bounds to remove
2885 : redundant tests. Only one of the bounds can exist,
2886 : since otherwise this node is bounded--a case tested already. */
2887 3465 : tree lhs, rhs;
2888 3465 : generate_range_test (bb, index, node->m_c->get_low (),
2889 3465 : node->m_c->get_high (), &lhs, &rhs);
2890 3465 : p = default_prob / (node->m_c->m_subtree_prob + default_prob);
2891 :
2892 3465 : bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,
2893 : m_default_bb, p, loc);
2894 :
2895 3465 : emit_jump (bb, node->m_c->m_case_bb);
2896 3465 : return NULL;
2897 : }
2898 : }
2899 :
2900 : return bb;
2901 : }
2902 :
2903 : /* The main function of the pass scans statements for switches and invokes
2904 : process_switch on them. */
2905 :
2906 : namespace {
2907 :
2908 : const pass_data pass_data_convert_switch =
2909 : {
2910 : GIMPLE_PASS, /* type */
2911 : "switchconv", /* name */
2912 : OPTGROUP_NONE, /* optinfo_flags */
2913 : TV_TREE_SWITCH_CONVERSION, /* tv_id */
2914 : ( PROP_cfg | PROP_ssa ), /* properties_required */
2915 : 0, /* properties_provided */
2916 : 0, /* properties_destroyed */
2917 : 0, /* todo_flags_start */
2918 : TODO_update_ssa, /* todo_flags_finish */
2919 : };
2920 :
2921 : class pass_convert_switch : public gimple_opt_pass
2922 : {
2923 : public:
2924 293828 : pass_convert_switch (gcc::context *ctxt)
2925 587656 : : gimple_opt_pass (pass_data_convert_switch, ctxt)
2926 : {}
2927 :
2928 : /* opt_pass methods: */
2929 2497463 : bool gate (function *) final override
2930 : {
2931 2497463 : return flag_tree_switch_conversion != 0;
2932 : }
2933 : unsigned int execute (function *) final override;
2934 :
2935 : }; // class pass_convert_switch
2936 :
2937 : unsigned int
2938 2389617 : pass_convert_switch::execute (function *fun)
2939 : {
2940 2389617 : basic_block bb;
2941 2389617 : bool cfg_altered = false;
2942 :
2943 13103475 : FOR_EACH_BB_FN (bb, fun)
2944 : {
2945 31825079 : if (gswitch *stmt = safe_dyn_cast <gswitch *> (*gsi_last_bb (bb)))
2946 : {
2947 27019 : if (dump_file)
2948 : {
2949 43 : expanded_location loc = expand_location (gimple_location (stmt));
2950 :
2951 43 : fprintf (dump_file, "beginning to process the following "
2952 : "SWITCH statement (%s:%d) : ------- \n",
2953 : loc.file, loc.line);
2954 43 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2955 43 : putc ('\n', dump_file);
2956 : }
2957 :
2958 27019 : switch_conversion sconv;
2959 27019 : sconv.expand (stmt);
2960 27019 : cfg_altered |= sconv.m_cfg_altered;
2961 27019 : if (!sconv.m_reason)
2962 : {
2963 567 : if (dump_file)
2964 : {
2965 39 : fputs ("Switch converted\n", dump_file);
2966 39 : fputs ("--------------------------------\n", dump_file);
2967 : }
2968 :
2969 : /* Make no effort to update the post-dominator tree.
2970 : It is actually not that hard for the transformations
2971 : we have performed, but it is not supported
2972 : by iterate_fix_dominators. */
2973 567 : free_dominance_info (CDI_POST_DOMINATORS);
2974 : }
2975 : else
2976 : {
2977 26452 : if (dump_file)
2978 : {
2979 4 : fputs ("Bailing out - ", dump_file);
2980 4 : fputs (sconv.m_reason, dump_file);
2981 4 : fputs ("\n--------------------------------\n", dump_file);
2982 : }
2983 : }
2984 27019 : }
2985 : }
2986 :
2987 2389617 : return cfg_altered ? TODO_cleanup_cfg : 0;;
2988 : }
2989 :
2990 : } // anon namespace
2991 :
2992 : gimple_opt_pass *
2993 293828 : make_pass_convert_switch (gcc::context *ctxt)
2994 : {
2995 293828 : return new pass_convert_switch (ctxt);
2996 : }
2997 :
2998 : /* The main function of the pass scans statements for switches and invokes
2999 : process_switch on them. */
3000 :
3001 : namespace {
3002 :
3003 : template <bool O0> class pass_lower_switch: public gimple_opt_pass
3004 : {
3005 : public:
3006 1762968 : pass_lower_switch (gcc::context *ctxt) : gimple_opt_pass (data, ctxt) {}
3007 :
3008 : static const pass_data data;
3009 : opt_pass *
3010 293828 : clone () final override
3011 : {
3012 293828 : return new pass_lower_switch<O0> (m_ctxt);
3013 : }
3014 :
3015 : bool
3016 2546019 : gate (function *) final override
3017 : {
3018 2546019 : return !O0 || !optimize;
3019 : }
3020 :
3021 : unsigned int execute (function *fun) final override;
3022 : }; // class pass_lower_switch
3023 :
3024 : template <bool O0>
3025 : const pass_data pass_lower_switch<O0>::data = {
3026 : GIMPLE_PASS, /* type */
3027 : O0 ? "switchlower_O0" : "switchlower", /* name */
3028 : OPTGROUP_NONE, /* optinfo_flags */
3029 : TV_TREE_SWITCH_LOWERING, /* tv_id */
3030 : ( PROP_cfg | PROP_ssa ), /* properties_required */
3031 : 0, /* properties_provided */
3032 : 0, /* properties_destroyed */
3033 : 0, /* todo_flags_start */
3034 : TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
3035 : };
3036 :
3037 : template <bool O0>
3038 : unsigned int
3039 1494789 : pass_lower_switch<O0>::execute (function *fun)
3040 : {
3041 : basic_block bb;
3042 1494789 : bool expanded = false;
3043 :
3044 1494789 : auto_vec<gimple *> switch_statements;
3045 1494789 : switch_statements.create (1);
3046 :
3047 14924325 : FOR_EACH_BB_FN (bb, fun)
3048 : {
3049 26636124 : if (gswitch *swtch = safe_dyn_cast <gswitch *> (*gsi_last_bb (bb)))
3050 : {
3051 : if (!O0)
3052 28933 : group_case_labels_stmt (swtch);
3053 44463 : switch_statements.safe_push (swtch);
3054 : }
3055 : }
3056 :
3057 1539252 : for (unsigned i = 0; i < switch_statements.length (); i++)
3058 : {
3059 44463 : gimple *stmt = switch_statements[i];
3060 44463 : if (dump_file)
3061 : {
3062 24 : expanded_location loc = expand_location (gimple_location (stmt));
3063 :
3064 24 : fprintf (dump_file, "beginning to process the following "
3065 : "SWITCH statement (%s:%d) : ------- \n",
3066 : loc.file, loc.line);
3067 24 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3068 24 : putc ('\n', dump_file);
3069 : }
3070 :
3071 44463 : gswitch *swtch = dyn_cast<gswitch *> (stmt);
3072 : if (swtch)
3073 : {
3074 44463 : switch_decision_tree dt (swtch);
3075 44463 : expanded |= dt.analyze_switch_statement ();
3076 44463 : }
3077 : }
3078 :
3079 1494789 : if (expanded)
3080 : {
3081 31893 : free_dominance_info (CDI_DOMINATORS);
3082 31893 : free_dominance_info (CDI_POST_DOMINATORS);
3083 31893 : mark_virtual_operands_for_renaming (cfun);
3084 : }
3085 :
3086 1494789 : return 0;
3087 1494789 : }
3088 :
3089 : } // anon namespace
3090 :
3091 : gimple_opt_pass *
3092 293828 : make_pass_lower_switch_O0 (gcc::context *ctxt)
3093 : {
3094 293828 : return new pass_lower_switch<true> (ctxt);
3095 : }
3096 : gimple_opt_pass *
3097 293828 : make_pass_lower_switch (gcc::context *ctxt)
3098 : {
3099 293828 : return new pass_lower_switch<false> (ctxt);
3100 : }
|
