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"
65 /* Functions and data structures for expanding case statements. */
67 /* Case label structure, used to hold info on labels within case
68 statements. We handle "range" labels; for a single-value label
69 as in C, the high and low limits are the same.
71 We start with a vector of case nodes sorted in ascending order, and
72 the default label as the last element in the vector. Before expanding
73 to RTL, we transform this vector into a list linked via the RIGHT
74 fields in the case_node struct. Nodes with higher case values are
77 Switch statements can be output in three forms. A branch table is
78 used if there are more than a few labels and the labels are dense
79 within the range between the smallest and largest case value. If a
80 branch table is used, no further manipulations are done with the case
83 The alternative to the use of a branch table is to generate a series
84 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
85 and PARENT fields to hold a binary tree. Initially the tree is
86 totally unbalanced, with everything on the right. We balance the tree
87 with nodes on the left having lower case values than the parent
88 and nodes on the right having higher values. We then output the tree
91 For very small, suitable switch statements, we can generate a series
92 of simple bit test and branches instead. */
96 struct case_node
*left
; /* Left son in binary tree */
97 struct case_node
*right
; /* Right son in binary tree; also node chain */
98 struct case_node
*parent
; /* Parent of node in binary tree */
99 tree low
; /* Lowest index value for this label */
100 tree high
; /* Highest index value for this label */
101 tree code_label
; /* Label to jump to when node matches */
102 int prob
; /* Probability of taking this case. */
103 /* Probability of reaching subtree rooted at this node */
107 typedef struct case_node case_node
;
108 typedef struct case_node
*case_node_ptr
;
110 extern basic_block
label_to_block_fn (struct function
*, tree
);
112 static bool check_unique_operand_names (tree
, tree
, tree
);
113 static char *resolve_operand_name_1 (char *, tree
, tree
, tree
);
114 static void balance_case_nodes (case_node_ptr
*, case_node_ptr
);
115 static int node_has_low_bound (case_node_ptr
, tree
);
116 static int node_has_high_bound (case_node_ptr
, tree
);
117 static int node_is_bounded (case_node_ptr
, tree
);
118 static void emit_case_nodes (rtx
, case_node_ptr
, rtx
, int, tree
);
120 /* Return the rtx-label that corresponds to a LABEL_DECL,
121 creating it if necessary. */
124 label_rtx (tree label
)
126 gcc_assert (TREE_CODE (label
) == LABEL_DECL
);
128 if (!DECL_RTL_SET_P (label
))
130 rtx r
= gen_label_rtx ();
131 SET_DECL_RTL (label
, r
);
132 if (FORCED_LABEL (label
) || DECL_NONLOCAL (label
))
133 LABEL_PRESERVE_P (r
) = 1;
136 return DECL_RTL (label
);
139 /* As above, but also put it on the forced-reference list of the
140 function that contains it. */
142 force_label_rtx (tree label
)
144 rtx ref
= label_rtx (label
);
145 tree function
= decl_function_context (label
);
147 gcc_assert (function
);
149 forced_labels
= gen_rtx_EXPR_LIST (VOIDmode
, ref
, forced_labels
);
153 /* Add an unconditional jump to LABEL as the next sequential instruction. */
156 emit_jump (rtx label
)
158 do_pending_stack_adjust ();
159 emit_jump_insn (gen_jump (label
));
163 /* Handle goto statements and the labels that they can go to. */
165 /* Specify the location in the RTL code of a label LABEL,
166 which is a LABEL_DECL tree node.
168 This is used for the kind of label that the user can jump to with a
169 goto statement, and for alternatives of a switch or case statement.
170 RTL labels generated for loops and conditionals don't go through here;
171 they are generated directly at the RTL level, by other functions below.
173 Note that this has nothing to do with defining label *names*.
174 Languages vary in how they do that and what that even means. */
177 expand_label (tree label
)
179 rtx label_r
= label_rtx (label
);
181 do_pending_stack_adjust ();
182 emit_label (label_r
);
183 if (DECL_NAME (label
))
184 LABEL_NAME (DECL_RTL (label
)) = IDENTIFIER_POINTER (DECL_NAME (label
));
186 if (DECL_NONLOCAL (label
))
188 expand_builtin_setjmp_receiver (NULL
);
189 nonlocal_goto_handler_labels
190 = gen_rtx_EXPR_LIST (VOIDmode
, label_r
,
191 nonlocal_goto_handler_labels
);
194 if (FORCED_LABEL (label
))
195 forced_labels
= gen_rtx_EXPR_LIST (VOIDmode
, label_r
, forced_labels
);
197 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
198 maybe_set_first_label_num (label_r
);
201 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
202 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
203 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
204 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
205 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
206 constraint allows the use of a register operand. And, *IS_INOUT
207 will be true if the operand is read-write, i.e., if it is used as
208 an input as well as an output. If *CONSTRAINT_P is not in
209 canonical form, it will be made canonical. (Note that `+' will be
210 replaced with `=' as part of this process.)
212 Returns TRUE if all went well; FALSE if an error occurred. */
215 parse_output_constraint (const char **constraint_p
, int operand_num
,
216 int ninputs
, int noutputs
, bool *allows_mem
,
217 bool *allows_reg
, bool *is_inout
)
219 const char *constraint
= *constraint_p
;
222 /* Assume the constraint doesn't allow the use of either a register
227 /* Allow the `=' or `+' to not be at the beginning of the string,
228 since it wasn't explicitly documented that way, and there is a
229 large body of code that puts it last. Swap the character to
230 the front, so as not to uglify any place else. */
231 p
= strchr (constraint
, '=');
233 p
= strchr (constraint
, '+');
235 /* If the string doesn't contain an `=', issue an error
239 error ("output operand constraint lacks %<=%>");
243 /* If the constraint begins with `+', then the operand is both read
244 from and written to. */
245 *is_inout
= (*p
== '+');
247 /* Canonicalize the output constraint so that it begins with `='. */
248 if (p
!= constraint
|| *is_inout
)
251 size_t c_len
= strlen (constraint
);
254 warning (0, "output constraint %qc for operand %d "
255 "is not at the beginning",
258 /* Make a copy of the constraint. */
259 buf
= XALLOCAVEC (char, c_len
+ 1);
260 strcpy (buf
, constraint
);
261 /* Swap the first character and the `=' or `+'. */
262 buf
[p
- constraint
] = buf
[0];
263 /* Make sure the first character is an `='. (Until we do this,
264 it might be a `+'.) */
266 /* Replace the constraint with the canonicalized string. */
267 *constraint_p
= ggc_alloc_string (buf
, c_len
);
268 constraint
= *constraint_p
;
271 /* Loop through the constraint string. */
272 for (p
= constraint
+ 1; *p
; p
+= CONSTRAINT_LEN (*p
, p
))
277 error ("operand constraint contains incorrectly positioned "
282 if (operand_num
+ 1 == ninputs
+ noutputs
)
284 error ("%<%%%> constraint used with last operand");
289 case 'V': case TARGET_MEM_CONSTRAINT
: case 'o':
293 case '?': case '!': case '*': case '&': case '#':
294 case 'E': case 'F': case 'G': case 'H':
295 case 's': case 'i': case 'n':
296 case 'I': case 'J': case 'K': case 'L': case 'M':
297 case 'N': case 'O': case 'P': case ',':
300 case '0': case '1': case '2': case '3': case '4':
301 case '5': case '6': case '7': case '8': case '9':
303 error ("matching constraint not valid in output operand");
307 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
308 excepting those that expand_call created. So match memory
325 enum constraint_num cn
= lookup_constraint (p
);
326 if (reg_class_for_constraint (cn
) != NO_REGS
327 || insn_extra_address_constraint (cn
))
329 else if (insn_extra_memory_constraint (cn
))
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. */
345 /* Similar, but for input constraints. */
348 parse_input_constraint (const char **constraint_p
, int input_num
,
349 int ninputs
, int noutputs
, int ninout
,
350 const char * const * constraints
,
351 bool *allows_mem
, bool *allows_reg
)
353 const char *constraint
= *constraint_p
;
354 const char *orig_constraint
= constraint
;
355 size_t c_len
= strlen (constraint
);
357 bool saw_match
= false;
359 /* Assume the constraint doesn't allow the use of either
360 a register or memory. */
364 /* Make sure constraint has neither `=', `+', nor '&'. */
366 for (j
= 0; j
< c_len
; j
+= CONSTRAINT_LEN (constraint
[j
], constraint
+j
))
367 switch (constraint
[j
])
369 case '+': case '=': case '&':
370 if (constraint
== orig_constraint
)
372 error ("input operand constraint contains %qc", constraint
[j
]);
378 if (constraint
== orig_constraint
379 && input_num
+ 1 == ninputs
- ninout
)
381 error ("%<%%%> constraint used with last operand");
386 case 'V': case TARGET_MEM_CONSTRAINT
: case 'o':
391 case '?': case '!': case '*': case '#':
392 case 'E': case 'F': case 'G': case 'H':
393 case 's': case 'i': case 'n':
394 case 'I': case 'J': case 'K': case 'L': case 'M':
395 case 'N': case 'O': case 'P': case ',':
398 /* Whether or not a numeric constraint allows a register is
399 decided by the matching constraint, and so there is no need
400 to do anything special with them. We must handle them in
401 the default case, so that we don't unnecessarily force
402 operands to memory. */
403 case '0': case '1': case '2': case '3': case '4':
404 case '5': case '6': case '7': case '8': case '9':
411 match
= strtoul (constraint
+ j
, &end
, 10);
412 if (match
>= (unsigned long) noutputs
)
414 error ("matching constraint references invalid operand number");
418 /* Try and find the real constraint for this dup. Only do this
419 if the matching constraint is the only alternative. */
421 && (j
== 0 || (j
== 1 && constraint
[0] == '%')))
423 constraint
= constraints
[match
];
424 *constraint_p
= constraint
;
425 c_len
= strlen (constraint
);
427 /* ??? At the end of the loop, we will skip the first part of
428 the matched constraint. This assumes not only that the
429 other constraint is an output constraint, but also that
430 the '=' or '+' come first. */
434 j
= end
- constraint
;
435 /* Anticipate increment at end of loop. */
450 if (! ISALPHA (constraint
[j
]))
452 error ("invalid punctuation %qc in constraint", constraint
[j
]);
455 enum constraint_num cn
= lookup_constraint (constraint
+ j
);
456 if (reg_class_for_constraint (cn
) != NO_REGS
457 || insn_extra_address_constraint (cn
))
459 else if (insn_extra_memory_constraint (cn
))
463 /* Otherwise we can't assume anything about the nature of
464 the constraint except that it isn't purely registers.
465 Treat it like "g" and hope for the best. */
472 if (saw_match
&& !*allows_reg
)
473 warning (0, "matching constraint does not allow a register");
478 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
479 can be an asm-declared register. Called via walk_tree. */
482 decl_overlaps_hard_reg_set_p (tree
*declp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
486 const HARD_REG_SET
*const regs
= (const HARD_REG_SET
*) data
;
488 if (TREE_CODE (decl
) == VAR_DECL
)
490 if (DECL_HARD_REGISTER (decl
)
491 && REG_P (DECL_RTL (decl
))
492 && REGNO (DECL_RTL (decl
)) < FIRST_PSEUDO_REGISTER
)
494 rtx reg
= DECL_RTL (decl
);
496 if (overlaps_hard_reg_set_p (*regs
, GET_MODE (reg
), REGNO (reg
)))
501 else if (TYPE_P (decl
) || TREE_CODE (decl
) == PARM_DECL
)
506 /* If there is an overlap between *REGS and DECL, return the first overlap
509 tree_overlaps_hard_reg_set (tree decl
, HARD_REG_SET
*regs
)
511 return walk_tree (&decl
, decl_overlaps_hard_reg_set_p
, regs
, NULL
);
515 /* A subroutine of expand_asm_operands. Check that all operand names
516 are unique. Return true if so. We rely on the fact that these names
517 are identifiers, and so have been canonicalized by get_identifier,
518 so all we need are pointer comparisons. */
521 check_unique_operand_names (tree outputs
, tree inputs
, tree labels
)
523 tree i
, j
, i_name
= NULL_TREE
;
525 for (i
= outputs
; i
; i
= TREE_CHAIN (i
))
527 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
531 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
532 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
536 for (i
= inputs
; i
; i
= TREE_CHAIN (i
))
538 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
542 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
543 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
545 for (j
= outputs
; j
; j
= TREE_CHAIN (j
))
546 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
550 for (i
= labels
; i
; i
= TREE_CHAIN (i
))
552 i_name
= TREE_PURPOSE (i
);
556 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
557 if (simple_cst_equal (i_name
, TREE_PURPOSE (j
)))
559 for (j
= inputs
; j
; j
= TREE_CHAIN (j
))
560 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
567 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name
));
571 /* A subroutine of expand_asm_operands. Resolve the names of the operands
572 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
573 STRING and in the constraints to those numbers. */
576 resolve_asm_operand_names (tree string
, tree outputs
, tree inputs
, tree labels
)
583 check_unique_operand_names (outputs
, inputs
, labels
);
585 /* Substitute [<name>] in input constraint strings. There should be no
586 named operands in output constraints. */
587 for (t
= inputs
; t
; t
= TREE_CHAIN (t
))
589 c
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
590 if (strchr (c
, '[') != NULL
)
592 p
= buffer
= xstrdup (c
);
593 while ((p
= strchr (p
, '[')) != NULL
)
594 p
= resolve_operand_name_1 (p
, outputs
, inputs
, NULL
);
595 TREE_VALUE (TREE_PURPOSE (t
))
596 = build_string (strlen (buffer
), buffer
);
601 /* Now check for any needed substitutions in the template. */
602 c
= TREE_STRING_POINTER (string
);
603 while ((c
= strchr (c
, '%')) != NULL
)
607 else if (ISALPHA (c
[1]) && c
[2] == '[')
611 c
+= 1 + (c
[1] == '%');
618 /* OK, we need to make a copy so we can perform the substitutions.
619 Assume that we will not need extra space--we get to remove '['
620 and ']', which means we cannot have a problem until we have more
621 than 999 operands. */
622 buffer
= xstrdup (TREE_STRING_POINTER (string
));
623 p
= buffer
+ (c
- TREE_STRING_POINTER (string
));
625 while ((p
= strchr (p
, '%')) != NULL
)
629 else if (ISALPHA (p
[1]) && p
[2] == '[')
633 p
+= 1 + (p
[1] == '%');
637 p
= resolve_operand_name_1 (p
, outputs
, inputs
, labels
);
640 string
= build_string (strlen (buffer
), buffer
);
647 /* A subroutine of resolve_operand_names. P points to the '[' for a
648 potential named operand of the form [<name>]. In place, replace
649 the name and brackets with a number. Return a pointer to the
650 balance of the string after substitution. */
653 resolve_operand_name_1 (char *p
, tree outputs
, tree inputs
, tree labels
)
659 /* Collect the operand name. */
660 q
= strchr (++p
, ']');
663 error ("missing close brace for named operand");
664 return strchr (p
, '\0');
668 /* Resolve the name to a number. */
669 for (op
= 0, t
= outputs
; t
; t
= TREE_CHAIN (t
), op
++)
671 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
672 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
675 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), op
++)
677 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
678 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
681 for (t
= labels
; t
; t
= TREE_CHAIN (t
), op
++)
683 tree name
= TREE_PURPOSE (t
);
684 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
688 error ("undefined named operand %qs", identifier_to_locale (p
));
692 /* Replace the name with the number. Unfortunately, not all libraries
693 get the return value of sprintf correct, so search for the end of the
694 generated string by hand. */
695 sprintf (--p
, "%d", op
);
696 p
= strchr (p
, '\0');
698 /* Verify the no extra buffer space assumption. */
701 /* Shift the rest of the buffer down to fill the gap. */
702 memmove (p
, q
+ 1, strlen (q
+ 1) + 1);
708 /* Generate RTL to return directly from the current function.
709 (That is, we bypass any return value.) */
712 expand_naked_return (void)
716 clear_pending_stack_adjust ();
717 do_pending_stack_adjust ();
719 end_label
= naked_return_label
;
721 end_label
= naked_return_label
= gen_label_rtx ();
723 emit_jump (end_label
);
726 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
727 is the probability of jumping to LABEL. */
729 do_jump_if_equal (enum machine_mode mode
, rtx op0
, rtx op1
, rtx label
,
730 int unsignedp
, int prob
)
732 gcc_assert (prob
<= REG_BR_PROB_BASE
);
733 do_compare_rtx_and_jump (op0
, op1
, EQ
, unsignedp
, mode
,
734 NULL_RTX
, NULL_RTX
, label
, prob
);
737 /* Do the insertion of a case label into case_list. The labels are
738 fed to us in descending order from the sorted vector of case labels used
739 in the tree part of the middle end. So the list we construct is
740 sorted in ascending order.
742 LABEL is the case label to be inserted. LOW and HIGH are the bounds
743 against which the index is compared to jump to LABEL and PROB is the
744 estimated probability LABEL is reached from the switch statement. */
746 static struct case_node
*
747 add_case_node (struct case_node
*head
, tree low
, tree high
,
748 tree label
, int prob
, alloc_pool case_node_pool
)
752 gcc_checking_assert (low
);
753 gcc_checking_assert (high
&& (TREE_TYPE (low
) == TREE_TYPE (high
)));
755 /* Add this label to the chain. */
756 r
= (struct case_node
*) pool_alloc (case_node_pool
);
759 r
->code_label
= label
;
760 r
->parent
= r
->left
= NULL
;
762 r
->subtree_prob
= prob
;
767 /* Dump ROOT, a list or tree of case nodes, to file. */
770 dump_case_nodes (FILE *f
, struct case_node
*root
,
771 int indent_step
, int indent_level
)
777 dump_case_nodes (f
, root
->left
, indent_step
, indent_level
);
780 fprintf (f
, "%*s", indent_step
* indent_level
, "");
781 print_dec (root
->low
, f
, TYPE_SIGN (TREE_TYPE (root
->low
)));
782 if (!tree_int_cst_equal (root
->low
, root
->high
))
784 fprintf (f
, " ... ");
785 print_dec (root
->high
, f
, TYPE_SIGN (TREE_TYPE (root
->high
)));
789 dump_case_nodes (f
, root
->right
, indent_step
, indent_level
);
793 #define HAVE_casesi 0
796 #ifndef HAVE_tablejump
797 #define HAVE_tablejump 0
800 /* Return the smallest number of different values for which it is best to use a
801 jump-table instead of a tree of conditional branches. */
804 case_values_threshold (void)
806 unsigned int threshold
= PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD
);
809 threshold
= targetm
.case_values_threshold ();
814 /* Return true if a switch should be expanded as a decision tree.
815 RANGE is the difference between highest and lowest case.
816 UNIQ is number of unique case node targets, not counting the default case.
817 COUNT is the number of comparisons needed, not counting the default case. */
820 expand_switch_as_decision_tree_p (tree range
,
821 unsigned int uniq ATTRIBUTE_UNUSED
,
826 /* If neither casesi or tablejump is available, or flag_jump_tables
827 over-ruled us, we really have no choice. */
828 if (!HAVE_casesi
&& !HAVE_tablejump
)
830 if (!flag_jump_tables
)
832 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
837 /* If the switch is relatively small such that the cost of one
838 indirect jump on the target are higher than the cost of a
839 decision tree, go with the decision tree.
841 If range of values is much bigger than number of values,
842 or if it is too large to represent in a HOST_WIDE_INT,
843 make a sequence of conditional branches instead of a dispatch.
845 The definition of "much bigger" depends on whether we are
846 optimizing for size or for speed. If the former, the maximum
847 ratio range/count = 3, because this was found to be the optimal
848 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
849 10 is much older, and was probably selected after an extensive
850 benchmarking investigation on numerous platforms. Or maybe it
851 just made sense to someone at some point in the history of GCC,
853 max_ratio
= optimize_insn_for_size_p () ? 3 : 10;
854 if (count
< case_values_threshold ()
855 || ! tree_fits_uhwi_p (range
)
856 || compare_tree_int (range
, max_ratio
* count
) > 0)
862 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
863 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
864 DEFAULT_PROB is the estimated probability that it jumps to
867 We generate a binary decision tree to select the appropriate target
868 code. This is done as follows:
870 If the index is a short or char that we do not have
871 an insn to handle comparisons directly, convert it to
872 a full integer now, rather than letting each comparison
873 generate the conversion.
875 Load the index into a register.
877 The list of cases is rearranged into a binary tree,
878 nearly optimal assuming equal probability for each case.
880 The tree is transformed into RTL, eliminating redundant
881 test conditions at the same time.
883 If program flow could reach the end of the decision tree
884 an unconditional jump to the default code is emitted.
886 The above process is unaware of the CFG. The caller has to fix up
887 the CFG itself. This is done in cfgexpand.c. */
890 emit_case_decision_tree (tree index_expr
, tree index_type
,
891 struct case_node
*case_list
, rtx default_label
,
894 rtx index
= expand_normal (index_expr
);
896 if (GET_MODE_CLASS (GET_MODE (index
)) == MODE_INT
897 && ! have_insn_for (COMPARE
, GET_MODE (index
)))
899 int unsignedp
= TYPE_UNSIGNED (index_type
);
900 enum machine_mode wider_mode
;
901 for (wider_mode
= GET_MODE (index
); wider_mode
!= VOIDmode
;
902 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
903 if (have_insn_for (COMPARE
, wider_mode
))
905 index
= convert_to_mode (wider_mode
, index
, unsignedp
);
910 do_pending_stack_adjust ();
914 index
= copy_to_reg (index
);
915 if (TREE_CODE (index_expr
) == SSA_NAME
)
916 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr
), index
);
919 balance_case_nodes (&case_list
, NULL
);
921 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
923 int indent_step
= ceil_log2 (TYPE_PRECISION (index_type
)) + 2;
924 fprintf (dump_file
, ";; Expanding GIMPLE switch as decision tree:\n");
925 dump_case_nodes (dump_file
, case_list
, indent_step
, 0);
928 emit_case_nodes (index
, case_list
, default_label
, default_prob
, index_type
);
930 emit_jump (default_label
);
933 /* Return the sum of probabilities of outgoing edges of basic block BB. */
936 get_outgoing_edge_probs (basic_block bb
)
943 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
944 prob_sum
+= e
->probability
;
948 /* Computes the conditional probability of jumping to a target if the branch
949 instruction is executed.
950 TARGET_PROB is the estimated probability of jumping to a target relative
951 to some basic block BB.
952 BASE_PROB is the probability of reaching the branch instruction relative
953 to the same basic block BB. */
956 conditional_probability (int target_prob
, int base_prob
)
960 gcc_assert (target_prob
>= 0);
961 gcc_assert (target_prob
<= base_prob
);
962 return GCOV_COMPUTE_SCALE (target_prob
, base_prob
);
967 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
968 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
969 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
970 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
972 First, a jump insn is emitted. First we try "casesi". If that
973 fails, try "tablejump". A target *must* have one of them (or both).
975 Then, a table with the target labels is emitted.
977 The process is unaware of the CFG. The caller has to fix up
978 the CFG itself. This is done in cfgexpand.c. */
981 emit_case_dispatch_table (tree index_expr
, tree index_type
,
982 struct case_node
*case_list
, rtx default_label
,
983 tree minval
, tree maxval
, tree range
,
989 rtx fallback_label
= label_rtx (case_list
->code_label
);
990 rtx table_label
= gen_label_rtx ();
991 bool has_gaps
= false;
992 edge default_edge
= stmt_bb
? EDGE_SUCC (stmt_bb
, 0) : NULL
;
993 int default_prob
= default_edge
? default_edge
->probability
: 0;
994 int base
= get_outgoing_edge_probs (stmt_bb
);
995 bool try_with_tablejump
= false;
997 int new_default_prob
= conditional_probability (default_prob
,
1000 if (! try_casesi (index_type
, index_expr
, minval
, range
,
1001 table_label
, default_label
, fallback_label
,
1004 /* Index jumptables from zero for suitable values of minval to avoid
1005 a subtraction. For the rationale see:
1006 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
1007 if (optimize_insn_for_speed_p ()
1008 && compare_tree_int (minval
, 0) > 0
1009 && compare_tree_int (minval
, 3) < 0)
1011 minval
= build_int_cst (index_type
, 0);
1015 try_with_tablejump
= true;
1018 /* Get table of labels to jump to, in order of case index. */
1020 ncases
= tree_to_shwi (range
) + 1;
1021 labelvec
= XALLOCAVEC (rtx
, ncases
);
1022 memset (labelvec
, 0, ncases
* sizeof (rtx
));
1024 for (n
= case_list
; n
; n
= n
->right
)
1026 /* Compute the low and high bounds relative to the minimum
1027 value since that should fit in a HOST_WIDE_INT while the
1028 actual values may not. */
1030 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1032 HOST_WIDE_INT i_high
1033 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1037 for (i
= i_low
; i
<= i_high
; i
++)
1039 = gen_rtx_LABEL_REF (Pmode
, label_rtx (n
->code_label
));
1042 /* Fill in the gaps with the default. We may have gaps at
1043 the beginning if we tried to avoid the minval subtraction,
1044 so substitute some label even if the default label was
1045 deemed unreachable. */
1047 default_label
= fallback_label
;
1048 for (i
= 0; i
< ncases
; i
++)
1049 if (labelvec
[i
] == 0)
1052 labelvec
[i
] = gen_rtx_LABEL_REF (Pmode
, default_label
);
1057 /* There is at least one entry in the jump table that jumps
1058 to default label. The default label can either be reached
1059 through the indirect jump or the direct conditional jump
1060 before that. Split the probability of reaching the
1061 default label among these two jumps. */
1062 new_default_prob
= conditional_probability (default_prob
/2,
1065 base
-= default_prob
;
1069 base
-= default_prob
;
1074 default_edge
->probability
= default_prob
;
1076 /* We have altered the probability of the default edge. So the probabilities
1077 of all other edges need to be adjusted so that it sums up to
1078 REG_BR_PROB_BASE. */
1083 FOR_EACH_EDGE (e
, ei
, stmt_bb
->succs
)
1084 e
->probability
= GCOV_COMPUTE_SCALE (e
->probability
, base
);
1087 if (try_with_tablejump
)
1089 bool ok
= try_tablejump (index_type
, index_expr
, minval
, range
,
1090 table_label
, default_label
, new_default_prob
);
1093 /* Output the table. */
1094 emit_label (table_label
);
1096 if (CASE_VECTOR_PC_RELATIVE
|| flag_pic
)
1097 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE
,
1098 gen_rtx_LABEL_REF (Pmode
,
1100 gen_rtvec_v (ncases
, labelvec
),
1101 const0_rtx
, const0_rtx
));
1103 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE
,
1104 gen_rtvec_v (ncases
, labelvec
)));
1106 /* Record no drop-through after the table. */
1110 /* Reset the aux field of all outgoing edges of basic block BB. */
1113 reset_out_edges_aux (basic_block bb
)
1117 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1121 /* Compute the number of case labels that correspond to each outgoing edge of
1122 STMT. Record this information in the aux field of the edge. */
1125 compute_cases_per_edge (gimple stmt
)
1127 basic_block bb
= gimple_bb (stmt
);
1128 reset_out_edges_aux (bb
);
1129 int ncases
= gimple_switch_num_labels (stmt
);
1130 for (int i
= ncases
- 1; i
>= 1; --i
)
1132 tree elt
= gimple_switch_label (stmt
, i
);
1133 tree lab
= CASE_LABEL (elt
);
1134 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1135 edge case_edge
= find_edge (bb
, case_bb
);
1136 case_edge
->aux
= (void *)((intptr_t)(case_edge
->aux
) + 1);
1140 /* Terminate a case (Pascal/Ada) or switch (C) statement
1141 in which ORIG_INDEX is the expression to be tested.
1142 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
1143 type as given in the source before any compiler conversions.
1144 Generate the code to test it and jump to the right place. */
1147 expand_case (gimple stmt
)
1149 tree minval
= NULL_TREE
, maxval
= NULL_TREE
, range
= NULL_TREE
;
1150 rtx default_label
= NULL_RTX
;
1151 unsigned int count
, uniq
;
1153 int ncases
= gimple_switch_num_labels (stmt
);
1154 tree index_expr
= gimple_switch_index (stmt
);
1155 tree index_type
= TREE_TYPE (index_expr
);
1157 basic_block bb
= gimple_bb (stmt
);
1159 /* A list of case labels; it is first built as a list and it may then
1160 be rearranged into a nearly balanced binary tree. */
1161 struct case_node
*case_list
= 0;
1163 /* A pool for case nodes. */
1164 alloc_pool case_node_pool
;
1166 /* An ERROR_MARK occurs for various reasons including invalid data type.
1167 ??? Can this still happen, with GIMPLE and all? */
1168 if (index_type
== error_mark_node
)
1171 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
1172 expressions being INTEGER_CST. */
1173 gcc_assert (TREE_CODE (index_expr
) != INTEGER_CST
);
1175 case_node_pool
= create_alloc_pool ("struct case_node pool",
1176 sizeof (struct case_node
),
1179 do_pending_stack_adjust ();
1181 /* Find the default case target label. */
1182 default_label
= label_rtx (CASE_LABEL (gimple_switch_default_label (stmt
)));
1183 edge default_edge
= EDGE_SUCC (bb
, 0);
1184 int default_prob
= default_edge
->probability
;
1186 /* Get upper and lower bounds of case values. */
1187 elt
= gimple_switch_label (stmt
, 1);
1188 minval
= fold_convert (index_type
, CASE_LOW (elt
));
1189 elt
= gimple_switch_label (stmt
, ncases
- 1);
1190 if (CASE_HIGH (elt
))
1191 maxval
= fold_convert (index_type
, CASE_HIGH (elt
));
1193 maxval
= fold_convert (index_type
, CASE_LOW (elt
));
1195 /* Compute span of values. */
1196 range
= fold_build2 (MINUS_EXPR
, index_type
, maxval
, minval
);
1198 /* Listify the labels queue and gather some numbers to decide
1199 how to expand this switch(). */
1202 struct pointer_set_t
*seen_labels
= pointer_set_create ();
1203 compute_cases_per_edge (stmt
);
1205 for (i
= ncases
- 1; i
>= 1; --i
)
1207 elt
= gimple_switch_label (stmt
, i
);
1208 tree low
= CASE_LOW (elt
);
1210 tree high
= CASE_HIGH (elt
);
1211 gcc_assert (! high
|| tree_int_cst_lt (low
, high
));
1212 tree lab
= CASE_LABEL (elt
);
1214 /* Count the elements.
1215 A range counts double, since it requires two compares. */
1220 /* If we have not seen this label yet, then increase the
1221 number of unique case node targets seen. */
1222 if (!pointer_set_insert (seen_labels
, lab
))
1225 /* The bounds on the case range, LOW and HIGH, have to be converted
1226 to case's index type TYPE. Note that the original type of the
1227 case index in the source code is usually "lost" during
1228 gimplification due to type promotion, but the case labels retain the
1229 original type. Make sure to drop overflow flags. */
1230 low
= fold_convert (index_type
, low
);
1231 if (TREE_OVERFLOW (low
))
1232 low
= wide_int_to_tree (index_type
, low
);
1234 /* The canonical from of a case label in GIMPLE is that a simple case
1235 has an empty CASE_HIGH. For the casesi and tablejump expanders,
1236 the back ends want simple cases to have high == low. */
1239 high
= fold_convert (index_type
, high
);
1240 if (TREE_OVERFLOW (high
))
1241 high
= wide_int_to_tree (index_type
, high
);
1243 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1244 edge case_edge
= find_edge (bb
, case_bb
);
1245 case_list
= add_case_node (
1246 case_list
, low
, high
, lab
,
1247 case_edge
->probability
/ (intptr_t)(case_edge
->aux
),
1250 pointer_set_destroy (seen_labels
);
1251 reset_out_edges_aux (bb
);
1253 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
1254 destination, such as one with a default case only.
1255 It also removes cases that are out of range for the switch
1256 type, so we should never get a zero here. */
1257 gcc_assert (count
> 0);
1259 rtx before_case
= get_last_insn ();
1261 /* Decide how to expand this switch.
1262 The two options at this point are a dispatch table (casesi or
1263 tablejump) or a decision tree. */
1265 if (expand_switch_as_decision_tree_p (range
, uniq
, count
))
1266 emit_case_decision_tree (index_expr
, index_type
,
1267 case_list
, default_label
,
1270 emit_case_dispatch_table (index_expr
, index_type
,
1271 case_list
, default_label
,
1272 minval
, maxval
, range
, bb
);
1274 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1277 free_alloc_pool (case_node_pool
);
1280 /* Expand the dispatch to a short decrement chain if there are few cases
1281 to dispatch to. Likewise if neither casesi nor tablejump is available,
1282 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
1283 tablejump. The index mode is always the mode of integer_type_node.
1284 Trap if no case matches the index.
1286 DISPATCH_INDEX is the index expression to switch on. It should be a
1287 memory or register operand.
1289 DISPATCH_TABLE is a set of case labels. The set should be sorted in
1290 ascending order, be contiguous, starting with value 0, and contain only
1291 single-valued case labels. */
1294 expand_sjlj_dispatch_table (rtx dispatch_index
,
1295 vec
<tree
> dispatch_table
)
1297 tree index_type
= integer_type_node
;
1298 enum machine_mode index_mode
= TYPE_MODE (index_type
);
1300 int ncases
= dispatch_table
.length ();
1302 do_pending_stack_adjust ();
1303 rtx before_case
= get_last_insn ();
1305 /* Expand as a decrement-chain if there are 5 or fewer dispatch
1306 labels. This covers more than 98% of the cases in libjava,
1307 and seems to be a reasonable compromise between the "old way"
1308 of expanding as a decision tree or dispatch table vs. the "new
1309 way" with decrement chain or dispatch table. */
1310 if (dispatch_table
.length () <= 5
1311 || (!HAVE_casesi
&& !HAVE_tablejump
)
1312 || !flag_jump_tables
)
1314 /* Expand the dispatch as a decrement chain:
1316 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1320 if (index == 0) do_0; else index--;
1321 if (index == 0) do_1; else index--;
1323 if (index == 0) do_N; else index--;
1325 This is more efficient than a dispatch table on most machines.
1326 The last "index--" is redundant but the code is trivially dead
1327 and will be cleaned up by later passes. */
1328 rtx index
= copy_to_mode_reg (index_mode
, dispatch_index
);
1329 rtx zero
= CONST0_RTX (index_mode
);
1330 for (int i
= 0; i
< ncases
; i
++)
1332 tree elt
= dispatch_table
[i
];
1333 rtx lab
= label_rtx (CASE_LABEL (elt
));
1334 do_jump_if_equal (index_mode
, index
, zero
, lab
, 0, -1);
1335 force_expand_binop (index_mode
, sub_optab
,
1336 index
, CONST1_RTX (index_mode
),
1337 index
, 0, OPTAB_DIRECT
);
1342 /* Similar to expand_case, but much simpler. */
1343 struct case_node
*case_list
= 0;
1344 alloc_pool case_node_pool
= create_alloc_pool ("struct sjlj_case pool",
1345 sizeof (struct case_node
),
1347 tree index_expr
= make_tree (index_type
, dispatch_index
);
1348 tree minval
= build_int_cst (index_type
, 0);
1349 tree maxval
= CASE_LOW (dispatch_table
.last ());
1350 tree range
= maxval
;
1351 rtx default_label
= gen_label_rtx ();
1353 for (int i
= ncases
- 1; i
>= 0; --i
)
1355 tree elt
= dispatch_table
[i
];
1356 tree low
= CASE_LOW (elt
);
1357 tree lab
= CASE_LABEL (elt
);
1358 case_list
= add_case_node (case_list
, low
, low
, lab
, 0, case_node_pool
);
1361 emit_case_dispatch_table (index_expr
, index_type
,
1362 case_list
, default_label
,
1363 minval
, maxval
, range
,
1364 BLOCK_FOR_INSN (before_case
));
1365 emit_label (default_label
);
1366 free_alloc_pool (case_node_pool
);
1369 /* Dispatching something not handled? Trap! */
1370 expand_builtin_trap ();
1372 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1378 /* Take an ordered list of case nodes
1379 and transform them into a near optimal binary tree,
1380 on the assumption that any target code selection value is as
1381 likely as any other.
1383 The transformation is performed by splitting the ordered
1384 list into two equal sections plus a pivot. The parts are
1385 then attached to the pivot as left and right branches. Each
1386 branch is then transformed recursively. */
1389 balance_case_nodes (case_node_ptr
*head
, case_node_ptr parent
)
1401 /* Count the number of entries on branch. Also count the ranges. */
1405 if (!tree_int_cst_equal (np
->low
, np
->high
))
1414 /* Split this list if it is long enough for that to help. */
1418 /* If there are just three nodes, split at the middle one. */
1420 npp
= &(*npp
)->right
;
1423 /* Find the place in the list that bisects the list's total cost,
1424 where ranges count as 2.
1425 Here I gets half the total cost. */
1426 i
= (i
+ ranges
+ 1) / 2;
1429 /* Skip nodes while their cost does not reach that amount. */
1430 if (!tree_int_cst_equal ((*npp
)->low
, (*npp
)->high
))
1435 npp
= &(*npp
)->right
;
1440 np
->parent
= parent
;
1443 /* Optimize each of the two split parts. */
1444 balance_case_nodes (&np
->left
, np
);
1445 balance_case_nodes (&np
->right
, np
);
1446 np
->subtree_prob
= np
->prob
;
1447 np
->subtree_prob
+= np
->left
->subtree_prob
;
1448 np
->subtree_prob
+= np
->right
->subtree_prob
;
1452 /* Else leave this branch as one level,
1453 but fill in `parent' fields. */
1455 np
->parent
= parent
;
1456 np
->subtree_prob
= np
->prob
;
1457 for (; np
->right
; np
= np
->right
)
1459 np
->right
->parent
= np
;
1460 (*head
)->subtree_prob
+= np
->right
->subtree_prob
;
1466 /* Search the parent sections of the case node tree
1467 to see if a test for the lower bound of NODE would be redundant.
1468 INDEX_TYPE is the type of the index expression.
1470 The instructions to generate the case decision tree are
1471 output in the same order as nodes are processed so it is
1472 known that if a parent node checks the range of the current
1473 node minus one that the current node is bounded at its lower
1474 span. Thus the test would be redundant. */
1477 node_has_low_bound (case_node_ptr node
, tree index_type
)
1480 case_node_ptr pnode
;
1482 /* If the lower bound of this node is the lowest value in the index type,
1483 we need not test it. */
1485 if (tree_int_cst_equal (node
->low
, TYPE_MIN_VALUE (index_type
)))
1488 /* If this node has a left branch, the value at the left must be less
1489 than that at this node, so it cannot be bounded at the bottom and
1490 we need not bother testing any further. */
1495 low_minus_one
= fold_build2 (MINUS_EXPR
, TREE_TYPE (node
->low
),
1497 build_int_cst (TREE_TYPE (node
->low
), 1));
1499 /* If the subtraction above overflowed, we can't verify anything.
1500 Otherwise, look for a parent that tests our value - 1. */
1502 if (! tree_int_cst_lt (low_minus_one
, node
->low
))
1505 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1506 if (tree_int_cst_equal (low_minus_one
, pnode
->high
))
1512 /* Search the parent sections of the case node tree
1513 to see if a test for the upper bound of NODE would be redundant.
1514 INDEX_TYPE is the type of the index expression.
1516 The instructions to generate the case decision tree are
1517 output in the same order as nodes are processed so it is
1518 known that if a parent node checks the range of the current
1519 node plus one that the current node is bounded at its upper
1520 span. Thus the test would be redundant. */
1523 node_has_high_bound (case_node_ptr node
, tree index_type
)
1526 case_node_ptr pnode
;
1528 /* If there is no upper bound, obviously no test is needed. */
1530 if (TYPE_MAX_VALUE (index_type
) == NULL
)
1533 /* If the upper bound of this node is the highest value in the type
1534 of the index expression, we need not test against it. */
1536 if (tree_int_cst_equal (node
->high
, TYPE_MAX_VALUE (index_type
)))
1539 /* If this node has a right branch, the value at the right must be greater
1540 than that at this node, so it cannot be bounded at the top and
1541 we need not bother testing any further. */
1546 high_plus_one
= fold_build2 (PLUS_EXPR
, TREE_TYPE (node
->high
),
1548 build_int_cst (TREE_TYPE (node
->high
), 1));
1550 /* If the addition above overflowed, we can't verify anything.
1551 Otherwise, look for a parent that tests our value + 1. */
1553 if (! tree_int_cst_lt (node
->high
, high_plus_one
))
1556 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1557 if (tree_int_cst_equal (high_plus_one
, pnode
->low
))
1563 /* Search the parent sections of the
1564 case node tree to see if both tests for the upper and lower
1565 bounds of NODE would be redundant. */
1568 node_is_bounded (case_node_ptr node
, tree index_type
)
1570 return (node_has_low_bound (node
, index_type
)
1571 && node_has_high_bound (node
, index_type
));
1575 /* Emit step-by-step code to select a case for the value of INDEX.
1576 The thus generated decision tree follows the form of the
1577 case-node binary tree NODE, whose nodes represent test conditions.
1578 INDEX_TYPE is the type of the index of the switch.
1580 Care is taken to prune redundant tests from the decision tree
1581 by detecting any boundary conditions already checked by
1582 emitted rtx. (See node_has_high_bound, node_has_low_bound
1583 and node_is_bounded, above.)
1585 Where the test conditions can be shown to be redundant we emit
1586 an unconditional jump to the target code. As a further
1587 optimization, the subordinates of a tree node are examined to
1588 check for bounded nodes. In this case conditional and/or
1589 unconditional jumps as a result of the boundary check for the
1590 current node are arranged to target the subordinates associated
1591 code for out of bound conditions on the current node.
1593 We can assume that when control reaches the code generated here,
1594 the index value has already been compared with the parents
1595 of this node, and determined to be on the same side of each parent
1596 as this node is. Thus, if this node tests for the value 51,
1597 and a parent tested for 52, we don't need to consider
1598 the possibility of a value greater than 51. If another parent
1599 tests for the value 50, then this node need not test anything. */
1602 emit_case_nodes (rtx index
, case_node_ptr node
, rtx default_label
,
1603 int default_prob
, tree index_type
)
1605 /* If INDEX has an unsigned type, we must make unsigned branches. */
1606 int unsignedp
= TYPE_UNSIGNED (index_type
);
1608 int prob
= node
->prob
, subtree_prob
= node
->subtree_prob
;
1609 enum machine_mode mode
= GET_MODE (index
);
1610 enum machine_mode imode
= TYPE_MODE (index_type
);
1612 /* Handle indices detected as constant during RTL expansion. */
1613 if (mode
== VOIDmode
)
1616 /* See if our parents have already tested everything for us.
1617 If they have, emit an unconditional jump for this node. */
1618 if (node_is_bounded (node
, index_type
))
1619 emit_jump (label_rtx (node
->code_label
));
1621 else if (tree_int_cst_equal (node
->low
, node
->high
))
1623 probability
= conditional_probability (prob
, subtree_prob
+ default_prob
);
1624 /* Node is single valued. First see if the index expression matches
1625 this node and then check our children, if any. */
1626 do_jump_if_equal (mode
, index
,
1627 convert_modes (mode
, imode
,
1628 expand_normal (node
->low
),
1630 label_rtx (node
->code_label
), unsignedp
, probability
);
1631 /* Since this case is taken at this point, reduce its weight from
1633 subtree_prob
-= prob
;
1634 if (node
->right
!= 0 && node
->left
!= 0)
1636 /* This node has children on both sides.
1637 Dispatch to one side or the other
1638 by comparing the index value with this node's value.
1639 If one subtree is bounded, check that one first,
1640 so we can avoid real branches in the tree. */
1642 if (node_is_bounded (node
->right
, index_type
))
1644 probability
= conditional_probability (
1646 subtree_prob
+ default_prob
);
1647 emit_cmp_and_jump_insns (index
,
1650 expand_normal (node
->high
),
1652 GT
, NULL_RTX
, mode
, unsignedp
,
1653 label_rtx (node
->right
->code_label
),
1655 emit_case_nodes (index
, node
->left
, default_label
, default_prob
,
1659 else if (node_is_bounded (node
->left
, index_type
))
1661 probability
= conditional_probability (
1663 subtree_prob
+ default_prob
);
1664 emit_cmp_and_jump_insns (index
,
1667 expand_normal (node
->high
),
1669 LT
, NULL_RTX
, mode
, unsignedp
,
1670 label_rtx (node
->left
->code_label
),
1672 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1675 /* If both children are single-valued cases with no
1676 children, finish up all the work. This way, we can save
1677 one ordered comparison. */
1678 else if (tree_int_cst_equal (node
->right
->low
, node
->right
->high
)
1679 && node
->right
->left
== 0
1680 && node
->right
->right
== 0
1681 && tree_int_cst_equal (node
->left
->low
, node
->left
->high
)
1682 && node
->left
->left
== 0
1683 && node
->left
->right
== 0)
1685 /* Neither node is bounded. First distinguish the two sides;
1686 then emit the code for one side at a time. */
1688 /* See if the value matches what the right hand side
1690 probability
= conditional_probability (
1692 subtree_prob
+ default_prob
);
1693 do_jump_if_equal (mode
, index
,
1694 convert_modes (mode
, imode
,
1695 expand_normal (node
->right
->low
),
1697 label_rtx (node
->right
->code_label
),
1698 unsignedp
, probability
);
1700 /* See if the value matches what the left hand side
1702 probability
= conditional_probability (
1704 subtree_prob
+ default_prob
);
1705 do_jump_if_equal (mode
, index
,
1706 convert_modes (mode
, imode
,
1707 expand_normal (node
->left
->low
),
1709 label_rtx (node
->left
->code_label
),
1710 unsignedp
, probability
);
1715 /* Neither node is bounded. First distinguish the two sides;
1716 then emit the code for one side at a time. */
1719 = build_decl (curr_insn_location (),
1720 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
1722 /* The default label could be reached either through the right
1723 subtree or the left subtree. Divide the probability
1725 probability
= conditional_probability (
1726 node
->right
->subtree_prob
+ default_prob
/2,
1727 subtree_prob
+ default_prob
);
1728 /* See if the value is on the right. */
1729 emit_cmp_and_jump_insns (index
,
1732 expand_normal (node
->high
),
1734 GT
, NULL_RTX
, mode
, unsignedp
,
1735 label_rtx (test_label
),
1739 /* Value must be on the left.
1740 Handle the left-hand subtree. */
1741 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1742 /* If left-hand subtree does nothing,
1745 emit_jump (default_label
);
1747 /* Code branches here for the right-hand subtree. */
1748 expand_label (test_label
);
1749 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1753 else if (node
->right
!= 0 && node
->left
== 0)
1755 /* Here we have a right child but no left so we issue a conditional
1756 branch to default and process the right child.
1758 Omit the conditional branch to default if the right child
1759 does not have any children and is single valued; it would
1760 cost too much space to save so little time. */
1762 if (node
->right
->right
|| node
->right
->left
1763 || !tree_int_cst_equal (node
->right
->low
, node
->right
->high
))
1765 if (!node_has_low_bound (node
, index_type
))
1767 probability
= conditional_probability (
1769 subtree_prob
+ default_prob
);
1770 emit_cmp_and_jump_insns (index
,
1773 expand_normal (node
->high
),
1775 LT
, NULL_RTX
, mode
, unsignedp
,
1781 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1785 probability
= conditional_probability (
1786 node
->right
->subtree_prob
,
1787 subtree_prob
+ default_prob
);
1788 /* We cannot process node->right normally
1789 since we haven't ruled out the numbers less than
1790 this node's value. So handle node->right explicitly. */
1791 do_jump_if_equal (mode
, index
,
1794 expand_normal (node
->right
->low
),
1796 label_rtx (node
->right
->code_label
), unsignedp
, probability
);
1800 else if (node
->right
== 0 && node
->left
!= 0)
1802 /* Just one subtree, on the left. */
1803 if (node
->left
->left
|| node
->left
->right
1804 || !tree_int_cst_equal (node
->left
->low
, node
->left
->high
))
1806 if (!node_has_high_bound (node
, index_type
))
1808 probability
= conditional_probability (
1810 subtree_prob
+ default_prob
);
1811 emit_cmp_and_jump_insns (index
,
1814 expand_normal (node
->high
),
1816 GT
, NULL_RTX
, mode
, unsignedp
,
1822 emit_case_nodes (index
, node
->left
, default_label
,
1823 default_prob
, index_type
);
1827 probability
= conditional_probability (
1828 node
->left
->subtree_prob
,
1829 subtree_prob
+ default_prob
);
1830 /* We cannot process node->left normally
1831 since we haven't ruled out the numbers less than
1832 this node's value. So handle node->left explicitly. */
1833 do_jump_if_equal (mode
, index
,
1836 expand_normal (node
->left
->low
),
1838 label_rtx (node
->left
->code_label
), unsignedp
, probability
);
1844 /* Node is a range. These cases are very similar to those for a single
1845 value, except that we do not start by testing whether this node
1846 is the one to branch to. */
1848 if (node
->right
!= 0 && node
->left
!= 0)
1850 /* Node has subtrees on both sides.
1851 If the right-hand subtree is bounded,
1852 test for it first, since we can go straight there.
1853 Otherwise, we need to make a branch in the control structure,
1854 then handle the two subtrees. */
1855 tree test_label
= 0;
1857 if (node_is_bounded (node
->right
, index_type
))
1859 /* Right hand node is fully bounded so we can eliminate any
1860 testing and branch directly to the target code. */
1861 probability
= conditional_probability (
1862 node
->right
->subtree_prob
,
1863 subtree_prob
+ default_prob
);
1864 emit_cmp_and_jump_insns (index
,
1867 expand_normal (node
->high
),
1869 GT
, NULL_RTX
, mode
, unsignedp
,
1870 label_rtx (node
->right
->code_label
),
1875 /* Right hand node requires testing.
1876 Branch to a label where we will handle it later. */
1878 test_label
= build_decl (curr_insn_location (),
1879 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
1880 probability
= conditional_probability (
1881 node
->right
->subtree_prob
+ default_prob
/2,
1882 subtree_prob
+ default_prob
);
1883 emit_cmp_and_jump_insns (index
,
1886 expand_normal (node
->high
),
1888 GT
, NULL_RTX
, mode
, unsignedp
,
1889 label_rtx (test_label
),
1894 /* Value belongs to this node or to the left-hand subtree. */
1896 probability
= conditional_probability (
1898 subtree_prob
+ default_prob
);
1899 emit_cmp_and_jump_insns (index
,
1902 expand_normal (node
->low
),
1904 GE
, NULL_RTX
, mode
, unsignedp
,
1905 label_rtx (node
->code_label
),
1908 /* Handle the left-hand subtree. */
1909 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1911 /* If right node had to be handled later, do that now. */
1915 /* If the left-hand subtree fell through,
1916 don't let it fall into the right-hand subtree. */
1918 emit_jump (default_label
);
1920 expand_label (test_label
);
1921 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1925 else if (node
->right
!= 0 && node
->left
== 0)
1927 /* Deal with values to the left of this node,
1928 if they are possible. */
1929 if (!node_has_low_bound (node
, index_type
))
1931 probability
= conditional_probability (
1933 subtree_prob
+ default_prob
);
1934 emit_cmp_and_jump_insns (index
,
1937 expand_normal (node
->low
),
1939 LT
, NULL_RTX
, mode
, unsignedp
,
1945 /* Value belongs to this node or to the right-hand subtree. */
1947 probability
= conditional_probability (
1949 subtree_prob
+ default_prob
);
1950 emit_cmp_and_jump_insns (index
,
1953 expand_normal (node
->high
),
1955 LE
, NULL_RTX
, mode
, unsignedp
,
1956 label_rtx (node
->code_label
),
1959 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1962 else if (node
->right
== 0 && node
->left
!= 0)
1964 /* Deal with values to the right of this node,
1965 if they are possible. */
1966 if (!node_has_high_bound (node
, index_type
))
1968 probability
= conditional_probability (
1970 subtree_prob
+ default_prob
);
1971 emit_cmp_and_jump_insns (index
,
1974 expand_normal (node
->high
),
1976 GT
, NULL_RTX
, mode
, unsignedp
,
1982 /* Value belongs to this node or to the left-hand subtree. */
1984 probability
= conditional_probability (
1986 subtree_prob
+ default_prob
);
1987 emit_cmp_and_jump_insns (index
,
1990 expand_normal (node
->low
),
1992 GE
, NULL_RTX
, mode
, unsignedp
,
1993 label_rtx (node
->code_label
),
1996 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
2001 /* Node has no children so we check low and high bounds to remove
2002 redundant tests. Only one of the bounds can exist,
2003 since otherwise this node is bounded--a case tested already. */
2004 int high_bound
= node_has_high_bound (node
, index_type
);
2005 int low_bound
= node_has_low_bound (node
, index_type
);
2007 if (!high_bound
&& low_bound
)
2009 probability
= conditional_probability (
2011 subtree_prob
+ default_prob
);
2012 emit_cmp_and_jump_insns (index
,
2015 expand_normal (node
->high
),
2017 GT
, NULL_RTX
, mode
, unsignedp
,
2022 else if (!low_bound
&& high_bound
)
2024 probability
= conditional_probability (
2026 subtree_prob
+ default_prob
);
2027 emit_cmp_and_jump_insns (index
,
2030 expand_normal (node
->low
),
2032 LT
, NULL_RTX
, mode
, unsignedp
,
2036 else if (!low_bound
&& !high_bound
)
2038 /* Widen LOW and HIGH to the same width as INDEX. */
2039 tree type
= lang_hooks
.types
.type_for_mode (mode
, unsignedp
);
2040 tree low
= build1 (CONVERT_EXPR
, type
, node
->low
);
2041 tree high
= build1 (CONVERT_EXPR
, type
, node
->high
);
2042 rtx low_rtx
, new_index
, new_bound
;
2044 /* Instead of doing two branches, emit one unsigned branch for
2045 (index-low) > (high-low). */
2046 low_rtx
= expand_expr (low
, NULL_RTX
, mode
, EXPAND_NORMAL
);
2047 new_index
= expand_simple_binop (mode
, MINUS
, index
, low_rtx
,
2048 NULL_RTX
, unsignedp
,
2050 new_bound
= expand_expr (fold_build2 (MINUS_EXPR
, type
,
2052 NULL_RTX
, mode
, EXPAND_NORMAL
);
2054 probability
= conditional_probability (
2056 subtree_prob
+ default_prob
);
2057 emit_cmp_and_jump_insns (new_index
, new_bound
, GT
, NULL_RTX
,
2058 mode
, 1, default_label
, probability
);
2061 emit_jump (label_rtx (node
->code_label
));