1/* Lower GIMPLE_SWITCH expressions to something more efficient than
2 a jump table.
3 Copyright (C) 2006-2017 Free Software Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by the
9Free Software Foundation; either version 3, or (at your option) any
10later version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT
13ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not, write to the Free
19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
2002110-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 "params.h"
40#include "fold-const.h"
41#include "varasm.h"
42#include "stor-layout.h"
43#include "cfganal.h"
44#include "gimplify.h"
45#include "gimple-iterator.h"
46#include "gimplify-me.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
53/* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
54 type in the GIMPLE type system that is language-independent? */
55#include "langhooks.h"
56
57
58/* Maximum number of case bit tests.
59 FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and
60 targetm.case_values_threshold(), or be its own param. */
61#define MAX_CASE_BIT_TESTS 3
62
63/* Split the basic block at the statement pointed to by GSIP, and insert
64 a branch to the target basic block of E_TRUE conditional on tree
65 expression COND.
66
67 It is assumed that there is already an edge from the to-be-split
68 basic block to E_TRUE->dest block. This edge is removed, and the
69 profile information on the edge is re-used for the new conditional
70 jump.
71
72 The CFG is updated. The dominator tree will not be valid after
73 this transformation, but the immediate dominators are updated if
74 UPDATE_DOMINATORS is true.
75
76 Returns the newly created basic block. */
77
78static basic_block
79hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
80 tree cond, edge e_true,
81 bool update_dominators)
82{
83 tree tmp;
84 gcond *cond_stmt;
85 edge e_false;
86 basic_block new_bb, split_bb = gsi_bb (*gsip);
87 bool dominated_e_true = false;
88
89 gcc_assert (e_true->src == split_bb);
90
91 if (update_dominators
92 && get_immediate_dominator (CDI_DOMINATORS, e_true->dest) == split_bb)
93 dominated_e_true = true;
94
95 tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
96 /*before=*/true, GSI_SAME_STMT);
97 cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
98 gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
99
100 e_false = split_block (split_bb, cond_stmt);
101 new_bb = e_false->dest;
102 redirect_edge_pred (e_true, split_bb);
103
104 e_true->flags &= ~EDGE_FALLTHRU;
105 e_true->flags |= EDGE_TRUE_VALUE;
106
107 e_false->flags &= ~EDGE_FALLTHRU;
108 e_false->flags |= EDGE_FALSE_VALUE;
109 e_false->probability = e_true->probability.invert ();
110 new_bb->count = e_false->count ();
111
112 if (update_dominators)
113 {
114 if (dominated_e_true)
115 set_immediate_dominator (CDI_DOMINATORS, e_true->dest, split_bb);
116 set_immediate_dominator (CDI_DOMINATORS, e_false->dest, split_bb);
117 }
118
119 return new_bb;
120}
121
122
123/* Return true if a switch should be expanded as a bit test.
124 RANGE is the difference between highest and lowest case.
125 UNIQ is number of unique case node targets, not counting the default case.
126 COUNT is the number of comparisons needed, not counting the default case. */
127
128static bool
129expand_switch_using_bit_tests_p (tree range,
130 unsigned int uniq,
131 unsigned int count, bool speed_p)
132{
133 return (((uniq == 1 && count >= 3)
134 || (uniq == 2 && count >= 5)
135 || (uniq == 3 && count >= 6))
136 && lshift_cheap_p (speed_p)
137 && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
138 && compare_tree_int (range, 0) > 0);
139}
140
141/* Implement switch statements with bit tests
142
143A GIMPLE switch statement can be expanded to a short sequence of bit-wise
144comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
145where CST and MINVAL are integer constants. This is better than a series
146of compare-and-banch insns in some cases, e.g. we can implement:
147
148 if ((x==4) || (x==6) || (x==9) || (x==11))
149
150as a single bit test:
151
152 if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
153
154This transformation is only applied if the number of case targets is small,
155if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are
156performed in "word_mode".
157
158The following example shows the code the transformation generates:
159
160 int bar(int x)
161 {
162 switch (x)
163 {
164 case '0': case '1': case '2': case '3': case '4':
165 case '5': case '6': case '7': case '8': case '9':
166 case 'A': case 'B': case 'C': case 'D': case 'E':
167 case 'F':
168 return 1;
169 }
170 return 0;
171 }
172
173==>
174
175 bar (int x)
176 {
177 tmp1 = x - 48;
178 if (tmp1 > (70 - 48)) goto L2;
179 tmp2 = 1 << tmp1;
180 tmp3 = 0b11111100000001111111111;
181 if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
182 L1:
183 return 1;
184 L2:
185 return 0;
186 }
187
188TODO: There are still some improvements to this transformation that could
189be implemented:
190
191* A narrower mode than word_mode could be used if that is cheaper, e.g.
192 for x86_64 where a narrower-mode shift may result in smaller code.
193
194* The compounded constant could be shifted rather than the one. The
195 test would be either on the sign bit or on the least significant bit,
196 depending on the direction of the shift. On some machines, the test
197 for the branch would be free if the bit to test is already set by the
198 shift operation.
199
200This transformation was contributed by Roger Sayle, see this e-mail:
201 http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
202*/
203
204/* A case_bit_test represents a set of case nodes that may be
205 selected from using a bit-wise comparison. HI and LO hold
206 the integer to be tested against, TARGET_EDGE contains the
207 edge to the basic block to jump to upon success and BITS
208 counts the number of case nodes handled by this test,
209 typically the number of bits set in HI:LO. The LABEL field
210 is used to quickly identify all cases in this set without
211 looking at label_to_block for every case label. */
212
213struct case_bit_test
214{
215 wide_int mask;
216 edge target_edge;
217 tree label;
218 int bits;
219};
220
221/* Comparison function for qsort to order bit tests by decreasing
222 probability of execution. Our best guess comes from a measured
223 profile. If the profile counts are equal, break even on the
224 number of case nodes, i.e. the node with the most cases gets
225 tested first.
226
227 TODO: Actually this currently runs before a profile is available.
228 Therefore the case-as-bit-tests transformation should be done
229 later in the pass pipeline, or something along the lines of
230 "Efficient and effective branch reordering using profile data"
231 (Yang et. al., 2002) should be implemented (although, how good
232 is a paper is called "Efficient and effective ..." when the
233 latter is implied by the former, but oh well...). */
234
235static int
236case_bit_test_cmp (const void *p1, const void *p2)
237{
238 const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
239 const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
240
241 if (d2->target_edge->count () < d1->target_edge->count ())
242 return -1;
243 if (d2->target_edge->count () > d1->target_edge->count ())
244 return 1;
245 if (d2->bits != d1->bits)
246 return d2->bits - d1->bits;
247
248 /* Stabilize the sort. */
249 return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (d1->label);
250}
251
252/* Expand a switch statement by a short sequence of bit-wise
253 comparisons. "switch(x)" is effectively converted into
254 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
255 integer constants.
256
257 INDEX_EXPR is the value being switched on.
258
259 MINVAL is the lowest case value of in the case nodes,
260 and RANGE is highest value minus MINVAL. MINVAL and RANGE
261 are not guaranteed to be of the same type as INDEX_EXPR
262 (the gimplifier doesn't change the type of case label values,
263 and MINVAL and RANGE are derived from those values).
264 MAXVAL is MINVAL + RANGE.
265
266 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
267 node targets. */
268
269static void
270emit_case_bit_tests (gswitch *swtch, tree index_expr,
271 tree minval, tree range, tree maxval)
272{
273 struct case_bit_test test[MAX_CASE_BIT_TESTS] = { {} };
274 unsigned int i, j, k;
275 unsigned int count;
276
277 basic_block switch_bb = gimple_bb (swtch);
278 basic_block default_bb, new_default_bb, new_bb;
279 edge default_edge;
280 bool update_dom = dom_info_available_p (CDI_DOMINATORS);
281
282 vec<basic_block> bbs_to_fix_dom = vNULL;
283
284 tree index_type = TREE_TYPE (index_expr);
285 tree unsigned_index_type = unsigned_type_for (index_type);
286 unsigned int branch_num = gimple_switch_num_labels (swtch);
287
288 gimple_stmt_iterator gsi;
289 gassign *shift_stmt;
290
291 tree idx, tmp, csui;
292 tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
293 tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
294 tree word_mode_one = fold_convert (word_type_node, integer_one_node);
295 int prec = TYPE_PRECISION (word_type_node);
296 wide_int wone = wi::one (prec);
297
298 /* Get the edge for the default case. */
299 tmp = gimple_switch_default_label (swtch);
300 default_bb = label_to_block (CASE_LABEL (tmp));
301 default_edge = find_edge (switch_bb, default_bb);
302
303 /* Go through all case labels, and collect the case labels, profile
304 counts, and other information we need to build the branch tests. */
305 count = 0;
306 for (i = 1; i < branch_num; i++)
307 {
308 unsigned int lo, hi;
309 tree cs = gimple_switch_label (swtch, i);
310 tree label = CASE_LABEL (cs);
311 edge e = find_edge (switch_bb, label_to_block (label));
312 for (k = 0; k < count; k++)
313 if (e == test[k].target_edge)
314 break;
315
316 if (k == count)
317 {
318 gcc_checking_assert (count < MAX_CASE_BIT_TESTS);
319 test[k].mask = wi::zero (prec);
320 test[k].target_edge = e;
321 test[k].label = label;
322 test[k].bits = 1;
323 count++;
324 }
325 else
326 test[k].bits++;
327
328 lo = tree_to_uhwi (int_const_binop (MINUS_EXPR,
329 CASE_LOW (cs), minval));
330 if (CASE_HIGH (cs) == NULL_TREE)
331 hi = lo;
332 else
333 hi = tree_to_uhwi (int_const_binop (MINUS_EXPR,
334 CASE_HIGH (cs), minval));
335
336 for (j = lo; j <= hi; j++)
337 test[k].mask |= wi::lshift (wone, j);
338 }
339
340 qsort (test, count, sizeof (*test), case_bit_test_cmp);
341
342 /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
343 the minval subtractions, but it might make the mask constants more
344 expensive. So, compare the costs. */
345 if (compare_tree_int (minval, 0) > 0
346 && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
347 {
348 int cost_diff;
349 HOST_WIDE_INT m = tree_to_uhwi (minval);
350 rtx reg = gen_raw_REG (word_mode, 10000);
351 bool speed_p = optimize_bb_for_speed_p (gimple_bb (swtch));
352 cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg,
353 GEN_INT (-m)), speed_p);
354 for (i = 0; i < count; i++)
355 {
356 rtx r = immed_wide_int_const (test[i].mask, word_mode);
357 cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r),
358 word_mode, speed_p);
359 r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode);
360 cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r),
361 word_mode, speed_p);
362 }
363 if (cost_diff > 0)
364 {
365 for (i = 0; i < count; i++)
366 test[i].mask = wi::lshift (test[i].mask, m);
367 minval = build_zero_cst (TREE_TYPE (minval));
368 range = maxval;
369 }
370 }
371
372 /* We generate two jumps to the default case label.
373 Split the default edge, so that we don't have to do any PHI node
374 updating. */
375 new_default_bb = split_edge (default_edge);
376
377 if (update_dom)
378 {
379 bbs_to_fix_dom.create (10);
380 bbs_to_fix_dom.quick_push (switch_bb);
381 bbs_to_fix_dom.quick_push (default_bb);
382 bbs_to_fix_dom.quick_push (new_default_bb);
383 }
384
385 /* Now build the test-and-branch code. */
386
387 gsi = gsi_last_bb (switch_bb);
388
389 /* idx = (unsigned)x - minval. */
390 idx = fold_convert (unsigned_index_type, index_expr);
391 idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx,
392 fold_convert (unsigned_index_type, minval));
393 idx = force_gimple_operand_gsi (&gsi, idx,
394 /*simple=*/true, NULL_TREE,
395 /*before=*/true, GSI_SAME_STMT);
396
397 /* if (idx > range) goto default */
398 range = force_gimple_operand_gsi (&gsi,
399 fold_convert (unsigned_index_type, range),
400 /*simple=*/true, NULL_TREE,
401 /*before=*/true, GSI_SAME_STMT);
402 tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
403 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_edge, update_dom);
404 if (update_dom)
405 bbs_to_fix_dom.quick_push (new_bb);
406 gcc_assert (gimple_bb (swtch) == new_bb);
407 gsi = gsi_last_bb (new_bb);
408
409 /* Any blocks dominated by the GIMPLE_SWITCH, but that are not successors
410 of NEW_BB, are still immediately dominated by SWITCH_BB. Make it so. */
411 if (update_dom)
412 {
413 vec<basic_block> dom_bbs;
414 basic_block dom_son;
415
416 dom_bbs = get_dominated_by (CDI_DOMINATORS, new_bb);
417 FOR_EACH_VEC_ELT (dom_bbs, i, dom_son)
418 {
419 edge e = find_edge (new_bb, dom_son);
420 if (e && single_pred_p (e->dest))
421 continue;
422 set_immediate_dominator (CDI_DOMINATORS, dom_son, switch_bb);
423 bbs_to_fix_dom.safe_push (dom_son);
424 }
425 dom_bbs.release ();
426 }
427
428 /* csui = (1 << (word_mode) idx) */
429 csui = make_ssa_name (word_type_node);
430 tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one,
431 fold_convert (word_type_node, idx));
432 tmp = force_gimple_operand_gsi (&gsi, tmp,
433 /*simple=*/false, NULL_TREE,
434 /*before=*/true, GSI_SAME_STMT);
435 shift_stmt = gimple_build_assign (csui, tmp);
436 gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
437 update_stmt (shift_stmt);
438
439 /* for each unique set of cases:
440 if (const & csui) goto target */
441 for (k = 0; k < count; k++)
442 {
443 tmp = wide_int_to_tree (word_type_node, test[k].mask);
444 tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp);
445 tmp = force_gimple_operand_gsi (&gsi, tmp,
446 /*simple=*/true, NULL_TREE,
447 /*before=*/true, GSI_SAME_STMT);
448 tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
449 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_edge,
450 update_dom);
451 if (update_dom)
452 bbs_to_fix_dom.safe_push (new_bb);
453 gcc_assert (gimple_bb (swtch) == new_bb);
454 gsi = gsi_last_bb (new_bb);
455 }
456
457 /* We should have removed all edges now. */
458 gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
459
460 /* If nothing matched, go to the default label. */
461 make_edge (gsi_bb (gsi), new_default_bb, EDGE_FALLTHRU);
462
463 /* The GIMPLE_SWITCH is now redundant. */
464 gsi_remove (&gsi, true);
465
466 if (update_dom)
467 {
468 /* Fix up the dominator tree. */
469 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
470 bbs_to_fix_dom.release ();
471 }
472}
473
474/*
475 Switch initialization conversion
476
477The following pass changes simple initializations of scalars in a switch
478statement into initializations from a static array. Obviously, the values
479must be constant and known at compile time and a default branch must be
480provided. For example, the following code:
481
482 int a,b;
483
484 switch (argc)
485 {
486 case 1:
487 case 2:
488 a_1 = 8;
489 b_1 = 6;
490 break;
491 case 3:
492 a_2 = 9;
493 b_2 = 5;
494 break;
495 case 12:
496 a_3 = 10;
497 b_3 = 4;
498 break;
499 default:
500 a_4 = 16;
501 b_4 = 1;
502 break;
503 }
504 a_5 = PHI <a_1, a_2, a_3, a_4>
505 b_5 = PHI <b_1, b_2, b_3, b_4>
506
507
508is changed into:
509
510 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
511 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
512 16, 16, 10};
513
514 if (((unsigned) argc) - 1 < 11)
515 {
516 a_6 = CSWTCH02[argc - 1];
517 b_6 = CSWTCH01[argc - 1];
518 }
519 else
520 {
521 a_7 = 16;
522 b_7 = 1;
523 }
524 a_5 = PHI <a_6, a_7>
525 b_b = PHI <b_6, b_7>
526
527There are further constraints. Specifically, the range of values across all
528case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
529eight) times the number of the actual switch branches.
530
531This transformation was contributed by Martin Jambor, see this e-mail:
532 http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
533
534/* The main structure of the pass. */
535struct switch_conv_info
536{
537 /* The expression used to decide the switch branch. */
538 tree index_expr;
539
540 /* The following integer constants store the minimum and maximum value
541 covered by the case labels. */
542 tree range_min;
543 tree range_max;
544
545 /* The difference between the above two numbers. Stored here because it
546 is used in all the conversion heuristics, as well as for some of the
547 transformation, and it is expensive to re-compute it all the time. */
548 tree range_size;
549
550 /* Basic block that contains the actual GIMPLE_SWITCH. */
551 basic_block switch_bb;
552
553 /* Basic block that is the target of the default case. */
554 basic_block default_bb;
555
556 /* The single successor block of all branches out of the GIMPLE_SWITCH,
557 if such a block exists. Otherwise NULL. */
558 basic_block final_bb;
559
560 /* The probability of the default edge in the replaced switch. */
561 profile_probability default_prob;
562
563 /* The count of the default edge in the replaced switch. */
564 profile_count default_count;
565
566 /* Combined count of all other (non-default) edges in the replaced switch. */
567 profile_count other_count;
568
569 /* Number of phi nodes in the final bb (that we'll be replacing). */
570 int phi_count;
571
572 /* Array of default values, in the same order as phi nodes. */
573 tree *default_values;
574
575 /* Constructors of new static arrays. */
576 vec<constructor_elt, va_gc> **constructors;
577
578 /* Array of ssa names that are initialized with a value from a new static
579 array. */
580 tree *target_inbound_names;
581
582 /* Array of ssa names that are initialized with the default value if the
583 switch expression is out of range. */
584 tree *target_outbound_names;
585
586 /* VOP SSA_NAME. */
587 tree target_vop;
588
589 /* The first load statement that loads a temporary from a new static array.
590 */
591 gimple *arr_ref_first;
592
593 /* The last load statement that loads a temporary from a new static array. */
594 gimple *arr_ref_last;
595
596 /* String reason why the case wasn't a good candidate that is written to the
597 dump file, if there is one. */
598 const char *reason;
599
600 /* True if default case is not used for any value between range_min and
601 range_max inclusive. */
602 bool contiguous_range;
603
604 /* True if default case does not have the required shape for other case
605 labels. */
606 bool default_case_nonstandard;
607
608 /* Parameters for expand_switch_using_bit_tests. Should be computed
609 the same way as in expand_case. */
610 unsigned int uniq;
611 unsigned int count;
612};
613
614/* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
615
616static void
617collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info)
618{
619 unsigned int branch_num = gimple_switch_num_labels (swtch);
620 tree min_case, max_case;
621 unsigned int count, i;
622 edge e, e_default, e_first;
623 edge_iterator ei;
624 basic_block first;
625
626 memset (info, 0, sizeof (*info));
627
628 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
629 is a default label which is the first in the vector.
630 Collect the bits we can deduce from the CFG. */
631 info->index_expr = gimple_switch_index (swtch);
632 info->switch_bb = gimple_bb (swtch);
633 info->default_bb
634 = label_to_block (CASE_LABEL (gimple_switch_default_label (swtch)));
635 e_default = find_edge (info->switch_bb, info->default_bb);
636 info->default_prob = e_default->probability;
637 info->default_count = e_default->count ();
638 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
639 if (e != e_default)
640 info->other_count += e->count ();
641
642 /* Get upper and lower bounds of case values, and the covered range. */
643 min_case = gimple_switch_label (swtch, 1);
644 max_case = gimple_switch_label (swtch, branch_num - 1);
645
646 info->range_min = CASE_LOW (min_case);
647 if (CASE_HIGH (max_case) != NULL_TREE)
648 info->range_max = CASE_HIGH (max_case);
649 else
650 info->range_max = CASE_LOW (max_case);
651
652 info->contiguous_range = true;
653 tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : info->range_min;
654 for (i = 2; i < branch_num; i++)
655 {
656 tree elt = gimple_switch_label (swtch, i);
657 if (wi::to_wide (last) + 1 != wi::to_wide (CASE_LOW (elt)))
658 {
659 info->contiguous_range = false;
660 break;
661 }
662 last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt);
663 }
664
665 if (info->contiguous_range)
666 {
667 first = label_to_block (CASE_LABEL (gimple_switch_label (swtch, 1)));
668 e_first = find_edge (info->switch_bb, first);
669 }
670 else
671 {
672 first = info->default_bb;
673 e_first = e_default;
674 }
675
676 /* See if there is one common successor block for all branch
677 targets. If it exists, record it in FINAL_BB.
678 Start with the destination of the first non-default case
679 if the range is contiguous and default case otherwise as
680 guess or its destination in case it is a forwarder block. */
681 if (! single_pred_p (e_first->dest))
682 info->final_bb = e_first->dest;
683 else if (single_succ_p (e_first->dest)
684 && ! single_pred_p (single_succ (e_first->dest)))
685 info->final_bb = single_succ (e_first->dest);
686 /* Require that all switch destinations are either that common
687 FINAL_BB or a forwarder to it, except for the default
688 case if contiguous range. */
689 if (info->final_bb)
690 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
691 {
692 if (e->dest == info->final_bb)
693 continue;
694
695 if (single_pred_p (e->dest)
696 && single_succ_p (e->dest)
697 && single_succ (e->dest) == info->final_bb)
698 continue;
699
700 if (e == e_default && info->contiguous_range)
701 {
702 info->default_case_nonstandard = true;
703 continue;
704 }
705
706 info->final_bb = NULL;
707 break;
708 }
709
710 info->range_size
711 = int_const_binop (MINUS_EXPR, info->range_max, info->range_min);
712
713 /* Get a count of the number of case labels. Single-valued case labels
714 simply count as one, but a case range counts double, since it may
715 require two compares if it gets lowered as a branching tree. */
716 count = 0;
717 for (i = 1; i < branch_num; i++)
718 {
719 tree elt = gimple_switch_label (swtch, i);
720 count++;
721 if (CASE_HIGH (elt)
722 && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
723 count++;
724 }
725 info->count = count;
726
727 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
728 block. Assume a CFG cleanup would have already removed degenerate
729 switch statements, this allows us to just use EDGE_COUNT. */
730 info->uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
731}
732
733/* Checks whether the range given by individual case statements of the SWTCH
734 switch statement isn't too big and whether the number of branches actually
735 satisfies the size of the new array. */
736
737static bool
738check_range (struct switch_conv_info *info)
739{
740 gcc_assert (info->range_size);
741 if (!tree_fits_uhwi_p (info->range_size))
742 {
743 info->reason = "index range way too large or otherwise unusable";
744 return false;
745 }
746
747 if (tree_to_uhwi (info->range_size)
748 > ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO))
749 {
750 info->reason = "the maximum range-branch ratio exceeded";
751 return false;
752 }
753
754 return true;
755}
756
757/* Checks whether all but the FINAL_BB basic blocks are empty. */
758
759static bool
760check_all_empty_except_final (struct switch_conv_info *info)
761{
762 edge e, e_default = find_edge (info->switch_bb, info->default_bb);
763 edge_iterator ei;
764
765 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
766 {
767 if (e->dest == info->final_bb)
768 continue;
769
770 if (!empty_block_p (e->dest))
771 {
772 if (info->contiguous_range && e == e_default)
773 {
774 info->default_case_nonstandard = true;
775 continue;
776 }
777
778 info->reason = "bad case - a non-final BB not empty";
779 return false;
780 }
781 }
782
783 return true;
784}
785
786/* This function checks whether all required values in phi nodes in final_bb
787 are constants. Required values are those that correspond to a basic block
788 which is a part of the examined switch statement. It returns true if the
789 phi nodes are OK, otherwise false. */
790
791static bool
792check_final_bb (gswitch *swtch, struct switch_conv_info *info)
793{
794 gphi_iterator gsi;
795
796 info->phi_count = 0;
797 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
798 {
799 gphi *phi = gsi.phi ();
800 unsigned int i;
801
802 if (virtual_operand_p (gimple_phi_result (phi)))
803 continue;
804
805 info->phi_count++;
806
807 for (i = 0; i < gimple_phi_num_args (phi); i++)
808 {
809 basic_block bb = gimple_phi_arg_edge (phi, i)->src;
810
811 if (bb == info->switch_bb
812 || (single_pred_p (bb)
813 && single_pred (bb) == info->switch_bb
814 && (!info->default_case_nonstandard
815 || empty_block_p (bb))))
816 {
817 tree reloc, val;
818 const char *reason = NULL;
819
820 val = gimple_phi_arg_def (phi, i);
821 if (!is_gimple_ip_invariant (val))
822 reason = "non-invariant value from a case";
823 else
824 {
825 reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
826 if ((flag_pic && reloc != null_pointer_node)
827 || (!flag_pic && reloc == NULL_TREE))
828 {
829 if (reloc)
830 reason
831 = "value from a case would need runtime relocations";
832 else
833 reason
834 = "value from a case is not a valid initializer";
835 }
836 }
837 if (reason)
838 {
839 /* For contiguous range, we can allow non-constant
840 or one that needs relocation, as long as it is
841 only reachable from the default case. */
842 if (bb == info->switch_bb)
843 bb = info->final_bb;
844 if (!info->contiguous_range || bb != info->default_bb)
845 {
846 info->reason = reason;
847 return false;
848 }
849
850 unsigned int branch_num = gimple_switch_num_labels (swtch);
851 for (unsigned int i = 1; i < branch_num; i++)
852 {
853 tree lab = CASE_LABEL (gimple_switch_label (swtch, i));
854 if (label_to_block (lab) == bb)
855 {
856 info->reason = reason;
857 return false;
858 }
859 }
860 info->default_case_nonstandard = true;
861 }
862 }
863 }
864 }
865
866 return true;
867}
868
869/* The following function allocates default_values, target_{in,out}_names and
870 constructors arrays. The last one is also populated with pointers to
871 vectors that will become constructors of new arrays. */
872
873static void
874create_temp_arrays (struct switch_conv_info *info)
875{
876 int i;
877
878 info->default_values = XCNEWVEC (tree, info->phi_count * 3);
879 /* ??? Macros do not support multi argument templates in their
880 argument list. We create a typedef to work around that problem. */
881 typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc;
882 info->constructors = XCNEWVEC (vec_constructor_elt_gc, info->phi_count);
883 info->target_inbound_names = info->default_values + info->phi_count;
884 info->target_outbound_names = info->target_inbound_names + info->phi_count;
885 for (i = 0; i < info->phi_count; i++)
886 vec_alloc (info->constructors[i], tree_to_uhwi (info->range_size) + 1);
887}
888
889/* Free the arrays created by create_temp_arrays(). The vectors that are
890 created by that function are not freed here, however, because they have
891 already become constructors and must be preserved. */
892
893static void
894free_temp_arrays (struct switch_conv_info *info)
895{
896 XDELETEVEC (info->constructors);
897 XDELETEVEC (info->default_values);
898}
899
900/* Populate the array of default values in the order of phi nodes.
901 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
902 if the range is non-contiguous or the default case has standard
903 structure, otherwise it is the first non-default case instead. */
904
905static void
906gather_default_values (tree default_case, struct switch_conv_info *info)
907{
908 gphi_iterator gsi;
909 basic_block bb = label_to_block (CASE_LABEL (default_case));
910 edge e;
911 int i = 0;
912
913 gcc_assert (CASE_LOW (default_case) == NULL_TREE
914 || info->default_case_nonstandard);
915
916 if (bb == info->final_bb)
917 e = find_edge (info->switch_bb, bb);
918 else
919 e = single_succ_edge (bb);
920
921 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
922 {
923 gphi *phi = gsi.phi ();
924 if (virtual_operand_p (gimple_phi_result (phi)))
925 continue;
926 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
927 gcc_assert (val);
928 info->default_values[i++] = val;
929 }
930}
931
932/* The following function populates the vectors in the constructors array with
933 future contents of the static arrays. The vectors are populated in the
934 order of phi nodes. SWTCH is the switch statement being converted. */
935
936static void
937build_constructors (gswitch *swtch, struct switch_conv_info *info)
938{
939 unsigned i, branch_num = gimple_switch_num_labels (swtch);
940 tree pos = info->range_min;
941 tree pos_one = build_int_cst (TREE_TYPE (pos), 1);
942
943 for (i = 1; i < branch_num; i++)
944 {
945 tree cs = gimple_switch_label (swtch, i);
946 basic_block bb = label_to_block (CASE_LABEL (cs));
947 edge e;
948 tree high;
949 gphi_iterator gsi;
950 int j;
951
952 if (bb == info->final_bb)
953 e = find_edge (info->switch_bb, bb);
954 else
955 e = single_succ_edge (bb);
956 gcc_assert (e);
957
958 while (tree_int_cst_lt (pos, CASE_LOW (cs)))
959 {
960 int k;
961 gcc_assert (!info->contiguous_range);
962 for (k = 0; k < info->phi_count; k++)
963 {
964 constructor_elt elt;
965
966 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
967 elt.value
968 = unshare_expr_without_location (info->default_values[k]);
969 info->constructors[k]->quick_push (elt);
970 }
971
972 pos = int_const_binop (PLUS_EXPR, pos, pos_one);
973 }
974 gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
975
976 j = 0;
977 if (CASE_HIGH (cs))
978 high = CASE_HIGH (cs);
979 else
980 high = CASE_LOW (cs);
981 for (gsi = gsi_start_phis (info->final_bb);
982 !gsi_end_p (gsi); gsi_next (&gsi))
983 {
984 gphi *phi = gsi.phi ();
985 if (virtual_operand_p (gimple_phi_result (phi)))
986 continue;
987 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
988 tree low = CASE_LOW (cs);
989 pos = CASE_LOW (cs);
990
991 do
992 {
993 constructor_elt elt;
994
995 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
996 elt.value = unshare_expr_without_location (val);
997 info->constructors[j]->quick_push (elt);
998
999 pos = int_const_binop (PLUS_EXPR, pos, pos_one);
1000 } while (!tree_int_cst_lt (high, pos)
1001 && tree_int_cst_lt (low, pos));
1002 j++;
1003 }
1004 }
1005}
1006
1007/* If all values in the constructor vector are the same, return the value.
1008 Otherwise return NULL_TREE. Not supposed to be called for empty
1009 vectors. */
1010
1011static tree
1012constructor_contains_same_values_p (vec<constructor_elt, va_gc> *vec)
1013{
1014 unsigned int i;
1015 tree prev = NULL_TREE;
1016 constructor_elt *elt;
1017
1018 FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
1019 {
1020 if (!prev)
1021 prev = elt->value;
1022 else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
1023 return NULL_TREE;
1024 }
1025 return prev;
1026}
1027
1028/* Return type which should be used for array elements, either TYPE's
1029 main variant or, for integral types, some smaller integral type
1030 that can still hold all the constants. */
1031
1032static tree
1033array_value_type (gswitch *swtch, tree type, int num,
1034 struct switch_conv_info *info)
1035{
1036 unsigned int i, len = vec_safe_length (info->constructors[num]);
1037 constructor_elt *elt;
1038 int sign = 0;
1039 tree smaller_type;
1040
1041 /* Types with alignments greater than their size can reach here, e.g. out of
1042 SRA. We couldn't use these as an array component type so get back to the
1043 main variant first, which, for our purposes, is fine for other types as
1044 well. */
1045
1046 type = TYPE_MAIN_VARIANT (type);
1047
1048 if (!INTEGRAL_TYPE_P (type))
1049 return type;
1050
1051 scalar_int_mode type_mode = SCALAR_INT_TYPE_MODE (type);
1052 scalar_int_mode mode = get_narrowest_mode (type_mode);
1053 if (GET_MODE_SIZE (type_mode) <= GET_MODE_SIZE (mode))
1054 return type;
1055
1056 if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32))
1057 return type;
1058
1059 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
1060 {
1061 wide_int cst;
1062
1063 if (TREE_CODE (elt->value) != INTEGER_CST)
1064 return type;
1065
1066 cst = wi::to_wide (elt->value);
1067 while (1)
1068 {
1069 unsigned int prec = GET_MODE_BITSIZE (mode);
1070 if (prec > HOST_BITS_PER_WIDE_INT)
1071 return type;
1072
1073 if (sign >= 0 && cst == wi::zext (cst, prec))
1074 {
1075 if (sign == 0 && cst == wi::sext (cst, prec))
1076 break;
1077 sign = 1;
1078 break;
1079 }
1080 if (sign <= 0 && cst == wi::sext (cst, prec))
1081 {
1082 sign = -1;
1083 break;
1084 }
1085
1086 if (sign == 1)
1087 sign = 0;
1088
1089 if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
1090 || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (type_mode))
1091 return type;
1092 }
1093 }
1094
1095 if (sign == 0)
1096 sign = TYPE_UNSIGNED (type) ? 1 : -1;
1097 smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
1098 if (GET_MODE_SIZE (type_mode)
1099 <= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (smaller_type)))
1100 return type;
1101
1102 return smaller_type;
1103}
1104
1105/* Create an appropriate array type and declaration and assemble a static array
1106 variable. Also create a load statement that initializes the variable in
1107 question with a value from the static array. SWTCH is the switch statement
1108 being converted, NUM is the index to arrays of constructors, default values
1109 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
1110 of the index of the new array, PHI is the phi node of the final BB that
1111 corresponds to the value that will be loaded from the created array. TIDX
1112 is an ssa name of a temporary variable holding the index for loads from the
1113 new array. */
1114
1115static void
1116build_one_array (gswitch *swtch, int num, tree arr_index_type,
1117 gphi *phi, tree tidx, struct switch_conv_info *info)
1118{
1119 tree name, cst;
1120 gimple *load;
1121 gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
1122 location_t loc = gimple_location (swtch);
1123
1124 gcc_assert (info->default_values[num]);
1125
1126 name = copy_ssa_name (PHI_RESULT (phi));
1127 info->target_inbound_names[num] = name;
1128
1129 cst = constructor_contains_same_values_p (info->constructors[num]);
1130 if (cst)
1131 load = gimple_build_assign (name, cst);
1132 else
1133 {
1134 tree array_type, ctor, decl, value_type, fetch, default_type;
1135
1136 default_type = TREE_TYPE (info->default_values[num]);
1137 value_type = array_value_type (swtch, default_type, num, info);
1138 array_type = build_array_type (value_type, arr_index_type);
1139 if (default_type != value_type)
1140 {
1141 unsigned int i;
1142 constructor_elt *elt;
1143
1144 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
1145 elt->value = fold_convert (value_type, elt->value);
1146 }
1147 ctor = build_constructor (array_type, info->constructors[num]);
1148 TREE_CONSTANT (ctor) = true;
1149 TREE_STATIC (ctor) = true;
1150
1151 decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
1152 TREE_STATIC (decl) = 1;
1153 DECL_INITIAL (decl) = ctor;
1154
1155 DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
1156 DECL_ARTIFICIAL (decl) = 1;
1157 DECL_IGNORED_P (decl) = 1;
1158 TREE_CONSTANT (decl) = 1;
1159 TREE_READONLY (decl) = 1;
1160 DECL_IGNORED_P (decl) = 1;
1161 varpool_node::finalize_decl (decl);
1162
1163 fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
1164 NULL_TREE);
1165 if (default_type != value_type)
1166 {
1167 fetch = fold_convert (default_type, fetch);
1168 fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
1169 true, GSI_SAME_STMT);
1170 }
1171 load = gimple_build_assign (name, fetch);
1172 }
1173
1174 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
1175 update_stmt (load);
1176 info->arr_ref_last = load;
1177}
1178
1179/* Builds and initializes static arrays initialized with values gathered from
1180 the SWTCH switch statement. Also creates statements that load values from
1181 them. */
1182
1183static void
1184build_arrays (gswitch *swtch, struct switch_conv_info *info)
1185{
1186 tree arr_index_type;
1187 tree tidx, sub, utype;
1188 gimple *stmt;
1189 gimple_stmt_iterator gsi;
1190 gphi_iterator gpi;
1191 int i;
1192 location_t loc = gimple_location (swtch);
1193
1194 gsi = gsi_for_stmt (swtch);
1195
1196 /* Make sure we do not generate arithmetics in a subrange. */
1197 utype = TREE_TYPE (info->index_expr);
1198 if (TREE_TYPE (utype))
1199 utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
1200 else
1201 utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
1202
1203 arr_index_type = build_index_type (info->range_size);
1204 tidx = make_ssa_name (utype);
1205 sub = fold_build2_loc (loc, MINUS_EXPR, utype,
1206 fold_convert_loc (loc, utype, info->index_expr),
1207 fold_convert_loc (loc, utype, info->range_min));
1208 sub = force_gimple_operand_gsi (&gsi, sub,
1209 false, NULL, true, GSI_SAME_STMT);
1210 stmt = gimple_build_assign (tidx, sub);
1211
1212 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1213 update_stmt (stmt);
1214 info->arr_ref_first = stmt;
1215
1216 for (gpi = gsi_start_phis (info->final_bb), i = 0;
1217 !gsi_end_p (gpi); gsi_next (&gpi))
1218 {
1219 gphi *phi = gpi.phi ();
1220 if (!virtual_operand_p (gimple_phi_result (phi)))
1221 build_one_array (swtch, i++, arr_index_type, phi, tidx, info);
1222 else
1223 {
1224 edge e;
1225 edge_iterator ei;
1226 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
1227 {
1228 if (e->dest == info->final_bb)
1229 break;
1230 if (!info->default_case_nonstandard
1231 || e->dest != info->default_bb)
1232 {
1233 e = single_succ_edge (e->dest);
1234 break;
1235 }
1236 }
1237 gcc_assert (e && e->dest == info->final_bb);
1238 info->target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e);
1239 }
1240 }
1241}
1242
1243/* Generates and appropriately inserts loads of default values at the position
1244 given by BSI. Returns the last inserted statement. */
1245
1246static gassign *
1247gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info)
1248{
1249 int i;
1250 gassign *assign = NULL;
1251
1252 for (i = 0; i < info->phi_count; i++)
1253 {
1254 tree name = copy_ssa_name (info->target_inbound_names[i]);
1255 info->target_outbound_names[i] = name;
1256 assign = gimple_build_assign (name, info->default_values[i]);
1257 gsi_insert_before (gsi, assign, GSI_SAME_STMT);
1258 update_stmt (assign);
1259 }
1260 return assign;
1261}
1262
1263/* Deletes the unused bbs and edges that now contain the switch statement and
1264 its empty branch bbs. BBD is the now dead BB containing the original switch
1265 statement, FINAL is the last BB of the converted switch statement (in terms
1266 of succession). */
1267
1268static void
1269prune_bbs (basic_block bbd, basic_block final, basic_block default_bb)
1270{
1271 edge_iterator ei;
1272 edge e;
1273
1274 for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
1275 {
1276 basic_block bb;
1277 bb = e->dest;
1278 remove_edge (e);
1279 if (bb != final && bb != default_bb)
1280 delete_basic_block (bb);
1281 }
1282 delete_basic_block (bbd);
1283}
1284
1285/* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
1286 from the basic block loading values from an array and E2F from the basic
1287 block loading default values. BBF is the last switch basic block (see the
1288 bbf description in the comment below). */
1289
1290static void
1291fix_phi_nodes (edge e1f, edge e2f, basic_block bbf,
1292 struct switch_conv_info *info)
1293{
1294 gphi_iterator gsi;
1295 int i;
1296
1297 for (gsi = gsi_start_phis (bbf), i = 0;
1298 !gsi_end_p (gsi); gsi_next (&gsi))
1299 {
1300 gphi *phi = gsi.phi ();
1301 tree inbound, outbound;
1302 if (virtual_operand_p (gimple_phi_result (phi)))
1303 inbound = outbound = info->target_vop;
1304 else
1305 {
1306 inbound = info->target_inbound_names[i];
1307 outbound = info->target_outbound_names[i++];
1308 }
1309 add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION);
1310 if (!info->default_case_nonstandard)
1311 add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION);
1312 }
1313}
1314
1315/* Creates a check whether the switch expression value actually falls into the
1316 range given by all the cases. If it does not, the temporaries are loaded
1317 with default values instead. SWTCH is the switch statement being converted.
1318
1319 bb0 is the bb with the switch statement, however, we'll end it with a
1320 condition instead.
1321
1322 bb1 is the bb to be used when the range check went ok. It is derived from
1323 the switch BB
1324
1325 bb2 is the bb taken when the expression evaluated outside of the range
1326 covered by the created arrays. It is populated by loads of default
1327 values.
1328
1329 bbF is a fall through for both bb1 and bb2 and contains exactly what
1330 originally followed the switch statement.
1331
1332 bbD contains the switch statement (in the end). It is unreachable but we
1333 still need to strip off its edges.
1334*/
1335
1336static void
1337gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
1338{
1339 tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
1340 tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
1341 tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
1342 glabel *label1, *label2, *label3;
1343 tree utype, tidx;
1344 tree bound;
1345
1346 gcond *cond_stmt;
1347
1348 gassign *last_assign = NULL;
1349 gimple_stmt_iterator gsi;
1350 basic_block bb0, bb1, bb2, bbf, bbd;
1351 edge e01 = NULL, e02, e21, e1d, e1f, e2f;
1352 location_t loc = gimple_location (swtch);
1353
1354 gcc_assert (info->default_values);
1355
1356 bb0 = gimple_bb (swtch);
1357
1358 tidx = gimple_assign_lhs (info->arr_ref_first);
1359 utype = TREE_TYPE (tidx);
1360
1361 /* (end of) block 0 */
1362 gsi = gsi_for_stmt (info->arr_ref_first);
1363 gsi_next (&gsi);
1364
1365 bound = fold_convert_loc (loc, utype, info->range_size);
1366 cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
1367 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1368 update_stmt (cond_stmt);
1369
1370 /* block 2 */
1371 if (!info->default_case_nonstandard)
1372 {
1373 label2 = gimple_build_label (label_decl2);
1374 gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
1375 last_assign = gen_def_assigns (&gsi, info);
1376 }
1377
1378 /* block 1 */
1379 label1 = gimple_build_label (label_decl1);
1380 gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
1381
1382 /* block F */
1383 gsi = gsi_start_bb (info->final_bb);
1384 label3 = gimple_build_label (label_decl3);
1385 gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
1386
1387 /* cfg fix */
1388 e02 = split_block (bb0, cond_stmt);
1389 bb2 = e02->dest;
1390
1391 if (info->default_case_nonstandard)
1392 {
1393 bb1 = bb2;
1394 bb2 = info->default_bb;
1395 e01 = e02;
1396 e01->flags = EDGE_TRUE_VALUE;
1397 e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE);
1398 edge e_default = find_edge (bb1, bb2);
1399 for (gphi_iterator gsi = gsi_start_phis (bb2);
1400 !gsi_end_p (gsi); gsi_next (&gsi))
1401 {
1402 gphi *phi = gsi.phi ();
1403 tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_default);
1404 add_phi_arg (phi, arg, e02,
1405 gimple_phi_arg_location_from_edge (phi, e_default));
1406 }
1407 /* Partially fix the dominator tree, if it is available. */
1408 if (dom_info_available_p (CDI_DOMINATORS))
1409 redirect_immediate_dominators (CDI_DOMINATORS, bb1, bb0);
1410 }
1411 else
1412 {
1413 e21 = split_block (bb2, last_assign);
1414 bb1 = e21->dest;
1415 remove_edge (e21);
1416 }
1417
1418 e1d = split_block (bb1, info->arr_ref_last);
1419 bbd = e1d->dest;
1420 remove_edge (e1d);
1421
1422 /* flags and profiles of the edge for in-range values */
1423 if (!info->default_case_nonstandard)
1424 e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
1425 e01->probability = info->default_prob.invert ();
1426
1427 /* flags and profiles of the edge taking care of out-of-range values */
1428 e02->flags &= ~EDGE_FALLTHRU;
1429 e02->flags |= EDGE_FALSE_VALUE;
1430 e02->probability = info->default_prob;
1431
1432 bbf = info->final_bb;
1433
1434 e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
1435 e1f->probability = profile_probability::always ();
1436
1437 if (info->default_case_nonstandard)
1438 e2f = NULL;
1439 else
1440 {
1441 e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
1442 e2f->probability = profile_probability::always ();
1443 }
1444
1445 /* frequencies of the new BBs */
1446 bb1->count = e01->count ();
1447 bb2->count = e02->count ();
1448 if (!info->default_case_nonstandard)
1449 bbf->count = e1f->count () + e2f->count ();
1450
1451 /* Tidy blocks that have become unreachable. */
1452 prune_bbs (bbd, info->final_bb,
1453 info->default_case_nonstandard ? info->default_bb : NULL);
1454
1455 /* Fixup the PHI nodes in bbF. */
1456 fix_phi_nodes (e1f, e2f, bbf, info);
1457
1458 /* Fix the dominator tree, if it is available. */
1459 if (dom_info_available_p (CDI_DOMINATORS))
1460 {
1461 vec<basic_block> bbs_to_fix_dom;
1462
1463 set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
1464 if (!info->default_case_nonstandard)
1465 set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
1466 if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
1467 /* If bbD was the immediate dominator ... */
1468 set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
1469
1470 bbs_to_fix_dom.create (3 + (bb2 != bbf));
1471 bbs_to_fix_dom.quick_push (bb0);
1472 bbs_to_fix_dom.quick_push (bb1);
1473 if (bb2 != bbf)
1474 bbs_to_fix_dom.quick_push (bb2);
1475 bbs_to_fix_dom.quick_push (bbf);
1476
1477 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
1478 bbs_to_fix_dom.release ();
1479 }
1480}
1481
1482/* The following function is invoked on every switch statement (the current one
1483 is given in SWTCH) and runs the individual phases of switch conversion on it
1484 one after another until one fails or the conversion is completed.
1485 Returns NULL on success, or a pointer to a string with the reason why the
1486 conversion failed. */
1487
1488static const char *
1489process_switch (gswitch *swtch)
1490{
1491 struct switch_conv_info info;
1492
1493 /* Group case labels so that we get the right results from the heuristics
1494 that decide on the code generation approach for this switch. */
1495 group_case_labels_stmt (swtch);
1496
1497 /* If this switch is now a degenerate case with only a default label,
1498 there is nothing left for us to do. */
1499 if (gimple_switch_num_labels (swtch) < 2)
1500 return "switch is a degenerate case";
1501
1502 collect_switch_conv_info (swtch, &info);
1503
1504 /* No error markers should reach here (they should be filtered out
1505 during gimplification). */
1506 gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node);
1507
1508 /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
1509 gcc_checking_assert (! TREE_CONSTANT (info.index_expr));
1510
1511 if (info.uniq <= MAX_CASE_BIT_TESTS)
1512 {
1513 if (expand_switch_using_bit_tests_p (info.range_size,
1514 info.uniq, info.count,
1515 optimize_bb_for_speed_p
1516 (gimple_bb (swtch))))
1517 {
1518 if (dump_file)
1519 fputs (" expanding as bit test is preferable\n", dump_file);
1520 emit_case_bit_tests (swtch, info.index_expr, info.range_min,
1521 info.range_size, info.range_max);
1522 loops_state_set (LOOPS_NEED_FIXUP);
1523 return NULL;
1524 }
1525
1526 if (info.uniq <= 2)
1527 /* This will be expanded as a decision tree in stmt.c:expand_case. */
1528 return " expanding as jumps is preferable";
1529 }
1530
1531 /* If there is no common successor, we cannot do the transformation. */
1532 if (! info.final_bb)
1533 return "no common successor to all case label target blocks found";
1534
1535 /* Check the case label values are within reasonable range: */
1536 if (!check_range (&info))
1537 {
1538 gcc_assert (info.reason);
1539 return info.reason;
1540 }
1541
1542 /* For all the cases, see whether they are empty, the assignments they
1543 represent constant and so on... */
1544 if (! check_all_empty_except_final (&info))
1545 {
1546 gcc_assert (info.reason);
1547 return info.reason;
1548 }
1549 if (!check_final_bb (swtch, &info))
1550 {
1551 gcc_assert (info.reason);
1552 return info.reason;
1553 }
1554
1555 /* At this point all checks have passed and we can proceed with the
1556 transformation. */
1557
1558 create_temp_arrays (&info);
1559 gather_default_values (info.default_case_nonstandard
1560 ? gimple_switch_label (swtch, 1)
1561 : gimple_switch_default_label (swtch), &info);
1562 build_constructors (swtch, &info);
1563
1564 build_arrays (swtch, &info); /* Build the static arrays and assignments. */
1565 gen_inbound_check (swtch, &info); /* Build the bounds check. */
1566
1567 /* Cleanup: */
1568 free_temp_arrays (&info);
1569 return NULL;
1570}
1571
1572/* The main function of the pass scans statements for switches and invokes
1573 process_switch on them. */
1574
1575namespace {
1576
1577const pass_data pass_data_convert_switch =
1578{
1579 GIMPLE_PASS, /* type */
1580 "switchconv", /* name */
1581 OPTGROUP_NONE, /* optinfo_flags */
1582 TV_TREE_SWITCH_CONVERSION, /* tv_id */
1583 ( PROP_cfg | PROP_ssa ), /* properties_required */
1584 0, /* properties_provided */
1585 0, /* properties_destroyed */
1586 0, /* todo_flags_start */
1587 TODO_update_ssa, /* todo_flags_finish */
1588};
1589
1590class pass_convert_switch : public gimple_opt_pass
1591{
1592public:
1593 pass_convert_switch (gcc::context *ctxt)
1594 : gimple_opt_pass (pass_data_convert_switch, ctxt)
1595 {}
1596
1597 /* opt_pass methods: */
1598 virtual bool gate (function *) { return flag_tree_switch_conversion != 0; }
1599 virtual unsigned int execute (function *);
1600
1601}; // class pass_convert_switch
1602
1603unsigned int
1604pass_convert_switch::execute (function *fun)
1605{
1606 basic_block bb;
1607
1608 FOR_EACH_BB_FN (bb, fun)
1609 {
1610 const char *failure_reason;
1611 gimple *stmt = last_stmt (bb);
1612 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1613 {
1614 if (dump_file)
1615 {
1616 expanded_location loc = expand_location (gimple_location (stmt));
1617
1618 fprintf (dump_file, "beginning to process the following "
1619 "SWITCH statement (%s:%d) : ------- \n",
1620 loc.file, loc.line);
1621 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1622 putc ('\n', dump_file);
1623 }
1624
1625 failure_reason = process_switch (as_a <gswitch *> (stmt));
1626 if (! failure_reason)
1627 {
1628 if (dump_file)
1629 {
1630 fputs ("Switch converted\n", dump_file);
1631 fputs ("--------------------------------\n", dump_file);
1632 }
1633
1634 /* Make no effort to update the post-dominator tree. It is actually not
1635 that hard for the transformations we have performed, but it is not
1636 supported by iterate_fix_dominators. */
1637 free_dominance_info (CDI_POST_DOMINATORS);
1638 }
1639 else
1640 {
1641 if (dump_file)
1642 {
1643 fputs ("Bailing out - ", dump_file);
1644 fputs (failure_reason, dump_file);
1645 fputs ("\n--------------------------------\n", dump_file);
1646 }
1647 }
1648 }
1649 }
1650
1651 return 0;
1652}
1653
1654} // anon namespace
1655
1656gimple_opt_pass *
1657make_pass_convert_switch (gcc::context *ctxt)
1658{
1659 return new pass_convert_switch (ctxt);
1660}
1661
1662struct case_node
1663{
1664 case_node *left; /* Left son in binary tree. */
1665 case_node *right; /* Right son in binary tree;
1666 also node chain. */
1667 case_node *parent; /* Parent of node in binary tree. */
1668 tree low; /* Lowest index value for this label. */
1669 tree high; /* Highest index value for this label. */
1670 basic_block case_bb; /* Label to jump to when node matches. */
1671 tree case_label; /* Label to jump to when node matches. */
1672 profile_probability prob; /* Probability of taking this case. */
1673 profile_probability subtree_prob; /* Probability of reaching subtree
1674 rooted at this node. */
1675};
1676
1677typedef case_node *case_node_ptr;
1678
1679static basic_block emit_case_nodes (basic_block, tree, case_node_ptr,
1680 basic_block, tree, profile_probability,
1681 tree, hash_map<tree, tree> *);
1682static bool node_has_low_bound (case_node_ptr, tree);
1683static bool node_has_high_bound (case_node_ptr, tree);
1684static bool node_is_bounded (case_node_ptr, tree);
1685
1686/* Return the smallest number of different values for which it is best to use a
1687 jump-table instead of a tree of conditional branches. */
1688
1689static unsigned int
1690case_values_threshold (void)
1691{
1692 unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
1693
1694 if (threshold == 0)
1695 threshold = targetm.case_values_threshold ();
1696
1697 return threshold;
1698}
1699
1700/* Reset the aux field of all outgoing edges of basic block BB. */
1701
1702static inline void
1703reset_out_edges_aux (basic_block bb)
1704{
1705 edge e;
1706 edge_iterator ei;
1707 FOR_EACH_EDGE (e, ei, bb->succs)
1708 e->aux = (void *) 0;
1709}
1710
1711/* Compute the number of case labels that correspond to each outgoing edge of
1712 STMT. Record this information in the aux field of the edge. */
1713
1714static inline void
1715compute_cases_per_edge (gswitch *stmt)
1716{
1717 basic_block bb = gimple_bb (stmt);
1718 reset_out_edges_aux (bb);
1719 int ncases = gimple_switch_num_labels (stmt);
1720 for (int i = ncases - 1; i >= 1; --i)
1721 {
1722 tree elt = gimple_switch_label (stmt, i);
1723 tree lab = CASE_LABEL (elt);
1724 basic_block case_bb = label_to_block_fn (cfun, lab);
1725 edge case_edge = find_edge (bb, case_bb);
1726 case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1);
1727 }
1728}
1729
1730/* Do the insertion of a case label into case_list. The labels are
1731 fed to us in descending order from the sorted vector of case labels used
1732 in the tree part of the middle end. So the list we construct is
1733 sorted in ascending order.
1734
1735 LABEL is the case label to be inserted. LOW and HIGH are the bounds
1736 against which the index is compared to jump to LABEL and PROB is the
1737 estimated probability LABEL is reached from the switch statement. */
1738
1739static case_node *
1740add_case_node (case_node *head, tree low, tree high, basic_block case_bb,
1741 tree case_label, profile_probability prob,
1742 object_allocator<case_node> &case_node_pool)
1743{
1744 case_node *r;
1745
1746 gcc_checking_assert (low);
1747 gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high)));
1748
1749 /* Add this label to the chain. */
1750 r = case_node_pool.allocate ();
1751 r->low = low;
1752 r->high = high;
1753 r->case_bb = case_bb;
1754 r->case_label = case_label;
1755 r->parent = r->left = NULL;
1756 r->prob = prob;
1757 r->subtree_prob = prob;
1758 r->right = head;
1759 return r;
1760}
1761
1762/* Dump ROOT, a list or tree of case nodes, to file. */
1763
1764static void
1765dump_case_nodes (FILE *f, case_node *root, int indent_step, int indent_level)
1766{
1767 if (root == 0)
1768 return;
1769 indent_level++;
1770
1771 dump_case_nodes (f, root->left, indent_step, indent_level);
1772
1773 fputs (";; ", f);
1774 fprintf (f, "%*s", indent_step * indent_level, "");
1775 print_dec (wi::to_wide (root->low), f, TYPE_SIGN (TREE_TYPE (root->low)));
1776 if (!tree_int_cst_equal (root->low, root->high))
1777 {
1778 fprintf (f, " ... ");
1779 print_dec (wi::to_wide (root->high), f,
1780 TYPE_SIGN (TREE_TYPE (root->high)));
1781 }
1782 fputs ("\n", f);
1783
1784 dump_case_nodes (f, root->right, indent_step, indent_level);
1785}
1786
1787/* Take an ordered list of case nodes
1788 and transform them into a near optimal binary tree,
1789 on the assumption that any target code selection value is as
1790 likely as any other.
1791
1792 The transformation is performed by splitting the ordered
1793 list into two equal sections plus a pivot. The parts are
1794 then attached to the pivot as left and right branches. Each
1795 branch is then transformed recursively. */
1796
1797static void
1798balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
1799{
1800 case_node_ptr np;
1801
1802 np = *head;
1803 if (np)
1804 {
1805 int i = 0;
1806 int ranges = 0;
1807 case_node_ptr *npp;
1808 case_node_ptr left;
1809
1810 /* Count the number of entries on branch. Also count the ranges. */
1811
1812 while (np)
1813 {
1814 if (!tree_int_cst_equal (np->low, np->high))
1815 ranges++;
1816
1817 i++;
1818 np = np->right;
1819 }
1820
1821 if (i > 2)
1822 {
1823 /* Split this list if it is long enough for that to help. */
1824 npp = head;
1825 left = *npp;
1826
1827 /* If there are just three nodes, split at the middle one. */
1828 if (i == 3)
1829 npp = &(*npp)->right;
1830 else
1831 {
1832 /* Find the place in the list that bisects the list's total cost,
1833 where ranges count as 2.
1834 Here I gets half the total cost. */
1835 i = (i + ranges + 1) / 2;
1836 while (1)
1837 {
1838 /* Skip nodes while their cost does not reach that amount. */
1839 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
1840 i--;
1841 i--;
1842 if (i <= 0)
1843 break;
1844 npp = &(*npp)->right;
1845 }
1846 }
1847 *head = np = *npp;
1848 *npp = 0;
1849 np->parent = parent;
1850 np->left = left;
1851
1852 /* Optimize each of the two split parts. */
1853 balance_case_nodes (&np->left, np);
1854 balance_case_nodes (&np->right, np);
1855 np->subtree_prob = np->prob;
1856 np->subtree_prob += np->left->subtree_prob;
1857 np->subtree_prob += np->right->subtree_prob;
1858 }
1859 else
1860 {
1861 /* Else leave this branch as one level,
1862 but fill in `parent' fields. */
1863 np = *head;
1864 np->parent = parent;
1865 np->subtree_prob = np->prob;
1866 for (; np->right; np = np->right)
1867 {
1868 np->right->parent = np;
1869 (*head)->subtree_prob += np->right->subtree_prob;
1870 }
1871 }
1872 }
1873}
1874
1875/* Return true if a switch should be expanded as a decision tree.
1876 RANGE is the difference between highest and lowest case.
1877 UNIQ is number of unique case node targets, not counting the default case.
1878 COUNT is the number of comparisons needed, not counting the default case. */
1879
1880static bool
1881expand_switch_as_decision_tree_p (tree range,
1882 unsigned int uniq ATTRIBUTE_UNUSED,
1883 unsigned int count)
1884{
1885 int max_ratio;
1886
1887 /* If neither casesi or tablejump is available, or flag_jump_tables
1888 over-ruled us, we really have no choice. */
1889 if (!targetm.have_casesi () && !targetm.have_tablejump ())
1890 return true;
1891 if (!flag_jump_tables)
1892 return true;
1893#ifndef ASM_OUTPUT_ADDR_DIFF_ELT
1894 if (flag_pic)
1895 return true;
1896#endif
1897
1898 /* If the switch is relatively small such that the cost of one
1899 indirect jump on the target are higher than the cost of a
1900 decision tree, go with the decision tree.
1901
1902 If range of values is much bigger than number of values,
1903 or if it is too large to represent in a HOST_WIDE_INT,
1904 make a sequence of conditional branches instead of a dispatch.
1905
1906 The definition of "much bigger" depends on whether we are
1907 optimizing for size or for speed. If the former, the maximum
1908 ratio range/count = 3, because this was found to be the optimal
1909 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
1910 10 is much older, and was probably selected after an extensive
1911 benchmarking investigation on numerous platforms. Or maybe it
1912 just made sense to someone at some point in the history of GCC,
1913 who knows... */
1914 max_ratio = optimize_insn_for_size_p () ? 3 : 10;
1915 if (count < case_values_threshold () || !tree_fits_uhwi_p (range)
1916 || compare_tree_int (range, max_ratio * count) > 0)
1917 return true;
1918
1919 return false;
1920}
1921
1922static void
1923fix_phi_operands_for_edge (edge e, hash_map<tree, tree> *phi_mapping)
1924{
1925 basic_block bb = e->dest;
1926 gphi_iterator gsi;
1927 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1928 {
1929 gphi *phi = gsi.phi ();
1930
1931 tree *definition = phi_mapping->get (gimple_phi_result (phi));
1932 if (definition)
1933 add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
1934 }
1935}
1936
1937
1938/* Add an unconditional jump to CASE_BB that happens in basic block BB. */
1939
1940static void
1941emit_jump (basic_block bb, basic_block case_bb,
1942 hash_map<tree, tree> *phi_mapping)
1943{
1944 edge e = single_succ_edge (bb);
1945 redirect_edge_succ (e, case_bb);
1946 fix_phi_operands_for_edge (e, phi_mapping);
1947}
1948
1949/* Generate a decision tree, switching on INDEX_EXPR and jumping to
1950 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
1951 DEFAULT_PROB is the estimated probability that it jumps to
1952 DEFAULT_LABEL.
1953
1954 We generate a binary decision tree to select the appropriate target
1955 code. */
1956
1957static void
1958emit_case_decision_tree (gswitch *s, tree index_expr, tree index_type,
1959 case_node_ptr case_list, basic_block default_bb,
1960 tree default_label, profile_probability default_prob,
1961 hash_map<tree, tree> *phi_mapping)
1962{
1963 balance_case_nodes (&case_list, NULL);
1964
1965 if (dump_file)
1966 dump_function_to_file (current_function_decl, dump_file, dump_flags);
1967 if (dump_file && (dump_flags & TDF_DETAILS))
1968 {
1969 int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
1970 fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
1971 dump_case_nodes (dump_file, case_list, indent_step, 0);
1972 }
1973
1974 basic_block bb = gimple_bb (s);
1975 gimple_stmt_iterator gsi = gsi_last_bb (bb);
1976 edge e;
1977 if (gsi_end_p (gsi))
1978 e = split_block_after_labels (bb);
1979 else
1980 {
1981 gsi_prev (&gsi);
1982 e = split_block (bb, gsi_stmt (gsi));
1983 }
1984 bb = split_edge (e);
1985
1986 bb = emit_case_nodes (bb, index_expr, case_list, default_bb, default_label,
1987 default_prob, index_type, phi_mapping);
1988
1989 if (bb)
1990 emit_jump (bb, default_bb, phi_mapping);
1991
1992 /* Remove all edges and do just an edge that will reach default_bb. */
1993 gsi = gsi_last_bb (gimple_bb (s));
1994 gsi_remove (&gsi, true);
1995}
1996
1997static void
1998record_phi_operand_mapping (const vec<basic_block> bbs, basic_block switch_bb,
1999 hash_map <tree, tree> *map)
2000{
2001 /* Record all PHI nodes that have to be fixed after conversion. */
2002 for (unsigned i = 0; i < bbs.length (); i++)
2003 {
2004 basic_block bb = bbs[i];
2005
2006 gphi_iterator gsi;
2007 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2008 {
2009 gphi *phi = gsi.phi ();
2010
2011 for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
2012 {
2013 basic_block phi_src_bb = gimple_phi_arg_edge (phi, i)->src;
2014 if (phi_src_bb == switch_bb)
2015 {
2016 tree def = gimple_phi_arg_def (phi, i);
2017 tree result = gimple_phi_result (phi);
2018 map->put (result, def);
2019 break;
2020 }
2021 }
2022 }
2023 }
2024}
2025
2026/* Attempt to expand gimple switch STMT to a decision tree. */
2027
2028static bool
2029try_switch_expansion (gswitch *stmt)
2030{
2031 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
2032 basic_block default_bb;
2033 unsigned int count, uniq;
2034 int i;
2035 int ncases = gimple_switch_num_labels (stmt);
2036 tree index_expr = gimple_switch_index (stmt);
2037 tree index_type = TREE_TYPE (index_expr);
2038 tree elt;
2039 basic_block bb = gimple_bb (stmt);
2040
2041 hash_map<tree, tree> phi_mapping;
2042 auto_vec<basic_block> case_bbs;
2043
2044 /* A list of case labels; it is first built as a list and it may then
2045 be rearranged into a nearly balanced binary tree. */
2046 case_node *case_list = 0;
2047
2048 /* A pool for case nodes. */
2049 object_allocator<case_node> case_node_pool ("struct case_node pool");
2050
2051 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
2052 expressions being INTEGER_CST. */
2053 gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
2054
2055 if (ncases == 1)
2056 return false;
2057
2058 /* Find the default case target label. */
2059 tree default_label = CASE_LABEL (gimple_switch_default_label (stmt));
2060 default_bb = label_to_block_fn (cfun, default_label);
2061 edge default_edge = find_edge (bb, default_bb);
2062 profile_probability default_prob = default_edge->probability;
2063 case_bbs.safe_push (default_bb);
2064
2065 /* Get upper and lower bounds of case values. */
2066 elt = gimple_switch_label (stmt, 1);
2067 minval = fold_convert (index_type, CASE_LOW (elt));
2068 elt = gimple_switch_label (stmt, ncases - 1);
2069 if (CASE_HIGH (elt))
2070 maxval = fold_convert (index_type, CASE_HIGH (elt));
2071 else
2072 maxval = fold_convert (index_type, CASE_LOW (elt));
2073
2074 /* Compute span of values. */
2075 range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
2076
2077 /* Listify the labels queue and gather some numbers to decide
2078 how to expand this switch. */
2079 uniq = 0;
2080 count = 0;
2081 hash_set<tree> seen_labels;
2082 compute_cases_per_edge (stmt);
2083
2084 for (i = ncases - 1; i >= 1; --i)
2085 {
2086 elt = gimple_switch_label (stmt, i);
2087 tree low = CASE_LOW (elt);
2088 gcc_assert (low);
2089 tree high = CASE_HIGH (elt);
2090 gcc_assert (!high || tree_int_cst_lt (low, high));
2091 tree lab = CASE_LABEL (elt);
2092
2093 /* Count the elements.
2094 A range counts double, since it requires two compares. */
2095 count++;
2096 if (high)
2097 count++;
2098
2099 /* If we have not seen this label yet, then increase the
2100 number of unique case node targets seen. */
2101 if (!seen_labels.add (lab))
2102 uniq++;
2103
2104 /* The bounds on the case range, LOW and HIGH, have to be converted
2105 to case's index type TYPE. Note that the original type of the
2106 case index in the source code is usually "lost" during
2107 gimplification due to type promotion, but the case labels retain the
2108 original type. Make sure to drop overflow flags. */
2109 low = fold_convert (index_type, low);
2110 if (TREE_OVERFLOW (low))
2111 low = wide_int_to_tree (index_type, wi::to_wide (low));
2112
2113 /* The canonical from of a case label in GIMPLE is that a simple case
2114 has an empty CASE_HIGH. For the casesi and tablejump expanders,
2115 the back ends want simple cases to have high == low. */
2116 if (!high)
2117 high = low;
2118 high = fold_convert (index_type, high);
2119 if (TREE_OVERFLOW (high))
2120 high = wide_int_to_tree (index_type, wi::to_wide (high));
2121
2122 basic_block case_bb = label_to_block_fn (cfun, lab);
2123 edge case_edge = find_edge (bb, case_bb);
2124 case_list = add_case_node (
2125 case_list, low, high, case_bb, lab,
2126 case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux)),
2127 case_node_pool);
2128
2129 case_bbs.safe_push (case_bb);
2130 }
2131 reset_out_edges_aux (bb);
2132 record_phi_operand_mapping (case_bbs, bb, &phi_mapping);
2133
2134 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
2135 destination, such as one with a default case only.
2136 It also removes cases that are out of range for the switch
2137 type, so we should never get a zero here. */
2138 gcc_assert (count > 0);
2139
2140 /* Decide how to expand this switch.
2141 The two options at this point are a dispatch table (casesi or
2142 tablejump) or a decision tree. */
2143
2144 if (expand_switch_as_decision_tree_p (range, uniq, count))
2145 {
2146 emit_case_decision_tree (stmt, index_expr, index_type, case_list,
2147 default_bb, default_label, default_prob,
2148 &phi_mapping);
2149 return true;
2150 }
2151
2152 return false;
2153}
2154
2155/* The main function of the pass scans statements for switches and invokes
2156 process_switch on them. */
2157
2158namespace {
2159
2160const pass_data pass_data_lower_switch =
2161{
2162 GIMPLE_PASS, /* type */
2163 "switchlower", /* name */
2164 OPTGROUP_NONE, /* optinfo_flags */
2165 TV_TREE_SWITCH_LOWERING, /* tv_id */
2166 ( PROP_cfg | PROP_ssa ), /* properties_required */
2167 0, /* properties_provided */
2168 0, /* properties_destroyed */
2169 0, /* todo_flags_start */
2170 TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
2171};
2172
2173class pass_lower_switch : public gimple_opt_pass
2174{
2175public:
2176 pass_lower_switch (gcc::context *ctxt)
2177 : gimple_opt_pass (pass_data_lower_switch, ctxt)
2178 {}
2179
2180 /* opt_pass methods: */
2181 virtual bool gate (function *) { return true; }
2182 virtual unsigned int execute (function *);
2183
2184}; // class pass_lower_switch
2185
2186unsigned int
2187pass_lower_switch::execute (function *fun)
2188{
2189 basic_block bb;
2190 bool expanded = false;
2191
2192 FOR_EACH_BB_FN (bb, fun)
2193 {
2194 gimple *stmt = last_stmt (bb);
2195 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
2196 {
2197 if (dump_file)
2198 {
2199 expanded_location loc = expand_location (gimple_location (stmt));
2200
2201 fprintf (dump_file, "beginning to process the following "
2202 "SWITCH statement (%s:%d) : ------- \n",
2203 loc.file, loc.line);
2204 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2205 putc ('\n', dump_file);
2206 }
2207
2208 expanded |= try_switch_expansion (as_a<gswitch *> (stmt));
2209 }
2210 }
2211
2212 if (expanded)
2213 {
2214 free_dominance_info (CDI_DOMINATORS);
2215 free_dominance_info (CDI_POST_DOMINATORS);
2216 mark_virtual_operands_for_renaming (cfun);
2217 }
2218
2219 return 0;
2220}
2221
2222} // anon namespace
2223
2224gimple_opt_pass *
2225make_pass_lower_switch (gcc::context *ctxt)
2226{
2227 return new pass_lower_switch (ctxt);
2228}
2229
2230/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
2231 PROB is the probability of jumping to LABEL. */
2232static basic_block
2233do_jump_if_equal (basic_block bb, tree op0, tree op1, basic_block label_bb,
2234 profile_probability prob, hash_map<tree, tree> *phi_mapping)
2235{
2236 gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE);
2237 gimple_stmt_iterator gsi = gsi_last_bb (bb);
2238 gsi_insert_before (&gsi, cond, GSI_SAME_STMT);
2239
2240 gcc_assert (single_succ_p (bb));
2241
2242 /* Make a new basic block where false branch will take place. */
2243 edge false_edge = split_block (bb, cond);
2244 false_edge->flags = EDGE_FALSE_VALUE;
2245 false_edge->probability = prob.invert ();
2246
2247 edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
2248 fix_phi_operands_for_edge (true_edge, phi_mapping);
2249 true_edge->probability = prob;
2250
2251 return false_edge->dest;
2252}
2253
2254/* Generate code to compare X with Y so that the condition codes are
2255 set and to jump to LABEL if the condition is true. If X is a
2256 constant and Y is not a constant, then the comparison is swapped to
2257 ensure that the comparison RTL has the canonical form.
2258
2259 UNSIGNEDP nonzero says that X and Y are unsigned; this matters if they
2260 need to be widened. UNSIGNEDP is also used to select the proper
2261 branch condition code.
2262
2263 If X and Y have mode BLKmode, then SIZE specifies the size of both X and Y.
2264
2265 MODE is the mode of the inputs (in case they are const_int).
2266
2267 COMPARISON is the rtl operator to compare with (EQ, NE, GT, etc.).
2268 It will be potentially converted into an unsigned variant based on
2269 UNSIGNEDP to select a proper jump instruction.
2270
2271 PROB is the probability of jumping to LABEL. */
2272
2273static basic_block
2274emit_cmp_and_jump_insns (basic_block bb, tree op0, tree op1,
2275 tree_code comparison, basic_block label_bb,
2276 profile_probability prob,
2277 hash_map<tree, tree> *phi_mapping)
2278{
2279 gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE);
2280 gimple_stmt_iterator gsi = gsi_last_bb (bb);
2281 gsi_insert_after (&gsi, cond, GSI_NEW_STMT);
2282
2283 gcc_assert (single_succ_p (bb));
2284
2285 /* Make a new basic block where false branch will take place. */
2286 edge false_edge = split_block (bb, cond);
2287 false_edge->flags = EDGE_FALSE_VALUE;
2288 false_edge->probability = prob.invert ();
2289
2290 edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
2291 fix_phi_operands_for_edge (true_edge, phi_mapping);
2292 true_edge->probability = prob;
2293
2294 return false_edge->dest;
2295}
2296
2297/* Computes the conditional probability of jumping to a target if the branch
2298 instruction is executed.
2299 TARGET_PROB is the estimated probability of jumping to a target relative
2300 to some basic block BB.
2301 BASE_PROB is the probability of reaching the branch instruction relative
2302 to the same basic block BB. */
2303
2304static inline profile_probability
2305conditional_probability (profile_probability target_prob,
2306 profile_probability base_prob)
2307{
2308 return target_prob / base_prob;
2309}
2310
2311/* Emit step-by-step code to select a case for the value of INDEX.
2312 The thus generated decision tree follows the form of the
2313 case-node binary tree NODE, whose nodes represent test conditions.
2314 INDEX_TYPE is the type of the index of the switch.
2315
2316 Care is taken to prune redundant tests from the decision tree
2317 by detecting any boundary conditions already checked by
2318 emitted rtx. (See node_has_high_bound, node_has_low_bound
2319 and node_is_bounded, above.)
2320
2321 Where the test conditions can be shown to be redundant we emit
2322 an unconditional jump to the target code. As a further
2323 optimization, the subordinates of a tree node are examined to
2324 check for bounded nodes. In this case conditional and/or
2325 unconditional jumps as a result of the boundary check for the
2326 current node are arranged to target the subordinates associated
2327 code for out of bound conditions on the current node.
2328
2329 We can assume that when control reaches the code generated here,
2330 the index value has already been compared with the parents
2331 of this node, and determined to be on the same side of each parent
2332 as this node is. Thus, if this node tests for the value 51,
2333 and a parent tested for 52, we don't need to consider
2334 the possibility of a value greater than 51. If another parent
2335 tests for the value 50, then this node need not test anything. */
2336
2337static basic_block
2338emit_case_nodes (basic_block bb, tree index, case_node_ptr node,
2339 basic_block default_bb, tree default_label,
2340 profile_probability default_prob, tree index_type,
2341 hash_map<tree, tree> *phi_mapping)
2342{
2343 /* If INDEX has an unsigned type, we must make unsigned branches. */
2344 profile_probability probability;
2345 profile_probability prob = node->prob, subtree_prob = node->subtree_prob;
2346
2347 /* See if our parents have already tested everything for us.
2348 If they have, emit an unconditional jump for this node. */
2349 if (node_is_bounded (node, index_type))
2350 {
2351 emit_jump (bb, node->case_bb, phi_mapping);
2352 return NULL;
2353 }
2354
2355 else if (tree_int_cst_equal (node->low, node->high))
2356 {
2357 probability = conditional_probability (prob, subtree_prob + default_prob);
2358 /* Node is single valued. First see if the index expression matches
2359 this node and then check our children, if any. */
2360 bb = do_jump_if_equal (bb, index, node->low, node->case_bb, probability,
2361 phi_mapping);
2362 /* Since this case is taken at this point, reduce its weight from
2363 subtree_weight. */
2364 subtree_prob -= prob;
2365 if (node->right != 0 && node->left != 0)
2366 {
2367 /* This node has children on both sides.
2368 Dispatch to one side or the other
2369 by comparing the index value with this node's value.
2370 If one subtree is bounded, check that one first,
2371 so we can avoid real branches in the tree. */
2372
2373 if (node_is_bounded (node->right, index_type))
2374 {
2375 probability
2376 = conditional_probability (node->right->prob,
2377 subtree_prob + default_prob);
2378 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2379 node->right->case_bb, probability,
2380 phi_mapping);
2381 bb = emit_case_nodes (bb, index, node->left, default_bb,
2382 default_label, default_prob, index_type,
2383 phi_mapping);
2384 }
2385
2386 else if (node_is_bounded (node->left, index_type))
2387 {
2388 probability
2389 = conditional_probability (node->left->prob,
2390 subtree_prob + default_prob);
2391 bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
2392 node->left->case_bb, probability,
2393 phi_mapping);
2394 bb = emit_case_nodes (bb, index, node->right, default_bb,
2395 default_label, default_prob, index_type,
2396 phi_mapping);
2397 }
2398
2399 /* If both children are single-valued cases with no
2400 children, finish up all the work. This way, we can save
2401 one ordered comparison. */
2402 else if (tree_int_cst_equal (node->right->low, node->right->high)
2403 && node->right->left == 0 && node->right->right == 0
2404 && tree_int_cst_equal (node->left->low, node->left->high)
2405 && node->left->left == 0 && node->left->right == 0)
2406 {
2407 /* Neither node is bounded. First distinguish the two sides;
2408 then emit the code for one side at a time. */
2409
2410 /* See if the value matches what the right hand side
2411 wants. */
2412 probability
2413 = conditional_probability (node->right->prob,
2414 subtree_prob + default_prob);
2415 bb = do_jump_if_equal (bb, index, node->right->low,
2416 node->right->case_bb, probability,
2417 phi_mapping);
2418
2419 /* See if the value matches what the left hand side
2420 wants. */
2421 probability
2422 = conditional_probability (node->left->prob,
2423 subtree_prob + default_prob);
2424 bb = do_jump_if_equal (bb, index, node->left->low,
2425 node->left->case_bb, probability,
2426 phi_mapping);
2427 }
2428
2429 else
2430 {
2431 /* Neither node is bounded. First distinguish the two sides;
2432 then emit the code for one side at a time. */
2433
2434 basic_block test_bb = split_edge (single_succ_edge (bb));
2435 redirect_edge_succ (single_pred_edge (test_bb),
2436 single_succ_edge (bb)->dest);
2437
2438 /* The default label could be reached either through the right
2439 subtree or the left subtree. Divide the probability
2440 equally. */
2441 probability
2442 = conditional_probability (node->right->subtree_prob
2443 + default_prob.apply_scale (1, 2),
2444 subtree_prob + default_prob);
2445 /* See if the value is on the right. */
2446 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2447 test_bb, probability, phi_mapping);
2448 default_prob = default_prob.apply_scale (1, 2);
2449
2450 /* Value must be on the left.
2451 Handle the left-hand subtree. */
2452 bb = emit_case_nodes (bb, index, node->left, default_bb,
2453 default_label, default_prob, index_type,
2454 phi_mapping);
2455 /* If left-hand subtree does nothing,
2456 go to default. */
2457
2458 if (bb && default_bb)
2459 emit_jump (bb, default_bb, phi_mapping);
2460
2461 /* Code branches here for the right-hand subtree. */
2462 bb = emit_case_nodes (test_bb, index, node->right, default_bb,
2463 default_label, default_prob, index_type,
2464 phi_mapping);
2465 }
2466 }
2467 else if (node->right != 0 && node->left == 0)
2468 {
2469 /* Here we have a right child but no left so we issue a conditional
2470 branch to default and process the right child.
2471
2472 Omit the conditional branch to default if the right child
2473 does not have any children and is single valued; it would
2474 cost too much space to save so little time. */
2475
2476 if (node->right->right || node->right->left
2477 || !tree_int_cst_equal (node->right->low, node->right->high))
2478 {
2479 if (!node_has_low_bound (node, index_type))
2480 {
2481 probability
2482 = conditional_probability (default_prob.apply_scale (1, 2),
2483 subtree_prob + default_prob);
2484 bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
2485 default_bb, probability,
2486 phi_mapping);
2487 default_prob = default_prob.apply_scale (1, 2);
2488 }
2489
2490 bb = emit_case_nodes (bb, index, node->right, default_bb,
2491 default_label, default_prob, index_type,
2492 phi_mapping);
2493 }
2494 else
2495 {
2496 probability
2497 = conditional_probability (node->right->subtree_prob,
2498 subtree_prob + default_prob);
2499 /* We cannot process node->right normally
2500 since we haven't ruled out the numbers less than
2501 this node's value. So handle node->right explicitly. */
2502 bb = do_jump_if_equal (bb, index, node->right->low,
2503 node->right->case_bb, probability,
2504 phi_mapping);
2505 }
2506 }
2507
2508 else if (node->right == 0 && node->left != 0)
2509 {
2510 /* Just one subtree, on the left. */
2511 if (node->left->left || node->left->right
2512 || !tree_int_cst_equal (node->left->low, node->left->high))
2513 {
2514 if (!node_has_high_bound (node, index_type))
2515 {
2516 probability
2517 = conditional_probability (default_prob.apply_scale (1, 2),
2518 subtree_prob + default_prob);
2519 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2520 default_bb, probability,
2521 phi_mapping);
2522 default_prob = default_prob.apply_scale (1, 2);
2523 }
2524
2525 bb = emit_case_nodes (bb, index, node->left, default_bb,
2526 default_label, default_prob, index_type,
2527 phi_mapping);
2528 }
2529 else
2530 {
2531 probability
2532 = conditional_probability (node->left->subtree_prob,
2533 subtree_prob + default_prob);
2534 /* We cannot process node->left normally
2535 since we haven't ruled out the numbers less than
2536 this node's value. So handle node->left explicitly. */
2537 do_jump_if_equal (bb, index, node->left->low, node->left->case_bb,
2538 probability, phi_mapping);
2539 }
2540 }
2541 }
2542 else
2543 {
2544 /* Node is a range. These cases are very similar to those for a single
2545 value, except that we do not start by testing whether this node
2546 is the one to branch to. */
2547
2548 if (node->right != 0 && node->left != 0)
2549 {
2550 /* Node has subtrees on both sides.
2551 If the right-hand subtree is bounded,
2552 test for it first, since we can go straight there.
2553 Otherwise, we need to make a branch in the control structure,
2554 then handle the two subtrees. */
2555 basic_block test_bb = NULL;
2556
2557 if (node_is_bounded (node->right, index_type))
2558 {
2559 /* Right hand node is fully bounded so we can eliminate any
2560 testing and branch directly to the target code. */
2561 probability
2562 = conditional_probability (node->right->subtree_prob,
2563 subtree_prob + default_prob);
2564 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2565 node->right->case_bb, probability,
2566 phi_mapping);
2567 }
2568 else
2569 {
2570 /* Right hand node requires testing.
2571 Branch to a label where we will handle it later. */
2572
2573 test_bb = split_edge (single_succ_edge (bb));
2574 redirect_edge_succ (single_pred_edge (test_bb),
2575 single_succ_edge (bb)->dest);
2576
2577 probability
2578 = conditional_probability (node->right->subtree_prob
2579 + default_prob.apply_scale (1, 2),
2580 subtree_prob + default_prob);
2581 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2582 test_bb, probability, phi_mapping);
2583 default_prob = default_prob.apply_scale (1, 2);
2584 }
2585
2586 /* Value belongs to this node or to the left-hand subtree. */
2587
2588 probability
2589 = conditional_probability (prob, subtree_prob + default_prob);
2590 bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
2591 node->case_bb, probability,
2592 phi_mapping);
2593
2594 /* Handle the left-hand subtree. */
2595 bb = emit_case_nodes (bb, index, node->left, default_bb,
2596 default_label, default_prob, index_type,
2597 phi_mapping);
2598
2599 /* If right node had to be handled later, do that now. */
2600 if (test_bb)
2601 {
2602 /* If the left-hand subtree fell through,
2603 don't let it fall into the right-hand subtree. */
2604 if (bb && default_bb)
2605 emit_jump (bb, default_bb, phi_mapping);
2606
2607 bb = emit_case_nodes (test_bb, index, node->right, default_bb,
2608 default_label, default_prob, index_type,
2609 phi_mapping);
2610 }
2611 }
2612
2613 else if (node->right != 0 && node->left == 0)
2614 {
2615 /* Deal with values to the left of this node,
2616 if they are possible. */
2617 if (!node_has_low_bound (node, index_type))
2618 {
2619 probability
2620 = conditional_probability (default_prob.apply_scale (1, 2),
2621 subtree_prob + default_prob);
2622 bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
2623 default_bb, probability,
2624 phi_mapping);
2625 default_prob = default_prob.apply_scale (1, 2);
2626 }
2627
2628 /* Value belongs to this node or to the right-hand subtree. */
2629
2630 probability
2631 = conditional_probability (prob, subtree_prob + default_prob);
2632 bb = emit_cmp_and_jump_insns (bb, index, node->high, LE_EXPR,
2633 node->case_bb, probability,
2634 phi_mapping);
2635
2636 bb = emit_case_nodes (bb, index, node->right, default_bb,
2637 default_label, default_prob, index_type,
2638 phi_mapping);
2639 }
2640
2641 else if (node->right == 0 && node->left != 0)
2642 {
2643 /* Deal with values to the right of this node,
2644 if they are possible. */
2645 if (!node_has_high_bound (node, index_type))
2646 {
2647 probability
2648 = conditional_probability (default_prob.apply_scale (1, 2),
2649 subtree_prob + default_prob);
2650 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2651 default_bb, probability,
2652 phi_mapping);
2653 default_prob = default_prob.apply_scale (1, 2);
2654 }
2655
2656 /* Value belongs to this node or to the left-hand subtree. */
2657
2658 probability
2659 = conditional_probability (prob, subtree_prob + default_prob);
2660 bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
2661 node->case_bb, probability,
2662 phi_mapping);
2663
2664 bb = emit_case_nodes (bb, index, node->left, default_bb,
2665 default_label, default_prob, index_type,
2666 phi_mapping);
2667 }
2668
2669 else
2670 {
2671 /* Node has no children so we check low and high bounds to remove
2672 redundant tests. Only one of the bounds can exist,
2673 since otherwise this node is bounded--a case tested already. */
2674 bool high_bound = node_has_high_bound (node, index_type);
2675 bool low_bound = node_has_low_bound (node, index_type);
2676
2677 if (!high_bound && low_bound)
2678 {
2679 probability
2680 = conditional_probability (default_prob,
2681 subtree_prob + default_prob);
2682 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2683 default_bb, probability,
2684 phi_mapping);
2685 }
2686
2687 else if (!low_bound && high_bound)
2688 {
2689 probability
2690 = conditional_probability (default_prob,
2691 subtree_prob + default_prob);
2692 bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
2693 default_bb, probability,
2694 phi_mapping);
2695 }
2696 else if (!low_bound && !high_bound)
2697 {
2698 tree lhs, rhs;
2699 generate_range_test (bb, index, node->low, node->high,
2700 &lhs, &rhs);
2701 probability
2702 = conditional_probability (default_prob,
2703 subtree_prob + default_prob);
2704 bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,
2705 default_bb, probability,
2706 phi_mapping);
2707 }
2708
2709 emit_jump (bb, node->case_bb, phi_mapping);
2710 return NULL;
2711 }
2712 }
2713
2714 return bb;
2715}
2716
2717/* Search the parent sections of the case node tree
2718 to see if a test for the lower bound of NODE would be redundant.
2719 INDEX_TYPE is the type of the index expression.
2720
2721 The instructions to generate the case decision tree are
2722 output in the same order as nodes are processed so it is
2723 known that if a parent node checks the range of the current
2724 node minus one that the current node is bounded at its lower
2725 span. Thus the test would be redundant. */
2726
2727static bool
2728node_has_low_bound (case_node_ptr node, tree index_type)
2729{
2730 tree low_minus_one;
2731 case_node_ptr pnode;
2732
2733 /* If the lower bound of this node is the lowest value in the index type,
2734 we need not test it. */
2735
2736 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
2737 return true;
2738
2739 /* If this node has a left branch, the value at the left must be less
2740 than that at this node, so it cannot be bounded at the bottom and
2741 we need not bother testing any further. */
2742
2743 if (node->left)
2744 return false;
2745
2746 low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), node->low,
2747 build_int_cst (TREE_TYPE (node->low), 1));
2748
2749 /* If the subtraction above overflowed, we can't verify anything.
2750 Otherwise, look for a parent that tests our value - 1. */
2751
2752 if (!tree_int_cst_lt (low_minus_one, node->low))
2753 return false;
2754
2755 for (pnode = node->parent; pnode; pnode = pnode->parent)
2756 if (tree_int_cst_equal (low_minus_one, pnode->high))
2757 return true;
2758
2759 return false;
2760}
2761
2762/* Search the parent sections of the case node tree
2763 to see if a test for the upper bound of NODE would be redundant.
2764 INDEX_TYPE is the type of the index expression.
2765
2766 The instructions to generate the case decision tree are
2767 output in the same order as nodes are processed so it is
2768 known that if a parent node checks the range of the current
2769 node plus one that the current node is bounded at its upper
2770 span. Thus the test would be redundant. */
2771
2772static bool
2773node_has_high_bound (case_node_ptr node, tree index_type)
2774{
2775 tree high_plus_one;
2776 case_node_ptr pnode;
2777
2778 /* If there is no upper bound, obviously no test is needed. */
2779
2780 if (TYPE_MAX_VALUE (index_type) == NULL)
2781 return true;
2782
2783 /* If the upper bound of this node is the highest value in the type
2784 of the index expression, we need not test against it. */
2785
2786 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
2787 return true;
2788
2789 /* If this node has a right branch, the value at the right must be greater
2790 than that at this node, so it cannot be bounded at the top and
2791 we need not bother testing any further. */
2792
2793 if (node->right)
2794 return false;
2795
2796 high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), node->high,
2797 build_int_cst (TREE_TYPE (node->high), 1));
2798
2799 /* If the addition above overflowed, we can't verify anything.
2800 Otherwise, look for a parent that tests our value + 1. */
2801
2802 if (!tree_int_cst_lt (node->high, high_plus_one))
2803 return false;
2804
2805 for (pnode = node->parent; pnode; pnode = pnode->parent)
2806 if (tree_int_cst_equal (high_plus_one, pnode->low))
2807 return true;
2808
2809 return false;
2810}
2811
2812/* Search the parent sections of the
2813 case node tree to see if both tests for the upper and lower
2814 bounds of NODE would be redundant. */
2815
2816static bool
2817node_is_bounded (case_node_ptr node, tree index_type)
2818{
2819 return (node_has_low_bound (node, index_type)
2820 && node_has_high_bound (node, index_type));
2821}
2822