1 /* Expands front end tree to back end RTL for GCC
2 Copyright (C) 1987-2014 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
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
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 /* This file handles the generation of rtl code from tree structure
21 above the level of expressions, using subroutines in exp*.c and emit-rtl.c.
22 The functions whose names start with `expand_' are called by the
23 expander to generate RTL instructions for various kinds of constructs. */
27 #include "coretypes.h"
31 #include "hard-reg-set.h"
34 #include "stor-layout.h"
39 #include "insn-config.h"
44 #include "diagnostic-core.h"
46 #include "langhooks.h"
50 #include "pointer-set.h"
51 #include "basic-block.h"
52 #include "tree-ssa-alias.h"
53 #include "internal-fn.h"
54 #include "gimple-expr.h"
58 #include "alloc-pool.h"
59 #include "pretty-print.h"
64 /* Functions and data structures for expanding case statements. */
66 /* Case label structure, used to hold info on labels within case
67 statements. We handle "range" labels; for a single-value label
68 as in C, the high and low limits are the same.
70 We start with a vector of case nodes sorted in ascending order, and
71 the default label as the last element in the vector. Before expanding
72 to RTL, we transform this vector into a list linked via the RIGHT
73 fields in the case_node struct. Nodes with higher case values are
76 Switch statements can be output in three forms. A branch table is
77 used if there are more than a few labels and the labels are dense
78 within the range between the smallest and largest case value. If a
79 branch table is used, no further manipulations are done with the case
82 The alternative to the use of a branch table is to generate a series
83 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
84 and PARENT fields to hold a binary tree. Initially the tree is
85 totally unbalanced, with everything on the right. We balance the tree
86 with nodes on the left having lower case values than the parent
87 and nodes on the right having higher values. We then output the tree
90 For very small, suitable switch statements, we can generate a series
91 of simple bit test and branches instead. */
95 struct case_node
*left
; /* Left son in binary tree */
96 struct case_node
*right
; /* Right son in binary tree; also node chain */
97 struct case_node
*parent
; /* Parent of node in binary tree */
98 tree low
; /* Lowest index value for this label */
99 tree high
; /* Highest index value for this label */
100 tree code_label
; /* Label to jump to when node matches */
101 int prob
; /* Probability of taking this case. */
102 /* Probability of reaching subtree rooted at this node */
106 typedef struct case_node case_node
;
107 typedef struct case_node
*case_node_ptr
;
109 extern basic_block
label_to_block_fn (struct function
*, tree
);
111 static bool check_unique_operand_names (tree
, tree
, tree
);
112 static char *resolve_operand_name_1 (char *, tree
, tree
, tree
);
113 static void balance_case_nodes (case_node_ptr
*, case_node_ptr
);
114 static int node_has_low_bound (case_node_ptr
, tree
);
115 static int node_has_high_bound (case_node_ptr
, tree
);
116 static int node_is_bounded (case_node_ptr
, tree
);
117 static void emit_case_nodes (rtx
, case_node_ptr
, rtx
, int, tree
);
119 /* Return the rtx-label that corresponds to a LABEL_DECL,
120 creating it if necessary. */
123 label_rtx (tree label
)
125 gcc_assert (TREE_CODE (label
) == LABEL_DECL
);
127 if (!DECL_RTL_SET_P (label
))
129 rtx r
= gen_label_rtx ();
130 SET_DECL_RTL (label
, r
);
131 if (FORCED_LABEL (label
) || DECL_NONLOCAL (label
))
132 LABEL_PRESERVE_P (r
) = 1;
135 return DECL_RTL (label
);
138 /* As above, but also put it on the forced-reference list of the
139 function that contains it. */
141 force_label_rtx (tree label
)
143 rtx ref
= label_rtx (label
);
144 tree function
= decl_function_context (label
);
146 gcc_assert (function
);
148 forced_labels
= gen_rtx_EXPR_LIST (VOIDmode
, ref
, forced_labels
);
152 /* Add an unconditional jump to LABEL as the next sequential instruction. */
155 emit_jump (rtx label
)
157 do_pending_stack_adjust ();
158 emit_jump_insn (gen_jump (label
));
162 /* Handle goto statements and the labels that they can go to. */
164 /* Specify the location in the RTL code of a label LABEL,
165 which is a LABEL_DECL tree node.
167 This is used for the kind of label that the user can jump to with a
168 goto statement, and for alternatives of a switch or case statement.
169 RTL labels generated for loops and conditionals don't go through here;
170 they are generated directly at the RTL level, by other functions below.
172 Note that this has nothing to do with defining label *names*.
173 Languages vary in how they do that and what that even means. */
176 expand_label (tree label
)
178 rtx label_r
= label_rtx (label
);
180 do_pending_stack_adjust ();
181 emit_label (label_r
);
182 if (DECL_NAME (label
))
183 LABEL_NAME (DECL_RTL (label
)) = IDENTIFIER_POINTER (DECL_NAME (label
));
185 if (DECL_NONLOCAL (label
))
187 expand_builtin_setjmp_receiver (NULL
);
188 nonlocal_goto_handler_labels
189 = gen_rtx_EXPR_LIST (VOIDmode
, label_r
,
190 nonlocal_goto_handler_labels
);
193 if (FORCED_LABEL (label
))
194 forced_labels
= gen_rtx_EXPR_LIST (VOIDmode
, label_r
, forced_labels
);
196 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
197 maybe_set_first_label_num (label_r
);
200 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
201 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
202 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
203 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
204 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
205 constraint allows the use of a register operand. And, *IS_INOUT
206 will be true if the operand is read-write, i.e., if it is used as
207 an input as well as an output. If *CONSTRAINT_P is not in
208 canonical form, it will be made canonical. (Note that `+' will be
209 replaced with `=' as part of this process.)
211 Returns TRUE if all went well; FALSE if an error occurred. */
214 parse_output_constraint (const char **constraint_p
, int operand_num
,
215 int ninputs
, int noutputs
, bool *allows_mem
,
216 bool *allows_reg
, bool *is_inout
)
218 const char *constraint
= *constraint_p
;
221 /* Assume the constraint doesn't allow the use of either a register
226 /* Allow the `=' or `+' to not be at the beginning of the string,
227 since it wasn't explicitly documented that way, and there is a
228 large body of code that puts it last. Swap the character to
229 the front, so as not to uglify any place else. */
230 p
= strchr (constraint
, '=');
232 p
= strchr (constraint
, '+');
234 /* If the string doesn't contain an `=', issue an error
238 error ("output operand constraint lacks %<=%>");
242 /* If the constraint begins with `+', then the operand is both read
243 from and written to. */
244 *is_inout
= (*p
== '+');
246 /* Canonicalize the output constraint so that it begins with `='. */
247 if (p
!= constraint
|| *is_inout
)
250 size_t c_len
= strlen (constraint
);
253 warning (0, "output constraint %qc for operand %d "
254 "is not at the beginning",
257 /* Make a copy of the constraint. */
258 buf
= XALLOCAVEC (char, c_len
+ 1);
259 strcpy (buf
, constraint
);
260 /* Swap the first character and the `=' or `+'. */
261 buf
[p
- constraint
] = buf
[0];
262 /* Make sure the first character is an `='. (Until we do this,
263 it might be a `+'.) */
265 /* Replace the constraint with the canonicalized string. */
266 *constraint_p
= ggc_alloc_string (buf
, c_len
);
267 constraint
= *constraint_p
;
270 /* Loop through the constraint string. */
271 for (p
= constraint
+ 1; *p
; p
+= CONSTRAINT_LEN (*p
, p
))
276 error ("operand constraint contains incorrectly positioned "
281 if (operand_num
+ 1 == ninputs
+ noutputs
)
283 error ("%<%%%> constraint used with last operand");
288 case 'V': case TARGET_MEM_CONSTRAINT
: case 'o':
292 case '?': case '!': case '*': case '&': case '#':
293 case 'E': case 'F': case 'G': case 'H':
294 case 's': case 'i': case 'n':
295 case 'I': case 'J': case 'K': case 'L': case 'M':
296 case 'N': case 'O': case 'P': case ',':
299 case '0': case '1': case '2': case '3': case '4':
300 case '5': case '6': case '7': case '8': case '9':
302 error ("matching constraint not valid in output operand");
306 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
307 excepting those that expand_call created. So match memory
324 if (REG_CLASS_FROM_CONSTRAINT (*p
, p
) != NO_REGS
)
326 #ifdef EXTRA_CONSTRAINT_STR
327 else if (EXTRA_ADDRESS_CONSTRAINT (*p
, p
))
329 else if (EXTRA_MEMORY_CONSTRAINT (*p
, p
))
333 /* Otherwise we can't assume anything about the nature of
334 the constraint except that it isn't purely registers.
335 Treat it like "g" and hope for the best. */
346 /* Similar, but for input constraints. */
349 parse_input_constraint (const char **constraint_p
, int input_num
,
350 int ninputs
, int noutputs
, int ninout
,
351 const char * const * constraints
,
352 bool *allows_mem
, bool *allows_reg
)
354 const char *constraint
= *constraint_p
;
355 const char *orig_constraint
= constraint
;
356 size_t c_len
= strlen (constraint
);
358 bool saw_match
= false;
360 /* Assume the constraint doesn't allow the use of either
361 a register or memory. */
365 /* Make sure constraint has neither `=', `+', nor '&'. */
367 for (j
= 0; j
< c_len
; j
+= CONSTRAINT_LEN (constraint
[j
], constraint
+j
))
368 switch (constraint
[j
])
370 case '+': case '=': case '&':
371 if (constraint
== orig_constraint
)
373 error ("input operand constraint contains %qc", constraint
[j
]);
379 if (constraint
== orig_constraint
380 && input_num
+ 1 == ninputs
- ninout
)
382 error ("%<%%%> constraint used with last operand");
387 case 'V': case TARGET_MEM_CONSTRAINT
: case 'o':
392 case '?': case '!': case '*': case '#':
393 case 'E': case 'F': case 'G': case 'H':
394 case 's': case 'i': case 'n':
395 case 'I': case 'J': case 'K': case 'L': case 'M':
396 case 'N': case 'O': case 'P': case ',':
399 /* Whether or not a numeric constraint allows a register is
400 decided by the matching constraint, and so there is no need
401 to do anything special with them. We must handle them in
402 the default case, so that we don't unnecessarily force
403 operands to memory. */
404 case '0': case '1': case '2': case '3': case '4':
405 case '5': case '6': case '7': case '8': case '9':
412 match
= strtoul (constraint
+ j
, &end
, 10);
413 if (match
>= (unsigned long) noutputs
)
415 error ("matching constraint references invalid operand number");
419 /* Try and find the real constraint for this dup. Only do this
420 if the matching constraint is the only alternative. */
422 && (j
== 0 || (j
== 1 && constraint
[0] == '%')))
424 constraint
= constraints
[match
];
425 *constraint_p
= constraint
;
426 c_len
= strlen (constraint
);
428 /* ??? At the end of the loop, we will skip the first part of
429 the matched constraint. This assumes not only that the
430 other constraint is an output constraint, but also that
431 the '=' or '+' come first. */
435 j
= end
- constraint
;
436 /* Anticipate increment at end of loop. */
451 if (! ISALPHA (constraint
[j
]))
453 error ("invalid punctuation %qc in constraint", constraint
[j
]);
456 if (REG_CLASS_FROM_CONSTRAINT (constraint
[j
], constraint
+ j
)
459 #ifdef EXTRA_CONSTRAINT_STR
460 else if (EXTRA_ADDRESS_CONSTRAINT (constraint
[j
], constraint
+ j
))
462 else if (EXTRA_MEMORY_CONSTRAINT (constraint
[j
], constraint
+ j
))
466 /* Otherwise we can't assume anything about the nature of
467 the constraint except that it isn't purely registers.
468 Treat it like "g" and hope for the best. */
476 if (saw_match
&& !*allows_reg
)
477 warning (0, "matching constraint does not allow a register");
482 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
483 can be an asm-declared register. Called via walk_tree. */
486 decl_overlaps_hard_reg_set_p (tree
*declp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
490 const HARD_REG_SET
*const regs
= (const HARD_REG_SET
*) data
;
492 if (TREE_CODE (decl
) == VAR_DECL
)
494 if (DECL_HARD_REGISTER (decl
)
495 && REG_P (DECL_RTL (decl
))
496 && REGNO (DECL_RTL (decl
)) < FIRST_PSEUDO_REGISTER
)
498 rtx reg
= DECL_RTL (decl
);
500 if (overlaps_hard_reg_set_p (*regs
, GET_MODE (reg
), REGNO (reg
)))
505 else if (TYPE_P (decl
) || TREE_CODE (decl
) == PARM_DECL
)
510 /* If there is an overlap between *REGS and DECL, return the first overlap
513 tree_overlaps_hard_reg_set (tree decl
, HARD_REG_SET
*regs
)
515 return walk_tree (&decl
, decl_overlaps_hard_reg_set_p
, regs
, NULL
);
519 /* A subroutine of expand_asm_operands. Check that all operand names
520 are unique. Return true if so. We rely on the fact that these names
521 are identifiers, and so have been canonicalized by get_identifier,
522 so all we need are pointer comparisons. */
525 check_unique_operand_names (tree outputs
, tree inputs
, tree labels
)
527 tree i
, j
, i_name
= NULL_TREE
;
529 for (i
= outputs
; i
; i
= TREE_CHAIN (i
))
531 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
535 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
536 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
540 for (i
= inputs
; i
; i
= TREE_CHAIN (i
))
542 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
546 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
547 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
549 for (j
= outputs
; j
; j
= TREE_CHAIN (j
))
550 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
554 for (i
= labels
; i
; i
= TREE_CHAIN (i
))
556 i_name
= TREE_PURPOSE (i
);
560 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
561 if (simple_cst_equal (i_name
, TREE_PURPOSE (j
)))
563 for (j
= inputs
; j
; j
= TREE_CHAIN (j
))
564 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
571 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name
));
575 /* A subroutine of expand_asm_operands. Resolve the names of the operands
576 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
577 STRING and in the constraints to those numbers. */
580 resolve_asm_operand_names (tree string
, tree outputs
, tree inputs
, tree labels
)
587 check_unique_operand_names (outputs
, inputs
, labels
);
589 /* Substitute [<name>] in input constraint strings. There should be no
590 named operands in output constraints. */
591 for (t
= inputs
; t
; t
= TREE_CHAIN (t
))
593 c
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
594 if (strchr (c
, '[') != NULL
)
596 p
= buffer
= xstrdup (c
);
597 while ((p
= strchr (p
, '[')) != NULL
)
598 p
= resolve_operand_name_1 (p
, outputs
, inputs
, NULL
);
599 TREE_VALUE (TREE_PURPOSE (t
))
600 = build_string (strlen (buffer
), buffer
);
605 /* Now check for any needed substitutions in the template. */
606 c
= TREE_STRING_POINTER (string
);
607 while ((c
= strchr (c
, '%')) != NULL
)
611 else if (ISALPHA (c
[1]) && c
[2] == '[')
615 c
+= 1 + (c
[1] == '%');
622 /* OK, we need to make a copy so we can perform the substitutions.
623 Assume that we will not need extra space--we get to remove '['
624 and ']', which means we cannot have a problem until we have more
625 than 999 operands. */
626 buffer
= xstrdup (TREE_STRING_POINTER (string
));
627 p
= buffer
+ (c
- TREE_STRING_POINTER (string
));
629 while ((p
= strchr (p
, '%')) != NULL
)
633 else if (ISALPHA (p
[1]) && p
[2] == '[')
637 p
+= 1 + (p
[1] == '%');
641 p
= resolve_operand_name_1 (p
, outputs
, inputs
, labels
);
644 string
= build_string (strlen (buffer
), buffer
);
651 /* A subroutine of resolve_operand_names. P points to the '[' for a
652 potential named operand of the form [<name>]. In place, replace
653 the name and brackets with a number. Return a pointer to the
654 balance of the string after substitution. */
657 resolve_operand_name_1 (char *p
, tree outputs
, tree inputs
, tree labels
)
663 /* Collect the operand name. */
664 q
= strchr (++p
, ']');
667 error ("missing close brace for named operand");
668 return strchr (p
, '\0');
672 /* Resolve the name to a number. */
673 for (op
= 0, t
= outputs
; t
; t
= TREE_CHAIN (t
), op
++)
675 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
676 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
679 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), op
++)
681 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
682 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
685 for (t
= labels
; t
; t
= TREE_CHAIN (t
), op
++)
687 tree name
= TREE_PURPOSE (t
);
688 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
692 error ("undefined named operand %qs", identifier_to_locale (p
));
696 /* Replace the name with the number. Unfortunately, not all libraries
697 get the return value of sprintf correct, so search for the end of the
698 generated string by hand. */
699 sprintf (--p
, "%d", op
);
700 p
= strchr (p
, '\0');
702 /* Verify the no extra buffer space assumption. */
705 /* Shift the rest of the buffer down to fill the gap. */
706 memmove (p
, q
+ 1, strlen (q
+ 1) + 1);
712 /* Generate RTL to return directly from the current function.
713 (That is, we bypass any return value.) */
716 expand_naked_return (void)
720 clear_pending_stack_adjust ();
721 do_pending_stack_adjust ();
723 end_label
= naked_return_label
;
725 end_label
= naked_return_label
= gen_label_rtx ();
727 emit_jump (end_label
);
730 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
731 is the probability of jumping to LABEL. */
733 do_jump_if_equal (enum machine_mode mode
, rtx op0
, rtx op1
, rtx label
,
734 int unsignedp
, int prob
)
736 gcc_assert (prob
<= REG_BR_PROB_BASE
);
737 do_compare_rtx_and_jump (op0
, op1
, EQ
, unsignedp
, mode
,
738 NULL_RTX
, NULL_RTX
, label
, prob
);
741 /* Do the insertion of a case label into case_list. The labels are
742 fed to us in descending order from the sorted vector of case labels used
743 in the tree part of the middle end. So the list we construct is
744 sorted in ascending order.
746 LABEL is the case label to be inserted. LOW and HIGH are the bounds
747 against which the index is compared to jump to LABEL and PROB is the
748 estimated probability LABEL is reached from the switch statement. */
750 static struct case_node
*
751 add_case_node (struct case_node
*head
, tree low
, tree high
,
752 tree label
, int prob
, alloc_pool case_node_pool
)
756 gcc_checking_assert (low
);
757 gcc_checking_assert (high
&& (TREE_TYPE (low
) == TREE_TYPE (high
)));
759 /* Add this label to the chain. */
760 r
= (struct case_node
*) pool_alloc (case_node_pool
);
763 r
->code_label
= label
;
764 r
->parent
= r
->left
= NULL
;
766 r
->subtree_prob
= prob
;
771 /* Dump ROOT, a list or tree of case nodes, to file. */
774 dump_case_nodes (FILE *f
, struct case_node
*root
,
775 int indent_step
, int indent_level
)
781 dump_case_nodes (f
, root
->left
, indent_step
, indent_level
);
784 fprintf (f
, "%*s", indent_step
* indent_level
, "");
785 print_dec (root
->low
, f
, TYPE_SIGN (TREE_TYPE (root
->low
)));
786 if (!tree_int_cst_equal (root
->low
, root
->high
))
788 fprintf (f
, " ... ");
789 print_dec (root
->high
, f
, TYPE_SIGN (TREE_TYPE (root
->high
)));
793 dump_case_nodes (f
, root
->right
, indent_step
, indent_level
);
797 #define HAVE_casesi 0
800 #ifndef HAVE_tablejump
801 #define HAVE_tablejump 0
804 /* Return the smallest number of different values for which it is best to use a
805 jump-table instead of a tree of conditional branches. */
808 case_values_threshold (void)
810 unsigned int threshold
= PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD
);
813 threshold
= targetm
.case_values_threshold ();
818 /* Return true if a switch should be expanded as a decision tree.
819 RANGE is the difference between highest and lowest case.
820 UNIQ is number of unique case node targets, not counting the default case.
821 COUNT is the number of comparisons needed, not counting the default case. */
824 expand_switch_as_decision_tree_p (tree range
,
825 unsigned int uniq ATTRIBUTE_UNUSED
,
830 /* If neither casesi or tablejump is available, or flag_jump_tables
831 over-ruled us, we really have no choice. */
832 if (!HAVE_casesi
&& !HAVE_tablejump
)
834 if (!flag_jump_tables
)
836 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
841 /* If the switch is relatively small such that the cost of one
842 indirect jump on the target are higher than the cost of a
843 decision tree, go with the decision tree.
845 If range of values is much bigger than number of values,
846 or if it is too large to represent in a HOST_WIDE_INT,
847 make a sequence of conditional branches instead of a dispatch.
849 The definition of "much bigger" depends on whether we are
850 optimizing for size or for speed. If the former, the maximum
851 ratio range/count = 3, because this was found to be the optimal
852 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
853 10 is much older, and was probably selected after an extensive
854 benchmarking investigation on numerous platforms. Or maybe it
855 just made sense to someone at some point in the history of GCC,
857 max_ratio
= optimize_insn_for_size_p () ? 3 : 10;
858 if (count
< case_values_threshold ()
859 || ! tree_fits_uhwi_p (range
)
860 || compare_tree_int (range
, max_ratio
* count
) > 0)
866 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
867 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
868 DEFAULT_PROB is the estimated probability that it jumps to
871 We generate a binary decision tree to select the appropriate target
872 code. This is done as follows:
874 If the index is a short or char that we do not have
875 an insn to handle comparisons directly, convert it to
876 a full integer now, rather than letting each comparison
877 generate the conversion.
879 Load the index into a register.
881 The list of cases is rearranged into a binary tree,
882 nearly optimal assuming equal probability for each case.
884 The tree is transformed into RTL, eliminating redundant
885 test conditions at the same time.
887 If program flow could reach the end of the decision tree
888 an unconditional jump to the default code is emitted.
890 The above process is unaware of the CFG. The caller has to fix up
891 the CFG itself. This is done in cfgexpand.c. */
894 emit_case_decision_tree (tree index_expr
, tree index_type
,
895 struct case_node
*case_list
, rtx default_label
,
898 rtx index
= expand_normal (index_expr
);
900 if (GET_MODE_CLASS (GET_MODE (index
)) == MODE_INT
901 && ! have_insn_for (COMPARE
, GET_MODE (index
)))
903 int unsignedp
= TYPE_UNSIGNED (index_type
);
904 enum machine_mode wider_mode
;
905 for (wider_mode
= GET_MODE (index
); wider_mode
!= VOIDmode
;
906 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
907 if (have_insn_for (COMPARE
, wider_mode
))
909 index
= convert_to_mode (wider_mode
, index
, unsignedp
);
914 do_pending_stack_adjust ();
918 index
= copy_to_reg (index
);
919 if (TREE_CODE (index_expr
) == SSA_NAME
)
920 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr
), index
);
923 balance_case_nodes (&case_list
, NULL
);
925 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
927 int indent_step
= ceil_log2 (TYPE_PRECISION (index_type
)) + 2;
928 fprintf (dump_file
, ";; Expanding GIMPLE switch as decision tree:\n");
929 dump_case_nodes (dump_file
, case_list
, indent_step
, 0);
932 emit_case_nodes (index
, case_list
, default_label
, default_prob
, index_type
);
934 emit_jump (default_label
);
937 /* Return the sum of probabilities of outgoing edges of basic block BB. */
940 get_outgoing_edge_probs (basic_block bb
)
947 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
948 prob_sum
+= e
->probability
;
952 /* Computes the conditional probability of jumping to a target if the branch
953 instruction is executed.
954 TARGET_PROB is the estimated probability of jumping to a target relative
955 to some basic block BB.
956 BASE_PROB is the probability of reaching the branch instruction relative
957 to the same basic block BB. */
960 conditional_probability (int target_prob
, int base_prob
)
964 gcc_assert (target_prob
>= 0);
965 gcc_assert (target_prob
<= base_prob
);
966 return GCOV_COMPUTE_SCALE (target_prob
, base_prob
);
971 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
972 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
973 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
974 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
976 First, a jump insn is emitted. First we try "casesi". If that
977 fails, try "tablejump". A target *must* have one of them (or both).
979 Then, a table with the target labels is emitted.
981 The process is unaware of the CFG. The caller has to fix up
982 the CFG itself. This is done in cfgexpand.c. */
985 emit_case_dispatch_table (tree index_expr
, tree index_type
,
986 struct case_node
*case_list
, rtx default_label
,
987 tree minval
, tree maxval
, tree range
,
993 rtx fallback_label
= label_rtx (case_list
->code_label
);
994 rtx table_label
= gen_label_rtx ();
995 bool has_gaps
= false;
996 edge default_edge
= stmt_bb
? EDGE_SUCC (stmt_bb
, 0) : NULL
;
997 int default_prob
= default_edge
? default_edge
->probability
: 0;
998 int base
= get_outgoing_edge_probs (stmt_bb
);
999 bool try_with_tablejump
= false;
1001 int new_default_prob
= conditional_probability (default_prob
,
1004 if (! try_casesi (index_type
, index_expr
, minval
, range
,
1005 table_label
, default_label
, fallback_label
,
1008 /* Index jumptables from zero for suitable values of minval to avoid
1009 a subtraction. For the rationale see:
1010 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
1011 if (optimize_insn_for_speed_p ()
1012 && compare_tree_int (minval
, 0) > 0
1013 && compare_tree_int (minval
, 3) < 0)
1015 minval
= build_int_cst (index_type
, 0);
1019 try_with_tablejump
= true;
1022 /* Get table of labels to jump to, in order of case index. */
1024 ncases
= tree_to_shwi (range
) + 1;
1025 labelvec
= XALLOCAVEC (rtx
, ncases
);
1026 memset (labelvec
, 0, ncases
* sizeof (rtx
));
1028 for (n
= case_list
; n
; n
= n
->right
)
1030 /* Compute the low and high bounds relative to the minimum
1031 value since that should fit in a HOST_WIDE_INT while the
1032 actual values may not. */
1034 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1036 HOST_WIDE_INT i_high
1037 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1041 for (i
= i_low
; i
<= i_high
; i
++)
1043 = gen_rtx_LABEL_REF (Pmode
, label_rtx (n
->code_label
));
1046 /* Fill in the gaps with the default. We may have gaps at
1047 the beginning if we tried to avoid the minval subtraction,
1048 so substitute some label even if the default label was
1049 deemed unreachable. */
1051 default_label
= fallback_label
;
1052 for (i
= 0; i
< ncases
; i
++)
1053 if (labelvec
[i
] == 0)
1056 labelvec
[i
] = gen_rtx_LABEL_REF (Pmode
, default_label
);
1061 /* There is at least one entry in the jump table that jumps
1062 to default label. The default label can either be reached
1063 through the indirect jump or the direct conditional jump
1064 before that. Split the probability of reaching the
1065 default label among these two jumps. */
1066 new_default_prob
= conditional_probability (default_prob
/2,
1069 base
-= default_prob
;
1073 base
-= default_prob
;
1078 default_edge
->probability
= default_prob
;
1080 /* We have altered the probability of the default edge. So the probabilities
1081 of all other edges need to be adjusted so that it sums up to
1082 REG_BR_PROB_BASE. */
1087 FOR_EACH_EDGE (e
, ei
, stmt_bb
->succs
)
1088 e
->probability
= GCOV_COMPUTE_SCALE (e
->probability
, base
);
1091 if (try_with_tablejump
)
1093 bool ok
= try_tablejump (index_type
, index_expr
, minval
, range
,
1094 table_label
, default_label
, new_default_prob
);
1097 /* Output the table. */
1098 emit_label (table_label
);
1100 if (CASE_VECTOR_PC_RELATIVE
|| flag_pic
)
1101 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE
,
1102 gen_rtx_LABEL_REF (Pmode
,
1104 gen_rtvec_v (ncases
, labelvec
),
1105 const0_rtx
, const0_rtx
));
1107 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE
,
1108 gen_rtvec_v (ncases
, labelvec
)));
1110 /* Record no drop-through after the table. */
1114 /* Reset the aux field of all outgoing edges of basic block BB. */
1117 reset_out_edges_aux (basic_block bb
)
1121 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1125 /* Compute the number of case labels that correspond to each outgoing edge of
1126 STMT. Record this information in the aux field of the edge. */
1129 compute_cases_per_edge (gimple stmt
)
1131 basic_block bb
= gimple_bb (stmt
);
1132 reset_out_edges_aux (bb
);
1133 int ncases
= gimple_switch_num_labels (stmt
);
1134 for (int i
= ncases
- 1; i
>= 1; --i
)
1136 tree elt
= gimple_switch_label (stmt
, i
);
1137 tree lab
= CASE_LABEL (elt
);
1138 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1139 edge case_edge
= find_edge (bb
, case_bb
);
1140 case_edge
->aux
= (void *)((intptr_t)(case_edge
->aux
) + 1);
1144 /* Terminate a case (Pascal/Ada) or switch (C) statement
1145 in which ORIG_INDEX is the expression to be tested.
1146 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
1147 type as given in the source before any compiler conversions.
1148 Generate the code to test it and jump to the right place. */
1151 expand_case (gimple stmt
)
1153 tree minval
= NULL_TREE
, maxval
= NULL_TREE
, range
= NULL_TREE
;
1154 rtx default_label
= NULL_RTX
;
1155 unsigned int count
, uniq
;
1157 int ncases
= gimple_switch_num_labels (stmt
);
1158 tree index_expr
= gimple_switch_index (stmt
);
1159 tree index_type
= TREE_TYPE (index_expr
);
1161 basic_block bb
= gimple_bb (stmt
);
1163 /* A list of case labels; it is first built as a list and it may then
1164 be rearranged into a nearly balanced binary tree. */
1165 struct case_node
*case_list
= 0;
1167 /* A pool for case nodes. */
1168 alloc_pool case_node_pool
;
1170 /* An ERROR_MARK occurs for various reasons including invalid data type.
1171 ??? Can this still happen, with GIMPLE and all? */
1172 if (index_type
== error_mark_node
)
1175 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
1176 expressions being INTEGER_CST. */
1177 gcc_assert (TREE_CODE (index_expr
) != INTEGER_CST
);
1179 case_node_pool
= create_alloc_pool ("struct case_node pool",
1180 sizeof (struct case_node
),
1183 do_pending_stack_adjust ();
1185 /* Find the default case target label. */
1186 default_label
= label_rtx (CASE_LABEL (gimple_switch_default_label (stmt
)));
1187 edge default_edge
= EDGE_SUCC (bb
, 0);
1188 int default_prob
= default_edge
->probability
;
1190 /* Get upper and lower bounds of case values. */
1191 elt
= gimple_switch_label (stmt
, 1);
1192 minval
= fold_convert (index_type
, CASE_LOW (elt
));
1193 elt
= gimple_switch_label (stmt
, ncases
- 1);
1194 if (CASE_HIGH (elt
))
1195 maxval
= fold_convert (index_type
, CASE_HIGH (elt
));
1197 maxval
= fold_convert (index_type
, CASE_LOW (elt
));
1199 /* Compute span of values. */
1200 range
= fold_build2 (MINUS_EXPR
, index_type
, maxval
, minval
);
1202 /* Listify the labels queue and gather some numbers to decide
1203 how to expand this switch(). */
1206 struct pointer_set_t
*seen_labels
= pointer_set_create ();
1207 compute_cases_per_edge (stmt
);
1209 for (i
= ncases
- 1; i
>= 1; --i
)
1211 elt
= gimple_switch_label (stmt
, i
);
1212 tree low
= CASE_LOW (elt
);
1214 tree high
= CASE_HIGH (elt
);
1215 gcc_assert (! high
|| tree_int_cst_lt (low
, high
));
1216 tree lab
= CASE_LABEL (elt
);
1218 /* Count the elements.
1219 A range counts double, since it requires two compares. */
1224 /* If we have not seen this label yet, then increase the
1225 number of unique case node targets seen. */
1226 if (!pointer_set_insert (seen_labels
, lab
))
1229 /* The bounds on the case range, LOW and HIGH, have to be converted
1230 to case's index type TYPE. Note that the original type of the
1231 case index in the source code is usually "lost" during
1232 gimplification due to type promotion, but the case labels retain the
1233 original type. Make sure to drop overflow flags. */
1234 low
= fold_convert (index_type
, low
);
1235 if (TREE_OVERFLOW (low
))
1236 low
= wide_int_to_tree (index_type
, low
);
1238 /* The canonical from of a case label in GIMPLE is that a simple case
1239 has an empty CASE_HIGH. For the casesi and tablejump expanders,
1240 the back ends want simple cases to have high == low. */
1243 high
= fold_convert (index_type
, high
);
1244 if (TREE_OVERFLOW (high
))
1245 high
= wide_int_to_tree (index_type
, high
);
1247 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1248 edge case_edge
= find_edge (bb
, case_bb
);
1249 case_list
= add_case_node (
1250 case_list
, low
, high
, lab
,
1251 case_edge
->probability
/ (intptr_t)(case_edge
->aux
),
1254 pointer_set_destroy (seen_labels
);
1255 reset_out_edges_aux (bb
);
1257 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
1258 destination, such as one with a default case only.
1259 It also removes cases that are out of range for the switch
1260 type, so we should never get a zero here. */
1261 gcc_assert (count
> 0);
1263 rtx before_case
= get_last_insn ();
1265 /* Decide how to expand this switch.
1266 The two options at this point are a dispatch table (casesi or
1267 tablejump) or a decision tree. */
1269 if (expand_switch_as_decision_tree_p (range
, uniq
, count
))
1270 emit_case_decision_tree (index_expr
, index_type
,
1271 case_list
, default_label
,
1274 emit_case_dispatch_table (index_expr
, index_type
,
1275 case_list
, default_label
,
1276 minval
, maxval
, range
, bb
);
1278 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1281 free_alloc_pool (case_node_pool
);
1284 /* Expand the dispatch to a short decrement chain if there are few cases
1285 to dispatch to. Likewise if neither casesi nor tablejump is available,
1286 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
1287 tablejump. The index mode is always the mode of integer_type_node.
1288 Trap if no case matches the index.
1290 DISPATCH_INDEX is the index expression to switch on. It should be a
1291 memory or register operand.
1293 DISPATCH_TABLE is a set of case labels. The set should be sorted in
1294 ascending order, be contiguous, starting with value 0, and contain only
1295 single-valued case labels. */
1298 expand_sjlj_dispatch_table (rtx dispatch_index
,
1299 vec
<tree
> dispatch_table
)
1301 tree index_type
= integer_type_node
;
1302 enum machine_mode index_mode
= TYPE_MODE (index_type
);
1304 int ncases
= dispatch_table
.length ();
1306 do_pending_stack_adjust ();
1307 rtx before_case
= get_last_insn ();
1309 /* Expand as a decrement-chain if there are 5 or fewer dispatch
1310 labels. This covers more than 98% of the cases in libjava,
1311 and seems to be a reasonable compromise between the "old way"
1312 of expanding as a decision tree or dispatch table vs. the "new
1313 way" with decrement chain or dispatch table. */
1314 if (dispatch_table
.length () <= 5
1315 || (!HAVE_casesi
&& !HAVE_tablejump
)
1316 || !flag_jump_tables
)
1318 /* Expand the dispatch as a decrement chain:
1320 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1324 if (index == 0) do_0; else index--;
1325 if (index == 0) do_1; else index--;
1327 if (index == 0) do_N; else index--;
1329 This is more efficient than a dispatch table on most machines.
1330 The last "index--" is redundant but the code is trivially dead
1331 and will be cleaned up by later passes. */
1332 rtx index
= copy_to_mode_reg (index_mode
, dispatch_index
);
1333 rtx zero
= CONST0_RTX (index_mode
);
1334 for (int i
= 0; i
< ncases
; i
++)
1336 tree elt
= dispatch_table
[i
];
1337 rtx lab
= label_rtx (CASE_LABEL (elt
));
1338 do_jump_if_equal (index_mode
, index
, zero
, lab
, 0, -1);
1339 force_expand_binop (index_mode
, sub_optab
,
1340 index
, CONST1_RTX (index_mode
),
1341 index
, 0, OPTAB_DIRECT
);
1346 /* Similar to expand_case, but much simpler. */
1347 struct case_node
*case_list
= 0;
1348 alloc_pool case_node_pool
= create_alloc_pool ("struct sjlj_case pool",
1349 sizeof (struct case_node
),
1351 tree index_expr
= make_tree (index_type
, dispatch_index
);
1352 tree minval
= build_int_cst (index_type
, 0);
1353 tree maxval
= CASE_LOW (dispatch_table
.last ());
1354 tree range
= maxval
;
1355 rtx default_label
= gen_label_rtx ();
1357 for (int i
= ncases
- 1; i
>= 0; --i
)
1359 tree elt
= dispatch_table
[i
];
1360 tree low
= CASE_LOW (elt
);
1361 tree lab
= CASE_LABEL (elt
);
1362 case_list
= add_case_node (case_list
, low
, low
, lab
, 0, case_node_pool
);
1365 emit_case_dispatch_table (index_expr
, index_type
,
1366 case_list
, default_label
,
1367 minval
, maxval
, range
,
1368 BLOCK_FOR_INSN (before_case
));
1369 emit_label (default_label
);
1370 free_alloc_pool (case_node_pool
);
1373 /* Dispatching something not handled? Trap! */
1374 expand_builtin_trap ();
1376 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1382 /* Take an ordered list of case nodes
1383 and transform them into a near optimal binary tree,
1384 on the assumption that any target code selection value is as
1385 likely as any other.
1387 The transformation is performed by splitting the ordered
1388 list into two equal sections plus a pivot. The parts are
1389 then attached to the pivot as left and right branches. Each
1390 branch is then transformed recursively. */
1393 balance_case_nodes (case_node_ptr
*head
, case_node_ptr parent
)
1405 /* Count the number of entries on branch. Also count the ranges. */
1409 if (!tree_int_cst_equal (np
->low
, np
->high
))
1418 /* Split this list if it is long enough for that to help. */
1422 /* If there are just three nodes, split at the middle one. */
1424 npp
= &(*npp
)->right
;
1427 /* Find the place in the list that bisects the list's total cost,
1428 where ranges count as 2.
1429 Here I gets half the total cost. */
1430 i
= (i
+ ranges
+ 1) / 2;
1433 /* Skip nodes while their cost does not reach that amount. */
1434 if (!tree_int_cst_equal ((*npp
)->low
, (*npp
)->high
))
1439 npp
= &(*npp
)->right
;
1444 np
->parent
= parent
;
1447 /* Optimize each of the two split parts. */
1448 balance_case_nodes (&np
->left
, np
);
1449 balance_case_nodes (&np
->right
, np
);
1450 np
->subtree_prob
= np
->prob
;
1451 np
->subtree_prob
+= np
->left
->subtree_prob
;
1452 np
->subtree_prob
+= np
->right
->subtree_prob
;
1456 /* Else leave this branch as one level,
1457 but fill in `parent' fields. */
1459 np
->parent
= parent
;
1460 np
->subtree_prob
= np
->prob
;
1461 for (; np
->right
; np
= np
->right
)
1463 np
->right
->parent
= np
;
1464 (*head
)->subtree_prob
+= np
->right
->subtree_prob
;
1470 /* Search the parent sections of the case node tree
1471 to see if a test for the lower bound of NODE would be redundant.
1472 INDEX_TYPE is the type of the index expression.
1474 The instructions to generate the case decision tree are
1475 output in the same order as nodes are processed so it is
1476 known that if a parent node checks the range of the current
1477 node minus one that the current node is bounded at its lower
1478 span. Thus the test would be redundant. */
1481 node_has_low_bound (case_node_ptr node
, tree index_type
)
1484 case_node_ptr pnode
;
1486 /* If the lower bound of this node is the lowest value in the index type,
1487 we need not test it. */
1489 if (tree_int_cst_equal (node
->low
, TYPE_MIN_VALUE (index_type
)))
1492 /* If this node has a left branch, the value at the left must be less
1493 than that at this node, so it cannot be bounded at the bottom and
1494 we need not bother testing any further. */
1499 low_minus_one
= fold_build2 (MINUS_EXPR
, TREE_TYPE (node
->low
),
1501 build_int_cst (TREE_TYPE (node
->low
), 1));
1503 /* If the subtraction above overflowed, we can't verify anything.
1504 Otherwise, look for a parent that tests our value - 1. */
1506 if (! tree_int_cst_lt (low_minus_one
, node
->low
))
1509 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1510 if (tree_int_cst_equal (low_minus_one
, pnode
->high
))
1516 /* Search the parent sections of the case node tree
1517 to see if a test for the upper bound of NODE would be redundant.
1518 INDEX_TYPE is the type of the index expression.
1520 The instructions to generate the case decision tree are
1521 output in the same order as nodes are processed so it is
1522 known that if a parent node checks the range of the current
1523 node plus one that the current node is bounded at its upper
1524 span. Thus the test would be redundant. */
1527 node_has_high_bound (case_node_ptr node
, tree index_type
)
1530 case_node_ptr pnode
;
1532 /* If there is no upper bound, obviously no test is needed. */
1534 if (TYPE_MAX_VALUE (index_type
) == NULL
)
1537 /* If the upper bound of this node is the highest value in the type
1538 of the index expression, we need not test against it. */
1540 if (tree_int_cst_equal (node
->high
, TYPE_MAX_VALUE (index_type
)))
1543 /* If this node has a right branch, the value at the right must be greater
1544 than that at this node, so it cannot be bounded at the top and
1545 we need not bother testing any further. */
1550 high_plus_one
= fold_build2 (PLUS_EXPR
, TREE_TYPE (node
->high
),
1552 build_int_cst (TREE_TYPE (node
->high
), 1));
1554 /* If the addition above overflowed, we can't verify anything.
1555 Otherwise, look for a parent that tests our value + 1. */
1557 if (! tree_int_cst_lt (node
->high
, high_plus_one
))
1560 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1561 if (tree_int_cst_equal (high_plus_one
, pnode
->low
))
1567 /* Search the parent sections of the
1568 case node tree to see if both tests for the upper and lower
1569 bounds of NODE would be redundant. */
1572 node_is_bounded (case_node_ptr node
, tree index_type
)
1574 return (node_has_low_bound (node
, index_type
)
1575 && node_has_high_bound (node
, index_type
));
1579 /* Emit step-by-step code to select a case for the value of INDEX.
1580 The thus generated decision tree follows the form of the
1581 case-node binary tree NODE, whose nodes represent test conditions.
1582 INDEX_TYPE is the type of the index of the switch.
1584 Care is taken to prune redundant tests from the decision tree
1585 by detecting any boundary conditions already checked by
1586 emitted rtx. (See node_has_high_bound, node_has_low_bound
1587 and node_is_bounded, above.)
1589 Where the test conditions can be shown to be redundant we emit
1590 an unconditional jump to the target code. As a further
1591 optimization, the subordinates of a tree node are examined to
1592 check for bounded nodes. In this case conditional and/or
1593 unconditional jumps as a result of the boundary check for the
1594 current node are arranged to target the subordinates associated
1595 code for out of bound conditions on the current node.
1597 We can assume that when control reaches the code generated here,
1598 the index value has already been compared with the parents
1599 of this node, and determined to be on the same side of each parent
1600 as this node is. Thus, if this node tests for the value 51,
1601 and a parent tested for 52, we don't need to consider
1602 the possibility of a value greater than 51. If another parent
1603 tests for the value 50, then this node need not test anything. */
1606 emit_case_nodes (rtx index
, case_node_ptr node
, rtx default_label
,
1607 int default_prob
, tree index_type
)
1609 /* If INDEX has an unsigned type, we must make unsigned branches. */
1610 int unsignedp
= TYPE_UNSIGNED (index_type
);
1612 int prob
= node
->prob
, subtree_prob
= node
->subtree_prob
;
1613 enum machine_mode mode
= GET_MODE (index
);
1614 enum machine_mode imode
= TYPE_MODE (index_type
);
1616 /* Handle indices detected as constant during RTL expansion. */
1617 if (mode
== VOIDmode
)
1620 /* See if our parents have already tested everything for us.
1621 If they have, emit an unconditional jump for this node. */
1622 if (node_is_bounded (node
, index_type
))
1623 emit_jump (label_rtx (node
->code_label
));
1625 else if (tree_int_cst_equal (node
->low
, node
->high
))
1627 probability
= conditional_probability (prob
, subtree_prob
+ default_prob
);
1628 /* Node is single valued. First see if the index expression matches
1629 this node and then check our children, if any. */
1630 do_jump_if_equal (mode
, index
,
1631 convert_modes (mode
, imode
,
1632 expand_normal (node
->low
),
1634 label_rtx (node
->code_label
), unsignedp
, probability
);
1635 /* Since this case is taken at this point, reduce its weight from
1637 subtree_prob
-= prob
;
1638 if (node
->right
!= 0 && node
->left
!= 0)
1640 /* This node has children on both sides.
1641 Dispatch to one side or the other
1642 by comparing the index value with this node's value.
1643 If one subtree is bounded, check that one first,
1644 so we can avoid real branches in the tree. */
1646 if (node_is_bounded (node
->right
, index_type
))
1648 probability
= conditional_probability (
1650 subtree_prob
+ default_prob
);
1651 emit_cmp_and_jump_insns (index
,
1654 expand_normal (node
->high
),
1656 GT
, NULL_RTX
, mode
, unsignedp
,
1657 label_rtx (node
->right
->code_label
),
1659 emit_case_nodes (index
, node
->left
, default_label
, default_prob
,
1663 else if (node_is_bounded (node
->left
, index_type
))
1665 probability
= conditional_probability (
1667 subtree_prob
+ default_prob
);
1668 emit_cmp_and_jump_insns (index
,
1671 expand_normal (node
->high
),
1673 LT
, NULL_RTX
, mode
, unsignedp
,
1674 label_rtx (node
->left
->code_label
),
1676 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1679 /* If both children are single-valued cases with no
1680 children, finish up all the work. This way, we can save
1681 one ordered comparison. */
1682 else if (tree_int_cst_equal (node
->right
->low
, node
->right
->high
)
1683 && node
->right
->left
== 0
1684 && node
->right
->right
== 0
1685 && tree_int_cst_equal (node
->left
->low
, node
->left
->high
)
1686 && node
->left
->left
== 0
1687 && node
->left
->right
== 0)
1689 /* Neither node is bounded. First distinguish the two sides;
1690 then emit the code for one side at a time. */
1692 /* See if the value matches what the right hand side
1694 probability
= conditional_probability (
1696 subtree_prob
+ default_prob
);
1697 do_jump_if_equal (mode
, index
,
1698 convert_modes (mode
, imode
,
1699 expand_normal (node
->right
->low
),
1701 label_rtx (node
->right
->code_label
),
1702 unsignedp
, probability
);
1704 /* See if the value matches what the left hand side
1706 probability
= conditional_probability (
1708 subtree_prob
+ default_prob
);
1709 do_jump_if_equal (mode
, index
,
1710 convert_modes (mode
, imode
,
1711 expand_normal (node
->left
->low
),
1713 label_rtx (node
->left
->code_label
),
1714 unsignedp
, probability
);
1719 /* Neither node is bounded. First distinguish the two sides;
1720 then emit the code for one side at a time. */
1723 = build_decl (curr_insn_location (),
1724 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
1726 /* The default label could be reached either through the right
1727 subtree or the left subtree. Divide the probability
1729 probability
= conditional_probability (
1730 node
->right
->subtree_prob
+ default_prob
/2,
1731 subtree_prob
+ default_prob
);
1732 /* See if the value is on the right. */
1733 emit_cmp_and_jump_insns (index
,
1736 expand_normal (node
->high
),
1738 GT
, NULL_RTX
, mode
, unsignedp
,
1739 label_rtx (test_label
),
1743 /* Value must be on the left.
1744 Handle the left-hand subtree. */
1745 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1746 /* If left-hand subtree does nothing,
1749 emit_jump (default_label
);
1751 /* Code branches here for the right-hand subtree. */
1752 expand_label (test_label
);
1753 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1757 else if (node
->right
!= 0 && node
->left
== 0)
1759 /* Here we have a right child but no left so we issue a conditional
1760 branch to default and process the right child.
1762 Omit the conditional branch to default if the right child
1763 does not have any children and is single valued; it would
1764 cost too much space to save so little time. */
1766 if (node
->right
->right
|| node
->right
->left
1767 || !tree_int_cst_equal (node
->right
->low
, node
->right
->high
))
1769 if (!node_has_low_bound (node
, index_type
))
1771 probability
= conditional_probability (
1773 subtree_prob
+ default_prob
);
1774 emit_cmp_and_jump_insns (index
,
1777 expand_normal (node
->high
),
1779 LT
, NULL_RTX
, mode
, unsignedp
,
1785 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1789 probability
= conditional_probability (
1790 node
->right
->subtree_prob
,
1791 subtree_prob
+ default_prob
);
1792 /* We cannot process node->right normally
1793 since we haven't ruled out the numbers less than
1794 this node's value. So handle node->right explicitly. */
1795 do_jump_if_equal (mode
, index
,
1798 expand_normal (node
->right
->low
),
1800 label_rtx (node
->right
->code_label
), unsignedp
, probability
);
1804 else if (node
->right
== 0 && node
->left
!= 0)
1806 /* Just one subtree, on the left. */
1807 if (node
->left
->left
|| node
->left
->right
1808 || !tree_int_cst_equal (node
->left
->low
, node
->left
->high
))
1810 if (!node_has_high_bound (node
, index_type
))
1812 probability
= conditional_probability (
1814 subtree_prob
+ default_prob
);
1815 emit_cmp_and_jump_insns (index
,
1818 expand_normal (node
->high
),
1820 GT
, NULL_RTX
, mode
, unsignedp
,
1826 emit_case_nodes (index
, node
->left
, default_label
,
1827 default_prob
, index_type
);
1831 probability
= conditional_probability (
1832 node
->left
->subtree_prob
,
1833 subtree_prob
+ default_prob
);
1834 /* We cannot process node->left normally
1835 since we haven't ruled out the numbers less than
1836 this node's value. So handle node->left explicitly. */
1837 do_jump_if_equal (mode
, index
,
1840 expand_normal (node
->left
->low
),
1842 label_rtx (node
->left
->code_label
), unsignedp
, probability
);
1848 /* Node is a range. These cases are very similar to those for a single
1849 value, except that we do not start by testing whether this node
1850 is the one to branch to. */
1852 if (node
->right
!= 0 && node
->left
!= 0)
1854 /* Node has subtrees on both sides.
1855 If the right-hand subtree is bounded,
1856 test for it first, since we can go straight there.
1857 Otherwise, we need to make a branch in the control structure,
1858 then handle the two subtrees. */
1859 tree test_label
= 0;
1861 if (node_is_bounded (node
->right
, index_type
))
1863 /* Right hand node is fully bounded so we can eliminate any
1864 testing and branch directly to the target code. */
1865 probability
= conditional_probability (
1866 node
->right
->subtree_prob
,
1867 subtree_prob
+ default_prob
);
1868 emit_cmp_and_jump_insns (index
,
1871 expand_normal (node
->high
),
1873 GT
, NULL_RTX
, mode
, unsignedp
,
1874 label_rtx (node
->right
->code_label
),
1879 /* Right hand node requires testing.
1880 Branch to a label where we will handle it later. */
1882 test_label
= build_decl (curr_insn_location (),
1883 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
1884 probability
= conditional_probability (
1885 node
->right
->subtree_prob
+ default_prob
/2,
1886 subtree_prob
+ default_prob
);
1887 emit_cmp_and_jump_insns (index
,
1890 expand_normal (node
->high
),
1892 GT
, NULL_RTX
, mode
, unsignedp
,
1893 label_rtx (test_label
),
1898 /* Value belongs to this node or to the left-hand subtree. */
1900 probability
= conditional_probability (
1902 subtree_prob
+ default_prob
);
1903 emit_cmp_and_jump_insns (index
,
1906 expand_normal (node
->low
),
1908 GE
, NULL_RTX
, mode
, unsignedp
,
1909 label_rtx (node
->code_label
),
1912 /* Handle the left-hand subtree. */
1913 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1915 /* If right node had to be handled later, do that now. */
1919 /* If the left-hand subtree fell through,
1920 don't let it fall into the right-hand subtree. */
1922 emit_jump (default_label
);
1924 expand_label (test_label
);
1925 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1929 else if (node
->right
!= 0 && node
->left
== 0)
1931 /* Deal with values to the left of this node,
1932 if they are possible. */
1933 if (!node_has_low_bound (node
, index_type
))
1935 probability
= conditional_probability (
1937 subtree_prob
+ default_prob
);
1938 emit_cmp_and_jump_insns (index
,
1941 expand_normal (node
->low
),
1943 LT
, NULL_RTX
, mode
, unsignedp
,
1949 /* Value belongs to this node or to the right-hand subtree. */
1951 probability
= conditional_probability (
1953 subtree_prob
+ default_prob
);
1954 emit_cmp_and_jump_insns (index
,
1957 expand_normal (node
->high
),
1959 LE
, NULL_RTX
, mode
, unsignedp
,
1960 label_rtx (node
->code_label
),
1963 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1966 else if (node
->right
== 0 && node
->left
!= 0)
1968 /* Deal with values to the right of this node,
1969 if they are possible. */
1970 if (!node_has_high_bound (node
, index_type
))
1972 probability
= conditional_probability (
1974 subtree_prob
+ default_prob
);
1975 emit_cmp_and_jump_insns (index
,
1978 expand_normal (node
->high
),
1980 GT
, NULL_RTX
, mode
, unsignedp
,
1986 /* Value belongs to this node or to the left-hand subtree. */
1988 probability
= conditional_probability (
1990 subtree_prob
+ default_prob
);
1991 emit_cmp_and_jump_insns (index
,
1994 expand_normal (node
->low
),
1996 GE
, NULL_RTX
, mode
, unsignedp
,
1997 label_rtx (node
->code_label
),
2000 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
2005 /* Node has no children so we check low and high bounds to remove
2006 redundant tests. Only one of the bounds can exist,
2007 since otherwise this node is bounded--a case tested already. */
2008 int high_bound
= node_has_high_bound (node
, index_type
);
2009 int low_bound
= node_has_low_bound (node
, index_type
);
2011 if (!high_bound
&& low_bound
)
2013 probability
= conditional_probability (
2015 subtree_prob
+ default_prob
);
2016 emit_cmp_and_jump_insns (index
,
2019 expand_normal (node
->high
),
2021 GT
, NULL_RTX
, mode
, unsignedp
,
2026 else if (!low_bound
&& high_bound
)
2028 probability
= conditional_probability (
2030 subtree_prob
+ default_prob
);
2031 emit_cmp_and_jump_insns (index
,
2034 expand_normal (node
->low
),
2036 LT
, NULL_RTX
, mode
, unsignedp
,
2040 else if (!low_bound
&& !high_bound
)
2042 /* Widen LOW and HIGH to the same width as INDEX. */
2043 tree type
= lang_hooks
.types
.type_for_mode (mode
, unsignedp
);
2044 tree low
= build1 (CONVERT_EXPR
, type
, node
->low
);
2045 tree high
= build1 (CONVERT_EXPR
, type
, node
->high
);
2046 rtx low_rtx
, new_index
, new_bound
;
2048 /* Instead of doing two branches, emit one unsigned branch for
2049 (index-low) > (high-low). */
2050 low_rtx
= expand_expr (low
, NULL_RTX
, mode
, EXPAND_NORMAL
);
2051 new_index
= expand_simple_binop (mode
, MINUS
, index
, low_rtx
,
2052 NULL_RTX
, unsignedp
,
2054 new_bound
= expand_expr (fold_build2 (MINUS_EXPR
, type
,
2056 NULL_RTX
, mode
, EXPAND_NORMAL
);
2058 probability
= conditional_probability (
2060 subtree_prob
+ default_prob
);
2061 emit_cmp_and_jump_insns (new_index
, new_bound
, GT
, NULL_RTX
,
2062 mode
, 1, default_label
, probability
);
2065 emit_jump (label_rtx (node
->code_label
));