Branch data Line data Source code
1 : : /* Lower GIMPLE_SWITCH expressions to something more efficient than
2 : : a jump table.
3 : : Copyright (C) 2006-2025 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 : 5948 : can_log2 (tree type, optimization_type opt_type)
78 : : {
79 : : /* Check if target supports FFS for given type. */
80 : 5948 : 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 : 811 : int prec = TYPE_PRECISION (type);
85 : 811 : int i_prec = TYPE_PRECISION (integer_type_node);
86 : 811 : int li_prec = TYPE_PRECISION (long_integer_type_node);
87 : 811 : int lli_prec = TYPE_PRECISION (long_long_integer_type_node);
88 : 811 : tree new_type;
89 : 811 : if (prec <= i_prec
90 : 811 : && direct_internal_fn_supported_p (IFN_FFS, integer_type_node, opt_type))
91 : 801 : new_type = integer_type_node;
92 : 10 : else if (prec <= li_prec
93 : 10 : && direct_internal_fn_supported_p (IFN_FFS, long_integer_type_node,
94 : : opt_type))
95 : 0 : new_type = long_integer_type_node;
96 : 10 : else if (prec <= lli_prec
97 : 10 : && 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 : 10 : 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 : 25982 : switch_conversion::switch_conversion (): m_final_bb (NULL),
171 : 25982 : m_constructors (NULL), m_default_values (NULL),
172 : 25982 : m_arr_ref_first (NULL), m_arr_ref_last (NULL),
173 : 25982 : m_reason (NULL), m_default_case_nonstandard (false), m_cfg_altered (false),
174 : 25982 : m_exp_index_transform_applied (false)
175 : : {
176 : 25982 : }
177 : :
178 : : /* Collection information about SWTCH statement. */
179 : :
180 : : void
181 : 25982 : switch_conversion::collect (gswitch *swtch)
182 : : {
183 : 25982 : unsigned int branch_num = gimple_switch_num_labels (swtch);
184 : 25982 : tree min_case, max_case;
185 : 25982 : unsigned int i;
186 : 25982 : edge e, e_default, e_first;
187 : 25982 : edge_iterator ei;
188 : :
189 : 25982 : 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 : 25982 : m_index_expr = gimple_switch_index (swtch);
195 : 25982 : m_switch_bb = gimple_bb (swtch);
196 : 25982 : e_default = gimple_switch_default_edge (cfun, swtch);
197 : 25982 : m_default_bb = e_default->dest;
198 : 25982 : m_default_prob = e_default->probability;
199 : :
200 : : /* Get upper and lower bounds of case values, and the covered range. */
201 : 25982 : min_case = gimple_switch_label (swtch, 1);
202 : 25982 : max_case = gimple_switch_label (swtch, branch_num - 1);
203 : :
204 : 25982 : m_range_min = CASE_LOW (min_case);
205 : 25982 : if (CASE_HIGH (max_case) != NULL_TREE)
206 : 1979 : m_range_max = CASE_HIGH (max_case);
207 : : else
208 : 24003 : m_range_max = CASE_LOW (max_case);
209 : :
210 : 25982 : m_contiguous_range = true;
211 : 25982 : tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : m_range_min;
212 : 86330 : for (i = 2; i < branch_num; i++)
213 : : {
214 : 73302 : tree elt = gimple_switch_label (swtch, i);
215 : 73303 : if (wi::to_wide (last) + 1 != wi::to_wide (CASE_LOW (elt)))
216 : : {
217 : 12954 : m_contiguous_range = false;
218 : 12954 : break;
219 : : }
220 : 60348 : last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt);
221 : : }
222 : :
223 : 25982 : if (m_contiguous_range)
224 : 13028 : 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 : 25982 : if (! single_pred_p (e_first->dest))
234 : 7598 : m_final_bb = e_first->dest;
235 : 18384 : else if (single_succ_p (e_first->dest)
236 : 16630 : && ! single_pred_p (single_succ (e_first->dest)))
237 : 11850 : 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 : 25982 : auto_vec<edge, 10> fw_edges;
242 : 25982 : m_uniq = 0;
243 : 25982 : if (m_final_bb)
244 : 93319 : FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
245 : : {
246 : 83052 : edge phi_e = nullptr;
247 : 83052 : if (e->dest == m_final_bb)
248 : 12232 : phi_e = e;
249 : 70820 : else if (single_pred_p (e->dest)
250 : 144433 : && single_succ_p (e->dest)
251 : 132201 : && single_succ (e->dest) == m_final_bb)
252 : 58931 : phi_e = single_succ_edge (e->dest);
253 : 83052 : if (phi_e)
254 : : {
255 : 71163 : if (e == e_default)
256 : : ;
257 : 54773 : 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 : 106819 : for (i = 0; i < fw_edges.length (); ++i)
263 : 92500 : if (phi_alternatives_equal (m_final_bb, fw_edges[i], phi_e))
264 : : break;
265 : 28714 : if (i == fw_edges.length ())
266 : : {
267 : : /* But limit the above possibly quadratic search. */
268 : 14319 : if (fw_edges.length () < 10)
269 : 5947 : fw_edges.quick_push (phi_e);
270 : 14319 : m_uniq++;
271 : : }
272 : : }
273 : : else
274 : 40416 : m_uniq++;
275 : 73871 : continue;
276 : 71163 : }
277 : :
278 : 11889 : if (e == e_default && m_contiguous_range)
279 : : {
280 : 2708 : m_default_case_nonstandard = true;
281 : 2708 : continue;
282 : : }
283 : :
284 : 9181 : m_final_bb = NULL;
285 : 9181 : break;
286 : : }
287 : :
288 : : /* When there's not a single common successor block conservatively
289 : : approximate the number of unique non-default targets. */
290 : 25982 : if (!m_final_bb)
291 : 31430 : m_uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
292 : :
293 : 25982 : m_range_size
294 : 25982 : = 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 : 25982 : m_count = 0;
300 : 178998 : for (i = 1; i < branch_num; i++)
301 : : {
302 : 153016 : tree elt = gimple_switch_label (swtch, i);
303 : 153016 : m_count++;
304 : 153016 : if (CASE_HIGH (elt)
305 : 153016 : && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
306 : 11458 : m_count++;
307 : : }
308 : 25982 : }
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 : 5948 : switch_conversion::is_exp_index_transform_viable (gswitch *swtch)
323 : : {
324 : 5948 : tree index = gimple_switch_index (swtch);
325 : 5948 : tree index_type = TREE_TYPE (index);
326 : 5948 : basic_block swtch_bb = gimple_bb (swtch);
327 : 5948 : unsigned num_labels = gimple_switch_num_labels (swtch);
328 : :
329 : 5948 : optimization_type opt_type = bb_optimization_type (swtch_bb);
330 : 5948 : m_exp_index_transform_log2_type = can_log2 (index_type, opt_type);
331 : 5948 : 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 : 47189 : for (i = 1; i < num_labels; i++)
338 : : {
339 : 41517 : tree label = gimple_switch_label (swtch, i);
340 : 41517 : if (CASE_HIGH (label))
341 : : return false;
342 : : }
343 : :
344 : : /* Check that each label is nonnegative and a power of 2. */
345 : 8357 : for (i = 1; i < num_labels; i++)
346 : : {
347 : 8292 : tree label = gimple_switch_label (swtch, i);
348 : 8292 : wide_int label_wi = wi::to_wide (CASE_LOW (label));
349 : 8292 : if (!wi::ge_p (label_wi, 0, TYPE_SIGN (index_type)))
350 : : return false;
351 : 8181 : if (wi::exact_log2 (label_wi) == -1)
352 : : return false;
353 : 8292 : }
354 : :
355 : 65 : 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 : 5883 : switch_conversion::check_range ()
555 : : {
556 : 5883 : gcc_assert (m_range_size);
557 : 5883 : 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 : 5865 : if (tree_to_uhwi (m_range_size)
564 : 5865 : > ((unsigned) m_count * param_switch_conversion_branch_ratio))
565 : : {
566 : 262 : m_reason = "the maximum range-branch ratio exceeded";
567 : 262 : 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 : 5668 : switch_conversion::check_all_empty_except_final ()
577 : : {
578 : 5668 : edge e, e_default = find_edge (m_switch_bb, m_default_bb);
579 : 5668 : edge_iterator ei;
580 : :
581 : 18997 : FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
582 : : {
583 : 18324 : if (e->dest == m_final_bb)
584 : 4134 : continue;
585 : :
586 : 14190 : if (!empty_block_p (e->dest))
587 : : {
588 : 5935 : if (m_contiguous_range && e == e_default)
589 : : {
590 : 940 : m_default_case_nonstandard = true;
591 : 940 : continue;
592 : : }
593 : :
594 : 4995 : m_reason = "bad case - a non-final BB not empty";
595 : 4995 : 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 : 673 : switch_conversion::check_final_bb ()
609 : : {
610 : 673 : gphi_iterator gsi;
611 : :
612 : 673 : m_phi_count = 0;
613 : 1325 : for (gsi = gsi_start_phis (m_final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
614 : : {
615 : 743 : gphi *phi = gsi.phi ();
616 : 743 : unsigned int i;
617 : :
618 : 1486 : if (virtual_operand_p (gimple_phi_result (phi)))
619 : 17 : continue;
620 : :
621 : 726 : m_phi_count++;
622 : :
623 : 9251 : for (i = 0; i < gimple_phi_num_args (phi); i++)
624 : : {
625 : 8616 : basic_block bb = gimple_phi_arg_edge (phi, i)->src;
626 : :
627 : 8616 : if (bb == m_switch_bb
628 : 25016 : || (single_pred_p (bb)
629 : 7875 : && single_pred (bb) == m_switch_bb
630 : 7703 : && (!m_default_case_nonstandard
631 : 473 : || empty_block_p (bb))))
632 : : {
633 : 8403 : tree reloc, val;
634 : 8403 : const char *reason = NULL;
635 : :
636 : 8403 : val = gimple_phi_arg_def (phi, i);
637 : 8403 : if (!is_gimple_ip_invariant (val))
638 : : reason = "non-invariant value from a case";
639 : : else
640 : : {
641 : 8360 : reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
642 : 8360 : if ((flag_pic && reloc != null_pointer_node)
643 : 8295 : || (!flag_pic && reloc == NULL_TREE))
644 : : {
645 : 65 : 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 : 108 : if (bb == m_switch_bb)
659 : 92 : bb = m_final_bb;
660 : 108 : if (!m_contiguous_range || bb != m_default_bb)
661 : : {
662 : 91 : m_reason = reason;
663 : 91 : 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 : 582 : switch_conversion::create_temp_arrays ()
690 : : {
691 : 582 : int i;
692 : :
693 : 582 : 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 : 582 : typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc;
697 : 582 : m_constructors = XCNEWVEC (vec_constructor_elt_gc, m_phi_count);
698 : 582 : m_target_inbound_names = m_default_values + m_phi_count;
699 : 582 : m_target_outbound_names = m_target_inbound_names + m_phi_count;
700 : 1215 : for (i = 0; i < m_phi_count; i++)
701 : 633 : vec_alloc (m_constructors[i], tree_to_uhwi (m_range_size) + 1);
702 : 582 : }
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 : 582 : switch_conversion::gather_default_values (tree default_case)
711 : : {
712 : 582 : gphi_iterator gsi;
713 : 582 : basic_block bb = label_to_block (cfun, CASE_LABEL (default_case));
714 : 582 : edge e;
715 : 582 : int i = 0;
716 : :
717 : 582 : gcc_assert (CASE_LOW (default_case) == NULL_TREE
718 : : || m_default_case_nonstandard);
719 : :
720 : 582 : if (bb == m_final_bb)
721 : 205 : e = find_edge (m_switch_bb, bb);
722 : : else
723 : 377 : e = single_succ_edge (bb);
724 : :
725 : 1232 : for (gsi = gsi_start_phis (m_final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
726 : : {
727 : 650 : gphi *phi = gsi.phi ();
728 : 1300 : if (virtual_operand_p (gimple_phi_result (phi)))
729 : 17 : continue;
730 : 633 : tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
731 : 633 : gcc_assert (val);
732 : 633 : m_default_values[i++] = val;
733 : : }
734 : 582 : }
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 : 582 : switch_conversion::build_constructors ()
742 : : {
743 : 582 : unsigned i, branch_num = gimple_switch_num_labels (m_switch);
744 : 582 : tree pos = m_range_min;
745 : 582 : tree pos_one = build_int_cst (TREE_TYPE (pos), 1);
746 : :
747 : 8296 : for (i = 1; i < branch_num; i++)
748 : : {
749 : 7714 : tree cs = gimple_switch_label (m_switch, i);
750 : 7714 : basic_block bb = label_to_block (cfun, CASE_LABEL (cs));
751 : 7714 : edge e;
752 : 7714 : tree high;
753 : 7714 : gphi_iterator gsi;
754 : 7714 : int j;
755 : :
756 : 7714 : if (bb == m_final_bb)
757 : 449 : e = find_edge (m_switch_bb, bb);
758 : : else
759 : 7265 : e = single_succ_edge (bb);
760 : 7714 : gcc_assert (e);
761 : :
762 : 10444 : while (tree_int_cst_lt (pos, CASE_LOW (cs)))
763 : : {
764 : : int k;
765 : 6892 : for (k = 0; k < m_phi_count; k++)
766 : : {
767 : 4162 : constructor_elt elt;
768 : :
769 : 4162 : elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min);
770 : 4162 : if (TYPE_PRECISION (TREE_TYPE (elt.index))
771 : 4162 : > TYPE_PRECISION (sizetype))
772 : 18 : elt.index = fold_convert (sizetype, elt.index);
773 : 4162 : elt.value
774 : 4162 : = unshare_expr_without_location (m_default_values[k]);
775 : 4162 : m_constructors[k]->quick_push (elt);
776 : : }
777 : :
778 : 2730 : pos = int_const_binop (PLUS_EXPR, pos, pos_one);
779 : : }
780 : 7714 : gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
781 : :
782 : 7714 : j = 0;
783 : 7714 : if (CASE_HIGH (cs))
784 : 108 : high = CASE_HIGH (cs);
785 : : else
786 : 7606 : high = CASE_LOW (cs);
787 : 7714 : for (gsi = gsi_start_phis (m_final_bb);
788 : 15924 : !gsi_end_p (gsi); gsi_next (&gsi))
789 : : {
790 : 8210 : gphi *phi = gsi.phi ();
791 : 16420 : if (virtual_operand_p (gimple_phi_result (phi)))
792 : 72 : continue;
793 : 8138 : tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
794 : 8138 : tree low = CASE_LOW (cs);
795 : 8138 : pos = CASE_LOW (cs);
796 : :
797 : 8465 : do
798 : : {
799 : 8465 : constructor_elt elt;
800 : :
801 : 8465 : elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min);
802 : 8465 : if (TYPE_PRECISION (TREE_TYPE (elt.index))
803 : 8465 : > TYPE_PRECISION (sizetype))
804 : 3 : elt.index = fold_convert (sizetype, elt.index);
805 : 8465 : elt.value = unshare_expr_without_location (val);
806 : 8465 : m_constructors[j]->quick_push (elt);
807 : :
808 : 8465 : pos = int_const_binop (PLUS_EXPR, pos, pos_one);
809 : 8465 : } while (!tree_int_cst_lt (high, pos)
810 : 16603 : && tree_int_cst_lt (low, pos));
811 : 8138 : j++;
812 : : }
813 : : }
814 : 582 : }
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 : 633 : switch_conversion::contains_linear_function_p (vec<constructor_elt, va_gc> *vec,
823 : : wide_int *coeff_a,
824 : : wide_int *coeff_b)
825 : : {
826 : 633 : unsigned int i;
827 : 633 : constructor_elt *elt;
828 : :
829 : 633 : 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 : 633 : tree elt0 = (*vec)[0].value;
844 : 633 : tree elt1 = (*vec)[1].value;
845 : :
846 : 633 : if (TREE_CODE (elt0) != INTEGER_CST || TREE_CODE (elt1) != INTEGER_CST)
847 : : return false;
848 : :
849 : 479 : wide_int range_min
850 : 479 : = wide_int::from (wi::to_wide (m_range_min),
851 : 479 : TYPE_PRECISION (TREE_TYPE (elt0)),
852 : 1437 : TYPE_SIGN (TREE_TYPE (m_range_min)));
853 : 479 : wide_int y1 = wi::to_wide (elt0);
854 : 479 : wide_int y2 = wi::to_wide (elt1);
855 : 479 : wide_int a = y2 - y1;
856 : 479 : wide_int b = y2 - a * (range_min + 1);
857 : :
858 : : /* Verify that all values fulfill the linear function. */
859 : 1914 : FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
860 : : {
861 : 1825 : if (TREE_CODE (elt->value) != INTEGER_CST)
862 : 390 : return false;
863 : :
864 : 1825 : wide_int value = wi::to_wide (elt->value);
865 : 1825 : if (a * range_min + b != value)
866 : 390 : return false;
867 : :
868 : 1435 : ++range_min;
869 : 1825 : }
870 : :
871 : 89 : *coeff_a = a;
872 : 89 : *coeff_b = b;
873 : :
874 : 89 : return true;
875 : 479 : }
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 : 544 : switch_conversion::array_value_type (tree type, int num)
883 : : {
884 : 544 : unsigned int i, len = vec_safe_length (m_constructors[num]);
885 : 544 : constructor_elt *elt;
886 : 544 : int sign = 0;
887 : 544 : 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 : 544 : type = TYPE_MAIN_VARIANT (type);
895 : :
896 : 544 : if (!INTEGRAL_TYPE_P (type)
897 : 544 : || (TREE_CODE (type) == BITINT_TYPE
898 : 0 : && (TYPE_PRECISION (type) > MAX_FIXED_MODE_SIZE
899 : 0 : || TYPE_MODE (type) == BLKmode)))
900 : 154 : return type;
901 : :
902 : 390 : scalar_int_mode type_mode = SCALAR_INT_TYPE_MODE (type);
903 : 390 : scalar_int_mode mode = get_narrowest_mode (type_mode);
904 : 1170 : if (GET_MODE_SIZE (type_mode) <= GET_MODE_SIZE (mode))
905 : : return type;
906 : :
907 : 728 : 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 : 633 : switch_conversion::build_one_array (int num, tree arr_index_type,
969 : : gphi *phi, tree tidx)
970 : : {
971 : 633 : tree name;
972 : 633 : gimple *load;
973 : 633 : gimple_stmt_iterator gsi = gsi_for_stmt (m_switch);
974 : 633 : location_t loc = gimple_location (m_switch);
975 : :
976 : 633 : gcc_assert (m_default_values[num]);
977 : :
978 : 633 : name = copy_ssa_name (PHI_RESULT (phi));
979 : 633 : m_target_inbound_names[num] = name;
980 : :
981 : 633 : vec<constructor_elt, va_gc> *constructor = m_constructors[num];
982 : 633 : wide_int coeff_a, coeff_b;
983 : 633 : bool linear_p = contains_linear_function_p (constructor, &coeff_a, &coeff_b);
984 : 633 : tree type;
985 : 633 : if (linear_p
986 : 633 : && (type = range_check_type (TREE_TYPE ((*constructor)[0].value))))
987 : : {
988 : 106 : if (dump_file && coeff_a.to_uhwi () > 0)
989 : 16 : fprintf (dump_file, "Linear transformation with A = %" PRId64
990 : : " and B = %" PRId64 "\n", coeff_a.to_shwi (),
991 : : coeff_b.to_shwi ());
992 : :
993 : : /* We must use type of constructor values. */
994 : 89 : gimple_seq seq = NULL;
995 : 89 : tree tmp = gimple_convert (&seq, type, m_index_expr);
996 : 178 : tree tmp2 = gimple_build (&seq, MULT_EXPR, type,
997 : 89 : wide_int_to_tree (type, coeff_a), tmp);
998 : 178 : tree tmp3 = gimple_build (&seq, PLUS_EXPR, type, tmp2,
999 : 89 : wide_int_to_tree (type, coeff_b));
1000 : 89 : tree tmp4 = gimple_convert (&seq, TREE_TYPE (name), tmp3);
1001 : 89 : gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
1002 : 89 : load = gimple_build_assign (name, tmp4);
1003 : : }
1004 : : else
1005 : : {
1006 : 544 : tree array_type, ctor, decl, value_type, fetch, default_type;
1007 : :
1008 : 544 : default_type = TREE_TYPE (m_default_values[num]);
1009 : 544 : value_type = array_value_type (default_type, num);
1010 : 544 : array_type = build_array_type (value_type, arr_index_type);
1011 : 544 : if (default_type != value_type)
1012 : : {
1013 : : unsigned int i;
1014 : : constructor_elt *elt;
1015 : :
1016 : 3368 : FOR_EACH_VEC_SAFE_ELT (constructor, i, elt)
1017 : 3256 : elt->value = fold_convert (value_type, elt->value);
1018 : : }
1019 : 544 : ctor = build_constructor (array_type, constructor);
1020 : 544 : TREE_CONSTANT (ctor) = true;
1021 : 544 : TREE_STATIC (ctor) = true;
1022 : :
1023 : 544 : decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
1024 : 544 : TREE_STATIC (decl) = 1;
1025 : 544 : DECL_INITIAL (decl) = ctor;
1026 : :
1027 : 544 : DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
1028 : 544 : DECL_ARTIFICIAL (decl) = 1;
1029 : 544 : DECL_IGNORED_P (decl) = 1;
1030 : 544 : TREE_CONSTANT (decl) = 1;
1031 : 544 : TREE_READONLY (decl) = 1;
1032 : 544 : DECL_IGNORED_P (decl) = 1;
1033 : 544 : if (offloading_function_p (cfun->decl))
1034 : 0 : DECL_ATTRIBUTES (decl)
1035 : 0 : = tree_cons (get_identifier ("omp declare target"), NULL_TREE,
1036 : : NULL_TREE);
1037 : 544 : varpool_node::finalize_decl (decl);
1038 : :
1039 : 544 : fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
1040 : : NULL_TREE);
1041 : 544 : if (default_type != value_type)
1042 : : {
1043 : 112 : fetch = fold_convert (default_type, fetch);
1044 : 112 : fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
1045 : : true, GSI_SAME_STMT);
1046 : : }
1047 : 544 : load = gimple_build_assign (name, fetch);
1048 : : }
1049 : :
1050 : 633 : gsi_insert_before (&gsi, load, GSI_SAME_STMT);
1051 : 633 : update_stmt (load);
1052 : 633 : m_arr_ref_last = load;
1053 : 633 : }
1054 : :
1055 : : /* Builds and initializes static arrays initialized with values gathered from
1056 : : the switch statement. Also creates statements that load values from
1057 : : them. */
1058 : :
1059 : : void
1060 : 582 : switch_conversion::build_arrays ()
1061 : : {
1062 : 582 : tree arr_index_type;
1063 : 582 : tree tidx, sub, utype, tidxtype;
1064 : 582 : gimple *stmt;
1065 : 582 : gimple_stmt_iterator gsi;
1066 : 582 : gphi_iterator gpi;
1067 : 582 : int i;
1068 : 582 : location_t loc = gimple_location (m_switch);
1069 : :
1070 : 582 : gsi = gsi_for_stmt (m_switch);
1071 : :
1072 : : /* Make sure we do not generate arithmetics in a subrange. */
1073 : 582 : utype = TREE_TYPE (m_index_expr);
1074 : 582 : if (TREE_TYPE (utype))
1075 : 46 : utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
1076 : 536 : else if (TREE_CODE (utype) == BITINT_TYPE
1077 : 537 : && (TYPE_PRECISION (utype) > MAX_FIXED_MODE_SIZE
1078 : 0 : || TYPE_MODE (utype) == BLKmode))
1079 : 1 : utype = unsigned_type_for (utype);
1080 : : else
1081 : 535 : utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
1082 : 582 : if (TYPE_PRECISION (utype) > TYPE_PRECISION (sizetype))
1083 : 1 : tidxtype = sizetype;
1084 : : else
1085 : : tidxtype = utype;
1086 : :
1087 : 582 : arr_index_type = build_index_type (m_range_size);
1088 : 582 : tidx = make_ssa_name (tidxtype);
1089 : 582 : sub = fold_build2_loc (loc, MINUS_EXPR, utype,
1090 : : fold_convert_loc (loc, utype, m_index_expr),
1091 : : fold_convert_loc (loc, utype, m_range_min));
1092 : 582 : sub = fold_convert (tidxtype, sub);
1093 : 582 : sub = force_gimple_operand_gsi (&gsi, sub,
1094 : : false, NULL, true, GSI_SAME_STMT);
1095 : 582 : stmt = gimple_build_assign (tidx, sub);
1096 : :
1097 : 582 : gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1098 : 582 : update_stmt (stmt);
1099 : 582 : m_arr_ref_first = stmt;
1100 : :
1101 : 582 : for (gpi = gsi_start_phis (m_final_bb), i = 0;
1102 : 1232 : !gsi_end_p (gpi); gsi_next (&gpi))
1103 : : {
1104 : 650 : gphi *phi = gpi.phi ();
1105 : 1300 : if (!virtual_operand_p (gimple_phi_result (phi)))
1106 : 633 : build_one_array (i++, arr_index_type, phi, tidx);
1107 : : else
1108 : : {
1109 : 17 : edge e;
1110 : 17 : edge_iterator ei;
1111 : 21 : FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
1112 : : {
1113 : 21 : if (e->dest == m_final_bb)
1114 : : break;
1115 : 11 : if (!m_default_case_nonstandard
1116 : 4 : || e->dest != m_default_bb)
1117 : : {
1118 : 7 : e = single_succ_edge (e->dest);
1119 : 7 : break;
1120 : : }
1121 : : }
1122 : 17 : gcc_assert (e && e->dest == m_final_bb);
1123 : 17 : m_target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e);
1124 : : }
1125 : : }
1126 : 582 : }
1127 : :
1128 : : /* Generates and appropriately inserts loads of default values at the position
1129 : : given by GSI. Returns the last inserted statement. */
1130 : :
1131 : : gassign *
1132 : 480 : switch_conversion::gen_def_assigns (gimple_stmt_iterator *gsi)
1133 : : {
1134 : 480 : int i;
1135 : 480 : gassign *assign = NULL;
1136 : :
1137 : 1001 : for (i = 0; i < m_phi_count; i++)
1138 : : {
1139 : 521 : tree name = copy_ssa_name (m_target_inbound_names[i]);
1140 : 521 : m_target_outbound_names[i] = name;
1141 : 521 : assign = gimple_build_assign (name, m_default_values[i]);
1142 : 521 : gsi_insert_before (gsi, assign, GSI_SAME_STMT);
1143 : 521 : update_stmt (assign);
1144 : : }
1145 : 480 : return assign;
1146 : : }
1147 : :
1148 : : /* Deletes the unused bbs and edges that now contain the switch statement and
1149 : : its empty branch bbs. BBD is the now dead BB containing
1150 : : the original switch statement, FINAL is the last BB of the converted
1151 : : switch statement (in terms of succession). */
1152 : :
1153 : : void
1154 : 582 : switch_conversion::prune_bbs (basic_block bbd, basic_block final,
1155 : : basic_block default_bb)
1156 : : {
1157 : 582 : edge_iterator ei;
1158 : 582 : edge e;
1159 : :
1160 : 9319 : for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
1161 : : {
1162 : 8155 : basic_block bb;
1163 : 8155 : bb = e->dest;
1164 : 8155 : remove_edge (e);
1165 : 8155 : if (bb != final && bb != default_bb)
1166 : 7482 : delete_basic_block (bb);
1167 : : }
1168 : 582 : delete_basic_block (bbd);
1169 : 582 : }
1170 : :
1171 : : /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
1172 : : from the basic block loading values from an array and E2F from the basic
1173 : : block loading default values. BBF is the last switch basic block (see the
1174 : : bbf description in the comment below). */
1175 : :
1176 : : void
1177 : 582 : switch_conversion::fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
1178 : : {
1179 : 582 : gphi_iterator gsi;
1180 : 582 : int i;
1181 : :
1182 : 582 : for (gsi = gsi_start_phis (bbf), i = 0;
1183 : 1232 : !gsi_end_p (gsi); gsi_next (&gsi))
1184 : : {
1185 : 650 : gphi *phi = gsi.phi ();
1186 : 650 : tree inbound, outbound;
1187 : 1300 : if (virtual_operand_p (gimple_phi_result (phi)))
1188 : 17 : inbound = outbound = m_target_vop;
1189 : : else
1190 : : {
1191 : 633 : inbound = m_target_inbound_names[i];
1192 : 633 : outbound = m_target_outbound_names[i++];
1193 : : }
1194 : 650 : add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION);
1195 : 650 : if (!m_default_case_nonstandard)
1196 : 534 : add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION);
1197 : : }
1198 : 582 : }
1199 : :
1200 : : /* Creates a check whether the switch expression value actually falls into the
1201 : : range given by all the cases. If it does not, the temporaries are loaded
1202 : : with default values instead. */
1203 : :
1204 : : void
1205 : 582 : switch_conversion::gen_inbound_check ()
1206 : : {
1207 : 582 : tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
1208 : 582 : tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
1209 : 582 : tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
1210 : 582 : glabel *label1, *label2, *label3;
1211 : 582 : tree utype, tidx;
1212 : 582 : tree bound;
1213 : :
1214 : 582 : gcond *cond_stmt;
1215 : :
1216 : 582 : gassign *last_assign = NULL;
1217 : 582 : gimple_stmt_iterator gsi;
1218 : 582 : basic_block bb0, bb1, bb2, bbf, bbd;
1219 : 582 : edge e01 = NULL, e02, e21, e1d, e1f, e2f;
1220 : 582 : location_t loc = gimple_location (m_switch);
1221 : :
1222 : 582 : gcc_assert (m_default_values);
1223 : :
1224 : 582 : bb0 = gimple_bb (m_switch);
1225 : :
1226 : 582 : tidx = gimple_assign_lhs (m_arr_ref_first);
1227 : 582 : utype = TREE_TYPE (tidx);
1228 : :
1229 : : /* (end of) block 0 */
1230 : 582 : gsi = gsi_for_stmt (m_arr_ref_first);
1231 : 582 : gsi_next (&gsi);
1232 : :
1233 : 582 : bound = fold_convert_loc (loc, utype, m_range_size);
1234 : 582 : cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
1235 : 582 : gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1236 : 582 : update_stmt (cond_stmt);
1237 : :
1238 : : /* block 2 */
1239 : 582 : if (!m_default_case_nonstandard)
1240 : : {
1241 : 480 : label2 = gimple_build_label (label_decl2);
1242 : 480 : gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
1243 : 480 : last_assign = gen_def_assigns (&gsi);
1244 : : }
1245 : :
1246 : : /* block 1 */
1247 : 582 : label1 = gimple_build_label (label_decl1);
1248 : 582 : gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
1249 : :
1250 : : /* block F */
1251 : 582 : gsi = gsi_start_bb (m_final_bb);
1252 : 582 : label3 = gimple_build_label (label_decl3);
1253 : 582 : gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
1254 : :
1255 : : /* cfg fix */
1256 : 582 : e02 = split_block (bb0, cond_stmt);
1257 : 582 : bb2 = e02->dest;
1258 : :
1259 : 582 : if (m_default_case_nonstandard)
1260 : : {
1261 : 102 : bb1 = bb2;
1262 : 102 : bb2 = m_default_bb;
1263 : 102 : e01 = e02;
1264 : 102 : e01->flags = EDGE_TRUE_VALUE;
1265 : 102 : e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE);
1266 : 102 : edge e_default = find_edge (bb1, bb2);
1267 : 102 : for (gphi_iterator gsi = gsi_start_phis (bb2);
1268 : 129 : !gsi_end_p (gsi); gsi_next (&gsi))
1269 : : {
1270 : 27 : gphi *phi = gsi.phi ();
1271 : 27 : tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_default);
1272 : 27 : add_phi_arg (phi, arg, e02,
1273 : : gimple_phi_arg_location_from_edge (phi, e_default));
1274 : : }
1275 : : /* Partially fix the dominator tree, if it is available. */
1276 : 102 : if (dom_info_available_p (CDI_DOMINATORS))
1277 : 102 : redirect_immediate_dominators (CDI_DOMINATORS, bb1, bb0);
1278 : : }
1279 : : else
1280 : : {
1281 : 480 : e21 = split_block (bb2, last_assign);
1282 : 480 : bb1 = e21->dest;
1283 : 480 : remove_edge (e21);
1284 : : }
1285 : :
1286 : 582 : e1d = split_block (bb1, m_arr_ref_last);
1287 : 582 : bbd = e1d->dest;
1288 : 582 : remove_edge (e1d);
1289 : :
1290 : : /* Flags and profiles of the edge for in-range values. */
1291 : 582 : if (!m_default_case_nonstandard)
1292 : 480 : e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
1293 : 582 : e01->probability = m_default_prob.invert ();
1294 : :
1295 : : /* Flags and profiles of the edge taking care of out-of-range values. */
1296 : 582 : e02->flags &= ~EDGE_FALLTHRU;
1297 : 582 : e02->flags |= EDGE_FALSE_VALUE;
1298 : 582 : e02->probability = m_default_prob;
1299 : :
1300 : 582 : bbf = m_final_bb;
1301 : :
1302 : 582 : e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
1303 : 582 : e1f->probability = profile_probability::always ();
1304 : :
1305 : 582 : if (m_default_case_nonstandard)
1306 : : e2f = NULL;
1307 : : else
1308 : : {
1309 : 480 : e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
1310 : 480 : e2f->probability = profile_probability::always ();
1311 : : }
1312 : :
1313 : : /* frequencies of the new BBs */
1314 : 582 : bb1->count = e01->count ();
1315 : 582 : bb2->count = e02->count ();
1316 : 582 : if (!m_default_case_nonstandard)
1317 : 480 : bbf->count = e1f->count () + e2f->count ();
1318 : :
1319 : : /* Tidy blocks that have become unreachable. */
1320 : 1287 : bool prune_default_bb = !m_default_case_nonstandard
1321 : 582 : && !m_exp_index_transform_applied;
1322 : 582 : prune_bbs (bbd, m_final_bb, prune_default_bb ? NULL : m_default_bb);
1323 : :
1324 : : /* Fixup the PHI nodes in bbF. */
1325 : 582 : fix_phi_nodes (e1f, e2f, bbf);
1326 : :
1327 : : /* Fix the dominator tree, if it is available. */
1328 : 582 : if (dom_info_available_p (CDI_DOMINATORS))
1329 : : {
1330 : 582 : vec<basic_block> bbs_to_fix_dom;
1331 : :
1332 : 582 : set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
1333 : 582 : if (!m_default_case_nonstandard)
1334 : 480 : set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
1335 : 582 : if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
1336 : : /* If bbD was the immediate dominator ... */
1337 : 359 : set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
1338 : :
1339 : 597 : bbs_to_fix_dom.create (3 + (bb2 != bbf));
1340 : 582 : bbs_to_fix_dom.quick_push (bb0);
1341 : 582 : bbs_to_fix_dom.quick_push (bb1);
1342 : 582 : if (bb2 != bbf)
1343 : 567 : bbs_to_fix_dom.quick_push (bb2);
1344 : 582 : bbs_to_fix_dom.quick_push (bbf);
1345 : :
1346 : 582 : iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
1347 : 582 : bbs_to_fix_dom.release ();
1348 : : }
1349 : 582 : }
1350 : :
1351 : : /* The following function is invoked on every switch statement (the current
1352 : : one is given in SWTCH) and runs the individual phases of switch
1353 : : conversion on it one after another until one fails or the conversion
1354 : : is completed. On success, NULL is in m_reason, otherwise points
1355 : : to a string with the reason why the conversion failed. */
1356 : :
1357 : : void
1358 : 25982 : switch_conversion::expand (gswitch *swtch)
1359 : : {
1360 : : /* Group case labels so that we get the right results from the heuristics
1361 : : that decide on the code generation approach for this switch. */
1362 : 25982 : m_cfg_altered |= group_case_labels_stmt (swtch);
1363 : :
1364 : : /* If this switch is now a degenerate case with only a default label,
1365 : : there is nothing left for us to do. */
1366 : 25982 : if (gimple_switch_num_labels (swtch) < 2)
1367 : : {
1368 : 0 : m_reason = "switch is a degenerate case";
1369 : 0 : return;
1370 : : }
1371 : :
1372 : 25982 : collect (swtch);
1373 : :
1374 : : /* No error markers should reach here (they should be filtered out
1375 : : during gimplification). */
1376 : 25982 : gcc_checking_assert (TREE_TYPE (m_index_expr) != error_mark_node);
1377 : :
1378 : : /* Prefer bit test if possible. */
1379 : 25982 : if (tree_fits_uhwi_p (m_range_size)
1380 : 25912 : && bit_test_cluster::can_be_handled (tree_to_uhwi (m_range_size), m_uniq)
1381 : 39422 : && bit_test_cluster::is_beneficial (m_count, m_uniq))
1382 : : {
1383 : 2258 : m_reason = "expanding as bit test is preferable";
1384 : 2258 : return;
1385 : : }
1386 : :
1387 : 23724 : if (m_uniq <= 2)
1388 : : {
1389 : : /* This will be expanded as a decision tree . */
1390 : 7839 : m_reason = "expanding as jumps is preferable";
1391 : 7839 : return;
1392 : : }
1393 : :
1394 : : /* If there is no common successor, we cannot do the transformation. */
1395 : 15885 : if (!m_final_bb)
1396 : : {
1397 : 9937 : m_reason = "no common successor to all case label target blocks found";
1398 : 9937 : return;
1399 : : }
1400 : :
1401 : : /* Sometimes it is possible to use the "exponential index transform" to help
1402 : : switch conversion convert switches which it otherwise could not convert.
1403 : : However, we want to do this transform only when we know that switch
1404 : : conversion will then really be able to convert the switch. So we first
1405 : : check if the transformation is applicable and then maybe later do the
1406 : : transformation. */
1407 : 5948 : bool exp_transform_viable = is_exp_index_transform_viable (swtch);
1408 : :
1409 : : /* Check the case label values are within reasonable range.
1410 : :
1411 : : If we will be doing exponential index transform, the range will be always
1412 : : reasonable. */
1413 : 5948 : if (!exp_transform_viable && !check_range ())
1414 : : {
1415 : 280 : gcc_assert (m_reason);
1416 : : return;
1417 : : }
1418 : :
1419 : : /* For all the cases, see whether they are empty, the assignments they
1420 : : represent constant and so on... */
1421 : 5668 : if (!check_all_empty_except_final ())
1422 : : {
1423 : 4995 : gcc_assert (m_reason);
1424 : : return;
1425 : : }
1426 : 673 : if (!check_final_bb ())
1427 : : {
1428 : 91 : gcc_assert (m_reason);
1429 : : return;
1430 : : }
1431 : :
1432 : : /* At this point all checks have passed and we can proceed with the
1433 : : transformation. */
1434 : :
1435 : 582 : if (exp_transform_viable)
1436 : 21 : exp_index_transform (swtch);
1437 : :
1438 : 582 : create_temp_arrays ();
1439 : 1164 : gather_default_values (m_default_case_nonstandard
1440 : 102 : ? gimple_switch_label (swtch, 1)
1441 : 480 : : gimple_switch_default_label (swtch));
1442 : 582 : build_constructors ();
1443 : :
1444 : 582 : build_arrays (); /* Build the static arrays and assignments. */
1445 : 582 : gen_inbound_check (); /* Build the bounds check. */
1446 : :
1447 : 582 : m_cfg_altered = true;
1448 : : }
1449 : :
1450 : : /* Destructor. */
1451 : :
1452 : 25982 : switch_conversion::~switch_conversion ()
1453 : : {
1454 : 25982 : XDELETEVEC (m_constructors);
1455 : 25982 : XDELETEVEC (m_default_values);
1456 : 25982 : }
1457 : :
1458 : : /* Constructor. */
1459 : :
1460 : 10869 : group_cluster::group_cluster (vec<cluster *> &clusters,
1461 : 10869 : unsigned start, unsigned end)
1462 : : {
1463 : 10869 : gcc_checking_assert (end - start + 1 >= 1);
1464 : 10869 : m_prob = profile_probability::never ();
1465 : 10869 : m_cases.create (end - start + 1);
1466 : 104636 : for (unsigned i = start; i <= end; i++)
1467 : : {
1468 : 93767 : m_cases.quick_push (static_cast<simple_cluster *> (clusters[i]));
1469 : 93767 : m_prob += clusters[i]->m_prob;
1470 : : }
1471 : 10869 : m_subtree_prob = m_prob;
1472 : 10869 : }
1473 : :
1474 : : /* Destructor. */
1475 : :
1476 : 10869 : group_cluster::~group_cluster ()
1477 : : {
1478 : 104636 : for (unsigned i = 0; i < m_cases.length (); i++)
1479 : 93767 : delete m_cases[i];
1480 : :
1481 : 10869 : m_cases.release ();
1482 : 10869 : }
1483 : :
1484 : : /* Dump content of a cluster. */
1485 : :
1486 : : void
1487 : 23 : group_cluster::dump (FILE *f, bool details)
1488 : : {
1489 : 23 : unsigned total_values = 0;
1490 : 272 : for (unsigned i = 0; i < m_cases.length (); i++)
1491 : 226 : total_values += m_cases[i]->get_range (m_cases[i]->get_low (),
1492 : 113 : m_cases[i]->get_high ());
1493 : :
1494 : : unsigned comparison_count = 0;
1495 : 136 : for (unsigned i = 0; i < m_cases.length (); i++)
1496 : : {
1497 : 113 : simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
1498 : 171 : comparison_count += sc->get_comparison_count ();
1499 : : }
1500 : :
1501 : 23 : unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ());
1502 : 36 : fprintf (f, "%s", get_type () == JUMP_TABLE ? "JT" : "BT");
1503 : :
1504 : 23 : if (details)
1505 : 0 : fprintf (f, "(values:%d comparisons:%d range:" HOST_WIDE_INT_PRINT_DEC
1506 : : " density: %.2f%%)", total_values, comparison_count, range,
1507 : 0 : 100.0f * comparison_count / range);
1508 : :
1509 : 23 : fprintf (f, ":");
1510 : 23 : PRINT_CASE (f, get_low ());
1511 : 23 : fprintf (f, "-");
1512 : 23 : PRINT_CASE (f, get_high ());
1513 : 23 : fprintf (f, " ");
1514 : 23 : }
1515 : :
1516 : : /* Emit GIMPLE code to handle the cluster. */
1517 : :
1518 : : void
1519 : 5868 : jump_table_cluster::emit (tree index_expr, tree,
1520 : : tree default_label_expr, basic_block default_bb,
1521 : : location_t loc)
1522 : : {
1523 : 5868 : tree low = get_low ();
1524 : 5868 : unsigned HOST_WIDE_INT range = get_range (low, get_high ());
1525 : 5868 : unsigned HOST_WIDE_INT nondefault_range = 0;
1526 : 5868 : bool bitint = false;
1527 : 5868 : gimple_stmt_iterator gsi = gsi_start_bb (m_case_bb);
1528 : :
1529 : : /* For large/huge _BitInt, subtract low from index_expr, cast to unsigned
1530 : : DImode type (get_range doesn't support ranges larger than 64-bits)
1531 : : and subtract low from all case values as well. */
1532 : 5868 : if (TREE_CODE (TREE_TYPE (index_expr)) == BITINT_TYPE
1533 : 5868 : && TYPE_PRECISION (TREE_TYPE (index_expr)) > GET_MODE_PRECISION (DImode))
1534 : : {
1535 : 2 : bitint = true;
1536 : 2 : tree this_low = low, type;
1537 : 2 : gimple *g;
1538 : 2 : gimple_seq seq = NULL;
1539 : 2 : if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (index_expr)))
1540 : : {
1541 : 1 : type = unsigned_type_for (TREE_TYPE (index_expr));
1542 : 1 : index_expr = gimple_convert (&seq, type, index_expr);
1543 : 1 : this_low = fold_convert (type, this_low);
1544 : : }
1545 : 2 : this_low = const_unop (NEGATE_EXPR, TREE_TYPE (this_low), this_low);
1546 : 2 : index_expr = gimple_build (&seq, PLUS_EXPR, TREE_TYPE (index_expr),
1547 : : index_expr, this_low);
1548 : 2 : type = build_nonstandard_integer_type (GET_MODE_PRECISION (DImode), 1);
1549 : 2 : g = gimple_build_cond (GT_EXPR, index_expr,
1550 : 2 : fold_convert (TREE_TYPE (index_expr),
1551 : : TYPE_MAX_VALUE (type)),
1552 : : NULL_TREE, NULL_TREE);
1553 : 2 : gimple_seq_add_stmt (&seq, g);
1554 : 2 : gimple_seq_set_location (seq, loc);
1555 : 2 : gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
1556 : 2 : edge e1 = split_block (m_case_bb, g);
1557 : 2 : e1->flags = EDGE_FALSE_VALUE;
1558 : 2 : e1->probability = profile_probability::likely ();
1559 : 2 : edge e2 = make_edge (e1->src, default_bb, EDGE_TRUE_VALUE);
1560 : 2 : e2->probability = e1->probability.invert ();
1561 : 2 : gsi = gsi_start_bb (e1->dest);
1562 : 2 : seq = NULL;
1563 : 2 : index_expr = gimple_convert (&seq, type, index_expr);
1564 : 2 : gimple_seq_set_location (seq, loc);
1565 : 2 : gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
1566 : : }
1567 : :
1568 : : /* For jump table we just emit a new gswitch statement that will
1569 : : be latter lowered to jump table. */
1570 : 5868 : auto_vec <tree> labels;
1571 : 11736 : labels.create (m_cases.length ());
1572 : :
1573 : 5868 : basic_block case_bb = gsi_bb (gsi);
1574 : 5868 : make_edge (case_bb, default_bb, 0);
1575 : 77635 : for (unsigned i = 0; i < m_cases.length (); i++)
1576 : : {
1577 : 71767 : tree lab = unshare_expr (m_cases[i]->m_case_label_expr);
1578 : 71767 : if (bitint)
1579 : : {
1580 : 13 : CASE_LOW (lab)
1581 : 13 : = fold_convert (TREE_TYPE (index_expr),
1582 : : const_binop (MINUS_EXPR,
1583 : : TREE_TYPE (CASE_LOW (lab)),
1584 : : CASE_LOW (lab), low));
1585 : 13 : if (CASE_HIGH (lab))
1586 : 0 : CASE_HIGH (lab)
1587 : 0 : = fold_convert (TREE_TYPE (index_expr),
1588 : : const_binop (MINUS_EXPR,
1589 : : TREE_TYPE (CASE_HIGH (lab)),
1590 : : CASE_HIGH (lab), low));
1591 : : }
1592 : 71767 : labels.quick_push (lab);
1593 : 71767 : make_edge (case_bb, m_cases[i]->m_case_bb, 0);
1594 : : }
1595 : :
1596 : 5868 : gswitch *s = gimple_build_switch (index_expr,
1597 : : unshare_expr (default_label_expr), labels);
1598 : 5868 : gimple_set_location (s, loc);
1599 : 5868 : gsi_insert_after (&gsi, s, GSI_NEW_STMT);
1600 : :
1601 : : /* Set up even probabilities for all cases. */
1602 : 77635 : for (unsigned i = 0; i < m_cases.length (); i++)
1603 : : {
1604 : 71767 : simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
1605 : 71767 : edge case_edge = find_edge (case_bb, sc->m_case_bb);
1606 : 71767 : unsigned HOST_WIDE_INT case_range
1607 : 71767 : = sc->get_range (sc->get_low (), sc->get_high ());
1608 : 71767 : nondefault_range += case_range;
1609 : :
1610 : : /* case_edge->aux is number of values in a jump-table that are covered
1611 : : by the case_edge. */
1612 : 71767 : case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + case_range);
1613 : : }
1614 : :
1615 : 5868 : edge default_edge = gimple_switch_default_edge (cfun, s);
1616 : 5868 : default_edge->probability = profile_probability::never ();
1617 : :
1618 : 77635 : for (unsigned i = 0; i < m_cases.length (); i++)
1619 : : {
1620 : 71767 : simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
1621 : 71767 : edge case_edge = find_edge (case_bb, sc->m_case_bb);
1622 : 71767 : case_edge->probability
1623 : 71767 : = profile_probability::always ().apply_scale ((intptr_t)case_edge->aux,
1624 : : range);
1625 : : }
1626 : :
1627 : : /* Number of non-default values is probability of default edge. */
1628 : 5868 : default_edge->probability
1629 : 5868 : += profile_probability::always ().apply_scale (nondefault_range,
1630 : 5868 : range).invert ();
1631 : :
1632 : 5868 : switch_decision_tree::reset_out_edges_aux (s);
1633 : 5868 : }
1634 : :
1635 : : /* Find jump tables of given CLUSTERS, where all members of the vector
1636 : : are of type simple_cluster. New clusters are returned. */
1637 : :
1638 : : vec<cluster *>
1639 : 63544 : jump_table_cluster::find_jump_tables (vec<cluster *> &clusters)
1640 : : {
1641 : 63544 : if (!is_enabled ())
1642 : 15027 : return clusters.copy ();
1643 : :
1644 : 48517 : unsigned l = clusters.length ();
1645 : :
1646 : 48517 : auto_vec<min_cluster_item> min;
1647 : 48517 : min.reserve (l + 1);
1648 : :
1649 : 48517 : min.quick_push (min_cluster_item (0, 0, 0));
1650 : :
1651 : 48517 : unsigned HOST_WIDE_INT max_ratio
1652 : 48517 : = (optimize_insn_for_size_p ()
1653 : 48517 : ? param_jump_table_max_growth_ratio_for_size
1654 : 47508 : : param_jump_table_max_growth_ratio_for_speed);
1655 : :
1656 : 231294 : for (unsigned i = 1; i <= l; i++)
1657 : : {
1658 : : /* Set minimal # of clusters with i-th item to infinite. */
1659 : 182777 : min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
1660 : :
1661 : : /* Pre-calculate number of comparisons for the clusters. */
1662 : 182777 : HOST_WIDE_INT comparison_count = 0;
1663 : 6956836 : for (unsigned k = 0; k <= i - 1; k++)
1664 : : {
1665 : 6774059 : simple_cluster *sc = static_cast<simple_cluster *> (clusters[k]);
1666 : 13368167 : comparison_count += sc->get_comparison_count ();
1667 : : }
1668 : :
1669 : 6956836 : for (unsigned j = 0; j < i; j++)
1670 : : {
1671 : 6774059 : unsigned HOST_WIDE_INT s = min[j].m_non_jt_cases;
1672 : 13547772 : if (i - j < case_values_threshold ())
1673 : 471425 : s += i - j;
1674 : :
1675 : : /* Prefer clusters with smaller number of numbers covered. */
1676 : 6774059 : if ((min[j].m_count + 1 < min[i].m_count
1677 : 1860276 : || (min[j].m_count + 1 == min[i].m_count
1678 : 985 : && s < min[i].m_non_jt_cases))
1679 : 6774097 : && can_be_handled (clusters, j, i - 1, max_ratio,
1680 : : comparison_count))
1681 : 182804 : min[i] = min_cluster_item (min[j].m_count + 1, j, s);
1682 : :
1683 : 6774059 : simple_cluster *sc = static_cast<simple_cluster *> (clusters[j]);
1684 : 13368167 : comparison_count -= sc->get_comparison_count ();
1685 : : }
1686 : :
1687 : 182777 : gcc_checking_assert (comparison_count == 0);
1688 : 182777 : gcc_checking_assert (min[i].m_count != INT_MAX);
1689 : : }
1690 : :
1691 : : /* No result. */
1692 : 48517 : if (min[l].m_count == l)
1693 : 7009 : return clusters.copy ();
1694 : :
1695 : 41508 : vec<cluster *> output;
1696 : 41508 : output.create (4);
1697 : :
1698 : : /* Find and build the clusters. */
1699 : 41508 : for (unsigned int end = l;;)
1700 : : {
1701 : 45628 : int start = min[end].m_start;
1702 : :
1703 : : /* Do not allow clusters with small number of cases. */
1704 : 45628 : if (is_beneficial (clusters, start, end - 1))
1705 : 6484 : output.safe_push (new jump_table_cluster (clusters, start, end - 1));
1706 : : else
1707 : 126994 : for (int i = end - 1; i >= start; i--)
1708 : 87850 : output.safe_push (clusters[i]);
1709 : :
1710 : 45628 : end = start;
1711 : :
1712 : 45628 : if (start <= 0)
1713 : : break;
1714 : : }
1715 : :
1716 : 41508 : output.reverse ();
1717 : 41508 : return output;
1718 : 48517 : }
1719 : :
1720 : : /* Return true when cluster starting at START and ending at END (inclusive)
1721 : : can build a jump-table. */
1722 : :
1723 : : bool
1724 : 4913821 : jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
1725 : : unsigned start, unsigned end,
1726 : : unsigned HOST_WIDE_INT max_ratio,
1727 : : unsigned HOST_WIDE_INT comparison_count)
1728 : : {
1729 : : /* If the switch is relatively small such that the cost of one
1730 : : indirect jump on the target are higher than the cost of a
1731 : : decision tree, go with the decision tree.
1732 : :
1733 : : If range of values is much bigger than number of values,
1734 : : or if it is too large to represent in a HOST_WIDE_INT,
1735 : : make a sequence of conditional branches instead of a dispatch.
1736 : :
1737 : : The definition of "much bigger" depends on whether we are
1738 : : optimizing for size or for speed.
1739 : :
1740 : : For algorithm correctness, jump table for a single case must return
1741 : : true. We bail out in is_beneficial if it's called just for
1742 : : a single case. */
1743 : 4913821 : if (start == end)
1744 : : return true;
1745 : :
1746 : 9697202 : unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
1747 : 4848601 : clusters[end]->get_high ());
1748 : : /* Check overflow. */
1749 : 4848601 : if (range == 0)
1750 : : return false;
1751 : :
1752 : 4845346 : if (range > HOST_WIDE_INT_M1U / 100)
1753 : : return false;
1754 : :
1755 : 635213 : unsigned HOST_WIDE_INT lhs = 100 * range;
1756 : 635213 : if (lhs < range)
1757 : : return false;
1758 : :
1759 : 635213 : return lhs <= max_ratio * comparison_count;
1760 : : }
1761 : :
1762 : : /* Return true if cluster starting at START and ending at END (inclusive)
1763 : : is profitable transformation. */
1764 : :
1765 : : bool
1766 : 45628 : jump_table_cluster::is_beneficial (const vec<cluster *> &,
1767 : : unsigned start, unsigned end)
1768 : : {
1769 : : /* Single case bail out. */
1770 : 45628 : if (start == end)
1771 : : return false;
1772 : :
1773 : 84322 : return end - start + 1 >= case_values_threshold ();
1774 : : }
1775 : :
1776 : : /* Find bit tests of given CLUSTERS, where all members of the vector are of
1777 : : type simple_cluster. Use a fast algorithm that might not find the optimal
1778 : : solution (minimal number of clusters on the output). New clusters are
1779 : : returned.
1780 : :
1781 : : You should call find_bit_tests () instead of calling this function
1782 : : directly. */
1783 : :
1784 : : vec<cluster *>
1785 : 1 : bit_test_cluster::find_bit_tests_fast (vec<cluster *> &clusters)
1786 : : {
1787 : 1 : unsigned l = clusters.length ();
1788 : 1 : vec<cluster *> output;
1789 : :
1790 : 1 : output.create (l);
1791 : :
1792 : : /* Look at sliding BITS_PER_WORD sized windows in the switch value space
1793 : : and determine if they are suitable for a bit test cluster. Worst case
1794 : : this can examine every value BITS_PER_WORD-1 times. */
1795 : 1 : unsigned k;
1796 : 3 : for (unsigned i = 0; i < l; i += k)
1797 : : {
1798 : 2 : hash_set<basic_block> targets;
1799 : 2 : cluster *start_cluster = clusters[i];
1800 : :
1801 : : /* Find the biggest k such that clusters i to i+k-1 can be turned into a
1802 : : one big bit test cluster. */
1803 : 2 : k = 0;
1804 : 5 : while (i + k < l)
1805 : : {
1806 : 3 : cluster *end_cluster = clusters[i + k];
1807 : :
1808 : : /* Does value range fit into the BITS_PER_WORD window? */
1809 : 3 : HOST_WIDE_INT w = cluster::get_range (start_cluster->get_low (),
1810 : 3 : end_cluster->get_high ());
1811 : 3 : if (w == 0 || w > BITS_PER_WORD)
1812 : : break;
1813 : :
1814 : : /* Check for max # of targets. */
1815 : 3 : if (targets.elements () == m_max_case_bit_tests
1816 : 3 : && !targets.contains (end_cluster->m_case_bb))
1817 : : break;
1818 : :
1819 : 3 : targets.add (end_cluster->m_case_bb);
1820 : 3 : k++;
1821 : : }
1822 : :
1823 : 2 : if (is_beneficial (k, targets.elements ()))
1824 : : {
1825 : 0 : output.safe_push (new bit_test_cluster (clusters, i, i + k - 1,
1826 : 0 : i == 0 && k == l));
1827 : : }
1828 : : else
1829 : : {
1830 : 2 : output.safe_push (clusters[i]);
1831 : : /* ??? Might be able to skip more. */
1832 : 2 : k = 1;
1833 : : }
1834 : 2 : }
1835 : :
1836 : 1 : return output;
1837 : : }
1838 : :
1839 : : /* Find bit tests of given CLUSTERS, where all members of the vector
1840 : : are of type simple_cluster. Use a slow (quadratic) algorithm that always
1841 : : finds the optimal solution (minimal number of clusters on the output). New
1842 : : clusters are returned.
1843 : :
1844 : : You should call find_bit_tests () instead of calling this function
1845 : : directly. */
1846 : :
1847 : : vec<cluster *>
1848 : 31381 : bit_test_cluster::find_bit_tests_slow (vec<cluster *> &clusters)
1849 : : {
1850 : 31381 : unsigned l = clusters.length ();
1851 : 31381 : auto_vec<min_cluster_item> min;
1852 : 31381 : min.reserve (l + 1);
1853 : :
1854 : 31381 : min.quick_push (min_cluster_item (0, 0, 0));
1855 : :
1856 : 146366 : for (unsigned i = 1; i <= l; i++)
1857 : : {
1858 : : /* Set minimal # of clusters with i-th item to infinite. */
1859 : 114985 : min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
1860 : :
1861 : 907236 : for (unsigned j = 0; j < i; j++)
1862 : : {
1863 : 792251 : if (min[j].m_count + 1 < min[i].m_count
1864 : 792251 : && can_be_handled (clusters, j, i - 1))
1865 : 114985 : min[i] = min_cluster_item (min[j].m_count + 1, j, INT_MAX);
1866 : : }
1867 : :
1868 : 114985 : gcc_checking_assert (min[i].m_count != INT_MAX);
1869 : : }
1870 : :
1871 : : /* No result. */
1872 : 31381 : if (min[l].m_count == l)
1873 : 4404 : return clusters.copy ();
1874 : :
1875 : 26977 : vec<cluster *> output;
1876 : 26977 : output.create (4);
1877 : :
1878 : : /* Find and build the clusters. */
1879 : 26977 : for (unsigned end = l;;)
1880 : : {
1881 : 42109 : int start = min[end].m_start;
1882 : :
1883 : 42109 : if (is_beneficial (clusters, start, end - 1))
1884 : : {
1885 : 7710 : bool entire = start == 0 && end == clusters.length ();
1886 : 4385 : output.safe_push (new bit_test_cluster (clusters, start, end - 1,
1887 : 4385 : entire));
1888 : : }
1889 : : else
1890 : 126370 : for (int i = end - 1; i >= start; i--)
1891 : 88646 : output.safe_push (clusters[i]);
1892 : :
1893 : 42109 : end = start;
1894 : :
1895 : 42109 : if (start <= 0)
1896 : : break;
1897 : : }
1898 : :
1899 : 26977 : output.reverse ();
1900 : 26977 : return output;
1901 : 31381 : }
1902 : :
1903 : : /* Find bit tests of given CLUSTERS, where all members of the vector
1904 : : are of type simple_cluster. MAX_C is the approx max number of cases per
1905 : : label. New clusters are returned. */
1906 : :
1907 : : vec<cluster *>
1908 : 64926 : bit_test_cluster::find_bit_tests (vec<cluster *> &clusters, int max_c)
1909 : : {
1910 : 64926 : if (!is_enabled () || max_c == 1)
1911 : 33544 : return clusters.copy ();
1912 : :
1913 : 31382 : unsigned l = clusters.length ();
1914 : :
1915 : : /* Note: l + 1 is the number of cases of the switch. */
1916 : 31382 : if (l + 1 > (unsigned) param_switch_lower_slow_alg_max_cases)
1917 : 1 : return find_bit_tests_fast (clusters);
1918 : : else
1919 : 31381 : return find_bit_tests_slow (clusters);
1920 : : }
1921 : :
1922 : : /* Return true when RANGE of case values with UNIQ labels
1923 : : can build a bit test. */
1924 : :
1925 : : bool
1926 : 632909 : bit_test_cluster::can_be_handled (unsigned HOST_WIDE_INT range,
1927 : : unsigned int uniq)
1928 : : {
1929 : : /* Check overflow. */
1930 : 632909 : if (range == 0)
1931 : : return false;
1932 : :
1933 : 1261830 : if (range >= GET_MODE_BITSIZE (word_mode))
1934 : : return false;
1935 : :
1936 : 515121 : return uniq <= m_max_case_bit_tests;
1937 : : }
1938 : :
1939 : : /* Return true when cluster starting at START and ending at END (inclusive)
1940 : : can build a bit test. */
1941 : :
1942 : : bool
1943 : 645360 : bit_test_cluster::can_be_handled (const vec<cluster *> &clusters,
1944 : : unsigned start, unsigned end)
1945 : : {
1946 : 645360 : auto_vec<int, m_max_case_bit_tests> dest_bbs;
1947 : : /* For algorithm correctness, bit test for a single case must return
1948 : : true. We bail out in is_beneficial if it's called just for
1949 : : a single case. */
1950 : 645360 : if (start == end)
1951 : : return true;
1952 : :
1953 : 1213994 : unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
1954 : 606997 : clusters[end]->get_high ());
1955 : :
1956 : : /* Make a guess first. */
1957 : 606997 : if (!can_be_handled (range, m_max_case_bit_tests))
1958 : : return false;
1959 : :
1960 : 2043650 : for (unsigned i = start; i <= end; i++)
1961 : : {
1962 : 1967028 : simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
1963 : : /* m_max_case_bit_tests is very small integer, thus the operation
1964 : : is constant. */
1965 : 1967028 : if (!dest_bbs.contains (sc->m_case_bb->index))
1966 : : {
1967 : 1840667 : if (dest_bbs.length () >= m_max_case_bit_tests)
1968 : : return false;
1969 : 1425168 : dest_bbs.quick_push (sc->m_case_bb->index);
1970 : : }
1971 : : }
1972 : :
1973 : : return true;
1974 : 645360 : }
1975 : :
1976 : : /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test
1977 : : transformation. */
1978 : :
1979 : : bool
1980 : 50775 : bit_test_cluster::is_beneficial (unsigned count, unsigned uniq)
1981 : : {
1982 : 50775 : return (((uniq == 1 && count >= 3)
1983 : 45301 : || (uniq == 2 && count >= 5)
1984 : 95668 : || (uniq == 3 && count >= 6)));
1985 : : }
1986 : :
1987 : : /* Return true if cluster starting at START and ending at END (inclusive)
1988 : : is profitable transformation. */
1989 : :
1990 : : bool
1991 : 42109 : bit_test_cluster::is_beneficial (const vec<cluster *> &clusters,
1992 : : unsigned start, unsigned end)
1993 : : {
1994 : : /* Single case bail out. */
1995 : 42109 : if (start == end)
1996 : : return false;
1997 : :
1998 : 37333 : auto_bitmap dest_bbs;
1999 : :
2000 : 138734 : for (unsigned i = start; i <= end; i++)
2001 : : {
2002 : 101401 : simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
2003 : 101401 : bitmap_set_bit (dest_bbs, sc->m_case_bb->index);
2004 : : }
2005 : :
2006 : 37333 : unsigned uniq = bitmap_count_bits (dest_bbs);
2007 : 37333 : unsigned count = end - start + 1;
2008 : 37333 : return is_beneficial (count, uniq);
2009 : 37333 : }
2010 : :
2011 : : /* Comparison function for qsort to order bit tests by decreasing
2012 : : probability of execution. */
2013 : :
2014 : : int
2015 : 7782 : case_bit_test::cmp (const void *p1, const void *p2)
2016 : : {
2017 : 7782 : const case_bit_test *const d1 = (const case_bit_test *) p1;
2018 : 7782 : const case_bit_test *const d2 = (const case_bit_test *) p2;
2019 : :
2020 : 7782 : if (d2->bits != d1->bits)
2021 : 6603 : return d2->bits - d1->bits;
2022 : :
2023 : : /* Stabilize the sort. */
2024 : 1179 : return (LABEL_DECL_UID (CASE_LABEL (d2->label))
2025 : 1179 : - LABEL_DECL_UID (CASE_LABEL (d1->label)));
2026 : : }
2027 : :
2028 : : /* Expand a switch statement by a short sequence of bit-wise
2029 : : comparisons. "switch(x)" is effectively converted into
2030 : : "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
2031 : : integer constants.
2032 : :
2033 : : INDEX_EXPR is the value being switched on.
2034 : :
2035 : : MINVAL is the lowest case value of in the case nodes,
2036 : : and RANGE is highest value minus MINVAL. MINVAL and RANGE
2037 : : are not guaranteed to be of the same type as INDEX_EXPR
2038 : : (the gimplifier doesn't change the type of case label values,
2039 : : and MINVAL and RANGE are derived from those values).
2040 : : MAXVAL is MINVAL + RANGE.
2041 : :
2042 : : There *MUST* be max_case_bit_tests or less unique case
2043 : : node targets. */
2044 : :
2045 : : void
2046 : 3579 : bit_test_cluster::emit (tree index_expr, tree index_type,
2047 : : tree, basic_block default_bb, location_t loc)
2048 : : {
2049 : 21474 : case_bit_test test[m_max_case_bit_tests] = { {} };
2050 : 3579 : unsigned int i, j, k;
2051 : 3579 : unsigned int count;
2052 : :
2053 : 3579 : tree unsigned_index_type = range_check_type (index_type);
2054 : :
2055 : 3579 : gimple_stmt_iterator gsi;
2056 : 3579 : gassign *shift_stmt;
2057 : :
2058 : 3579 : tree idx, tmp, csui;
2059 : 3579 : tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
2060 : 3579 : tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
2061 : 3579 : tree word_mode_one = fold_convert (word_type_node, integer_one_node);
2062 : 3579 : int prec = TYPE_PRECISION (word_type_node);
2063 : 3579 : wide_int wone = wi::one (prec);
2064 : :
2065 : 3579 : tree minval = get_low ();
2066 : 3579 : tree maxval = get_high ();
2067 : :
2068 : : /* Go through all case labels, and collect the case labels, profile
2069 : : counts, and other information we need to build the branch tests. */
2070 : 3579 : count = 0;
2071 : 18639 : for (i = 0; i < m_cases.length (); i++)
2072 : : {
2073 : 15060 : unsigned int lo, hi;
2074 : 15060 : simple_cluster *n = static_cast<simple_cluster *> (m_cases[i]);
2075 : 19346 : for (k = 0; k < count; k++)
2076 : 14285 : if (n->m_case_bb == test[k].target_bb)
2077 : : break;
2078 : :
2079 : 15060 : if (k == count)
2080 : : {
2081 : 5061 : gcc_checking_assert (count < m_max_case_bit_tests);
2082 : 5061 : test[k].mask = wi::zero (prec);
2083 : 5061 : test[k].target_bb = n->m_case_bb;
2084 : 5061 : test[k].label = n->m_case_label_expr;
2085 : 5061 : test[k].bits = 0;
2086 : 5061 : test[k].prob = profile_probability::never ();
2087 : 5061 : count++;
2088 : : }
2089 : :
2090 : 15060 : test[k].bits += n->get_range (n->get_low (), n->get_high ());
2091 : 15060 : test[k].prob += n->m_prob;
2092 : :
2093 : 15060 : lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval));
2094 : 15060 : if (n->get_high () == NULL_TREE)
2095 : : hi = lo;
2096 : : else
2097 : 15060 : hi = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_high (),
2098 : : minval));
2099 : :
2100 : 35747 : for (j = lo; j <= hi; j++)
2101 : 20687 : test[k].mask |= wi::lshift (wone, j);
2102 : : }
2103 : :
2104 : 3579 : qsort (test, count, sizeof (*test), case_bit_test::cmp);
2105 : :
2106 : : /* If every possible relative value of the index expression is a valid shift
2107 : : amount, then we can merge the entry test in the bit test. */
2108 : 3579 : bool entry_test_needed;
2109 : 3579 : int_range_max r;
2110 : 7158 : if (TREE_CODE (index_expr) == SSA_NAME
2111 : 7158 : && get_range_query (cfun)->range_of_expr (r, index_expr)
2112 : 3579 : && !r.undefined_p ()
2113 : 3578 : && !r.varying_p ()
2114 : 8805 : && wi::leu_p (r.upper_bound () - r.lower_bound (), prec - 1))
2115 : : {
2116 : 57 : wide_int min = r.lower_bound ();
2117 : 57 : wide_int max = r.upper_bound ();
2118 : 57 : tree index_type = TREE_TYPE (index_expr);
2119 : 57 : minval = fold_convert (index_type, minval);
2120 : 57 : wide_int iminval = wi::to_wide (minval);
2121 : 57 : if (wi::lt_p (min, iminval, TYPE_SIGN (index_type)))
2122 : : {
2123 : 52 : minval = wide_int_to_tree (index_type, min);
2124 : 163 : for (i = 0; i < count; i++)
2125 : 111 : test[i].mask = wi::lshift (test[i].mask, iminval - min);
2126 : : }
2127 : 5 : else if (wi::gt_p (min, iminval, TYPE_SIGN (index_type)))
2128 : : {
2129 : 0 : minval = wide_int_to_tree (index_type, min);
2130 : 0 : for (i = 0; i < count; i++)
2131 : 0 : test[i].mask = wi::lrshift (test[i].mask, min - iminval);
2132 : : }
2133 : 57 : maxval = wide_int_to_tree (index_type, max);
2134 : 57 : entry_test_needed = false;
2135 : 57 : }
2136 : : else
2137 : : entry_test_needed = true;
2138 : :
2139 : : /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
2140 : : the minval subtractions, but it might make the mask constants more
2141 : : expensive. So, compare the costs. */
2142 : 3579 : if (compare_tree_int (minval, 0) > 0 && compare_tree_int (maxval, prec) < 0)
2143 : : {
2144 : 2087 : int cost_diff;
2145 : 2087 : HOST_WIDE_INT m = tree_to_uhwi (minval);
2146 : 2087 : rtx reg = gen_raw_REG (word_mode, 10000);
2147 : 2087 : bool speed_p = optimize_insn_for_speed_p ();
2148 : 2087 : cost_diff = set_src_cost (gen_rtx_PLUS (word_mode, reg,
2149 : : GEN_INT (-m)),
2150 : : word_mode, speed_p);
2151 : 4481 : for (i = 0; i < count; i++)
2152 : : {
2153 : 2394 : rtx r = immed_wide_int_const (test[i].mask, word_mode);
2154 : 2394 : cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r),
2155 : : word_mode, speed_p);
2156 : 2394 : r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode);
2157 : 2394 : cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r),
2158 : : word_mode, speed_p);
2159 : : }
2160 : 2087 : if (cost_diff > 0)
2161 : : {
2162 : 4127 : for (i = 0; i < count; i++)
2163 : 2183 : test[i].mask = wi::lshift (test[i].mask, m);
2164 : 1944 : minval = build_zero_cst (TREE_TYPE (minval));
2165 : : }
2166 : : }
2167 : :
2168 : : /* Now build the test-and-branch code. */
2169 : :
2170 : 3579 : gsi = gsi_last_bb (m_case_bb);
2171 : :
2172 : : /* idx = (unsigned)x - minval. */
2173 : 3579 : idx = fold_convert_loc (loc, unsigned_index_type, index_expr);
2174 : 3579 : idx = fold_build2_loc (loc, MINUS_EXPR, unsigned_index_type, idx,
2175 : : fold_convert_loc (loc, unsigned_index_type, minval));
2176 : 3579 : idx = force_gimple_operand_gsi (&gsi, idx,
2177 : : /*simple=*/true, NULL_TREE,
2178 : : /*before=*/true, GSI_SAME_STMT);
2179 : :
2180 : 3579 : profile_probability subtree_prob = m_subtree_prob;
2181 : 3579 : profile_probability default_prob = m_default_prob;
2182 : 3579 : if (!default_prob.initialized_p ())
2183 : 2342 : default_prob = m_subtree_prob.invert ();
2184 : :
2185 : 3579 : if (m_handles_entire_switch && entry_test_needed)
2186 : : {
2187 : 2301 : tree range = int_const_binop (MINUS_EXPR, maxval, minval);
2188 : : /* if (idx > range) goto default */
2189 : 2301 : range
2190 : 2301 : = force_gimple_operand_gsi (&gsi,
2191 : : fold_convert (unsigned_index_type, range),
2192 : : /*simple=*/true, NULL_TREE,
2193 : : /*before=*/true, GSI_SAME_STMT);
2194 : 2301 : tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
2195 : 2301 : default_prob = default_prob / 2;
2196 : 2301 : basic_block new_bb
2197 : 2301 : = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb,
2198 : : default_prob, loc);
2199 : 4602 : gsi = gsi_last_bb (new_bb);
2200 : : }
2201 : :
2202 : 3579 : tmp = fold_build2_loc (loc, LSHIFT_EXPR, word_type_node, word_mode_one,
2203 : : fold_convert_loc (loc, word_type_node, idx));
2204 : :
2205 : : /* csui = (1 << (word_mode) idx) */
2206 : 3579 : if (count > 1)
2207 : : {
2208 : 864 : csui = make_ssa_name (word_type_node);
2209 : 864 : tmp = force_gimple_operand_gsi (&gsi, tmp,
2210 : : /*simple=*/false, NULL_TREE,
2211 : : /*before=*/true, GSI_SAME_STMT);
2212 : 864 : shift_stmt = gimple_build_assign (csui, tmp);
2213 : 864 : gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
2214 : 864 : update_stmt (shift_stmt);
2215 : : }
2216 : : else
2217 : : csui = tmp;
2218 : :
2219 : : /* for each unique set of cases:
2220 : : if (const & csui) goto target */
2221 : 8640 : for (k = 0; k < count; k++)
2222 : : {
2223 : 5061 : profile_probability prob = test[k].prob / (subtree_prob + default_prob);
2224 : 5061 : subtree_prob -= test[k].prob;
2225 : 5061 : tmp = wide_int_to_tree (word_type_node, test[k].mask);
2226 : 5061 : tmp = fold_build2_loc (loc, BIT_AND_EXPR, word_type_node, csui, tmp);
2227 : 5061 : tmp = fold_build2_loc (loc, NE_EXPR, boolean_type_node,
2228 : : tmp, word_mode_zero);
2229 : 5061 : tmp = force_gimple_operand_gsi (&gsi, tmp,
2230 : : /*simple=*/true, NULL_TREE,
2231 : : /*before=*/true, GSI_SAME_STMT);
2232 : 5061 : basic_block new_bb
2233 : 5061 : = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_bb,
2234 : : prob, loc);
2235 : 10122 : gsi = gsi_last_bb (new_bb);
2236 : : }
2237 : :
2238 : : /* We should have removed all edges now. */
2239 : 3579 : gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
2240 : :
2241 : : /* If nothing matched, go to the default label. */
2242 : 3579 : edge e = make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU);
2243 : 3579 : e->probability = profile_probability::always ();
2244 : 14316 : }
2245 : :
2246 : : /* Split the basic block at the statement pointed to by GSIP, and insert
2247 : : a branch to the target basic block of E_TRUE conditional on tree
2248 : : expression COND.
2249 : :
2250 : : It is assumed that there is already an edge from the to-be-split
2251 : : basic block to E_TRUE->dest block. This edge is removed, and the
2252 : : profile information on the edge is re-used for the new conditional
2253 : : jump.
2254 : :
2255 : : The CFG is updated. The dominator tree will not be valid after
2256 : : this transformation, but the immediate dominators are updated if
2257 : : UPDATE_DOMINATORS is true.
2258 : :
2259 : : Returns the newly created basic block. */
2260 : :
2261 : : basic_block
2262 : 7362 : bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
2263 : : tree cond, basic_block case_bb,
2264 : : profile_probability prob,
2265 : : location_t loc)
2266 : : {
2267 : 7362 : tree tmp;
2268 : 7362 : gcond *cond_stmt;
2269 : 7362 : edge e_false;
2270 : 7362 : basic_block new_bb, split_bb = gsi_bb (*gsip);
2271 : :
2272 : 7362 : edge e_true = make_edge (split_bb, case_bb, EDGE_TRUE_VALUE);
2273 : 7362 : e_true->probability = prob;
2274 : 7362 : gcc_assert (e_true->src == split_bb);
2275 : :
2276 : 7362 : tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
2277 : : /*before=*/true, GSI_SAME_STMT);
2278 : 7362 : cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
2279 : 7362 : gimple_set_location (cond_stmt, loc);
2280 : 7362 : gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
2281 : :
2282 : 7362 : e_false = split_block (split_bb, cond_stmt);
2283 : 7362 : new_bb = e_false->dest;
2284 : 7362 : redirect_edge_pred (e_true, split_bb);
2285 : :
2286 : 7362 : e_false->flags &= ~EDGE_FALLTHRU;
2287 : 7362 : e_false->flags |= EDGE_FALSE_VALUE;
2288 : 7362 : e_false->probability = e_true->probability.invert ();
2289 : 7362 : new_bb->count = e_false->count ();
2290 : :
2291 : 7362 : return new_bb;
2292 : : }
2293 : :
2294 : : /* Compute the number of case labels that correspond to each outgoing edge of
2295 : : switch statement. Record this information in the aux field of the edge.
2296 : : Return the approx max number of cases per edge. */
2297 : :
2298 : : int
2299 : 42402 : switch_decision_tree::compute_cases_per_edge ()
2300 : : {
2301 : 42402 : int max_c = 0;
2302 : 42402 : reset_out_edges_aux (m_switch);
2303 : 42402 : int ncases = gimple_switch_num_labels (m_switch);
2304 : 283179 : for (int i = ncases - 1; i >= 1; --i)
2305 : : {
2306 : 240777 : edge case_edge = gimple_switch_edge (cfun, m_switch, i);
2307 : 240777 : case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1);
2308 : : /* For a range case add one extra. That's enough for the bit
2309 : : cluster heuristic. */
2310 : 240777 : if ((intptr_t)case_edge->aux > max_c)
2311 : 134264 : max_c = (intptr_t)case_edge->aux +
2312 : 67132 : !!CASE_HIGH (gimple_switch_label (m_switch, i));
2313 : : }
2314 : 42402 : return max_c;
2315 : : }
2316 : :
2317 : : /* Analyze switch statement and return true when the statement is expanded
2318 : : as decision tree. */
2319 : :
2320 : : bool
2321 : 42402 : switch_decision_tree::analyze_switch_statement ()
2322 : : {
2323 : 42402 : unsigned l = gimple_switch_num_labels (m_switch);
2324 : 42402 : basic_block bb = gimple_bb (m_switch);
2325 : 42402 : auto_vec<cluster *> clusters;
2326 : 42402 : clusters.create (l - 1);
2327 : :
2328 : 42402 : basic_block default_bb = gimple_switch_default_bb (cfun, m_switch);
2329 : 42402 : m_case_bbs.reserve (l);
2330 : 42402 : m_case_bbs.quick_push (default_bb);
2331 : :
2332 : 42402 : int max_c = compute_cases_per_edge ();
2333 : :
2334 : 283179 : for (unsigned i = 1; i < l; i++)
2335 : : {
2336 : 240777 : tree elt = gimple_switch_label (m_switch, i);
2337 : 240777 : tree lab = CASE_LABEL (elt);
2338 : 240777 : basic_block case_bb = label_to_block (cfun, lab);
2339 : 240777 : edge case_edge = find_edge (bb, case_bb);
2340 : 240777 : tree low = CASE_LOW (elt);
2341 : 240777 : tree high = CASE_HIGH (elt);
2342 : :
2343 : 240777 : profile_probability p
2344 : 240777 : = case_edge->probability / ((intptr_t) (case_edge->aux));
2345 : 240777 : clusters.quick_push (new simple_cluster (low, high, elt, case_edge->dest,
2346 : 240777 : p));
2347 : 240777 : m_case_bbs.quick_push (case_edge->dest);
2348 : : }
2349 : :
2350 : 42402 : reset_out_edges_aux (m_switch);
2351 : :
2352 : 42402 : if (l > (unsigned) param_switch_lower_slow_alg_max_cases)
2353 : 6 : warning_at (gimple_location (m_switch), OPT_Wdisabled_optimization,
2354 : : "Using faster switch lowering algorithms. "
2355 : : "Number of switch cases (%d) exceeds "
2356 : : "%<--param=switch-lower-slow-alg-max-cases=%d%> limit.",
2357 : : l, param_switch_lower_slow_alg_max_cases);
2358 : :
2359 : : /* Find bit-test clusters. */
2360 : 42402 : vec<cluster *> output = bit_test_cluster::find_bit_tests (clusters, max_c);
2361 : :
2362 : : /* Find jump table clusters. We are looking for these in the sequences of
2363 : : simple clusters which we didn't manage to convert into bit-test
2364 : : clusters. */
2365 : 42402 : vec<cluster *> output2;
2366 : 42402 : auto_vec<cluster *> tmp;
2367 : 42402 : output2.create (1);
2368 : 42402 : tmp.create (1);
2369 : :
2370 : 271698 : for (unsigned i = 0; i < output.length (); i++)
2371 : : {
2372 : 229296 : cluster *c = output[i];
2373 : 229296 : if (c->get_type () != SIMPLE_CASE)
2374 : : {
2375 : 3579 : if (!tmp.is_empty ())
2376 : : {
2377 : 929 : vec<cluster *> n = jump_table_cluster::find_jump_tables (tmp);
2378 : 929 : output2.safe_splice (n);
2379 : 929 : n.release ();
2380 : 929 : tmp.truncate (0);
2381 : : }
2382 : 3579 : output2.safe_push (c);
2383 : : }
2384 : : else
2385 : 225717 : tmp.safe_push (c);
2386 : : }
2387 : :
2388 : : /* We still can have a temporary vector to test. */
2389 : 42402 : if (!tmp.is_empty ())
2390 : : {
2391 : 39481 : vec<cluster *> n = jump_table_cluster::find_jump_tables (tmp);
2392 : 39481 : output2.safe_splice (n);
2393 : 39481 : n.release ();
2394 : : }
2395 : :
2396 : 42402 : if (dump_file)
2397 : : {
2398 : 21 : fprintf (dump_file, ";; GIMPLE switch case clusters: ");
2399 : 103 : for (unsigned i = 0; i < output2.length (); i++)
2400 : 82 : output2[i]->dump (dump_file, dump_flags & TDF_DETAILS);
2401 : 21 : fprintf (dump_file, "\n");
2402 : : }
2403 : :
2404 : 42402 : output.release ();
2405 : :
2406 : 42402 : bool expanded = try_switch_expansion (output2);
2407 : 42402 : release_clusters (output2);
2408 : 42402 : return expanded;
2409 : 42402 : }
2410 : :
2411 : : /* Attempt to expand CLUSTERS as a decision tree. Return true when
2412 : : expanded. */
2413 : :
2414 : : bool
2415 : 42402 : switch_decision_tree::try_switch_expansion (vec<cluster *> &clusters)
2416 : : {
2417 : 42402 : tree index_expr = gimple_switch_index (m_switch);
2418 : 42402 : tree index_type = TREE_TYPE (index_expr);
2419 : 42402 : basic_block bb = gimple_bb (m_switch);
2420 : :
2421 : 42402 : if (gimple_switch_num_labels (m_switch) == 1
2422 : 42402 : || range_check_type (index_type) == NULL_TREE)
2423 : 0 : return false;
2424 : :
2425 : : /* Find the default case target label. */
2426 : 42402 : edge default_edge = gimple_switch_default_edge (cfun, m_switch);
2427 : 42402 : m_default_bb = default_edge->dest;
2428 : :
2429 : : /* Do the insertion of a case label into m_case_list. The labels are
2430 : : fed to us in descending order from the sorted vector of case labels used
2431 : : in the tree part of the middle end. So the list we construct is
2432 : : sorted in ascending order. */
2433 : :
2434 : 248201 : for (int i = clusters.length () - 1; i >= 0; i--)
2435 : : {
2436 : 163397 : case_tree_node *r = m_case_list;
2437 : 163397 : m_case_list = m_case_node_pool.allocate ();
2438 : 163397 : m_case_list->m_right = r;
2439 : 163397 : m_case_list->m_c = clusters[i];
2440 : : }
2441 : :
2442 : 42402 : record_phi_operand_mapping ();
2443 : :
2444 : : /* Split basic block that contains the gswitch statement. */
2445 : 42402 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
2446 : 42402 : edge e;
2447 : 42402 : if (gsi_end_p (gsi))
2448 : 0 : e = split_block_after_labels (bb);
2449 : : else
2450 : : {
2451 : 42402 : gsi_prev (&gsi);
2452 : 42402 : e = split_block (bb, gsi_stmt (gsi));
2453 : : }
2454 : 42402 : bb = split_edge (e);
2455 : :
2456 : : /* Create new basic blocks for non-case clusters where specific expansion
2457 : : needs to happen. */
2458 : 205799 : for (unsigned i = 0; i < clusters.length (); i++)
2459 : 163397 : if (clusters[i]->get_type () != SIMPLE_CASE)
2460 : : {
2461 : 9447 : clusters[i]->m_case_bb = create_empty_bb (bb);
2462 : 9447 : clusters[i]->m_case_bb->count = bb->count;
2463 : 9447 : clusters[i]->m_case_bb->loop_father = bb->loop_father;
2464 : : }
2465 : :
2466 : : /* Do not do an extra work for a single cluster. */
2467 : 42402 : if (clusters.length () == 1
2468 : 50906 : && clusters[0]->get_type () != SIMPLE_CASE)
2469 : : {
2470 : 7475 : cluster *c = clusters[0];
2471 : 7475 : c->emit (index_expr, index_type,
2472 : : gimple_switch_default_label (m_switch), m_default_bb,
2473 : 7475 : gimple_location (m_switch));
2474 : 7475 : redirect_edge_succ (single_succ_edge (bb), c->m_case_bb);
2475 : : }
2476 : : else
2477 : : {
2478 : 34927 : emit (bb, index_expr, default_edge->probability, index_type);
2479 : :
2480 : : /* Emit cluster-specific switch handling. */
2481 : 190849 : for (unsigned i = 0; i < clusters.length (); i++)
2482 : 155922 : if (clusters[i]->get_type () != SIMPLE_CASE)
2483 : : {
2484 : 1972 : edge e = single_pred_edge (clusters[i]->m_case_bb);
2485 : 1972 : e->dest->count = e->src->count.apply_probability (e->probability);
2486 : 3944 : clusters[i]->emit (index_expr, index_type,
2487 : : gimple_switch_default_label (m_switch),
2488 : 1972 : m_default_bb, gimple_location (m_switch));
2489 : : }
2490 : : }
2491 : :
2492 : 42402 : fix_phi_operands_for_edges ();
2493 : :
2494 : 42402 : return true;
2495 : : }
2496 : :
2497 : : /* Before switch transformation, record all SSA_NAMEs defined in switch BB
2498 : : and used in a label basic block. */
2499 : :
2500 : : void
2501 : 42402 : switch_decision_tree::record_phi_operand_mapping ()
2502 : : {
2503 : 42402 : basic_block switch_bb = gimple_bb (m_switch);
2504 : : /* Record all PHI nodes that have to be fixed after conversion. */
2505 : 325581 : for (unsigned i = 0; i < m_case_bbs.length (); i++)
2506 : : {
2507 : 283179 : gphi_iterator gsi;
2508 : 283179 : basic_block bb = m_case_bbs[i];
2509 : 336420 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2510 : : {
2511 : 53241 : gphi *phi = gsi.phi ();
2512 : :
2513 : 175126 : for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
2514 : : {
2515 : 175126 : basic_block phi_src_bb = gimple_phi_arg_edge (phi, i)->src;
2516 : 175126 : if (phi_src_bb == switch_bb)
2517 : : {
2518 : 53241 : tree def = gimple_phi_arg_def (phi, i);
2519 : 53241 : tree result = gimple_phi_result (phi);
2520 : 53241 : m_phi_mapping.put (result, def);
2521 : 53241 : break;
2522 : : }
2523 : : }
2524 : : }
2525 : : }
2526 : 42402 : }
2527 : :
2528 : : /* Append new operands to PHI statements that were introduced due to
2529 : : addition of new edges to case labels. */
2530 : :
2531 : : void
2532 : 42402 : switch_decision_tree::fix_phi_operands_for_edges ()
2533 : : {
2534 : 42402 : gphi_iterator gsi;
2535 : :
2536 : 325581 : for (unsigned i = 0; i < m_case_bbs.length (); i++)
2537 : : {
2538 : 283179 : basic_block bb = m_case_bbs[i];
2539 : 336420 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2540 : : {
2541 : 53241 : gphi *phi = gsi.phi ();
2542 : 426037 : for (unsigned j = 0; j < gimple_phi_num_args (phi); j++)
2543 : : {
2544 : 372796 : tree def = gimple_phi_arg_def (phi, j);
2545 : 372796 : if (def == NULL_TREE)
2546 : : {
2547 : 55415 : edge e = gimple_phi_arg_edge (phi, j);
2548 : 55415 : tree *definition
2549 : 55415 : = m_phi_mapping.get (gimple_phi_result (phi));
2550 : 55415 : gcc_assert (definition);
2551 : 55415 : add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
2552 : : }
2553 : : }
2554 : : }
2555 : : }
2556 : 42402 : }
2557 : :
2558 : : /* Generate a decision tree, switching on INDEX_EXPR and jumping to
2559 : : one of the labels in CASE_LIST or to the DEFAULT_LABEL.
2560 : :
2561 : : We generate a binary decision tree to select the appropriate target
2562 : : code. */
2563 : :
2564 : : void
2565 : 34927 : switch_decision_tree::emit (basic_block bb, tree index_expr,
2566 : : profile_probability default_prob, tree index_type)
2567 : : {
2568 : 34927 : balance_case_nodes (&m_case_list, NULL);
2569 : :
2570 : 34927 : if (dump_file)
2571 : 15 : dump_function_to_file (current_function_decl, dump_file, dump_flags);
2572 : 34927 : if (dump_file && (dump_flags & TDF_DETAILS))
2573 : : {
2574 : 0 : int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
2575 : 0 : fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
2576 : 0 : gcc_assert (m_case_list != NULL);
2577 : 0 : dump_case_nodes (dump_file, m_case_list, indent_step, 0);
2578 : : }
2579 : :
2580 : 69854 : bb = emit_case_nodes (bb, index_expr, m_case_list, default_prob, index_type,
2581 : 34927 : gimple_location (m_switch));
2582 : :
2583 : 34927 : if (bb)
2584 : 32635 : emit_jump (bb, m_default_bb);
2585 : :
2586 : : /* Remove all edges and do just an edge that will reach default_bb. */
2587 : 34927 : bb = gimple_bb (m_switch);
2588 : 34927 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
2589 : 34927 : gsi_remove (&gsi, true);
2590 : :
2591 : 34927 : delete_basic_block (bb);
2592 : 34927 : }
2593 : :
2594 : : /* Take an ordered list of case nodes
2595 : : and transform them into a near optimal binary tree,
2596 : : on the assumption that any target code selection value is as
2597 : : likely as any other.
2598 : :
2599 : : The transformation is performed by splitting the ordered
2600 : : list into two equal sections plus a pivot. The parts are
2601 : : then attached to the pivot as left and right branches. Each
2602 : : branch is then transformed recursively. */
2603 : :
2604 : : void
2605 : 193599 : switch_decision_tree::balance_case_nodes (case_tree_node **head,
2606 : : case_tree_node *parent)
2607 : : {
2608 : 193599 : case_tree_node *np;
2609 : :
2610 : 193599 : np = *head;
2611 : 193599 : if (np)
2612 : : {
2613 : 125355 : int i = 0;
2614 : 125355 : case_tree_node **npp;
2615 : 125355 : case_tree_node *left;
2616 : 125355 : profile_probability prob = profile_probability::never ();
2617 : :
2618 : : /* Count the number of entries on branch. */
2619 : :
2620 : 2315195 : while (np)
2621 : : {
2622 : 2189840 : i++;
2623 : 2189840 : prob += np->m_c->m_prob;
2624 : 2189840 : np = np->m_right;
2625 : : }
2626 : :
2627 : 125355 : if (i > 2)
2628 : : {
2629 : : /* Split this list if it is long enough for that to help. */
2630 : 79336 : npp = head;
2631 : 79336 : left = *npp;
2632 : 79336 : profile_probability pivot_prob = prob / 2;
2633 : :
2634 : : /* Find the place in the list that bisects the list's total cost
2635 : : by probability. */
2636 : 4091834 : while (1)
2637 : : {
2638 : : /* Skip nodes while their probability does not reach
2639 : : that amount. */
2640 : 2085585 : prob -= (*npp)->m_c->m_prob;
2641 : 2085585 : if ((prob.initialized_p () && prob < pivot_prob)
2642 : 2117562 : || ! (*npp)->m_right)
2643 : : break;
2644 : 2006249 : npp = &(*npp)->m_right;
2645 : : }
2646 : :
2647 : 79336 : np = *npp;
2648 : 79336 : *npp = 0;
2649 : 79336 : *head = np;
2650 : 79336 : np->m_parent = parent;
2651 : 79336 : np->m_left = left == np ? NULL : left;
2652 : :
2653 : : /* Optimize each of the two split parts. */
2654 : 79336 : balance_case_nodes (&np->m_left, np);
2655 : 79336 : balance_case_nodes (&np->m_right, np);
2656 : 79336 : np->m_c->m_subtree_prob = np->m_c->m_prob;
2657 : 79336 : if (np->m_left)
2658 : 79039 : np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob;
2659 : 79336 : if (np->m_right)
2660 : 11389 : np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
2661 : : }
2662 : : else
2663 : : {
2664 : : /* Else leave this branch as one level,
2665 : : but fill in `parent' fields. */
2666 : 46019 : np = *head;
2667 : 46019 : np->m_parent = parent;
2668 : 46019 : np->m_c->m_subtree_prob = np->m_c->m_prob;
2669 : 76586 : for (; np->m_right; np = np->m_right)
2670 : : {
2671 : 30567 : np->m_right->m_parent = np;
2672 : 30567 : (*head)->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
2673 : : }
2674 : : }
2675 : : }
2676 : 193599 : }
2677 : :
2678 : : /* Dump ROOT, a list or tree of case nodes, to file. */
2679 : :
2680 : : void
2681 : 0 : switch_decision_tree::dump_case_nodes (FILE *f, case_tree_node *root,
2682 : : int indent_step, int indent_level)
2683 : : {
2684 : 0 : if (root == 0)
2685 : 0 : return;
2686 : 0 : indent_level++;
2687 : :
2688 : 0 : dump_case_nodes (f, root->m_left, indent_step, indent_level);
2689 : :
2690 : 0 : fputs (";; ", f);
2691 : 0 : fprintf (f, "%*s", indent_step * indent_level, "");
2692 : 0 : root->m_c->dump (f);
2693 : 0 : root->m_c->m_prob.dump (f);
2694 : 0 : fputs (" subtree: ", f);
2695 : 0 : root->m_c->m_subtree_prob.dump (f);
2696 : 0 : fputs (")\n", f);
2697 : :
2698 : 0 : dump_case_nodes (f, root->m_right, indent_step, indent_level);
2699 : : }
2700 : :
2701 : :
2702 : : /* Add an unconditional jump to CASE_BB that happens in basic block BB. */
2703 : :
2704 : : void
2705 : 64139 : switch_decision_tree::emit_jump (basic_block bb, basic_block case_bb)
2706 : : {
2707 : 64139 : edge e = single_succ_edge (bb);
2708 : 64139 : redirect_edge_succ (e, case_bb);
2709 : 64139 : }
2710 : :
2711 : : /* Generate code to compare OP0 with OP1 so that the condition codes are
2712 : : set and to jump to LABEL_BB if the condition is true.
2713 : : COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
2714 : : PROB is the probability of jumping to LABEL_BB. */
2715 : :
2716 : : basic_block
2717 : 107207 : switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0,
2718 : : tree op1, tree_code comparison,
2719 : : basic_block label_bb,
2720 : : profile_probability prob,
2721 : : location_t loc)
2722 : : {
2723 : : // TODO: it's once called with lhs != index.
2724 : 107207 : op1 = fold_convert (TREE_TYPE (op0), op1);
2725 : :
2726 : 107207 : gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE);
2727 : 107207 : gimple_set_location (cond, loc);
2728 : 107207 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
2729 : 107207 : gsi_insert_after (&gsi, cond, GSI_NEW_STMT);
2730 : :
2731 : 107207 : gcc_assert (single_succ_p (bb));
2732 : :
2733 : : /* Make a new basic block where false branch will take place. */
2734 : 107207 : edge false_edge = split_block (bb, cond);
2735 : 107207 : false_edge->flags = EDGE_FALSE_VALUE;
2736 : 107207 : false_edge->probability = prob.invert ();
2737 : 107207 : false_edge->dest->count = bb->count.apply_probability (prob.invert ());
2738 : :
2739 : 107207 : edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
2740 : 107207 : true_edge->probability = prob;
2741 : :
2742 : 107207 : return false_edge->dest;
2743 : : }
2744 : :
2745 : : /* Generate code to jump to LABEL if OP0 and OP1 are equal.
2746 : : PROB is the probability of jumping to LABEL_BB.
2747 : : BB is a basic block where the new condition will be placed. */
2748 : :
2749 : : basic_block
2750 : 128326 : switch_decision_tree::do_jump_if_equal (basic_block bb, tree op0, tree op1,
2751 : : basic_block label_bb,
2752 : : profile_probability prob,
2753 : : location_t loc)
2754 : : {
2755 : 128326 : op1 = fold_convert (TREE_TYPE (op0), op1);
2756 : :
2757 : 128326 : gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE);
2758 : 128326 : gimple_set_location (cond, loc);
2759 : 128326 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
2760 : 128326 : gsi_insert_before (&gsi, cond, GSI_SAME_STMT);
2761 : :
2762 : 128326 : gcc_assert (single_succ_p (bb));
2763 : :
2764 : : /* Make a new basic block where false branch will take place. */
2765 : 128326 : edge false_edge = split_block (bb, cond);
2766 : 128326 : false_edge->flags = EDGE_FALSE_VALUE;
2767 : 128326 : false_edge->probability = prob.invert ();
2768 : 128326 : false_edge->dest->count = bb->count.apply_probability (prob.invert ());
2769 : :
2770 : 128326 : edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
2771 : 128326 : true_edge->probability = prob;
2772 : :
2773 : 128326 : return false_edge->dest;
2774 : : }
2775 : :
2776 : : /* Emit step-by-step code to select a case for the value of INDEX.
2777 : : The thus generated decision tree follows the form of the
2778 : : case-node binary tree NODE, whose nodes represent test conditions.
2779 : : DEFAULT_PROB is probability of cases leading to default BB.
2780 : : INDEX_TYPE is the type of the index of the switch. */
2781 : :
2782 : : basic_block
2783 : 64139 : switch_decision_tree::emit_case_nodes (basic_block bb, tree index,
2784 : : case_tree_node *node,
2785 : : profile_probability default_prob,
2786 : : tree index_type, location_t loc)
2787 : : {
2788 : 143750 : profile_probability p;
2789 : :
2790 : : /* If node is null, we are done. */
2791 : 143750 : if (node == NULL)
2792 : : return bb;
2793 : :
2794 : : /* Single value case. */
2795 : 120523 : if (node->m_c->is_single_value_p ())
2796 : : {
2797 : : /* Node is single valued. First see if the index expression matches
2798 : : this node and then check our children, if any. */
2799 : 92927 : p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
2800 : 92927 : bb = do_jump_if_equal (bb, index, node->m_c->get_low (),
2801 : : node->m_c->m_case_bb, p, loc);
2802 : : /* Since this case is taken at this point, reduce its weight from
2803 : : subtree_weight. */
2804 : 92927 : node->m_c->m_subtree_prob -= node->m_c->m_prob;
2805 : :
2806 : 92927 : if (node->m_left != NULL && node->m_right != NULL)
2807 : : {
2808 : : /* 1) the node has both children
2809 : :
2810 : : If both children are single-valued cases with no
2811 : : children, finish up all the work. This way, we can save
2812 : : one ordered comparison. */
2813 : :
2814 : 10463 : if (!node->m_left->has_child ()
2815 : 5194 : && node->m_left->m_c->is_single_value_p ()
2816 : 4567 : && !node->m_right->has_child ()
2817 : 4380 : && node->m_right->m_c->is_single_value_p ())
2818 : : {
2819 : 4304 : p = (node->m_right->m_c->m_prob
2820 : 4304 : / (node->m_c->m_subtree_prob + default_prob));
2821 : 4304 : bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
2822 : : node->m_right->m_c->m_case_bb, p, loc);
2823 : 4304 : node->m_c->m_subtree_prob -= node->m_right->m_c->m_prob;
2824 : :
2825 : 4304 : p = (node->m_left->m_c->m_prob
2826 : 4304 : / (node->m_c->m_subtree_prob + default_prob));
2827 : 4304 : bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
2828 : : node->m_left->m_c->m_case_bb, p, loc);
2829 : : }
2830 : : else
2831 : : {
2832 : : /* Branch to a label where we will handle it later. */
2833 : 6159 : basic_block test_bb = split_edge (single_succ_edge (bb));
2834 : 6159 : redirect_edge_succ (single_pred_edge (test_bb),
2835 : 6159 : single_succ_edge (bb)->dest);
2836 : :
2837 : 18477 : p = ((node->m_right->m_c->m_subtree_prob + default_prob / 2)
2838 : 6159 : / (node->m_c->m_subtree_prob + default_prob));
2839 : 6159 : test_bb->count = bb->count.apply_probability (p);
2840 : 6159 : bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
2841 : : GT_EXPR, test_bb, p, loc);
2842 : 6159 : default_prob /= 2;
2843 : :
2844 : : /* Handle the left-hand subtree. */
2845 : 6159 : bb = emit_case_nodes (bb, index, node->m_left,
2846 : : default_prob, index_type, loc);
2847 : :
2848 : : /* If the left-hand subtree fell through,
2849 : : don't let it fall into the right-hand subtree. */
2850 : 6159 : if (bb && m_default_bb)
2851 : 4211 : emit_jump (bb, m_default_bb);
2852 : :
2853 : 6159 : bb = emit_case_nodes (test_bb, index, node->m_right,
2854 : : default_prob, index_type, loc);
2855 : : }
2856 : : }
2857 : 82464 : else if (node->m_left == NULL && node->m_right != NULL)
2858 : : {
2859 : : /* 2) the node has only right child. */
2860 : :
2861 : : /* Here we have a right child but no left so we issue a conditional
2862 : : branch to default and process the right child.
2863 : :
2864 : : Omit the conditional branch to default if the right child
2865 : : does not have any children and is single valued; it would
2866 : : cost too much space to save so little time. */
2867 : :
2868 : 27716 : if (node->m_right->has_child ()
2869 : 27507 : || !node->m_right->m_c->is_single_value_p ())
2870 : : {
2871 : 2775 : p = ((default_prob / 2)
2872 : 925 : / (node->m_c->m_subtree_prob + default_prob));
2873 : 925 : bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
2874 : : LT_EXPR, m_default_bb, p, loc);
2875 : 925 : default_prob /= 2;
2876 : :
2877 : 925 : bb = emit_case_nodes (bb, index, node->m_right, default_prob,
2878 : : index_type, loc);
2879 : : }
2880 : : else
2881 : : {
2882 : : /* We cannot process node->right normally
2883 : : since we haven't ruled out the numbers less than
2884 : : this node's value. So handle node->right explicitly. */
2885 : 26791 : p = (node->m_right->m_c->m_subtree_prob
2886 : 26791 : / (node->m_c->m_subtree_prob + default_prob));
2887 : 26791 : bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
2888 : : node->m_right->m_c->m_case_bb, p, loc);
2889 : : }
2890 : : }
2891 : 54748 : else if (node->m_left != NULL && node->m_right == NULL)
2892 : : {
2893 : : /* 3) just one subtree, on the left. Similar case as previous. */
2894 : :
2895 : 49474 : if (node->m_left->has_child ()
2896 : 0 : || !node->m_left->m_c->is_single_value_p ())
2897 : : {
2898 : 148422 : p = ((default_prob / 2)
2899 : 49474 : / (node->m_c->m_subtree_prob + default_prob));
2900 : 49474 : bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
2901 : : GT_EXPR, m_default_bb, p, loc);
2902 : 49474 : default_prob /= 2;
2903 : :
2904 : 49474 : bb = emit_case_nodes (bb, index, node->m_left, default_prob,
2905 : : index_type, loc);
2906 : : }
2907 : : else
2908 : : {
2909 : : /* We cannot process node->left normally
2910 : : since we haven't ruled out the numbers less than
2911 : : this node's value. So handle node->left explicitly. */
2912 : 0 : p = (node->m_left->m_c->m_subtree_prob
2913 : 0 : / (node->m_c->m_subtree_prob + default_prob));
2914 : 0 : bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
2915 : : node->m_left->m_c->m_case_bb, p, loc);
2916 : : }
2917 : : }
2918 : : }
2919 : : else
2920 : : {
2921 : : /* Node is a range. These cases are very similar to those for a single
2922 : : value, except that we do not start by testing whether this node
2923 : : is the one to branch to. */
2924 : 32942 : if (node->has_child () || node->m_c->get_type () != SIMPLE_CASE)
2925 : : {
2926 : 23053 : bool is_bt = node->m_c->get_type () == BIT_TEST;
2927 : 23053 : int parts = is_bt ? 3 : 2;
2928 : :
2929 : : /* Branch to a label where we will handle it later. */
2930 : 23053 : basic_block test_bb = split_edge (single_succ_edge (bb));
2931 : 23053 : redirect_edge_succ (single_pred_edge (test_bb),
2932 : 23053 : single_succ_edge (bb)->dest);
2933 : :
2934 : 23053 : profile_probability right_prob = profile_probability::never ();
2935 : 23053 : if (node->m_right)
2936 : 3777 : right_prob = node->m_right->m_c->m_subtree_prob;
2937 : 69159 : p = ((right_prob + default_prob / parts)
2938 : 23053 : / (node->m_c->m_subtree_prob + default_prob));
2939 : 23053 : test_bb->count = bb->count.apply_probability (p);
2940 : :
2941 : 23053 : bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
2942 : : GT_EXPR, test_bb, p, loc);
2943 : :
2944 : 23053 : default_prob /= parts;
2945 : 23053 : node->m_c->m_subtree_prob -= right_prob;
2946 : 23053 : if (is_bt)
2947 : 1237 : node->m_c->m_default_prob = default_prob;
2948 : :
2949 : : /* Value belongs to this node or to the left-hand subtree. */
2950 : 23053 : p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
2951 : 23053 : bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
2952 : : GE_EXPR, node->m_c->m_case_bb, p, loc);
2953 : :
2954 : : /* Handle the left-hand subtree. */
2955 : 23053 : bb = emit_case_nodes (bb, index, node->m_left, default_prob,
2956 : : index_type, loc);
2957 : :
2958 : : /* If the left-hand subtree fell through,
2959 : : don't let it fall into the right-hand subtree. */
2960 : 23053 : if (bb && m_default_bb)
2961 : 22750 : emit_jump (bb, m_default_bb);
2962 : :
2963 : 23053 : bb = emit_case_nodes (test_bb, index, node->m_right, default_prob,
2964 : : index_type, loc);
2965 : : }
2966 : : else
2967 : : {
2968 : : /* Node has no children so we check low and high bounds to remove
2969 : : redundant tests. Only one of the bounds can exist,
2970 : : since otherwise this node is bounded--a case tested already. */
2971 : 4543 : tree lhs, rhs;
2972 : 4543 : generate_range_test (bb, index, node->m_c->get_low (),
2973 : 4543 : node->m_c->get_high (), &lhs, &rhs);
2974 : 4543 : p = default_prob / (node->m_c->m_subtree_prob + default_prob);
2975 : :
2976 : 4543 : bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,
2977 : : m_default_bb, p, loc);
2978 : :
2979 : 4543 : emit_jump (bb, node->m_c->m_case_bb);
2980 : 4543 : return NULL;
2981 : : }
2982 : : }
2983 : :
2984 : : return bb;
2985 : : }
2986 : :
2987 : : /* The main function of the pass scans statements for switches and invokes
2988 : : process_switch on them. */
2989 : :
2990 : : namespace {
2991 : :
2992 : : const pass_data pass_data_convert_switch =
2993 : : {
2994 : : GIMPLE_PASS, /* type */
2995 : : "switchconv", /* name */
2996 : : OPTGROUP_NONE, /* optinfo_flags */
2997 : : TV_TREE_SWITCH_CONVERSION, /* tv_id */
2998 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
2999 : : 0, /* properties_provided */
3000 : : 0, /* properties_destroyed */
3001 : : 0, /* todo_flags_start */
3002 : : TODO_update_ssa, /* todo_flags_finish */
3003 : : };
3004 : :
3005 : : class pass_convert_switch : public gimple_opt_pass
3006 : : {
3007 : : public:
3008 : 282953 : pass_convert_switch (gcc::context *ctxt)
3009 : 565906 : : gimple_opt_pass (pass_data_convert_switch, ctxt)
3010 : : {}
3011 : :
3012 : : /* opt_pass methods: */
3013 : 2257587 : bool gate (function *) final override
3014 : : {
3015 : 2257587 : return flag_tree_switch_conversion != 0;
3016 : : }
3017 : : unsigned int execute (function *) final override;
3018 : :
3019 : : }; // class pass_convert_switch
3020 : :
3021 : : unsigned int
3022 : 2157041 : pass_convert_switch::execute (function *fun)
3023 : : {
3024 : 2157041 : basic_block bb;
3025 : 2157041 : bool cfg_altered = false;
3026 : :
3027 : 13244667 : FOR_EACH_BB_FN (bb, fun)
3028 : : {
3029 : 32984672 : if (gswitch *stmt = safe_dyn_cast <gswitch *> (*gsi_last_bb (bb)))
3030 : : {
3031 : 25982 : if (dump_file)
3032 : : {
3033 : 43 : expanded_location loc = expand_location (gimple_location (stmt));
3034 : :
3035 : 43 : fprintf (dump_file, "beginning to process the following "
3036 : : "SWITCH statement (%s:%d) : ------- \n",
3037 : : loc.file, loc.line);
3038 : 43 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3039 : 43 : putc ('\n', dump_file);
3040 : : }
3041 : :
3042 : 25982 : switch_conversion sconv;
3043 : 25982 : sconv.expand (stmt);
3044 : 25982 : cfg_altered |= sconv.m_cfg_altered;
3045 : 25982 : if (!sconv.m_reason)
3046 : : {
3047 : 582 : if (dump_file)
3048 : : {
3049 : 39 : fputs ("Switch converted\n", dump_file);
3050 : 39 : fputs ("--------------------------------\n", dump_file);
3051 : : }
3052 : :
3053 : : /* Make no effort to update the post-dominator tree.
3054 : : It is actually not that hard for the transformations
3055 : : we have performed, but it is not supported
3056 : : by iterate_fix_dominators. */
3057 : 582 : free_dominance_info (CDI_POST_DOMINATORS);
3058 : : }
3059 : : else
3060 : : {
3061 : 25400 : if (dump_file)
3062 : : {
3063 : 4 : fputs ("Bailing out - ", dump_file);
3064 : 4 : fputs (sconv.m_reason, dump_file);
3065 : 4 : fputs ("\n--------------------------------\n", dump_file);
3066 : : }
3067 : : }
3068 : 25982 : }
3069 : : }
3070 : :
3071 : 2157041 : return cfg_altered ? TODO_cleanup_cfg : 0;;
3072 : : }
3073 : :
3074 : : } // anon namespace
3075 : :
3076 : : gimple_opt_pass *
3077 : 282953 : make_pass_convert_switch (gcc::context *ctxt)
3078 : : {
3079 : 282953 : return new pass_convert_switch (ctxt);
3080 : : }
3081 : :
3082 : : /* The main function of the pass scans statements for switches and invokes
3083 : : process_switch on them. */
3084 : :
3085 : : namespace {
3086 : :
3087 : : template <bool O0> class pass_lower_switch: public gimple_opt_pass
3088 : : {
3089 : : public:
3090 : 1697718 : pass_lower_switch (gcc::context *ctxt) : gimple_opt_pass (data, ctxt) {}
3091 : :
3092 : : static const pass_data data;
3093 : : opt_pass *
3094 : 282953 : clone () final override
3095 : : {
3096 : 282953 : return new pass_lower_switch<O0> (m_ctxt);
3097 : : }
3098 : :
3099 : : bool
3100 : 2439302 : gate (function *) final override
3101 : : {
3102 : 2439302 : return !O0 || !optimize;
3103 : : }
3104 : :
3105 : : unsigned int execute (function *fun) final override;
3106 : : }; // class pass_lower_switch
3107 : :
3108 : : template <bool O0>
3109 : : const pass_data pass_lower_switch<O0>::data = {
3110 : : GIMPLE_PASS, /* type */
3111 : : O0 ? "switchlower_O0" : "switchlower", /* name */
3112 : : OPTGROUP_NONE, /* optinfo_flags */
3113 : : TV_TREE_SWITCH_LOWERING, /* tv_id */
3114 : : ( PROP_cfg | PROP_ssa ), /* properties_required */
3115 : : 0, /* properties_provided */
3116 : : 0, /* properties_destroyed */
3117 : : 0, /* todo_flags_start */
3118 : : TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
3119 : : };
3120 : :
3121 : : template <bool O0>
3122 : : unsigned int
3123 : 1433929 : pass_lower_switch<O0>::execute (function *fun)
3124 : : {
3125 : : basic_block bb;
3126 : 1433929 : bool expanded = false;
3127 : :
3128 : 1433929 : auto_vec<gimple *> switch_statements;
3129 : 1433929 : switch_statements.create (1);
3130 : :
3131 : 14391915 : FOR_EACH_BB_FN (bb, fun)
3132 : : {
3133 : 25569528 : if (gswitch *swtch = safe_dyn_cast <gswitch *> (*gsi_last_bb (bb)))
3134 : : {
3135 : : if (!O0)
3136 : 27402 : group_case_labels_stmt (swtch);
3137 : 42392 : switch_statements.safe_push (swtch);
3138 : : }
3139 : : }
3140 : :
3141 : 1476321 : for (unsigned i = 0; i < switch_statements.length (); i++)
3142 : : {
3143 : 42392 : gimple *stmt = switch_statements[i];
3144 : 42392 : if (dump_file)
3145 : : {
3146 : 21 : expanded_location loc = expand_location (gimple_location (stmt));
3147 : :
3148 : 21 : fprintf (dump_file, "beginning to process the following "
3149 : : "SWITCH statement (%s:%d) : ------- \n",
3150 : : loc.file, loc.line);
3151 : 21 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3152 : 21 : putc ('\n', dump_file);
3153 : : }
3154 : :
3155 : 42392 : gswitch *swtch = dyn_cast<gswitch *> (stmt);
3156 : : if (swtch)
3157 : : {
3158 : 42392 : switch_decision_tree dt (swtch);
3159 : 42392 : expanded |= dt.analyze_switch_statement ();
3160 : 42392 : }
3161 : : }
3162 : :
3163 : 1433929 : if (expanded)
3164 : : {
3165 : 32042 : free_dominance_info (CDI_DOMINATORS);
3166 : 32042 : free_dominance_info (CDI_POST_DOMINATORS);
3167 : 32042 : mark_virtual_operands_for_renaming (cfun);
3168 : : }
3169 : :
3170 : 1433929 : return 0;
3171 : 1433929 : }
3172 : :
3173 : : } // anon namespace
3174 : :
3175 : : gimple_opt_pass *
3176 : 282953 : make_pass_lower_switch_O0 (gcc::context *ctxt)
3177 : : {
3178 : 282953 : return new pass_lower_switch<true> (ctxt);
3179 : : }
3180 : : gimple_opt_pass *
3181 : 282953 : make_pass_lower_switch (gcc::context *ctxt)
3182 : : {
3183 : 282953 : return new pass_lower_switch<false> (ctxt);
3184 : : }
|
