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