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 are of
401 type simple_cluster. Use a fast algorithm that might not find the optimal
402 solution (minimal number of clusters on the output). New clusters are
403 returned.
404
405 You should call find_bit_tests () instead of calling this function
406 directly. */
407 static vec<cluster *> find_bit_tests_fast (vec<cluster *> &clusters);
408
409 /* Find bit tests of given CLUSTERS, where all members of the vector
410 are of type simple_cluster. Use a slow (quadratic) algorithm that always
411 finds the optimal solution (minimal number of clusters on the output). New
412 clusters are returned.
413
414 You should call find_bit_tests () instead of calling this function
415 directly. */
416 static vec<cluster *> find_bit_tests_slow (vec<cluster *> &clusters);
417
418 /* Find bit tests of given CLUSTERS, where all members of the vector
419 are of type simple_cluster. New clusters are returned. */
420 static vec<cluster *> find_bit_tests (vec<cluster *> &clusters, int max_c);
421
422 /* Return true when RANGE of case values with UNIQ labels
423 can build a bit test. */
424 static bool can_be_handled (unsigned HOST_WIDE_INT range, unsigned uniq);
425
426 /* Return true when cluster starting at START and ending at END (inclusive)
427 can build a bit test. */
428 static bool can_be_handled (const vec<cluster *> &clusters, unsigned start,
429 unsigned end);
430
431 /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test
432 transformation. */
433 static bool is_beneficial (unsigned count, unsigned uniq);
434
435 /* Return true if cluster starting at START and ending at END (inclusive)
436 is profitable transformation. */
437 static bool is_beneficial (const vec<cluster *> &clusters, unsigned start,
438 unsigned end);
439
440/* Split the basic block at the statement pointed to by GSIP, and insert
441 a branch to the target basic block of E_TRUE conditional on tree
442 expression COND.
443
444 It is assumed that there is already an edge from the to-be-split
445 basic block to E_TRUE->dest block. This edge is removed, and the
446 profile information on the edge is re-used for the new conditional
447 jump.
448
449 The CFG is updated. The dominator tree will not be valid after
450 this transformation, but the immediate dominators are updated if
451 UPDATE_DOMINATORS is true.
452
453 Returns the newly created basic block. */
454 static basic_block hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
455 tree cond,
456 basic_block case_bb,
458 location_t);
459
460 /* Return whether bit test expansion is allowed. */
461 static inline bool is_enabled (void)
462 {
463 return flag_bit_tests;
464 }
465
466 /* True when the jump table handles an entire switch statement. */
468
469 /* Maximum number of different basic blocks that can be handled by
470 a bit test. */
471 static const int m_max_case_bit_tests = 3;
472};
473
474/* Helper struct to find minimal clusters. */
475
477{
478public:
479 /* Constructor. */
480 min_cluster_item (unsigned count, unsigned start, unsigned non_jt_cases):
481 m_count (count), m_start (start), m_non_jt_cases (non_jt_cases)
482 {}
483
484 /* Count of clusters. */
485 unsigned m_count;
486
487 /* Index where is cluster boundary. */
488 unsigned m_start;
489
490 /* Total number of cases that will not be in a jump table. */
492};
493
494/* Helper struct to represent switch decision tree. */
495
497{
498public:
499 /* Empty Constructor. */
501
502 /* Return true when it has a child. */
503 bool has_child ()
504 {
505 return m_left != NULL || m_right != NULL;
506 }
507
508 /* Left son in binary tree. */
510
511 /* Right son in binary tree; also node chain. */
513
514 /* Parent of node in binary tree. */
516
517 /* Cluster represented by this tree node. */
519};
520
521inline
523 m_left (NULL), m_right (NULL), m_parent (NULL), m_c (NULL)
524{
525}
526
527unsigned int
529{
530 unsigned int threshold = param_case_values_threshold;
531
532 if (threshold == 0)
533 threshold = targetm.case_values_threshold ();
534
535 return threshold;
536}
537
538/* Return whether jump table expansion is allowed. */
540{
541 /* If neither casesi or tablejump is available, or flag_jump_tables
542 over-ruled us, we really have no choice. */
543 if (!targetm.have_casesi () && !targetm.have_tablejump ())
544 return false;
545 if (!flag_jump_tables)
546 return false;
547#ifndef ASM_OUTPUT_ADDR_DIFF_ELT
548 if (flag_pic)
549 return false;
550#endif
551
552 return true;
553}
554
555/* A case_bit_test represents a set of case nodes that may be
556 selected from using a bit-wise comparison. HI and LO hold
557 the integer to be tested against, TARGET_EDGE contains the
558 edge to the basic block to jump to upon success and BITS
559 counts the number of case nodes handled by this test,
560 typically the number of bits set in HI:LO. The LABEL field
561 is used to quickly identify all cases in this set without
562 looking at label_to_block for every case label. */
563
565{
566public:
570 int bits;
572
573 /* Comparison function for qsort to order bit tests by decreasing
574 probability of execution. */
575 static int cmp (const void *p1, const void *p2);
576};
577
579{
580public:
581 /* Constructor. */
583 m_case_bbs (), m_case_node_pool ("struct case_node pool"),
585 {
586 }
587
588 /* Analyze switch statement and return true when the statement is expanded
589 as decision tree. */
591
592 /* Attempt to expand CLUSTERS as a decision tree. Return true when
593 expanded. */
594 bool try_switch_expansion (vec<cluster *> &clusters);
595 /* Compute the number of case labels that correspond to each outgoing edge of
596 switch statement. Record this information in the aux field of the edge.
597 Returns approx max number of cases per edge.
598 */
600
601 /* Before switch transformation, record all SSA_NAMEs defined in switch BB
602 and used in a label basic block. */
604
605 /* Append new operands to PHI statements that were introduced due to
606 addition of new edges to case labels. */
608
609 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
610 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
611
612 We generate a binary decision tree to select the appropriate target
613 code. */
614 void emit (basic_block bb, tree index_expr,
615 profile_probability default_prob, tree index_type);
616
617 /* Emit step-by-step code to select a case for the value of INDEX.
618 The thus generated decision tree follows the form of the
619 case-node binary tree NODE, whose nodes represent test conditions.
620 DEFAULT_PROB is probability of cases leading to default BB.
621 INDEX_TYPE is the type of the index of the switch. */
623 case_tree_node *node,
624 profile_probability default_prob,
625 tree index_type, location_t);
626
627 /* Take an ordered list of case nodes
628 and transform them into a near optimal binary tree,
629 on the assumption that any target code selection value is as
630 likely as any other.
631
632 The transformation is performed by splitting the ordered
633 list into two equal sections plus a pivot. The parts are
634 then attached to the pivot as left and right branches. Each
635 branch is then transformed recursively. */
637 case_tree_node *parent);
638
639 /* Dump ROOT, a list or tree of case nodes, to file F. */
640 static void dump_case_nodes (FILE *f, case_tree_node *root, int indent_step,
641 int indent_level);
642
643 /* Add an unconditional jump to CASE_BB that happens in basic block BB. */
644 static void emit_jump (basic_block bb, basic_block case_bb);
645
646 /* Generate code to compare OP0 with OP1 so that the condition codes are
647 set and to jump to LABEL_BB if the condition is true.
648 COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
649 PROB is the probability of jumping to LABEL_BB. */
652 basic_block label_bb,
654 location_t);
655
656 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
657 PROB is the probability of jumping to LABEL_BB. */
658 static basic_block do_jump_if_equal (basic_block bb, tree op0, tree op1,
659 basic_block label_bb,
661 location_t);
662
663 /* Reset the aux field of all outgoing edges of switch basic block. */
664 static inline void reset_out_edges_aux (gswitch *swtch);
665
666 /* Switch statement. */
668
669 /* Map of PHI nodes that have to be fixed after expansion. */
671
672 /* List of basic blocks that belong to labels of the switch. */
674
675 /* Basic block with default label. */
677
678 /* A pool for case nodes. */
680
681 /* Balanced tree of case nodes. */
683};
684
685/*
686 Switch initialization conversion
687
688The following pass changes simple initializations of scalars in a switch
689statement into initializations from a static array. Obviously, the values
690must be constant and known at compile time and a default branch must be
691provided. For example, the following code:
692
693 int a,b;
694
695 switch (argc)
696 {
697 case 1:
698 case 2:
699 a_1 = 8;
700 b_1 = 6;
701 break;
702 case 3:
703 a_2 = 9;
704 b_2 = 5;
705 break;
706 case 12:
707 a_3 = 10;
708 b_3 = 4;
709 break;
710 default:
711 a_4 = 16;
712 b_4 = 1;
713 break;
714 }
715 a_5 = PHI <a_1, a_2, a_3, a_4>
716 b_5 = PHI <b_1, b_2, b_3, b_4>
717
718
719is changed into:
720
721 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
722 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
723 16, 16, 10};
724
725 if (((unsigned) argc) - 1 < 11)
726 {
727 a_6 = CSWTCH02[argc - 1];
728 b_6 = CSWTCH01[argc - 1];
729 }
730 else
731 {
732 a_7 = 16;
733 b_7 = 1;
734 }
735 a_5 = PHI <a_6, a_7>
736 b_b = PHI <b_6, b_7>
737
738There are further constraints. Specifically, the range of values across all
739case labels must not be bigger than param_switch_conversion_branch_ratio
740(default eight) times the number of the actual switch branches.
741
742This transformation was contributed by Martin Jambor, see this e-mail:
743 http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
744
745/* The main structure of the pass. */
747{
748public:
749 /* Constructor. */
751
752 /* Destructor. */
754
755 /* The following function is invoked on every switch statement (the current
756 one is given in SWTCH) and runs the individual phases of switch
757 conversion on it one after another until one fails or the conversion
758 is completed. On success, NULL is in m_reason, otherwise points
759 to a string with the reason why the conversion failed. */
760 void expand (gswitch *swtch);
761
762 /* Collection information about SWTCH statement. */
763 void collect (gswitch *swtch);
764
765 /* Check that the 'exponential index transform' can be applied.
766
767 See the comment at the function definition for more details. */
769
770 /* Perform the 'exponential index transform'.
771
772 The exponential index transform shrinks the range of case numbers which
773 helps switch conversion convert switches it otherwise could not.
774
775 See the comment at the function definition for more details. */
776 void exp_index_transform (gswitch *swtch);
777
778 /* Checks whether the range given by individual case statements of the switch
779 switch statement isn't too big and whether the number of branches actually
780 satisfies the size of the new array. */
781 bool check_range ();
782
783 /* Checks whether all but the final BB basic blocks are empty. */
785
786 /* This function checks whether all required values in phi nodes in final_bb
787 are constants. Required values are those that correspond to a basic block
788 which is a part of the examined switch statement. It returns true if the
789 phi nodes are OK, otherwise false. */
790 bool check_final_bb ();
791
792 /* The following function allocates default_values, target_{in,out}_names and
793 constructors arrays. The last one is also populated with pointers to
794 vectors that will become constructors of new arrays. */
795 void create_temp_arrays ();
796
797 /* Populate the array of default values in the order of phi nodes.
798 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
799 if the range is non-contiguous or the default case has standard
800 structure, otherwise it is the first non-default case instead. */
801 void gather_default_values (tree default_case);
802
803 /* The following function populates the vectors in the constructors array with
804 future contents of the static arrays. The vectors are populated in the
805 order of phi nodes. */
806 void build_constructors ();
807
808 /* If all values in the constructor vector are products of a linear function
809 a * x + b, then return true. When true, COEFF_A and COEFF_B and
810 coefficients of the linear function. Note that equal values are special
811 case of a linear function with a and b equal to zero. */
813 wide_int *coeff_a, wide_int *coeff_b);
814
815 /* Return type which should be used for array elements, either TYPE's
816 main variant or, for integral types, some smaller integral type
817 that can still hold all the constants. */
818 tree array_value_type (tree type, int num);
819
820 /* Create an appropriate array type and declaration and assemble a static
821 array variable. Also create a load statement that initializes
822 the variable in question with a value from the static array. SWTCH is
823 the switch statement being converted, NUM is the index to
824 arrays of constructors, default values and target SSA names
825 for this particular array. ARR_INDEX_TYPE is the type of the index
826 of the new array, PHI is the phi node of the final BB that corresponds
827 to the value that will be loaded from the created array. TIDX
828 is an ssa name of a temporary variable holding the index for loads from the
829 new array. */
830 void build_one_array (int num, tree arr_index_type,
831 gphi *phi, tree tidx);
832
833 /* Builds and initializes static arrays initialized with values gathered from
834 the switch statement. Also creates statements that load values from
835 them. */
836 void build_arrays ();
837
838 /* Generates and appropriately inserts loads of default values at the position
839 given by GSI. Returns the last inserted statement. */
841
842 /* Deletes the unused bbs and edges that now contain the switch statement and
843 its empty branch bbs. BBD is the now dead BB containing
844 the original switch statement, FINAL is the last BB of the converted
845 switch statement (in terms of succession). */
846 void prune_bbs (basic_block bbd, basic_block final, basic_block default_bb);
847
848 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
849 from the basic block loading values from an array and E2F from the basic
850 block loading default values. BBF is the last switch basic block (see the
851 bbf description in the comment below). */
852 void fix_phi_nodes (edge e1f, edge e2f, basic_block bbf);
853
854 /* Creates a check whether the switch expression value actually falls into the
855 range given by all the cases. If it does not, the temporaries are loaded
856 with default values instead. */
857 void gen_inbound_check ();
858
859 /* Switch statement for which switch conversion takes place. */
861
862 /* The expression used to decide the switch branch. */
864
865 /* The following integer constants store the minimum and maximum value
866 covered by the case labels. */
869
870 /* The difference between the above two numbers. Stored here because it
871 is used in all the conversion heuristics, as well as for some of the
872 transformation, and it is expensive to re-compute it all the time. */
874
875 /* Basic block that contains the actual GIMPLE_SWITCH. */
877
878 /* Basic block that is the target of the default case. */
880
881 /* The single successor block of all branches out of the GIMPLE_SWITCH,
882 if such a block exists. Otherwise NULL. */
884
885 /* The probability of the default edge in the replaced switch. */
887
888 /* Number of phi nodes in the final bb (that we'll be replacing). */
890
891 /* Constructors of new static arrays. */
893
894 /* Array of default values, in the same order as phi nodes. */
896
897 /* Array of ssa names that are initialized with a value from a new static
898 array. */
900
901 /* Array of ssa names that are initialized with the default value if the
902 switch expression is out of range. */
904
905 /* VOP SSA_NAME. */
907
908 /* The first load statement that loads a temporary from a new static array.
909 */
911
912 /* The last load statement that loads a temporary from a new static array. */
914
915 /* String reason why the case wasn't a good candidate that is written to the
916 dump file, if there is one. */
917 const char *m_reason;
918
919 /* True if default case is not used for any value between range_min and
920 range_max inclusive. */
922
923 /* True if default case does not have the required shape for other case
924 labels. */
926
927 /* Number of uniq labels for non-default edges. */
928 unsigned int m_uniq;
929
930 /* Count is number of non-default edges. */
931 unsigned int m_count;
932
933 /* True if CFG has been changed. */
935
936 /* True if exponential index transform has been applied. See the comment at
937 the definition of exp_index_transform for details about the
938 transformation. */
940
941 /* If switch conversion decided exponential index transform is viable, here
942 will be stored the type to which index variable has to be converted
943 before the logarithm operation which is a part of the transform. */
945};
946
947void
949{
950 basic_block bb = gimple_bb (swtch);
951 edge e;
952 edge_iterator ei;
953 FOR_EACH_EDGE (e, ei, bb->succs)
954 e->aux = (void *) 0;
955}
956
957/* Release CLUSTERS vector and destruct all dynamically allocated items. */
958
959inline void
961{
962 for (unsigned i = 0; i < clusters.length (); i++)
963 delete clusters[i];
964 clusters.release ();
965}
966
967} // tree_switch_conversion namespace
968
969#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:467
static bool is_enabled(void)
Definition tree-switch-conversion.h:461
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:565
wide_int mask
Definition tree-switch-conversion.h:567
basic_block target_bb
Definition tree-switch-conversion.h:568
tree label
Definition tree-switch-conversion.h:569
int bits
Definition tree-switch-conversion.h:570
profile_probability prob
Definition tree-switch-conversion.h:571
static int cmp(const void *p1, const void *p2)
Definition tree-switch-conversion.cc:2019
Definition tree-switch-conversion.h:497
case_tree_node * m_right
Definition tree-switch-conversion.h:512
case_tree_node * m_parent
Definition tree-switch-conversion.h:515
bool has_child()
Definition tree-switch-conversion.h:503
case_tree_node * m_left
Definition tree-switch-conversion.h:509
cluster * m_c
Definition tree-switch-conversion.h:518
case_tree_node()
Definition tree-switch-conversion.h:522
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:1460
vec< simple_cluster * > m_cases
Definition tree-switch-conversion.h:252
~group_cluster()
Definition tree-switch-conversion.cc:1476
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:1487
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:539
static unsigned int case_values_threshold(void)
Definition tree-switch-conversion.h:528
Definition tree-switch-conversion.h:477
min_cluster_item(unsigned count, unsigned start, unsigned non_jt_cases)
Definition tree-switch-conversion.h:480
unsigned m_start
Definition tree-switch-conversion.h:488
unsigned m_count
Definition tree-switch-conversion.h:485
unsigned m_non_jt_cases
Definition tree-switch-conversion.h:491
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:747
basic_block m_switch_bb
Definition tree-switch-conversion.h:876
int m_phi_count
Definition tree-switch-conversion.h:889
gimple * m_arr_ref_last
Definition tree-switch-conversion.h:913
unsigned int m_count
Definition tree-switch-conversion.h:931
tree * m_target_outbound_names
Definition tree-switch-conversion.h:903
bool m_exp_index_transform_applied
Definition tree-switch-conversion.h:939
bool contains_linear_function_p(vec< constructor_elt, va_gc > *vec, wide_int *coeff_a, wide_int *coeff_b)
Definition tree-switch-conversion.cc:822
gimple * m_arr_ref_first
Definition tree-switch-conversion.h:910
gassign * gen_def_assigns(gimple_stmt_iterator *gsi)
Definition tree-switch-conversion.cc:1132
tree m_range_min
Definition tree-switch-conversion.h:867
void expand(gswitch *swtch)
Definition tree-switch-conversion.cc:1358
void build_constructors()
Definition tree-switch-conversion.cc:741
tree array_value_type(tree type, int num)
Definition tree-switch-conversion.cc:882
tree m_range_max
Definition tree-switch-conversion.h:868
void create_temp_arrays()
Definition tree-switch-conversion.cc:689
void exp_index_transform(gswitch *swtch)
Definition tree-switch-conversion.cc:399
void gather_default_values(tree default_case)
Definition tree-switch-conversion.cc:710
void build_one_array(int num, tree arr_index_type, gphi *phi, tree tidx)
Definition tree-switch-conversion.cc:968
tree m_index_expr
Definition tree-switch-conversion.h:863
tree * m_target_inbound_names
Definition tree-switch-conversion.h:899
bool m_default_case_nonstandard
Definition tree-switch-conversion.h:925
bool check_range()
Definition tree-switch-conversion.cc:554
tree * m_default_values
Definition tree-switch-conversion.h:895
void collect(gswitch *swtch)
Definition tree-switch-conversion.cc:181
basic_block m_final_bb
Definition tree-switch-conversion.h:883
const char * m_reason
Definition tree-switch-conversion.h:917
void fix_phi_nodes(edge e1f, edge e2f, basic_block bbf)
Definition tree-switch-conversion.cc:1177
~switch_conversion()
Definition tree-switch-conversion.cc:1452
void build_arrays()
Definition tree-switch-conversion.cc:1060
switch_conversion()
Definition tree-switch-conversion.cc:170
basic_block m_default_bb
Definition tree-switch-conversion.h:879
bool check_all_empty_except_final()
Definition tree-switch-conversion.cc:576
tree m_range_size
Definition tree-switch-conversion.h:873
tree m_exp_index_transform_log2_type
Definition tree-switch-conversion.h:944
unsigned int m_uniq
Definition tree-switch-conversion.h:928
bool m_contiguous_range
Definition tree-switch-conversion.h:921
bool check_final_bb()
Definition tree-switch-conversion.cc:608
profile_probability m_default_prob
Definition tree-switch-conversion.h:886
bool is_exp_index_transform_viable(gswitch *swtch)
Definition tree-switch-conversion.cc:322
void gen_inbound_check()
Definition tree-switch-conversion.cc:1205
void prune_bbs(basic_block bbd, basic_block final, basic_block default_bb)
Definition tree-switch-conversion.cc:1154
tree m_target_vop
Definition tree-switch-conversion.h:906
bool m_cfg_altered
Definition tree-switch-conversion.h:934
gswitch * m_switch
Definition tree-switch-conversion.h:860
vec< constructor_elt, va_gc > ** m_constructors
Definition tree-switch-conversion.h:892
Definition tree-switch-conversion.h:579
void fix_phi_operands_for_edges()
Definition tree-switch-conversion.cc:2536
static void dump_case_nodes(FILE *f, case_tree_node *root, int indent_step, int indent_level)
Definition tree-switch-conversion.cc:2685
static void emit_jump(basic_block bb, basic_block case_bb)
Definition tree-switch-conversion.cc:2709
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:2754
static void balance_case_nodes(case_tree_node **head, case_tree_node *parent)
Definition tree-switch-conversion.cc:2609
static void reset_out_edges_aux(gswitch *swtch)
Definition tree-switch-conversion.h:948
void record_phi_operand_mapping()
Definition tree-switch-conversion.cc:2505
bool try_switch_expansion(vec< cluster * > &clusters)
Definition tree-switch-conversion.cc:2419
hash_map< tree, tree > m_phi_mapping
Definition tree-switch-conversion.h:670
switch_decision_tree(gswitch *swtch)
Definition tree-switch-conversion.h:582
void emit(basic_block bb, tree index_expr, profile_probability default_prob, tree index_type)
Definition tree-switch-conversion.cc:2569
case_tree_node * m_case_list
Definition tree-switch-conversion.h:682
gswitch * m_switch
Definition tree-switch-conversion.h:667
bool analyze_switch_statement()
Definition tree-switch-conversion.cc:2325
object_allocator< case_tree_node > m_case_node_pool
Definition tree-switch-conversion.h:679
int compute_cases_per_edge()
Definition tree-switch-conversion.cc:2303
basic_block m_default_bb
Definition tree-switch-conversion.h:676
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:2721
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:2787
auto_vec< basic_block > m_case_bbs
Definition tree-switch-conversion.h:673
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:2004
tree_code
Definition genmatch.cc:992
basic_block gimple_bb(const gimple *g)
Definition gimple.h:1861
Definition tree-switch-conversion.h:23
void release_clusters(vec< cluster * > &clusters)
Definition tree-switch-conversion.h:960
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:6439
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:903
Definition gimple-iterator.h:26
Definition gimple.h:221
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:841
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:6423
#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