]> git.ipfire.org Git - thirdparty/gcc.git/blame - gcc/tree-switch-conversion.c
[AArch64] Implement <su><maxmin>v2di3 pattern
[thirdparty/gcc.git] / gcc / tree-switch-conversion.c
CommitLineData
531b10fc
SB
1/* Lower GIMPLE_SWITCH expressions to something more efficient than
2 a jump table.
23a5b65a 3 Copyright (C) 2006-2014 Free Software Foundation, Inc.
b6e99746
MJ
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
531b10fc
SB
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 "tm.h"
29#include "line-map.h"
30#include "params.h"
31#include "flags.h"
32#include "tree.h"
d8a2d370
DN
33#include "varasm.h"
34#include "stor-layout.h"
60393bbc
AM
35#include "predict.h"
36#include "vec.h"
37#include "hashtab.h"
38#include "hash-set.h"
39#include "machmode.h"
40#include "hard-reg-set.h"
41#include "input.h"
42#include "function.h"
43#include "dominance.h"
44#include "cfg.h"
45#include "cfganal.h"
531b10fc 46#include "basic-block.h"
2fb9a547
AM
47#include "tree-ssa-alias.h"
48#include "internal-fn.h"
49#include "gimple-expr.h"
50#include "is-a.h"
18f429e2 51#include "gimple.h"
45b0be94 52#include "gimplify.h"
5be5c238 53#include "gimple-iterator.h"
18f429e2 54#include "gimplify-me.h"
442b4905 55#include "gimple-ssa.h"
c582198b
AM
56#include "hash-map.h"
57#include "plugin-api.h"
58#include "ipa-ref.h"
442b4905
AM
59#include "cgraph.h"
60#include "tree-cfg.h"
61#include "tree-phinodes.h"
d8a2d370 62#include "stringpool.h"
442b4905 63#include "tree-ssanames.h"
531b10fc
SB
64#include "tree-pass.h"
65#include "gimple-pretty-print.h"
a9e0d843 66#include "cfgloop.h"
7ee2468b
SB
67
68/* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
69 type in the GIMPLE type system that is language-independent? */
531b10fc
SB
70#include "langhooks.h"
71
72/* Need to include expr.h and optabs.h for lshift_cheap_p. */
73#include "expr.h"
b0710fe1 74#include "insn-codes.h"
531b10fc
SB
75#include "optabs.h"
76\f
77/* Maximum number of case bit tests.
78 FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and
79 targetm.case_values_threshold(), or be its own param. */
80#define MAX_CASE_BIT_TESTS 3
81
82/* Split the basic block at the statement pointed to by GSIP, and insert
83 a branch to the target basic block of E_TRUE conditional on tree
84 expression COND.
85
86 It is assumed that there is already an edge from the to-be-split
87 basic block to E_TRUE->dest block. This edge is removed, and the
88 profile information on the edge is re-used for the new conditional
89 jump.
90
91 The CFG is updated. The dominator tree will not be valid after
92 this transformation, but the immediate dominators are updated if
93 UPDATE_DOMINATORS is true.
94
95 Returns the newly created basic block. */
96
97static basic_block
98hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
99 tree cond, edge e_true,
100 bool update_dominators)
101{
102 tree tmp;
103 gimple cond_stmt;
104 edge e_false;
105 basic_block new_bb, split_bb = gsi_bb (*gsip);
106 bool dominated_e_true = false;
107
108 gcc_assert (e_true->src == split_bb);
109
110 if (update_dominators
111 && get_immediate_dominator (CDI_DOMINATORS, e_true->dest) == split_bb)
112 dominated_e_true = true;
113
114 tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
115 /*before=*/true, GSI_SAME_STMT);
116 cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
117 gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
118
119 e_false = split_block (split_bb, cond_stmt);
120 new_bb = e_false->dest;
121 redirect_edge_pred (e_true, split_bb);
122
123 e_true->flags &= ~EDGE_FALLTHRU;
124 e_true->flags |= EDGE_TRUE_VALUE;
125
126 e_false->flags &= ~EDGE_FALLTHRU;
127 e_false->flags |= EDGE_FALSE_VALUE;
128 e_false->probability = REG_BR_PROB_BASE - e_true->probability;
129 e_false->count = split_bb->count - e_true->count;
130 new_bb->count = e_false->count;
131
132 if (update_dominators)
133 {
134 if (dominated_e_true)
135 set_immediate_dominator (CDI_DOMINATORS, e_true->dest, split_bb);
136 set_immediate_dominator (CDI_DOMINATORS, e_false->dest, split_bb);
137 }
138
139 return new_bb;
140}
141
142
531b10fc
SB
143/* Return true if a switch should be expanded as a bit test.
144 RANGE is the difference between highest and lowest case.
145 UNIQ is number of unique case node targets, not counting the default case.
146 COUNT is the number of comparisons needed, not counting the default case. */
147
148static bool
149expand_switch_using_bit_tests_p (tree range,
150 unsigned int uniq,
72798784 151 unsigned int count, bool speed_p)
531b10fc
SB
152{
153 return (((uniq == 1 && count >= 3)
154 || (uniq == 2 && count >= 5)
155 || (uniq == 3 && count >= 6))
72798784 156 && lshift_cheap_p (speed_p)
531b10fc
SB
157 && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
158 && compare_tree_int (range, 0) > 0);
159}
160\f
161/* Implement switch statements with bit tests
162
163A GIMPLE switch statement can be expanded to a short sequence of bit-wise
164comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
165where CST and MINVAL are integer constants. This is better than a series
166of compare-and-banch insns in some cases, e.g. we can implement:
167
168 if ((x==4) || (x==6) || (x==9) || (x==11))
169
170as a single bit test:
171
172 if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
173
174This transformation is only applied if the number of case targets is small,
34540577 175if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are
531b10fc
SB
176performed in "word_mode".
177
178The following example shows the code the transformation generates:
179
180 int bar(int x)
181 {
182 switch (x)
183 {
184 case '0': case '1': case '2': case '3': case '4':
185 case '5': case '6': case '7': case '8': case '9':
186 case 'A': case 'B': case 'C': case 'D': case 'E':
187 case 'F':
188 return 1;
189 }
190 return 0;
191 }
192
193==>
194
195 bar (int x)
196 {
197 tmp1 = x - 48;
198 if (tmp1 > (70 - 48)) goto L2;
199 tmp2 = 1 << tmp1;
200 tmp3 = 0b11111100000001111111111;
201 if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
202 L1:
203 return 1;
204 L2:
205 return 0;
206 }
207
208TODO: There are still some improvements to this transformation that could
209be implemented:
210
211* A narrower mode than word_mode could be used if that is cheaper, e.g.
212 for x86_64 where a narrower-mode shift may result in smaller code.
213
214* The compounded constant could be shifted rather than the one. The
215 test would be either on the sign bit or on the least significant bit,
216 depending on the direction of the shift. On some machines, the test
217 for the branch would be free if the bit to test is already set by the
218 shift operation.
219
220This transformation was contributed by Roger Sayle, see this e-mail:
221 http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
222*/
223
224/* A case_bit_test represents a set of case nodes that may be
225 selected from using a bit-wise comparison. HI and LO hold
226 the integer to be tested against, TARGET_EDGE contains the
227 edge to the basic block to jump to upon success and BITS
228 counts the number of case nodes handled by this test,
229 typically the number of bits set in HI:LO. The LABEL field
230 is used to quickly identify all cases in this set without
231 looking at label_to_block for every case label. */
232
233struct case_bit_test
234{
aa79a1e1 235 wide_int mask;
531b10fc
SB
236 edge target_edge;
237 tree label;
238 int bits;
239};
240
241/* Comparison function for qsort to order bit tests by decreasing
242 probability of execution. Our best guess comes from a measured
243 profile. If the profile counts are equal, break even on the
244 number of case nodes, i.e. the node with the most cases gets
245 tested first.
246
247 TODO: Actually this currently runs before a profile is available.
248 Therefore the case-as-bit-tests transformation should be done
249 later in the pass pipeline, or something along the lines of
250 "Efficient and effective branch reordering using profile data"
251 (Yang et. al., 2002) should be implemented (although, how good
252 is a paper is called "Efficient and effective ..." when the
253 latter is implied by the former, but oh well...). */
254
255static int
256case_bit_test_cmp (const void *p1, const void *p2)
257{
258 const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
259 const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
260
261 if (d2->target_edge->count != d1->target_edge->count)
262 return d2->target_edge->count - d1->target_edge->count;
263 if (d2->bits != d1->bits)
264 return d2->bits - d1->bits;
265
266 /* Stabilize the sort. */
267 return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (d1->label);
268}
269
270/* Expand a switch statement by a short sequence of bit-wise
271 comparisons. "switch(x)" is effectively converted into
272 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
273 integer constants.
274
275 INDEX_EXPR is the value being switched on.
276
277 MINVAL is the lowest case value of in the case nodes,
278 and RANGE is highest value minus MINVAL. MINVAL and RANGE
279 are not guaranteed to be of the same type as INDEX_EXPR
280 (the gimplifier doesn't change the type of case label values,
281 and MINVAL and RANGE are derived from those values).
aa79a1e1 282 MAXVAL is MINVAL + RANGE.
531b10fc
SB
283
284 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
285 node targets. */
286
287static void
288emit_case_bit_tests (gimple swtch, tree index_expr,
aa79a1e1 289 tree minval, tree range, tree maxval)
531b10fc
SB
290{
291 struct case_bit_test test[MAX_CASE_BIT_TESTS];
292 unsigned int i, j, k;
293 unsigned int count;
294
295 basic_block switch_bb = gimple_bb (swtch);
296 basic_block default_bb, new_default_bb, new_bb;
297 edge default_edge;
298 bool update_dom = dom_info_available_p (CDI_DOMINATORS);
299
6e1aa848 300 vec<basic_block> bbs_to_fix_dom = vNULL;
531b10fc
SB
301
302 tree index_type = TREE_TYPE (index_expr);
303 tree unsigned_index_type = unsigned_type_for (index_type);
304 unsigned int branch_num = gimple_switch_num_labels (swtch);
305
306 gimple_stmt_iterator gsi;
307 gimple shift_stmt;
308
309 tree idx, tmp, csui;
310 tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
311 tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
312 tree word_mode_one = fold_convert (word_type_node, integer_one_node);
aa79a1e1
JJ
313 int prec = TYPE_PRECISION (word_type_node);
314 wide_int wone = wi::one (prec);
531b10fc
SB
315
316 memset (&test, 0, sizeof (test));
317
318 /* Get the edge for the default case. */
fd8d363e 319 tmp = gimple_switch_default_label (swtch);
531b10fc
SB
320 default_bb = label_to_block (CASE_LABEL (tmp));
321 default_edge = find_edge (switch_bb, default_bb);
322
323 /* Go through all case labels, and collect the case labels, profile
324 counts, and other information we need to build the branch tests. */
325 count = 0;
326 for (i = 1; i < branch_num; i++)
327 {
328 unsigned int lo, hi;
329 tree cs = gimple_switch_label (swtch, i);
330 tree label = CASE_LABEL (cs);
8166ff4d 331 edge e = find_edge (switch_bb, label_to_block (label));
531b10fc 332 for (k = 0; k < count; k++)
8166ff4d 333 if (e == test[k].target_edge)
531b10fc
SB
334 break;
335
336 if (k == count)
337 {
531b10fc 338 gcc_checking_assert (count < MAX_CASE_BIT_TESTS);
aa79a1e1 339 test[k].mask = wi::zero (prec);
531b10fc
SB
340 test[k].target_edge = e;
341 test[k].label = label;
342 test[k].bits = 1;
343 count++;
344 }
345 else
346 test[k].bits++;
347
386b1f1f
RS
348 lo = tree_to_uhwi (int_const_binop (MINUS_EXPR,
349 CASE_LOW (cs), minval));
531b10fc
SB
350 if (CASE_HIGH (cs) == NULL_TREE)
351 hi = lo;
352 else
386b1f1f
RS
353 hi = tree_to_uhwi (int_const_binop (MINUS_EXPR,
354 CASE_HIGH (cs), minval));
531b10fc
SB
355
356 for (j = lo; j <= hi; j++)
aa79a1e1 357 test[k].mask |= wi::lshift (wone, j);
531b10fc
SB
358 }
359
c3284718 360 qsort (test, count, sizeof (*test), case_bit_test_cmp);
531b10fc 361
aa79a1e1
JJ
362 /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
363 the minval subtractions, but it might make the mask constants more
364 expensive. So, compare the costs. */
365 if (compare_tree_int (minval, 0) > 0
366 && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
367 {
368 int cost_diff;
369 HOST_WIDE_INT m = tree_to_uhwi (minval);
370 rtx reg = gen_raw_REG (word_mode, 10000);
371 bool speed_p = optimize_bb_for_speed_p (gimple_bb (swtch));
372 cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg,
373 GEN_INT (-m)), speed_p);
374 for (i = 0; i < count; i++)
375 {
376 rtx r = immed_wide_int_const (test[i].mask, word_mode);
377 cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r), speed_p);
378 r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode);
379 cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r), speed_p);
380 }
381 if (cost_diff > 0)
382 {
383 for (i = 0; i < count; i++)
384 test[i].mask = wi::lshift (test[i].mask, m);
385 minval = build_zero_cst (TREE_TYPE (minval));
386 range = maxval;
387 }
388 }
389
531b10fc
SB
390 /* We generate two jumps to the default case label.
391 Split the default edge, so that we don't have to do any PHI node
392 updating. */
393 new_default_bb = split_edge (default_edge);
394
395 if (update_dom)
396 {
9771b263
DN
397 bbs_to_fix_dom.create (10);
398 bbs_to_fix_dom.quick_push (switch_bb);
399 bbs_to_fix_dom.quick_push (default_bb);
400 bbs_to_fix_dom.quick_push (new_default_bb);
531b10fc
SB
401 }
402
403 /* Now build the test-and-branch code. */
404
405 gsi = gsi_last_bb (switch_bb);
406
d9e408de
TV
407 /* idx = (unsigned)x - minval. */
408 idx = fold_convert (unsigned_index_type, index_expr);
409 idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx,
410 fold_convert (unsigned_index_type, minval));
531b10fc
SB
411 idx = force_gimple_operand_gsi (&gsi, idx,
412 /*simple=*/true, NULL_TREE,
413 /*before=*/true, GSI_SAME_STMT);
414
415 /* if (idx > range) goto default */
416 range = force_gimple_operand_gsi (&gsi,
417 fold_convert (unsigned_index_type, range),
418 /*simple=*/true, NULL_TREE,
419 /*before=*/true, GSI_SAME_STMT);
420 tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
421 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_edge, update_dom);
422 if (update_dom)
9771b263 423 bbs_to_fix_dom.quick_push (new_bb);
531b10fc
SB
424 gcc_assert (gimple_bb (swtch) == new_bb);
425 gsi = gsi_last_bb (new_bb);
426
427 /* Any blocks dominated by the GIMPLE_SWITCH, but that are not successors
428 of NEW_BB, are still immediately dominated by SWITCH_BB. Make it so. */
429 if (update_dom)
430 {
9771b263 431 vec<basic_block> dom_bbs;
531b10fc
SB
432 basic_block dom_son;
433
434 dom_bbs = get_dominated_by (CDI_DOMINATORS, new_bb);
9771b263 435 FOR_EACH_VEC_ELT (dom_bbs, i, dom_son)
531b10fc
SB
436 {
437 edge e = find_edge (new_bb, dom_son);
438 if (e && single_pred_p (e->dest))
439 continue;
440 set_immediate_dominator (CDI_DOMINATORS, dom_son, switch_bb);
9771b263 441 bbs_to_fix_dom.safe_push (dom_son);
531b10fc 442 }
9771b263 443 dom_bbs.release ();
531b10fc
SB
444 }
445
446 /* csui = (1 << (word_mode) idx) */
83d5977e 447 csui = make_ssa_name (word_type_node, NULL);
531b10fc
SB
448 tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one,
449 fold_convert (word_type_node, idx));
450 tmp = force_gimple_operand_gsi (&gsi, tmp,
451 /*simple=*/false, NULL_TREE,
452 /*before=*/true, GSI_SAME_STMT);
453 shift_stmt = gimple_build_assign (csui, tmp);
531b10fc
SB
454 gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
455 update_stmt (shift_stmt);
456
457 /* for each unique set of cases:
458 if (const & csui) goto target */
459 for (k = 0; k < count; k++)
460 {
aa79a1e1 461 tmp = wide_int_to_tree (word_type_node, test[k].mask);
531b10fc
SB
462 tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp);
463 tmp = force_gimple_operand_gsi (&gsi, tmp,
464 /*simple=*/true, NULL_TREE,
465 /*before=*/true, GSI_SAME_STMT);
466 tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
467 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_edge,
468 update_dom);
469 if (update_dom)
9771b263 470 bbs_to_fix_dom.safe_push (new_bb);
531b10fc
SB
471 gcc_assert (gimple_bb (swtch) == new_bb);
472 gsi = gsi_last_bb (new_bb);
473 }
474
475 /* We should have removed all edges now. */
476 gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
477
478 /* If nothing matched, go to the default label. */
479 make_edge (gsi_bb (gsi), new_default_bb, EDGE_FALLTHRU);
480
481 /* The GIMPLE_SWITCH is now redundant. */
482 gsi_remove (&gsi, true);
483
484 if (update_dom)
485 {
486 /* Fix up the dominator tree. */
487 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
9771b263 488 bbs_to_fix_dom.release ();
531b10fc
SB
489 }
490}
491\f
b6e99746
MJ
492/*
493 Switch initialization conversion
494
495The following pass changes simple initializations of scalars in a switch
fade902a
SB
496statement into initializations from a static array. Obviously, the values
497must be constant and known at compile time and a default branch must be
b6e99746
MJ
498provided. For example, the following code:
499
500 int a,b;
501
502 switch (argc)
503 {
504 case 1:
505 case 2:
506 a_1 = 8;
507 b_1 = 6;
508 break;
509 case 3:
510 a_2 = 9;
511 b_2 = 5;
512 break;
513 case 12:
514 a_3 = 10;
515 b_3 = 4;
516 break;
517 default:
518 a_4 = 16;
519 b_4 = 1;
886cd84f 520 break;
b6e99746
MJ
521 }
522 a_5 = PHI <a_1, a_2, a_3, a_4>
523 b_5 = PHI <b_1, b_2, b_3, b_4>
524
525
526is changed into:
527
528 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
529 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
530 16, 16, 10};
531
532 if (((unsigned) argc) - 1 < 11)
533 {
534 a_6 = CSWTCH02[argc - 1];
535 b_6 = CSWTCH01[argc - 1];
536 }
537 else
538 {
539 a_7 = 16;
540 b_7 = 1;
541 }
886cd84f
SB
542 a_5 = PHI <a_6, a_7>
543 b_b = PHI <b_6, b_7>
b6e99746
MJ
544
545There are further constraints. Specifically, the range of values across all
546case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
531b10fc 547eight) times the number of the actual switch branches.
b6e99746 548
531b10fc
SB
549This transformation was contributed by Martin Jambor, see this e-mail:
550 http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
b6e99746
MJ
551
552/* The main structure of the pass. */
553struct switch_conv_info
554{
886cd84f 555 /* The expression used to decide the switch branch. */
b6e99746
MJ
556 tree index_expr;
557
886cd84f
SB
558 /* The following integer constants store the minimum and maximum value
559 covered by the case labels. */
b6e99746 560 tree range_min;
886cd84f 561 tree range_max;
b6e99746 562
886cd84f
SB
563 /* The difference between the above two numbers. Stored here because it
564 is used in all the conversion heuristics, as well as for some of the
565 transformation, and it is expensive to re-compute it all the time. */
b6e99746
MJ
566 tree range_size;
567
886cd84f 568 /* Basic block that contains the actual GIMPLE_SWITCH. */
b6e99746
MJ
569 basic_block switch_bb;
570
886cd84f
SB
571 /* Basic block that is the target of the default case. */
572 basic_block default_bb;
573
574 /* The single successor block of all branches out of the GIMPLE_SWITCH,
575 if such a block exists. Otherwise NULL. */
b6e99746
MJ
576 basic_block final_bb;
577
886cd84f
SB
578 /* The probability of the default edge in the replaced switch. */
579 int default_prob;
580
581 /* The count of the default edge in the replaced switch. */
582 gcov_type default_count;
583
584 /* Combined count of all other (non-default) edges in the replaced switch. */
585 gcov_type other_count;
586
b6e99746
MJ
587 /* Number of phi nodes in the final bb (that we'll be replacing). */
588 int phi_count;
589
b1ae1681 590 /* Array of default values, in the same order as phi nodes. */
b6e99746
MJ
591 tree *default_values;
592
593 /* Constructors of new static arrays. */
9771b263 594 vec<constructor_elt, va_gc> **constructors;
b6e99746
MJ
595
596 /* Array of ssa names that are initialized with a value from a new static
597 array. */
598 tree *target_inbound_names;
599
600 /* Array of ssa names that are initialized with the default value if the
601 switch expression is out of range. */
602 tree *target_outbound_names;
603
b1ae1681
MJ
604 /* The first load statement that loads a temporary from a new static array.
605 */
726a989a 606 gimple arr_ref_first;
b6e99746
MJ
607
608 /* The last load statement that loads a temporary from a new static array. */
726a989a 609 gimple arr_ref_last;
b6e99746
MJ
610
611 /* String reason why the case wasn't a good candidate that is written to the
612 dump file, if there is one. */
613 const char *reason;
8e97bc2b
JJ
614
615 /* Parameters for expand_switch_using_bit_tests. Should be computed
616 the same way as in expand_case. */
886cd84f
SB
617 unsigned int uniq;
618 unsigned int count;
b6e99746
MJ
619};
620
886cd84f 621/* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
b6e99746 622
886cd84f
SB
623static void
624collect_switch_conv_info (gimple swtch, struct switch_conv_info *info)
b6e99746 625{
726a989a 626 unsigned int branch_num = gimple_switch_num_labels (swtch);
886cd84f
SB
627 tree min_case, max_case;
628 unsigned int count, i;
629 edge e, e_default;
630 edge_iterator ei;
631
632 memset (info, 0, sizeof (*info));
b6e99746
MJ
633
634 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
fd8d363e
SB
635 is a default label which is the first in the vector.
636 Collect the bits we can deduce from the CFG. */
886cd84f
SB
637 info->index_expr = gimple_switch_index (swtch);
638 info->switch_bb = gimple_bb (swtch);
639 info->default_bb =
fd8d363e 640 label_to_block (CASE_LABEL (gimple_switch_default_label (swtch)));
886cd84f
SB
641 e_default = find_edge (info->switch_bb, info->default_bb);
642 info->default_prob = e_default->probability;
643 info->default_count = e_default->count;
644 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
645 if (e != e_default)
646 info->other_count += e->count;
b6e99746 647
886cd84f 648 /* See if there is one common successor block for all branch
866f20d6
RB
649 targets. If it exists, record it in FINAL_BB.
650 Start with the destination of the default case as guess
651 or its destination in case it is a forwarder block. */
652 if (! single_pred_p (e_default->dest))
653 info->final_bb = e_default->dest;
654 else if (single_succ_p (e_default->dest)
655 && ! single_pred_p (single_succ (e_default->dest)))
656 info->final_bb = single_succ (e_default->dest);
657 /* Require that all switch destinations are either that common
658 FINAL_BB or a forwarder to it. */
886cd84f
SB
659 if (info->final_bb)
660 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
661 {
662 if (e->dest == info->final_bb)
663 continue;
664
665 if (single_pred_p (e->dest)
666 && single_succ_p (e->dest)
667 && single_succ (e->dest) == info->final_bb)
668 continue;
669
670 info->final_bb = NULL;
671 break;
672 }
673
674 /* Get upper and lower bounds of case values, and the covered range. */
675 min_case = gimple_switch_label (swtch, 1);
726a989a 676 max_case = gimple_switch_label (swtch, branch_num - 1);
886cd84f
SB
677
678 info->range_min = CASE_LOW (min_case);
b6e99746 679 if (CASE_HIGH (max_case) != NULL_TREE)
886cd84f 680 info->range_max = CASE_HIGH (max_case);
b6e99746 681 else
886cd84f
SB
682 info->range_max = CASE_LOW (max_case);
683
684 info->range_size =
685 int_const_binop (MINUS_EXPR, info->range_max, info->range_min);
b6e99746 686
886cd84f
SB
687 /* Get a count of the number of case labels. Single-valued case labels
688 simply count as one, but a case range counts double, since it may
689 require two compares if it gets lowered as a branching tree. */
690 count = 0;
691 for (i = 1; i < branch_num; i++)
692 {
693 tree elt = gimple_switch_label (swtch, i);
694 count++;
695 if (CASE_HIGH (elt)
696 && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
697 count++;
698 }
699 info->count = count;
700
701 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
702 block. Assume a CFG cleanup would have already removed degenerate
703 switch statements, this allows us to just use EDGE_COUNT. */
704 info->uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
705}
b6e99746 706
886cd84f
SB
707/* Checks whether the range given by individual case statements of the SWTCH
708 switch statement isn't too big and whether the number of branches actually
709 satisfies the size of the new array. */
b6e99746 710
886cd84f
SB
711static bool
712check_range (struct switch_conv_info *info)
713{
fade902a 714 gcc_assert (info->range_size);
cc269bb6 715 if (!tree_fits_uhwi_p (info->range_size))
b6e99746 716 {
fade902a 717 info->reason = "index range way too large or otherwise unusable";
b6e99746
MJ
718 return false;
719 }
720
7d362f6c 721 if (tree_to_uhwi (info->range_size)
886cd84f 722 > ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO))
b6e99746 723 {
fade902a 724 info->reason = "the maximum range-branch ratio exceeded";
b6e99746
MJ
725 return false;
726 }
727
728 return true;
729}
730
886cd84f 731/* Checks whether all but the FINAL_BB basic blocks are empty. */
b6e99746
MJ
732
733static bool
886cd84f 734check_all_empty_except_final (struct switch_conv_info *info)
b6e99746 735{
b6e99746 736 edge e;
886cd84f 737 edge_iterator ei;
b6e99746 738
886cd84f 739 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
b6e99746 740 {
886cd84f
SB
741 if (e->dest == info->final_bb)
742 continue;
b6e99746 743
886cd84f 744 if (!empty_block_p (e->dest))
b6e99746 745 {
fade902a 746 info->reason = "bad case - a non-final BB not empty";
b6e99746
MJ
747 return false;
748 }
b6e99746
MJ
749 }
750
751 return true;
752}
753
754/* This function checks whether all required values in phi nodes in final_bb
755 are constants. Required values are those that correspond to a basic block
756 which is a part of the examined switch statement. It returns true if the
757 phi nodes are OK, otherwise false. */
758
759static bool
fade902a 760check_final_bb (struct switch_conv_info *info)
b6e99746 761{
726a989a 762 gimple_stmt_iterator gsi;
b6e99746 763
fade902a
SB
764 info->phi_count = 0;
765 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
b6e99746 766 {
726a989a
RB
767 gimple phi = gsi_stmt (gsi);
768 unsigned int i;
b6e99746 769
fade902a 770 info->phi_count++;
b6e99746 771
726a989a 772 for (i = 0; i < gimple_phi_num_args (phi); i++)
b6e99746 773 {
726a989a 774 basic_block bb = gimple_phi_arg_edge (phi, i)->src;
b6e99746 775
fade902a
SB
776 if (bb == info->switch_bb
777 || (single_pred_p (bb) && single_pred (bb) == info->switch_bb))
b6e99746 778 {
f6e6e990
JJ
779 tree reloc, val;
780
781 val = gimple_phi_arg_def (phi, i);
782 if (!is_gimple_ip_invariant (val))
783 {
fade902a 784 info->reason = "non-invariant value from a case";
f6e6e990
JJ
785 return false; /* Non-invariant argument. */
786 }
787 reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
788 if ((flag_pic && reloc != null_pointer_node)
789 || (!flag_pic && reloc == NULL_TREE))
790 {
791 if (reloc)
fade902a
SB
792 info->reason
793 = "value from a case would need runtime relocations";
f6e6e990 794 else
fade902a
SB
795 info->reason
796 = "value from a case is not a valid initializer";
f6e6e990
JJ
797 return false;
798 }
b6e99746
MJ
799 }
800 }
801 }
802
803 return true;
804}
805
806/* The following function allocates default_values, target_{in,out}_names and
807 constructors arrays. The last one is also populated with pointers to
808 vectors that will become constructors of new arrays. */
809
810static void
fade902a 811create_temp_arrays (struct switch_conv_info *info)
b6e99746
MJ
812{
813 int i;
814
fade902a 815 info->default_values = XCNEWVEC (tree, info->phi_count * 3);
9771b263
DN
816 /* ??? Macros do not support multi argument templates in their
817 argument list. We create a typedef to work around that problem. */
818 typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc;
819 info->constructors = XCNEWVEC (vec_constructor_elt_gc, info->phi_count);
fade902a
SB
820 info->target_inbound_names = info->default_values + info->phi_count;
821 info->target_outbound_names = info->target_inbound_names + info->phi_count;
822 for (i = 0; i < info->phi_count; i++)
ae7e9ddd 823 vec_alloc (info->constructors[i], tree_to_uhwi (info->range_size) + 1);
b6e99746
MJ
824}
825
826/* Free the arrays created by create_temp_arrays(). The vectors that are
827 created by that function are not freed here, however, because they have
828 already become constructors and must be preserved. */
829
830static void
fade902a 831free_temp_arrays (struct switch_conv_info *info)
b6e99746 832{
fade902a
SB
833 XDELETEVEC (info->constructors);
834 XDELETEVEC (info->default_values);
b6e99746
MJ
835}
836
837/* Populate the array of default values in the order of phi nodes.
838 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */
839
840static void
fade902a 841gather_default_values (tree default_case, struct switch_conv_info *info)
b6e99746 842{
726a989a 843 gimple_stmt_iterator gsi;
b6e99746
MJ
844 basic_block bb = label_to_block (CASE_LABEL (default_case));
845 edge e;
726a989a 846 int i = 0;
b6e99746
MJ
847
848 gcc_assert (CASE_LOW (default_case) == NULL_TREE);
849
fade902a
SB
850 if (bb == info->final_bb)
851 e = find_edge (info->switch_bb, bb);
b6e99746
MJ
852 else
853 e = single_succ_edge (bb);
854
fade902a 855 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
b6e99746 856 {
726a989a 857 gimple phi = gsi_stmt (gsi);
b6e99746
MJ
858 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
859 gcc_assert (val);
fade902a 860 info->default_values[i++] = val;
b6e99746
MJ
861 }
862}
863
864/* The following function populates the vectors in the constructors array with
865 future contents of the static arrays. The vectors are populated in the
866 order of phi nodes. SWTCH is the switch statement being converted. */
867
868static void
fade902a 869build_constructors (gimple swtch, struct switch_conv_info *info)
b6e99746 870{
726a989a 871 unsigned i, branch_num = gimple_switch_num_labels (swtch);
fade902a 872 tree pos = info->range_min;
b6e99746 873
726a989a 874 for (i = 1; i < branch_num; i++)
b6e99746 875 {
726a989a 876 tree cs = gimple_switch_label (swtch, i);
b6e99746
MJ
877 basic_block bb = label_to_block (CASE_LABEL (cs));
878 edge e;
726a989a
RB
879 tree high;
880 gimple_stmt_iterator gsi;
b6e99746
MJ
881 int j;
882
fade902a
SB
883 if (bb == info->final_bb)
884 e = find_edge (info->switch_bb, bb);
b6e99746
MJ
885 else
886 e = single_succ_edge (bb);
887 gcc_assert (e);
888
889 while (tree_int_cst_lt (pos, CASE_LOW (cs)))
890 {
891 int k;
fade902a 892 for (k = 0; k < info->phi_count; k++)
b6e99746 893 {
f32682ca 894 constructor_elt elt;
b6e99746 895
f32682ca 896 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
d1f98542
RB
897 elt.value
898 = unshare_expr_without_location (info->default_values[k]);
9771b263 899 info->constructors[k]->quick_push (elt);
b6e99746
MJ
900 }
901
807e902e
KZ
902 pos = int_const_binop (PLUS_EXPR, pos,
903 build_int_cst (TREE_TYPE (pos), 1));
b6e99746 904 }
b1ae1681 905 gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
b6e99746
MJ
906
907 j = 0;
908 if (CASE_HIGH (cs))
909 high = CASE_HIGH (cs);
910 else
b1ae1681 911 high = CASE_LOW (cs);
fade902a 912 for (gsi = gsi_start_phis (info->final_bb);
726a989a 913 !gsi_end_p (gsi); gsi_next (&gsi))
b6e99746 914 {
726a989a 915 gimple phi = gsi_stmt (gsi);
b6e99746 916 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
7f2a9982 917 tree low = CASE_LOW (cs);
b6e99746
MJ
918 pos = CASE_LOW (cs);
919
b8698a0f 920 do
b6e99746 921 {
f32682ca 922 constructor_elt elt;
b6e99746 923
f32682ca 924 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
d1f98542 925 elt.value = unshare_expr_without_location (val);
9771b263 926 info->constructors[j]->quick_push (elt);
b6e99746 927
807e902e
KZ
928 pos = int_const_binop (PLUS_EXPR, pos,
929 build_int_cst (TREE_TYPE (pos), 1));
7156c8ab
MJ
930 } while (!tree_int_cst_lt (high, pos)
931 && tree_int_cst_lt (low, pos));
b6e99746
MJ
932 j++;
933 }
934 }
935}
936
7156c8ab
MJ
937/* If all values in the constructor vector are the same, return the value.
938 Otherwise return NULL_TREE. Not supposed to be called for empty
939 vectors. */
940
941static tree
9771b263 942constructor_contains_same_values_p (vec<constructor_elt, va_gc> *vec)
7156c8ab 943{
8e97bc2b 944 unsigned int i;
7156c8ab 945 tree prev = NULL_TREE;
8e97bc2b 946 constructor_elt *elt;
7156c8ab 947
9771b263 948 FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
7156c8ab 949 {
7156c8ab
MJ
950 if (!prev)
951 prev = elt->value;
952 else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
953 return NULL_TREE;
954 }
955 return prev;
956}
957
8e97bc2b
JJ
958/* Return type which should be used for array elements, either TYPE,
959 or for integral type some smaller integral type that can still hold
960 all the constants. */
961
962static tree
fade902a
SB
963array_value_type (gimple swtch, tree type, int num,
964 struct switch_conv_info *info)
8e97bc2b 965{
9771b263 966 unsigned int i, len = vec_safe_length (info->constructors[num]);
8e97bc2b 967 constructor_elt *elt;
ef4bddc2 968 machine_mode mode;
8e97bc2b
JJ
969 int sign = 0;
970 tree smaller_type;
971
972 if (!INTEGRAL_TYPE_P (type))
973 return type;
974
975 mode = GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type)));
976 if (GET_MODE_SIZE (TYPE_MODE (type)) <= GET_MODE_SIZE (mode))
977 return type;
978
979 if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32))
980 return type;
981
9771b263 982 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
8e97bc2b 983 {
807e902e 984 wide_int cst;
8e97bc2b
JJ
985
986 if (TREE_CODE (elt->value) != INTEGER_CST)
987 return type;
988
807e902e 989 cst = elt->value;
8e97bc2b
JJ
990 while (1)
991 {
992 unsigned int prec = GET_MODE_BITSIZE (mode);
993 if (prec > HOST_BITS_PER_WIDE_INT)
994 return type;
995
807e902e 996 if (sign >= 0 && cst == wi::zext (cst, prec))
8e97bc2b 997 {
807e902e 998 if (sign == 0 && cst == wi::sext (cst, prec))
8e97bc2b
JJ
999 break;
1000 sign = 1;
1001 break;
1002 }
807e902e 1003 if (sign <= 0 && cst == wi::sext (cst, prec))
8e97bc2b
JJ
1004 {
1005 sign = -1;
1006 break;
1007 }
1008
1009 if (sign == 1)
1010 sign = 0;
1011
1012 mode = GET_MODE_WIDER_MODE (mode);
1013 if (mode == VOIDmode
1014 || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (TYPE_MODE (type)))
1015 return type;
1016 }
1017 }
1018
1019 if (sign == 0)
1020 sign = TYPE_UNSIGNED (type) ? 1 : -1;
1021 smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
1022 if (GET_MODE_SIZE (TYPE_MODE (type))
1023 <= GET_MODE_SIZE (TYPE_MODE (smaller_type)))
1024 return type;
1025
1026 return smaller_type;
1027}
1028
b6e99746
MJ
1029/* Create an appropriate array type and declaration and assemble a static array
1030 variable. Also create a load statement that initializes the variable in
1031 question with a value from the static array. SWTCH is the switch statement
1032 being converted, NUM is the index to arrays of constructors, default values
1033 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
1034 of the index of the new array, PHI is the phi node of the final BB that
1035 corresponds to the value that will be loaded from the created array. TIDX
7156c8ab
MJ
1036 is an ssa name of a temporary variable holding the index for loads from the
1037 new array. */
b6e99746
MJ
1038
1039static void
726a989a 1040build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi,
fade902a 1041 tree tidx, struct switch_conv_info *info)
b6e99746 1042{
7156c8ab 1043 tree name, cst;
726a989a 1044 gimple load;
7156c8ab 1045 gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
c2255bc4 1046 location_t loc = gimple_location (swtch);
b6e99746 1047
fade902a 1048 gcc_assert (info->default_values[num]);
b6e99746 1049
070ecdfd 1050 name = copy_ssa_name (PHI_RESULT (phi), NULL);
fade902a 1051 info->target_inbound_names[num] = name;
b6e99746 1052
fade902a 1053 cst = constructor_contains_same_values_p (info->constructors[num]);
7156c8ab
MJ
1054 if (cst)
1055 load = gimple_build_assign (name, cst);
1056 else
1057 {
8e97bc2b 1058 tree array_type, ctor, decl, value_type, fetch, default_type;
7156c8ab 1059
fade902a
SB
1060 default_type = TREE_TYPE (info->default_values[num]);
1061 value_type = array_value_type (swtch, default_type, num, info);
7156c8ab 1062 array_type = build_array_type (value_type, arr_index_type);
8e97bc2b
JJ
1063 if (default_type != value_type)
1064 {
1065 unsigned int i;
1066 constructor_elt *elt;
1067
9771b263 1068 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
8e97bc2b
JJ
1069 elt->value = fold_convert (value_type, elt->value);
1070 }
fade902a 1071 ctor = build_constructor (array_type, info->constructors[num]);
7156c8ab 1072 TREE_CONSTANT (ctor) = true;
5f7ae6b6 1073 TREE_STATIC (ctor) = true;
7156c8ab 1074
c2255bc4 1075 decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
7156c8ab
MJ
1076 TREE_STATIC (decl) = 1;
1077 DECL_INITIAL (decl) = ctor;
1078
1079 DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
1080 DECL_ARTIFICIAL (decl) = 1;
1081 TREE_CONSTANT (decl) = 1;
2e3b4885 1082 TREE_READONLY (decl) = 1;
9041d2e6 1083 varpool_node::finalize_decl (decl);
7156c8ab
MJ
1084
1085 fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
1086 NULL_TREE);
8e97bc2b
JJ
1087 if (default_type != value_type)
1088 {
1089 fetch = fold_convert (default_type, fetch);
1090 fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
1091 true, GSI_SAME_STMT);
1092 }
7156c8ab
MJ
1093 load = gimple_build_assign (name, fetch);
1094 }
b6e99746 1095
726a989a 1096 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
7156c8ab 1097 update_stmt (load);
fade902a 1098 info->arr_ref_last = load;
b6e99746
MJ
1099}
1100
1101/* Builds and initializes static arrays initialized with values gathered from
1102 the SWTCH switch statement. Also creates statements that load values from
1103 them. */
1104
1105static void
fade902a 1106build_arrays (gimple swtch, struct switch_conv_info *info)
b6e99746
MJ
1107{
1108 tree arr_index_type;
83d5977e 1109 tree tidx, sub, utype;
726a989a
RB
1110 gimple stmt;
1111 gimple_stmt_iterator gsi;
b6e99746 1112 int i;
db3927fb 1113 location_t loc = gimple_location (swtch);
b6e99746 1114
726a989a 1115 gsi = gsi_for_stmt (swtch);
04e78aa9 1116
edb9b69e 1117 /* Make sure we do not generate arithmetics in a subrange. */
fade902a 1118 utype = TREE_TYPE (info->index_expr);
edb9b69e
JJ
1119 if (TREE_TYPE (utype))
1120 utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
1121 else
1122 utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
1123
fade902a 1124 arr_index_type = build_index_type (info->range_size);
83d5977e 1125 tidx = make_ssa_name (utype, NULL);
edb9b69e 1126 sub = fold_build2_loc (loc, MINUS_EXPR, utype,
fade902a
SB
1127 fold_convert_loc (loc, utype, info->index_expr),
1128 fold_convert_loc (loc, utype, info->range_min));
fae1034e 1129 sub = force_gimple_operand_gsi (&gsi, sub,
726a989a
RB
1130 false, NULL, true, GSI_SAME_STMT);
1131 stmt = gimple_build_assign (tidx, sub);
b6e99746 1132
726a989a 1133 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
7156c8ab 1134 update_stmt (stmt);
fade902a 1135 info->arr_ref_first = stmt;
b6e99746 1136
fade902a 1137 for (gsi = gsi_start_phis (info->final_bb), i = 0;
726a989a 1138 !gsi_end_p (gsi); gsi_next (&gsi), i++)
fade902a 1139 build_one_array (swtch, i, arr_index_type, gsi_stmt (gsi), tidx, info);
b6e99746
MJ
1140}
1141
1142/* Generates and appropriately inserts loads of default values at the position
1143 given by BSI. Returns the last inserted statement. */
1144
726a989a 1145static gimple
fade902a 1146gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info)
b6e99746
MJ
1147{
1148 int i;
726a989a 1149 gimple assign = NULL;
b6e99746 1150
fade902a 1151 for (i = 0; i < info->phi_count; i++)
b6e99746 1152 {
070ecdfd 1153 tree name = copy_ssa_name (info->target_inbound_names[i], NULL);
fade902a
SB
1154 info->target_outbound_names[i] = name;
1155 assign = gimple_build_assign (name, info->default_values[i]);
726a989a 1156 gsi_insert_before (gsi, assign, GSI_SAME_STMT);
7156c8ab 1157 update_stmt (assign);
b6e99746
MJ
1158 }
1159 return assign;
1160}
1161
1162/* Deletes the unused bbs and edges that now contain the switch statement and
1163 its empty branch bbs. BBD is the now dead BB containing the original switch
1164 statement, FINAL is the last BB of the converted switch statement (in terms
1165 of succession). */
1166
1167static void
1168prune_bbs (basic_block bbd, basic_block final)
1169{
1170 edge_iterator ei;
1171 edge e;
1172
1173 for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
1174 {
1175 basic_block bb;
1176 bb = e->dest;
1177 remove_edge (e);
1178 if (bb != final)
1179 delete_basic_block (bb);
1180 }
1181 delete_basic_block (bbd);
1182}
1183
1184/* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
1185 from the basic block loading values from an array and E2F from the basic
1186 block loading default values. BBF is the last switch basic block (see the
1187 bbf description in the comment below). */
1188
1189static void
fade902a
SB
1190fix_phi_nodes (edge e1f, edge e2f, basic_block bbf,
1191 struct switch_conv_info *info)
b6e99746 1192{
726a989a 1193 gimple_stmt_iterator gsi;
b6e99746
MJ
1194 int i;
1195
726a989a
RB
1196 for (gsi = gsi_start_phis (bbf), i = 0;
1197 !gsi_end_p (gsi); gsi_next (&gsi), i++)
b6e99746 1198 {
726a989a 1199 gimple phi = gsi_stmt (gsi);
9e227d60
DC
1200 add_phi_arg (phi, info->target_inbound_names[i], e1f, UNKNOWN_LOCATION);
1201 add_phi_arg (phi, info->target_outbound_names[i], e2f, UNKNOWN_LOCATION);
b6e99746 1202 }
b6e99746
MJ
1203}
1204
1205/* Creates a check whether the switch expression value actually falls into the
1206 range given by all the cases. If it does not, the temporaries are loaded
1207 with default values instead. SWTCH is the switch statement being converted.
1208
1209 bb0 is the bb with the switch statement, however, we'll end it with a
1210 condition instead.
1211
1212 bb1 is the bb to be used when the range check went ok. It is derived from
1213 the switch BB
1214
1215 bb2 is the bb taken when the expression evaluated outside of the range
1216 covered by the created arrays. It is populated by loads of default
1217 values.
1218
1219 bbF is a fall through for both bb1 and bb2 and contains exactly what
1220 originally followed the switch statement.
1221
1222 bbD contains the switch statement (in the end). It is unreachable but we
1223 still need to strip off its edges.
1224*/
1225
1226static void
fade902a 1227gen_inbound_check (gimple swtch, struct switch_conv_info *info)
b6e99746 1228{
c2255bc4
AH
1229 tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
1230 tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
1231 tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
726a989a 1232 gimple label1, label2, label3;
edb9b69e 1233 tree utype, tidx;
b6e99746
MJ
1234 tree bound;
1235
726a989a 1236 gimple cond_stmt;
b6e99746 1237
726a989a
RB
1238 gimple last_assign;
1239 gimple_stmt_iterator gsi;
b6e99746
MJ
1240 basic_block bb0, bb1, bb2, bbf, bbd;
1241 edge e01, e02, e21, e1d, e1f, e2f;
db3927fb 1242 location_t loc = gimple_location (swtch);
b6e99746 1243
fade902a 1244 gcc_assert (info->default_values);
6ab1ab14 1245
726a989a 1246 bb0 = gimple_bb (swtch);
b6e99746 1247
fade902a 1248 tidx = gimple_assign_lhs (info->arr_ref_first);
edb9b69e 1249 utype = TREE_TYPE (tidx);
145544ab 1250
b6e99746 1251 /* (end of) block 0 */
fade902a 1252 gsi = gsi_for_stmt (info->arr_ref_first);
edb9b69e 1253 gsi_next (&gsi);
b6e99746 1254
fade902a 1255 bound = fold_convert_loc (loc, utype, info->range_size);
edb9b69e 1256 cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
726a989a 1257 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
7156c8ab 1258 update_stmt (cond_stmt);
b6e99746
MJ
1259
1260 /* block 2 */
726a989a
RB
1261 label2 = gimple_build_label (label_decl2);
1262 gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
fade902a 1263 last_assign = gen_def_assigns (&gsi, info);
b6e99746
MJ
1264
1265 /* block 1 */
726a989a
RB
1266 label1 = gimple_build_label (label_decl1);
1267 gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
b6e99746
MJ
1268
1269 /* block F */
fade902a 1270 gsi = gsi_start_bb (info->final_bb);
726a989a
RB
1271 label3 = gimple_build_label (label_decl3);
1272 gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
b6e99746
MJ
1273
1274 /* cfg fix */
726a989a 1275 e02 = split_block (bb0, cond_stmt);
b6e99746
MJ
1276 bb2 = e02->dest;
1277
1278 e21 = split_block (bb2, last_assign);
1279 bb1 = e21->dest;
1280 remove_edge (e21);
1281
fade902a 1282 e1d = split_block (bb1, info->arr_ref_last);
b6e99746
MJ
1283 bbd = e1d->dest;
1284 remove_edge (e1d);
1285
1286 /* flags and profiles of the edge for in-range values */
1287 e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
fade902a
SB
1288 e01->probability = REG_BR_PROB_BASE - info->default_prob;
1289 e01->count = info->other_count;
b6e99746
MJ
1290
1291 /* flags and profiles of the edge taking care of out-of-range values */
1292 e02->flags &= ~EDGE_FALLTHRU;
1293 e02->flags |= EDGE_FALSE_VALUE;
fade902a
SB
1294 e02->probability = info->default_prob;
1295 e02->count = info->default_count;
b6e99746 1296
fade902a 1297 bbf = info->final_bb;
b6e99746
MJ
1298
1299 e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
1300 e1f->probability = REG_BR_PROB_BASE;
fade902a 1301 e1f->count = info->other_count;
b6e99746
MJ
1302
1303 e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
1304 e2f->probability = REG_BR_PROB_BASE;
fade902a 1305 e2f->count = info->default_count;
b6e99746
MJ
1306
1307 /* frequencies of the new BBs */
1308 bb1->frequency = EDGE_FREQUENCY (e01);
1309 bb2->frequency = EDGE_FREQUENCY (e02);
1310 bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
1311
6ab1ab14
SB
1312 /* Tidy blocks that have become unreachable. */
1313 prune_bbs (bbd, info->final_bb);
b6e99746 1314
6ab1ab14 1315 /* Fixup the PHI nodes in bbF. */
fade902a 1316 fix_phi_nodes (e1f, e2f, bbf, info);
b6e99746 1317
6ab1ab14
SB
1318 /* Fix the dominator tree, if it is available. */
1319 if (dom_info_available_p (CDI_DOMINATORS))
1320 {
9771b263 1321 vec<basic_block> bbs_to_fix_dom;
6ab1ab14
SB
1322
1323 set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
1324 set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
531b10fc 1325 if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
6ab1ab14
SB
1326 /* If bbD was the immediate dominator ... */
1327 set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
1328
9771b263
DN
1329 bbs_to_fix_dom.create (4);
1330 bbs_to_fix_dom.quick_push (bb0);
1331 bbs_to_fix_dom.quick_push (bb1);
1332 bbs_to_fix_dom.quick_push (bb2);
1333 bbs_to_fix_dom.quick_push (bbf);
6ab1ab14
SB
1334
1335 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
9771b263 1336 bbs_to_fix_dom.release ();
6ab1ab14 1337 }
b6e99746
MJ
1338}
1339
1340/* The following function is invoked on every switch statement (the current one
1341 is given in SWTCH) and runs the individual phases of switch conversion on it
fade902a
SB
1342 one after another until one fails or the conversion is completed.
1343 Returns NULL on success, or a pointer to a string with the reason why the
1344 conversion failed. */
b6e99746 1345
fade902a 1346static const char *
726a989a 1347process_switch (gimple swtch)
b6e99746 1348{
fade902a 1349 struct switch_conv_info info;
b6e99746 1350
238065a7
SB
1351 /* Group case labels so that we get the right results from the heuristics
1352 that decide on the code generation approach for this switch. */
1353 group_case_labels_stmt (swtch);
1354
1355 /* If this switch is now a degenerate case with only a default label,
1356 there is nothing left for us to do. */
1357 if (gimple_switch_num_labels (swtch) < 2)
1358 return "switch is a degenerate case";
886cd84f
SB
1359
1360 collect_switch_conv_info (swtch, &info);
1361
1362 /* No error markers should reach here (they should be filtered out
1363 during gimplification). */
1364 gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node);
1365
531b10fc
SB
1366 /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
1367 gcc_checking_assert (! TREE_CONSTANT (info.index_expr));
886cd84f 1368
531b10fc 1369 if (info.uniq <= MAX_CASE_BIT_TESTS)
886cd84f 1370 {
531b10fc 1371 if (expand_switch_using_bit_tests_p (info.range_size,
72798784
RB
1372 info.uniq, info.count,
1373 optimize_bb_for_speed_p
1374 (gimple_bb (swtch))))
531b10fc
SB
1375 {
1376 if (dump_file)
1377 fputs (" expanding as bit test is preferable\n", dump_file);
aa79a1e1
JJ
1378 emit_case_bit_tests (swtch, info.index_expr, info.range_min,
1379 info.range_size, info.range_max);
726338f4 1380 loops_state_set (LOOPS_NEED_FIXUP);
531b10fc
SB
1381 return NULL;
1382 }
1383
1384 if (info.uniq <= 2)
1385 /* This will be expanded as a decision tree in stmt.c:expand_case. */
1386 return " expanding as jumps is preferable";
886cd84f 1387 }
b6e99746 1388
531b10fc
SB
1389 /* If there is no common successor, we cannot do the transformation. */
1390 if (! info.final_bb)
1391 return "no common successor to all case label target blocks found";
1392
b6e99746 1393 /* Check the case label values are within reasonable range: */
886cd84f 1394 if (!check_range (&info))
fade902a
SB
1395 {
1396 gcc_assert (info.reason);
1397 return info.reason;
1398 }
b6e99746
MJ
1399
1400 /* For all the cases, see whether they are empty, the assignments they
1401 represent constant and so on... */
886cd84f 1402 if (! check_all_empty_except_final (&info))
8e97bc2b 1403 {
886cd84f
SB
1404 gcc_assert (info.reason);
1405 return info.reason;
8e97bc2b 1406 }
fade902a
SB
1407 if (!check_final_bb (&info))
1408 {
1409 gcc_assert (info.reason);
1410 return info.reason;
1411 }
b6e99746
MJ
1412
1413 /* At this point all checks have passed and we can proceed with the
1414 transformation. */
1415
fade902a 1416 create_temp_arrays (&info);
fd8d363e 1417 gather_default_values (gimple_switch_default_label (swtch), &info);
fade902a 1418 build_constructors (swtch, &info);
b6e99746 1419
fade902a
SB
1420 build_arrays (swtch, &info); /* Build the static arrays and assignments. */
1421 gen_inbound_check (swtch, &info); /* Build the bounds check. */
b6e99746
MJ
1422
1423 /* Cleanup: */
fade902a
SB
1424 free_temp_arrays (&info);
1425 return NULL;
b6e99746
MJ
1426}
1427
1428/* The main function of the pass scans statements for switches and invokes
1429 process_switch on them. */
1430
be55bfe6
TS
1431namespace {
1432
1433const pass_data pass_data_convert_switch =
1434{
1435 GIMPLE_PASS, /* type */
1436 "switchconv", /* name */
1437 OPTGROUP_NONE, /* optinfo_flags */
be55bfe6
TS
1438 TV_TREE_SWITCH_CONVERSION, /* tv_id */
1439 ( PROP_cfg | PROP_ssa ), /* properties_required */
1440 0, /* properties_provided */
1441 0, /* properties_destroyed */
1442 0, /* todo_flags_start */
3bea341f 1443 TODO_update_ssa, /* todo_flags_finish */
be55bfe6
TS
1444};
1445
1446class pass_convert_switch : public gimple_opt_pass
1447{
1448public:
1449 pass_convert_switch (gcc::context *ctxt)
1450 : gimple_opt_pass (pass_data_convert_switch, ctxt)
1451 {}
1452
1453 /* opt_pass methods: */
1454 virtual bool gate (function *) { return flag_tree_switch_conversion != 0; }
1455 virtual unsigned int execute (function *);
1456
1457}; // class pass_convert_switch
1458
1459unsigned int
1460pass_convert_switch::execute (function *fun)
b6e99746
MJ
1461{
1462 basic_block bb;
1463
be55bfe6 1464 FOR_EACH_BB_FN (bb, fun)
b6e99746 1465 {
fade902a 1466 const char *failure_reason;
726a989a
RB
1467 gimple stmt = last_stmt (bb);
1468 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
b6e99746 1469 {
b6e99746
MJ
1470 if (dump_file)
1471 {
726a989a
RB
1472 expanded_location loc = expand_location (gimple_location (stmt));
1473
b6e99746
MJ
1474 fprintf (dump_file, "beginning to process the following "
1475 "SWITCH statement (%s:%d) : ------- \n",
1476 loc.file, loc.line);
726a989a 1477 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
edb30094 1478 putc ('\n', dump_file);
b6e99746
MJ
1479 }
1480
fade902a
SB
1481 failure_reason = process_switch (stmt);
1482 if (! failure_reason)
b6e99746
MJ
1483 {
1484 if (dump_file)
1485 {
edb30094
UB
1486 fputs ("Switch converted\n", dump_file);
1487 fputs ("--------------------------------\n", dump_file);
b6e99746 1488 }
531b10fc
SB
1489
1490 /* Make no effort to update the post-dominator tree. It is actually not
1491 that hard for the transformations we have performed, but it is not
1492 supported by iterate_fix_dominators. */
1493 free_dominance_info (CDI_POST_DOMINATORS);
b6e99746
MJ
1494 }
1495 else
1496 {
1497 if (dump_file)
1498 {
edb30094 1499 fputs ("Bailing out - ", dump_file);
fade902a
SB
1500 fputs (failure_reason, dump_file);
1501 fputs ("\n--------------------------------\n", dump_file);
b6e99746
MJ
1502 }
1503 }
1504 }
1505 }
1506
1507 return 0;
1508}
1509
27a4cd48
DM
1510} // anon namespace
1511
1512gimple_opt_pass *
1513make_pass_convert_switch (gcc::context *ctxt)
1514{
1515 return new pass_convert_switch (ctxt);
1516}