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 "fold-const.h"
37 #include "stor-layout.h"
42 #include "insn-config.h"
52 #include "diagnostic-core.h"
54 #include "langhooks.h"
56 #include "insn-codes.h"
60 #include "basic-block.h"
61 #include "tree-ssa-alias.h"
62 #include "internal-fn.h"
63 #include "gimple-expr.h"
66 #include "alloc-pool.h"
67 #include "pretty-print.h"
73 /* Functions and data structures for expanding case statements. */
75 /* Case label structure, used to hold info on labels within case
76 statements. We handle "range" labels; for a single-value label
77 as in C, the high and low limits are the same.
79 We start with a vector of case nodes sorted in ascending order, and
80 the default label as the last element in the vector. Before expanding
81 to RTL, we transform this vector into a list linked via the RIGHT
82 fields in the case_node struct. Nodes with higher case values are
85 Switch statements can be output in three forms. A branch table is
86 used if there are more than a few labels and the labels are dense
87 within the range between the smallest and largest case value. If a
88 branch table is used, no further manipulations are done with the case
91 The alternative to the use of a branch table is to generate a series
92 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
93 and PARENT fields to hold a binary tree. Initially the tree is
94 totally unbalanced, with everything on the right. We balance the tree
95 with nodes on the left having lower case values than the parent
96 and nodes on the right having higher values. We then output the tree
99 For very small, suitable switch statements, we can generate a series
100 of simple bit test and branches instead. */
104 struct case_node
*left
; /* Left son in binary tree */
105 struct case_node
*right
; /* Right son in binary tree; also node chain */
106 struct case_node
*parent
; /* Parent of node in binary tree */
107 tree low
; /* Lowest index value for this label */
108 tree high
; /* Highest index value for this label */
109 tree code_label
; /* Label to jump to when node matches */
110 int prob
; /* Probability of taking this case. */
111 /* Probability of reaching subtree rooted at this node */
115 typedef struct case_node case_node
;
116 typedef struct case_node
*case_node_ptr
;
118 extern basic_block
label_to_block_fn (struct function
*, tree
);
120 static bool check_unique_operand_names (tree
, tree
, tree
);
121 static char *resolve_operand_name_1 (char *, tree
, tree
, tree
);
122 static void balance_case_nodes (case_node_ptr
*, case_node_ptr
);
123 static int node_has_low_bound (case_node_ptr
, tree
);
124 static int node_has_high_bound (case_node_ptr
, tree
);
125 static int node_is_bounded (case_node_ptr
, tree
);
126 static void emit_case_nodes (rtx
, case_node_ptr
, rtx_code_label
*, int, tree
);
128 /* Return the rtx-label that corresponds to a LABEL_DECL,
129 creating it if necessary. */
132 label_rtx (tree label
)
134 gcc_assert (TREE_CODE (label
) == LABEL_DECL
);
136 if (!DECL_RTL_SET_P (label
))
138 rtx_code_label
*r
= gen_label_rtx ();
139 SET_DECL_RTL (label
, r
);
140 if (FORCED_LABEL (label
) || DECL_NONLOCAL (label
))
141 LABEL_PRESERVE_P (r
) = 1;
144 return as_a
<rtx_insn
*> (DECL_RTL (label
));
147 /* As above, but also put it on the forced-reference list of the
148 function that contains it. */
150 force_label_rtx (tree label
)
152 rtx_insn
*ref
= label_rtx (label
);
153 tree function
= decl_function_context (label
);
155 gcc_assert (function
);
157 forced_labels
= gen_rtx_INSN_LIST (VOIDmode
, ref
, forced_labels
);
161 /* As label_rtx, but ensures (in check build), that returned value is
162 an existing label (i.e. rtx with code CODE_LABEL). */
164 jump_target_rtx (tree label
)
166 return as_a
<rtx_code_label
*> (label_rtx (label
));
169 /* Add an unconditional jump to LABEL as the next sequential instruction. */
172 emit_jump (rtx label
)
174 do_pending_stack_adjust ();
175 emit_jump_insn (targetm
.gen_jump (label
));
179 /* Handle goto statements and the labels that they can go to. */
181 /* Specify the location in the RTL code of a label LABEL,
182 which is a LABEL_DECL tree node.
184 This is used for the kind of label that the user can jump to with a
185 goto statement, and for alternatives of a switch or case statement.
186 RTL labels generated for loops and conditionals don't go through here;
187 they are generated directly at the RTL level, by other functions below.
189 Note that this has nothing to do with defining label *names*.
190 Languages vary in how they do that and what that even means. */
193 expand_label (tree label
)
195 rtx_code_label
*label_r
= jump_target_rtx (label
);
197 do_pending_stack_adjust ();
198 emit_label (label_r
);
199 if (DECL_NAME (label
))
200 LABEL_NAME (DECL_RTL (label
)) = IDENTIFIER_POINTER (DECL_NAME (label
));
202 if (DECL_NONLOCAL (label
))
204 expand_builtin_setjmp_receiver (NULL
);
205 nonlocal_goto_handler_labels
206 = gen_rtx_INSN_LIST (VOIDmode
, label_r
,
207 nonlocal_goto_handler_labels
);
210 if (FORCED_LABEL (label
))
211 forced_labels
= gen_rtx_INSN_LIST (VOIDmode
, label_r
, forced_labels
);
213 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
214 maybe_set_first_label_num (label_r
);
217 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
218 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
219 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
220 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
221 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
222 constraint allows the use of a register operand. And, *IS_INOUT
223 will be true if the operand is read-write, i.e., if it is used as
224 an input as well as an output. If *CONSTRAINT_P is not in
225 canonical form, it will be made canonical. (Note that `+' will be
226 replaced with `=' as part of this process.)
228 Returns TRUE if all went well; FALSE if an error occurred. */
231 parse_output_constraint (const char **constraint_p
, int operand_num
,
232 int ninputs
, int noutputs
, bool *allows_mem
,
233 bool *allows_reg
, bool *is_inout
)
235 const char *constraint
= *constraint_p
;
238 /* Assume the constraint doesn't allow the use of either a register
243 /* Allow the `=' or `+' to not be at the beginning of the string,
244 since it wasn't explicitly documented that way, and there is a
245 large body of code that puts it last. Swap the character to
246 the front, so as not to uglify any place else. */
247 p
= strchr (constraint
, '=');
249 p
= strchr (constraint
, '+');
251 /* If the string doesn't contain an `=', issue an error
255 error ("output operand constraint lacks %<=%>");
259 /* If the constraint begins with `+', then the operand is both read
260 from and written to. */
261 *is_inout
= (*p
== '+');
263 /* Canonicalize the output constraint so that it begins with `='. */
264 if (p
!= constraint
|| *is_inout
)
267 size_t c_len
= strlen (constraint
);
270 warning (0, "output constraint %qc for operand %d "
271 "is not at the beginning",
274 /* Make a copy of the constraint. */
275 buf
= XALLOCAVEC (char, c_len
+ 1);
276 strcpy (buf
, constraint
);
277 /* Swap the first character and the `=' or `+'. */
278 buf
[p
- constraint
] = buf
[0];
279 /* Make sure the first character is an `='. (Until we do this,
280 it might be a `+'.) */
282 /* Replace the constraint with the canonicalized string. */
283 *constraint_p
= ggc_alloc_string (buf
, c_len
);
284 constraint
= *constraint_p
;
287 /* Loop through the constraint string. */
288 for (p
= constraint
+ 1; *p
; p
+= CONSTRAINT_LEN (*p
, p
))
293 error ("operand constraint contains incorrectly positioned "
298 if (operand_num
+ 1 == ninputs
+ noutputs
)
300 error ("%<%%%> constraint used with last operand");
305 case '?': case '!': case '*': case '&': case '#':
307 case 'E': case 'F': case 'G': case 'H':
308 case 's': case 'i': case 'n':
309 case 'I': case 'J': case 'K': case 'L': case 'M':
310 case 'N': case 'O': case 'P': case ',':
313 case '0': case '1': case '2': case '3': case '4':
314 case '5': case '6': case '7': case '8': case '9':
316 error ("matching constraint not valid in output operand");
320 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
321 excepting those that expand_call created. So match memory
334 enum constraint_num cn
= lookup_constraint (p
);
335 if (reg_class_for_constraint (cn
) != NO_REGS
336 || insn_extra_address_constraint (cn
))
338 else if (insn_extra_memory_constraint (cn
))
341 insn_extra_constraint_allows_reg_mem (cn
, allows_reg
, allows_mem
);
348 /* Similar, but for input constraints. */
351 parse_input_constraint (const char **constraint_p
, int input_num
,
352 int ninputs
, int noutputs
, int ninout
,
353 const char * const * constraints
,
354 bool *allows_mem
, bool *allows_reg
)
356 const char *constraint
= *constraint_p
;
357 const char *orig_constraint
= constraint
;
358 size_t c_len
= strlen (constraint
);
360 bool saw_match
= false;
362 /* Assume the constraint doesn't allow the use of either
363 a register or memory. */
367 /* Make sure constraint has neither `=', `+', nor '&'. */
369 for (j
= 0; j
< c_len
; j
+= CONSTRAINT_LEN (constraint
[j
], constraint
+j
))
370 switch (constraint
[j
])
372 case '+': case '=': case '&':
373 if (constraint
== orig_constraint
)
375 error ("input operand constraint contains %qc", constraint
[j
]);
381 if (constraint
== orig_constraint
382 && input_num
+ 1 == ninputs
- ninout
)
384 error ("%<%%%> constraint used with last operand");
390 case '?': case '!': case '*': case '#':
392 case 'E': case 'F': case 'G': case 'H':
393 case 's': case 'i': case 'n':
394 case 'I': case 'J': case 'K': case 'L': case 'M':
395 case 'N': case 'O': case 'P': case ',':
398 /* Whether or not a numeric constraint allows a register is
399 decided by the matching constraint, and so there is no need
400 to do anything special with them. We must handle them in
401 the default case, so that we don't unnecessarily force
402 operands to memory. */
403 case '0': case '1': case '2': case '3': case '4':
404 case '5': case '6': case '7': case '8': case '9':
411 match
= strtoul (constraint
+ j
, &end
, 10);
412 if (match
>= (unsigned long) noutputs
)
414 error ("matching constraint references invalid operand number");
418 /* Try and find the real constraint for this dup. Only do this
419 if the matching constraint is the only alternative. */
421 && (j
== 0 || (j
== 1 && constraint
[0] == '%')))
423 constraint
= constraints
[match
];
424 *constraint_p
= constraint
;
425 c_len
= strlen (constraint
);
427 /* ??? At the end of the loop, we will skip the first part of
428 the matched constraint. This assumes not only that the
429 other constraint is an output constraint, but also that
430 the '=' or '+' come first. */
434 j
= end
- constraint
;
435 /* Anticipate increment at end of loop. */
446 if (! ISALPHA (constraint
[j
]))
448 error ("invalid punctuation %qc in constraint", constraint
[j
]);
451 enum constraint_num cn
= lookup_constraint (constraint
+ j
);
452 if (reg_class_for_constraint (cn
) != NO_REGS
453 || insn_extra_address_constraint (cn
))
455 else if (insn_extra_memory_constraint (cn
))
458 insn_extra_constraint_allows_reg_mem (cn
, allows_reg
, allows_mem
);
462 if (saw_match
&& !*allows_reg
)
463 warning (0, "matching constraint does not allow a register");
468 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
469 can be an asm-declared register. Called via walk_tree. */
472 decl_overlaps_hard_reg_set_p (tree
*declp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
476 const HARD_REG_SET
*const regs
= (const HARD_REG_SET
*) data
;
478 if (TREE_CODE (decl
) == VAR_DECL
)
480 if (DECL_HARD_REGISTER (decl
)
481 && REG_P (DECL_RTL (decl
))
482 && REGNO (DECL_RTL (decl
)) < FIRST_PSEUDO_REGISTER
)
484 rtx reg
= DECL_RTL (decl
);
486 if (overlaps_hard_reg_set_p (*regs
, GET_MODE (reg
), REGNO (reg
)))
491 else if (TYPE_P (decl
) || TREE_CODE (decl
) == PARM_DECL
)
496 /* If there is an overlap between *REGS and DECL, return the first overlap
499 tree_overlaps_hard_reg_set (tree decl
, HARD_REG_SET
*regs
)
501 return walk_tree (&decl
, decl_overlaps_hard_reg_set_p
, regs
, NULL
);
505 /* A subroutine of expand_asm_operands. Check that all operand names
506 are unique. Return true if so. We rely on the fact that these names
507 are identifiers, and so have been canonicalized by get_identifier,
508 so all we need are pointer comparisons. */
511 check_unique_operand_names (tree outputs
, tree inputs
, tree labels
)
513 tree i
, j
, i_name
= NULL_TREE
;
515 for (i
= outputs
; i
; i
= TREE_CHAIN (i
))
517 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
521 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
522 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
526 for (i
= inputs
; i
; i
= TREE_CHAIN (i
))
528 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
532 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
533 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
535 for (j
= outputs
; j
; j
= TREE_CHAIN (j
))
536 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
540 for (i
= labels
; i
; i
= TREE_CHAIN (i
))
542 i_name
= TREE_PURPOSE (i
);
546 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
547 if (simple_cst_equal (i_name
, TREE_PURPOSE (j
)))
549 for (j
= inputs
; j
; j
= TREE_CHAIN (j
))
550 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
557 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name
));
561 /* Resolve the names of the operands in *POUTPUTS and *PINPUTS to numbers,
562 and replace the name expansions in STRING and in the constraints to
563 those numbers. This is generally done in the front end while creating
564 the ASM_EXPR generic tree that eventually becomes the GIMPLE_ASM. */
567 resolve_asm_operand_names (tree string
, tree outputs
, tree inputs
, tree labels
)
574 check_unique_operand_names (outputs
, inputs
, labels
);
576 /* Substitute [<name>] in input constraint strings. There should be no
577 named operands in output constraints. */
578 for (t
= inputs
; t
; t
= TREE_CHAIN (t
))
580 c
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
581 if (strchr (c
, '[') != NULL
)
583 p
= buffer
= xstrdup (c
);
584 while ((p
= strchr (p
, '[')) != NULL
)
585 p
= resolve_operand_name_1 (p
, outputs
, inputs
, NULL
);
586 TREE_VALUE (TREE_PURPOSE (t
))
587 = build_string (strlen (buffer
), buffer
);
592 /* Now check for any needed substitutions in the template. */
593 c
= TREE_STRING_POINTER (string
);
594 while ((c
= strchr (c
, '%')) != NULL
)
598 else if (ISALPHA (c
[1]) && c
[2] == '[')
602 c
+= 1 + (c
[1] == '%');
609 /* OK, we need to make a copy so we can perform the substitutions.
610 Assume that we will not need extra space--we get to remove '['
611 and ']', which means we cannot have a problem until we have more
612 than 999 operands. */
613 buffer
= xstrdup (TREE_STRING_POINTER (string
));
614 p
= buffer
+ (c
- TREE_STRING_POINTER (string
));
616 while ((p
= strchr (p
, '%')) != NULL
)
620 else if (ISALPHA (p
[1]) && p
[2] == '[')
624 p
+= 1 + (p
[1] == '%');
628 p
= resolve_operand_name_1 (p
, outputs
, inputs
, labels
);
631 string
= build_string (strlen (buffer
), buffer
);
638 /* A subroutine of resolve_operand_names. P points to the '[' for a
639 potential named operand of the form [<name>]. In place, replace
640 the name and brackets with a number. Return a pointer to the
641 balance of the string after substitution. */
644 resolve_operand_name_1 (char *p
, tree outputs
, tree inputs
, tree labels
)
650 /* Collect the operand name. */
651 q
= strchr (++p
, ']');
654 error ("missing close brace for named operand");
655 return strchr (p
, '\0');
659 /* Resolve the name to a number. */
660 for (op
= 0, t
= outputs
; t
; t
= TREE_CHAIN (t
), op
++)
662 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
663 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
666 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), op
++)
668 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
669 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
672 for (t
= labels
; t
; t
= TREE_CHAIN (t
), op
++)
674 tree name
= TREE_PURPOSE (t
);
675 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
679 error ("undefined named operand %qs", identifier_to_locale (p
));
683 /* Replace the name with the number. Unfortunately, not all libraries
684 get the return value of sprintf correct, so search for the end of the
685 generated string by hand. */
686 sprintf (--p
, "%d", op
);
687 p
= strchr (p
, '\0');
689 /* Verify the no extra buffer space assumption. */
692 /* Shift the rest of the buffer down to fill the gap. */
693 memmove (p
, q
+ 1, strlen (q
+ 1) + 1);
699 /* Generate RTL to return directly from the current function.
700 (That is, we bypass any return value.) */
703 expand_naked_return (void)
705 rtx_code_label
*end_label
;
707 clear_pending_stack_adjust ();
708 do_pending_stack_adjust ();
710 end_label
= naked_return_label
;
712 end_label
= naked_return_label
= gen_label_rtx ();
714 emit_jump (end_label
);
717 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
718 is the probability of jumping to LABEL. */
720 do_jump_if_equal (machine_mode mode
, rtx op0
, rtx op1
, rtx_code_label
*label
,
721 int unsignedp
, int prob
)
723 gcc_assert (prob
<= REG_BR_PROB_BASE
);
724 do_compare_rtx_and_jump (op0
, op1
, EQ
, unsignedp
, mode
,
725 NULL_RTX
, NULL
, label
, prob
);
728 /* Do the insertion of a case label into case_list. The labels are
729 fed to us in descending order from the sorted vector of case labels used
730 in the tree part of the middle end. So the list we construct is
731 sorted in ascending order.
733 LABEL is the case label to be inserted. LOW and HIGH are the bounds
734 against which the index is compared to jump to LABEL and PROB is the
735 estimated probability LABEL is reached from the switch statement. */
737 static struct case_node
*
738 add_case_node (struct case_node
*head
, tree low
, tree high
,
739 tree label
, int prob
, pool_allocator
<case_node
> &case_node_pool
)
743 gcc_checking_assert (low
);
744 gcc_checking_assert (high
&& (TREE_TYPE (low
) == TREE_TYPE (high
)));
746 /* Add this label to the chain. */
747 r
= case_node_pool
.allocate ();
750 r
->code_label
= label
;
751 r
->parent
= r
->left
= NULL
;
753 r
->subtree_prob
= prob
;
758 /* Dump ROOT, a list or tree of case nodes, to file. */
761 dump_case_nodes (FILE *f
, struct case_node
*root
,
762 int indent_step
, int indent_level
)
768 dump_case_nodes (f
, root
->left
, indent_step
, indent_level
);
771 fprintf (f
, "%*s", indent_step
* indent_level
, "");
772 print_dec (root
->low
, f
, TYPE_SIGN (TREE_TYPE (root
->low
)));
773 if (!tree_int_cst_equal (root
->low
, root
->high
))
775 fprintf (f
, " ... ");
776 print_dec (root
->high
, f
, TYPE_SIGN (TREE_TYPE (root
->high
)));
780 dump_case_nodes (f
, root
->right
, indent_step
, indent_level
);
783 /* Return the smallest number of different values for which it is best to use a
784 jump-table instead of a tree of conditional branches. */
787 case_values_threshold (void)
789 unsigned int threshold
= PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD
);
792 threshold
= targetm
.case_values_threshold ();
797 /* Return true if a switch should be expanded as a decision tree.
798 RANGE is the difference between highest and lowest case.
799 UNIQ is number of unique case node targets, not counting the default case.
800 COUNT is the number of comparisons needed, not counting the default case. */
803 expand_switch_as_decision_tree_p (tree range
,
804 unsigned int uniq ATTRIBUTE_UNUSED
,
809 /* If neither casesi or tablejump is available, or flag_jump_tables
810 over-ruled us, we really have no choice. */
811 if (!targetm
.have_casesi () && !targetm
.have_tablejump ())
813 if (!flag_jump_tables
)
815 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
820 /* If the switch is relatively small such that the cost of one
821 indirect jump on the target are higher than the cost of a
822 decision tree, go with the decision tree.
824 If range of values is much bigger than number of values,
825 or if it is too large to represent in a HOST_WIDE_INT,
826 make a sequence of conditional branches instead of a dispatch.
828 The definition of "much bigger" depends on whether we are
829 optimizing for size or for speed. If the former, the maximum
830 ratio range/count = 3, because this was found to be the optimal
831 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
832 10 is much older, and was probably selected after an extensive
833 benchmarking investigation on numerous platforms. Or maybe it
834 just made sense to someone at some point in the history of GCC,
836 max_ratio
= optimize_insn_for_size_p () ? 3 : 10;
837 if (count
< case_values_threshold ()
838 || ! tree_fits_uhwi_p (range
)
839 || compare_tree_int (range
, max_ratio
* count
) > 0)
845 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
846 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
847 DEFAULT_PROB is the estimated probability that it jumps to
850 We generate a binary decision tree to select the appropriate target
851 code. This is done as follows:
853 If the index is a short or char that we do not have
854 an insn to handle comparisons directly, convert it to
855 a full integer now, rather than letting each comparison
856 generate the conversion.
858 Load the index into a register.
860 The list of cases is rearranged into a binary tree,
861 nearly optimal assuming equal probability for each case.
863 The tree is transformed into RTL, eliminating redundant
864 test conditions at the same time.
866 If program flow could reach the end of the decision tree
867 an unconditional jump to the default code is emitted.
869 The above process is unaware of the CFG. The caller has to fix up
870 the CFG itself. This is done in cfgexpand.c. */
873 emit_case_decision_tree (tree index_expr
, tree index_type
,
874 case_node_ptr case_list
, rtx_code_label
*default_label
,
877 rtx index
= expand_normal (index_expr
);
879 if (GET_MODE_CLASS (GET_MODE (index
)) == MODE_INT
880 && ! have_insn_for (COMPARE
, GET_MODE (index
)))
882 int unsignedp
= TYPE_UNSIGNED (index_type
);
883 machine_mode wider_mode
;
884 for (wider_mode
= GET_MODE (index
); wider_mode
!= VOIDmode
;
885 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
886 if (have_insn_for (COMPARE
, wider_mode
))
888 index
= convert_to_mode (wider_mode
, index
, unsignedp
);
893 do_pending_stack_adjust ();
897 index
= copy_to_reg (index
);
898 if (TREE_CODE (index_expr
) == SSA_NAME
)
899 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr
), index
);
902 balance_case_nodes (&case_list
, NULL
);
904 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
906 int indent_step
= ceil_log2 (TYPE_PRECISION (index_type
)) + 2;
907 fprintf (dump_file
, ";; Expanding GIMPLE switch as decision tree:\n");
908 dump_case_nodes (dump_file
, case_list
, indent_step
, 0);
911 emit_case_nodes (index
, case_list
, default_label
, default_prob
, index_type
);
913 emit_jump (default_label
);
916 /* Return the sum of probabilities of outgoing edges of basic block BB. */
919 get_outgoing_edge_probs (basic_block bb
)
926 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
927 prob_sum
+= e
->probability
;
931 /* Computes the conditional probability of jumping to a target if the branch
932 instruction is executed.
933 TARGET_PROB is the estimated probability of jumping to a target relative
934 to some basic block BB.
935 BASE_PROB is the probability of reaching the branch instruction relative
936 to the same basic block BB. */
939 conditional_probability (int target_prob
, int base_prob
)
943 gcc_assert (target_prob
>= 0);
944 gcc_assert (target_prob
<= base_prob
);
945 return GCOV_COMPUTE_SCALE (target_prob
, base_prob
);
950 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
951 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
952 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
953 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
955 First, a jump insn is emitted. First we try "casesi". If that
956 fails, try "tablejump". A target *must* have one of them (or both).
958 Then, a table with the target labels is emitted.
960 The process is unaware of the CFG. The caller has to fix up
961 the CFG itself. This is done in cfgexpand.c. */
964 emit_case_dispatch_table (tree index_expr
, tree index_type
,
965 struct case_node
*case_list
, rtx default_label
,
966 tree minval
, tree maxval
, tree range
,
972 rtx_insn
*fallback_label
= label_rtx (case_list
->code_label
);
973 rtx_code_label
*table_label
= gen_label_rtx ();
974 bool has_gaps
= false;
975 edge default_edge
= stmt_bb
? EDGE_SUCC (stmt_bb
, 0) : NULL
;
976 int default_prob
= default_edge
? default_edge
->probability
: 0;
977 int base
= get_outgoing_edge_probs (stmt_bb
);
978 bool try_with_tablejump
= false;
980 int new_default_prob
= conditional_probability (default_prob
,
983 if (! try_casesi (index_type
, index_expr
, minval
, range
,
984 table_label
, default_label
, fallback_label
,
987 /* Index jumptables from zero for suitable values of minval to avoid
988 a subtraction. For the rationale see:
989 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
990 if (optimize_insn_for_speed_p ()
991 && compare_tree_int (minval
, 0) > 0
992 && compare_tree_int (minval
, 3) < 0)
994 minval
= build_int_cst (index_type
, 0);
998 try_with_tablejump
= true;
1001 /* Get table of labels to jump to, in order of case index. */
1003 ncases
= tree_to_shwi (range
) + 1;
1004 labelvec
= XALLOCAVEC (rtx
, ncases
);
1005 memset (labelvec
, 0, ncases
* sizeof (rtx
));
1007 for (n
= case_list
; n
; n
= n
->right
)
1009 /* Compute the low and high bounds relative to the minimum
1010 value since that should fit in a HOST_WIDE_INT while the
1011 actual values may not. */
1013 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1015 HOST_WIDE_INT i_high
1016 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1020 for (i
= i_low
; i
<= i_high
; i
++)
1022 = gen_rtx_LABEL_REF (Pmode
, label_rtx (n
->code_label
));
1025 /* Fill in the gaps with the default. We may have gaps at
1026 the beginning if we tried to avoid the minval subtraction,
1027 so substitute some label even if the default label was
1028 deemed unreachable. */
1030 default_label
= fallback_label
;
1031 for (i
= 0; i
< ncases
; i
++)
1032 if (labelvec
[i
] == 0)
1035 labelvec
[i
] = gen_rtx_LABEL_REF (Pmode
, default_label
);
1040 /* There is at least one entry in the jump table that jumps
1041 to default label. The default label can either be reached
1042 through the indirect jump or the direct conditional jump
1043 before that. Split the probability of reaching the
1044 default label among these two jumps. */
1045 new_default_prob
= conditional_probability (default_prob
/2,
1048 base
-= default_prob
;
1052 base
-= default_prob
;
1057 default_edge
->probability
= default_prob
;
1059 /* We have altered the probability of the default edge. So the probabilities
1060 of all other edges need to be adjusted so that it sums up to
1061 REG_BR_PROB_BASE. */
1066 FOR_EACH_EDGE (e
, ei
, stmt_bb
->succs
)
1067 e
->probability
= GCOV_COMPUTE_SCALE (e
->probability
, base
);
1070 if (try_with_tablejump
)
1072 bool ok
= try_tablejump (index_type
, index_expr
, minval
, range
,
1073 table_label
, default_label
, new_default_prob
);
1076 /* Output the table. */
1077 emit_label (table_label
);
1079 if (CASE_VECTOR_PC_RELATIVE
|| flag_pic
)
1080 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE
,
1081 gen_rtx_LABEL_REF (Pmode
,
1083 gen_rtvec_v (ncases
, labelvec
),
1084 const0_rtx
, const0_rtx
));
1086 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE
,
1087 gen_rtvec_v (ncases
, labelvec
)));
1089 /* Record no drop-through after the table. */
1093 /* Reset the aux field of all outgoing edges of basic block BB. */
1096 reset_out_edges_aux (basic_block bb
)
1100 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1104 /* Compute the number of case labels that correspond to each outgoing edge of
1105 STMT. Record this information in the aux field of the edge. */
1108 compute_cases_per_edge (gswitch
*stmt
)
1110 basic_block bb
= gimple_bb (stmt
);
1111 reset_out_edges_aux (bb
);
1112 int ncases
= gimple_switch_num_labels (stmt
);
1113 for (int i
= ncases
- 1; i
>= 1; --i
)
1115 tree elt
= gimple_switch_label (stmt
, i
);
1116 tree lab
= CASE_LABEL (elt
);
1117 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1118 edge case_edge
= find_edge (bb
, case_bb
);
1119 case_edge
->aux
= (void *)((intptr_t)(case_edge
->aux
) + 1);
1123 /* Terminate a case (Pascal/Ada) or switch (C) statement
1124 in which ORIG_INDEX is the expression to be tested.
1125 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
1126 type as given in the source before any compiler conversions.
1127 Generate the code to test it and jump to the right place. */
1130 expand_case (gswitch
*stmt
)
1132 tree minval
= NULL_TREE
, maxval
= NULL_TREE
, range
= NULL_TREE
;
1133 rtx_code_label
*default_label
= NULL
;
1134 unsigned int count
, uniq
;
1136 int ncases
= gimple_switch_num_labels (stmt
);
1137 tree index_expr
= gimple_switch_index (stmt
);
1138 tree index_type
= TREE_TYPE (index_expr
);
1140 basic_block bb
= gimple_bb (stmt
);
1142 /* A list of case labels; it is first built as a list and it may then
1143 be rearranged into a nearly balanced binary tree. */
1144 struct case_node
*case_list
= 0;
1146 /* A pool for case nodes. */
1147 pool_allocator
<case_node
> case_node_pool ("struct case_node pool", 100);
1149 /* An ERROR_MARK occurs for various reasons including invalid data type.
1150 ??? Can this still happen, with GIMPLE and all? */
1151 if (index_type
== error_mark_node
)
1154 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
1155 expressions being INTEGER_CST. */
1156 gcc_assert (TREE_CODE (index_expr
) != INTEGER_CST
);
1159 do_pending_stack_adjust ();
1161 /* Find the default case target label. */
1162 default_label
= jump_target_rtx
1163 (CASE_LABEL (gimple_switch_default_label (stmt
)));
1164 edge default_edge
= EDGE_SUCC (bb
, 0);
1165 int default_prob
= default_edge
->probability
;
1167 /* Get upper and lower bounds of case values. */
1168 elt
= gimple_switch_label (stmt
, 1);
1169 minval
= fold_convert (index_type
, CASE_LOW (elt
));
1170 elt
= gimple_switch_label (stmt
, ncases
- 1);
1171 if (CASE_HIGH (elt
))
1172 maxval
= fold_convert (index_type
, CASE_HIGH (elt
));
1174 maxval
= fold_convert (index_type
, CASE_LOW (elt
));
1176 /* Compute span of values. */
1177 range
= fold_build2 (MINUS_EXPR
, index_type
, maxval
, minval
);
1179 /* Listify the labels queue and gather some numbers to decide
1180 how to expand this switch(). */
1183 hash_set
<tree
> seen_labels
;
1184 compute_cases_per_edge (stmt
);
1186 for (i
= ncases
- 1; i
>= 1; --i
)
1188 elt
= gimple_switch_label (stmt
, i
);
1189 tree low
= CASE_LOW (elt
);
1191 tree high
= CASE_HIGH (elt
);
1192 gcc_assert (! high
|| tree_int_cst_lt (low
, high
));
1193 tree lab
= CASE_LABEL (elt
);
1195 /* Count the elements.
1196 A range counts double, since it requires two compares. */
1201 /* If we have not seen this label yet, then increase the
1202 number of unique case node targets seen. */
1203 if (!seen_labels
.add (lab
))
1206 /* The bounds on the case range, LOW and HIGH, have to be converted
1207 to case's index type TYPE. Note that the original type of the
1208 case index in the source code is usually "lost" during
1209 gimplification due to type promotion, but the case labels retain the
1210 original type. Make sure to drop overflow flags. */
1211 low
= fold_convert (index_type
, low
);
1212 if (TREE_OVERFLOW (low
))
1213 low
= wide_int_to_tree (index_type
, low
);
1215 /* The canonical from of a case label in GIMPLE is that a simple case
1216 has an empty CASE_HIGH. For the casesi and tablejump expanders,
1217 the back ends want simple cases to have high == low. */
1220 high
= fold_convert (index_type
, high
);
1221 if (TREE_OVERFLOW (high
))
1222 high
= wide_int_to_tree (index_type
, high
);
1224 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1225 edge case_edge
= find_edge (bb
, case_bb
);
1226 case_list
= add_case_node (
1227 case_list
, low
, high
, lab
,
1228 case_edge
->probability
/ (intptr_t)(case_edge
->aux
),
1231 reset_out_edges_aux (bb
);
1233 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
1234 destination, such as one with a default case only.
1235 It also removes cases that are out of range for the switch
1236 type, so we should never get a zero here. */
1237 gcc_assert (count
> 0);
1239 rtx_insn
*before_case
= get_last_insn ();
1241 /* Decide how to expand this switch.
1242 The two options at this point are a dispatch table (casesi or
1243 tablejump) or a decision tree. */
1245 if (expand_switch_as_decision_tree_p (range
, uniq
, count
))
1246 emit_case_decision_tree (index_expr
, index_type
,
1247 case_list
, default_label
,
1250 emit_case_dispatch_table (index_expr
, index_type
,
1251 case_list
, default_label
,
1252 minval
, maxval
, range
, bb
);
1254 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1259 /* Expand the dispatch to a short decrement chain if there are few cases
1260 to dispatch to. Likewise if neither casesi nor tablejump is available,
1261 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
1262 tablejump. The index mode is always the mode of integer_type_node.
1263 Trap if no case matches the index.
1265 DISPATCH_INDEX is the index expression to switch on. It should be a
1266 memory or register operand.
1268 DISPATCH_TABLE is a set of case labels. The set should be sorted in
1269 ascending order, be contiguous, starting with value 0, and contain only
1270 single-valued case labels. */
1273 expand_sjlj_dispatch_table (rtx dispatch_index
,
1274 vec
<tree
> dispatch_table
)
1276 tree index_type
= integer_type_node
;
1277 machine_mode index_mode
= TYPE_MODE (index_type
);
1279 int ncases
= dispatch_table
.length ();
1281 do_pending_stack_adjust ();
1282 rtx_insn
*before_case
= get_last_insn ();
1284 /* Expand as a decrement-chain if there are 5 or fewer dispatch
1285 labels. This covers more than 98% of the cases in libjava,
1286 and seems to be a reasonable compromise between the "old way"
1287 of expanding as a decision tree or dispatch table vs. the "new
1288 way" with decrement chain or dispatch table. */
1289 if (dispatch_table
.length () <= 5
1290 || (!targetm
.have_casesi () && !targetm
.have_tablejump ())
1291 || !flag_jump_tables
)
1293 /* Expand the dispatch as a decrement chain:
1295 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1299 if (index == 0) do_0; else index--;
1300 if (index == 0) do_1; else index--;
1302 if (index == 0) do_N; else index--;
1304 This is more efficient than a dispatch table on most machines.
1305 The last "index--" is redundant but the code is trivially dead
1306 and will be cleaned up by later passes. */
1307 rtx index
= copy_to_mode_reg (index_mode
, dispatch_index
);
1308 rtx zero
= CONST0_RTX (index_mode
);
1309 for (int i
= 0; i
< ncases
; i
++)
1311 tree elt
= dispatch_table
[i
];
1312 rtx_code_label
*lab
= jump_target_rtx (CASE_LABEL (elt
));
1313 do_jump_if_equal (index_mode
, index
, zero
, lab
, 0, -1);
1314 force_expand_binop (index_mode
, sub_optab
,
1315 index
, CONST1_RTX (index_mode
),
1316 index
, 0, OPTAB_DIRECT
);
1321 /* Similar to expand_case, but much simpler. */
1322 struct case_node
*case_list
= 0;
1323 pool_allocator
<case_node
> case_node_pool ("struct sjlj_case pool",
1325 tree index_expr
= make_tree (index_type
, dispatch_index
);
1326 tree minval
= build_int_cst (index_type
, 0);
1327 tree maxval
= CASE_LOW (dispatch_table
.last ());
1328 tree range
= maxval
;
1329 rtx_code_label
*default_label
= gen_label_rtx ();
1331 for (int i
= ncases
- 1; i
>= 0; --i
)
1333 tree elt
= dispatch_table
[i
];
1334 tree low
= CASE_LOW (elt
);
1335 tree lab
= CASE_LABEL (elt
);
1336 case_list
= add_case_node (case_list
, low
, low
, lab
, 0, case_node_pool
);
1339 emit_case_dispatch_table (index_expr
, index_type
,
1340 case_list
, default_label
,
1341 minval
, maxval
, range
,
1342 BLOCK_FOR_INSN (before_case
));
1343 emit_label (default_label
);
1346 /* Dispatching something not handled? Trap! */
1347 expand_builtin_trap ();
1349 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1355 /* Take an ordered list of case nodes
1356 and transform them into a near optimal binary tree,
1357 on the assumption that any target code selection value is as
1358 likely as any other.
1360 The transformation is performed by splitting the ordered
1361 list into two equal sections plus a pivot. The parts are
1362 then attached to the pivot as left and right branches. Each
1363 branch is then transformed recursively. */
1366 balance_case_nodes (case_node_ptr
*head
, case_node_ptr parent
)
1378 /* Count the number of entries on branch. Also count the ranges. */
1382 if (!tree_int_cst_equal (np
->low
, np
->high
))
1391 /* Split this list if it is long enough for that to help. */
1395 /* If there are just three nodes, split at the middle one. */
1397 npp
= &(*npp
)->right
;
1400 /* Find the place in the list that bisects the list's total cost,
1401 where ranges count as 2.
1402 Here I gets half the total cost. */
1403 i
= (i
+ ranges
+ 1) / 2;
1406 /* Skip nodes while their cost does not reach that amount. */
1407 if (!tree_int_cst_equal ((*npp
)->low
, (*npp
)->high
))
1412 npp
= &(*npp
)->right
;
1417 np
->parent
= parent
;
1420 /* Optimize each of the two split parts. */
1421 balance_case_nodes (&np
->left
, np
);
1422 balance_case_nodes (&np
->right
, np
);
1423 np
->subtree_prob
= np
->prob
;
1424 np
->subtree_prob
+= np
->left
->subtree_prob
;
1425 np
->subtree_prob
+= np
->right
->subtree_prob
;
1429 /* Else leave this branch as one level,
1430 but fill in `parent' fields. */
1432 np
->parent
= parent
;
1433 np
->subtree_prob
= np
->prob
;
1434 for (; np
->right
; np
= np
->right
)
1436 np
->right
->parent
= np
;
1437 (*head
)->subtree_prob
+= np
->right
->subtree_prob
;
1443 /* Search the parent sections of the case node tree
1444 to see if a test for the lower bound of NODE would be redundant.
1445 INDEX_TYPE is the type of the index expression.
1447 The instructions to generate the case decision tree are
1448 output in the same order as nodes are processed so it is
1449 known that if a parent node checks the range of the current
1450 node minus one that the current node is bounded at its lower
1451 span. Thus the test would be redundant. */
1454 node_has_low_bound (case_node_ptr node
, tree index_type
)
1457 case_node_ptr pnode
;
1459 /* If the lower bound of this node is the lowest value in the index type,
1460 we need not test it. */
1462 if (tree_int_cst_equal (node
->low
, TYPE_MIN_VALUE (index_type
)))
1465 /* If this node has a left branch, the value at the left must be less
1466 than that at this node, so it cannot be bounded at the bottom and
1467 we need not bother testing any further. */
1472 low_minus_one
= fold_build2 (MINUS_EXPR
, TREE_TYPE (node
->low
),
1474 build_int_cst (TREE_TYPE (node
->low
), 1));
1476 /* If the subtraction above overflowed, we can't verify anything.
1477 Otherwise, look for a parent that tests our value - 1. */
1479 if (! tree_int_cst_lt (low_minus_one
, node
->low
))
1482 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1483 if (tree_int_cst_equal (low_minus_one
, pnode
->high
))
1489 /* Search the parent sections of the case node tree
1490 to see if a test for the upper bound of NODE would be redundant.
1491 INDEX_TYPE is the type of the index expression.
1493 The instructions to generate the case decision tree are
1494 output in the same order as nodes are processed so it is
1495 known that if a parent node checks the range of the current
1496 node plus one that the current node is bounded at its upper
1497 span. Thus the test would be redundant. */
1500 node_has_high_bound (case_node_ptr node
, tree index_type
)
1503 case_node_ptr pnode
;
1505 /* If there is no upper bound, obviously no test is needed. */
1507 if (TYPE_MAX_VALUE (index_type
) == NULL
)
1510 /* If the upper bound of this node is the highest value in the type
1511 of the index expression, we need not test against it. */
1513 if (tree_int_cst_equal (node
->high
, TYPE_MAX_VALUE (index_type
)))
1516 /* If this node has a right branch, the value at the right must be greater
1517 than that at this node, so it cannot be bounded at the top and
1518 we need not bother testing any further. */
1523 high_plus_one
= fold_build2 (PLUS_EXPR
, TREE_TYPE (node
->high
),
1525 build_int_cst (TREE_TYPE (node
->high
), 1));
1527 /* If the addition above overflowed, we can't verify anything.
1528 Otherwise, look for a parent that tests our value + 1. */
1530 if (! tree_int_cst_lt (node
->high
, high_plus_one
))
1533 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1534 if (tree_int_cst_equal (high_plus_one
, pnode
->low
))
1540 /* Search the parent sections of the
1541 case node tree to see if both tests for the upper and lower
1542 bounds of NODE would be redundant. */
1545 node_is_bounded (case_node_ptr node
, tree index_type
)
1547 return (node_has_low_bound (node
, index_type
)
1548 && node_has_high_bound (node
, index_type
));
1552 /* Emit step-by-step code to select a case for the value of INDEX.
1553 The thus generated decision tree follows the form of the
1554 case-node binary tree NODE, whose nodes represent test conditions.
1555 INDEX_TYPE is the type of the index of the switch.
1557 Care is taken to prune redundant tests from the decision tree
1558 by detecting any boundary conditions already checked by
1559 emitted rtx. (See node_has_high_bound, node_has_low_bound
1560 and node_is_bounded, above.)
1562 Where the test conditions can be shown to be redundant we emit
1563 an unconditional jump to the target code. As a further
1564 optimization, the subordinates of a tree node are examined to
1565 check for bounded nodes. In this case conditional and/or
1566 unconditional jumps as a result of the boundary check for the
1567 current node are arranged to target the subordinates associated
1568 code for out of bound conditions on the current node.
1570 We can assume that when control reaches the code generated here,
1571 the index value has already been compared with the parents
1572 of this node, and determined to be on the same side of each parent
1573 as this node is. Thus, if this node tests for the value 51,
1574 and a parent tested for 52, we don't need to consider
1575 the possibility of a value greater than 51. If another parent
1576 tests for the value 50, then this node need not test anything. */
1579 emit_case_nodes (rtx index
, case_node_ptr node
, rtx_code_label
*default_label
,
1580 int default_prob
, tree index_type
)
1582 /* If INDEX has an unsigned type, we must make unsigned branches. */
1583 int unsignedp
= TYPE_UNSIGNED (index_type
);
1585 int prob
= node
->prob
, subtree_prob
= node
->subtree_prob
;
1586 machine_mode mode
= GET_MODE (index
);
1587 machine_mode imode
= TYPE_MODE (index_type
);
1589 /* Handle indices detected as constant during RTL expansion. */
1590 if (mode
== VOIDmode
)
1593 /* See if our parents have already tested everything for us.
1594 If they have, emit an unconditional jump for this node. */
1595 if (node_is_bounded (node
, index_type
))
1596 emit_jump (label_rtx (node
->code_label
));
1598 else if (tree_int_cst_equal (node
->low
, node
->high
))
1600 probability
= conditional_probability (prob
, subtree_prob
+ default_prob
);
1601 /* Node is single valued. First see if the index expression matches
1602 this node and then check our children, if any. */
1603 do_jump_if_equal (mode
, index
,
1604 convert_modes (mode
, imode
,
1605 expand_normal (node
->low
),
1607 jump_target_rtx (node
->code_label
),
1608 unsignedp
, probability
);
1609 /* Since this case is taken at this point, reduce its weight from
1611 subtree_prob
-= prob
;
1612 if (node
->right
!= 0 && node
->left
!= 0)
1614 /* This node has children on both sides.
1615 Dispatch to one side or the other
1616 by comparing the index value with this node's value.
1617 If one subtree is bounded, check that one first,
1618 so we can avoid real branches in the tree. */
1620 if (node_is_bounded (node
->right
, index_type
))
1622 probability
= conditional_probability (
1624 subtree_prob
+ default_prob
);
1625 emit_cmp_and_jump_insns (index
,
1628 expand_normal (node
->high
),
1630 GT
, NULL_RTX
, mode
, unsignedp
,
1631 label_rtx (node
->right
->code_label
),
1633 emit_case_nodes (index
, node
->left
, default_label
, default_prob
,
1637 else if (node_is_bounded (node
->left
, index_type
))
1639 probability
= conditional_probability (
1641 subtree_prob
+ default_prob
);
1642 emit_cmp_and_jump_insns (index
,
1645 expand_normal (node
->high
),
1647 LT
, NULL_RTX
, mode
, unsignedp
,
1648 label_rtx (node
->left
->code_label
),
1650 emit_case_nodes (index
, node
->right
, default_label
, default_prob
,
1654 /* If both children are single-valued cases with no
1655 children, finish up all the work. This way, we can save
1656 one ordered comparison. */
1657 else if (tree_int_cst_equal (node
->right
->low
, node
->right
->high
)
1658 && node
->right
->left
== 0
1659 && node
->right
->right
== 0
1660 && tree_int_cst_equal (node
->left
->low
, node
->left
->high
)
1661 && node
->left
->left
== 0
1662 && node
->left
->right
== 0)
1664 /* Neither node is bounded. First distinguish the two sides;
1665 then emit the code for one side at a time. */
1667 /* See if the value matches what the right hand side
1669 probability
= conditional_probability (
1671 subtree_prob
+ default_prob
);
1672 do_jump_if_equal (mode
, index
,
1673 convert_modes (mode
, imode
,
1674 expand_normal (node
->right
->low
),
1676 jump_target_rtx (node
->right
->code_label
),
1677 unsignedp
, probability
);
1679 /* See if the value matches what the left hand side
1681 probability
= conditional_probability (
1683 subtree_prob
+ default_prob
);
1684 do_jump_if_equal (mode
, index
,
1685 convert_modes (mode
, imode
,
1686 expand_normal (node
->left
->low
),
1688 jump_target_rtx (node
->left
->code_label
),
1689 unsignedp
, probability
);
1694 /* Neither node is bounded. First distinguish the two sides;
1695 then emit the code for one side at a time. */
1698 = build_decl (curr_insn_location (),
1699 LABEL_DECL
, NULL_TREE
, void_type_node
);
1701 /* The default label could be reached either through the right
1702 subtree or the left subtree. Divide the probability
1704 probability
= conditional_probability (
1705 node
->right
->subtree_prob
+ default_prob
/2,
1706 subtree_prob
+ default_prob
);
1707 /* See if the value is on the right. */
1708 emit_cmp_and_jump_insns (index
,
1711 expand_normal (node
->high
),
1713 GT
, NULL_RTX
, mode
, unsignedp
,
1714 label_rtx (test_label
),
1718 /* Value must be on the left.
1719 Handle the left-hand subtree. */
1720 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1721 /* If left-hand subtree does nothing,
1724 emit_jump (default_label
);
1726 /* Code branches here for the right-hand subtree. */
1727 expand_label (test_label
);
1728 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1732 else if (node
->right
!= 0 && node
->left
== 0)
1734 /* Here we have a right child but no left so we issue a conditional
1735 branch to default and process the right child.
1737 Omit the conditional branch to default if the right child
1738 does not have any children and is single valued; it would
1739 cost too much space to save so little time. */
1741 if (node
->right
->right
|| node
->right
->left
1742 || !tree_int_cst_equal (node
->right
->low
, node
->right
->high
))
1744 if (!node_has_low_bound (node
, index_type
))
1746 probability
= conditional_probability (
1748 subtree_prob
+ default_prob
);
1749 emit_cmp_and_jump_insns (index
,
1752 expand_normal (node
->high
),
1754 LT
, NULL_RTX
, mode
, unsignedp
,
1760 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1764 probability
= conditional_probability (
1765 node
->right
->subtree_prob
,
1766 subtree_prob
+ default_prob
);
1767 /* We cannot process node->right normally
1768 since we haven't ruled out the numbers less than
1769 this node's value. So handle node->right explicitly. */
1770 do_jump_if_equal (mode
, index
,
1773 expand_normal (node
->right
->low
),
1775 jump_target_rtx (node
->right
->code_label
),
1776 unsignedp
, probability
);
1780 else if (node
->right
== 0 && node
->left
!= 0)
1782 /* Just one subtree, on the left. */
1783 if (node
->left
->left
|| node
->left
->right
1784 || !tree_int_cst_equal (node
->left
->low
, node
->left
->high
))
1786 if (!node_has_high_bound (node
, index_type
))
1788 probability
= conditional_probability (
1790 subtree_prob
+ default_prob
);
1791 emit_cmp_and_jump_insns (index
,
1794 expand_normal (node
->high
),
1796 GT
, NULL_RTX
, mode
, unsignedp
,
1802 emit_case_nodes (index
, node
->left
, default_label
,
1803 default_prob
, index_type
);
1807 probability
= conditional_probability (
1808 node
->left
->subtree_prob
,
1809 subtree_prob
+ default_prob
);
1810 /* We cannot process node->left normally
1811 since we haven't ruled out the numbers less than
1812 this node's value. So handle node->left explicitly. */
1813 do_jump_if_equal (mode
, index
,
1816 expand_normal (node
->left
->low
),
1818 jump_target_rtx (node
->left
->code_label
),
1819 unsignedp
, probability
);
1825 /* Node is a range. These cases are very similar to those for a single
1826 value, except that we do not start by testing whether this node
1827 is the one to branch to. */
1829 if (node
->right
!= 0 && node
->left
!= 0)
1831 /* Node has subtrees on both sides.
1832 If the right-hand subtree is bounded,
1833 test for it first, since we can go straight there.
1834 Otherwise, we need to make a branch in the control structure,
1835 then handle the two subtrees. */
1836 tree test_label
= 0;
1838 if (node_is_bounded (node
->right
, index_type
))
1840 /* Right hand node is fully bounded so we can eliminate any
1841 testing and branch directly to the target code. */
1842 probability
= conditional_probability (
1843 node
->right
->subtree_prob
,
1844 subtree_prob
+ default_prob
);
1845 emit_cmp_and_jump_insns (index
,
1848 expand_normal (node
->high
),
1850 GT
, NULL_RTX
, mode
, unsignedp
,
1851 label_rtx (node
->right
->code_label
),
1856 /* Right hand node requires testing.
1857 Branch to a label where we will handle it later. */
1859 test_label
= build_decl (curr_insn_location (),
1860 LABEL_DECL
, NULL_TREE
, void_type_node
);
1861 probability
= conditional_probability (
1862 node
->right
->subtree_prob
+ default_prob
/2,
1863 subtree_prob
+ default_prob
);
1864 emit_cmp_and_jump_insns (index
,
1867 expand_normal (node
->high
),
1869 GT
, NULL_RTX
, mode
, unsignedp
,
1870 label_rtx (test_label
),
1875 /* Value belongs to this node or to the left-hand subtree. */
1877 probability
= conditional_probability (
1879 subtree_prob
+ default_prob
);
1880 emit_cmp_and_jump_insns (index
,
1883 expand_normal (node
->low
),
1885 GE
, NULL_RTX
, mode
, unsignedp
,
1886 label_rtx (node
->code_label
),
1889 /* Handle the left-hand subtree. */
1890 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1892 /* If right node had to be handled later, do that now. */
1896 /* If the left-hand subtree fell through,
1897 don't let it fall into the right-hand subtree. */
1899 emit_jump (default_label
);
1901 expand_label (test_label
);
1902 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1906 else if (node
->right
!= 0 && node
->left
== 0)
1908 /* Deal with values to the left of this node,
1909 if they are possible. */
1910 if (!node_has_low_bound (node
, index_type
))
1912 probability
= conditional_probability (
1914 subtree_prob
+ default_prob
);
1915 emit_cmp_and_jump_insns (index
,
1918 expand_normal (node
->low
),
1920 LT
, NULL_RTX
, mode
, unsignedp
,
1926 /* Value belongs to this node or to the right-hand subtree. */
1928 probability
= conditional_probability (
1930 subtree_prob
+ default_prob
);
1931 emit_cmp_and_jump_insns (index
,
1934 expand_normal (node
->high
),
1936 LE
, NULL_RTX
, mode
, unsignedp
,
1937 label_rtx (node
->code_label
),
1940 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1943 else if (node
->right
== 0 && node
->left
!= 0)
1945 /* Deal with values to the right of this node,
1946 if they are possible. */
1947 if (!node_has_high_bound (node
, index_type
))
1949 probability
= conditional_probability (
1951 subtree_prob
+ default_prob
);
1952 emit_cmp_and_jump_insns (index
,
1955 expand_normal (node
->high
),
1957 GT
, NULL_RTX
, mode
, unsignedp
,
1963 /* Value belongs to this node or to the left-hand subtree. */
1965 probability
= conditional_probability (
1967 subtree_prob
+ default_prob
);
1968 emit_cmp_and_jump_insns (index
,
1971 expand_normal (node
->low
),
1973 GE
, NULL_RTX
, mode
, unsignedp
,
1974 label_rtx (node
->code_label
),
1977 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1982 /* Node has no children so we check low and high bounds to remove
1983 redundant tests. Only one of the bounds can exist,
1984 since otherwise this node is bounded--a case tested already. */
1985 int high_bound
= node_has_high_bound (node
, index_type
);
1986 int low_bound
= node_has_low_bound (node
, index_type
);
1988 if (!high_bound
&& low_bound
)
1990 probability
= conditional_probability (
1992 subtree_prob
+ default_prob
);
1993 emit_cmp_and_jump_insns (index
,
1996 expand_normal (node
->high
),
1998 GT
, NULL_RTX
, mode
, unsignedp
,
2003 else if (!low_bound
&& high_bound
)
2005 probability
= conditional_probability (
2007 subtree_prob
+ default_prob
);
2008 emit_cmp_and_jump_insns (index
,
2011 expand_normal (node
->low
),
2013 LT
, NULL_RTX
, mode
, unsignedp
,
2017 else if (!low_bound
&& !high_bound
)
2019 /* Widen LOW and HIGH to the same width as INDEX. */
2020 tree type
= lang_hooks
.types
.type_for_mode (mode
, unsignedp
);
2021 tree low
= build1 (CONVERT_EXPR
, type
, node
->low
);
2022 tree high
= build1 (CONVERT_EXPR
, type
, node
->high
);
2023 rtx low_rtx
, new_index
, new_bound
;
2025 /* Instead of doing two branches, emit one unsigned branch for
2026 (index-low) > (high-low). */
2027 low_rtx
= expand_expr (low
, NULL_RTX
, mode
, EXPAND_NORMAL
);
2028 new_index
= expand_simple_binop (mode
, MINUS
, index
, low_rtx
,
2029 NULL_RTX
, unsignedp
,
2031 new_bound
= expand_expr (fold_build2 (MINUS_EXPR
, type
,
2033 NULL_RTX
, mode
, EXPAND_NORMAL
);
2035 probability
= conditional_probability (
2037 subtree_prob
+ default_prob
);
2038 emit_cmp_and_jump_insns (new_index
, new_bound
, GT
, NULL_RTX
,
2039 mode
, 1, default_label
, probability
);
2042 emit_jump (jump_target_rtx (node
->code_label
));