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