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