Daily bump.
[official-gcc.git] / gcc / tree-switch-conversion.h
blob37ed21937244ad5be6ee159f27c819bb64db6622
1 /* Tree switch conversion for GNU compiler.
2 Copyright (C) 2017 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #ifndef TREE_SWITCH_CONVERSION_H
21 #define TREE_SWITCH_CONVERSION_H
23 namespace tree_switch_conversion {
25 /* Type of cluster. */
27 enum cluster_type
29 SIMPLE_CASE,
30 JUMP_TABLE,
31 BIT_TEST
34 #define PRINT_CASE(f,c) print_generic_expr (f, c)
36 /* Abstract base class for representing a cluster of cases.
38 Here is the inheritance hierarachy, and the enum_cluster_type
39 values for the concrete subclasses:
41 cluster
42 |-simple_cluster (SIMPLE_CASE)
43 `-group_cluster
44 |-jump_table_cluster (JUMP_TABLE)
45 `-bit_test_cluster (BIT_TEST). */
47 struct cluster
49 /* Constructor. */
50 cluster (tree case_label_expr, basic_block case_bb, profile_probability prob,
51 profile_probability subtree_prob);
53 /* Destructor. */
54 virtual ~cluster ()
57 /* Return type. */
58 virtual cluster_type get_type () = 0;
60 /* Get low value covered by a cluster. */
61 virtual tree get_low () = 0;
63 /* Get high value covered by a cluster. */
64 virtual tree get_high () = 0;
66 /* Debug content of a cluster. */
67 virtual void debug () = 0;
69 /* Dump content of a cluster. */
70 virtual void dump (FILE *f, bool details = false) = 0;
72 /* Emit GIMPLE code to handle the cluster. */
73 virtual void emit (tree, tree, tree, basic_block) = 0;
75 /* Return true if a cluster handles only a single case value and the
76 value is not a range. */
77 virtual bool is_single_value_p ()
79 return false;
82 /* Return range of a cluster. If value would overflow in type of LOW,
83 then return 0. */
84 static unsigned HOST_WIDE_INT get_range (tree low, tree high)
86 tree r = fold_build2 (MINUS_EXPR, TREE_TYPE (low), high, low);
87 if (!tree_fits_uhwi_p (r))
88 return 0;
90 return tree_to_uhwi (r) + 1;
93 /* Case label. */
94 tree m_case_label_expr;
96 /* Basic block of the case. */
97 basic_block m_case_bb;
99 /* Probability of taking this cluster. */
100 profile_probability m_prob;
102 /* Probability of reaching subtree rooted at this node. */
103 profile_probability m_subtree_prob;
105 protected:
106 /* Default constructor. */
107 cluster () {}
110 cluster::cluster (tree case_label_expr, basic_block case_bb,
111 profile_probability prob, profile_probability subtree_prob):
112 m_case_label_expr (case_label_expr), m_case_bb (case_bb), m_prob (prob),
113 m_subtree_prob (subtree_prob)
117 /* Subclass of cluster representing a simple contiguous range
118 from [low..high]. */
120 struct simple_cluster: public cluster
122 /* Constructor. */
123 simple_cluster (tree low, tree high, tree case_label_expr,
124 basic_block case_bb, profile_probability prob);
126 /* Destructor. */
127 ~simple_cluster ()
130 cluster_type
131 get_type ()
133 return SIMPLE_CASE;
136 tree
137 get_low ()
139 return m_low;
142 tree
143 get_high ()
145 return m_high;
148 void
149 debug ()
151 dump (stderr);
154 void
155 dump (FILE *f, bool details ATTRIBUTE_UNUSED = false)
157 PRINT_CASE (f, get_low ());
158 if (get_low () != get_high ())
160 fprintf (f, "-");
161 PRINT_CASE (f, get_high ());
163 fprintf (f, " ");
166 void emit (tree, tree, tree, basic_block)
168 gcc_unreachable ();
171 bool is_single_value_p ()
173 return tree_int_cst_equal (get_low (), get_high ());
176 /* Low value of the case. */
177 tree m_low;
179 /* High value of the case. */
180 tree m_high;
182 /* True if case is a range. */
183 bool m_range_p;
186 simple_cluster::simple_cluster (tree low, tree high, tree case_label_expr,
187 basic_block case_bb, profile_probability prob):
188 cluster (case_label_expr, case_bb, prob, prob),
189 m_low (low), m_high (high)
191 m_range_p = m_high != NULL;
192 if (m_high == NULL)
193 m_high = m_low;
196 /* Abstract subclass of jump table and bit test cluster,
197 handling a collection of simple_cluster instances. */
199 struct group_cluster: public cluster
201 /* Constructor. */
202 group_cluster (vec<cluster *> &clusters, unsigned start, unsigned end);
204 /* Destructor. */
205 ~group_cluster ();
207 tree
208 get_low ()
210 return m_cases[0]->get_low ();
213 tree
214 get_high ()
216 return m_cases[m_cases.length () - 1]->get_high ();
219 void
220 debug ()
222 dump (stderr);
225 void dump (FILE *f, bool details = false);
227 /* List of simple clusters handled by the group. */
228 vec<simple_cluster *> m_cases;
231 /* Concrete subclass of group_cluster representing a collection
232 of cases to be implemented as a jump table.
233 The "emit" vfunc gernerates a nested switch statement which
234 is later lowered to a jump table. */
236 struct jump_table_cluster: public group_cluster
238 /* Constructor. */
239 jump_table_cluster (vec<cluster *> &clusters, unsigned start, unsigned end)
240 : group_cluster (clusters, start, end)
243 cluster_type
244 get_type ()
246 return JUMP_TABLE;
249 void emit (tree index_expr, tree index_type,
250 tree default_label_expr, basic_block default_bb);
252 /* Find jump tables of given CLUSTERS, where all members of the vector
253 are of type simple_cluster. New clusters are returned. */
254 static vec<cluster *> find_jump_tables (vec<cluster *> &clusters);
256 /* Return true when cluster starting at START and ending at END (inclusive)
257 can build a jump-table. */
258 static bool can_be_handled (const vec<cluster *> &clusters, unsigned start,
259 unsigned end);
261 /* Return true if cluster starting at START and ending at END (inclusive)
262 is profitable transformation. */
263 static bool is_beneficial (const vec<cluster *> &clusters, unsigned start,
264 unsigned end);
266 /* Return the smallest number of different values for which it is best
267 to use a jump-table instead of a tree of conditional branches. */
268 static inline unsigned int case_values_threshold (void);
270 /* Return whether jump table expansion is allowed. */
271 static bool is_enabled (void);
273 /* Max growth ratio for code that is optimized for size. */
274 static const unsigned HOST_WIDE_INT max_ratio_for_size = 3;
276 /* Max growth ratio for code that is optimized for speed. */
277 static const unsigned HOST_WIDE_INT max_ratio_for_speed = 8;
280 /* A GIMPLE switch statement can be expanded to a short sequence of bit-wise
281 comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
282 where CST and MINVAL are integer constants. This is better than a series
283 of compare-and-banch insns in some cases, e.g. we can implement:
285 if ((x==4) || (x==6) || (x==9) || (x==11))
287 as a single bit test:
289 if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
291 This transformation is only applied if the number of case targets is small,
292 if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are
293 performed in "word_mode".
295 The following example shows the code the transformation generates:
297 int bar(int x)
299 switch (x)
301 case '0': case '1': case '2': case '3': case '4':
302 case '5': case '6': case '7': case '8': case '9':
303 case 'A': case 'B': case 'C': case 'D': case 'E':
304 case 'F':
305 return 1;
307 return 0;
312 bar (int x)
314 tmp1 = x - 48;
315 if (tmp1 > (70 - 48)) goto L2;
316 tmp2 = 1 << tmp1;
317 tmp3 = 0b11111100000001111111111;
318 if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
320 return 1;
322 return 0;
325 TODO: There are still some improvements to this transformation that could
326 be implemented:
328 * A narrower mode than word_mode could be used if that is cheaper, e.g.
329 for x86_64 where a narrower-mode shift may result in smaller code.
331 * The compounded constant could be shifted rather than the one. The
332 test would be either on the sign bit or on the least significant bit,
333 depending on the direction of the shift. On some machines, the test
334 for the branch would be free if the bit to test is already set by the
335 shift operation.
337 This transformation was contributed by Roger Sayle, see this e-mail:
338 http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
341 struct bit_test_cluster: public group_cluster
343 /* Constructor. */
344 bit_test_cluster (vec<cluster *> &clusters, unsigned start, unsigned end,
345 bool handles_entire_switch)
346 :group_cluster (clusters, start, end),
347 m_handles_entire_switch (handles_entire_switch)
350 cluster_type
351 get_type ()
353 return BIT_TEST;
356 /* Expand a switch statement by a short sequence of bit-wise
357 comparisons. "switch(x)" is effectively converted into
358 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
359 integer constants.
361 INDEX_EXPR is the value being switched on.
363 MINVAL is the lowest case value of in the case nodes,
364 and RANGE is highest value minus MINVAL. MINVAL and RANGE
365 are not guaranteed to be of the same type as INDEX_EXPR
366 (the gimplifier doesn't change the type of case label values,
367 and MINVAL and RANGE are derived from those values).
368 MAXVAL is MINVAL + RANGE.
370 There *MUST* be max_case_bit_tests or less unique case
371 node targets. */
372 void emit (tree index_expr, tree index_type,
373 tree default_label_expr, basic_block default_bb);
375 /* Find bit tests of given CLUSTERS, where all members of the vector
376 are of type simple_cluster. New clusters are returned. */
377 static vec<cluster *> find_bit_tests (vec<cluster *> &clusters);
379 /* Return true when RANGE of case values with UNIQ labels
380 can build a bit test. */
381 static bool can_be_handled (unsigned HOST_WIDE_INT range, unsigned uniq);
383 /* Return true when cluster starting at START and ending at END (inclusive)
384 can build a bit test. */
385 static bool can_be_handled (const vec<cluster *> &clusters, unsigned start,
386 unsigned end);
388 /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test
389 transformation. */
390 static bool is_beneficial (unsigned count, unsigned uniq);
392 /* Return true if cluster starting at START and ending at END (inclusive)
393 is profitable transformation. */
394 static bool is_beneficial (const vec<cluster *> &clusters, unsigned start,
395 unsigned end);
397 /* Split the basic block at the statement pointed to by GSIP, and insert
398 a branch to the target basic block of E_TRUE conditional on tree
399 expression COND.
401 It is assumed that there is already an edge from the to-be-split
402 basic block to E_TRUE->dest block. This edge is removed, and the
403 profile information on the edge is re-used for the new conditional
404 jump.
406 The CFG is updated. The dominator tree will not be valid after
407 this transformation, but the immediate dominators are updated if
408 UPDATE_DOMINATORS is true.
410 Returns the newly created basic block. */
411 static basic_block hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
412 tree cond,
413 basic_block case_bb,
414 profile_probability prob);
416 /* True when the jump table handles an entire switch statement. */
417 bool m_handles_entire_switch;
419 /* Maximum number of different basic blocks that can be handled by
420 a bit test. */
421 static const int m_max_case_bit_tests = 3;
424 /* Helper struct to find minimal clusters. */
426 struct min_cluster_item
428 /* Constructor. */
429 min_cluster_item (unsigned count, unsigned start, unsigned non_jt_cases):
430 m_count (count), m_start (start), m_non_jt_cases (non_jt_cases)
433 /* Count of clusters. */
434 unsigned m_count;
436 /* Index where is cluster boundary. */
437 unsigned m_start;
439 /* Total number of cases that will not be in a jump table. */
440 unsigned m_non_jt_cases;
443 /* Helper struct to represent switch decision tree. */
445 struct case_tree_node
447 /* Empty Constructor. */
448 case_tree_node ();
450 /* Return true when it has a child. */
451 bool has_child ()
453 return m_left != NULL || m_right != NULL;
456 /* Left son in binary tree. */
457 case_tree_node *m_left;
459 /* Right son in binary tree; also node chain. */
460 case_tree_node *m_right;
462 /* Parent of node in binary tree. */
463 case_tree_node *m_parent;
465 /* Cluster represented by this tree node. */
466 cluster *m_c;
469 inline
470 case_tree_node::case_tree_node ():
471 m_left (NULL), m_right (NULL), m_parent (NULL), m_c (NULL)
475 unsigned int
476 jump_table_cluster::case_values_threshold (void)
478 unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
480 if (threshold == 0)
481 threshold = targetm.case_values_threshold ();
483 return threshold;
486 /* Return whether jump table expansion is allowed. */
487 bool jump_table_cluster::is_enabled (void)
489 /* If neither casesi or tablejump is available, or flag_jump_tables
490 over-ruled us, we really have no choice. */
491 if (!targetm.have_casesi () && !targetm.have_tablejump ())
492 return false;
493 if (!flag_jump_tables)
494 return false;
495 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
496 if (flag_pic)
497 return false;
498 #endif
500 return true;
503 /* A case_bit_test represents a set of case nodes that may be
504 selected from using a bit-wise comparison. HI and LO hold
505 the integer to be tested against, TARGET_EDGE contains the
506 edge to the basic block to jump to upon success and BITS
507 counts the number of case nodes handled by this test,
508 typically the number of bits set in HI:LO. The LABEL field
509 is used to quickly identify all cases in this set without
510 looking at label_to_block for every case label. */
512 struct case_bit_test
514 wide_int mask;
515 basic_block target_bb;
516 tree label;
517 int bits;
519 /* Comparison function for qsort to order bit tests by decreasing
520 probability of execution. */
521 static int cmp (const void *p1, const void *p2);
524 struct switch_decision_tree
526 /* Constructor. */
527 switch_decision_tree (gswitch *swtch): m_switch (swtch), m_phi_mapping (),
528 m_case_bbs (), m_case_node_pool ("struct case_node pool"),
529 m_case_list (NULL)
533 /* Analyze switch statement and return true when the statement is expanded
534 as decision tree. */
535 bool analyze_switch_statement ();
537 /* Attempt to expand CLUSTERS as a decision tree. Return true when
538 expanded. */
539 bool try_switch_expansion (vec<cluster *> &clusters);
540 /* Compute the number of case labels that correspond to each outgoing edge of
541 switch statement. Record this information in the aux field of the edge.
543 void compute_cases_per_edge ();
545 /* Before switch transformation, record all SSA_NAMEs defined in switch BB
546 and used in a label basic block. */
547 void record_phi_operand_mapping ();
549 /* Append new operands to PHI statements that were introduced due to
550 addition of new edges to case labels. */
551 void fix_phi_operands_for_edges ();
553 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
554 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
556 We generate a binary decision tree to select the appropriate target
557 code. */
558 void emit (basic_block bb, tree index_expr,
559 profile_probability default_prob, tree index_type);
561 /* Emit step-by-step code to select a case for the value of INDEX.
562 The thus generated decision tree follows the form of the
563 case-node binary tree NODE, whose nodes represent test conditions.
564 DEFAULT_PROB is probability of cases leading to default BB.
565 INDEX_TYPE is the type of the index of the switch. */
566 basic_block emit_case_nodes (basic_block bb, tree index,
567 case_tree_node *node,
568 profile_probability default_prob,
569 tree index_type);
571 /* Take an ordered list of case nodes
572 and transform them into a near optimal binary tree,
573 on the assumption that any target code selection value is as
574 likely as any other.
576 The transformation is performed by splitting the ordered
577 list into two equal sections plus a pivot. The parts are
578 then attached to the pivot as left and right branches. Each
579 branch is then transformed recursively. */
580 static void balance_case_nodes (case_tree_node **head,
581 case_tree_node *parent);
583 /* Dump ROOT, a list or tree of case nodes, to file F. */
584 static void dump_case_nodes (FILE *f, case_tree_node *root, int indent_step,
585 int indent_level);
587 /* Add an unconditional jump to CASE_BB that happens in basic block BB. */
588 static void emit_jump (basic_block bb, basic_block case_bb);
590 /* Generate code to compare OP0 with OP1 so that the condition codes are
591 set and to jump to LABEL_BB if the condition is true.
592 COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
593 PROB is the probability of jumping to LABEL_BB. */
594 static basic_block emit_cmp_and_jump_insns (basic_block bb, tree op0,
595 tree op1, tree_code comparison,
596 basic_block label_bb,
597 profile_probability prob);
599 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
600 PROB is the probability of jumping to LABEL_BB. */
601 static basic_block do_jump_if_equal (basic_block bb, tree op0, tree op1,
602 basic_block label_bb,
603 profile_probability prob);
605 /* Reset the aux field of all outgoing edges of switch basic block. */
606 static inline void reset_out_edges_aux (gswitch *swtch);
608 /* Switch statement. */
609 gswitch *m_switch;
611 /* Map of PHI nodes that have to be fixed after expansion. */
612 hash_map<tree, tree> m_phi_mapping;
614 /* List of basic blocks that belong to labels of the switch. */
615 auto_vec<basic_block> m_case_bbs;
617 /* Basic block with default label. */
618 basic_block m_default_bb;
620 /* A pool for case nodes. */
621 object_allocator<case_tree_node> m_case_node_pool;
623 /* Balanced tree of case nodes. */
624 case_tree_node *m_case_list;
628 Switch initialization conversion
630 The following pass changes simple initializations of scalars in a switch
631 statement into initializations from a static array. Obviously, the values
632 must be constant and known at compile time and a default branch must be
633 provided. For example, the following code:
635 int a,b;
637 switch (argc)
639 case 1:
640 case 2:
641 a_1 = 8;
642 b_1 = 6;
643 break;
644 case 3:
645 a_2 = 9;
646 b_2 = 5;
647 break;
648 case 12:
649 a_3 = 10;
650 b_3 = 4;
651 break;
652 default:
653 a_4 = 16;
654 b_4 = 1;
655 break;
657 a_5 = PHI <a_1, a_2, a_3, a_4>
658 b_5 = PHI <b_1, b_2, b_3, b_4>
661 is changed into:
663 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
664 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
665 16, 16, 10};
667 if (((unsigned) argc) - 1 < 11)
669 a_6 = CSWTCH02[argc - 1];
670 b_6 = CSWTCH01[argc - 1];
672 else
674 a_7 = 16;
675 b_7 = 1;
677 a_5 = PHI <a_6, a_7>
678 b_b = PHI <b_6, b_7>
680 There are further constraints. Specifically, the range of values across all
681 case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
682 eight) times the number of the actual switch branches.
684 This transformation was contributed by Martin Jambor, see this e-mail:
685 http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
687 /* The main structure of the pass. */
688 struct switch_conversion
690 /* Constructor. */
691 switch_conversion ();
693 /* Destructor. */
694 ~switch_conversion ();
696 /* The following function is invoked on every switch statement (the current
697 one is given in SWTCH) and runs the individual phases of switch
698 conversion on it one after another until one fails or the conversion
699 is completed. On success, NULL is in m_reason, otherwise points
700 to a string with the reason why the conversion failed. */
701 void expand (gswitch *swtch);
703 /* Collection information about SWTCH statement. */
704 void collect (gswitch *swtch);
706 /* Checks whether the range given by individual case statements of the switch
707 switch statement isn't too big and whether the number of branches actually
708 satisfies the size of the new array. */
709 bool check_range ();
711 /* Checks whether all but the final BB basic blocks are empty. */
712 bool check_all_empty_except_final ();
714 /* This function checks whether all required values in phi nodes in final_bb
715 are constants. Required values are those that correspond to a basic block
716 which is a part of the examined switch statement. It returns true if the
717 phi nodes are OK, otherwise false. */
718 bool check_final_bb ();
720 /* The following function allocates default_values, target_{in,out}_names and
721 constructors arrays. The last one is also populated with pointers to
722 vectors that will become constructors of new arrays. */
723 void create_temp_arrays ();
725 /* Populate the array of default values in the order of phi nodes.
726 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
727 if the range is non-contiguous or the default case has standard
728 structure, otherwise it is the first non-default case instead. */
729 void gather_default_values (tree default_case);
731 /* The following function populates the vectors in the constructors array with
732 future contents of the static arrays. The vectors are populated in the
733 order of phi nodes. */
734 void build_constructors ();
736 /* If all values in the constructor vector are the same, return the value.
737 Otherwise return NULL_TREE. Not supposed to be called for empty
738 vectors. */
739 tree contains_same_values_p (vec<constructor_elt, va_gc> *vec);
741 /* Return type which should be used for array elements, either TYPE's
742 main variant or, for integral types, some smaller integral type
743 that can still hold all the constants. */
744 tree array_value_type (tree type, int num);
746 /* Create an appropriate array type and declaration and assemble a static
747 array variable. Also create a load statement that initializes
748 the variable in question with a value from the static array. SWTCH is
749 the switch statement being converted, NUM is the index to
750 arrays of constructors, default values and target SSA names
751 for this particular array. ARR_INDEX_TYPE is the type of the index
752 of the new array, PHI is the phi node of the final BB that corresponds
753 to the value that will be loaded from the created array. TIDX
754 is an ssa name of a temporary variable holding the index for loads from the
755 new array. */
756 void build_one_array (int num, tree arr_index_type,
757 gphi *phi, tree tidx);
759 /* Builds and initializes static arrays initialized with values gathered from
760 the switch statement. Also creates statements that load values from
761 them. */
762 void build_arrays ();
764 /* Generates and appropriately inserts loads of default values at the position
765 given by GSI. Returns the last inserted statement. */
766 gassign *gen_def_assigns (gimple_stmt_iterator *gsi);
768 /* Deletes the unused bbs and edges that now contain the switch statement and
769 its empty branch bbs. BBD is the now dead BB containing
770 the original switch statement, FINAL is the last BB of the converted
771 switch statement (in terms of succession). */
772 void prune_bbs (basic_block bbd, basic_block final, basic_block default_bb);
774 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
775 from the basic block loading values from an array and E2F from the basic
776 block loading default values. BBF is the last switch basic block (see the
777 bbf description in the comment below). */
778 void fix_phi_nodes (edge e1f, edge e2f, basic_block bbf);
780 /* Creates a check whether the switch expression value actually falls into the
781 range given by all the cases. If it does not, the temporaries are loaded
782 with default values instead. */
783 void gen_inbound_check ();
785 /* Switch statement for which switch conversion takes place. */
786 gswitch *m_switch;
788 /* The expression used to decide the switch branch. */
789 tree m_index_expr;
791 /* The following integer constants store the minimum and maximum value
792 covered by the case labels. */
793 tree m_range_min;
794 tree m_range_max;
796 /* The difference between the above two numbers. Stored here because it
797 is used in all the conversion heuristics, as well as for some of the
798 transformation, and it is expensive to re-compute it all the time. */
799 tree m_range_size;
801 /* Basic block that contains the actual GIMPLE_SWITCH. */
802 basic_block m_switch_bb;
804 /* Basic block that is the target of the default case. */
805 basic_block m_default_bb;
807 /* The single successor block of all branches out of the GIMPLE_SWITCH,
808 if such a block exists. Otherwise NULL. */
809 basic_block m_final_bb;
811 /* The probability of the default edge in the replaced switch. */
812 profile_probability m_default_prob;
814 /* The count of the default edge in the replaced switch. */
815 profile_count m_default_count;
817 /* Combined count of all other (non-default) edges in the replaced switch. */
818 profile_count m_other_count;
820 /* Number of phi nodes in the final bb (that we'll be replacing). */
821 int m_phi_count;
823 /* Constructors of new static arrays. */
824 vec<constructor_elt, va_gc> **m_constructors;
826 /* Array of default values, in the same order as phi nodes. */
827 tree *m_default_values;
829 /* Array of ssa names that are initialized with a value from a new static
830 array. */
831 tree *m_target_inbound_names;
833 /* Array of ssa names that are initialized with the default value if the
834 switch expression is out of range. */
835 tree *m_target_outbound_names;
837 /* VOP SSA_NAME. */
838 tree m_target_vop;
840 /* The first load statement that loads a temporary from a new static array.
842 gimple *m_arr_ref_first;
844 /* The last load statement that loads a temporary from a new static array. */
845 gimple *m_arr_ref_last;
847 /* String reason why the case wasn't a good candidate that is written to the
848 dump file, if there is one. */
849 const char *m_reason;
851 /* True if default case is not used for any value between range_min and
852 range_max inclusive. */
853 bool m_contiguous_range;
855 /* True if default case does not have the required shape for other case
856 labels. */
857 bool m_default_case_nonstandard;
859 /* Number of uniq labels for non-default edges. */
860 unsigned int m_uniq;
862 /* Count is number of non-default edges. */
863 unsigned int m_count;
865 /* True if CFG has been changed. */
866 bool m_cfg_altered;
869 void
870 switch_decision_tree::reset_out_edges_aux (gswitch *swtch)
872 basic_block bb = gimple_bb (swtch);
873 edge e;
874 edge_iterator ei;
875 FOR_EACH_EDGE (e, ei, bb->succs)
876 e->aux = (void *) 0;
879 } // tree_switch_conversion namespace
881 #endif // TREE_SWITCH_CONVERSION_H