GCC Middle and Back End API Reference
tree-switch-conversion.h
Go to the documentation of this file.
1/* Tree switch conversion for GNU compiler.
2 Copyright (C) 2017-2024 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
24
25/* Type of cluster. */
26
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
48{
49public:
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. */
95
96 /* Basic block of the case. */
98
99 /* Probability of taking this cluster. */
101
102 /* Probability of reaching subtree rooted at this node. */
104
105 /* Probability of default case when reaching the node.
106 It is used by bit-test right now. */
108
109protected:
110 /* Default constructor. */
112};
113
114cluster::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
126{
127public:
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. */
136
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 {
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
191 {
192 return m_range_p ? 2 : 1;
193 }
194
195 /* Low value of the case. */
197
198 /* High value of the case. */
200
201 /* True if case is a range. */
203
204 /* True if the case will use a forwarder BB. */
206};
207
208simple_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
223{
224public:
225 /* Constructor. */
226 group_cluster (vec<cluster *> &clusters, unsigned start, unsigned end);
227
228 /* Destructor. */
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. */
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
261{
262public:
263 /* Constructor. */
264 jump_table_cluster (vec<cluster *> &clusters, unsigned start, unsigned end)
265 : group_cluster (clusters, start, end)
266 {}
267
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
304comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
305where CST and MINVAL are integer constants. This is better than a series
306of compare-and-branch insns in some cases, e.g. we can implement:
307
308 if ((x==4) || (x==6) || (x==9) || (x==11))
309
310as a single bit test:
311
312 if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
313
314This transformation is only applied if the number of case targets is small,
315if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are
316performed in "word_mode".
317
318The 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
348TODO: There are still some improvements to this transformation that could
349be 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
360This transformation was contributed by Roger Sayle, see this e-mail:
361 http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
362*/
363
365{
366public:
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
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,
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. */
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
459{
460public:
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. */
474};
475
476/* Helper struct to represent switch decision tree. */
477
479{
480public:
481 /* Empty Constructor. */
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. */
492
493 /* Right son in binary tree; also node chain. */
495
496 /* Parent of node in binary tree. */
498
499 /* Cluster represented by this tree node. */
501};
502
503inline
505 m_left (NULL), m_right (NULL), m_parent (NULL), m_c (NULL)
506{
507}
508
509unsigned int
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. */
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
547{
548public:
552 int bits;
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
561{
562public:
563 /* Constructor. */
565 m_case_bbs (), m_case_node_pool ("struct case_node pool"),
567 {
568 }
569
570 /* Analyze switch statement and return true when the statement is expanded
571 as decision tree. */
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 */
581
582 /* Before switch transformation, record all SSA_NAMEs defined in switch BB
583 and used in a label basic block. */
585
586 /* Append new operands to PHI statements that were introduced due to
587 addition of new edges to case labels. */
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. */
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. */
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. */
633 basic_block label_bb,
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,
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. */
649
650 /* Map of PHI nodes that have to be fixed after expansion. */
652
653 /* List of basic blocks that belong to labels of the switch. */
655
656 /* Basic block with default label. */
658
659 /* A pool for case nodes. */
661
662 /* Balanced tree of case nodes. */
664};
665
666/*
667 Switch initialization conversion
668
669The following pass changes simple initializations of scalars in a switch
670statement into initializations from a static array. Obviously, the values
671must be constant and known at compile time and a default branch must be
672provided. 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
700is 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
719There are further constraints. Specifically, the range of values across all
720case labels must not be bigger than param_switch_conversion_branch_ratio
721(default eight) times the number of the actual switch branches.
722
723This 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. */
728{
729public:
730 /* Constructor. */
732
733 /* Destructor. */
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 /* Check that the 'exponential index transform' can be applied.
747
748 See the comment at the function definition for more details. */
750
751 /* Perform the 'exponential index transform'.
752
753 The exponential index transform shrinks the range of case numbers which
754 helps switch conversion convert switches it otherwise could not.
755
756 See the comment at the function definition for more details. */
757 void exp_index_transform (gswitch *swtch);
758
759 /* Checks whether the range given by individual case statements of the switch
760 switch statement isn't too big and whether the number of branches actually
761 satisfies the size of the new array. */
762 bool check_range ();
763
764 /* Checks whether all but the final BB basic blocks are empty. */
766
767 /* This function checks whether all required values in phi nodes in final_bb
768 are constants. Required values are those that correspond to a basic block
769 which is a part of the examined switch statement. It returns true if the
770 phi nodes are OK, otherwise false. */
771 bool check_final_bb ();
772
773 /* The following function allocates default_values, target_{in,out}_names and
774 constructors arrays. The last one is also populated with pointers to
775 vectors that will become constructors of new arrays. */
776 void create_temp_arrays ();
777
778 /* Populate the array of default values in the order of phi nodes.
779 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
780 if the range is non-contiguous or the default case has standard
781 structure, otherwise it is the first non-default case instead. */
782 void gather_default_values (tree default_case);
783
784 /* The following function populates the vectors in the constructors array with
785 future contents of the static arrays. The vectors are populated in the
786 order of phi nodes. */
787 void build_constructors ();
788
789 /* If all values in the constructor vector are products of a linear function
790 a * x + b, then return true. When true, COEFF_A and COEFF_B and
791 coefficients of the linear function. Note that equal values are special
792 case of a linear function with a and b equal to zero. */
794 wide_int *coeff_a, wide_int *coeff_b);
795
796 /* Return type which should be used for array elements, either TYPE's
797 main variant or, for integral types, some smaller integral type
798 that can still hold all the constants. */
799 tree array_value_type (tree type, int num);
800
801 /* Create an appropriate array type and declaration and assemble a static
802 array variable. Also create a load statement that initializes
803 the variable in question with a value from the static array. SWTCH is
804 the switch statement being converted, NUM is the index to
805 arrays of constructors, default values and target SSA names
806 for this particular array. ARR_INDEX_TYPE is the type of the index
807 of the new array, PHI is the phi node of the final BB that corresponds
808 to the value that will be loaded from the created array. TIDX
809 is an ssa name of a temporary variable holding the index for loads from the
810 new array. */
811 void build_one_array (int num, tree arr_index_type,
812 gphi *phi, tree tidx);
813
814 /* Builds and initializes static arrays initialized with values gathered from
815 the switch statement. Also creates statements that load values from
816 them. */
817 void build_arrays ();
818
819 /* Generates and appropriately inserts loads of default values at the position
820 given by GSI. Returns the last inserted statement. */
822
823 /* Deletes the unused bbs and edges that now contain the switch statement and
824 its empty branch bbs. BBD is the now dead BB containing
825 the original switch statement, FINAL is the last BB of the converted
826 switch statement (in terms of succession). */
827 void prune_bbs (basic_block bbd, basic_block final, basic_block default_bb);
828
829 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
830 from the basic block loading values from an array and E2F from the basic
831 block loading default values. BBF is the last switch basic block (see the
832 bbf description in the comment below). */
833 void fix_phi_nodes (edge e1f, edge e2f, basic_block bbf);
834
835 /* Creates a check whether the switch expression value actually falls into the
836 range given by all the cases. If it does not, the temporaries are loaded
837 with default values instead. */
838 void gen_inbound_check ();
839
840 /* Switch statement for which switch conversion takes place. */
842
843 /* The expression used to decide the switch branch. */
845
846 /* The following integer constants store the minimum and maximum value
847 covered by the case labels. */
850
851 /* The difference between the above two numbers. Stored here because it
852 is used in all the conversion heuristics, as well as for some of the
853 transformation, and it is expensive to re-compute it all the time. */
855
856 /* Basic block that contains the actual GIMPLE_SWITCH. */
858
859 /* Basic block that is the target of the default case. */
861
862 /* The single successor block of all branches out of the GIMPLE_SWITCH,
863 if such a block exists. Otherwise NULL. */
865
866 /* The probability of the default edge in the replaced switch. */
868
869 /* Number of phi nodes in the final bb (that we'll be replacing). */
871
872 /* Constructors of new static arrays. */
874
875 /* Array of default values, in the same order as phi nodes. */
877
878 /* Array of ssa names that are initialized with a value from a new static
879 array. */
881
882 /* Array of ssa names that are initialized with the default value if the
883 switch expression is out of range. */
885
886 /* VOP SSA_NAME. */
888
889 /* The first load statement that loads a temporary from a new static array.
890 */
892
893 /* The last load statement that loads a temporary from a new static array. */
895
896 /* String reason why the case wasn't a good candidate that is written to the
897 dump file, if there is one. */
898 const char *m_reason;
899
900 /* True if default case is not used for any value between range_min and
901 range_max inclusive. */
903
904 /* True if default case does not have the required shape for other case
905 labels. */
907
908 /* Number of uniq labels for non-default edges. */
909 unsigned int m_uniq;
910
911 /* Count is number of non-default edges. */
912 unsigned int m_count;
913
914 /* True if CFG has been changed. */
916
917 /* True if exponential index transform has been applied. See the comment at
918 the definition of exp_index_transform for details about the
919 transformation. */
921
922 /* If switch conversion decided exponential index transform is viable, here
923 will be stored the type to which index variable has to be converted
924 before the logarithm operation which is a part of the transform. */
926};
927
928void
930{
931 basic_block bb = gimple_bb (swtch);
932 edge e;
933 edge_iterator ei;
934 FOR_EACH_EDGE (e, ei, bb->succs)
935 e->aux = (void *) 0;
936}
937
938/* Release CLUSTERS vector and destruct all dynamically allocated items. */
939
940inline void
942{
943 for (unsigned i = 0; i < clusters.length (); i++)
944 delete clusters[i];
945 clusters.release ();
946}
947
948} // tree_switch_conversion namespace
949
950#endif // TREE_SWITCH_CONVERSION_H
#define FOR_EACH_EDGE(EDGE, ITER, EDGE_VEC)
Definition basic-block.h:487
static bbro_basic_block_data * bbd
Definition bb-reorder.cc:177
Definition vec.h:1656
unsigned HOST_WIDE_INT to_uhwi(unsigned int) const
Definition wide-int.h:887
Definition hash-map.h:40
Definition alloc-pool.h:482
Definition profile-count.h:147
Definition tree-switch-conversion.h:365
bool m_handles_entire_switch
Definition tree-switch-conversion.h:449
static bool is_enabled(void)
Definition tree-switch-conversion.h:443
bit_test_cluster(vec< cluster * > &clusters, unsigned start, unsigned end, bool handles_entire_switch)
Definition tree-switch-conversion.h:368
cluster_type get_type() final override
Definition tree-switch-conversion.h:375
static bool can_be_handled(unsigned HOST_WIDE_INT range, unsigned uniq)
Definition tree-switch-conversion.h:547
wide_int mask
Definition tree-switch-conversion.h:549
basic_block target_bb
Definition tree-switch-conversion.h:550
tree label
Definition tree-switch-conversion.h:551
int bits
Definition tree-switch-conversion.h:552
profile_probability prob
Definition tree-switch-conversion.h:553
static int cmp(const void *p1, const void *p2)
Definition tree-switch-conversion.cc:1929
Definition tree-switch-conversion.h:479
case_tree_node * m_right
Definition tree-switch-conversion.h:494
case_tree_node * m_parent
Definition tree-switch-conversion.h:497
bool has_child()
Definition tree-switch-conversion.h:485
case_tree_node * m_left
Definition tree-switch-conversion.h:491
cluster * m_c
Definition tree-switch-conversion.h:500
case_tree_node()
Definition tree-switch-conversion.h:504
Definition tree-switch-conversion.h:48
profile_probability m_default_prob
Definition tree-switch-conversion.h:107
virtual void dump(FILE *f, bool details=false)=0
static unsigned HOST_WIDE_INT get_range(tree low, tree high)
Definition tree-switch-conversion.h:85
virtual void emit(tree, tree, tree, basic_block, location_t)=0
cluster()
Definition tree-switch-conversion.h:111
virtual bool is_single_value_p()
Definition tree-switch-conversion.h:78
profile_probability m_prob
Definition tree-switch-conversion.h:100
tree m_case_label_expr
Definition tree-switch-conversion.h:94
virtual ~cluster()
Definition tree-switch-conversion.h:55
virtual cluster_type get_type()=0
basic_block m_case_bb
Definition tree-switch-conversion.h:97
profile_probability m_subtree_prob
Definition tree-switch-conversion.h:103
Definition tree-switch-conversion.h:223
group_cluster(vec< cluster * > &clusters, unsigned start, unsigned end)
Definition tree-switch-conversion.cc:1459
vec< simple_cluster * > m_cases
Definition tree-switch-conversion.h:252
~group_cluster()
Definition tree-switch-conversion.cc:1475
void debug() final override
Definition tree-switch-conversion.h:244
tree get_high() final override
Definition tree-switch-conversion.h:238
void dump(FILE *f, bool details=false) final override
Definition tree-switch-conversion.cc:1486
tree get_low() final override
Definition tree-switch-conversion.h:232
Definition tree-switch-conversion.h:261
jump_table_cluster(vec< cluster * > &clusters, unsigned start, unsigned end)
Definition tree-switch-conversion.h:264
cluster_type get_type() final override
Definition tree-switch-conversion.h:269
static bool is_enabled(void)
Definition tree-switch-conversion.h:521
static unsigned int case_values_threshold(void)
Definition tree-switch-conversion.h:510
Definition tree-switch-conversion.h:459
min_cluster_item(unsigned count, unsigned start, unsigned non_jt_cases)
Definition tree-switch-conversion.h:462
unsigned m_start
Definition tree-switch-conversion.h:470
unsigned m_count
Definition tree-switch-conversion.h:467
unsigned m_non_jt_cases
Definition tree-switch-conversion.h:473
Definition tree-switch-conversion.h:126
void emit(tree, tree, tree, basic_block, location_t) final override
Definition tree-switch-conversion.h:178
simple_cluster(tree low, tree high, tree case_label_expr, basic_block case_bb, profile_probability prob, bool has_forward_bb=false)
Definition tree-switch-conversion.h:208
~simple_cluster()
Definition tree-switch-conversion.h:134
void debug() final override
Definition tree-switch-conversion.h:161
void set_high(tree high)
Definition tree-switch-conversion.h:155
bool is_single_value_p() final override
Definition tree-switch-conversion.h:183
bool m_range_p
Definition tree-switch-conversion.h:202
tree get_low() final override
Definition tree-switch-conversion.h:144
tree m_low
Definition tree-switch-conversion.h:196
bool m_has_forward_bb
Definition tree-switch-conversion.h:205
tree m_high
Definition tree-switch-conversion.h:199
unsigned get_comparison_count()
Definition tree-switch-conversion.h:190
cluster_type get_type() final override
Definition tree-switch-conversion.h:138
tree get_high() final override
Definition tree-switch-conversion.h:150
void dump(FILE *f, bool details=false) final override
Definition tree-switch-conversion.h:167
Definition tree-switch-conversion.h:728
basic_block m_switch_bb
Definition tree-switch-conversion.h:857
int m_phi_count
Definition tree-switch-conversion.h:870
gimple * m_arr_ref_last
Definition tree-switch-conversion.h:894
unsigned int m_count
Definition tree-switch-conversion.h:912
tree * m_target_outbound_names
Definition tree-switch-conversion.h:884
bool m_exp_index_transform_applied
Definition tree-switch-conversion.h:920
bool contains_linear_function_p(vec< constructor_elt, va_gc > *vec, wide_int *coeff_a, wide_int *coeff_b)
Definition tree-switch-conversion.cc:821
gimple * m_arr_ref_first
Definition tree-switch-conversion.h:891
gassign * gen_def_assigns(gimple_stmt_iterator *gsi)
Definition tree-switch-conversion.cc:1131
tree m_range_min
Definition tree-switch-conversion.h:848
void expand(gswitch *swtch)
Definition tree-switch-conversion.cc:1357
void build_constructors()
Definition tree-switch-conversion.cc:740
tree array_value_type(tree type, int num)
Definition tree-switch-conversion.cc:881
tree m_range_max
Definition tree-switch-conversion.h:849
void create_temp_arrays()
Definition tree-switch-conversion.cc:688
void exp_index_transform(gswitch *swtch)
Definition tree-switch-conversion.cc:398
void gather_default_values(tree default_case)
Definition tree-switch-conversion.cc:709
void build_one_array(int num, tree arr_index_type, gphi *phi, tree tidx)
Definition tree-switch-conversion.cc:967
tree m_index_expr
Definition tree-switch-conversion.h:844
tree * m_target_inbound_names
Definition tree-switch-conversion.h:880
bool m_default_case_nonstandard
Definition tree-switch-conversion.h:906
bool check_range()
Definition tree-switch-conversion.cc:553
tree * m_default_values
Definition tree-switch-conversion.h:876
void collect(gswitch *swtch)
Definition tree-switch-conversion.cc:180
basic_block m_final_bb
Definition tree-switch-conversion.h:864
const char * m_reason
Definition tree-switch-conversion.h:898
void fix_phi_nodes(edge e1f, edge e2f, basic_block bbf)
Definition tree-switch-conversion.cc:1176
~switch_conversion()
Definition tree-switch-conversion.cc:1451
void build_arrays()
Definition tree-switch-conversion.cc:1059
switch_conversion()
Definition tree-switch-conversion.cc:169
basic_block m_default_bb
Definition tree-switch-conversion.h:860
bool check_all_empty_except_final()
Definition tree-switch-conversion.cc:575
tree m_range_size
Definition tree-switch-conversion.h:854
tree m_exp_index_transform_log2_type
Definition tree-switch-conversion.h:925
unsigned int m_uniq
Definition tree-switch-conversion.h:909
bool m_contiguous_range
Definition tree-switch-conversion.h:902
bool check_final_bb()
Definition tree-switch-conversion.cc:607
profile_probability m_default_prob
Definition tree-switch-conversion.h:867
bool is_exp_index_transform_viable(gswitch *swtch)
Definition tree-switch-conversion.cc:321
void gen_inbound_check()
Definition tree-switch-conversion.cc:1204
void prune_bbs(basic_block bbd, basic_block final, basic_block default_bb)
Definition tree-switch-conversion.cc:1153
tree m_target_vop
Definition tree-switch-conversion.h:887
bool m_cfg_altered
Definition tree-switch-conversion.h:915
gswitch * m_switch
Definition tree-switch-conversion.h:841
vec< constructor_elt, va_gc > ** m_constructors
Definition tree-switch-conversion.h:873
Definition tree-switch-conversion.h:561
void fix_phi_operands_for_edges()
Definition tree-switch-conversion.cc:2429
static void dump_case_nodes(FILE *f, case_tree_node *root, int indent_step, int indent_level)
Definition tree-switch-conversion.cc:2578
static void emit_jump(basic_block bb, basic_block case_bb)
Definition tree-switch-conversion.cc:2602
static basic_block do_jump_if_equal(basic_block bb, tree op0, tree op1, basic_block label_bb, profile_probability prob, location_t)
Definition tree-switch-conversion.cc:2647
static void balance_case_nodes(case_tree_node **head, case_tree_node *parent)
Definition tree-switch-conversion.cc:2502
static void reset_out_edges_aux(gswitch *swtch)
Definition tree-switch-conversion.h:929
void record_phi_operand_mapping()
Definition tree-switch-conversion.cc:2398
bool try_switch_expansion(vec< cluster * > &clusters)
Definition tree-switch-conversion.cc:2312
hash_map< tree, tree > m_phi_mapping
Definition tree-switch-conversion.h:651
switch_decision_tree(gswitch *swtch)
Definition tree-switch-conversion.h:564
void emit(basic_block bb, tree index_expr, profile_probability default_prob, tree index_type)
Definition tree-switch-conversion.cc:2462
case_tree_node * m_case_list
Definition tree-switch-conversion.h:663
gswitch * m_switch
Definition tree-switch-conversion.h:648
bool analyze_switch_statement()
Definition tree-switch-conversion.cc:2227
object_allocator< case_tree_node > m_case_node_pool
Definition tree-switch-conversion.h:660
basic_block m_default_bb
Definition tree-switch-conversion.h:657
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, location_t)
Definition tree-switch-conversion.cc:2614
void compute_cases_per_edge()
Definition tree-switch-conversion.cc:2212
basic_block emit_case_nodes(basic_block bb, tree index, case_tree_node *node, profile_probability default_prob, tree index_type, location_t)
Definition tree-switch-conversion.cc:2680
auto_vec< basic_block > m_case_bbs
Definition tree-switch-conversion.h:654
class edge_def * edge
Definition coretypes.h:352
union tree_node * tree
Definition coretypes.h:97
static unsigned int count[debug_counter_number_of_counters]
Definition dbgcnt.cc:50
rtx_insn * emit(rtx x, bool allow_barrier_p)
Definition emit-rtl.cc:5604
void final(rtx_insn *first, FILE *file, int optimize_p)
Definition final.cc:2002
tree_code
Definition genmatch.cc:347
basic_block gimple_bb(const gimple *g)
Definition gimple.h:1856
Definition tree-switch-conversion.h:23
void release_clusters(vec< cluster * > &clusters)
Definition tree-switch-conversion.h:941
cluster_type
Definition tree-switch-conversion.h:28
@ BIT_TEST
Definition tree-switch-conversion.h:31
@ JUMP_TABLE
Definition tree-switch-conversion.h:30
@ SIMPLE_CASE
Definition tree-switch-conversion.h:29
UNARY_PREDICATE neg_p(const T &, signop=SIGNED)
UNARY_PREDICATE fits_uhwi_p(const T &)
tree_to_wide_ref to_wide(const_tree)
Definition tree.h:6388
i
Definition poly-int.h:776
Definition basic-block.h:117
vec< edge, va_gc > * succs
Definition basic-block.h:120
Definition compare-elim.cc:91
Definition basic-block.h:366
Definition gimple.h:900
Definition gimple-iterator.h:26
Definition gimple.h:221
Definition gimple.h:458
Definition gimple.h:891
Definition collect2.cc:175
Definition gengtype.h:252
Definition vec.h:450
#define NULL
Definition system.h:50
#define gcc_unreachable()
Definition system.h:848
struct gcc_target targetm
#define PRINT_CASE(f, c)
Definition tree-switch-conversion.h:34
bool tree_int_cst_equal(const_tree t1, const_tree t2)
Definition tree.cc:6388
#define TYPE_SIGN(NODE)
Definition tree.h:952
#define TREE_TYPE(NODE)
Definition tree.h:512
T * end(vec< T, A, L > *v)
Definition vec.h:457