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"
50 #include "insn-config.h"
54 #include "diagnostic-core.h"
56 #include "langhooks.h"
58 #include "insn-codes.h"
62 #include "basic-block.h"
63 #include "tree-ssa-alias.h"
64 #include "internal-fn.h"
65 #include "gimple-expr.h"
69 #include "alloc-pool.h"
70 #include "pretty-print.h"
76 /* Functions and data structures for expanding case statements. */
78 /* Case label structure, used to hold info on labels within case
79 statements. We handle "range" labels; for a single-value label
80 as in C, the high and low limits are the same.
82 We start with a vector of case nodes sorted in ascending order, and
83 the default label as the last element in the vector. Before expanding
84 to RTL, we transform this vector into a list linked via the RIGHT
85 fields in the case_node struct. Nodes with higher case values are
88 Switch statements can be output in three forms. A branch table is
89 used if there are more than a few labels and the labels are dense
90 within the range between the smallest and largest case value. If a
91 branch table is used, no further manipulations are done with the case
94 The alternative to the use of a branch table is to generate a series
95 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
96 and PARENT fields to hold a binary tree. Initially the tree is
97 totally unbalanced, with everything on the right. We balance the tree
98 with nodes on the left having lower case values than the parent
99 and nodes on the right having higher values. We then output the tree
102 For very small, suitable switch statements, we can generate a series
103 of simple bit test and branches instead. */
107 struct case_node
*left
; /* Left son in binary tree */
108 struct case_node
*right
; /* Right son in binary tree; also node chain */
109 struct case_node
*parent
; /* Parent of node in binary tree */
110 tree low
; /* Lowest index value for this label */
111 tree high
; /* Highest index value for this label */
112 tree code_label
; /* Label to jump to when node matches */
113 int prob
; /* Probability of taking this case. */
114 /* Probability of reaching subtree rooted at this node */
118 typedef struct case_node case_node
;
119 typedef struct case_node
*case_node_ptr
;
121 extern basic_block
label_to_block_fn (struct function
*, tree
);
123 static bool check_unique_operand_names (tree
, tree
, tree
);
124 static char *resolve_operand_name_1 (char *, tree
, tree
, tree
);
125 static void balance_case_nodes (case_node_ptr
*, case_node_ptr
);
126 static int node_has_low_bound (case_node_ptr
, tree
);
127 static int node_has_high_bound (case_node_ptr
, tree
);
128 static int node_is_bounded (case_node_ptr
, tree
);
129 static void emit_case_nodes (rtx
, case_node_ptr
, rtx
, int, tree
);
131 /* Return the rtx-label that corresponds to a LABEL_DECL,
132 creating it if necessary. */
135 label_rtx (tree label
)
137 gcc_assert (TREE_CODE (label
) == LABEL_DECL
);
139 if (!DECL_RTL_SET_P (label
))
141 rtx_code_label
*r
= gen_label_rtx ();
142 SET_DECL_RTL (label
, r
);
143 if (FORCED_LABEL (label
) || DECL_NONLOCAL (label
))
144 LABEL_PRESERVE_P (r
) = 1;
147 return DECL_RTL (label
);
150 /* As above, but also put it on the forced-reference list of the
151 function that contains it. */
153 force_label_rtx (tree label
)
155 rtx_insn
*ref
= as_a
<rtx_insn
*> (label_rtx (label
));
156 tree function
= decl_function_context (label
);
158 gcc_assert (function
);
160 forced_labels
= gen_rtx_INSN_LIST (VOIDmode
, ref
, forced_labels
);
164 /* Add an unconditional jump to LABEL as the next sequential instruction. */
167 emit_jump (rtx label
)
169 do_pending_stack_adjust ();
170 emit_jump_insn (gen_jump (label
));
174 /* Handle goto statements and the labels that they can go to. */
176 /* Specify the location in the RTL code of a label LABEL,
177 which is a LABEL_DECL tree node.
179 This is used for the kind of label that the user can jump to with a
180 goto statement, and for alternatives of a switch or case statement.
181 RTL labels generated for loops and conditionals don't go through here;
182 they are generated directly at the RTL level, by other functions below.
184 Note that this has nothing to do with defining label *names*.
185 Languages vary in how they do that and what that even means. */
188 expand_label (tree label
)
190 rtx_insn
*label_r
= as_a
<rtx_insn
*> (label_rtx (label
));
192 do_pending_stack_adjust ();
193 emit_label (label_r
);
194 if (DECL_NAME (label
))
195 LABEL_NAME (DECL_RTL (label
)) = IDENTIFIER_POINTER (DECL_NAME (label
));
197 if (DECL_NONLOCAL (label
))
199 expand_builtin_setjmp_receiver (NULL
);
200 nonlocal_goto_handler_labels
201 = gen_rtx_INSN_LIST (VOIDmode
, label_r
,
202 nonlocal_goto_handler_labels
);
205 if (FORCED_LABEL (label
))
206 forced_labels
= gen_rtx_INSN_LIST (VOIDmode
, label_r
, forced_labels
);
208 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
209 maybe_set_first_label_num (label_r
);
212 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
213 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
214 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
215 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
216 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
217 constraint allows the use of a register operand. And, *IS_INOUT
218 will be true if the operand is read-write, i.e., if it is used as
219 an input as well as an output. If *CONSTRAINT_P is not in
220 canonical form, it will be made canonical. (Note that `+' will be
221 replaced with `=' as part of this process.)
223 Returns TRUE if all went well; FALSE if an error occurred. */
226 parse_output_constraint (const char **constraint_p
, int operand_num
,
227 int ninputs
, int noutputs
, bool *allows_mem
,
228 bool *allows_reg
, bool *is_inout
)
230 const char *constraint
= *constraint_p
;
233 /* Assume the constraint doesn't allow the use of either a register
238 /* Allow the `=' or `+' to not be at the beginning of the string,
239 since it wasn't explicitly documented that way, and there is a
240 large body of code that puts it last. Swap the character to
241 the front, so as not to uglify any place else. */
242 p
= strchr (constraint
, '=');
244 p
= strchr (constraint
, '+');
246 /* If the string doesn't contain an `=', issue an error
250 error ("output operand constraint lacks %<=%>");
254 /* If the constraint begins with `+', then the operand is both read
255 from and written to. */
256 *is_inout
= (*p
== '+');
258 /* Canonicalize the output constraint so that it begins with `='. */
259 if (p
!= constraint
|| *is_inout
)
262 size_t c_len
= strlen (constraint
);
265 warning (0, "output constraint %qc for operand %d "
266 "is not at the beginning",
269 /* Make a copy of the constraint. */
270 buf
= XALLOCAVEC (char, c_len
+ 1);
271 strcpy (buf
, constraint
);
272 /* Swap the first character and the `=' or `+'. */
273 buf
[p
- constraint
] = buf
[0];
274 /* Make sure the first character is an `='. (Until we do this,
275 it might be a `+'.) */
277 /* Replace the constraint with the canonicalized string. */
278 *constraint_p
= ggc_alloc_string (buf
, c_len
);
279 constraint
= *constraint_p
;
282 /* Loop through the constraint string. */
283 for (p
= constraint
+ 1; *p
; p
+= CONSTRAINT_LEN (*p
, p
))
288 error ("operand constraint contains incorrectly positioned "
293 if (operand_num
+ 1 == ninputs
+ noutputs
)
295 error ("%<%%%> constraint used with last operand");
300 case '?': case '!': case '*': case '&': case '#':
301 case 'E': case 'F': case 'G': case 'H':
302 case 's': case 'i': case 'n':
303 case 'I': case 'J': case 'K': case 'L': case 'M':
304 case 'N': case 'O': case 'P': case ',':
307 case '0': case '1': case '2': case '3': case '4':
308 case '5': case '6': case '7': case '8': case '9':
310 error ("matching constraint not valid in output operand");
314 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
315 excepting those that expand_call created. So match memory
328 enum constraint_num cn
= lookup_constraint (p
);
329 if (reg_class_for_constraint (cn
) != NO_REGS
330 || insn_extra_address_constraint (cn
))
332 else if (insn_extra_memory_constraint (cn
))
336 /* Otherwise we can't assume anything about the nature of
337 the constraint except that it isn't purely registers.
338 Treat it like "g" and hope for the best. */
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 '#':
391 case 'E': case 'F': case 'G': case 'H':
392 case 's': case 'i': case 'n':
393 case 'I': case 'J': case 'K': case 'L': case 'M':
394 case 'N': case 'O': case 'P': case ',':
397 /* Whether or not a numeric constraint allows a register is
398 decided by the matching constraint, and so there is no need
399 to do anything special with them. We must handle them in
400 the default case, so that we don't unnecessarily force
401 operands to memory. */
402 case '0': case '1': case '2': case '3': case '4':
403 case '5': case '6': case '7': case '8': case '9':
410 match
= strtoul (constraint
+ j
, &end
, 10);
411 if (match
>= (unsigned long) noutputs
)
413 error ("matching constraint references invalid operand number");
417 /* Try and find the real constraint for this dup. Only do this
418 if the matching constraint is the only alternative. */
420 && (j
== 0 || (j
== 1 && constraint
[0] == '%')))
422 constraint
= constraints
[match
];
423 *constraint_p
= constraint
;
424 c_len
= strlen (constraint
);
426 /* ??? At the end of the loop, we will skip the first part of
427 the matched constraint. This assumes not only that the
428 other constraint is an output constraint, but also that
429 the '=' or '+' come first. */
433 j
= end
- constraint
;
434 /* Anticipate increment at end of loop. */
445 if (! ISALPHA (constraint
[j
]))
447 error ("invalid punctuation %qc in constraint", constraint
[j
]);
450 enum constraint_num cn
= lookup_constraint (constraint
+ j
);
451 if (reg_class_for_constraint (cn
) != NO_REGS
452 || insn_extra_address_constraint (cn
))
454 else if (insn_extra_memory_constraint (cn
))
458 /* Otherwise we can't assume anything about the nature of
459 the constraint except that it isn't purely registers.
460 Treat it like "g" and hope for the best. */
467 if (saw_match
&& !*allows_reg
)
468 warning (0, "matching constraint does not allow a register");
473 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
474 can be an asm-declared register. Called via walk_tree. */
477 decl_overlaps_hard_reg_set_p (tree
*declp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
481 const HARD_REG_SET
*const regs
= (const HARD_REG_SET
*) data
;
483 if (TREE_CODE (decl
) == VAR_DECL
)
485 if (DECL_HARD_REGISTER (decl
)
486 && REG_P (DECL_RTL (decl
))
487 && REGNO (DECL_RTL (decl
)) < FIRST_PSEUDO_REGISTER
)
489 rtx reg
= DECL_RTL (decl
);
491 if (overlaps_hard_reg_set_p (*regs
, GET_MODE (reg
), REGNO (reg
)))
496 else if (TYPE_P (decl
) || TREE_CODE (decl
) == PARM_DECL
)
501 /* If there is an overlap between *REGS and DECL, return the first overlap
504 tree_overlaps_hard_reg_set (tree decl
, HARD_REG_SET
*regs
)
506 return walk_tree (&decl
, decl_overlaps_hard_reg_set_p
, regs
, NULL
);
510 /* A subroutine of expand_asm_operands. Check that all operand names
511 are unique. Return true if so. We rely on the fact that these names
512 are identifiers, and so have been canonicalized by get_identifier,
513 so all we need are pointer comparisons. */
516 check_unique_operand_names (tree outputs
, tree inputs
, tree labels
)
518 tree i
, j
, i_name
= NULL_TREE
;
520 for (i
= outputs
; i
; i
= TREE_CHAIN (i
))
522 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
526 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
527 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
531 for (i
= inputs
; i
; i
= TREE_CHAIN (i
))
533 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
537 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
538 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
540 for (j
= outputs
; j
; j
= TREE_CHAIN (j
))
541 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
545 for (i
= labels
; i
; i
= TREE_CHAIN (i
))
547 i_name
= TREE_PURPOSE (i
);
551 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
552 if (simple_cst_equal (i_name
, TREE_PURPOSE (j
)))
554 for (j
= inputs
; j
; j
= TREE_CHAIN (j
))
555 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
562 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name
));
566 /* A subroutine of expand_asm_operands. Resolve the names of the operands
567 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
568 STRING and in the constraints to those numbers. */
571 resolve_asm_operand_names (tree string
, tree outputs
, tree inputs
, tree labels
)
578 check_unique_operand_names (outputs
, inputs
, labels
);
580 /* Substitute [<name>] in input constraint strings. There should be no
581 named operands in output constraints. */
582 for (t
= inputs
; t
; t
= TREE_CHAIN (t
))
584 c
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
585 if (strchr (c
, '[') != NULL
)
587 p
= buffer
= xstrdup (c
);
588 while ((p
= strchr (p
, '[')) != NULL
)
589 p
= resolve_operand_name_1 (p
, outputs
, inputs
, NULL
);
590 TREE_VALUE (TREE_PURPOSE (t
))
591 = build_string (strlen (buffer
), buffer
);
596 /* Now check for any needed substitutions in the template. */
597 c
= TREE_STRING_POINTER (string
);
598 while ((c
= strchr (c
, '%')) != NULL
)
602 else if (ISALPHA (c
[1]) && c
[2] == '[')
606 c
+= 1 + (c
[1] == '%');
613 /* OK, we need to make a copy so we can perform the substitutions.
614 Assume that we will not need extra space--we get to remove '['
615 and ']', which means we cannot have a problem until we have more
616 than 999 operands. */
617 buffer
= xstrdup (TREE_STRING_POINTER (string
));
618 p
= buffer
+ (c
- TREE_STRING_POINTER (string
));
620 while ((p
= strchr (p
, '%')) != NULL
)
624 else if (ISALPHA (p
[1]) && p
[2] == '[')
628 p
+= 1 + (p
[1] == '%');
632 p
= resolve_operand_name_1 (p
, outputs
, inputs
, labels
);
635 string
= build_string (strlen (buffer
), buffer
);
642 /* A subroutine of resolve_operand_names. P points to the '[' for a
643 potential named operand of the form [<name>]. In place, replace
644 the name and brackets with a number. Return a pointer to the
645 balance of the string after substitution. */
648 resolve_operand_name_1 (char *p
, tree outputs
, tree inputs
, tree labels
)
654 /* Collect the operand name. */
655 q
= strchr (++p
, ']');
658 error ("missing close brace for named operand");
659 return strchr (p
, '\0');
663 /* Resolve the name to a number. */
664 for (op
= 0, t
= outputs
; t
; t
= TREE_CHAIN (t
), op
++)
666 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
667 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
670 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), op
++)
672 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
673 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
676 for (t
= labels
; t
; t
= TREE_CHAIN (t
), op
++)
678 tree name
= TREE_PURPOSE (t
);
679 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
683 error ("undefined named operand %qs", identifier_to_locale (p
));
687 /* Replace the name with the number. Unfortunately, not all libraries
688 get the return value of sprintf correct, so search for the end of the
689 generated string by hand. */
690 sprintf (--p
, "%d", op
);
691 p
= strchr (p
, '\0');
693 /* Verify the no extra buffer space assumption. */
696 /* Shift the rest of the buffer down to fill the gap. */
697 memmove (p
, q
+ 1, strlen (q
+ 1) + 1);
703 /* Generate RTL to return directly from the current function.
704 (That is, we bypass any return value.) */
707 expand_naked_return (void)
711 clear_pending_stack_adjust ();
712 do_pending_stack_adjust ();
714 end_label
= naked_return_label
;
716 end_label
= naked_return_label
= gen_label_rtx ();
718 emit_jump (end_label
);
721 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
722 is the probability of jumping to LABEL. */
724 do_jump_if_equal (machine_mode mode
, rtx op0
, rtx op1
, rtx label
,
725 int unsignedp
, int prob
)
727 gcc_assert (prob
<= REG_BR_PROB_BASE
);
728 do_compare_rtx_and_jump (op0
, op1
, EQ
, unsignedp
, mode
,
729 NULL_RTX
, NULL_RTX
, label
, prob
);
732 /* Do the insertion of a case label into case_list. The labels are
733 fed to us in descending order from the sorted vector of case labels used
734 in the tree part of the middle end. So the list we construct is
735 sorted in ascending order.
737 LABEL is the case label to be inserted. LOW and HIGH are the bounds
738 against which the index is compared to jump to LABEL and PROB is the
739 estimated probability LABEL is reached from the switch statement. */
741 static struct case_node
*
742 add_case_node (struct case_node
*head
, tree low
, tree high
,
743 tree label
, int prob
, alloc_pool case_node_pool
)
747 gcc_checking_assert (low
);
748 gcc_checking_assert (high
&& (TREE_TYPE (low
) == TREE_TYPE (high
)));
750 /* Add this label to the chain. */
751 r
= (struct case_node
*) pool_alloc (case_node_pool
);
754 r
->code_label
= label
;
755 r
->parent
= r
->left
= NULL
;
757 r
->subtree_prob
= prob
;
762 /* Dump ROOT, a list or tree of case nodes, to file. */
765 dump_case_nodes (FILE *f
, struct case_node
*root
,
766 int indent_step
, int indent_level
)
772 dump_case_nodes (f
, root
->left
, indent_step
, indent_level
);
775 fprintf (f
, "%*s", indent_step
* indent_level
, "");
776 print_dec (root
->low
, f
, TYPE_SIGN (TREE_TYPE (root
->low
)));
777 if (!tree_int_cst_equal (root
->low
, root
->high
))
779 fprintf (f
, " ... ");
780 print_dec (root
->high
, f
, TYPE_SIGN (TREE_TYPE (root
->high
)));
784 dump_case_nodes (f
, root
->right
, indent_step
, indent_level
);
788 #define HAVE_casesi 0
791 #ifndef HAVE_tablejump
792 #define HAVE_tablejump 0
795 /* Return the smallest number of different values for which it is best to use a
796 jump-table instead of a tree of conditional branches. */
799 case_values_threshold (void)
801 unsigned int threshold
= PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD
);
804 threshold
= targetm
.case_values_threshold ();
809 /* Return true if a switch should be expanded as a decision tree.
810 RANGE is the difference between highest and lowest case.
811 UNIQ is number of unique case node targets, not counting the default case.
812 COUNT is the number of comparisons needed, not counting the default case. */
815 expand_switch_as_decision_tree_p (tree range
,
816 unsigned int uniq ATTRIBUTE_UNUSED
,
821 /* If neither casesi or tablejump is available, or flag_jump_tables
822 over-ruled us, we really have no choice. */
823 if (!HAVE_casesi
&& !HAVE_tablejump
)
825 if (!flag_jump_tables
)
827 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
832 /* If the switch is relatively small such that the cost of one
833 indirect jump on the target are higher than the cost of a
834 decision tree, go with the decision tree.
836 If range of values is much bigger than number of values,
837 or if it is too large to represent in a HOST_WIDE_INT,
838 make a sequence of conditional branches instead of a dispatch.
840 The definition of "much bigger" depends on whether we are
841 optimizing for size or for speed. If the former, the maximum
842 ratio range/count = 3, because this was found to be the optimal
843 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
844 10 is much older, and was probably selected after an extensive
845 benchmarking investigation on numerous platforms. Or maybe it
846 just made sense to someone at some point in the history of GCC,
848 max_ratio
= optimize_insn_for_size_p () ? 3 : 10;
849 if (count
< case_values_threshold ()
850 || ! tree_fits_uhwi_p (range
)
851 || compare_tree_int (range
, max_ratio
* count
) > 0)
857 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
858 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
859 DEFAULT_PROB is the estimated probability that it jumps to
862 We generate a binary decision tree to select the appropriate target
863 code. This is done as follows:
865 If the index is a short or char that we do not have
866 an insn to handle comparisons directly, convert it to
867 a full integer now, rather than letting each comparison
868 generate the conversion.
870 Load the index into a register.
872 The list of cases is rearranged into a binary tree,
873 nearly optimal assuming equal probability for each case.
875 The tree is transformed into RTL, eliminating redundant
876 test conditions at the same time.
878 If program flow could reach the end of the decision tree
879 an unconditional jump to the default code is emitted.
881 The above process is unaware of the CFG. The caller has to fix up
882 the CFG itself. This is done in cfgexpand.c. */
885 emit_case_decision_tree (tree index_expr
, tree index_type
,
886 struct case_node
*case_list
, rtx default_label
,
889 rtx index
= expand_normal (index_expr
);
891 if (GET_MODE_CLASS (GET_MODE (index
)) == MODE_INT
892 && ! have_insn_for (COMPARE
, GET_MODE (index
)))
894 int unsignedp
= TYPE_UNSIGNED (index_type
);
895 machine_mode wider_mode
;
896 for (wider_mode
= GET_MODE (index
); wider_mode
!= VOIDmode
;
897 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
898 if (have_insn_for (COMPARE
, wider_mode
))
900 index
= convert_to_mode (wider_mode
, index
, unsignedp
);
905 do_pending_stack_adjust ();
909 index
= copy_to_reg (index
);
910 if (TREE_CODE (index_expr
) == SSA_NAME
)
911 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr
), index
);
914 balance_case_nodes (&case_list
, NULL
);
916 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
918 int indent_step
= ceil_log2 (TYPE_PRECISION (index_type
)) + 2;
919 fprintf (dump_file
, ";; Expanding GIMPLE switch as decision tree:\n");
920 dump_case_nodes (dump_file
, case_list
, indent_step
, 0);
923 emit_case_nodes (index
, case_list
, default_label
, default_prob
, index_type
);
925 emit_jump (default_label
);
928 /* Return the sum of probabilities of outgoing edges of basic block BB. */
931 get_outgoing_edge_probs (basic_block bb
)
938 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
939 prob_sum
+= e
->probability
;
943 /* Computes the conditional probability of jumping to a target if the branch
944 instruction is executed.
945 TARGET_PROB is the estimated probability of jumping to a target relative
946 to some basic block BB.
947 BASE_PROB is the probability of reaching the branch instruction relative
948 to the same basic block BB. */
951 conditional_probability (int target_prob
, int base_prob
)
955 gcc_assert (target_prob
>= 0);
956 gcc_assert (target_prob
<= base_prob
);
957 return GCOV_COMPUTE_SCALE (target_prob
, base_prob
);
962 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
963 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
964 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
965 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
967 First, a jump insn is emitted. First we try "casesi". If that
968 fails, try "tablejump". A target *must* have one of them (or both).
970 Then, a table with the target labels is emitted.
972 The process is unaware of the CFG. The caller has to fix up
973 the CFG itself. This is done in cfgexpand.c. */
976 emit_case_dispatch_table (tree index_expr
, tree index_type
,
977 struct case_node
*case_list
, rtx default_label
,
978 tree minval
, tree maxval
, tree range
,
984 rtx fallback_label
= label_rtx (case_list
->code_label
);
985 rtx_code_label
*table_label
= gen_label_rtx ();
986 bool has_gaps
= false;
987 edge default_edge
= stmt_bb
? EDGE_SUCC (stmt_bb
, 0) : NULL
;
988 int default_prob
= default_edge
? default_edge
->probability
: 0;
989 int base
= get_outgoing_edge_probs (stmt_bb
);
990 bool try_with_tablejump
= false;
992 int new_default_prob
= conditional_probability (default_prob
,
995 if (! try_casesi (index_type
, index_expr
, minval
, range
,
996 table_label
, default_label
, fallback_label
,
999 /* Index jumptables from zero for suitable values of minval to avoid
1000 a subtraction. For the rationale see:
1001 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
1002 if (optimize_insn_for_speed_p ()
1003 && compare_tree_int (minval
, 0) > 0
1004 && compare_tree_int (minval
, 3) < 0)
1006 minval
= build_int_cst (index_type
, 0);
1010 try_with_tablejump
= true;
1013 /* Get table of labels to jump to, in order of case index. */
1015 ncases
= tree_to_shwi (range
) + 1;
1016 labelvec
= XALLOCAVEC (rtx
, ncases
);
1017 memset (labelvec
, 0, ncases
* sizeof (rtx
));
1019 for (n
= case_list
; n
; n
= n
->right
)
1021 /* Compute the low and high bounds relative to the minimum
1022 value since that should fit in a HOST_WIDE_INT while the
1023 actual values may not. */
1025 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1027 HOST_WIDE_INT i_high
1028 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1032 for (i
= i_low
; i
<= i_high
; i
++)
1034 = gen_rtx_LABEL_REF (Pmode
, label_rtx (n
->code_label
));
1037 /* Fill in the gaps with the default. We may have gaps at
1038 the beginning if we tried to avoid the minval subtraction,
1039 so substitute some label even if the default label was
1040 deemed unreachable. */
1042 default_label
= fallback_label
;
1043 for (i
= 0; i
< ncases
; i
++)
1044 if (labelvec
[i
] == 0)
1047 labelvec
[i
] = gen_rtx_LABEL_REF (Pmode
, default_label
);
1052 /* There is at least one entry in the jump table that jumps
1053 to default label. The default label can either be reached
1054 through the indirect jump or the direct conditional jump
1055 before that. Split the probability of reaching the
1056 default label among these two jumps. */
1057 new_default_prob
= conditional_probability (default_prob
/2,
1060 base
-= default_prob
;
1064 base
-= default_prob
;
1069 default_edge
->probability
= default_prob
;
1071 /* We have altered the probability of the default edge. So the probabilities
1072 of all other edges need to be adjusted so that it sums up to
1073 REG_BR_PROB_BASE. */
1078 FOR_EACH_EDGE (e
, ei
, stmt_bb
->succs
)
1079 e
->probability
= GCOV_COMPUTE_SCALE (e
->probability
, base
);
1082 if (try_with_tablejump
)
1084 bool ok
= try_tablejump (index_type
, index_expr
, minval
, range
,
1085 table_label
, default_label
, new_default_prob
);
1088 /* Output the table. */
1089 emit_label (table_label
);
1091 if (CASE_VECTOR_PC_RELATIVE
|| flag_pic
)
1092 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE
,
1093 gen_rtx_LABEL_REF (Pmode
,
1095 gen_rtvec_v (ncases
, labelvec
),
1096 const0_rtx
, const0_rtx
));
1098 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE
,
1099 gen_rtvec_v (ncases
, labelvec
)));
1101 /* Record no drop-through after the table. */
1105 /* Reset the aux field of all outgoing edges of basic block BB. */
1108 reset_out_edges_aux (basic_block bb
)
1112 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1116 /* Compute the number of case labels that correspond to each outgoing edge of
1117 STMT. Record this information in the aux field of the edge. */
1120 compute_cases_per_edge (gswitch
*stmt
)
1122 basic_block bb
= gimple_bb (stmt
);
1123 reset_out_edges_aux (bb
);
1124 int ncases
= gimple_switch_num_labels (stmt
);
1125 for (int i
= ncases
- 1; i
>= 1; --i
)
1127 tree elt
= gimple_switch_label (stmt
, i
);
1128 tree lab
= CASE_LABEL (elt
);
1129 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1130 edge case_edge
= find_edge (bb
, case_bb
);
1131 case_edge
->aux
= (void *)((intptr_t)(case_edge
->aux
) + 1);
1135 /* Terminate a case (Pascal/Ada) or switch (C) statement
1136 in which ORIG_INDEX is the expression to be tested.
1137 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
1138 type as given in the source before any compiler conversions.
1139 Generate the code to test it and jump to the right place. */
1142 expand_case (gswitch
*stmt
)
1144 tree minval
= NULL_TREE
, maxval
= NULL_TREE
, range
= NULL_TREE
;
1145 rtx default_label
= NULL_RTX
;
1146 unsigned int count
, uniq
;
1148 int ncases
= gimple_switch_num_labels (stmt
);
1149 tree index_expr
= gimple_switch_index (stmt
);
1150 tree index_type
= TREE_TYPE (index_expr
);
1152 basic_block bb
= gimple_bb (stmt
);
1154 /* A list of case labels; it is first built as a list and it may then
1155 be rearranged into a nearly balanced binary tree. */
1156 struct case_node
*case_list
= 0;
1158 /* A pool for case nodes. */
1159 alloc_pool case_node_pool
;
1161 /* An ERROR_MARK occurs for various reasons including invalid data type.
1162 ??? Can this still happen, with GIMPLE and all? */
1163 if (index_type
== error_mark_node
)
1166 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
1167 expressions being INTEGER_CST. */
1168 gcc_assert (TREE_CODE (index_expr
) != INTEGER_CST
);
1170 case_node_pool
= create_alloc_pool ("struct case_node pool",
1171 sizeof (struct case_node
),
1174 do_pending_stack_adjust ();
1176 /* Find the default case target label. */
1177 default_label
= label_rtx (CASE_LABEL (gimple_switch_default_label (stmt
)));
1178 edge default_edge
= EDGE_SUCC (bb
, 0);
1179 int default_prob
= default_edge
->probability
;
1181 /* Get upper and lower bounds of case values. */
1182 elt
= gimple_switch_label (stmt
, 1);
1183 minval
= fold_convert (index_type
, CASE_LOW (elt
));
1184 elt
= gimple_switch_label (stmt
, ncases
- 1);
1185 if (CASE_HIGH (elt
))
1186 maxval
= fold_convert (index_type
, CASE_HIGH (elt
));
1188 maxval
= fold_convert (index_type
, CASE_LOW (elt
));
1190 /* Compute span of values. */
1191 range
= fold_build2 (MINUS_EXPR
, index_type
, maxval
, minval
);
1193 /* Listify the labels queue and gather some numbers to decide
1194 how to expand this switch(). */
1197 hash_set
<tree
> seen_labels
;
1198 compute_cases_per_edge (stmt
);
1200 for (i
= ncases
- 1; i
>= 1; --i
)
1202 elt
= gimple_switch_label (stmt
, i
);
1203 tree low
= CASE_LOW (elt
);
1205 tree high
= CASE_HIGH (elt
);
1206 gcc_assert (! high
|| tree_int_cst_lt (low
, high
));
1207 tree lab
= CASE_LABEL (elt
);
1209 /* Count the elements.
1210 A range counts double, since it requires two compares. */
1215 /* If we have not seen this label yet, then increase the
1216 number of unique case node targets seen. */
1217 if (!seen_labels
.add (lab
))
1220 /* The bounds on the case range, LOW and HIGH, have to be converted
1221 to case's index type TYPE. Note that the original type of the
1222 case index in the source code is usually "lost" during
1223 gimplification due to type promotion, but the case labels retain the
1224 original type. Make sure to drop overflow flags. */
1225 low
= fold_convert (index_type
, low
);
1226 if (TREE_OVERFLOW (low
))
1227 low
= wide_int_to_tree (index_type
, low
);
1229 /* The canonical from of a case label in GIMPLE is that a simple case
1230 has an empty CASE_HIGH. For the casesi and tablejump expanders,
1231 the back ends want simple cases to have high == low. */
1234 high
= fold_convert (index_type
, high
);
1235 if (TREE_OVERFLOW (high
))
1236 high
= wide_int_to_tree (index_type
, high
);
1238 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1239 edge case_edge
= find_edge (bb
, case_bb
);
1240 case_list
= add_case_node (
1241 case_list
, low
, high
, lab
,
1242 case_edge
->probability
/ (intptr_t)(case_edge
->aux
),
1245 reset_out_edges_aux (bb
);
1247 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
1248 destination, such as one with a default case only.
1249 It also removes cases that are out of range for the switch
1250 type, so we should never get a zero here. */
1251 gcc_assert (count
> 0);
1253 rtx_insn
*before_case
= get_last_insn ();
1255 /* Decide how to expand this switch.
1256 The two options at this point are a dispatch table (casesi or
1257 tablejump) or a decision tree. */
1259 if (expand_switch_as_decision_tree_p (range
, uniq
, count
))
1260 emit_case_decision_tree (index_expr
, index_type
,
1261 case_list
, default_label
,
1264 emit_case_dispatch_table (index_expr
, index_type
,
1265 case_list
, default_label
,
1266 minval
, maxval
, range
, bb
);
1268 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1271 free_alloc_pool (case_node_pool
);
1274 /* Expand the dispatch to a short decrement chain if there are few cases
1275 to dispatch to. Likewise if neither casesi nor tablejump is available,
1276 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
1277 tablejump. The index mode is always the mode of integer_type_node.
1278 Trap if no case matches the index.
1280 DISPATCH_INDEX is the index expression to switch on. It should be a
1281 memory or register operand.
1283 DISPATCH_TABLE is a set of case labels. The set should be sorted in
1284 ascending order, be contiguous, starting with value 0, and contain only
1285 single-valued case labels. */
1288 expand_sjlj_dispatch_table (rtx dispatch_index
,
1289 vec
<tree
> dispatch_table
)
1291 tree index_type
= integer_type_node
;
1292 machine_mode index_mode
= TYPE_MODE (index_type
);
1294 int ncases
= dispatch_table
.length ();
1296 do_pending_stack_adjust ();
1297 rtx_insn
*before_case
= get_last_insn ();
1299 /* Expand as a decrement-chain if there are 5 or fewer dispatch
1300 labels. This covers more than 98% of the cases in libjava,
1301 and seems to be a reasonable compromise between the "old way"
1302 of expanding as a decision tree or dispatch table vs. the "new
1303 way" with decrement chain or dispatch table. */
1304 if (dispatch_table
.length () <= 5
1305 || (!HAVE_casesi
&& !HAVE_tablejump
)
1306 || !flag_jump_tables
)
1308 /* Expand the dispatch as a decrement chain:
1310 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1314 if (index == 0) do_0; else index--;
1315 if (index == 0) do_1; else index--;
1317 if (index == 0) do_N; else index--;
1319 This is more efficient than a dispatch table on most machines.
1320 The last "index--" is redundant but the code is trivially dead
1321 and will be cleaned up by later passes. */
1322 rtx index
= copy_to_mode_reg (index_mode
, dispatch_index
);
1323 rtx zero
= CONST0_RTX (index_mode
);
1324 for (int i
= 0; i
< ncases
; i
++)
1326 tree elt
= dispatch_table
[i
];
1327 rtx lab
= label_rtx (CASE_LABEL (elt
));
1328 do_jump_if_equal (index_mode
, index
, zero
, lab
, 0, -1);
1329 force_expand_binop (index_mode
, sub_optab
,
1330 index
, CONST1_RTX (index_mode
),
1331 index
, 0, OPTAB_DIRECT
);
1336 /* Similar to expand_case, but much simpler. */
1337 struct case_node
*case_list
= 0;
1338 alloc_pool case_node_pool
= create_alloc_pool ("struct sjlj_case pool",
1339 sizeof (struct case_node
),
1341 tree index_expr
= make_tree (index_type
, dispatch_index
);
1342 tree minval
= build_int_cst (index_type
, 0);
1343 tree maxval
= CASE_LOW (dispatch_table
.last ());
1344 tree range
= maxval
;
1345 rtx_code_label
*default_label
= gen_label_rtx ();
1347 for (int i
= ncases
- 1; i
>= 0; --i
)
1349 tree elt
= dispatch_table
[i
];
1350 tree low
= CASE_LOW (elt
);
1351 tree lab
= CASE_LABEL (elt
);
1352 case_list
= add_case_node (case_list
, low
, low
, lab
, 0, case_node_pool
);
1355 emit_case_dispatch_table (index_expr
, index_type
,
1356 case_list
, default_label
,
1357 minval
, maxval
, range
,
1358 BLOCK_FOR_INSN (before_case
));
1359 emit_label (default_label
);
1360 free_alloc_pool (case_node_pool
);
1363 /* Dispatching something not handled? Trap! */
1364 expand_builtin_trap ();
1366 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1372 /* Take an ordered list of case nodes
1373 and transform them into a near optimal binary tree,
1374 on the assumption that any target code selection value is as
1375 likely as any other.
1377 The transformation is performed by splitting the ordered
1378 list into two equal sections plus a pivot. The parts are
1379 then attached to the pivot as left and right branches. Each
1380 branch is then transformed recursively. */
1383 balance_case_nodes (case_node_ptr
*head
, case_node_ptr parent
)
1395 /* Count the number of entries on branch. Also count the ranges. */
1399 if (!tree_int_cst_equal (np
->low
, np
->high
))
1408 /* Split this list if it is long enough for that to help. */
1412 /* If there are just three nodes, split at the middle one. */
1414 npp
= &(*npp
)->right
;
1417 /* Find the place in the list that bisects the list's total cost,
1418 where ranges count as 2.
1419 Here I gets half the total cost. */
1420 i
= (i
+ ranges
+ 1) / 2;
1423 /* Skip nodes while their cost does not reach that amount. */
1424 if (!tree_int_cst_equal ((*npp
)->low
, (*npp
)->high
))
1429 npp
= &(*npp
)->right
;
1434 np
->parent
= parent
;
1437 /* Optimize each of the two split parts. */
1438 balance_case_nodes (&np
->left
, np
);
1439 balance_case_nodes (&np
->right
, np
);
1440 np
->subtree_prob
= np
->prob
;
1441 np
->subtree_prob
+= np
->left
->subtree_prob
;
1442 np
->subtree_prob
+= np
->right
->subtree_prob
;
1446 /* Else leave this branch as one level,
1447 but fill in `parent' fields. */
1449 np
->parent
= parent
;
1450 np
->subtree_prob
= np
->prob
;
1451 for (; np
->right
; np
= np
->right
)
1453 np
->right
->parent
= np
;
1454 (*head
)->subtree_prob
+= np
->right
->subtree_prob
;
1460 /* Search the parent sections of the case node tree
1461 to see if a test for the lower bound of NODE would be redundant.
1462 INDEX_TYPE is the type of the index expression.
1464 The instructions to generate the case decision tree are
1465 output in the same order as nodes are processed so it is
1466 known that if a parent node checks the range of the current
1467 node minus one that the current node is bounded at its lower
1468 span. Thus the test would be redundant. */
1471 node_has_low_bound (case_node_ptr node
, tree index_type
)
1474 case_node_ptr pnode
;
1476 /* If the lower bound of this node is the lowest value in the index type,
1477 we need not test it. */
1479 if (tree_int_cst_equal (node
->low
, TYPE_MIN_VALUE (index_type
)))
1482 /* If this node has a left branch, the value at the left must be less
1483 than that at this node, so it cannot be bounded at the bottom and
1484 we need not bother testing any further. */
1489 low_minus_one
= fold_build2 (MINUS_EXPR
, TREE_TYPE (node
->low
),
1491 build_int_cst (TREE_TYPE (node
->low
), 1));
1493 /* If the subtraction above overflowed, we can't verify anything.
1494 Otherwise, look for a parent that tests our value - 1. */
1496 if (! tree_int_cst_lt (low_minus_one
, node
->low
))
1499 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1500 if (tree_int_cst_equal (low_minus_one
, pnode
->high
))
1506 /* Search the parent sections of the case node tree
1507 to see if a test for the upper bound of NODE would be redundant.
1508 INDEX_TYPE is the type of the index expression.
1510 The instructions to generate the case decision tree are
1511 output in the same order as nodes are processed so it is
1512 known that if a parent node checks the range of the current
1513 node plus one that the current node is bounded at its upper
1514 span. Thus the test would be redundant. */
1517 node_has_high_bound (case_node_ptr node
, tree index_type
)
1520 case_node_ptr pnode
;
1522 /* If there is no upper bound, obviously no test is needed. */
1524 if (TYPE_MAX_VALUE (index_type
) == NULL
)
1527 /* If the upper bound of this node is the highest value in the type
1528 of the index expression, we need not test against it. */
1530 if (tree_int_cst_equal (node
->high
, TYPE_MAX_VALUE (index_type
)))
1533 /* If this node has a right branch, the value at the right must be greater
1534 than that at this node, so it cannot be bounded at the top and
1535 we need not bother testing any further. */
1540 high_plus_one
= fold_build2 (PLUS_EXPR
, TREE_TYPE (node
->high
),
1542 build_int_cst (TREE_TYPE (node
->high
), 1));
1544 /* If the addition above overflowed, we can't verify anything.
1545 Otherwise, look for a parent that tests our value + 1. */
1547 if (! tree_int_cst_lt (node
->high
, high_plus_one
))
1550 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1551 if (tree_int_cst_equal (high_plus_one
, pnode
->low
))
1557 /* Search the parent sections of the
1558 case node tree to see if both tests for the upper and lower
1559 bounds of NODE would be redundant. */
1562 node_is_bounded (case_node_ptr node
, tree index_type
)
1564 return (node_has_low_bound (node
, index_type
)
1565 && node_has_high_bound (node
, index_type
));
1569 /* Emit step-by-step code to select a case for the value of INDEX.
1570 The thus generated decision tree follows the form of the
1571 case-node binary tree NODE, whose nodes represent test conditions.
1572 INDEX_TYPE is the type of the index of the switch.
1574 Care is taken to prune redundant tests from the decision tree
1575 by detecting any boundary conditions already checked by
1576 emitted rtx. (See node_has_high_bound, node_has_low_bound
1577 and node_is_bounded, above.)
1579 Where the test conditions can be shown to be redundant we emit
1580 an unconditional jump to the target code. As a further
1581 optimization, the subordinates of a tree node are examined to
1582 check for bounded nodes. In this case conditional and/or
1583 unconditional jumps as a result of the boundary check for the
1584 current node are arranged to target the subordinates associated
1585 code for out of bound conditions on the current node.
1587 We can assume that when control reaches the code generated here,
1588 the index value has already been compared with the parents
1589 of this node, and determined to be on the same side of each parent
1590 as this node is. Thus, if this node tests for the value 51,
1591 and a parent tested for 52, we don't need to consider
1592 the possibility of a value greater than 51. If another parent
1593 tests for the value 50, then this node need not test anything. */
1596 emit_case_nodes (rtx index
, case_node_ptr node
, rtx default_label
,
1597 int default_prob
, tree index_type
)
1599 /* If INDEX has an unsigned type, we must make unsigned branches. */
1600 int unsignedp
= TYPE_UNSIGNED (index_type
);
1602 int prob
= node
->prob
, subtree_prob
= node
->subtree_prob
;
1603 machine_mode mode
= GET_MODE (index
);
1604 machine_mode imode
= TYPE_MODE (index_type
);
1606 /* Handle indices detected as constant during RTL expansion. */
1607 if (mode
== VOIDmode
)
1610 /* See if our parents have already tested everything for us.
1611 If they have, emit an unconditional jump for this node. */
1612 if (node_is_bounded (node
, index_type
))
1613 emit_jump (label_rtx (node
->code_label
));
1615 else if (tree_int_cst_equal (node
->low
, node
->high
))
1617 probability
= conditional_probability (prob
, subtree_prob
+ default_prob
);
1618 /* Node is single valued. First see if the index expression matches
1619 this node and then check our children, if any. */
1620 do_jump_if_equal (mode
, index
,
1621 convert_modes (mode
, imode
,
1622 expand_normal (node
->low
),
1624 label_rtx (node
->code_label
), unsignedp
, probability
);
1625 /* Since this case is taken at this point, reduce its weight from
1627 subtree_prob
-= prob
;
1628 if (node
->right
!= 0 && node
->left
!= 0)
1630 /* This node has children on both sides.
1631 Dispatch to one side or the other
1632 by comparing the index value with this node's value.
1633 If one subtree is bounded, check that one first,
1634 so we can avoid real branches in the tree. */
1636 if (node_is_bounded (node
->right
, index_type
))
1638 probability
= conditional_probability (
1640 subtree_prob
+ default_prob
);
1641 emit_cmp_and_jump_insns (index
,
1644 expand_normal (node
->high
),
1646 GT
, NULL_RTX
, mode
, unsignedp
,
1647 label_rtx (node
->right
->code_label
),
1649 emit_case_nodes (index
, node
->left
, default_label
, default_prob
,
1653 else if (node_is_bounded (node
->left
, index_type
))
1655 probability
= conditional_probability (
1657 subtree_prob
+ default_prob
);
1658 emit_cmp_and_jump_insns (index
,
1661 expand_normal (node
->high
),
1663 LT
, NULL_RTX
, mode
, unsignedp
,
1664 label_rtx (node
->left
->code_label
),
1666 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1669 /* If both children are single-valued cases with no
1670 children, finish up all the work. This way, we can save
1671 one ordered comparison. */
1672 else if (tree_int_cst_equal (node
->right
->low
, node
->right
->high
)
1673 && node
->right
->left
== 0
1674 && node
->right
->right
== 0
1675 && tree_int_cst_equal (node
->left
->low
, node
->left
->high
)
1676 && node
->left
->left
== 0
1677 && node
->left
->right
== 0)
1679 /* Neither node is bounded. First distinguish the two sides;
1680 then emit the code for one side at a time. */
1682 /* See if the value matches what the right hand side
1684 probability
= conditional_probability (
1686 subtree_prob
+ default_prob
);
1687 do_jump_if_equal (mode
, index
,
1688 convert_modes (mode
, imode
,
1689 expand_normal (node
->right
->low
),
1691 label_rtx (node
->right
->code_label
),
1692 unsignedp
, probability
);
1694 /* See if the value matches what the left hand side
1696 probability
= conditional_probability (
1698 subtree_prob
+ default_prob
);
1699 do_jump_if_equal (mode
, index
,
1700 convert_modes (mode
, imode
,
1701 expand_normal (node
->left
->low
),
1703 label_rtx (node
->left
->code_label
),
1704 unsignedp
, probability
);
1709 /* Neither node is bounded. First distinguish the two sides;
1710 then emit the code for one side at a time. */
1713 = build_decl (curr_insn_location (),
1714 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
1716 /* The default label could be reached either through the right
1717 subtree or the left subtree. Divide the probability
1719 probability
= conditional_probability (
1720 node
->right
->subtree_prob
+ default_prob
/2,
1721 subtree_prob
+ default_prob
);
1722 /* See if the value is on the right. */
1723 emit_cmp_and_jump_insns (index
,
1726 expand_normal (node
->high
),
1728 GT
, NULL_RTX
, mode
, unsignedp
,
1729 label_rtx (test_label
),
1733 /* Value must be on the left.
1734 Handle the left-hand subtree. */
1735 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1736 /* If left-hand subtree does nothing,
1739 emit_jump (default_label
);
1741 /* Code branches here for the right-hand subtree. */
1742 expand_label (test_label
);
1743 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1747 else if (node
->right
!= 0 && node
->left
== 0)
1749 /* Here we have a right child but no left so we issue a conditional
1750 branch to default and process the right child.
1752 Omit the conditional branch to default if the right child
1753 does not have any children and is single valued; it would
1754 cost too much space to save so little time. */
1756 if (node
->right
->right
|| node
->right
->left
1757 || !tree_int_cst_equal (node
->right
->low
, node
->right
->high
))
1759 if (!node_has_low_bound (node
, index_type
))
1761 probability
= conditional_probability (
1763 subtree_prob
+ default_prob
);
1764 emit_cmp_and_jump_insns (index
,
1767 expand_normal (node
->high
),
1769 LT
, NULL_RTX
, mode
, unsignedp
,
1775 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1779 probability
= conditional_probability (
1780 node
->right
->subtree_prob
,
1781 subtree_prob
+ default_prob
);
1782 /* We cannot process node->right normally
1783 since we haven't ruled out the numbers less than
1784 this node's value. So handle node->right explicitly. */
1785 do_jump_if_equal (mode
, index
,
1788 expand_normal (node
->right
->low
),
1790 label_rtx (node
->right
->code_label
), unsignedp
, probability
);
1794 else if (node
->right
== 0 && node
->left
!= 0)
1796 /* Just one subtree, on the left. */
1797 if (node
->left
->left
|| node
->left
->right
1798 || !tree_int_cst_equal (node
->left
->low
, node
->left
->high
))
1800 if (!node_has_high_bound (node
, index_type
))
1802 probability
= conditional_probability (
1804 subtree_prob
+ default_prob
);
1805 emit_cmp_and_jump_insns (index
,
1808 expand_normal (node
->high
),
1810 GT
, NULL_RTX
, mode
, unsignedp
,
1816 emit_case_nodes (index
, node
->left
, default_label
,
1817 default_prob
, index_type
);
1821 probability
= conditional_probability (
1822 node
->left
->subtree_prob
,
1823 subtree_prob
+ default_prob
);
1824 /* We cannot process node->left normally
1825 since we haven't ruled out the numbers less than
1826 this node's value. So handle node->left explicitly. */
1827 do_jump_if_equal (mode
, index
,
1830 expand_normal (node
->left
->low
),
1832 label_rtx (node
->left
->code_label
), unsignedp
, probability
);
1838 /* Node is a range. These cases are very similar to those for a single
1839 value, except that we do not start by testing whether this node
1840 is the one to branch to. */
1842 if (node
->right
!= 0 && node
->left
!= 0)
1844 /* Node has subtrees on both sides.
1845 If the right-hand subtree is bounded,
1846 test for it first, since we can go straight there.
1847 Otherwise, we need to make a branch in the control structure,
1848 then handle the two subtrees. */
1849 tree test_label
= 0;
1851 if (node_is_bounded (node
->right
, index_type
))
1853 /* Right hand node is fully bounded so we can eliminate any
1854 testing and branch directly to the target code. */
1855 probability
= conditional_probability (
1856 node
->right
->subtree_prob
,
1857 subtree_prob
+ default_prob
);
1858 emit_cmp_and_jump_insns (index
,
1861 expand_normal (node
->high
),
1863 GT
, NULL_RTX
, mode
, unsignedp
,
1864 label_rtx (node
->right
->code_label
),
1869 /* Right hand node requires testing.
1870 Branch to a label where we will handle it later. */
1872 test_label
= build_decl (curr_insn_location (),
1873 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
1874 probability
= conditional_probability (
1875 node
->right
->subtree_prob
+ default_prob
/2,
1876 subtree_prob
+ default_prob
);
1877 emit_cmp_and_jump_insns (index
,
1880 expand_normal (node
->high
),
1882 GT
, NULL_RTX
, mode
, unsignedp
,
1883 label_rtx (test_label
),
1888 /* Value belongs to this node or to the left-hand subtree. */
1890 probability
= conditional_probability (
1892 subtree_prob
+ default_prob
);
1893 emit_cmp_and_jump_insns (index
,
1896 expand_normal (node
->low
),
1898 GE
, NULL_RTX
, mode
, unsignedp
,
1899 label_rtx (node
->code_label
),
1902 /* Handle the left-hand subtree. */
1903 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1905 /* If right node had to be handled later, do that now. */
1909 /* If the left-hand subtree fell through,
1910 don't let it fall into the right-hand subtree. */
1912 emit_jump (default_label
);
1914 expand_label (test_label
);
1915 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1919 else if (node
->right
!= 0 && node
->left
== 0)
1921 /* Deal with values to the left of this node,
1922 if they are possible. */
1923 if (!node_has_low_bound (node
, index_type
))
1925 probability
= conditional_probability (
1927 subtree_prob
+ default_prob
);
1928 emit_cmp_and_jump_insns (index
,
1931 expand_normal (node
->low
),
1933 LT
, NULL_RTX
, mode
, unsignedp
,
1939 /* Value belongs to this node or to the right-hand subtree. */
1941 probability
= conditional_probability (
1943 subtree_prob
+ default_prob
);
1944 emit_cmp_and_jump_insns (index
,
1947 expand_normal (node
->high
),
1949 LE
, NULL_RTX
, mode
, unsignedp
,
1950 label_rtx (node
->code_label
),
1953 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1956 else if (node
->right
== 0 && node
->left
!= 0)
1958 /* Deal with values to the right of this node,
1959 if they are possible. */
1960 if (!node_has_high_bound (node
, index_type
))
1962 probability
= conditional_probability (
1964 subtree_prob
+ default_prob
);
1965 emit_cmp_and_jump_insns (index
,
1968 expand_normal (node
->high
),
1970 GT
, NULL_RTX
, mode
, unsignedp
,
1976 /* Value belongs to this node or to the left-hand subtree. */
1978 probability
= conditional_probability (
1980 subtree_prob
+ default_prob
);
1981 emit_cmp_and_jump_insns (index
,
1984 expand_normal (node
->low
),
1986 GE
, NULL_RTX
, mode
, unsignedp
,
1987 label_rtx (node
->code_label
),
1990 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1995 /* Node has no children so we check low and high bounds to remove
1996 redundant tests. Only one of the bounds can exist,
1997 since otherwise this node is bounded--a case tested already. */
1998 int high_bound
= node_has_high_bound (node
, index_type
);
1999 int low_bound
= node_has_low_bound (node
, index_type
);
2001 if (!high_bound
&& low_bound
)
2003 probability
= conditional_probability (
2005 subtree_prob
+ default_prob
);
2006 emit_cmp_and_jump_insns (index
,
2009 expand_normal (node
->high
),
2011 GT
, NULL_RTX
, mode
, unsignedp
,
2016 else if (!low_bound
&& high_bound
)
2018 probability
= conditional_probability (
2020 subtree_prob
+ default_prob
);
2021 emit_cmp_and_jump_insns (index
,
2024 expand_normal (node
->low
),
2026 LT
, NULL_RTX
, mode
, unsignedp
,
2030 else if (!low_bound
&& !high_bound
)
2032 /* Widen LOW and HIGH to the same width as INDEX. */
2033 tree type
= lang_hooks
.types
.type_for_mode (mode
, unsignedp
);
2034 tree low
= build1 (CONVERT_EXPR
, type
, node
->low
);
2035 tree high
= build1 (CONVERT_EXPR
, type
, node
->high
);
2036 rtx low_rtx
, new_index
, new_bound
;
2038 /* Instead of doing two branches, emit one unsigned branch for
2039 (index-low) > (high-low). */
2040 low_rtx
= expand_expr (low
, NULL_RTX
, mode
, EXPAND_NORMAL
);
2041 new_index
= expand_simple_binop (mode
, MINUS
, index
, low_rtx
,
2042 NULL_RTX
, unsignedp
,
2044 new_bound
= expand_expr (fold_build2 (MINUS_EXPR
, type
,
2046 NULL_RTX
, mode
, EXPAND_NORMAL
);
2048 probability
= conditional_probability (
2050 subtree_prob
+ default_prob
);
2051 emit_cmp_and_jump_insns (new_index
, new_bound
, GT
, NULL_RTX
,
2052 mode
, 1, default_label
, probability
);
2055 emit_jump (label_rtx (node
->code_label
));