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. */
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
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,
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
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
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,
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,
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. */
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,
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{
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. */
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. */
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,
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. */
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,
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 /* 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. */
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. */
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. */
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. */
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). */
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). */
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. */
829
830 /* The expression used to decide the switch branch. */
832
833 /* The following integer constants store the minimum and maximum value
834 covered by the case labels. */
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. */
842
843 /* Basic block that contains the actual GIMPLE_SWITCH. */
845
846 /* Basic block that is the target of the default case. */
848
849 /* The single successor block of all branches out of the GIMPLE_SWITCH,
850 if such a block exists. Otherwise NULL. */
852
853 /* The probability of the default edge in the replaced switch. */
855
856 /* Number of phi nodes in the final bb (that we'll be replacing). */
858
859 /* Constructors of new static arrays. */
861
862 /* Array of default values, in the same order as phi nodes. */
864
865 /* Array of ssa names that are initialized with a value from a new static
866 array. */
868
869 /* Array of ssa names that are initialized with the default value if the
870 switch expression is out of range. */
872
873 /* VOP SSA_NAME. */
875
876 /* The first load statement that loads a temporary from a new static array.
877 */
879
880 /* The last load statement that loads a temporary from a new static array. */
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. */
890
891 /* True if default case does not have the required shape for other case
892 labels. */
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. */
903};
904
905void
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
917inline void
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
#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
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:1571
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:1101
vec< simple_cluster * > m_cases
Definition tree-switch-conversion.h:252
~group_cluster()
Definition tree-switch-conversion.cc:1117
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:1128
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:844
int m_phi_count
Definition tree-switch-conversion.h:857
gimple * m_arr_ref_last
Definition tree-switch-conversion.h:881
unsigned int m_count
Definition tree-switch-conversion.h:899
tree * m_target_outbound_names
Definition tree-switch-conversion.h:871
bool contains_linear_function_p(vec< constructor_elt, va_gc > *vec, wide_int *coeff_a, wide_int *coeff_b)
Definition tree-switch-conversion.cc:478
gimple * m_arr_ref_first
Definition tree-switch-conversion.h:878
gassign * gen_def_assigns(gimple_stmt_iterator *gsi)
Definition tree-switch-conversion.cc:788
tree m_range_min
Definition tree-switch-conversion.h:835
void expand(gswitch *swtch)
Definition tree-switch-conversion.cc:1013
void build_constructors()
Definition tree-switch-conversion.cc:397
tree array_value_type(tree type, int num)
Definition tree-switch-conversion.cc:538
tree m_range_max
Definition tree-switch-conversion.h:836
void create_temp_arrays()
Definition tree-switch-conversion.cc:345
void gather_default_values(tree default_case)
Definition tree-switch-conversion.cc:366
void build_one_array(int num, tree arr_index_type, gphi *phi, tree tidx)
Definition tree-switch-conversion.cc:624
tree m_index_expr
Definition tree-switch-conversion.h:831
tree * m_target_inbound_names
Definition tree-switch-conversion.h:867
bool m_default_case_nonstandard
Definition tree-switch-conversion.h:893
bool check_range()
Definition tree-switch-conversion.cc:210
tree * m_default_values
Definition tree-switch-conversion.h:863
void collect(gswitch *swtch)
Definition tree-switch-conversion.cc:76
basic_block m_final_bb
Definition tree-switch-conversion.h:851
const char * m_reason
Definition tree-switch-conversion.h:885
void fix_phi_nodes(edge e1f, edge e2f, basic_block bbf)
Definition tree-switch-conversion.cc:833
~switch_conversion()
Definition tree-switch-conversion.cc:1093
void build_arrays()
Definition tree-switch-conversion.cc:716
switch_conversion()
Definition tree-switch-conversion.cc:66
basic_block m_default_bb
Definition tree-switch-conversion.h:847
bool check_all_empty_except_final()
Definition tree-switch-conversion.cc:232
tree m_range_size
Definition tree-switch-conversion.h:841
unsigned int m_uniq
Definition tree-switch-conversion.h:896
bool m_contiguous_range
Definition tree-switch-conversion.h:889
bool check_final_bb()
Definition tree-switch-conversion.cc:264
profile_probability m_default_prob
Definition tree-switch-conversion.h:854
void gen_inbound_check()
Definition tree-switch-conversion.cc:861
void prune_bbs(basic_block bbd, basic_block final, basic_block default_bb)
Definition tree-switch-conversion.cc:810
tree m_target_vop
Definition tree-switch-conversion.h:874
bool m_cfg_altered
Definition tree-switch-conversion.h:902
gswitch * m_switch
Definition tree-switch-conversion.h:828
vec< constructor_elt, va_gc > ** m_constructors
Definition tree-switch-conversion.h:860
Definition tree-switch-conversion.h:561
void fix_phi_operands_for_edges()
Definition tree-switch-conversion.cc:2071
static void dump_case_nodes(FILE *f, case_tree_node *root, int indent_step, int indent_level)
Definition tree-switch-conversion.cc:2220
static void emit_jump(basic_block bb, basic_block case_bb)
Definition tree-switch-conversion.cc:2244
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:2289
static void balance_case_nodes(case_tree_node **head, case_tree_node *parent)
Definition tree-switch-conversion.cc:2144
static void reset_out_edges_aux(gswitch *swtch)
Definition tree-switch-conversion.h:906
void record_phi_operand_mapping()
Definition tree-switch-conversion.cc:2040
bool try_switch_expansion(vec< cluster * > &clusters)
Definition tree-switch-conversion.cc:1954
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:2104
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:1869
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:2256
void compute_cases_per_edge()
Definition tree-switch-conversion.cc:1854
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:2322
auto_vec< basic_block > m_case_bbs
Definition tree-switch-conversion.h:654
class edge_def * edge
Definition coretypes.h:342
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
T * ggc_alloc(ALONE_CXX_MEM_STAT_INFO)
Definition ggc.h:184
basic_block gimple_bb(const gimple *g)
Definition gimple.h:1859
Definition tree-switch-conversion.h:23
void release_clusters(vec< cluster * > &clusters)
Definition tree-switch-conversion.h:918
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:6372
i
Definition poly-int.h:772
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:903
Definition gimple-iterator.h:26
Definition gimple.h:225
Definition gimple.h:461
Definition gimple.h:894
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:6376
#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