xref: /netbsd-src/external/gpl3/gcc/dist/gcc/tree-switch-conversion.h (revision b1e838363e3c6fc78a55519254d99869742dd33c)
1 /* Tree switch conversion for GNU compiler.
2    Copyright (C) 2017-2022 Free Software Foundation, Inc.
3 
4 This file is part of GCC.
5 
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
10 
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 for more details.
15 
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3.  If not see
18 <http://www.gnu.org/licenses/>.  */
19 
20 #ifndef TREE_SWITCH_CONVERSION_H
21 #define TREE_SWITCH_CONVERSION_H
22 
23 namespace tree_switch_conversion {
24 
25 /* Type of cluster.  */
26 
27 enum cluster_type
28 {
29   SIMPLE_CASE,
30   JUMP_TABLE,
31   BIT_TEST
32 };
33 
34 #define PRINT_CASE(f,c) print_generic_expr (f, c)
35 
36 /* Abstract base class for representing a cluster of cases.
37 
38    Here is the inheritance hierarachy, and the enum_cluster_type
39    values for the concrete subclasses:
40 
41    cluster
42    |-simple_cluster (SIMPLE_CASE)
43    `-group_cluster
44      |-jump_table_cluster (JUMP_TABLE)
45      `-bit_test_cluster   (BIT_TEST).  */
46 
47 class cluster
48 {
49 public:
50   /* Constructor.  */
51   inline cluster (tree case_label_expr, basic_block case_bb,
52 		  profile_probability prob, profile_probability subtree_prob);
53 
54   /* Destructor.  */
~cluster()55   virtual ~cluster ()
56   {}
57 
58   /* Return type.  */
59   virtual cluster_type get_type () = 0;
60 
61   /* Get low value covered by a cluster.  */
62   virtual tree get_low () = 0;
63 
64   /* Get high value covered by a cluster.  */
65   virtual tree get_high () = 0;
66 
67   /* Debug content of a cluster.  */
68   virtual void debug () = 0;
69 
70   /* Dump content of a cluster.  */
71   virtual void dump (FILE *f, bool details = false) = 0;
72 
73   /* Emit GIMPLE code to handle the cluster.  */
74   virtual void emit (tree, tree, tree, basic_block, location_t) = 0;
75 
76   /* Return true if a cluster handles only a single case value and the
77      value is not a range.  */
is_single_value_p()78   virtual bool is_single_value_p ()
79   {
80     return false;
81   }
82 
83   /* Return range of a cluster.  If value would overflow in type of LOW,
84      then return 0.  */
get_range(tree low,tree high)85   static unsigned HOST_WIDE_INT get_range (tree low, tree high)
86   {
87     wide_int w = wi::to_wide (high) - wi::to_wide (low);
88     if (wi::neg_p (w, TYPE_SIGN (TREE_TYPE (low))) || !wi::fits_uhwi_p (w))
89       return 0;
90     return w.to_uhwi () + 1;
91   }
92 
93   /* Case label.  */
94   tree m_case_label_expr;
95 
96   /* Basic block of the case.  */
97   basic_block m_case_bb;
98 
99   /* Probability of taking this cluster.  */
100   profile_probability m_prob;
101 
102   /* Probability of reaching subtree rooted at this node.  */
103   profile_probability m_subtree_prob;
104 
105 protected:
106   /* Default constructor.  */
cluster()107   cluster () {}
108 };
109 
cluster(tree case_label_expr,basic_block case_bb,profile_probability prob,profile_probability subtree_prob)110 cluster::cluster (tree case_label_expr, basic_block case_bb,
111 		  profile_probability prob, profile_probability subtree_prob):
112   m_case_label_expr (case_label_expr), m_case_bb (case_bb), m_prob (prob),
113   m_subtree_prob (subtree_prob)
114 {
115 }
116 
117 /* Subclass of cluster representing a simple contiguous range
118    from [low..high].  */
119 
120 class simple_cluster: public cluster
121 {
122 public:
123   /* Constructor.  */
124   inline simple_cluster (tree low, tree high, tree case_label_expr,
125 			 basic_block case_bb, profile_probability prob,
126 			 bool has_forward_bb = false);
127 
128   /* Destructor.  */
~simple_cluster()129   ~simple_cluster ()
130   {}
131 
132   cluster_type
get_type()133   get_type ()
134   {
135     return SIMPLE_CASE;
136   }
137 
138   tree
get_low()139   get_low ()
140   {
141     return m_low;
142   }
143 
144   tree
get_high()145   get_high ()
146   {
147     return m_high;
148   }
149 
set_high(tree high)150   void set_high (tree high)
151   {
152     m_high = high;
153   }
154 
155   void
debug()156   debug ()
157   {
158     dump (stderr);
159   }
160 
161   void
162   dump (FILE *f, bool details ATTRIBUTE_UNUSED = false)
163   {
164     PRINT_CASE (f, get_low ());
165     if (get_low () != get_high ())
166       {
167 	fprintf (f, "-");
168 	PRINT_CASE (f, get_high ());
169       }
170     fprintf (f, " ");
171   }
172 
emit(tree,tree,tree,basic_block,location_t)173   void emit (tree, tree, tree, basic_block, location_t)
174   {
175     gcc_unreachable ();
176   }
177 
is_single_value_p()178   bool is_single_value_p ()
179   {
180     return tree_int_cst_equal (get_low (), get_high ());
181   }
182 
183   /* Return number of comparisons needed for the case.  */
184   unsigned
get_comparison_count()185   get_comparison_count ()
186   {
187     return m_range_p ? 2 : 1;
188   }
189 
190   /* Low value of the case.  */
191   tree m_low;
192 
193   /* High value of the case.  */
194   tree m_high;
195 
196   /* True if case is a range.  */
197   bool m_range_p;
198 
199   /* True if the case will use a forwarder BB.  */
200   bool m_has_forward_bb;
201 };
202 
simple_cluster(tree low,tree high,tree case_label_expr,basic_block case_bb,profile_probability prob,bool has_forward_bb)203 simple_cluster::simple_cluster (tree low, tree high, tree case_label_expr,
204 				basic_block case_bb, profile_probability prob,
205 				bool has_forward_bb):
206   cluster (case_label_expr, case_bb, prob, prob),
207   m_low (low), m_high (high), m_has_forward_bb (has_forward_bb)
208 {
209   m_range_p = m_high != NULL;
210   if (m_high == NULL)
211     m_high = m_low;
212 }
213 
214 /* Abstract subclass of jump table and bit test cluster,
215    handling a collection of simple_cluster instances.  */
216 
217 class group_cluster: public cluster
218 {
219 public:
220   /* Constructor.  */
221   group_cluster (vec<cluster *> &clusters, unsigned start, unsigned end);
222 
223   /* Destructor.  */
224   ~group_cluster ();
225 
226   tree
get_low()227   get_low ()
228   {
229     return m_cases[0]->get_low ();
230   }
231 
232   tree
get_high()233   get_high ()
234   {
235     return m_cases[m_cases.length () - 1]->get_high ();
236   }
237 
238   void
debug()239   debug ()
240   {
241     dump (stderr);
242   }
243 
244   void dump (FILE *f, bool details = false);
245 
246   /* List of simple clusters handled by the group.  */
247   vec<simple_cluster *> m_cases;
248 };
249 
250 /* Concrete subclass of group_cluster representing a collection
251    of cases to be implemented as a jump table.
252    The "emit" vfunc gernerates a nested switch statement which
253    is later lowered to a jump table.  */
254 
255 class jump_table_cluster: public group_cluster
256 {
257 public:
258   /* Constructor.  */
jump_table_cluster(vec<cluster * > & clusters,unsigned start,unsigned end)259   jump_table_cluster (vec<cluster *> &clusters, unsigned start, unsigned end)
260   : group_cluster (clusters, start, end)
261   {}
262 
263   cluster_type
get_type()264   get_type ()
265   {
266     return JUMP_TABLE;
267   }
268 
269   void emit (tree index_expr, tree index_type,
270 	     tree default_label_expr, basic_block default_bb, location_t loc);
271 
272   /* Find jump tables of given CLUSTERS, where all members of the vector
273      are of type simple_cluster.  New clusters are returned.  */
274   static vec<cluster *> find_jump_tables (vec<cluster *> &clusters);
275 
276   /* Return true when cluster starting at START and ending at END (inclusive)
277      can build a jump-table.  COMPARISON_COUNT is number of comparison
278      operations needed if the clusters are expanded as decision tree.
279      MAX_RATIO tells about the maximum code growth (in percent).  */
280   static bool can_be_handled (const vec<cluster *> &clusters, unsigned start,
281 			      unsigned end, unsigned HOST_WIDE_INT max_ratio,
282 			      unsigned HOST_WIDE_INT comparison_count);
283 
284   /* Return true if cluster starting at START and ending at END (inclusive)
285      is profitable transformation.  */
286   static bool is_beneficial (const vec<cluster *> &clusters, unsigned start,
287 			     unsigned end);
288 
289   /* Return the smallest number of different values for which it is best
290      to use a jump-table instead of a tree of conditional branches.  */
291   static inline unsigned int case_values_threshold (void);
292 
293   /* Return whether jump table expansion is allowed.  */
294   static inline bool is_enabled (void);
295 };
296 
297 /* A GIMPLE switch statement can be expanded to a short sequence of bit-wise
298 comparisons.  "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
299 where CST and MINVAL are integer constants.  This is better than a series
300 of compare-and-banch insns in some cases,  e.g. we can implement:
301 
302 	if ((x==4) || (x==6) || (x==9) || (x==11))
303 
304 as a single bit test:
305 
306 	if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
307 
308 This transformation is only applied if the number of case targets is small,
309 if CST constains at least 3 bits, and "1 << x" is cheap.  The bit tests are
310 performed in "word_mode".
311 
312 The following example shows the code the transformation generates:
313 
314 	int bar(int x)
315 	{
316 		switch (x)
317 		{
318 		case '0':  case '1':  case '2':  case '3':  case '4':
319 		case '5':  case '6':  case '7':  case '8':  case '9':
320 		case 'A':  case 'B':  case 'C':  case 'D':  case 'E':
321 		case 'F':
322 			return 1;
323 		}
324 		return 0;
325 	}
326 
327 ==>
328 
329 	bar (int x)
330 	{
331 		tmp1 = x - 48;
332 		if (tmp1 > (70 - 48)) goto L2;
333 		tmp2 = 1 << tmp1;
334 		tmp3 = 0b11111100000001111111111;
335 		if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
336 	L1:
337 		return 1;
338 	L2:
339 		return 0;
340 	}
341 
342 TODO: There are still some improvements to this transformation that could
343 be implemented:
344 
345 * A narrower mode than word_mode could be used if that is cheaper, e.g.
346   for x86_64 where a narrower-mode shift may result in smaller code.
347 
348 * The compounded constant could be shifted rather than the one.  The
349   test would be either on the sign bit or on the least significant bit,
350   depending on the direction of the shift.  On some machines, the test
351   for the branch would be free if the bit to test is already set by the
352   shift operation.
353 
354 This transformation was contributed by Roger Sayle, see this e-mail:
355    http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
356 */
357 
358 class bit_test_cluster: public group_cluster
359 {
360 public:
361   /* Constructor.  */
bit_test_cluster(vec<cluster * > & clusters,unsigned start,unsigned end,bool handles_entire_switch)362   bit_test_cluster (vec<cluster *> &clusters, unsigned start, unsigned end,
363 		    bool handles_entire_switch)
364   :group_cluster (clusters, start, end),
365   m_handles_entire_switch (handles_entire_switch)
366   {}
367 
368   cluster_type
get_type()369   get_type ()
370   {
371     return BIT_TEST;
372   }
373 
374 /*  Expand a switch statement by a short sequence of bit-wise
375     comparisons.  "switch(x)" is effectively converted into
376     "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
377     integer constants.
378 
379     INDEX_EXPR is the value being switched on.
380 
381     MINVAL is the lowest case value of in the case nodes,
382     and RANGE is highest value minus MINVAL.  MINVAL and RANGE
383     are not guaranteed to be of the same type as INDEX_EXPR
384     (the gimplifier doesn't change the type of case label values,
385     and MINVAL and RANGE are derived from those values).
386     MAXVAL is MINVAL + RANGE.
387 
388     There *MUST* be max_case_bit_tests or less unique case
389     node targets.  */
390   void emit (tree index_expr, tree index_type,
391 	     tree default_label_expr, basic_block default_bb, location_t loc);
392 
393   /* Find bit tests of given CLUSTERS, where all members of the vector
394      are of type simple_cluster.  New clusters are returned.  */
395   static vec<cluster *> find_bit_tests (vec<cluster *> &clusters);
396 
397   /* Return true when RANGE of case values with UNIQ labels
398      can build a bit test.  */
399   static bool can_be_handled (unsigned HOST_WIDE_INT range, unsigned uniq);
400 
401   /* Return true when cluster starting at START and ending at END (inclusive)
402      can build a bit test.  */
403   static bool can_be_handled (const vec<cluster *> &clusters, unsigned start,
404 			      unsigned end);
405 
406   /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test
407      transformation.  */
408   static bool is_beneficial (unsigned count, unsigned uniq);
409 
410   /* Return true if cluster starting at START and ending at END (inclusive)
411      is profitable transformation.  */
412   static bool is_beneficial (const vec<cluster *> &clusters, unsigned start,
413 			     unsigned end);
414 
415 /* Split the basic block at the statement pointed to by GSIP, and insert
416    a branch to the target basic block of E_TRUE conditional on tree
417    expression COND.
418 
419    It is assumed that there is already an edge from the to-be-split
420    basic block to E_TRUE->dest block.  This edge is removed, and the
421    profile information on the edge is re-used for the new conditional
422    jump.
423 
424    The CFG is updated.  The dominator tree will not be valid after
425    this transformation, but the immediate dominators are updated if
426    UPDATE_DOMINATORS is true.
427 
428    Returns the newly created basic block.  */
429   static basic_block hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
430 						    tree cond,
431 						    basic_block case_bb,
432 						    profile_probability prob,
433 						    location_t);
434 
435   /* Return whether bit test expansion is allowed.  */
is_enabled(void)436   static inline bool is_enabled (void)
437   {
438     return flag_bit_tests;
439   }
440 
441   /* True when the jump table handles an entire switch statement.  */
442   bool m_handles_entire_switch;
443 
444   /* Maximum number of different basic blocks that can be handled by
445      a bit test.  */
446   static const int m_max_case_bit_tests = 3;
447 };
448 
449 /* Helper struct to find minimal clusters.  */
450 
451 class min_cluster_item
452 {
453 public:
454   /* Constructor.  */
min_cluster_item(unsigned count,unsigned start,unsigned non_jt_cases)455   min_cluster_item (unsigned count, unsigned start, unsigned non_jt_cases):
456     m_count (count), m_start (start), m_non_jt_cases (non_jt_cases)
457   {}
458 
459   /* Count of clusters.  */
460   unsigned m_count;
461 
462   /* Index where is cluster boundary.  */
463   unsigned m_start;
464 
465   /* Total number of cases that will not be in a jump table.  */
466   unsigned m_non_jt_cases;
467 };
468 
469 /* Helper struct to represent switch decision tree.  */
470 
471 class case_tree_node
472 {
473 public:
474   /* Empty Constructor.  */
475   case_tree_node ();
476 
477   /* Return true when it has a child.  */
has_child()478   bool has_child ()
479   {
480     return m_left != NULL || m_right != NULL;
481   }
482 
483   /* Left son in binary tree.  */
484   case_tree_node *m_left;
485 
486   /* Right son in binary tree; also node chain.  */
487   case_tree_node *m_right;
488 
489   /* Parent of node in binary tree.  */
490   case_tree_node *m_parent;
491 
492   /* Cluster represented by this tree node.  */
493   cluster *m_c;
494 };
495 
496 inline
case_tree_node()497 case_tree_node::case_tree_node ():
498   m_left (NULL), m_right (NULL), m_parent (NULL), m_c (NULL)
499 {
500 }
501 
502 unsigned int
case_values_threshold(void)503 jump_table_cluster::case_values_threshold (void)
504 {
505   unsigned int threshold = param_case_values_threshold;
506 
507   if (threshold == 0)
508     threshold = targetm.case_values_threshold ();
509 
510   return threshold;
511 }
512 
513 /* Return whether jump table expansion is allowed.  */
is_enabled(void)514 bool jump_table_cluster::is_enabled (void)
515 {
516   /* If neither casesi or tablejump is available, or flag_jump_tables
517      over-ruled us, we really have no choice.  */
518   if (!targetm.have_casesi () && !targetm.have_tablejump ())
519     return false;
520   if (!flag_jump_tables)
521     return false;
522 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
523   if (flag_pic)
524     return false;
525 #endif
526 
527   return true;
528 }
529 
530 /* A case_bit_test represents a set of case nodes that may be
531    selected from using a bit-wise comparison.  HI and LO hold
532    the integer to be tested against, TARGET_EDGE contains the
533    edge to the basic block to jump to upon success and BITS
534    counts the number of case nodes handled by this test,
535    typically the number of bits set in HI:LO.  The LABEL field
536    is used to quickly identify all cases in this set without
537    looking at label_to_block for every case label.  */
538 
539 class case_bit_test
540 {
541 public:
542   wide_int mask;
543   basic_block target_bb;
544   tree label;
545   int bits;
546 
547   /* Comparison function for qsort to order bit tests by decreasing
548      probability of execution.  */
549   static int cmp (const void *p1, const void *p2);
550 };
551 
552 class switch_decision_tree
553 {
554 public:
555   /* Constructor.  */
switch_decision_tree(gswitch * swtch)556   switch_decision_tree (gswitch *swtch): m_switch (swtch), m_phi_mapping (),
557     m_case_bbs (), m_case_node_pool ("struct case_node pool"),
558     m_case_list (NULL)
559   {
560   }
561 
562   /* Analyze switch statement and return true when the statement is expanded
563      as decision tree.  */
564   bool analyze_switch_statement ();
565 
566   /* Attempt to expand CLUSTERS as a decision tree.  Return true when
567      expanded.  */
568   bool try_switch_expansion (vec<cluster *> &clusters);
569   /* Compute the number of case labels that correspond to each outgoing edge of
570      switch statement.  Record this information in the aux field of the edge.
571      */
572   void compute_cases_per_edge ();
573 
574   /* Before switch transformation, record all SSA_NAMEs defined in switch BB
575      and used in a label basic block.  */
576   void record_phi_operand_mapping ();
577 
578   /* Append new operands to PHI statements that were introduced due to
579      addition of new edges to case labels.  */
580   void fix_phi_operands_for_edges ();
581 
582   /* Generate a decision tree, switching on INDEX_EXPR and jumping to
583      one of the labels in CASE_LIST or to the DEFAULT_LABEL.
584 
585      We generate a binary decision tree to select the appropriate target
586      code.  */
587   void emit (basic_block bb, tree index_expr,
588 	     profile_probability default_prob, tree index_type);
589 
590   /* Emit step-by-step code to select a case for the value of INDEX.
591      The thus generated decision tree follows the form of the
592      case-node binary tree NODE, whose nodes represent test conditions.
593      DEFAULT_PROB is probability of cases leading to default BB.
594      INDEX_TYPE is the type of the index of the switch.  */
595   basic_block emit_case_nodes (basic_block bb, tree index,
596 			       case_tree_node *node,
597 			       profile_probability default_prob,
598 			       tree index_type, location_t);
599 
600   /* Take an ordered list of case nodes
601      and transform them into a near optimal binary tree,
602      on the assumption that any target code selection value is as
603      likely as any other.
604 
605      The transformation is performed by splitting the ordered
606      list into two equal sections plus a pivot.  The parts are
607      then attached to the pivot as left and right branches.  Each
608      branch is then transformed recursively.  */
609   static void balance_case_nodes (case_tree_node **head,
610 				  case_tree_node *parent);
611 
612   /* Dump ROOT, a list or tree of case nodes, to file F.  */
613   static void dump_case_nodes (FILE *f, case_tree_node *root, int indent_step,
614 			       int indent_level);
615 
616   /* Add an unconditional jump to CASE_BB that happens in basic block BB.  */
617   static void emit_jump (basic_block bb, basic_block case_bb);
618 
619   /* Generate code to compare OP0 with OP1 so that the condition codes are
620      set and to jump to LABEL_BB if the condition is true.
621      COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
622      PROB is the probability of jumping to LABEL_BB.  */
623   static basic_block emit_cmp_and_jump_insns (basic_block bb, tree op0,
624 					      tree op1, tree_code comparison,
625 					      basic_block label_bb,
626 					      profile_probability prob,
627 					      location_t);
628 
629   /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
630      PROB is the probability of jumping to LABEL_BB.  */
631   static basic_block do_jump_if_equal (basic_block bb, tree op0, tree op1,
632 				       basic_block label_bb,
633 				       profile_probability prob,
634 				       location_t);
635 
636   /* Reset the aux field of all outgoing edges of switch basic block.  */
637   static inline void reset_out_edges_aux (gswitch *swtch);
638 
639   /* Switch statement.  */
640   gswitch *m_switch;
641 
642   /* Map of PHI nodes that have to be fixed after expansion.  */
643   hash_map<tree, tree> m_phi_mapping;
644 
645   /* List of basic blocks that belong to labels of the switch.  */
646   auto_vec<basic_block> m_case_bbs;
647 
648   /* Basic block with default label.  */
649   basic_block m_default_bb;
650 
651   /* A pool for case nodes.  */
652   object_allocator<case_tree_node> m_case_node_pool;
653 
654   /* Balanced tree of case nodes.  */
655   case_tree_node *m_case_list;
656 };
657 
658 /*
659      Switch initialization conversion
660 
661 The following pass changes simple initializations of scalars in a switch
662 statement into initializations from a static array.  Obviously, the values
663 must be constant and known at compile time and a default branch must be
664 provided.  For example, the following code:
665 
666 	int a,b;
667 
668 	switch (argc)
669 	{
670 	 case 1:
671 	 case 2:
672 		a_1 = 8;
673 		b_1 = 6;
674 		break;
675 	 case 3:
676 		a_2 = 9;
677 		b_2 = 5;
678 		break;
679 	 case 12:
680 		a_3 = 10;
681 		b_3 = 4;
682 		break;
683 	 default:
684 		a_4 = 16;
685 		b_4 = 1;
686 		break;
687 	}
688 	a_5 = PHI <a_1, a_2, a_3, a_4>
689 	b_5 = PHI <b_1, b_2, b_3, b_4>
690 
691 
692 is changed into:
693 
694 	static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
695 	static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
696 				 16, 16, 10};
697 
698 	if (((unsigned) argc) - 1 < 11)
699 	  {
700 	    a_6 = CSWTCH02[argc - 1];
701 	    b_6 = CSWTCH01[argc - 1];
702 	  }
703 	else
704 	  {
705 	    a_7 = 16;
706 	    b_7 = 1;
707 	  }
708 	a_5 = PHI <a_6, a_7>
709 	b_b = PHI <b_6, b_7>
710 
711 There are further constraints.  Specifically, the range of values across all
712 case labels must not be bigger than param_switch_conversion_branch_ratio
713 (default eight) times the number of the actual switch branches.
714 
715 This transformation was contributed by Martin Jambor, see this e-mail:
716    http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html  */
717 
718 /* The main structure of the pass.  */
719 class switch_conversion
720 {
721 public:
722   /* Constructor.  */
723   switch_conversion ();
724 
725   /* Destructor.  */
726   ~switch_conversion ();
727 
728   /* The following function is invoked on every switch statement (the current
729      one is given in SWTCH) and runs the individual phases of switch
730      conversion on it one after another until one fails or the conversion
731      is completed.  On success, NULL is in m_reason, otherwise points
732      to a string with the reason why the conversion failed.  */
733   void expand (gswitch *swtch);
734 
735   /* Collection information about SWTCH statement.  */
736   void collect (gswitch *swtch);
737 
738   /* Checks whether the range given by individual case statements of the switch
739      switch statement isn't too big and whether the number of branches actually
740      satisfies the size of the new array.  */
741   bool check_range ();
742 
743   /* Checks whether all but the final BB basic blocks are empty.  */
744   bool check_all_empty_except_final ();
745 
746   /* This function checks whether all required values in phi nodes in final_bb
747      are constants.  Required values are those that correspond to a basic block
748      which is a part of the examined switch statement.  It returns true if the
749      phi nodes are OK, otherwise false.  */
750   bool check_final_bb ();
751 
752   /* The following function allocates default_values, target_{in,out}_names and
753      constructors arrays.  The last one is also populated with pointers to
754      vectors that will become constructors of new arrays.  */
755   void create_temp_arrays ();
756 
757   /* Populate the array of default values in the order of phi nodes.
758      DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
759      if the range is non-contiguous or the default case has standard
760      structure, otherwise it is the first non-default case instead.  */
761   void gather_default_values (tree default_case);
762 
763   /* The following function populates the vectors in the constructors array with
764      future contents of the static arrays.  The vectors are populated in the
765      order of phi nodes.  */
766   void build_constructors ();
767 
768   /* If all values in the constructor vector are products of a linear function
769      a * x + b, then return true.  When true, COEFF_A and COEFF_B and
770      coefficients of the linear function.  Note that equal values are special
771      case of a linear function with a and b equal to zero.  */
772   bool contains_linear_function_p (vec<constructor_elt, va_gc> *vec,
773 				   wide_int *coeff_a, wide_int *coeff_b);
774 
775   /* Return type which should be used for array elements, either TYPE's
776      main variant or, for integral types, some smaller integral type
777      that can still hold all the constants.  */
778   tree array_value_type (tree type, int num);
779 
780   /* Create an appropriate array type and declaration and assemble a static
781      array variable.  Also create a load statement that initializes
782      the variable in question with a value from the static array.  SWTCH is
783      the switch statement being converted, NUM is the index to
784      arrays of constructors, default values and target SSA names
785      for this particular array.  ARR_INDEX_TYPE is the type of the index
786      of the new array, PHI is the phi node of the final BB that corresponds
787      to the value that will be loaded from the created array.  TIDX
788      is an ssa name of a temporary variable holding the index for loads from the
789      new array.  */
790   void build_one_array (int num, tree arr_index_type,
791 			gphi *phi, tree tidx);
792 
793   /* Builds and initializes static arrays initialized with values gathered from
794      the switch statement.  Also creates statements that load values from
795      them.  */
796   void build_arrays ();
797 
798   /* Generates and appropriately inserts loads of default values at the position
799      given by GSI.  Returns the last inserted statement.  */
800   gassign *gen_def_assigns (gimple_stmt_iterator *gsi);
801 
802   /* Deletes the unused bbs and edges that now contain the switch statement and
803      its empty branch bbs.  BBD is the now dead BB containing
804      the original switch statement, FINAL is the last BB of the converted
805      switch statement (in terms of succession).  */
806   void prune_bbs (basic_block bbd, basic_block final, basic_block default_bb);
807 
808   /* Add values to phi nodes in final_bb for the two new edges.  E1F is the edge
809      from the basic block loading values from an array and E2F from the basic
810      block loading default values.  BBF is the last switch basic block (see the
811      bbf description in the comment below).  */
812   void fix_phi_nodes (edge e1f, edge e2f, basic_block bbf);
813 
814   /* Creates a check whether the switch expression value actually falls into the
815      range given by all the cases.  If it does not, the temporaries are loaded
816      with default values instead.  */
817   void gen_inbound_check ();
818 
819   /* Switch statement for which switch conversion takes place.  */
820   gswitch *m_switch;
821 
822   /* The expression used to decide the switch branch.  */
823   tree m_index_expr;
824 
825   /* The following integer constants store the minimum and maximum value
826      covered by the case labels.  */
827   tree m_range_min;
828   tree m_range_max;
829 
830   /* The difference between the above two numbers.  Stored here because it
831      is used in all the conversion heuristics, as well as for some of the
832      transformation, and it is expensive to re-compute it all the time.  */
833   tree m_range_size;
834 
835   /* Basic block that contains the actual GIMPLE_SWITCH.  */
836   basic_block m_switch_bb;
837 
838   /* Basic block that is the target of the default case.  */
839   basic_block m_default_bb;
840 
841   /* The single successor block of all branches out of the GIMPLE_SWITCH,
842      if such a block exists.  Otherwise NULL.  */
843   basic_block m_final_bb;
844 
845   /* The probability of the default edge in the replaced switch.  */
846   profile_probability m_default_prob;
847 
848   /* Number of phi nodes in the final bb (that we'll be replacing).  */
849   int m_phi_count;
850 
851   /* Constructors of new static arrays.  */
852   vec<constructor_elt, va_gc> **m_constructors;
853 
854   /* Array of default values, in the same order as phi nodes.  */
855   tree *m_default_values;
856 
857   /* Array of ssa names that are initialized with a value from a new static
858      array.  */
859   tree *m_target_inbound_names;
860 
861   /* Array of ssa names that are initialized with the default value if the
862      switch expression is out of range.  */
863   tree *m_target_outbound_names;
864 
865   /* VOP SSA_NAME.  */
866   tree m_target_vop;
867 
868   /* The first load statement that loads a temporary from a new static array.
869    */
870   gimple *m_arr_ref_first;
871 
872   /* The last load statement that loads a temporary from a new static array.  */
873   gimple *m_arr_ref_last;
874 
875   /* String reason why the case wasn't a good candidate that is written to the
876      dump file, if there is one.  */
877   const char *m_reason;
878 
879   /* True if default case is not used for any value between range_min and
880      range_max inclusive.  */
881   bool m_contiguous_range;
882 
883   /* True if default case does not have the required shape for other case
884      labels.  */
885   bool m_default_case_nonstandard;
886 
887   /* Number of uniq labels for non-default edges.  */
888   unsigned int m_uniq;
889 
890   /* Count is number of non-default edges.  */
891   unsigned int m_count;
892 
893   /* True if CFG has been changed.  */
894   bool m_cfg_altered;
895 };
896 
897 void
reset_out_edges_aux(gswitch * swtch)898 switch_decision_tree::reset_out_edges_aux (gswitch *swtch)
899 {
900   basic_block bb = gimple_bb (swtch);
901   edge e;
902   edge_iterator ei;
903   FOR_EACH_EDGE (e, ei, bb->succs)
904     e->aux = (void *) 0;
905 }
906 
907 /* Release CLUSTERS vector and destruct all dynamically allocated items.  */
908 
909 static inline void
release_clusters(vec<cluster * > & clusters)910 release_clusters (vec<cluster *> &clusters)
911 {
912   for (unsigned i = 0; i < clusters.length (); i++)
913     delete clusters[i];
914   clusters.release ();
915 }
916 
917 } // tree_switch_conversion namespace
918 
919 #endif // TREE_SWITCH_CONVERSION_H
920