1 /* Expands front end tree to back end RTL for GCC
2 Copyright (C) 1987-2015 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"
35 #include "double-int.h"
42 #include "fold-const.h"
44 #include "stor-layout.h"
49 #include "insn-config.h"
51 #include "statistics.h"
53 #include "fixed-value.h"
63 #include "diagnostic-core.h"
65 #include "langhooks.h"
67 #include "insn-codes.h"
71 #include "basic-block.h"
72 #include "tree-ssa-alias.h"
73 #include "internal-fn.h"
74 #include "gimple-expr.h"
78 #include "alloc-pool.h"
79 #include "pretty-print.h"
85 /* Functions and data structures for expanding case statements. */
87 /* Case label structure, used to hold info on labels within case
88 statements. We handle "range" labels; for a single-value label
89 as in C, the high and low limits are the same.
91 We start with a vector of case nodes sorted in ascending order, and
92 the default label as the last element in the vector. Before expanding
93 to RTL, we transform this vector into a list linked via the RIGHT
94 fields in the case_node struct. Nodes with higher case values are
97 Switch statements can be output in three forms. A branch table is
98 used if there are more than a few labels and the labels are dense
99 within the range between the smallest and largest case value. If a
100 branch table is used, no further manipulations are done with the case
103 The alternative to the use of a branch table is to generate a series
104 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
105 and PARENT fields to hold a binary tree. Initially the tree is
106 totally unbalanced, with everything on the right. We balance the tree
107 with nodes on the left having lower case values than the parent
108 and nodes on the right having higher values. We then output the tree
111 For very small, suitable switch statements, we can generate a series
112 of simple bit test and branches instead. */
116 struct case_node
*left
; /* Left son in binary tree */
117 struct case_node
*right
; /* Right son in binary tree; also node chain */
118 struct case_node
*parent
; /* Parent of node in binary tree */
119 tree low
; /* Lowest index value for this label */
120 tree high
; /* Highest index value for this label */
121 tree code_label
; /* Label to jump to when node matches */
122 int prob
; /* Probability of taking this case. */
123 /* Probability of reaching subtree rooted at this node */
127 typedef struct case_node case_node
;
128 typedef struct case_node
*case_node_ptr
;
130 extern basic_block
label_to_block_fn (struct function
*, tree
);
132 static bool check_unique_operand_names (tree
, tree
, tree
);
133 static char *resolve_operand_name_1 (char *, tree
, tree
, tree
);
134 static void balance_case_nodes (case_node_ptr
*, case_node_ptr
);
135 static int node_has_low_bound (case_node_ptr
, tree
);
136 static int node_has_high_bound (case_node_ptr
, tree
);
137 static int node_is_bounded (case_node_ptr
, tree
);
138 static void emit_case_nodes (rtx
, case_node_ptr
, rtx
, int, tree
);
140 /* Return the rtx-label that corresponds to a LABEL_DECL,
141 creating it if necessary. */
144 label_rtx (tree label
)
146 gcc_assert (TREE_CODE (label
) == LABEL_DECL
);
148 if (!DECL_RTL_SET_P (label
))
150 rtx_code_label
*r
= gen_label_rtx ();
151 SET_DECL_RTL (label
, r
);
152 if (FORCED_LABEL (label
) || DECL_NONLOCAL (label
))
153 LABEL_PRESERVE_P (r
) = 1;
156 return DECL_RTL (label
);
159 /* As above, but also put it on the forced-reference list of the
160 function that contains it. */
162 force_label_rtx (tree label
)
164 rtx_insn
*ref
= as_a
<rtx_insn
*> (label_rtx (label
));
165 tree function
= decl_function_context (label
);
167 gcc_assert (function
);
169 forced_labels
= gen_rtx_INSN_LIST (VOIDmode
, ref
, forced_labels
);
173 /* Add an unconditional jump to LABEL as the next sequential instruction. */
176 emit_jump (rtx label
)
178 do_pending_stack_adjust ();
179 emit_jump_insn (gen_jump (label
));
183 /* Handle goto statements and the labels that they can go to. */
185 /* Specify the location in the RTL code of a label LABEL,
186 which is a LABEL_DECL tree node.
188 This is used for the kind of label that the user can jump to with a
189 goto statement, and for alternatives of a switch or case statement.
190 RTL labels generated for loops and conditionals don't go through here;
191 they are generated directly at the RTL level, by other functions below.
193 Note that this has nothing to do with defining label *names*.
194 Languages vary in how they do that and what that even means. */
197 expand_label (tree label
)
199 rtx_insn
*label_r
= as_a
<rtx_insn
*> (label_rtx (label
));
201 do_pending_stack_adjust ();
202 emit_label (label_r
);
203 if (DECL_NAME (label
))
204 LABEL_NAME (DECL_RTL (label
)) = IDENTIFIER_POINTER (DECL_NAME (label
));
206 if (DECL_NONLOCAL (label
))
208 expand_builtin_setjmp_receiver (NULL
);
209 nonlocal_goto_handler_labels
210 = gen_rtx_INSN_LIST (VOIDmode
, label_r
,
211 nonlocal_goto_handler_labels
);
214 if (FORCED_LABEL (label
))
215 forced_labels
= gen_rtx_INSN_LIST (VOIDmode
, label_r
, forced_labels
);
217 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
218 maybe_set_first_label_num (label_r
);
221 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
222 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
223 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
224 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
225 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
226 constraint allows the use of a register operand. And, *IS_INOUT
227 will be true if the operand is read-write, i.e., if it is used as
228 an input as well as an output. If *CONSTRAINT_P is not in
229 canonical form, it will be made canonical. (Note that `+' will be
230 replaced with `=' as part of this process.)
232 Returns TRUE if all went well; FALSE if an error occurred. */
235 parse_output_constraint (const char **constraint_p
, int operand_num
,
236 int ninputs
, int noutputs
, bool *allows_mem
,
237 bool *allows_reg
, bool *is_inout
)
239 const char *constraint
= *constraint_p
;
242 /* Assume the constraint doesn't allow the use of either a register
247 /* Allow the `=' or `+' to not be at the beginning of the string,
248 since it wasn't explicitly documented that way, and there is a
249 large body of code that puts it last. Swap the character to
250 the front, so as not to uglify any place else. */
251 p
= strchr (constraint
, '=');
253 p
= strchr (constraint
, '+');
255 /* If the string doesn't contain an `=', issue an error
259 error ("output operand constraint lacks %<=%>");
263 /* If the constraint begins with `+', then the operand is both read
264 from and written to. */
265 *is_inout
= (*p
== '+');
267 /* Canonicalize the output constraint so that it begins with `='. */
268 if (p
!= constraint
|| *is_inout
)
271 size_t c_len
= strlen (constraint
);
274 warning (0, "output constraint %qc for operand %d "
275 "is not at the beginning",
278 /* Make a copy of the constraint. */
279 buf
= XALLOCAVEC (char, c_len
+ 1);
280 strcpy (buf
, constraint
);
281 /* Swap the first character and the `=' or `+'. */
282 buf
[p
- constraint
] = buf
[0];
283 /* Make sure the first character is an `='. (Until we do this,
284 it might be a `+'.) */
286 /* Replace the constraint with the canonicalized string. */
287 *constraint_p
= ggc_alloc_string (buf
, c_len
);
288 constraint
= *constraint_p
;
291 /* Loop through the constraint string. */
292 for (p
= constraint
+ 1; *p
; p
+= CONSTRAINT_LEN (*p
, p
))
297 error ("operand constraint contains incorrectly positioned "
302 if (operand_num
+ 1 == ninputs
+ noutputs
)
304 error ("%<%%%> constraint used with last operand");
309 case '?': case '!': case '*': case '&': case '#':
311 case 'E': case 'F': case 'G': case 'H':
312 case 's': case 'i': case 'n':
313 case 'I': case 'J': case 'K': case 'L': case 'M':
314 case 'N': case 'O': case 'P': case ',':
317 case '0': case '1': case '2': case '3': case '4':
318 case '5': case '6': case '7': case '8': case '9':
320 error ("matching constraint not valid in output operand");
324 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
325 excepting those that expand_call created. So match memory
338 enum constraint_num cn
= lookup_constraint (p
);
339 if (reg_class_for_constraint (cn
) != NO_REGS
340 || insn_extra_address_constraint (cn
))
342 else if (insn_extra_memory_constraint (cn
))
345 insn_extra_constraint_allows_reg_mem (cn
, allows_reg
, allows_mem
);
352 /* Similar, but for input constraints. */
355 parse_input_constraint (const char **constraint_p
, int input_num
,
356 int ninputs
, int noutputs
, int ninout
,
357 const char * const * constraints
,
358 bool *allows_mem
, bool *allows_reg
)
360 const char *constraint
= *constraint_p
;
361 const char *orig_constraint
= constraint
;
362 size_t c_len
= strlen (constraint
);
364 bool saw_match
= false;
366 /* Assume the constraint doesn't allow the use of either
367 a register or memory. */
371 /* Make sure constraint has neither `=', `+', nor '&'. */
373 for (j
= 0; j
< c_len
; j
+= CONSTRAINT_LEN (constraint
[j
], constraint
+j
))
374 switch (constraint
[j
])
376 case '+': case '=': case '&':
377 if (constraint
== orig_constraint
)
379 error ("input operand constraint contains %qc", constraint
[j
]);
385 if (constraint
== orig_constraint
386 && input_num
+ 1 == ninputs
- ninout
)
388 error ("%<%%%> constraint used with last operand");
394 case '?': case '!': case '*': case '#':
396 case 'E': case 'F': case 'G': case 'H':
397 case 's': case 'i': case 'n':
398 case 'I': case 'J': case 'K': case 'L': case 'M':
399 case 'N': case 'O': case 'P': case ',':
402 /* Whether or not a numeric constraint allows a register is
403 decided by the matching constraint, and so there is no need
404 to do anything special with them. We must handle them in
405 the default case, so that we don't unnecessarily force
406 operands to memory. */
407 case '0': case '1': case '2': case '3': case '4':
408 case '5': case '6': case '7': case '8': case '9':
415 match
= strtoul (constraint
+ j
, &end
, 10);
416 if (match
>= (unsigned long) noutputs
)
418 error ("matching constraint references invalid operand number");
422 /* Try and find the real constraint for this dup. Only do this
423 if the matching constraint is the only alternative. */
425 && (j
== 0 || (j
== 1 && constraint
[0] == '%')))
427 constraint
= constraints
[match
];
428 *constraint_p
= constraint
;
429 c_len
= strlen (constraint
);
431 /* ??? At the end of the loop, we will skip the first part of
432 the matched constraint. This assumes not only that the
433 other constraint is an output constraint, but also that
434 the '=' or '+' come first. */
438 j
= end
- constraint
;
439 /* 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
))
462 insn_extra_constraint_allows_reg_mem (cn
, allows_reg
, allows_mem
);
466 if (saw_match
&& !*allows_reg
)
467 warning (0, "matching constraint does not allow a register");
472 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
473 can be an asm-declared register. Called via walk_tree. */
476 decl_overlaps_hard_reg_set_p (tree
*declp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
480 const HARD_REG_SET
*const regs
= (const HARD_REG_SET
*) data
;
482 if (TREE_CODE (decl
) == VAR_DECL
)
484 if (DECL_HARD_REGISTER (decl
)
485 && REG_P (DECL_RTL (decl
))
486 && REGNO (DECL_RTL (decl
)) < FIRST_PSEUDO_REGISTER
)
488 rtx reg
= DECL_RTL (decl
);
490 if (overlaps_hard_reg_set_p (*regs
, GET_MODE (reg
), REGNO (reg
)))
495 else if (TYPE_P (decl
) || TREE_CODE (decl
) == PARM_DECL
)
500 /* If there is an overlap between *REGS and DECL, return the first overlap
503 tree_overlaps_hard_reg_set (tree decl
, HARD_REG_SET
*regs
)
505 return walk_tree (&decl
, decl_overlaps_hard_reg_set_p
, regs
, NULL
);
509 /* A subroutine of expand_asm_operands. Check that all operand names
510 are unique. Return true if so. We rely on the fact that these names
511 are identifiers, and so have been canonicalized by get_identifier,
512 so all we need are pointer comparisons. */
515 check_unique_operand_names (tree outputs
, tree inputs
, tree labels
)
517 tree i
, j
, i_name
= NULL_TREE
;
519 for (i
= outputs
; i
; i
= TREE_CHAIN (i
))
521 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
525 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
526 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
530 for (i
= inputs
; i
; i
= TREE_CHAIN (i
))
532 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
536 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
537 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
539 for (j
= outputs
; j
; j
= TREE_CHAIN (j
))
540 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
544 for (i
= labels
; i
; i
= TREE_CHAIN (i
))
546 i_name
= TREE_PURPOSE (i
);
550 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
551 if (simple_cst_equal (i_name
, TREE_PURPOSE (j
)))
553 for (j
= inputs
; j
; j
= TREE_CHAIN (j
))
554 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
561 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name
));
565 /* A subroutine of expand_asm_operands. Resolve the names of the operands
566 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
567 STRING and in the constraints to those numbers. */
570 resolve_asm_operand_names (tree string
, tree outputs
, tree inputs
, tree labels
)
577 check_unique_operand_names (outputs
, inputs
, labels
);
579 /* Substitute [<name>] in input constraint strings. There should be no
580 named operands in output constraints. */
581 for (t
= inputs
; t
; t
= TREE_CHAIN (t
))
583 c
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
584 if (strchr (c
, '[') != NULL
)
586 p
= buffer
= xstrdup (c
);
587 while ((p
= strchr (p
, '[')) != NULL
)
588 p
= resolve_operand_name_1 (p
, outputs
, inputs
, NULL
);
589 TREE_VALUE (TREE_PURPOSE (t
))
590 = build_string (strlen (buffer
), buffer
);
595 /* Now check for any needed substitutions in the template. */
596 c
= TREE_STRING_POINTER (string
);
597 while ((c
= strchr (c
, '%')) != NULL
)
601 else if (ISALPHA (c
[1]) && c
[2] == '[')
605 c
+= 1 + (c
[1] == '%');
612 /* OK, we need to make a copy so we can perform the substitutions.
613 Assume that we will not need extra space--we get to remove '['
614 and ']', which means we cannot have a problem until we have more
615 than 999 operands. */
616 buffer
= xstrdup (TREE_STRING_POINTER (string
));
617 p
= buffer
+ (c
- TREE_STRING_POINTER (string
));
619 while ((p
= strchr (p
, '%')) != NULL
)
623 else if (ISALPHA (p
[1]) && p
[2] == '[')
627 p
+= 1 + (p
[1] == '%');
631 p
= resolve_operand_name_1 (p
, outputs
, inputs
, labels
);
634 string
= build_string (strlen (buffer
), buffer
);
641 /* A subroutine of resolve_operand_names. P points to the '[' for a
642 potential named operand of the form [<name>]. In place, replace
643 the name and brackets with a number. Return a pointer to the
644 balance of the string after substitution. */
647 resolve_operand_name_1 (char *p
, tree outputs
, tree inputs
, tree labels
)
653 /* Collect the operand name. */
654 q
= strchr (++p
, ']');
657 error ("missing close brace for named operand");
658 return strchr (p
, '\0');
662 /* Resolve the name to a number. */
663 for (op
= 0, t
= outputs
; 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
= inputs
; 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
= labels
; t
; t
= TREE_CHAIN (t
), op
++)
677 tree name
= TREE_PURPOSE (t
);
678 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
682 error ("undefined named operand %qs", identifier_to_locale (p
));
686 /* Replace the name with the number. Unfortunately, not all libraries
687 get the return value of sprintf correct, so search for the end of the
688 generated string by hand. */
689 sprintf (--p
, "%d", op
);
690 p
= strchr (p
, '\0');
692 /* Verify the no extra buffer space assumption. */
695 /* Shift the rest of the buffer down to fill the gap. */
696 memmove (p
, q
+ 1, strlen (q
+ 1) + 1);
702 /* Generate RTL to return directly from the current function.
703 (That is, we bypass any return value.) */
706 expand_naked_return (void)
710 clear_pending_stack_adjust ();
711 do_pending_stack_adjust ();
713 end_label
= naked_return_label
;
715 end_label
= naked_return_label
= gen_label_rtx ();
717 emit_jump (end_label
);
720 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
721 is the probability of jumping to LABEL. */
723 do_jump_if_equal (machine_mode mode
, rtx op0
, rtx op1
, rtx label
,
724 int unsignedp
, int prob
)
726 gcc_assert (prob
<= REG_BR_PROB_BASE
);
727 do_compare_rtx_and_jump (op0
, op1
, EQ
, unsignedp
, mode
,
728 NULL_RTX
, NULL_RTX
, label
, prob
);
731 /* Do the insertion of a case label into case_list. The labels are
732 fed to us in descending order from the sorted vector of case labels used
733 in the tree part of the middle end. So the list we construct is
734 sorted in ascending order.
736 LABEL is the case label to be inserted. LOW and HIGH are the bounds
737 against which the index is compared to jump to LABEL and PROB is the
738 estimated probability LABEL is reached from the switch statement. */
740 static struct case_node
*
741 add_case_node (struct case_node
*head
, tree low
, tree high
,
742 tree label
, int prob
, alloc_pool case_node_pool
)
746 gcc_checking_assert (low
);
747 gcc_checking_assert (high
&& (TREE_TYPE (low
) == TREE_TYPE (high
)));
749 /* Add this label to the chain. */
750 r
= (struct case_node
*) pool_alloc (case_node_pool
);
753 r
->code_label
= label
;
754 r
->parent
= r
->left
= NULL
;
756 r
->subtree_prob
= prob
;
761 /* Dump ROOT, a list or tree of case nodes, to file. */
764 dump_case_nodes (FILE *f
, struct case_node
*root
,
765 int indent_step
, int indent_level
)
771 dump_case_nodes (f
, root
->left
, indent_step
, indent_level
);
774 fprintf (f
, "%*s", indent_step
* indent_level
, "");
775 print_dec (root
->low
, f
, TYPE_SIGN (TREE_TYPE (root
->low
)));
776 if (!tree_int_cst_equal (root
->low
, root
->high
))
778 fprintf (f
, " ... ");
779 print_dec (root
->high
, f
, TYPE_SIGN (TREE_TYPE (root
->high
)));
783 dump_case_nodes (f
, root
->right
, indent_step
, indent_level
);
787 #define HAVE_casesi 0
790 #ifndef HAVE_tablejump
791 #define HAVE_tablejump 0
794 /* Return the smallest number of different values for which it is best to use a
795 jump-table instead of a tree of conditional branches. */
798 case_values_threshold (void)
800 unsigned int threshold
= PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD
);
803 threshold
= targetm
.case_values_threshold ();
808 /* Return true if a switch should be expanded as a decision tree.
809 RANGE is the difference between highest and lowest case.
810 UNIQ is number of unique case node targets, not counting the default case.
811 COUNT is the number of comparisons needed, not counting the default case. */
814 expand_switch_as_decision_tree_p (tree range
,
815 unsigned int uniq ATTRIBUTE_UNUSED
,
820 /* If neither casesi or tablejump is available, or flag_jump_tables
821 over-ruled us, we really have no choice. */
822 if (!HAVE_casesi
&& !HAVE_tablejump
)
824 if (!flag_jump_tables
)
826 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
831 /* If the switch is relatively small such that the cost of one
832 indirect jump on the target are higher than the cost of a
833 decision tree, go with the decision tree.
835 If range of values is much bigger than number of values,
836 or if it is too large to represent in a HOST_WIDE_INT,
837 make a sequence of conditional branches instead of a dispatch.
839 The definition of "much bigger" depends on whether we are
840 optimizing for size or for speed. If the former, the maximum
841 ratio range/count = 3, because this was found to be the optimal
842 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
843 10 is much older, and was probably selected after an extensive
844 benchmarking investigation on numerous platforms. Or maybe it
845 just made sense to someone at some point in the history of GCC,
847 max_ratio
= optimize_insn_for_size_p () ? 3 : 10;
848 if (count
< case_values_threshold ()
849 || ! tree_fits_uhwi_p (range
)
850 || compare_tree_int (range
, max_ratio
* count
) > 0)
856 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
857 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
858 DEFAULT_PROB is the estimated probability that it jumps to
861 We generate a binary decision tree to select the appropriate target
862 code. This is done as follows:
864 If the index is a short or char that we do not have
865 an insn to handle comparisons directly, convert it to
866 a full integer now, rather than letting each comparison
867 generate the conversion.
869 Load the index into a register.
871 The list of cases is rearranged into a binary tree,
872 nearly optimal assuming equal probability for each case.
874 The tree is transformed into RTL, eliminating redundant
875 test conditions at the same time.
877 If program flow could reach the end of the decision tree
878 an unconditional jump to the default code is emitted.
880 The above process is unaware of the CFG. The caller has to fix up
881 the CFG itself. This is done in cfgexpand.c. */
884 emit_case_decision_tree (tree index_expr
, tree index_type
,
885 struct case_node
*case_list
, rtx default_label
,
888 rtx index
= expand_normal (index_expr
);
890 if (GET_MODE_CLASS (GET_MODE (index
)) == MODE_INT
891 && ! have_insn_for (COMPARE
, GET_MODE (index
)))
893 int unsignedp
= TYPE_UNSIGNED (index_type
);
894 machine_mode wider_mode
;
895 for (wider_mode
= GET_MODE (index
); wider_mode
!= VOIDmode
;
896 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
897 if (have_insn_for (COMPARE
, wider_mode
))
899 index
= convert_to_mode (wider_mode
, index
, unsignedp
);
904 do_pending_stack_adjust ();
908 index
= copy_to_reg (index
);
909 if (TREE_CODE (index_expr
) == SSA_NAME
)
910 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr
), index
);
913 balance_case_nodes (&case_list
, NULL
);
915 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
917 int indent_step
= ceil_log2 (TYPE_PRECISION (index_type
)) + 2;
918 fprintf (dump_file
, ";; Expanding GIMPLE switch as decision tree:\n");
919 dump_case_nodes (dump_file
, case_list
, indent_step
, 0);
922 emit_case_nodes (index
, case_list
, default_label
, default_prob
, index_type
);
924 emit_jump (default_label
);
927 /* Return the sum of probabilities of outgoing edges of basic block BB. */
930 get_outgoing_edge_probs (basic_block bb
)
937 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
938 prob_sum
+= e
->probability
;
942 /* Computes the conditional probability of jumping to a target if the branch
943 instruction is executed.
944 TARGET_PROB is the estimated probability of jumping to a target relative
945 to some basic block BB.
946 BASE_PROB is the probability of reaching the branch instruction relative
947 to the same basic block BB. */
950 conditional_probability (int target_prob
, int base_prob
)
954 gcc_assert (target_prob
>= 0);
955 gcc_assert (target_prob
<= base_prob
);
956 return GCOV_COMPUTE_SCALE (target_prob
, base_prob
);
961 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
962 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
963 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
964 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
966 First, a jump insn is emitted. First we try "casesi". If that
967 fails, try "tablejump". A target *must* have one of them (or both).
969 Then, a table with the target labels is emitted.
971 The process is unaware of the CFG. The caller has to fix up
972 the CFG itself. This is done in cfgexpand.c. */
975 emit_case_dispatch_table (tree index_expr
, tree index_type
,
976 struct case_node
*case_list
, rtx default_label
,
977 tree minval
, tree maxval
, tree range
,
983 rtx fallback_label
= label_rtx (case_list
->code_label
);
984 rtx_code_label
*table_label
= gen_label_rtx ();
985 bool has_gaps
= false;
986 edge default_edge
= stmt_bb
? EDGE_SUCC (stmt_bb
, 0) : NULL
;
987 int default_prob
= default_edge
? default_edge
->probability
: 0;
988 int base
= get_outgoing_edge_probs (stmt_bb
);
989 bool try_with_tablejump
= false;
991 int new_default_prob
= conditional_probability (default_prob
,
994 if (! try_casesi (index_type
, index_expr
, minval
, range
,
995 table_label
, default_label
, fallback_label
,
998 /* Index jumptables from zero for suitable values of minval to avoid
999 a subtraction. For the rationale see:
1000 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
1001 if (optimize_insn_for_speed_p ()
1002 && compare_tree_int (minval
, 0) > 0
1003 && compare_tree_int (minval
, 3) < 0)
1005 minval
= build_int_cst (index_type
, 0);
1009 try_with_tablejump
= true;
1012 /* Get table of labels to jump to, in order of case index. */
1014 ncases
= tree_to_shwi (range
) + 1;
1015 labelvec
= XALLOCAVEC (rtx
, ncases
);
1016 memset (labelvec
, 0, ncases
* sizeof (rtx
));
1018 for (n
= case_list
; n
; n
= n
->right
)
1020 /* Compute the low and high bounds relative to the minimum
1021 value since that should fit in a HOST_WIDE_INT while the
1022 actual values may not. */
1024 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1026 HOST_WIDE_INT i_high
1027 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1031 for (i
= i_low
; i
<= i_high
; i
++)
1033 = gen_rtx_LABEL_REF (Pmode
, label_rtx (n
->code_label
));
1036 /* Fill in the gaps with the default. We may have gaps at
1037 the beginning if we tried to avoid the minval subtraction,
1038 so substitute some label even if the default label was
1039 deemed unreachable. */
1041 default_label
= fallback_label
;
1042 for (i
= 0; i
< ncases
; i
++)
1043 if (labelvec
[i
] == 0)
1046 labelvec
[i
] = gen_rtx_LABEL_REF (Pmode
, default_label
);
1051 /* There is at least one entry in the jump table that jumps
1052 to default label. The default label can either be reached
1053 through the indirect jump or the direct conditional jump
1054 before that. Split the probability of reaching the
1055 default label among these two jumps. */
1056 new_default_prob
= conditional_probability (default_prob
/2,
1059 base
-= default_prob
;
1063 base
-= default_prob
;
1068 default_edge
->probability
= default_prob
;
1070 /* We have altered the probability of the default edge. So the probabilities
1071 of all other edges need to be adjusted so that it sums up to
1072 REG_BR_PROB_BASE. */
1077 FOR_EACH_EDGE (e
, ei
, stmt_bb
->succs
)
1078 e
->probability
= GCOV_COMPUTE_SCALE (e
->probability
, base
);
1081 if (try_with_tablejump
)
1083 bool ok
= try_tablejump (index_type
, index_expr
, minval
, range
,
1084 table_label
, default_label
, new_default_prob
);
1087 /* Output the table. */
1088 emit_label (table_label
);
1090 if (CASE_VECTOR_PC_RELATIVE
|| flag_pic
)
1091 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE
,
1092 gen_rtx_LABEL_REF (Pmode
,
1094 gen_rtvec_v (ncases
, labelvec
),
1095 const0_rtx
, const0_rtx
));
1097 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE
,
1098 gen_rtvec_v (ncases
, labelvec
)));
1100 /* Record no drop-through after the table. */
1104 /* Reset the aux field of all outgoing edges of basic block BB. */
1107 reset_out_edges_aux (basic_block bb
)
1111 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1115 /* Compute the number of case labels that correspond to each outgoing edge of
1116 STMT. Record this information in the aux field of the edge. */
1119 compute_cases_per_edge (gswitch
*stmt
)
1121 basic_block bb
= gimple_bb (stmt
);
1122 reset_out_edges_aux (bb
);
1123 int ncases
= gimple_switch_num_labels (stmt
);
1124 for (int i
= ncases
- 1; i
>= 1; --i
)
1126 tree elt
= gimple_switch_label (stmt
, i
);
1127 tree lab
= CASE_LABEL (elt
);
1128 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1129 edge case_edge
= find_edge (bb
, case_bb
);
1130 case_edge
->aux
= (void *)((intptr_t)(case_edge
->aux
) + 1);
1134 /* Terminate a case (Pascal/Ada) or switch (C) statement
1135 in which ORIG_INDEX is the expression to be tested.
1136 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
1137 type as given in the source before any compiler conversions.
1138 Generate the code to test it and jump to the right place. */
1141 expand_case (gswitch
*stmt
)
1143 tree minval
= NULL_TREE
, maxval
= NULL_TREE
, range
= NULL_TREE
;
1144 rtx default_label
= NULL_RTX
;
1145 unsigned int count
, uniq
;
1147 int ncases
= gimple_switch_num_labels (stmt
);
1148 tree index_expr
= gimple_switch_index (stmt
);
1149 tree index_type
= TREE_TYPE (index_expr
);
1151 basic_block bb
= gimple_bb (stmt
);
1153 /* A list of case labels; it is first built as a list and it may then
1154 be rearranged into a nearly balanced binary tree. */
1155 struct case_node
*case_list
= 0;
1157 /* A pool for case nodes. */
1158 alloc_pool case_node_pool
;
1160 /* An ERROR_MARK occurs for various reasons including invalid data type.
1161 ??? Can this still happen, with GIMPLE and all? */
1162 if (index_type
== error_mark_node
)
1165 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
1166 expressions being INTEGER_CST. */
1167 gcc_assert (TREE_CODE (index_expr
) != INTEGER_CST
);
1169 case_node_pool
= create_alloc_pool ("struct case_node pool",
1170 sizeof (struct case_node
),
1173 do_pending_stack_adjust ();
1175 /* Find the default case target label. */
1176 default_label
= label_rtx (CASE_LABEL (gimple_switch_default_label (stmt
)));
1177 edge default_edge
= EDGE_SUCC (bb
, 0);
1178 int default_prob
= default_edge
->probability
;
1180 /* Get upper and lower bounds of case values. */
1181 elt
= gimple_switch_label (stmt
, 1);
1182 minval
= fold_convert (index_type
, CASE_LOW (elt
));
1183 elt
= gimple_switch_label (stmt
, ncases
- 1);
1184 if (CASE_HIGH (elt
))
1185 maxval
= fold_convert (index_type
, CASE_HIGH (elt
));
1187 maxval
= fold_convert (index_type
, CASE_LOW (elt
));
1189 /* Compute span of values. */
1190 range
= fold_build2 (MINUS_EXPR
, index_type
, maxval
, minval
);
1192 /* Listify the labels queue and gather some numbers to decide
1193 how to expand this switch(). */
1196 hash_set
<tree
> seen_labels
;
1197 compute_cases_per_edge (stmt
);
1199 for (i
= ncases
- 1; i
>= 1; --i
)
1201 elt
= gimple_switch_label (stmt
, i
);
1202 tree low
= CASE_LOW (elt
);
1204 tree high
= CASE_HIGH (elt
);
1205 gcc_assert (! high
|| tree_int_cst_lt (low
, high
));
1206 tree lab
= CASE_LABEL (elt
);
1208 /* Count the elements.
1209 A range counts double, since it requires two compares. */
1214 /* If we have not seen this label yet, then increase the
1215 number of unique case node targets seen. */
1216 if (!seen_labels
.add (lab
))
1219 /* The bounds on the case range, LOW and HIGH, have to be converted
1220 to case's index type TYPE. Note that the original type of the
1221 case index in the source code is usually "lost" during
1222 gimplification due to type promotion, but the case labels retain the
1223 original type. Make sure to drop overflow flags. */
1224 low
= fold_convert (index_type
, low
);
1225 if (TREE_OVERFLOW (low
))
1226 low
= wide_int_to_tree (index_type
, low
);
1228 /* The canonical from of a case label in GIMPLE is that a simple case
1229 has an empty CASE_HIGH. For the casesi and tablejump expanders,
1230 the back ends want simple cases to have high == low. */
1233 high
= fold_convert (index_type
, high
);
1234 if (TREE_OVERFLOW (high
))
1235 high
= wide_int_to_tree (index_type
, high
);
1237 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1238 edge case_edge
= find_edge (bb
, case_bb
);
1239 case_list
= add_case_node (
1240 case_list
, low
, high
, lab
,
1241 case_edge
->probability
/ (intptr_t)(case_edge
->aux
),
1244 reset_out_edges_aux (bb
);
1246 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
1247 destination, such as one with a default case only.
1248 It also removes cases that are out of range for the switch
1249 type, so we should never get a zero here. */
1250 gcc_assert (count
> 0);
1252 rtx_insn
*before_case
= get_last_insn ();
1254 /* Decide how to expand this switch.
1255 The two options at this point are a dispatch table (casesi or
1256 tablejump) or a decision tree. */
1258 if (expand_switch_as_decision_tree_p (range
, uniq
, count
))
1259 emit_case_decision_tree (index_expr
, index_type
,
1260 case_list
, default_label
,
1263 emit_case_dispatch_table (index_expr
, index_type
,
1264 case_list
, default_label
,
1265 minval
, maxval
, range
, bb
);
1267 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1270 free_alloc_pool (case_node_pool
);
1273 /* Expand the dispatch to a short decrement chain if there are few cases
1274 to dispatch to. Likewise if neither casesi nor tablejump is available,
1275 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
1276 tablejump. The index mode is always the mode of integer_type_node.
1277 Trap if no case matches the index.
1279 DISPATCH_INDEX is the index expression to switch on. It should be a
1280 memory or register operand.
1282 DISPATCH_TABLE is a set of case labels. The set should be sorted in
1283 ascending order, be contiguous, starting with value 0, and contain only
1284 single-valued case labels. */
1287 expand_sjlj_dispatch_table (rtx dispatch_index
,
1288 vec
<tree
> dispatch_table
)
1290 tree index_type
= integer_type_node
;
1291 machine_mode index_mode
= TYPE_MODE (index_type
);
1293 int ncases
= dispatch_table
.length ();
1295 do_pending_stack_adjust ();
1296 rtx_insn
*before_case
= get_last_insn ();
1298 /* Expand as a decrement-chain if there are 5 or fewer dispatch
1299 labels. This covers more than 98% of the cases in libjava,
1300 and seems to be a reasonable compromise between the "old way"
1301 of expanding as a decision tree or dispatch table vs. the "new
1302 way" with decrement chain or dispatch table. */
1303 if (dispatch_table
.length () <= 5
1304 || (!HAVE_casesi
&& !HAVE_tablejump
)
1305 || !flag_jump_tables
)
1307 /* Expand the dispatch as a decrement chain:
1309 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1313 if (index == 0) do_0; else index--;
1314 if (index == 0) do_1; else index--;
1316 if (index == 0) do_N; else index--;
1318 This is more efficient than a dispatch table on most machines.
1319 The last "index--" is redundant but the code is trivially dead
1320 and will be cleaned up by later passes. */
1321 rtx index
= copy_to_mode_reg (index_mode
, dispatch_index
);
1322 rtx zero
= CONST0_RTX (index_mode
);
1323 for (int i
= 0; i
< ncases
; i
++)
1325 tree elt
= dispatch_table
[i
];
1326 rtx lab
= label_rtx (CASE_LABEL (elt
));
1327 do_jump_if_equal (index_mode
, index
, zero
, lab
, 0, -1);
1328 force_expand_binop (index_mode
, sub_optab
,
1329 index
, CONST1_RTX (index_mode
),
1330 index
, 0, OPTAB_DIRECT
);
1335 /* Similar to expand_case, but much simpler. */
1336 struct case_node
*case_list
= 0;
1337 alloc_pool case_node_pool
= create_alloc_pool ("struct sjlj_case pool",
1338 sizeof (struct case_node
),
1340 tree index_expr
= make_tree (index_type
, dispatch_index
);
1341 tree minval
= build_int_cst (index_type
, 0);
1342 tree maxval
= CASE_LOW (dispatch_table
.last ());
1343 tree range
= maxval
;
1344 rtx_code_label
*default_label
= gen_label_rtx ();
1346 for (int i
= ncases
- 1; i
>= 0; --i
)
1348 tree elt
= dispatch_table
[i
];
1349 tree low
= CASE_LOW (elt
);
1350 tree lab
= CASE_LABEL (elt
);
1351 case_list
= add_case_node (case_list
, low
, low
, lab
, 0, case_node_pool
);
1354 emit_case_dispatch_table (index_expr
, index_type
,
1355 case_list
, default_label
,
1356 minval
, maxval
, range
,
1357 BLOCK_FOR_INSN (before_case
));
1358 emit_label (default_label
);
1359 free_alloc_pool (case_node_pool
);
1362 /* Dispatching something not handled? Trap! */
1363 expand_builtin_trap ();
1365 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1371 /* Take an ordered list of case nodes
1372 and transform them into a near optimal binary tree,
1373 on the assumption that any target code selection value is as
1374 likely as any other.
1376 The transformation is performed by splitting the ordered
1377 list into two equal sections plus a pivot. The parts are
1378 then attached to the pivot as left and right branches. Each
1379 branch is then transformed recursively. */
1382 balance_case_nodes (case_node_ptr
*head
, case_node_ptr parent
)
1394 /* Count the number of entries on branch. Also count the ranges. */
1398 if (!tree_int_cst_equal (np
->low
, np
->high
))
1407 /* Split this list if it is long enough for that to help. */
1411 /* If there are just three nodes, split at the middle one. */
1413 npp
= &(*npp
)->right
;
1416 /* Find the place in the list that bisects the list's total cost,
1417 where ranges count as 2.
1418 Here I gets half the total cost. */
1419 i
= (i
+ ranges
+ 1) / 2;
1422 /* Skip nodes while their cost does not reach that amount. */
1423 if (!tree_int_cst_equal ((*npp
)->low
, (*npp
)->high
))
1428 npp
= &(*npp
)->right
;
1433 np
->parent
= parent
;
1436 /* Optimize each of the two split parts. */
1437 balance_case_nodes (&np
->left
, np
);
1438 balance_case_nodes (&np
->right
, np
);
1439 np
->subtree_prob
= np
->prob
;
1440 np
->subtree_prob
+= np
->left
->subtree_prob
;
1441 np
->subtree_prob
+= np
->right
->subtree_prob
;
1445 /* Else leave this branch as one level,
1446 but fill in `parent' fields. */
1448 np
->parent
= parent
;
1449 np
->subtree_prob
= np
->prob
;
1450 for (; np
->right
; np
= np
->right
)
1452 np
->right
->parent
= np
;
1453 (*head
)->subtree_prob
+= np
->right
->subtree_prob
;
1459 /* Search the parent sections of the case node tree
1460 to see if a test for the lower bound of NODE would be redundant.
1461 INDEX_TYPE is the type of the index expression.
1463 The instructions to generate the case decision tree are
1464 output in the same order as nodes are processed so it is
1465 known that if a parent node checks the range of the current
1466 node minus one that the current node is bounded at its lower
1467 span. Thus the test would be redundant. */
1470 node_has_low_bound (case_node_ptr node
, tree index_type
)
1473 case_node_ptr pnode
;
1475 /* If the lower bound of this node is the lowest value in the index type,
1476 we need not test it. */
1478 if (tree_int_cst_equal (node
->low
, TYPE_MIN_VALUE (index_type
)))
1481 /* If this node has a left branch, the value at the left must be less
1482 than that at this node, so it cannot be bounded at the bottom and
1483 we need not bother testing any further. */
1488 low_minus_one
= fold_build2 (MINUS_EXPR
, TREE_TYPE (node
->low
),
1490 build_int_cst (TREE_TYPE (node
->low
), 1));
1492 /* If the subtraction above overflowed, we can't verify anything.
1493 Otherwise, look for a parent that tests our value - 1. */
1495 if (! tree_int_cst_lt (low_minus_one
, node
->low
))
1498 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1499 if (tree_int_cst_equal (low_minus_one
, pnode
->high
))
1505 /* Search the parent sections of the case node tree
1506 to see if a test for the upper bound of NODE would be redundant.
1507 INDEX_TYPE is the type of the index expression.
1509 The instructions to generate the case decision tree are
1510 output in the same order as nodes are processed so it is
1511 known that if a parent node checks the range of the current
1512 node plus one that the current node is bounded at its upper
1513 span. Thus the test would be redundant. */
1516 node_has_high_bound (case_node_ptr node
, tree index_type
)
1519 case_node_ptr pnode
;
1521 /* If there is no upper bound, obviously no test is needed. */
1523 if (TYPE_MAX_VALUE (index_type
) == NULL
)
1526 /* If the upper bound of this node is the highest value in the type
1527 of the index expression, we need not test against it. */
1529 if (tree_int_cst_equal (node
->high
, TYPE_MAX_VALUE (index_type
)))
1532 /* If this node has a right branch, the value at the right must be greater
1533 than that at this node, so it cannot be bounded at the top and
1534 we need not bother testing any further. */
1539 high_plus_one
= fold_build2 (PLUS_EXPR
, TREE_TYPE (node
->high
),
1541 build_int_cst (TREE_TYPE (node
->high
), 1));
1543 /* If the addition above overflowed, we can't verify anything.
1544 Otherwise, look for a parent that tests our value + 1. */
1546 if (! tree_int_cst_lt (node
->high
, high_plus_one
))
1549 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1550 if (tree_int_cst_equal (high_plus_one
, pnode
->low
))
1556 /* Search the parent sections of the
1557 case node tree to see if both tests for the upper and lower
1558 bounds of NODE would be redundant. */
1561 node_is_bounded (case_node_ptr node
, tree index_type
)
1563 return (node_has_low_bound (node
, index_type
)
1564 && node_has_high_bound (node
, index_type
));
1568 /* Emit step-by-step code to select a case for the value of INDEX.
1569 The thus generated decision tree follows the form of the
1570 case-node binary tree NODE, whose nodes represent test conditions.
1571 INDEX_TYPE is the type of the index of the switch.
1573 Care is taken to prune redundant tests from the decision tree
1574 by detecting any boundary conditions already checked by
1575 emitted rtx. (See node_has_high_bound, node_has_low_bound
1576 and node_is_bounded, above.)
1578 Where the test conditions can be shown to be redundant we emit
1579 an unconditional jump to the target code. As a further
1580 optimization, the subordinates of a tree node are examined to
1581 check for bounded nodes. In this case conditional and/or
1582 unconditional jumps as a result of the boundary check for the
1583 current node are arranged to target the subordinates associated
1584 code for out of bound conditions on the current node.
1586 We can assume that when control reaches the code generated here,
1587 the index value has already been compared with the parents
1588 of this node, and determined to be on the same side of each parent
1589 as this node is. Thus, if this node tests for the value 51,
1590 and a parent tested for 52, we don't need to consider
1591 the possibility of a value greater than 51. If another parent
1592 tests for the value 50, then this node need not test anything. */
1595 emit_case_nodes (rtx index
, case_node_ptr node
, rtx default_label
,
1596 int default_prob
, tree index_type
)
1598 /* If INDEX has an unsigned type, we must make unsigned branches. */
1599 int unsignedp
= TYPE_UNSIGNED (index_type
);
1601 int prob
= node
->prob
, subtree_prob
= node
->subtree_prob
;
1602 machine_mode mode
= GET_MODE (index
);
1603 machine_mode imode
= TYPE_MODE (index_type
);
1605 /* Handle indices detected as constant during RTL expansion. */
1606 if (mode
== VOIDmode
)
1609 /* See if our parents have already tested everything for us.
1610 If they have, emit an unconditional jump for this node. */
1611 if (node_is_bounded (node
, index_type
))
1612 emit_jump (label_rtx (node
->code_label
));
1614 else if (tree_int_cst_equal (node
->low
, node
->high
))
1616 probability
= conditional_probability (prob
, subtree_prob
+ default_prob
);
1617 /* Node is single valued. First see if the index expression matches
1618 this node and then check our children, if any. */
1619 do_jump_if_equal (mode
, index
,
1620 convert_modes (mode
, imode
,
1621 expand_normal (node
->low
),
1623 label_rtx (node
->code_label
), unsignedp
, probability
);
1624 /* Since this case is taken at this point, reduce its weight from
1626 subtree_prob
-= prob
;
1627 if (node
->right
!= 0 && node
->left
!= 0)
1629 /* This node has children on both sides.
1630 Dispatch to one side or the other
1631 by comparing the index value with this node's value.
1632 If one subtree is bounded, check that one first,
1633 so we can avoid real branches in the tree. */
1635 if (node_is_bounded (node
->right
, index_type
))
1637 probability
= conditional_probability (
1639 subtree_prob
+ default_prob
);
1640 emit_cmp_and_jump_insns (index
,
1643 expand_normal (node
->high
),
1645 GT
, NULL_RTX
, mode
, unsignedp
,
1646 label_rtx (node
->right
->code_label
),
1648 emit_case_nodes (index
, node
->left
, default_label
, default_prob
,
1652 else if (node_is_bounded (node
->left
, index_type
))
1654 probability
= conditional_probability (
1656 subtree_prob
+ default_prob
);
1657 emit_cmp_and_jump_insns (index
,
1660 expand_normal (node
->high
),
1662 LT
, NULL_RTX
, mode
, unsignedp
,
1663 label_rtx (node
->left
->code_label
),
1665 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1668 /* If both children are single-valued cases with no
1669 children, finish up all the work. This way, we can save
1670 one ordered comparison. */
1671 else if (tree_int_cst_equal (node
->right
->low
, node
->right
->high
)
1672 && node
->right
->left
== 0
1673 && node
->right
->right
== 0
1674 && tree_int_cst_equal (node
->left
->low
, node
->left
->high
)
1675 && node
->left
->left
== 0
1676 && node
->left
->right
== 0)
1678 /* Neither node is bounded. First distinguish the two sides;
1679 then emit the code for one side at a time. */
1681 /* See if the value matches what the right hand side
1683 probability
= conditional_probability (
1685 subtree_prob
+ default_prob
);
1686 do_jump_if_equal (mode
, index
,
1687 convert_modes (mode
, imode
,
1688 expand_normal (node
->right
->low
),
1690 label_rtx (node
->right
->code_label
),
1691 unsignedp
, probability
);
1693 /* See if the value matches what the left hand side
1695 probability
= conditional_probability (
1697 subtree_prob
+ default_prob
);
1698 do_jump_if_equal (mode
, index
,
1699 convert_modes (mode
, imode
,
1700 expand_normal (node
->left
->low
),
1702 label_rtx (node
->left
->code_label
),
1703 unsignedp
, probability
);
1708 /* Neither node is bounded. First distinguish the two sides;
1709 then emit the code for one side at a time. */
1712 = build_decl (curr_insn_location (),
1713 LABEL_DECL
, NULL_TREE
, void_type_node
);
1715 /* The default label could be reached either through the right
1716 subtree or the left subtree. Divide the probability
1718 probability
= conditional_probability (
1719 node
->right
->subtree_prob
+ default_prob
/2,
1720 subtree_prob
+ default_prob
);
1721 /* See if the value is on the right. */
1722 emit_cmp_and_jump_insns (index
,
1725 expand_normal (node
->high
),
1727 GT
, NULL_RTX
, mode
, unsignedp
,
1728 label_rtx (test_label
),
1732 /* Value must be on the left.
1733 Handle the left-hand subtree. */
1734 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1735 /* If left-hand subtree does nothing,
1738 emit_jump (default_label
);
1740 /* Code branches here for the right-hand subtree. */
1741 expand_label (test_label
);
1742 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1746 else if (node
->right
!= 0 && node
->left
== 0)
1748 /* Here we have a right child but no left so we issue a conditional
1749 branch to default and process the right child.
1751 Omit the conditional branch to default if the right child
1752 does not have any children and is single valued; it would
1753 cost too much space to save so little time. */
1755 if (node
->right
->right
|| node
->right
->left
1756 || !tree_int_cst_equal (node
->right
->low
, node
->right
->high
))
1758 if (!node_has_low_bound (node
, index_type
))
1760 probability
= conditional_probability (
1762 subtree_prob
+ default_prob
);
1763 emit_cmp_and_jump_insns (index
,
1766 expand_normal (node
->high
),
1768 LT
, NULL_RTX
, mode
, unsignedp
,
1774 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1778 probability
= conditional_probability (
1779 node
->right
->subtree_prob
,
1780 subtree_prob
+ default_prob
);
1781 /* We cannot process node->right normally
1782 since we haven't ruled out the numbers less than
1783 this node's value. So handle node->right explicitly. */
1784 do_jump_if_equal (mode
, index
,
1787 expand_normal (node
->right
->low
),
1789 label_rtx (node
->right
->code_label
), unsignedp
, probability
);
1793 else if (node
->right
== 0 && node
->left
!= 0)
1795 /* Just one subtree, on the left. */
1796 if (node
->left
->left
|| node
->left
->right
1797 || !tree_int_cst_equal (node
->left
->low
, node
->left
->high
))
1799 if (!node_has_high_bound (node
, index_type
))
1801 probability
= conditional_probability (
1803 subtree_prob
+ default_prob
);
1804 emit_cmp_and_jump_insns (index
,
1807 expand_normal (node
->high
),
1809 GT
, NULL_RTX
, mode
, unsignedp
,
1815 emit_case_nodes (index
, node
->left
, default_label
,
1816 default_prob
, index_type
);
1820 probability
= conditional_probability (
1821 node
->left
->subtree_prob
,
1822 subtree_prob
+ default_prob
);
1823 /* We cannot process node->left normally
1824 since we haven't ruled out the numbers less than
1825 this node's value. So handle node->left explicitly. */
1826 do_jump_if_equal (mode
, index
,
1829 expand_normal (node
->left
->low
),
1831 label_rtx (node
->left
->code_label
), unsignedp
, probability
);
1837 /* Node is a range. These cases are very similar to those for a single
1838 value, except that we do not start by testing whether this node
1839 is the one to branch to. */
1841 if (node
->right
!= 0 && node
->left
!= 0)
1843 /* Node has subtrees on both sides.
1844 If the right-hand subtree is bounded,
1845 test for it first, since we can go straight there.
1846 Otherwise, we need to make a branch in the control structure,
1847 then handle the two subtrees. */
1848 tree test_label
= 0;
1850 if (node_is_bounded (node
->right
, index_type
))
1852 /* Right hand node is fully bounded so we can eliminate any
1853 testing and branch directly to the target code. */
1854 probability
= conditional_probability (
1855 node
->right
->subtree_prob
,
1856 subtree_prob
+ default_prob
);
1857 emit_cmp_and_jump_insns (index
,
1860 expand_normal (node
->high
),
1862 GT
, NULL_RTX
, mode
, unsignedp
,
1863 label_rtx (node
->right
->code_label
),
1868 /* Right hand node requires testing.
1869 Branch to a label where we will handle it later. */
1871 test_label
= build_decl (curr_insn_location (),
1872 LABEL_DECL
, NULL_TREE
, void_type_node
);
1873 probability
= conditional_probability (
1874 node
->right
->subtree_prob
+ default_prob
/2,
1875 subtree_prob
+ default_prob
);
1876 emit_cmp_and_jump_insns (index
,
1879 expand_normal (node
->high
),
1881 GT
, NULL_RTX
, mode
, unsignedp
,
1882 label_rtx (test_label
),
1887 /* Value belongs to this node or to the left-hand subtree. */
1889 probability
= conditional_probability (
1891 subtree_prob
+ default_prob
);
1892 emit_cmp_and_jump_insns (index
,
1895 expand_normal (node
->low
),
1897 GE
, NULL_RTX
, mode
, unsignedp
,
1898 label_rtx (node
->code_label
),
1901 /* Handle the left-hand subtree. */
1902 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1904 /* If right node had to be handled later, do that now. */
1908 /* If the left-hand subtree fell through,
1909 don't let it fall into the right-hand subtree. */
1911 emit_jump (default_label
);
1913 expand_label (test_label
);
1914 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1918 else if (node
->right
!= 0 && node
->left
== 0)
1920 /* Deal with values to the left of this node,
1921 if they are possible. */
1922 if (!node_has_low_bound (node
, index_type
))
1924 probability
= conditional_probability (
1926 subtree_prob
+ default_prob
);
1927 emit_cmp_and_jump_insns (index
,
1930 expand_normal (node
->low
),
1932 LT
, NULL_RTX
, mode
, unsignedp
,
1938 /* Value belongs to this node or to the right-hand subtree. */
1940 probability
= conditional_probability (
1942 subtree_prob
+ default_prob
);
1943 emit_cmp_and_jump_insns (index
,
1946 expand_normal (node
->high
),
1948 LE
, NULL_RTX
, mode
, unsignedp
,
1949 label_rtx (node
->code_label
),
1952 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1955 else if (node
->right
== 0 && node
->left
!= 0)
1957 /* Deal with values to the right of this node,
1958 if they are possible. */
1959 if (!node_has_high_bound (node
, index_type
))
1961 probability
= conditional_probability (
1963 subtree_prob
+ default_prob
);
1964 emit_cmp_and_jump_insns (index
,
1967 expand_normal (node
->high
),
1969 GT
, NULL_RTX
, mode
, unsignedp
,
1975 /* Value belongs to this node or to the left-hand subtree. */
1977 probability
= conditional_probability (
1979 subtree_prob
+ default_prob
);
1980 emit_cmp_and_jump_insns (index
,
1983 expand_normal (node
->low
),
1985 GE
, NULL_RTX
, mode
, unsignedp
,
1986 label_rtx (node
->code_label
),
1989 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1994 /* Node has no children so we check low and high bounds to remove
1995 redundant tests. Only one of the bounds can exist,
1996 since otherwise this node is bounded--a case tested already. */
1997 int high_bound
= node_has_high_bound (node
, index_type
);
1998 int low_bound
= node_has_low_bound (node
, index_type
);
2000 if (!high_bound
&& low_bound
)
2002 probability
= conditional_probability (
2004 subtree_prob
+ default_prob
);
2005 emit_cmp_and_jump_insns (index
,
2008 expand_normal (node
->high
),
2010 GT
, NULL_RTX
, mode
, unsignedp
,
2015 else if (!low_bound
&& high_bound
)
2017 probability
= conditional_probability (
2019 subtree_prob
+ default_prob
);
2020 emit_cmp_and_jump_insns (index
,
2023 expand_normal (node
->low
),
2025 LT
, NULL_RTX
, mode
, unsignedp
,
2029 else if (!low_bound
&& !high_bound
)
2031 /* Widen LOW and HIGH to the same width as INDEX. */
2032 tree type
= lang_hooks
.types
.type_for_mode (mode
, unsignedp
);
2033 tree low
= build1 (CONVERT_EXPR
, type
, node
->low
);
2034 tree high
= build1 (CONVERT_EXPR
, type
, node
->high
);
2035 rtx low_rtx
, new_index
, new_bound
;
2037 /* Instead of doing two branches, emit one unsigned branch for
2038 (index-low) > (high-low). */
2039 low_rtx
= expand_expr (low
, NULL_RTX
, mode
, EXPAND_NORMAL
);
2040 new_index
= expand_simple_binop (mode
, MINUS
, index
, low_rtx
,
2041 NULL_RTX
, unsignedp
,
2043 new_bound
= expand_expr (fold_build2 (MINUS_EXPR
, type
,
2045 NULL_RTX
, mode
, EXPAND_NORMAL
);
2047 probability
= conditional_probability (
2049 subtree_prob
+ default_prob
);
2050 emit_cmp_and_jump_insns (new_index
, new_bound
, GT
, NULL_RTX
,
2051 mode
, 1, default_label
, probability
);
2054 emit_jump (label_rtx (node
->code_label
));