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"
44 #include "insn-config.h"
48 #include "diagnostic-core.h"
50 #include "langhooks.h"
55 #include "basic-block.h"
56 #include "tree-ssa-alias.h"
57 #include "internal-fn.h"
58 #include "gimple-expr.h"
62 #include "alloc-pool.h"
63 #include "pretty-print.h"
69 /* Functions and data structures for expanding case statements. */
71 /* Case label structure, used to hold info on labels within case
72 statements. We handle "range" labels; for a single-value label
73 as in C, the high and low limits are the same.
75 We start with a vector of case nodes sorted in ascending order, and
76 the default label as the last element in the vector. Before expanding
77 to RTL, we transform this vector into a list linked via the RIGHT
78 fields in the case_node struct. Nodes with higher case values are
81 Switch statements can be output in three forms. A branch table is
82 used if there are more than a few labels and the labels are dense
83 within the range between the smallest and largest case value. If a
84 branch table is used, no further manipulations are done with the case
87 The alternative to the use of a branch table is to generate a series
88 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
89 and PARENT fields to hold a binary tree. Initially the tree is
90 totally unbalanced, with everything on the right. We balance the tree
91 with nodes on the left having lower case values than the parent
92 and nodes on the right having higher values. We then output the tree
95 For very small, suitable switch statements, we can generate a series
96 of simple bit test and branches instead. */
100 struct case_node
*left
; /* Left son in binary tree */
101 struct case_node
*right
; /* Right son in binary tree; also node chain */
102 struct case_node
*parent
; /* Parent of node in binary tree */
103 tree low
; /* Lowest index value for this label */
104 tree high
; /* Highest index value for this label */
105 tree code_label
; /* Label to jump to when node matches */
106 int prob
; /* Probability of taking this case. */
107 /* Probability of reaching subtree rooted at this node */
111 typedef struct case_node case_node
;
112 typedef struct case_node
*case_node_ptr
;
114 extern basic_block
label_to_block_fn (struct function
*, tree
);
116 static bool check_unique_operand_names (tree
, tree
, tree
);
117 static char *resolve_operand_name_1 (char *, tree
, tree
, tree
);
118 static void balance_case_nodes (case_node_ptr
*, case_node_ptr
);
119 static int node_has_low_bound (case_node_ptr
, tree
);
120 static int node_has_high_bound (case_node_ptr
, tree
);
121 static int node_is_bounded (case_node_ptr
, tree
);
122 static void emit_case_nodes (rtx
, case_node_ptr
, rtx
, int, tree
);
124 /* Return the rtx-label that corresponds to a LABEL_DECL,
125 creating it if necessary. */
128 label_rtx (tree label
)
130 gcc_assert (TREE_CODE (label
) == LABEL_DECL
);
132 if (!DECL_RTL_SET_P (label
))
134 rtx_code_label
*r
= gen_label_rtx ();
135 SET_DECL_RTL (label
, r
);
136 if (FORCED_LABEL (label
) || DECL_NONLOCAL (label
))
137 LABEL_PRESERVE_P (r
) = 1;
140 return DECL_RTL (label
);
143 /* As above, but also put it on the forced-reference list of the
144 function that contains it. */
146 force_label_rtx (tree label
)
148 rtx_insn
*ref
= as_a
<rtx_insn
*> (label_rtx (label
));
149 tree function
= decl_function_context (label
);
151 gcc_assert (function
);
153 forced_labels
= gen_rtx_INSN_LIST (VOIDmode
, ref
, forced_labels
);
157 /* Add an unconditional jump to LABEL as the next sequential instruction. */
160 emit_jump (rtx label
)
162 do_pending_stack_adjust ();
163 emit_jump_insn (gen_jump (label
));
167 /* Handle goto statements and the labels that they can go to. */
169 /* Specify the location in the RTL code of a label LABEL,
170 which is a LABEL_DECL tree node.
172 This is used for the kind of label that the user can jump to with a
173 goto statement, and for alternatives of a switch or case statement.
174 RTL labels generated for loops and conditionals don't go through here;
175 they are generated directly at the RTL level, by other functions below.
177 Note that this has nothing to do with defining label *names*.
178 Languages vary in how they do that and what that even means. */
181 expand_label (tree label
)
183 rtx_insn
*label_r
= as_a
<rtx_insn
*> (label_rtx (label
));
185 do_pending_stack_adjust ();
186 emit_label (label_r
);
187 if (DECL_NAME (label
))
188 LABEL_NAME (DECL_RTL (label
)) = IDENTIFIER_POINTER (DECL_NAME (label
));
190 if (DECL_NONLOCAL (label
))
192 expand_builtin_setjmp_receiver (NULL
);
193 nonlocal_goto_handler_labels
194 = gen_rtx_INSN_LIST (VOIDmode
, label_r
,
195 nonlocal_goto_handler_labels
);
198 if (FORCED_LABEL (label
))
199 forced_labels
= gen_rtx_INSN_LIST (VOIDmode
, label_r
, forced_labels
);
201 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
202 maybe_set_first_label_num (label_r
);
205 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
206 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
207 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
208 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
209 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
210 constraint allows the use of a register operand. And, *IS_INOUT
211 will be true if the operand is read-write, i.e., if it is used as
212 an input as well as an output. If *CONSTRAINT_P is not in
213 canonical form, it will be made canonical. (Note that `+' will be
214 replaced with `=' as part of this process.)
216 Returns TRUE if all went well; FALSE if an error occurred. */
219 parse_output_constraint (const char **constraint_p
, int operand_num
,
220 int ninputs
, int noutputs
, bool *allows_mem
,
221 bool *allows_reg
, bool *is_inout
)
223 const char *constraint
= *constraint_p
;
226 /* Assume the constraint doesn't allow the use of either a register
231 /* Allow the `=' or `+' to not be at the beginning of the string,
232 since it wasn't explicitly documented that way, and there is a
233 large body of code that puts it last. Swap the character to
234 the front, so as not to uglify any place else. */
235 p
= strchr (constraint
, '=');
237 p
= strchr (constraint
, '+');
239 /* If the string doesn't contain an `=', issue an error
243 error ("output operand constraint lacks %<=%>");
247 /* If the constraint begins with `+', then the operand is both read
248 from and written to. */
249 *is_inout
= (*p
== '+');
251 /* Canonicalize the output constraint so that it begins with `='. */
252 if (p
!= constraint
|| *is_inout
)
255 size_t c_len
= strlen (constraint
);
258 warning (0, "output constraint %qc for operand %d "
259 "is not at the beginning",
262 /* Make a copy of the constraint. */
263 buf
= XALLOCAVEC (char, c_len
+ 1);
264 strcpy (buf
, constraint
);
265 /* Swap the first character and the `=' or `+'. */
266 buf
[p
- constraint
] = buf
[0];
267 /* Make sure the first character is an `='. (Until we do this,
268 it might be a `+'.) */
270 /* Replace the constraint with the canonicalized string. */
271 *constraint_p
= ggc_alloc_string (buf
, c_len
);
272 constraint
= *constraint_p
;
275 /* Loop through the constraint string. */
276 for (p
= constraint
+ 1; *p
; p
+= CONSTRAINT_LEN (*p
, p
))
281 error ("operand constraint contains incorrectly positioned "
286 if (operand_num
+ 1 == ninputs
+ noutputs
)
288 error ("%<%%%> constraint used with last operand");
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
321 enum constraint_num cn
= lookup_constraint (p
);
322 if (reg_class_for_constraint (cn
) != NO_REGS
323 || insn_extra_address_constraint (cn
))
325 else if (insn_extra_memory_constraint (cn
))
329 /* Otherwise we can't assume anything about the nature of
330 the constraint except that it isn't purely registers.
331 Treat it like "g" and hope for the best. */
341 /* Similar, but for input constraints. */
344 parse_input_constraint (const char **constraint_p
, int input_num
,
345 int ninputs
, int noutputs
, int ninout
,
346 const char * const * constraints
,
347 bool *allows_mem
, bool *allows_reg
)
349 const char *constraint
= *constraint_p
;
350 const char *orig_constraint
= constraint
;
351 size_t c_len
= strlen (constraint
);
353 bool saw_match
= false;
355 /* Assume the constraint doesn't allow the use of either
356 a register or memory. */
360 /* Make sure constraint has neither `=', `+', nor '&'. */
362 for (j
= 0; j
< c_len
; j
+= CONSTRAINT_LEN (constraint
[j
], constraint
+j
))
363 switch (constraint
[j
])
365 case '+': case '=': case '&':
366 if (constraint
== orig_constraint
)
368 error ("input operand constraint contains %qc", constraint
[j
]);
374 if (constraint
== orig_constraint
375 && input_num
+ 1 == ninputs
- ninout
)
377 error ("%<%%%> constraint used with last operand");
383 case '?': case '!': case '*': case '#':
384 case 'E': case 'F': case 'G': case 'H':
385 case 's': case 'i': case 'n':
386 case 'I': case 'J': case 'K': case 'L': case 'M':
387 case 'N': case 'O': case 'P': case ',':
390 /* Whether or not a numeric constraint allows a register is
391 decided by the matching constraint, and so there is no need
392 to do anything special with them. We must handle them in
393 the default case, so that we don't unnecessarily force
394 operands to memory. */
395 case '0': case '1': case '2': case '3': case '4':
396 case '5': case '6': case '7': case '8': case '9':
403 match
= strtoul (constraint
+ j
, &end
, 10);
404 if (match
>= (unsigned long) noutputs
)
406 error ("matching constraint references invalid operand number");
410 /* Try and find the real constraint for this dup. Only do this
411 if the matching constraint is the only alternative. */
413 && (j
== 0 || (j
== 1 && constraint
[0] == '%')))
415 constraint
= constraints
[match
];
416 *constraint_p
= constraint
;
417 c_len
= strlen (constraint
);
419 /* ??? At the end of the loop, we will skip the first part of
420 the matched constraint. This assumes not only that the
421 other constraint is an output constraint, but also that
422 the '=' or '+' come first. */
426 j
= end
- constraint
;
427 /* Anticipate increment at end of loop. */
438 if (! ISALPHA (constraint
[j
]))
440 error ("invalid punctuation %qc in constraint", constraint
[j
]);
443 enum constraint_num cn
= lookup_constraint (constraint
+ j
);
444 if (reg_class_for_constraint (cn
) != NO_REGS
445 || insn_extra_address_constraint (cn
))
447 else if (insn_extra_memory_constraint (cn
))
451 /* Otherwise we can't assume anything about the nature of
452 the constraint except that it isn't purely registers.
453 Treat it like "g" and hope for the best. */
460 if (saw_match
&& !*allows_reg
)
461 warning (0, "matching constraint does not allow a register");
466 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
467 can be an asm-declared register. Called via walk_tree. */
470 decl_overlaps_hard_reg_set_p (tree
*declp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
474 const HARD_REG_SET
*const regs
= (const HARD_REG_SET
*) data
;
476 if (TREE_CODE (decl
) == VAR_DECL
)
478 if (DECL_HARD_REGISTER (decl
)
479 && REG_P (DECL_RTL (decl
))
480 && REGNO (DECL_RTL (decl
)) < FIRST_PSEUDO_REGISTER
)
482 rtx reg
= DECL_RTL (decl
);
484 if (overlaps_hard_reg_set_p (*regs
, GET_MODE (reg
), REGNO (reg
)))
489 else if (TYPE_P (decl
) || TREE_CODE (decl
) == PARM_DECL
)
494 /* If there is an overlap between *REGS and DECL, return the first overlap
497 tree_overlaps_hard_reg_set (tree decl
, HARD_REG_SET
*regs
)
499 return walk_tree (&decl
, decl_overlaps_hard_reg_set_p
, regs
, NULL
);
503 /* A subroutine of expand_asm_operands. Check that all operand names
504 are unique. Return true if so. We rely on the fact that these names
505 are identifiers, and so have been canonicalized by get_identifier,
506 so all we need are pointer comparisons. */
509 check_unique_operand_names (tree outputs
, tree inputs
, tree labels
)
511 tree i
, j
, i_name
= NULL_TREE
;
513 for (i
= outputs
; i
; i
= TREE_CHAIN (i
))
515 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
519 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
520 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
524 for (i
= inputs
; i
; i
= TREE_CHAIN (i
))
526 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
530 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
531 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
533 for (j
= outputs
; j
; j
= TREE_CHAIN (j
))
534 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
538 for (i
= labels
; i
; i
= TREE_CHAIN (i
))
540 i_name
= TREE_PURPOSE (i
);
544 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
545 if (simple_cst_equal (i_name
, TREE_PURPOSE (j
)))
547 for (j
= inputs
; j
; j
= TREE_CHAIN (j
))
548 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
555 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name
));
559 /* A subroutine of expand_asm_operands. Resolve the names of the operands
560 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
561 STRING and in the constraints to those numbers. */
564 resolve_asm_operand_names (tree string
, tree outputs
, tree inputs
, tree labels
)
571 check_unique_operand_names (outputs
, inputs
, labels
);
573 /* Substitute [<name>] in input constraint strings. There should be no
574 named operands in output constraints. */
575 for (t
= inputs
; t
; t
= TREE_CHAIN (t
))
577 c
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
578 if (strchr (c
, '[') != NULL
)
580 p
= buffer
= xstrdup (c
);
581 while ((p
= strchr (p
, '[')) != NULL
)
582 p
= resolve_operand_name_1 (p
, outputs
, inputs
, NULL
);
583 TREE_VALUE (TREE_PURPOSE (t
))
584 = build_string (strlen (buffer
), buffer
);
589 /* Now check for any needed substitutions in the template. */
590 c
= TREE_STRING_POINTER (string
);
591 while ((c
= strchr (c
, '%')) != NULL
)
595 else if (ISALPHA (c
[1]) && c
[2] == '[')
599 c
+= 1 + (c
[1] == '%');
606 /* OK, we need to make a copy so we can perform the substitutions.
607 Assume that we will not need extra space--we get to remove '['
608 and ']', which means we cannot have a problem until we have more
609 than 999 operands. */
610 buffer
= xstrdup (TREE_STRING_POINTER (string
));
611 p
= buffer
+ (c
- TREE_STRING_POINTER (string
));
613 while ((p
= strchr (p
, '%')) != NULL
)
617 else if (ISALPHA (p
[1]) && p
[2] == '[')
621 p
+= 1 + (p
[1] == '%');
625 p
= resolve_operand_name_1 (p
, outputs
, inputs
, labels
);
628 string
= build_string (strlen (buffer
), buffer
);
635 /* A subroutine of resolve_operand_names. P points to the '[' for a
636 potential named operand of the form [<name>]. In place, replace
637 the name and brackets with a number. Return a pointer to the
638 balance of the string after substitution. */
641 resolve_operand_name_1 (char *p
, tree outputs
, tree inputs
, tree labels
)
647 /* Collect the operand name. */
648 q
= strchr (++p
, ']');
651 error ("missing close brace for named operand");
652 return strchr (p
, '\0');
656 /* Resolve the name to a number. */
657 for (op
= 0, t
= outputs
; t
; t
= TREE_CHAIN (t
), op
++)
659 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
660 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
663 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), op
++)
665 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
666 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
669 for (t
= labels
; t
; t
= TREE_CHAIN (t
), op
++)
671 tree name
= TREE_PURPOSE (t
);
672 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
676 error ("undefined named operand %qs", identifier_to_locale (p
));
680 /* Replace the name with the number. Unfortunately, not all libraries
681 get the return value of sprintf correct, so search for the end of the
682 generated string by hand. */
683 sprintf (--p
, "%d", op
);
684 p
= strchr (p
, '\0');
686 /* Verify the no extra buffer space assumption. */
689 /* Shift the rest of the buffer down to fill the gap. */
690 memmove (p
, q
+ 1, strlen (q
+ 1) + 1);
696 /* Generate RTL to return directly from the current function.
697 (That is, we bypass any return value.) */
700 expand_naked_return (void)
704 clear_pending_stack_adjust ();
705 do_pending_stack_adjust ();
707 end_label
= naked_return_label
;
709 end_label
= naked_return_label
= gen_label_rtx ();
711 emit_jump (end_label
);
714 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
715 is the probability of jumping to LABEL. */
717 do_jump_if_equal (machine_mode mode
, rtx op0
, rtx op1
, rtx label
,
718 int unsignedp
, int prob
)
720 gcc_assert (prob
<= REG_BR_PROB_BASE
);
721 do_compare_rtx_and_jump (op0
, op1
, EQ
, unsignedp
, mode
,
722 NULL_RTX
, NULL_RTX
, label
, prob
);
725 /* Do the insertion of a case label into case_list. The labels are
726 fed to us in descending order from the sorted vector of case labels used
727 in the tree part of the middle end. So the list we construct is
728 sorted in ascending order.
730 LABEL is the case label to be inserted. LOW and HIGH are the bounds
731 against which the index is compared to jump to LABEL and PROB is the
732 estimated probability LABEL is reached from the switch statement. */
734 static struct case_node
*
735 add_case_node (struct case_node
*head
, tree low
, tree high
,
736 tree label
, int prob
, alloc_pool case_node_pool
)
740 gcc_checking_assert (low
);
741 gcc_checking_assert (high
&& (TREE_TYPE (low
) == TREE_TYPE (high
)));
743 /* Add this label to the chain. */
744 r
= (struct case_node
*) pool_alloc (case_node_pool
);
747 r
->code_label
= label
;
748 r
->parent
= r
->left
= NULL
;
750 r
->subtree_prob
= prob
;
755 /* Dump ROOT, a list or tree of case nodes, to file. */
758 dump_case_nodes (FILE *f
, struct case_node
*root
,
759 int indent_step
, int indent_level
)
765 dump_case_nodes (f
, root
->left
, indent_step
, indent_level
);
768 fprintf (f
, "%*s", indent_step
* indent_level
, "");
769 print_dec (root
->low
, f
, TYPE_SIGN (TREE_TYPE (root
->low
)));
770 if (!tree_int_cst_equal (root
->low
, root
->high
))
772 fprintf (f
, " ... ");
773 print_dec (root
->high
, f
, TYPE_SIGN (TREE_TYPE (root
->high
)));
777 dump_case_nodes (f
, root
->right
, indent_step
, indent_level
);
781 #define HAVE_casesi 0
784 #ifndef HAVE_tablejump
785 #define HAVE_tablejump 0
788 /* Return the smallest number of different values for which it is best to use a
789 jump-table instead of a tree of conditional branches. */
792 case_values_threshold (void)
794 unsigned int threshold
= PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD
);
797 threshold
= targetm
.case_values_threshold ();
802 /* Return true if a switch should be expanded as a decision tree.
803 RANGE is the difference between highest and lowest case.
804 UNIQ is number of unique case node targets, not counting the default case.
805 COUNT is the number of comparisons needed, not counting the default case. */
808 expand_switch_as_decision_tree_p (tree range
,
809 unsigned int uniq ATTRIBUTE_UNUSED
,
814 /* If neither casesi or tablejump is available, or flag_jump_tables
815 over-ruled us, we really have no choice. */
816 if (!HAVE_casesi
&& !HAVE_tablejump
)
818 if (!flag_jump_tables
)
820 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
825 /* If the switch is relatively small such that the cost of one
826 indirect jump on the target are higher than the cost of a
827 decision tree, go with the decision tree.
829 If range of values is much bigger than number of values,
830 or if it is too large to represent in a HOST_WIDE_INT,
831 make a sequence of conditional branches instead of a dispatch.
833 The definition of "much bigger" depends on whether we are
834 optimizing for size or for speed. If the former, the maximum
835 ratio range/count = 3, because this was found to be the optimal
836 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
837 10 is much older, and was probably selected after an extensive
838 benchmarking investigation on numerous platforms. Or maybe it
839 just made sense to someone at some point in the history of GCC,
841 max_ratio
= optimize_insn_for_size_p () ? 3 : 10;
842 if (count
< case_values_threshold ()
843 || ! tree_fits_uhwi_p (range
)
844 || compare_tree_int (range
, max_ratio
* count
) > 0)
850 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
851 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
852 DEFAULT_PROB is the estimated probability that it jumps to
855 We generate a binary decision tree to select the appropriate target
856 code. This is done as follows:
858 If the index is a short or char that we do not have
859 an insn to handle comparisons directly, convert it to
860 a full integer now, rather than letting each comparison
861 generate the conversion.
863 Load the index into a register.
865 The list of cases is rearranged into a binary tree,
866 nearly optimal assuming equal probability for each case.
868 The tree is transformed into RTL, eliminating redundant
869 test conditions at the same time.
871 If program flow could reach the end of the decision tree
872 an unconditional jump to the default code is emitted.
874 The above process is unaware of the CFG. The caller has to fix up
875 the CFG itself. This is done in cfgexpand.c. */
878 emit_case_decision_tree (tree index_expr
, tree index_type
,
879 struct case_node
*case_list
, rtx default_label
,
882 rtx index
= expand_normal (index_expr
);
884 if (GET_MODE_CLASS (GET_MODE (index
)) == MODE_INT
885 && ! have_insn_for (COMPARE
, GET_MODE (index
)))
887 int unsignedp
= TYPE_UNSIGNED (index_type
);
888 machine_mode wider_mode
;
889 for (wider_mode
= GET_MODE (index
); wider_mode
!= VOIDmode
;
890 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
891 if (have_insn_for (COMPARE
, wider_mode
))
893 index
= convert_to_mode (wider_mode
, index
, unsignedp
);
898 do_pending_stack_adjust ();
902 index
= copy_to_reg (index
);
903 if (TREE_CODE (index_expr
) == SSA_NAME
)
904 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr
), index
);
907 balance_case_nodes (&case_list
, NULL
);
909 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
911 int indent_step
= ceil_log2 (TYPE_PRECISION (index_type
)) + 2;
912 fprintf (dump_file
, ";; Expanding GIMPLE switch as decision tree:\n");
913 dump_case_nodes (dump_file
, case_list
, indent_step
, 0);
916 emit_case_nodes (index
, case_list
, default_label
, default_prob
, index_type
);
918 emit_jump (default_label
);
921 /* Return the sum of probabilities of outgoing edges of basic block BB. */
924 get_outgoing_edge_probs (basic_block bb
)
931 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
932 prob_sum
+= e
->probability
;
936 /* Computes the conditional probability of jumping to a target if the branch
937 instruction is executed.
938 TARGET_PROB is the estimated probability of jumping to a target relative
939 to some basic block BB.
940 BASE_PROB is the probability of reaching the branch instruction relative
941 to the same basic block BB. */
944 conditional_probability (int target_prob
, int base_prob
)
948 gcc_assert (target_prob
>= 0);
949 gcc_assert (target_prob
<= base_prob
);
950 return GCOV_COMPUTE_SCALE (target_prob
, base_prob
);
955 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
956 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
957 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
958 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
960 First, a jump insn is emitted. First we try "casesi". If that
961 fails, try "tablejump". A target *must* have one of them (or both).
963 Then, a table with the target labels is emitted.
965 The process is unaware of the CFG. The caller has to fix up
966 the CFG itself. This is done in cfgexpand.c. */
969 emit_case_dispatch_table (tree index_expr
, tree index_type
,
970 struct case_node
*case_list
, rtx default_label
,
971 tree minval
, tree maxval
, tree range
,
977 rtx fallback_label
= label_rtx (case_list
->code_label
);
978 rtx_code_label
*table_label
= gen_label_rtx ();
979 bool has_gaps
= false;
980 edge default_edge
= stmt_bb
? EDGE_SUCC (stmt_bb
, 0) : NULL
;
981 int default_prob
= default_edge
? default_edge
->probability
: 0;
982 int base
= get_outgoing_edge_probs (stmt_bb
);
983 bool try_with_tablejump
= false;
985 int new_default_prob
= conditional_probability (default_prob
,
988 if (! try_casesi (index_type
, index_expr
, minval
, range
,
989 table_label
, default_label
, fallback_label
,
992 /* Index jumptables from zero for suitable values of minval to avoid
993 a subtraction. For the rationale see:
994 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
995 if (optimize_insn_for_speed_p ()
996 && compare_tree_int (minval
, 0) > 0
997 && compare_tree_int (minval
, 3) < 0)
999 minval
= build_int_cst (index_type
, 0);
1003 try_with_tablejump
= true;
1006 /* Get table of labels to jump to, in order of case index. */
1008 ncases
= tree_to_shwi (range
) + 1;
1009 labelvec
= XALLOCAVEC (rtx
, ncases
);
1010 memset (labelvec
, 0, ncases
* sizeof (rtx
));
1012 for (n
= case_list
; n
; n
= n
->right
)
1014 /* Compute the low and high bounds relative to the minimum
1015 value since that should fit in a HOST_WIDE_INT while the
1016 actual values may not. */
1018 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1020 HOST_WIDE_INT i_high
1021 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1025 for (i
= i_low
; i
<= i_high
; i
++)
1027 = gen_rtx_LABEL_REF (Pmode
, label_rtx (n
->code_label
));
1030 /* Fill in the gaps with the default. We may have gaps at
1031 the beginning if we tried to avoid the minval subtraction,
1032 so substitute some label even if the default label was
1033 deemed unreachable. */
1035 default_label
= fallback_label
;
1036 for (i
= 0; i
< ncases
; i
++)
1037 if (labelvec
[i
] == 0)
1040 labelvec
[i
] = gen_rtx_LABEL_REF (Pmode
, default_label
);
1045 /* There is at least one entry in the jump table that jumps
1046 to default label. The default label can either be reached
1047 through the indirect jump or the direct conditional jump
1048 before that. Split the probability of reaching the
1049 default label among these two jumps. */
1050 new_default_prob
= conditional_probability (default_prob
/2,
1053 base
-= default_prob
;
1057 base
-= default_prob
;
1062 default_edge
->probability
= default_prob
;
1064 /* We have altered the probability of the default edge. So the probabilities
1065 of all other edges need to be adjusted so that it sums up to
1066 REG_BR_PROB_BASE. */
1071 FOR_EACH_EDGE (e
, ei
, stmt_bb
->succs
)
1072 e
->probability
= GCOV_COMPUTE_SCALE (e
->probability
, base
);
1075 if (try_with_tablejump
)
1077 bool ok
= try_tablejump (index_type
, index_expr
, minval
, range
,
1078 table_label
, default_label
, new_default_prob
);
1081 /* Output the table. */
1082 emit_label (table_label
);
1084 if (CASE_VECTOR_PC_RELATIVE
|| flag_pic
)
1085 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE
,
1086 gen_rtx_LABEL_REF (Pmode
,
1088 gen_rtvec_v (ncases
, labelvec
),
1089 const0_rtx
, const0_rtx
));
1091 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE
,
1092 gen_rtvec_v (ncases
, labelvec
)));
1094 /* Record no drop-through after the table. */
1098 /* Reset the aux field of all outgoing edges of basic block BB. */
1101 reset_out_edges_aux (basic_block bb
)
1105 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1109 /* Compute the number of case labels that correspond to each outgoing edge of
1110 STMT. Record this information in the aux field of the edge. */
1113 compute_cases_per_edge (gimple stmt
)
1115 basic_block bb
= gimple_bb (stmt
);
1116 reset_out_edges_aux (bb
);
1117 int ncases
= gimple_switch_num_labels (stmt
);
1118 for (int i
= ncases
- 1; i
>= 1; --i
)
1120 tree elt
= gimple_switch_label (stmt
, i
);
1121 tree lab
= CASE_LABEL (elt
);
1122 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1123 edge case_edge
= find_edge (bb
, case_bb
);
1124 case_edge
->aux
= (void *)((intptr_t)(case_edge
->aux
) + 1);
1128 /* Terminate a case (Pascal/Ada) or switch (C) statement
1129 in which ORIG_INDEX is the expression to be tested.
1130 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
1131 type as given in the source before any compiler conversions.
1132 Generate the code to test it and jump to the right place. */
1135 expand_case (gimple stmt
)
1137 tree minval
= NULL_TREE
, maxval
= NULL_TREE
, range
= NULL_TREE
;
1138 rtx default_label
= NULL_RTX
;
1139 unsigned int count
, uniq
;
1141 int ncases
= gimple_switch_num_labels (stmt
);
1142 tree index_expr
= gimple_switch_index (stmt
);
1143 tree index_type
= TREE_TYPE (index_expr
);
1145 basic_block bb
= gimple_bb (stmt
);
1147 /* A list of case labels; it is first built as a list and it may then
1148 be rearranged into a nearly balanced binary tree. */
1149 struct case_node
*case_list
= 0;
1151 /* A pool for case nodes. */
1152 alloc_pool case_node_pool
;
1154 /* An ERROR_MARK occurs for various reasons including invalid data type.
1155 ??? Can this still happen, with GIMPLE and all? */
1156 if (index_type
== error_mark_node
)
1159 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
1160 expressions being INTEGER_CST. */
1161 gcc_assert (TREE_CODE (index_expr
) != INTEGER_CST
);
1163 case_node_pool
= create_alloc_pool ("struct case_node pool",
1164 sizeof (struct case_node
),
1167 do_pending_stack_adjust ();
1169 /* Find the default case target label. */
1170 default_label
= label_rtx (CASE_LABEL (gimple_switch_default_label (stmt
)));
1171 edge default_edge
= EDGE_SUCC (bb
, 0);
1172 int default_prob
= default_edge
->probability
;
1174 /* Get upper and lower bounds of case values. */
1175 elt
= gimple_switch_label (stmt
, 1);
1176 minval
= fold_convert (index_type
, CASE_LOW (elt
));
1177 elt
= gimple_switch_label (stmt
, ncases
- 1);
1178 if (CASE_HIGH (elt
))
1179 maxval
= fold_convert (index_type
, CASE_HIGH (elt
));
1181 maxval
= fold_convert (index_type
, CASE_LOW (elt
));
1183 /* Compute span of values. */
1184 range
= fold_build2 (MINUS_EXPR
, index_type
, maxval
, minval
);
1186 /* Listify the labels queue and gather some numbers to decide
1187 how to expand this switch(). */
1190 hash_set
<tree
> seen_labels
;
1191 compute_cases_per_edge (stmt
);
1193 for (i
= ncases
- 1; i
>= 1; --i
)
1195 elt
= gimple_switch_label (stmt
, i
);
1196 tree low
= CASE_LOW (elt
);
1198 tree high
= CASE_HIGH (elt
);
1199 gcc_assert (! high
|| tree_int_cst_lt (low
, high
));
1200 tree lab
= CASE_LABEL (elt
);
1202 /* Count the elements.
1203 A range counts double, since it requires two compares. */
1208 /* If we have not seen this label yet, then increase the
1209 number of unique case node targets seen. */
1210 if (!seen_labels
.add (lab
))
1213 /* The bounds on the case range, LOW and HIGH, have to be converted
1214 to case's index type TYPE. Note that the original type of the
1215 case index in the source code is usually "lost" during
1216 gimplification due to type promotion, but the case labels retain the
1217 original type. Make sure to drop overflow flags. */
1218 low
= fold_convert (index_type
, low
);
1219 if (TREE_OVERFLOW (low
))
1220 low
= wide_int_to_tree (index_type
, low
);
1222 /* The canonical from of a case label in GIMPLE is that a simple case
1223 has an empty CASE_HIGH. For the casesi and tablejump expanders,
1224 the back ends want simple cases to have high == low. */
1227 high
= fold_convert (index_type
, high
);
1228 if (TREE_OVERFLOW (high
))
1229 high
= wide_int_to_tree (index_type
, high
);
1231 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1232 edge case_edge
= find_edge (bb
, case_bb
);
1233 case_list
= add_case_node (
1234 case_list
, low
, high
, lab
,
1235 case_edge
->probability
/ (intptr_t)(case_edge
->aux
),
1238 reset_out_edges_aux (bb
);
1240 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
1241 destination, such as one with a default case only.
1242 It also removes cases that are out of range for the switch
1243 type, so we should never get a zero here. */
1244 gcc_assert (count
> 0);
1246 rtx_insn
*before_case
= get_last_insn ();
1248 /* Decide how to expand this switch.
1249 The two options at this point are a dispatch table (casesi or
1250 tablejump) or a decision tree. */
1252 if (expand_switch_as_decision_tree_p (range
, uniq
, count
))
1253 emit_case_decision_tree (index_expr
, index_type
,
1254 case_list
, default_label
,
1257 emit_case_dispatch_table (index_expr
, index_type
,
1258 case_list
, default_label
,
1259 minval
, maxval
, range
, bb
);
1261 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1264 free_alloc_pool (case_node_pool
);
1267 /* Expand the dispatch to a short decrement chain if there are few cases
1268 to dispatch to. Likewise if neither casesi nor tablejump is available,
1269 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
1270 tablejump. The index mode is always the mode of integer_type_node.
1271 Trap if no case matches the index.
1273 DISPATCH_INDEX is the index expression to switch on. It should be a
1274 memory or register operand.
1276 DISPATCH_TABLE is a set of case labels. The set should be sorted in
1277 ascending order, be contiguous, starting with value 0, and contain only
1278 single-valued case labels. */
1281 expand_sjlj_dispatch_table (rtx dispatch_index
,
1282 vec
<tree
> dispatch_table
)
1284 tree index_type
= integer_type_node
;
1285 machine_mode index_mode
= TYPE_MODE (index_type
);
1287 int ncases
= dispatch_table
.length ();
1289 do_pending_stack_adjust ();
1290 rtx_insn
*before_case
= get_last_insn ();
1292 /* Expand as a decrement-chain if there are 5 or fewer dispatch
1293 labels. This covers more than 98% of the cases in libjava,
1294 and seems to be a reasonable compromise between the "old way"
1295 of expanding as a decision tree or dispatch table vs. the "new
1296 way" with decrement chain or dispatch table. */
1297 if (dispatch_table
.length () <= 5
1298 || (!HAVE_casesi
&& !HAVE_tablejump
)
1299 || !flag_jump_tables
)
1301 /* Expand the dispatch as a decrement chain:
1303 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1307 if (index == 0) do_0; else index--;
1308 if (index == 0) do_1; else index--;
1310 if (index == 0) do_N; else index--;
1312 This is more efficient than a dispatch table on most machines.
1313 The last "index--" is redundant but the code is trivially dead
1314 and will be cleaned up by later passes. */
1315 rtx index
= copy_to_mode_reg (index_mode
, dispatch_index
);
1316 rtx zero
= CONST0_RTX (index_mode
);
1317 for (int i
= 0; i
< ncases
; i
++)
1319 tree elt
= dispatch_table
[i
];
1320 rtx lab
= label_rtx (CASE_LABEL (elt
));
1321 do_jump_if_equal (index_mode
, index
, zero
, lab
, 0, -1);
1322 force_expand_binop (index_mode
, sub_optab
,
1323 index
, CONST1_RTX (index_mode
),
1324 index
, 0, OPTAB_DIRECT
);
1329 /* Similar to expand_case, but much simpler. */
1330 struct case_node
*case_list
= 0;
1331 alloc_pool case_node_pool
= create_alloc_pool ("struct sjlj_case pool",
1332 sizeof (struct case_node
),
1334 tree index_expr
= make_tree (index_type
, dispatch_index
);
1335 tree minval
= build_int_cst (index_type
, 0);
1336 tree maxval
= CASE_LOW (dispatch_table
.last ());
1337 tree range
= maxval
;
1338 rtx_code_label
*default_label
= gen_label_rtx ();
1340 for (int i
= ncases
- 1; i
>= 0; --i
)
1342 tree elt
= dispatch_table
[i
];
1343 tree low
= CASE_LOW (elt
);
1344 tree lab
= CASE_LABEL (elt
);
1345 case_list
= add_case_node (case_list
, low
, low
, lab
, 0, case_node_pool
);
1348 emit_case_dispatch_table (index_expr
, index_type
,
1349 case_list
, default_label
,
1350 minval
, maxval
, range
,
1351 BLOCK_FOR_INSN (before_case
));
1352 emit_label (default_label
);
1353 free_alloc_pool (case_node_pool
);
1356 /* Dispatching something not handled? Trap! */
1357 expand_builtin_trap ();
1359 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1365 /* Take an ordered list of case nodes
1366 and transform them into a near optimal binary tree,
1367 on the assumption that any target code selection value is as
1368 likely as any other.
1370 The transformation is performed by splitting the ordered
1371 list into two equal sections plus a pivot. The parts are
1372 then attached to the pivot as left and right branches. Each
1373 branch is then transformed recursively. */
1376 balance_case_nodes (case_node_ptr
*head
, case_node_ptr parent
)
1388 /* Count the number of entries on branch. Also count the ranges. */
1392 if (!tree_int_cst_equal (np
->low
, np
->high
))
1401 /* Split this list if it is long enough for that to help. */
1405 /* If there are just three nodes, split at the middle one. */
1407 npp
= &(*npp
)->right
;
1410 /* Find the place in the list that bisects the list's total cost,
1411 where ranges count as 2.
1412 Here I gets half the total cost. */
1413 i
= (i
+ ranges
+ 1) / 2;
1416 /* Skip nodes while their cost does not reach that amount. */
1417 if (!tree_int_cst_equal ((*npp
)->low
, (*npp
)->high
))
1422 npp
= &(*npp
)->right
;
1427 np
->parent
= parent
;
1430 /* Optimize each of the two split parts. */
1431 balance_case_nodes (&np
->left
, np
);
1432 balance_case_nodes (&np
->right
, np
);
1433 np
->subtree_prob
= np
->prob
;
1434 np
->subtree_prob
+= np
->left
->subtree_prob
;
1435 np
->subtree_prob
+= np
->right
->subtree_prob
;
1439 /* Else leave this branch as one level,
1440 but fill in `parent' fields. */
1442 np
->parent
= parent
;
1443 np
->subtree_prob
= np
->prob
;
1444 for (; np
->right
; np
= np
->right
)
1446 np
->right
->parent
= np
;
1447 (*head
)->subtree_prob
+= np
->right
->subtree_prob
;
1453 /* Search the parent sections of the case node tree
1454 to see if a test for the lower bound of NODE would be redundant.
1455 INDEX_TYPE is the type of the index expression.
1457 The instructions to generate the case decision tree are
1458 output in the same order as nodes are processed so it is
1459 known that if a parent node checks the range of the current
1460 node minus one that the current node is bounded at its lower
1461 span. Thus the test would be redundant. */
1464 node_has_low_bound (case_node_ptr node
, tree index_type
)
1467 case_node_ptr pnode
;
1469 /* If the lower bound of this node is the lowest value in the index type,
1470 we need not test it. */
1472 if (tree_int_cst_equal (node
->low
, TYPE_MIN_VALUE (index_type
)))
1475 /* If this node has a left branch, the value at the left must be less
1476 than that at this node, so it cannot be bounded at the bottom and
1477 we need not bother testing any further. */
1482 low_minus_one
= fold_build2 (MINUS_EXPR
, TREE_TYPE (node
->low
),
1484 build_int_cst (TREE_TYPE (node
->low
), 1));
1486 /* If the subtraction above overflowed, we can't verify anything.
1487 Otherwise, look for a parent that tests our value - 1. */
1489 if (! tree_int_cst_lt (low_minus_one
, node
->low
))
1492 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1493 if (tree_int_cst_equal (low_minus_one
, pnode
->high
))
1499 /* Search the parent sections of the case node tree
1500 to see if a test for the upper bound of NODE would be redundant.
1501 INDEX_TYPE is the type of the index expression.
1503 The instructions to generate the case decision tree are
1504 output in the same order as nodes are processed so it is
1505 known that if a parent node checks the range of the current
1506 node plus one that the current node is bounded at its upper
1507 span. Thus the test would be redundant. */
1510 node_has_high_bound (case_node_ptr node
, tree index_type
)
1513 case_node_ptr pnode
;
1515 /* If there is no upper bound, obviously no test is needed. */
1517 if (TYPE_MAX_VALUE (index_type
) == NULL
)
1520 /* If the upper bound of this node is the highest value in the type
1521 of the index expression, we need not test against it. */
1523 if (tree_int_cst_equal (node
->high
, TYPE_MAX_VALUE (index_type
)))
1526 /* If this node has a right branch, the value at the right must be greater
1527 than that at this node, so it cannot be bounded at the top and
1528 we need not bother testing any further. */
1533 high_plus_one
= fold_build2 (PLUS_EXPR
, TREE_TYPE (node
->high
),
1535 build_int_cst (TREE_TYPE (node
->high
), 1));
1537 /* If the addition above overflowed, we can't verify anything.
1538 Otherwise, look for a parent that tests our value + 1. */
1540 if (! tree_int_cst_lt (node
->high
, high_plus_one
))
1543 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1544 if (tree_int_cst_equal (high_plus_one
, pnode
->low
))
1550 /* Search the parent sections of the
1551 case node tree to see if both tests for the upper and lower
1552 bounds of NODE would be redundant. */
1555 node_is_bounded (case_node_ptr node
, tree index_type
)
1557 return (node_has_low_bound (node
, index_type
)
1558 && node_has_high_bound (node
, index_type
));
1562 /* Emit step-by-step code to select a case for the value of INDEX.
1563 The thus generated decision tree follows the form of the
1564 case-node binary tree NODE, whose nodes represent test conditions.
1565 INDEX_TYPE is the type of the index of the switch.
1567 Care is taken to prune redundant tests from the decision tree
1568 by detecting any boundary conditions already checked by
1569 emitted rtx. (See node_has_high_bound, node_has_low_bound
1570 and node_is_bounded, above.)
1572 Where the test conditions can be shown to be redundant we emit
1573 an unconditional jump to the target code. As a further
1574 optimization, the subordinates of a tree node are examined to
1575 check for bounded nodes. In this case conditional and/or
1576 unconditional jumps as a result of the boundary check for the
1577 current node are arranged to target the subordinates associated
1578 code for out of bound conditions on the current node.
1580 We can assume that when control reaches the code generated here,
1581 the index value has already been compared with the parents
1582 of this node, and determined to be on the same side of each parent
1583 as this node is. Thus, if this node tests for the value 51,
1584 and a parent tested for 52, we don't need to consider
1585 the possibility of a value greater than 51. If another parent
1586 tests for the value 50, then this node need not test anything. */
1589 emit_case_nodes (rtx index
, case_node_ptr node
, rtx default_label
,
1590 int default_prob
, tree index_type
)
1592 /* If INDEX has an unsigned type, we must make unsigned branches. */
1593 int unsignedp
= TYPE_UNSIGNED (index_type
);
1595 int prob
= node
->prob
, subtree_prob
= node
->subtree_prob
;
1596 machine_mode mode
= GET_MODE (index
);
1597 machine_mode imode
= TYPE_MODE (index_type
);
1599 /* Handle indices detected as constant during RTL expansion. */
1600 if (mode
== VOIDmode
)
1603 /* See if our parents have already tested everything for us.
1604 If they have, emit an unconditional jump for this node. */
1605 if (node_is_bounded (node
, index_type
))
1606 emit_jump (label_rtx (node
->code_label
));
1608 else if (tree_int_cst_equal (node
->low
, node
->high
))
1610 probability
= conditional_probability (prob
, subtree_prob
+ default_prob
);
1611 /* Node is single valued. First see if the index expression matches
1612 this node and then check our children, if any. */
1613 do_jump_if_equal (mode
, index
,
1614 convert_modes (mode
, imode
,
1615 expand_normal (node
->low
),
1617 label_rtx (node
->code_label
), unsignedp
, probability
);
1618 /* Since this case is taken at this point, reduce its weight from
1620 subtree_prob
-= prob
;
1621 if (node
->right
!= 0 && node
->left
!= 0)
1623 /* This node has children on both sides.
1624 Dispatch to one side or the other
1625 by comparing the index value with this node's value.
1626 If one subtree is bounded, check that one first,
1627 so we can avoid real branches in the tree. */
1629 if (node_is_bounded (node
->right
, index_type
))
1631 probability
= conditional_probability (
1633 subtree_prob
+ default_prob
);
1634 emit_cmp_and_jump_insns (index
,
1637 expand_normal (node
->high
),
1639 GT
, NULL_RTX
, mode
, unsignedp
,
1640 label_rtx (node
->right
->code_label
),
1642 emit_case_nodes (index
, node
->left
, default_label
, default_prob
,
1646 else if (node_is_bounded (node
->left
, index_type
))
1648 probability
= conditional_probability (
1650 subtree_prob
+ default_prob
);
1651 emit_cmp_and_jump_insns (index
,
1654 expand_normal (node
->high
),
1656 LT
, NULL_RTX
, mode
, unsignedp
,
1657 label_rtx (node
->left
->code_label
),
1659 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1662 /* If both children are single-valued cases with no
1663 children, finish up all the work. This way, we can save
1664 one ordered comparison. */
1665 else if (tree_int_cst_equal (node
->right
->low
, node
->right
->high
)
1666 && node
->right
->left
== 0
1667 && node
->right
->right
== 0
1668 && tree_int_cst_equal (node
->left
->low
, node
->left
->high
)
1669 && node
->left
->left
== 0
1670 && node
->left
->right
== 0)
1672 /* Neither node is bounded. First distinguish the two sides;
1673 then emit the code for one side at a time. */
1675 /* See if the value matches what the right hand side
1677 probability
= conditional_probability (
1679 subtree_prob
+ default_prob
);
1680 do_jump_if_equal (mode
, index
,
1681 convert_modes (mode
, imode
,
1682 expand_normal (node
->right
->low
),
1684 label_rtx (node
->right
->code_label
),
1685 unsignedp
, probability
);
1687 /* See if the value matches what the left hand side
1689 probability
= conditional_probability (
1691 subtree_prob
+ default_prob
);
1692 do_jump_if_equal (mode
, index
,
1693 convert_modes (mode
, imode
,
1694 expand_normal (node
->left
->low
),
1696 label_rtx (node
->left
->code_label
),
1697 unsignedp
, probability
);
1702 /* Neither node is bounded. First distinguish the two sides;
1703 then emit the code for one side at a time. */
1706 = build_decl (curr_insn_location (),
1707 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
1709 /* The default label could be reached either through the right
1710 subtree or the left subtree. Divide the probability
1712 probability
= conditional_probability (
1713 node
->right
->subtree_prob
+ default_prob
/2,
1714 subtree_prob
+ default_prob
);
1715 /* See if the value is on the right. */
1716 emit_cmp_and_jump_insns (index
,
1719 expand_normal (node
->high
),
1721 GT
, NULL_RTX
, mode
, unsignedp
,
1722 label_rtx (test_label
),
1726 /* Value must be on the left.
1727 Handle the left-hand subtree. */
1728 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1729 /* If left-hand subtree does nothing,
1732 emit_jump (default_label
);
1734 /* Code branches here for the right-hand subtree. */
1735 expand_label (test_label
);
1736 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1740 else if (node
->right
!= 0 && node
->left
== 0)
1742 /* Here we have a right child but no left so we issue a conditional
1743 branch to default and process the right child.
1745 Omit the conditional branch to default if the right child
1746 does not have any children and is single valued; it would
1747 cost too much space to save so little time. */
1749 if (node
->right
->right
|| node
->right
->left
1750 || !tree_int_cst_equal (node
->right
->low
, node
->right
->high
))
1752 if (!node_has_low_bound (node
, index_type
))
1754 probability
= conditional_probability (
1756 subtree_prob
+ default_prob
);
1757 emit_cmp_and_jump_insns (index
,
1760 expand_normal (node
->high
),
1762 LT
, NULL_RTX
, mode
, unsignedp
,
1768 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1772 probability
= conditional_probability (
1773 node
->right
->subtree_prob
,
1774 subtree_prob
+ default_prob
);
1775 /* We cannot process node->right normally
1776 since we haven't ruled out the numbers less than
1777 this node's value. So handle node->right explicitly. */
1778 do_jump_if_equal (mode
, index
,
1781 expand_normal (node
->right
->low
),
1783 label_rtx (node
->right
->code_label
), unsignedp
, probability
);
1787 else if (node
->right
== 0 && node
->left
!= 0)
1789 /* Just one subtree, on the left. */
1790 if (node
->left
->left
|| node
->left
->right
1791 || !tree_int_cst_equal (node
->left
->low
, node
->left
->high
))
1793 if (!node_has_high_bound (node
, index_type
))
1795 probability
= conditional_probability (
1797 subtree_prob
+ default_prob
);
1798 emit_cmp_and_jump_insns (index
,
1801 expand_normal (node
->high
),
1803 GT
, NULL_RTX
, mode
, unsignedp
,
1809 emit_case_nodes (index
, node
->left
, default_label
,
1810 default_prob
, index_type
);
1814 probability
= conditional_probability (
1815 node
->left
->subtree_prob
,
1816 subtree_prob
+ default_prob
);
1817 /* We cannot process node->left normally
1818 since we haven't ruled out the numbers less than
1819 this node's value. So handle node->left explicitly. */
1820 do_jump_if_equal (mode
, index
,
1823 expand_normal (node
->left
->low
),
1825 label_rtx (node
->left
->code_label
), unsignedp
, probability
);
1831 /* Node is a range. These cases are very similar to those for a single
1832 value, except that we do not start by testing whether this node
1833 is the one to branch to. */
1835 if (node
->right
!= 0 && node
->left
!= 0)
1837 /* Node has subtrees on both sides.
1838 If the right-hand subtree is bounded,
1839 test for it first, since we can go straight there.
1840 Otherwise, we need to make a branch in the control structure,
1841 then handle the two subtrees. */
1842 tree test_label
= 0;
1844 if (node_is_bounded (node
->right
, index_type
))
1846 /* Right hand node is fully bounded so we can eliminate any
1847 testing and branch directly to the target code. */
1848 probability
= conditional_probability (
1849 node
->right
->subtree_prob
,
1850 subtree_prob
+ default_prob
);
1851 emit_cmp_and_jump_insns (index
,
1854 expand_normal (node
->high
),
1856 GT
, NULL_RTX
, mode
, unsignedp
,
1857 label_rtx (node
->right
->code_label
),
1862 /* Right hand node requires testing.
1863 Branch to a label where we will handle it later. */
1865 test_label
= build_decl (curr_insn_location (),
1866 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
1867 probability
= conditional_probability (
1868 node
->right
->subtree_prob
+ default_prob
/2,
1869 subtree_prob
+ default_prob
);
1870 emit_cmp_and_jump_insns (index
,
1873 expand_normal (node
->high
),
1875 GT
, NULL_RTX
, mode
, unsignedp
,
1876 label_rtx (test_label
),
1881 /* Value belongs to this node or to the left-hand subtree. */
1883 probability
= conditional_probability (
1885 subtree_prob
+ default_prob
);
1886 emit_cmp_and_jump_insns (index
,
1889 expand_normal (node
->low
),
1891 GE
, NULL_RTX
, mode
, unsignedp
,
1892 label_rtx (node
->code_label
),
1895 /* Handle the left-hand subtree. */
1896 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1898 /* If right node had to be handled later, do that now. */
1902 /* If the left-hand subtree fell through,
1903 don't let it fall into the right-hand subtree. */
1905 emit_jump (default_label
);
1907 expand_label (test_label
);
1908 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1912 else if (node
->right
!= 0 && node
->left
== 0)
1914 /* Deal with values to the left of this node,
1915 if they are possible. */
1916 if (!node_has_low_bound (node
, index_type
))
1918 probability
= conditional_probability (
1920 subtree_prob
+ default_prob
);
1921 emit_cmp_and_jump_insns (index
,
1924 expand_normal (node
->low
),
1926 LT
, NULL_RTX
, mode
, unsignedp
,
1932 /* Value belongs to this node or to the right-hand subtree. */
1934 probability
= conditional_probability (
1936 subtree_prob
+ default_prob
);
1937 emit_cmp_and_jump_insns (index
,
1940 expand_normal (node
->high
),
1942 LE
, NULL_RTX
, mode
, unsignedp
,
1943 label_rtx (node
->code_label
),
1946 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1949 else if (node
->right
== 0 && node
->left
!= 0)
1951 /* Deal with values to the right of this node,
1952 if they are possible. */
1953 if (!node_has_high_bound (node
, index_type
))
1955 probability
= conditional_probability (
1957 subtree_prob
+ default_prob
);
1958 emit_cmp_and_jump_insns (index
,
1961 expand_normal (node
->high
),
1963 GT
, NULL_RTX
, mode
, unsignedp
,
1969 /* Value belongs to this node or to the left-hand subtree. */
1971 probability
= conditional_probability (
1973 subtree_prob
+ default_prob
);
1974 emit_cmp_and_jump_insns (index
,
1977 expand_normal (node
->low
),
1979 GE
, NULL_RTX
, mode
, unsignedp
,
1980 label_rtx (node
->code_label
),
1983 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1988 /* Node has no children so we check low and high bounds to remove
1989 redundant tests. Only one of the bounds can exist,
1990 since otherwise this node is bounded--a case tested already. */
1991 int high_bound
= node_has_high_bound (node
, index_type
);
1992 int low_bound
= node_has_low_bound (node
, index_type
);
1994 if (!high_bound
&& low_bound
)
1996 probability
= conditional_probability (
1998 subtree_prob
+ default_prob
);
1999 emit_cmp_and_jump_insns (index
,
2002 expand_normal (node
->high
),
2004 GT
, NULL_RTX
, mode
, unsignedp
,
2009 else if (!low_bound
&& high_bound
)
2011 probability
= conditional_probability (
2013 subtree_prob
+ default_prob
);
2014 emit_cmp_and_jump_insns (index
,
2017 expand_normal (node
->low
),
2019 LT
, NULL_RTX
, mode
, unsignedp
,
2023 else if (!low_bound
&& !high_bound
)
2025 /* Widen LOW and HIGH to the same width as INDEX. */
2026 tree type
= lang_hooks
.types
.type_for_mode (mode
, unsignedp
);
2027 tree low
= build1 (CONVERT_EXPR
, type
, node
->low
);
2028 tree high
= build1 (CONVERT_EXPR
, type
, node
->high
);
2029 rtx low_rtx
, new_index
, new_bound
;
2031 /* Instead of doing two branches, emit one unsigned branch for
2032 (index-low) > (high-low). */
2033 low_rtx
= expand_expr (low
, NULL_RTX
, mode
, EXPAND_NORMAL
);
2034 new_index
= expand_simple_binop (mode
, MINUS
, index
, low_rtx
,
2035 NULL_RTX
, unsignedp
,
2037 new_bound
= expand_expr (fold_build2 (MINUS_EXPR
, type
,
2039 NULL_RTX
, mode
, EXPAND_NORMAL
);
2041 probability
= conditional_probability (
2043 subtree_prob
+ default_prob
);
2044 emit_cmp_and_jump_insns (new_index
, new_bound
, GT
, NULL_RTX
,
2045 mode
, 1, default_label
, probability
);
2048 emit_jump (label_rtx (node
->code_label
));