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
)
777 HOST_WIDE_INT low
, high
;
783 dump_case_nodes (f
, root
->left
, indent_step
, indent_level
);
785 low
= tree_to_shwi (root
->low
);
786 high
= tree_to_shwi (root
->high
);
790 fprintf (f
, "%*s" HOST_WIDE_INT_PRINT_DEC
,
791 indent_step
* indent_level
, "", low
);
793 fprintf (f
, "%*s" HOST_WIDE_INT_PRINT_DEC
" ... " HOST_WIDE_INT_PRINT_DEC
,
794 indent_step
* indent_level
, "", low
, high
);
797 dump_case_nodes (f
, root
->right
, indent_step
, indent_level
);
801 #define HAVE_casesi 0
804 #ifndef HAVE_tablejump
805 #define HAVE_tablejump 0
808 /* Return the smallest number of different values for which it is best to use a
809 jump-table instead of a tree of conditional branches. */
812 case_values_threshold (void)
814 unsigned int threshold
= PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD
);
817 threshold
= targetm
.case_values_threshold ();
822 /* Return true if a switch should be expanded as a decision tree.
823 RANGE is the difference between highest and lowest case.
824 UNIQ is number of unique case node targets, not counting the default case.
825 COUNT is the number of comparisons needed, not counting the default case. */
828 expand_switch_as_decision_tree_p (tree range
,
829 unsigned int uniq ATTRIBUTE_UNUSED
,
834 /* If neither casesi or tablejump is available, or flag_jump_tables
835 over-ruled us, we really have no choice. */
836 if (!HAVE_casesi
&& !HAVE_tablejump
)
838 if (!flag_jump_tables
)
840 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
845 /* If the switch is relatively small such that the cost of one
846 indirect jump on the target are higher than the cost of a
847 decision tree, go with the decision tree.
849 If range of values is much bigger than number of values,
850 or if it is too large to represent in a HOST_WIDE_INT,
851 make a sequence of conditional branches instead of a dispatch.
853 The definition of "much bigger" depends on whether we are
854 optimizing for size or for speed. If the former, the maximum
855 ratio range/count = 3, because this was found to be the optimal
856 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
857 10 is much older, and was probably selected after an extensive
858 benchmarking investigation on numerous platforms. Or maybe it
859 just made sense to someone at some point in the history of GCC,
861 max_ratio
= optimize_insn_for_size_p () ? 3 : 10;
862 if (count
< case_values_threshold ()
863 || ! tree_fits_uhwi_p (range
)
864 || compare_tree_int (range
, max_ratio
* count
) > 0)
870 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
871 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
872 DEFAULT_PROB is the estimated probability that it jumps to
875 We generate a binary decision tree to select the appropriate target
876 code. This is done as follows:
878 If the index is a short or char that we do not have
879 an insn to handle comparisons directly, convert it to
880 a full integer now, rather than letting each comparison
881 generate the conversion.
883 Load the index into a register.
885 The list of cases is rearranged into a binary tree,
886 nearly optimal assuming equal probability for each case.
888 The tree is transformed into RTL, eliminating redundant
889 test conditions at the same time.
891 If program flow could reach the end of the decision tree
892 an unconditional jump to the default code is emitted.
894 The above process is unaware of the CFG. The caller has to fix up
895 the CFG itself. This is done in cfgexpand.c. */
898 emit_case_decision_tree (tree index_expr
, tree index_type
,
899 struct case_node
*case_list
, rtx default_label
,
902 rtx index
= expand_normal (index_expr
);
904 if (GET_MODE_CLASS (GET_MODE (index
)) == MODE_INT
905 && ! have_insn_for (COMPARE
, GET_MODE (index
)))
907 int unsignedp
= TYPE_UNSIGNED (index_type
);
908 enum machine_mode wider_mode
;
909 for (wider_mode
= GET_MODE (index
); wider_mode
!= VOIDmode
;
910 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
911 if (have_insn_for (COMPARE
, wider_mode
))
913 index
= convert_to_mode (wider_mode
, index
, unsignedp
);
918 do_pending_stack_adjust ();
922 index
= copy_to_reg (index
);
923 if (TREE_CODE (index_expr
) == SSA_NAME
)
924 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr
), index
);
927 balance_case_nodes (&case_list
, NULL
);
929 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
931 int indent_step
= ceil_log2 (TYPE_PRECISION (index_type
)) + 2;
932 fprintf (dump_file
, ";; Expanding GIMPLE switch as decision tree:\n");
933 dump_case_nodes (dump_file
, case_list
, indent_step
, 0);
936 emit_case_nodes (index
, case_list
, default_label
, default_prob
, index_type
);
938 emit_jump (default_label
);
941 /* Return the sum of probabilities of outgoing edges of basic block BB. */
944 get_outgoing_edge_probs (basic_block bb
)
951 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
952 prob_sum
+= e
->probability
;
956 /* Computes the conditional probability of jumping to a target if the branch
957 instruction is executed.
958 TARGET_PROB is the estimated probability of jumping to a target relative
959 to some basic block BB.
960 BASE_PROB is the probability of reaching the branch instruction relative
961 to the same basic block BB. */
964 conditional_probability (int target_prob
, int base_prob
)
968 gcc_assert (target_prob
>= 0);
969 gcc_assert (target_prob
<= base_prob
);
970 return GCOV_COMPUTE_SCALE (target_prob
, base_prob
);
975 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
976 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
977 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
978 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
980 First, a jump insn is emitted. First we try "casesi". If that
981 fails, try "tablejump". A target *must* have one of them (or both).
983 Then, a table with the target labels is emitted.
985 The process is unaware of the CFG. The caller has to fix up
986 the CFG itself. This is done in cfgexpand.c. */
989 emit_case_dispatch_table (tree index_expr
, tree index_type
,
990 struct case_node
*case_list
, rtx default_label
,
991 tree minval
, tree maxval
, tree range
,
997 rtx fallback_label
= label_rtx (case_list
->code_label
);
998 rtx table_label
= gen_label_rtx ();
999 bool has_gaps
= false;
1000 edge default_edge
= stmt_bb
? EDGE_SUCC (stmt_bb
, 0) : NULL
;
1001 int default_prob
= default_edge
? default_edge
->probability
: 0;
1002 int base
= get_outgoing_edge_probs (stmt_bb
);
1003 bool try_with_tablejump
= false;
1005 int new_default_prob
= conditional_probability (default_prob
,
1008 if (! try_casesi (index_type
, index_expr
, minval
, range
,
1009 table_label
, default_label
, fallback_label
,
1012 /* Index jumptables from zero for suitable values of minval to avoid
1013 a subtraction. For the rationale see:
1014 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
1015 if (optimize_insn_for_speed_p ()
1016 && compare_tree_int (minval
, 0) > 0
1017 && compare_tree_int (minval
, 3) < 0)
1019 minval
= build_int_cst (index_type
, 0);
1023 try_with_tablejump
= true;
1026 /* Get table of labels to jump to, in order of case index. */
1028 ncases
= tree_to_shwi (range
) + 1;
1029 labelvec
= XALLOCAVEC (rtx
, ncases
);
1030 memset (labelvec
, 0, ncases
* sizeof (rtx
));
1032 for (n
= case_list
; n
; n
= n
->right
)
1034 /* Compute the low and high bounds relative to the minimum
1035 value since that should fit in a HOST_WIDE_INT while the
1036 actual values may not. */
1038 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1040 HOST_WIDE_INT i_high
1041 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1045 for (i
= i_low
; i
<= i_high
; i
++)
1047 = gen_rtx_LABEL_REF (Pmode
, label_rtx (n
->code_label
));
1050 /* Fill in the gaps with the default. We may have gaps at
1051 the beginning if we tried to avoid the minval subtraction,
1052 so substitute some label even if the default label was
1053 deemed unreachable. */
1055 default_label
= fallback_label
;
1056 for (i
= 0; i
< ncases
; i
++)
1057 if (labelvec
[i
] == 0)
1060 labelvec
[i
] = gen_rtx_LABEL_REF (Pmode
, default_label
);
1065 /* There is at least one entry in the jump table that jumps
1066 to default label. The default label can either be reached
1067 through the indirect jump or the direct conditional jump
1068 before that. Split the probability of reaching the
1069 default label among these two jumps. */
1070 new_default_prob
= conditional_probability (default_prob
/2,
1073 base
-= default_prob
;
1077 base
-= default_prob
;
1082 default_edge
->probability
= default_prob
;
1084 /* We have altered the probability of the default edge. So the probabilities
1085 of all other edges need to be adjusted so that it sums up to
1086 REG_BR_PROB_BASE. */
1091 FOR_EACH_EDGE (e
, ei
, stmt_bb
->succs
)
1092 e
->probability
= GCOV_COMPUTE_SCALE (e
->probability
, base
);
1095 if (try_with_tablejump
)
1097 bool ok
= try_tablejump (index_type
, index_expr
, minval
, range
,
1098 table_label
, default_label
, new_default_prob
);
1101 /* Output the table. */
1102 emit_label (table_label
);
1104 if (CASE_VECTOR_PC_RELATIVE
|| flag_pic
)
1105 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE
,
1106 gen_rtx_LABEL_REF (Pmode
,
1108 gen_rtvec_v (ncases
, labelvec
),
1109 const0_rtx
, const0_rtx
));
1111 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE
,
1112 gen_rtvec_v (ncases
, labelvec
)));
1114 /* Record no drop-through after the table. */
1118 /* Reset the aux field of all outgoing edges of basic block BB. */
1121 reset_out_edges_aux (basic_block bb
)
1125 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1129 /* Compute the number of case labels that correspond to each outgoing edge of
1130 STMT. Record this information in the aux field of the edge. */
1133 compute_cases_per_edge (gimple stmt
)
1135 basic_block bb
= gimple_bb (stmt
);
1136 reset_out_edges_aux (bb
);
1137 int ncases
= gimple_switch_num_labels (stmt
);
1138 for (int i
= ncases
- 1; i
>= 1; --i
)
1140 tree elt
= gimple_switch_label (stmt
, i
);
1141 tree lab
= CASE_LABEL (elt
);
1142 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1143 edge case_edge
= find_edge (bb
, case_bb
);
1144 case_edge
->aux
= (void *)((intptr_t)(case_edge
->aux
) + 1);
1148 /* Terminate a case (Pascal/Ada) or switch (C) statement
1149 in which ORIG_INDEX is the expression to be tested.
1150 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
1151 type as given in the source before any compiler conversions.
1152 Generate the code to test it and jump to the right place. */
1155 expand_case (gimple stmt
)
1157 tree minval
= NULL_TREE
, maxval
= NULL_TREE
, range
= NULL_TREE
;
1158 rtx default_label
= NULL_RTX
;
1159 unsigned int count
, uniq
;
1161 int ncases
= gimple_switch_num_labels (stmt
);
1162 tree index_expr
= gimple_switch_index (stmt
);
1163 tree index_type
= TREE_TYPE (index_expr
);
1165 basic_block bb
= gimple_bb (stmt
);
1167 /* A list of case labels; it is first built as a list and it may then
1168 be rearranged into a nearly balanced binary tree. */
1169 struct case_node
*case_list
= 0;
1171 /* A pool for case nodes. */
1172 alloc_pool case_node_pool
;
1174 /* An ERROR_MARK occurs for various reasons including invalid data type.
1175 ??? Can this still happen, with GIMPLE and all? */
1176 if (index_type
== error_mark_node
)
1179 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
1180 expressions being INTEGER_CST. */
1181 gcc_assert (TREE_CODE (index_expr
) != INTEGER_CST
);
1183 case_node_pool
= create_alloc_pool ("struct case_node pool",
1184 sizeof (struct case_node
),
1187 do_pending_stack_adjust ();
1189 /* Find the default case target label. */
1190 default_label
= label_rtx (CASE_LABEL (gimple_switch_default_label (stmt
)));
1191 edge default_edge
= EDGE_SUCC (bb
, 0);
1192 int default_prob
= default_edge
->probability
;
1194 /* Get upper and lower bounds of case values. */
1195 elt
= gimple_switch_label (stmt
, 1);
1196 minval
= fold_convert (index_type
, CASE_LOW (elt
));
1197 elt
= gimple_switch_label (stmt
, ncases
- 1);
1198 if (CASE_HIGH (elt
))
1199 maxval
= fold_convert (index_type
, CASE_HIGH (elt
));
1201 maxval
= fold_convert (index_type
, CASE_LOW (elt
));
1203 /* Compute span of values. */
1204 range
= fold_build2 (MINUS_EXPR
, index_type
, maxval
, minval
);
1206 /* Listify the labels queue and gather some numbers to decide
1207 how to expand this switch(). */
1210 struct pointer_set_t
*seen_labels
= pointer_set_create ();
1211 compute_cases_per_edge (stmt
);
1213 for (i
= ncases
- 1; i
>= 1; --i
)
1215 elt
= gimple_switch_label (stmt
, i
);
1216 tree low
= CASE_LOW (elt
);
1218 tree high
= CASE_HIGH (elt
);
1219 gcc_assert (! high
|| tree_int_cst_lt (low
, high
));
1220 tree lab
= CASE_LABEL (elt
);
1222 /* Count the elements.
1223 A range counts double, since it requires two compares. */
1228 /* If we have not seen this label yet, then increase the
1229 number of unique case node targets seen. */
1230 if (!pointer_set_insert (seen_labels
, lab
))
1233 /* The bounds on the case range, LOW and HIGH, have to be converted
1234 to case's index type TYPE. Note that the original type of the
1235 case index in the source code is usually "lost" during
1236 gimplification due to type promotion, but the case labels retain the
1237 original type. Make sure to drop overflow flags. */
1238 low
= fold_convert (index_type
, low
);
1239 if (TREE_OVERFLOW (low
))
1240 low
= wide_int_to_tree (index_type
, low
);
1242 /* The canonical from of a case label in GIMPLE is that a simple case
1243 has an empty CASE_HIGH. For the casesi and tablejump expanders,
1244 the back ends want simple cases to have high == low. */
1247 high
= fold_convert (index_type
, high
);
1248 if (TREE_OVERFLOW (high
))
1249 high
= wide_int_to_tree (index_type
, high
);
1251 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1252 edge case_edge
= find_edge (bb
, case_bb
);
1253 case_list
= add_case_node (
1254 case_list
, low
, high
, lab
,
1255 case_edge
->probability
/ (intptr_t)(case_edge
->aux
),
1258 pointer_set_destroy (seen_labels
);
1259 reset_out_edges_aux (bb
);
1261 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
1262 destination, such as one with a default case only.
1263 It also removes cases that are out of range for the switch
1264 type, so we should never get a zero here. */
1265 gcc_assert (count
> 0);
1267 rtx before_case
= get_last_insn ();
1269 /* Decide how to expand this switch.
1270 The two options at this point are a dispatch table (casesi or
1271 tablejump) or a decision tree. */
1273 if (expand_switch_as_decision_tree_p (range
, uniq
, count
))
1274 emit_case_decision_tree (index_expr
, index_type
,
1275 case_list
, default_label
,
1278 emit_case_dispatch_table (index_expr
, index_type
,
1279 case_list
, default_label
,
1280 minval
, maxval
, range
, bb
);
1282 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1285 free_alloc_pool (case_node_pool
);
1288 /* Expand the dispatch to a short decrement chain if there are few cases
1289 to dispatch to. Likewise if neither casesi nor tablejump is available,
1290 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
1291 tablejump. The index mode is always the mode of integer_type_node.
1292 Trap if no case matches the index.
1294 DISPATCH_INDEX is the index expression to switch on. It should be a
1295 memory or register operand.
1297 DISPATCH_TABLE is a set of case labels. The set should be sorted in
1298 ascending order, be contiguous, starting with value 0, and contain only
1299 single-valued case labels. */
1302 expand_sjlj_dispatch_table (rtx dispatch_index
,
1303 vec
<tree
> dispatch_table
)
1305 tree index_type
= integer_type_node
;
1306 enum machine_mode index_mode
= TYPE_MODE (index_type
);
1308 int ncases
= dispatch_table
.length ();
1310 do_pending_stack_adjust ();
1311 rtx before_case
= get_last_insn ();
1313 /* Expand as a decrement-chain if there are 5 or fewer dispatch
1314 labels. This covers more than 98% of the cases in libjava,
1315 and seems to be a reasonable compromise between the "old way"
1316 of expanding as a decision tree or dispatch table vs. the "new
1317 way" with decrement chain or dispatch table. */
1318 if (dispatch_table
.length () <= 5
1319 || (!HAVE_casesi
&& !HAVE_tablejump
)
1320 || !flag_jump_tables
)
1322 /* Expand the dispatch as a decrement chain:
1324 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1328 if (index == 0) do_0; else index--;
1329 if (index == 0) do_1; else index--;
1331 if (index == 0) do_N; else index--;
1333 This is more efficient than a dispatch table on most machines.
1334 The last "index--" is redundant but the code is trivially dead
1335 and will be cleaned up by later passes. */
1336 rtx index
= copy_to_mode_reg (index_mode
, dispatch_index
);
1337 rtx zero
= CONST0_RTX (index_mode
);
1338 for (int i
= 0; i
< ncases
; i
++)
1340 tree elt
= dispatch_table
[i
];
1341 rtx lab
= label_rtx (CASE_LABEL (elt
));
1342 do_jump_if_equal (index_mode
, index
, zero
, lab
, 0, -1);
1343 force_expand_binop (index_mode
, sub_optab
,
1344 index
, CONST1_RTX (index_mode
),
1345 index
, 0, OPTAB_DIRECT
);
1350 /* Similar to expand_case, but much simpler. */
1351 struct case_node
*case_list
= 0;
1352 alloc_pool case_node_pool
= create_alloc_pool ("struct sjlj_case pool",
1353 sizeof (struct case_node
),
1355 tree index_expr
= make_tree (index_type
, dispatch_index
);
1356 tree minval
= build_int_cst (index_type
, 0);
1357 tree maxval
= CASE_LOW (dispatch_table
.last ());
1358 tree range
= maxval
;
1359 rtx default_label
= gen_label_rtx ();
1361 for (int i
= ncases
- 1; i
>= 0; --i
)
1363 tree elt
= dispatch_table
[i
];
1364 tree low
= CASE_LOW (elt
);
1365 tree lab
= CASE_LABEL (elt
);
1366 case_list
= add_case_node (case_list
, low
, low
, lab
, 0, case_node_pool
);
1369 emit_case_dispatch_table (index_expr
, index_type
,
1370 case_list
, default_label
,
1371 minval
, maxval
, range
,
1372 BLOCK_FOR_INSN (before_case
));
1373 emit_label (default_label
);
1374 free_alloc_pool (case_node_pool
);
1377 /* Dispatching something not handled? Trap! */
1378 expand_builtin_trap ();
1380 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1386 /* Take an ordered list of case nodes
1387 and transform them into a near optimal binary tree,
1388 on the assumption that any target code selection value is as
1389 likely as any other.
1391 The transformation is performed by splitting the ordered
1392 list into two equal sections plus a pivot. The parts are
1393 then attached to the pivot as left and right branches. Each
1394 branch is then transformed recursively. */
1397 balance_case_nodes (case_node_ptr
*head
, case_node_ptr parent
)
1409 /* Count the number of entries on branch. Also count the ranges. */
1413 if (!tree_int_cst_equal (np
->low
, np
->high
))
1422 /* Split this list if it is long enough for that to help. */
1426 /* If there are just three nodes, split at the middle one. */
1428 npp
= &(*npp
)->right
;
1431 /* Find the place in the list that bisects the list's total cost,
1432 where ranges count as 2.
1433 Here I gets half the total cost. */
1434 i
= (i
+ ranges
+ 1) / 2;
1437 /* Skip nodes while their cost does not reach that amount. */
1438 if (!tree_int_cst_equal ((*npp
)->low
, (*npp
)->high
))
1443 npp
= &(*npp
)->right
;
1448 np
->parent
= parent
;
1451 /* Optimize each of the two split parts. */
1452 balance_case_nodes (&np
->left
, np
);
1453 balance_case_nodes (&np
->right
, np
);
1454 np
->subtree_prob
= np
->prob
;
1455 np
->subtree_prob
+= np
->left
->subtree_prob
;
1456 np
->subtree_prob
+= np
->right
->subtree_prob
;
1460 /* Else leave this branch as one level,
1461 but fill in `parent' fields. */
1463 np
->parent
= parent
;
1464 np
->subtree_prob
= np
->prob
;
1465 for (; np
->right
; np
= np
->right
)
1467 np
->right
->parent
= np
;
1468 (*head
)->subtree_prob
+= np
->right
->subtree_prob
;
1474 /* Search the parent sections of the case node tree
1475 to see if a test for the lower bound of NODE would be redundant.
1476 INDEX_TYPE is the type of the index expression.
1478 The instructions to generate the case decision tree are
1479 output in the same order as nodes are processed so it is
1480 known that if a parent node checks the range of the current
1481 node minus one that the current node is bounded at its lower
1482 span. Thus the test would be redundant. */
1485 node_has_low_bound (case_node_ptr node
, tree index_type
)
1488 case_node_ptr pnode
;
1490 /* If the lower bound of this node is the lowest value in the index type,
1491 we need not test it. */
1493 if (tree_int_cst_equal (node
->low
, TYPE_MIN_VALUE (index_type
)))
1496 /* If this node has a left branch, the value at the left must be less
1497 than that at this node, so it cannot be bounded at the bottom and
1498 we need not bother testing any further. */
1503 low_minus_one
= fold_build2 (MINUS_EXPR
, TREE_TYPE (node
->low
),
1505 build_int_cst (TREE_TYPE (node
->low
), 1));
1507 /* If the subtraction above overflowed, we can't verify anything.
1508 Otherwise, look for a parent that tests our value - 1. */
1510 if (! tree_int_cst_lt (low_minus_one
, node
->low
))
1513 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1514 if (tree_int_cst_equal (low_minus_one
, pnode
->high
))
1520 /* Search the parent sections of the case node tree
1521 to see if a test for the upper bound of NODE would be redundant.
1522 INDEX_TYPE is the type of the index expression.
1524 The instructions to generate the case decision tree are
1525 output in the same order as nodes are processed so it is
1526 known that if a parent node checks the range of the current
1527 node plus one that the current node is bounded at its upper
1528 span. Thus the test would be redundant. */
1531 node_has_high_bound (case_node_ptr node
, tree index_type
)
1534 case_node_ptr pnode
;
1536 /* If there is no upper bound, obviously no test is needed. */
1538 if (TYPE_MAX_VALUE (index_type
) == NULL
)
1541 /* If the upper bound of this node is the highest value in the type
1542 of the index expression, we need not test against it. */
1544 if (tree_int_cst_equal (node
->high
, TYPE_MAX_VALUE (index_type
)))
1547 /* If this node has a right branch, the value at the right must be greater
1548 than that at this node, so it cannot be bounded at the top and
1549 we need not bother testing any further. */
1554 high_plus_one
= fold_build2 (PLUS_EXPR
, TREE_TYPE (node
->high
),
1556 build_int_cst (TREE_TYPE (node
->high
), 1));
1558 /* If the addition above overflowed, we can't verify anything.
1559 Otherwise, look for a parent that tests our value + 1. */
1561 if (! tree_int_cst_lt (node
->high
, high_plus_one
))
1564 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1565 if (tree_int_cst_equal (high_plus_one
, pnode
->low
))
1571 /* Search the parent sections of the
1572 case node tree to see if both tests for the upper and lower
1573 bounds of NODE would be redundant. */
1576 node_is_bounded (case_node_ptr node
, tree index_type
)
1578 return (node_has_low_bound (node
, index_type
)
1579 && node_has_high_bound (node
, index_type
));
1583 /* Emit step-by-step code to select a case for the value of INDEX.
1584 The thus generated decision tree follows the form of the
1585 case-node binary tree NODE, whose nodes represent test conditions.
1586 INDEX_TYPE is the type of the index of the switch.
1588 Care is taken to prune redundant tests from the decision tree
1589 by detecting any boundary conditions already checked by
1590 emitted rtx. (See node_has_high_bound, node_has_low_bound
1591 and node_is_bounded, above.)
1593 Where the test conditions can be shown to be redundant we emit
1594 an unconditional jump to the target code. As a further
1595 optimization, the subordinates of a tree node are examined to
1596 check for bounded nodes. In this case conditional and/or
1597 unconditional jumps as a result of the boundary check for the
1598 current node are arranged to target the subordinates associated
1599 code for out of bound conditions on the current node.
1601 We can assume that when control reaches the code generated here,
1602 the index value has already been compared with the parents
1603 of this node, and determined to be on the same side of each parent
1604 as this node is. Thus, if this node tests for the value 51,
1605 and a parent tested for 52, we don't need to consider
1606 the possibility of a value greater than 51. If another parent
1607 tests for the value 50, then this node need not test anything. */
1610 emit_case_nodes (rtx index
, case_node_ptr node
, rtx default_label
,
1611 int default_prob
, tree index_type
)
1613 /* If INDEX has an unsigned type, we must make unsigned branches. */
1614 int unsignedp
= TYPE_UNSIGNED (index_type
);
1616 int prob
= node
->prob
, subtree_prob
= node
->subtree_prob
;
1617 enum machine_mode mode
= GET_MODE (index
);
1618 enum machine_mode imode
= TYPE_MODE (index_type
);
1620 /* Handle indices detected as constant during RTL expansion. */
1621 if (mode
== VOIDmode
)
1624 /* See if our parents have already tested everything for us.
1625 If they have, emit an unconditional jump for this node. */
1626 if (node_is_bounded (node
, index_type
))
1627 emit_jump (label_rtx (node
->code_label
));
1629 else if (tree_int_cst_equal (node
->low
, node
->high
))
1631 probability
= conditional_probability (prob
, subtree_prob
+ default_prob
);
1632 /* Node is single valued. First see if the index expression matches
1633 this node and then check our children, if any. */
1634 do_jump_if_equal (mode
, index
,
1635 convert_modes (mode
, imode
,
1636 expand_normal (node
->low
),
1638 label_rtx (node
->code_label
), unsignedp
, probability
);
1639 /* Since this case is taken at this point, reduce its weight from
1641 subtree_prob
-= prob
;
1642 if (node
->right
!= 0 && node
->left
!= 0)
1644 /* This node has children on both sides.
1645 Dispatch to one side or the other
1646 by comparing the index value with this node's value.
1647 If one subtree is bounded, check that one first,
1648 so we can avoid real branches in the tree. */
1650 if (node_is_bounded (node
->right
, index_type
))
1652 probability
= conditional_probability (
1654 subtree_prob
+ default_prob
);
1655 emit_cmp_and_jump_insns (index
,
1658 expand_normal (node
->high
),
1660 GT
, NULL_RTX
, mode
, unsignedp
,
1661 label_rtx (node
->right
->code_label
),
1663 emit_case_nodes (index
, node
->left
, default_label
, default_prob
,
1667 else if (node_is_bounded (node
->left
, index_type
))
1669 probability
= conditional_probability (
1671 subtree_prob
+ default_prob
);
1672 emit_cmp_and_jump_insns (index
,
1675 expand_normal (node
->high
),
1677 LT
, NULL_RTX
, mode
, unsignedp
,
1678 label_rtx (node
->left
->code_label
),
1680 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1683 /* If both children are single-valued cases with no
1684 children, finish up all the work. This way, we can save
1685 one ordered comparison. */
1686 else if (tree_int_cst_equal (node
->right
->low
, node
->right
->high
)
1687 && node
->right
->left
== 0
1688 && node
->right
->right
== 0
1689 && tree_int_cst_equal (node
->left
->low
, node
->left
->high
)
1690 && node
->left
->left
== 0
1691 && node
->left
->right
== 0)
1693 /* Neither node is bounded. First distinguish the two sides;
1694 then emit the code for one side at a time. */
1696 /* See if the value matches what the right hand side
1698 probability
= conditional_probability (
1700 subtree_prob
+ default_prob
);
1701 do_jump_if_equal (mode
, index
,
1702 convert_modes (mode
, imode
,
1703 expand_normal (node
->right
->low
),
1705 label_rtx (node
->right
->code_label
),
1706 unsignedp
, probability
);
1708 /* See if the value matches what the left hand side
1710 probability
= conditional_probability (
1712 subtree_prob
+ default_prob
);
1713 do_jump_if_equal (mode
, index
,
1714 convert_modes (mode
, imode
,
1715 expand_normal (node
->left
->low
),
1717 label_rtx (node
->left
->code_label
),
1718 unsignedp
, probability
);
1723 /* Neither node is bounded. First distinguish the two sides;
1724 then emit the code for one side at a time. */
1727 = build_decl (curr_insn_location (),
1728 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
1730 /* The default label could be reached either through the right
1731 subtree or the left subtree. Divide the probability
1733 probability
= conditional_probability (
1734 node
->right
->subtree_prob
+ default_prob
/2,
1735 subtree_prob
+ default_prob
);
1736 /* See if the value is on the right. */
1737 emit_cmp_and_jump_insns (index
,
1740 expand_normal (node
->high
),
1742 GT
, NULL_RTX
, mode
, unsignedp
,
1743 label_rtx (test_label
),
1747 /* Value must be on the left.
1748 Handle the left-hand subtree. */
1749 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1750 /* If left-hand subtree does nothing,
1753 emit_jump (default_label
);
1755 /* Code branches here for the right-hand subtree. */
1756 expand_label (test_label
);
1757 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1761 else if (node
->right
!= 0 && node
->left
== 0)
1763 /* Here we have a right child but no left so we issue a conditional
1764 branch to default and process the right child.
1766 Omit the conditional branch to default if the right child
1767 does not have any children and is single valued; it would
1768 cost too much space to save so little time. */
1770 if (node
->right
->right
|| node
->right
->left
1771 || !tree_int_cst_equal (node
->right
->low
, node
->right
->high
))
1773 if (!node_has_low_bound (node
, index_type
))
1775 probability
= conditional_probability (
1777 subtree_prob
+ default_prob
);
1778 emit_cmp_and_jump_insns (index
,
1781 expand_normal (node
->high
),
1783 LT
, NULL_RTX
, mode
, unsignedp
,
1789 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1793 probability
= conditional_probability (
1794 node
->right
->subtree_prob
,
1795 subtree_prob
+ default_prob
);
1796 /* We cannot process node->right normally
1797 since we haven't ruled out the numbers less than
1798 this node's value. So handle node->right explicitly. */
1799 do_jump_if_equal (mode
, index
,
1802 expand_normal (node
->right
->low
),
1804 label_rtx (node
->right
->code_label
), unsignedp
, probability
);
1808 else if (node
->right
== 0 && node
->left
!= 0)
1810 /* Just one subtree, on the left. */
1811 if (node
->left
->left
|| node
->left
->right
1812 || !tree_int_cst_equal (node
->left
->low
, node
->left
->high
))
1814 if (!node_has_high_bound (node
, index_type
))
1816 probability
= conditional_probability (
1818 subtree_prob
+ default_prob
);
1819 emit_cmp_and_jump_insns (index
,
1822 expand_normal (node
->high
),
1824 GT
, NULL_RTX
, mode
, unsignedp
,
1830 emit_case_nodes (index
, node
->left
, default_label
,
1831 default_prob
, index_type
);
1835 probability
= conditional_probability (
1836 node
->left
->subtree_prob
,
1837 subtree_prob
+ default_prob
);
1838 /* We cannot process node->left normally
1839 since we haven't ruled out the numbers less than
1840 this node's value. So handle node->left explicitly. */
1841 do_jump_if_equal (mode
, index
,
1844 expand_normal (node
->left
->low
),
1846 label_rtx (node
->left
->code_label
), unsignedp
, probability
);
1852 /* Node is a range. These cases are very similar to those for a single
1853 value, except that we do not start by testing whether this node
1854 is the one to branch to. */
1856 if (node
->right
!= 0 && node
->left
!= 0)
1858 /* Node has subtrees on both sides.
1859 If the right-hand subtree is bounded,
1860 test for it first, since we can go straight there.
1861 Otherwise, we need to make a branch in the control structure,
1862 then handle the two subtrees. */
1863 tree test_label
= 0;
1865 if (node_is_bounded (node
->right
, index_type
))
1867 /* Right hand node is fully bounded so we can eliminate any
1868 testing and branch directly to the target code. */
1869 probability
= conditional_probability (
1870 node
->right
->subtree_prob
,
1871 subtree_prob
+ default_prob
);
1872 emit_cmp_and_jump_insns (index
,
1875 expand_normal (node
->high
),
1877 GT
, NULL_RTX
, mode
, unsignedp
,
1878 label_rtx (node
->right
->code_label
),
1883 /* Right hand node requires testing.
1884 Branch to a label where we will handle it later. */
1886 test_label
= build_decl (curr_insn_location (),
1887 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
1888 probability
= conditional_probability (
1889 node
->right
->subtree_prob
+ default_prob
/2,
1890 subtree_prob
+ default_prob
);
1891 emit_cmp_and_jump_insns (index
,
1894 expand_normal (node
->high
),
1896 GT
, NULL_RTX
, mode
, unsignedp
,
1897 label_rtx (test_label
),
1902 /* Value belongs to this node or to the left-hand subtree. */
1904 probability
= conditional_probability (
1906 subtree_prob
+ default_prob
);
1907 emit_cmp_and_jump_insns (index
,
1910 expand_normal (node
->low
),
1912 GE
, NULL_RTX
, mode
, unsignedp
,
1913 label_rtx (node
->code_label
),
1916 /* Handle the left-hand subtree. */
1917 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1919 /* If right node had to be handled later, do that now. */
1923 /* If the left-hand subtree fell through,
1924 don't let it fall into the right-hand subtree. */
1926 emit_jump (default_label
);
1928 expand_label (test_label
);
1929 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1933 else if (node
->right
!= 0 && node
->left
== 0)
1935 /* Deal with values to the left of this node,
1936 if they are possible. */
1937 if (!node_has_low_bound (node
, index_type
))
1939 probability
= conditional_probability (
1941 subtree_prob
+ default_prob
);
1942 emit_cmp_and_jump_insns (index
,
1945 expand_normal (node
->low
),
1947 LT
, NULL_RTX
, mode
, unsignedp
,
1953 /* Value belongs to this node or to the right-hand subtree. */
1955 probability
= conditional_probability (
1957 subtree_prob
+ default_prob
);
1958 emit_cmp_and_jump_insns (index
,
1961 expand_normal (node
->high
),
1963 LE
, NULL_RTX
, mode
, unsignedp
,
1964 label_rtx (node
->code_label
),
1967 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1970 else if (node
->right
== 0 && node
->left
!= 0)
1972 /* Deal with values to the right of this node,
1973 if they are possible. */
1974 if (!node_has_high_bound (node
, index_type
))
1976 probability
= conditional_probability (
1978 subtree_prob
+ default_prob
);
1979 emit_cmp_and_jump_insns (index
,
1982 expand_normal (node
->high
),
1984 GT
, NULL_RTX
, mode
, unsignedp
,
1990 /* Value belongs to this node or to the left-hand subtree. */
1992 probability
= conditional_probability (
1994 subtree_prob
+ default_prob
);
1995 emit_cmp_and_jump_insns (index
,
1998 expand_normal (node
->low
),
2000 GE
, NULL_RTX
, mode
, unsignedp
,
2001 label_rtx (node
->code_label
),
2004 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
2009 /* Node has no children so we check low and high bounds to remove
2010 redundant tests. Only one of the bounds can exist,
2011 since otherwise this node is bounded--a case tested already. */
2012 int high_bound
= node_has_high_bound (node
, index_type
);
2013 int low_bound
= node_has_low_bound (node
, index_type
);
2015 if (!high_bound
&& low_bound
)
2017 probability
= conditional_probability (
2019 subtree_prob
+ default_prob
);
2020 emit_cmp_and_jump_insns (index
,
2023 expand_normal (node
->high
),
2025 GT
, NULL_RTX
, mode
, unsignedp
,
2030 else if (!low_bound
&& high_bound
)
2032 probability
= conditional_probability (
2034 subtree_prob
+ default_prob
);
2035 emit_cmp_and_jump_insns (index
,
2038 expand_normal (node
->low
),
2040 LT
, NULL_RTX
, mode
, unsignedp
,
2044 else if (!low_bound
&& !high_bound
)
2046 /* Widen LOW and HIGH to the same width as INDEX. */
2047 tree type
= lang_hooks
.types
.type_for_mode (mode
, unsignedp
);
2048 tree low
= build1 (CONVERT_EXPR
, type
, node
->low
);
2049 tree high
= build1 (CONVERT_EXPR
, type
, node
->high
);
2050 rtx low_rtx
, new_index
, new_bound
;
2052 /* Instead of doing two branches, emit one unsigned branch for
2053 (index-low) > (high-low). */
2054 low_rtx
= expand_expr (low
, NULL_RTX
, mode
, EXPAND_NORMAL
);
2055 new_index
= expand_simple_binop (mode
, MINUS
, index
, low_rtx
,
2056 NULL_RTX
, unsignedp
,
2058 new_bound
= expand_expr (fold_build2 (MINUS_EXPR
, type
,
2060 NULL_RTX
, mode
, EXPAND_NORMAL
);
2062 probability
= conditional_probability (
2064 subtree_prob
+ default_prob
);
2065 emit_cmp_and_jump_insns (new_index
, new_bound
, GT
, NULL_RTX
,
2066 mode
, 1, default_label
, probability
);
2069 emit_jump (label_rtx (node
->code_label
));