1 /* Expands front end tree to back end RTL for GCC
2 Copyright (C) 1987-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file handles the generation of rtl code from tree structure
21 above the level of expressions, using subroutines in exp*.c and emit-rtl.c.
22 The functions whose names start with `expand_' are called by the
23 expander to generate RTL instructions for various kinds of constructs. */
27 #include "coretypes.h"
31 #include "hard-reg-set.h"
35 #include "double-int.h"
42 #include "fold-const.h"
44 #include "stor-layout.h"
49 #include "insn-config.h"
51 #include "statistics.h"
53 #include "fixed-value.h"
63 #include "diagnostic-core.h"
65 #include "langhooks.h"
67 #include "insn-codes.h"
71 #include "basic-block.h"
72 #include "tree-ssa-alias.h"
73 #include "internal-fn.h"
74 #include "gimple-expr.h"
78 #include "alloc-pool.h"
79 #include "pretty-print.h"
85 /* Functions and data structures for expanding case statements. */
87 /* Case label structure, used to hold info on labels within case
88 statements. We handle "range" labels; for a single-value label
89 as in C, the high and low limits are the same.
91 We start with a vector of case nodes sorted in ascending order, and
92 the default label as the last element in the vector. Before expanding
93 to RTL, we transform this vector into a list linked via the RIGHT
94 fields in the case_node struct. Nodes with higher case values are
97 Switch statements can be output in three forms. A branch table is
98 used if there are more than a few labels and the labels are dense
99 within the range between the smallest and largest case value. If a
100 branch table is used, no further manipulations are done with the case
103 The alternative to the use of a branch table is to generate a series
104 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
105 and PARENT fields to hold a binary tree. Initially the tree is
106 totally unbalanced, with everything on the right. We balance the tree
107 with nodes on the left having lower case values than the parent
108 and nodes on the right having higher values. We then output the tree
111 For very small, suitable switch statements, we can generate a series
112 of simple bit test and branches instead. */
116 struct case_node
*left
; /* Left son in binary tree */
117 struct case_node
*right
; /* Right son in binary tree; also node chain */
118 struct case_node
*parent
; /* Parent of node in binary tree */
119 tree low
; /* Lowest index value for this label */
120 tree high
; /* Highest index value for this label */
121 tree code_label
; /* Label to jump to when node matches */
122 int prob
; /* Probability of taking this case. */
123 /* Probability of reaching subtree rooted at this node */
127 typedef struct case_node case_node
;
128 typedef struct case_node
*case_node_ptr
;
130 extern basic_block
label_to_block_fn (struct function
*, tree
);
132 static bool check_unique_operand_names (tree
, tree
, tree
);
133 static char *resolve_operand_name_1 (char *, tree
, tree
, tree
);
134 static void balance_case_nodes (case_node_ptr
*, case_node_ptr
);
135 static int node_has_low_bound (case_node_ptr
, tree
);
136 static int node_has_high_bound (case_node_ptr
, tree
);
137 static int node_is_bounded (case_node_ptr
, tree
);
138 static void emit_case_nodes (rtx
, case_node_ptr
, rtx_code_label
*, int, tree
);
140 /* Return the rtx-label that corresponds to a LABEL_DECL,
141 creating it if necessary. */
144 label_rtx (tree label
)
146 gcc_assert (TREE_CODE (label
) == LABEL_DECL
);
148 if (!DECL_RTL_SET_P (label
))
150 rtx_code_label
*r
= gen_label_rtx ();
151 SET_DECL_RTL (label
, r
);
152 if (FORCED_LABEL (label
) || DECL_NONLOCAL (label
))
153 LABEL_PRESERVE_P (r
) = 1;
156 return as_a
<rtx_insn
*> (DECL_RTL (label
));
159 /* As above, but also put it on the forced-reference list of the
160 function that contains it. */
162 force_label_rtx (tree label
)
164 rtx_insn
*ref
= label_rtx (label
);
165 tree function
= decl_function_context (label
);
167 gcc_assert (function
);
169 forced_labels
= gen_rtx_INSN_LIST (VOIDmode
, ref
, forced_labels
);
173 /* As label_rtx, but ensures (in check build), that returned value is
174 an existing label (i.e. rtx with code CODE_LABEL). */
176 jump_target_rtx (tree label
)
178 return as_a
<rtx_code_label
*> (label_rtx (label
));
181 /* Add an unconditional jump to LABEL as the next sequential instruction. */
184 emit_jump (rtx label
)
186 do_pending_stack_adjust ();
187 emit_jump_insn (gen_jump (label
));
191 /* Handle goto statements and the labels that they can go to. */
193 /* Specify the location in the RTL code of a label LABEL,
194 which is a LABEL_DECL tree node.
196 This is used for the kind of label that the user can jump to with a
197 goto statement, and for alternatives of a switch or case statement.
198 RTL labels generated for loops and conditionals don't go through here;
199 they are generated directly at the RTL level, by other functions below.
201 Note that this has nothing to do with defining label *names*.
202 Languages vary in how they do that and what that even means. */
205 expand_label (tree label
)
207 rtx_code_label
*label_r
= jump_target_rtx (label
);
209 do_pending_stack_adjust ();
210 emit_label (label_r
);
211 if (DECL_NAME (label
))
212 LABEL_NAME (DECL_RTL (label
)) = IDENTIFIER_POINTER (DECL_NAME (label
));
214 if (DECL_NONLOCAL (label
))
216 expand_builtin_setjmp_receiver (NULL
);
217 nonlocal_goto_handler_labels
218 = gen_rtx_INSN_LIST (VOIDmode
, label_r
,
219 nonlocal_goto_handler_labels
);
222 if (FORCED_LABEL (label
))
223 forced_labels
= gen_rtx_INSN_LIST (VOIDmode
, label_r
, forced_labels
);
225 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
226 maybe_set_first_label_num (label_r
);
229 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
230 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
231 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
232 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
233 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
234 constraint allows the use of a register operand. And, *IS_INOUT
235 will be true if the operand is read-write, i.e., if it is used as
236 an input as well as an output. If *CONSTRAINT_P is not in
237 canonical form, it will be made canonical. (Note that `+' will be
238 replaced with `=' as part of this process.)
240 Returns TRUE if all went well; FALSE if an error occurred. */
243 parse_output_constraint (const char **constraint_p
, int operand_num
,
244 int ninputs
, int noutputs
, bool *allows_mem
,
245 bool *allows_reg
, bool *is_inout
)
247 const char *constraint
= *constraint_p
;
250 /* Assume the constraint doesn't allow the use of either a register
255 /* Allow the `=' or `+' to not be at the beginning of the string,
256 since it wasn't explicitly documented that way, and there is a
257 large body of code that puts it last. Swap the character to
258 the front, so as not to uglify any place else. */
259 p
= strchr (constraint
, '=');
261 p
= strchr (constraint
, '+');
263 /* If the string doesn't contain an `=', issue an error
267 error ("output operand constraint lacks %<=%>");
271 /* If the constraint begins with `+', then the operand is both read
272 from and written to. */
273 *is_inout
= (*p
== '+');
275 /* Canonicalize the output constraint so that it begins with `='. */
276 if (p
!= constraint
|| *is_inout
)
279 size_t c_len
= strlen (constraint
);
282 warning (0, "output constraint %qc for operand %d "
283 "is not at the beginning",
286 /* Make a copy of the constraint. */
287 buf
= XALLOCAVEC (char, c_len
+ 1);
288 strcpy (buf
, constraint
);
289 /* Swap the first character and the `=' or `+'. */
290 buf
[p
- constraint
] = buf
[0];
291 /* Make sure the first character is an `='. (Until we do this,
292 it might be a `+'.) */
294 /* Replace the constraint with the canonicalized string. */
295 *constraint_p
= ggc_alloc_string (buf
, c_len
);
296 constraint
= *constraint_p
;
299 /* Loop through the constraint string. */
300 for (p
= constraint
+ 1; *p
; p
+= CONSTRAINT_LEN (*p
, p
))
305 error ("operand constraint contains incorrectly positioned "
310 if (operand_num
+ 1 == ninputs
+ noutputs
)
312 error ("%<%%%> constraint used with last operand");
317 case '?': case '!': case '*': case '&': case '#':
319 case 'E': case 'F': case 'G': case 'H':
320 case 's': case 'i': case 'n':
321 case 'I': case 'J': case 'K': case 'L': case 'M':
322 case 'N': case 'O': case 'P': case ',':
325 case '0': case '1': case '2': case '3': case '4':
326 case '5': case '6': case '7': case '8': case '9':
328 error ("matching constraint not valid in output operand");
332 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
333 excepting those that expand_call created. So match memory
346 enum constraint_num cn
= lookup_constraint (p
);
347 if (reg_class_for_constraint (cn
) != NO_REGS
348 || insn_extra_address_constraint (cn
))
350 else if (insn_extra_memory_constraint (cn
))
353 insn_extra_constraint_allows_reg_mem (cn
, allows_reg
, allows_mem
);
360 /* Similar, but for input constraints. */
363 parse_input_constraint (const char **constraint_p
, int input_num
,
364 int ninputs
, int noutputs
, int ninout
,
365 const char * const * constraints
,
366 bool *allows_mem
, bool *allows_reg
)
368 const char *constraint
= *constraint_p
;
369 const char *orig_constraint
= constraint
;
370 size_t c_len
= strlen (constraint
);
372 bool saw_match
= false;
374 /* Assume the constraint doesn't allow the use of either
375 a register or memory. */
379 /* Make sure constraint has neither `=', `+', nor '&'. */
381 for (j
= 0; j
< c_len
; j
+= CONSTRAINT_LEN (constraint
[j
], constraint
+j
))
382 switch (constraint
[j
])
384 case '+': case '=': case '&':
385 if (constraint
== orig_constraint
)
387 error ("input operand constraint contains %qc", constraint
[j
]);
393 if (constraint
== orig_constraint
394 && input_num
+ 1 == ninputs
- ninout
)
396 error ("%<%%%> constraint used with last operand");
402 case '?': case '!': case '*': case '#':
404 case 'E': case 'F': case 'G': case 'H':
405 case 's': case 'i': case 'n':
406 case 'I': case 'J': case 'K': case 'L': case 'M':
407 case 'N': case 'O': case 'P': case ',':
410 /* Whether or not a numeric constraint allows a register is
411 decided by the matching constraint, and so there is no need
412 to do anything special with them. We must handle them in
413 the default case, so that we don't unnecessarily force
414 operands to memory. */
415 case '0': case '1': case '2': case '3': case '4':
416 case '5': case '6': case '7': case '8': case '9':
423 match
= strtoul (constraint
+ j
, &end
, 10);
424 if (match
>= (unsigned long) noutputs
)
426 error ("matching constraint references invalid operand number");
430 /* Try and find the real constraint for this dup. Only do this
431 if the matching constraint is the only alternative. */
433 && (j
== 0 || (j
== 1 && constraint
[0] == '%')))
435 constraint
= constraints
[match
];
436 *constraint_p
= constraint
;
437 c_len
= strlen (constraint
);
439 /* ??? At the end of the loop, we will skip the first part of
440 the matched constraint. This assumes not only that the
441 other constraint is an output constraint, but also that
442 the '=' or '+' come first. */
446 j
= end
- constraint
;
447 /* Anticipate increment at end of loop. */
458 if (! ISALPHA (constraint
[j
]))
460 error ("invalid punctuation %qc in constraint", constraint
[j
]);
463 enum constraint_num cn
= lookup_constraint (constraint
+ j
);
464 if (reg_class_for_constraint (cn
) != NO_REGS
465 || insn_extra_address_constraint (cn
))
467 else if (insn_extra_memory_constraint (cn
))
470 insn_extra_constraint_allows_reg_mem (cn
, allows_reg
, allows_mem
);
474 if (saw_match
&& !*allows_reg
)
475 warning (0, "matching constraint does not allow a register");
480 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
481 can be an asm-declared register. Called via walk_tree. */
484 decl_overlaps_hard_reg_set_p (tree
*declp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
488 const HARD_REG_SET
*const regs
= (const HARD_REG_SET
*) data
;
490 if (TREE_CODE (decl
) == VAR_DECL
)
492 if (DECL_HARD_REGISTER (decl
)
493 && REG_P (DECL_RTL (decl
))
494 && REGNO (DECL_RTL (decl
)) < FIRST_PSEUDO_REGISTER
)
496 rtx reg
= DECL_RTL (decl
);
498 if (overlaps_hard_reg_set_p (*regs
, GET_MODE (reg
), REGNO (reg
)))
503 else if (TYPE_P (decl
) || TREE_CODE (decl
) == PARM_DECL
)
508 /* If there is an overlap between *REGS and DECL, return the first overlap
511 tree_overlaps_hard_reg_set (tree decl
, HARD_REG_SET
*regs
)
513 return walk_tree (&decl
, decl_overlaps_hard_reg_set_p
, regs
, NULL
);
517 /* A subroutine of expand_asm_operands. Check that all operand names
518 are unique. Return true if so. We rely on the fact that these names
519 are identifiers, and so have been canonicalized by get_identifier,
520 so all we need are pointer comparisons. */
523 check_unique_operand_names (tree outputs
, tree inputs
, tree labels
)
525 tree i
, j
, i_name
= NULL_TREE
;
527 for (i
= outputs
; i
; i
= TREE_CHAIN (i
))
529 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
533 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
534 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
538 for (i
= inputs
; i
; i
= TREE_CHAIN (i
))
540 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
544 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
545 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
547 for (j
= outputs
; j
; j
= TREE_CHAIN (j
))
548 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
552 for (i
= labels
; i
; i
= TREE_CHAIN (i
))
554 i_name
= TREE_PURPOSE (i
);
558 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
559 if (simple_cst_equal (i_name
, TREE_PURPOSE (j
)))
561 for (j
= inputs
; j
; j
= TREE_CHAIN (j
))
562 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
569 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name
));
573 /* Resolve the names of the operands in *POUTPUTS and *PINPUTS to numbers,
574 and replace the name expansions in STRING and in the constraints to
575 those numbers. This is generally done in the front end while creating
576 the ASM_EXPR generic tree that eventually becomes the GIMPLE_ASM. */
579 resolve_asm_operand_names (tree string
, tree outputs
, tree inputs
, tree labels
)
586 check_unique_operand_names (outputs
, inputs
, labels
);
588 /* Substitute [<name>] in input constraint strings. There should be no
589 named operands in output constraints. */
590 for (t
= inputs
; t
; t
= TREE_CHAIN (t
))
592 c
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
593 if (strchr (c
, '[') != NULL
)
595 p
= buffer
= xstrdup (c
);
596 while ((p
= strchr (p
, '[')) != NULL
)
597 p
= resolve_operand_name_1 (p
, outputs
, inputs
, NULL
);
598 TREE_VALUE (TREE_PURPOSE (t
))
599 = build_string (strlen (buffer
), buffer
);
604 /* Now check for any needed substitutions in the template. */
605 c
= TREE_STRING_POINTER (string
);
606 while ((c
= strchr (c
, '%')) != NULL
)
610 else if (ISALPHA (c
[1]) && c
[2] == '[')
614 c
+= 1 + (c
[1] == '%');
621 /* OK, we need to make a copy so we can perform the substitutions.
622 Assume that we will not need extra space--we get to remove '['
623 and ']', which means we cannot have a problem until we have more
624 than 999 operands. */
625 buffer
= xstrdup (TREE_STRING_POINTER (string
));
626 p
= buffer
+ (c
- TREE_STRING_POINTER (string
));
628 while ((p
= strchr (p
, '%')) != NULL
)
632 else if (ISALPHA (p
[1]) && p
[2] == '[')
636 p
+= 1 + (p
[1] == '%');
640 p
= resolve_operand_name_1 (p
, outputs
, inputs
, labels
);
643 string
= build_string (strlen (buffer
), buffer
);
650 /* A subroutine of resolve_operand_names. P points to the '[' for a
651 potential named operand of the form [<name>]. In place, replace
652 the name and brackets with a number. Return a pointer to the
653 balance of the string after substitution. */
656 resolve_operand_name_1 (char *p
, tree outputs
, tree inputs
, tree labels
)
662 /* Collect the operand name. */
663 q
= strchr (++p
, ']');
666 error ("missing close brace for named operand");
667 return strchr (p
, '\0');
671 /* Resolve the name to a number. */
672 for (op
= 0, t
= outputs
; t
; t
= TREE_CHAIN (t
), op
++)
674 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
675 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
678 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), op
++)
680 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
681 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
684 for (t
= labels
; t
; t
= TREE_CHAIN (t
), op
++)
686 tree name
= TREE_PURPOSE (t
);
687 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
691 error ("undefined named operand %qs", identifier_to_locale (p
));
695 /* Replace the name with the number. Unfortunately, not all libraries
696 get the return value of sprintf correct, so search for the end of the
697 generated string by hand. */
698 sprintf (--p
, "%d", op
);
699 p
= strchr (p
, '\0');
701 /* Verify the no extra buffer space assumption. */
704 /* Shift the rest of the buffer down to fill the gap. */
705 memmove (p
, q
+ 1, strlen (q
+ 1) + 1);
711 /* Generate RTL to return directly from the current function.
712 (That is, we bypass any return value.) */
715 expand_naked_return (void)
717 rtx_code_label
*end_label
;
719 clear_pending_stack_adjust ();
720 do_pending_stack_adjust ();
722 end_label
= naked_return_label
;
724 end_label
= naked_return_label
= gen_label_rtx ();
726 emit_jump (end_label
);
729 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
730 is the probability of jumping to LABEL. */
732 do_jump_if_equal (machine_mode mode
, rtx op0
, rtx op1
, rtx_code_label
*label
,
733 int unsignedp
, int prob
)
735 gcc_assert (prob
<= REG_BR_PROB_BASE
);
736 do_compare_rtx_and_jump (op0
, op1
, EQ
, unsignedp
, mode
,
737 NULL_RTX
, NULL
, label
, prob
);
740 /* Do the insertion of a case label into case_list. The labels are
741 fed to us in descending order from the sorted vector of case labels used
742 in the tree part of the middle end. So the list we construct is
743 sorted in ascending order.
745 LABEL is the case label to be inserted. LOW and HIGH are the bounds
746 against which the index is compared to jump to LABEL and PROB is the
747 estimated probability LABEL is reached from the switch statement. */
749 static struct case_node
*
750 add_case_node (struct case_node
*head
, tree low
, tree high
,
751 tree label
, int prob
, alloc_pool case_node_pool
)
755 gcc_checking_assert (low
);
756 gcc_checking_assert (high
&& (TREE_TYPE (low
) == TREE_TYPE (high
)));
758 /* Add this label to the chain. */
759 r
= (struct case_node
*) pool_alloc (case_node_pool
);
762 r
->code_label
= label
;
763 r
->parent
= r
->left
= NULL
;
765 r
->subtree_prob
= prob
;
770 /* Dump ROOT, a list or tree of case nodes, to file. */
773 dump_case_nodes (FILE *f
, struct case_node
*root
,
774 int indent_step
, int indent_level
)
780 dump_case_nodes (f
, root
->left
, indent_step
, indent_level
);
783 fprintf (f
, "%*s", indent_step
* indent_level
, "");
784 print_dec (root
->low
, f
, TYPE_SIGN (TREE_TYPE (root
->low
)));
785 if (!tree_int_cst_equal (root
->low
, root
->high
))
787 fprintf (f
, " ... ");
788 print_dec (root
->high
, f
, TYPE_SIGN (TREE_TYPE (root
->high
)));
792 dump_case_nodes (f
, root
->right
, indent_step
, indent_level
);
796 #define HAVE_casesi 0
799 #ifndef HAVE_tablejump
800 #define HAVE_tablejump 0
803 /* Return the smallest number of different values for which it is best to use a
804 jump-table instead of a tree of conditional branches. */
807 case_values_threshold (void)
809 unsigned int threshold
= PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD
);
812 threshold
= targetm
.case_values_threshold ();
817 /* Return true if a switch should be expanded as a decision tree.
818 RANGE is the difference between highest and lowest case.
819 UNIQ is number of unique case node targets, not counting the default case.
820 COUNT is the number of comparisons needed, not counting the default case. */
823 expand_switch_as_decision_tree_p (tree range
,
824 unsigned int uniq ATTRIBUTE_UNUSED
,
829 /* If neither casesi or tablejump is available, or flag_jump_tables
830 over-ruled us, we really have no choice. */
831 if (!HAVE_casesi
&& !HAVE_tablejump
)
833 if (!flag_jump_tables
)
835 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
840 /* If the switch is relatively small such that the cost of one
841 indirect jump on the target are higher than the cost of a
842 decision tree, go with the decision tree.
844 If range of values is much bigger than number of values,
845 or if it is too large to represent in a HOST_WIDE_INT,
846 make a sequence of conditional branches instead of a dispatch.
848 The definition of "much bigger" depends on whether we are
849 optimizing for size or for speed. If the former, the maximum
850 ratio range/count = 3, because this was found to be the optimal
851 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
852 10 is much older, and was probably selected after an extensive
853 benchmarking investigation on numerous platforms. Or maybe it
854 just made sense to someone at some point in the history of GCC,
856 max_ratio
= optimize_insn_for_size_p () ? 3 : 10;
857 if (count
< case_values_threshold ()
858 || ! tree_fits_uhwi_p (range
)
859 || compare_tree_int (range
, max_ratio
* count
) > 0)
865 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
866 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
867 DEFAULT_PROB is the estimated probability that it jumps to
870 We generate a binary decision tree to select the appropriate target
871 code. This is done as follows:
873 If the index is a short or char that we do not have
874 an insn to handle comparisons directly, convert it to
875 a full integer now, rather than letting each comparison
876 generate the conversion.
878 Load the index into a register.
880 The list of cases is rearranged into a binary tree,
881 nearly optimal assuming equal probability for each case.
883 The tree is transformed into RTL, eliminating redundant
884 test conditions at the same time.
886 If program flow could reach the end of the decision tree
887 an unconditional jump to the default code is emitted.
889 The above process is unaware of the CFG. The caller has to fix up
890 the CFG itself. This is done in cfgexpand.c. */
893 emit_case_decision_tree (tree index_expr
, tree index_type
,
894 case_node_ptr case_list
, rtx_code_label
*default_label
,
897 rtx index
= expand_normal (index_expr
);
899 if (GET_MODE_CLASS (GET_MODE (index
)) == MODE_INT
900 && ! have_insn_for (COMPARE
, GET_MODE (index
)))
902 int unsignedp
= TYPE_UNSIGNED (index_type
);
903 machine_mode wider_mode
;
904 for (wider_mode
= GET_MODE (index
); wider_mode
!= VOIDmode
;
905 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
906 if (have_insn_for (COMPARE
, wider_mode
))
908 index
= convert_to_mode (wider_mode
, index
, unsignedp
);
913 do_pending_stack_adjust ();
917 index
= copy_to_reg (index
);
918 if (TREE_CODE (index_expr
) == SSA_NAME
)
919 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr
), index
);
922 balance_case_nodes (&case_list
, NULL
);
924 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
926 int indent_step
= ceil_log2 (TYPE_PRECISION (index_type
)) + 2;
927 fprintf (dump_file
, ";; Expanding GIMPLE switch as decision tree:\n");
928 dump_case_nodes (dump_file
, case_list
, indent_step
, 0);
931 emit_case_nodes (index
, case_list
, default_label
, default_prob
, index_type
);
933 emit_jump (default_label
);
936 /* Return the sum of probabilities of outgoing edges of basic block BB. */
939 get_outgoing_edge_probs (basic_block bb
)
946 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
947 prob_sum
+= e
->probability
;
951 /* Computes the conditional probability of jumping to a target if the branch
952 instruction is executed.
953 TARGET_PROB is the estimated probability of jumping to a target relative
954 to some basic block BB.
955 BASE_PROB is the probability of reaching the branch instruction relative
956 to the same basic block BB. */
959 conditional_probability (int target_prob
, int base_prob
)
963 gcc_assert (target_prob
>= 0);
964 gcc_assert (target_prob
<= base_prob
);
965 return GCOV_COMPUTE_SCALE (target_prob
, base_prob
);
970 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
971 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
972 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
973 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
975 First, a jump insn is emitted. First we try "casesi". If that
976 fails, try "tablejump". A target *must* have one of them (or both).
978 Then, a table with the target labels is emitted.
980 The process is unaware of the CFG. The caller has to fix up
981 the CFG itself. This is done in cfgexpand.c. */
984 emit_case_dispatch_table (tree index_expr
, tree index_type
,
985 struct case_node
*case_list
, rtx default_label
,
986 tree minval
, tree maxval
, tree range
,
992 rtx fallback_label
= label_rtx (case_list
->code_label
);
993 rtx_code_label
*table_label
= gen_label_rtx ();
994 bool has_gaps
= false;
995 edge default_edge
= stmt_bb
? EDGE_SUCC (stmt_bb
, 0) : NULL
;
996 int default_prob
= default_edge
? default_edge
->probability
: 0;
997 int base
= get_outgoing_edge_probs (stmt_bb
);
998 bool try_with_tablejump
= false;
1000 int new_default_prob
= conditional_probability (default_prob
,
1003 if (! try_casesi (index_type
, index_expr
, minval
, range
,
1004 table_label
, default_label
, fallback_label
,
1007 /* Index jumptables from zero for suitable values of minval to avoid
1008 a subtraction. For the rationale see:
1009 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
1010 if (optimize_insn_for_speed_p ()
1011 && compare_tree_int (minval
, 0) > 0
1012 && compare_tree_int (minval
, 3) < 0)
1014 minval
= build_int_cst (index_type
, 0);
1018 try_with_tablejump
= true;
1021 /* Get table of labels to jump to, in order of case index. */
1023 ncases
= tree_to_shwi (range
) + 1;
1024 labelvec
= XALLOCAVEC (rtx
, ncases
);
1025 memset (labelvec
, 0, ncases
* sizeof (rtx
));
1027 for (n
= case_list
; n
; n
= n
->right
)
1029 /* Compute the low and high bounds relative to the minimum
1030 value since that should fit in a HOST_WIDE_INT while the
1031 actual values may not. */
1033 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1035 HOST_WIDE_INT i_high
1036 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1040 for (i
= i_low
; i
<= i_high
; i
++)
1042 = gen_rtx_LABEL_REF (Pmode
, label_rtx (n
->code_label
));
1045 /* Fill in the gaps with the default. We may have gaps at
1046 the beginning if we tried to avoid the minval subtraction,
1047 so substitute some label even if the default label was
1048 deemed unreachable. */
1050 default_label
= fallback_label
;
1051 for (i
= 0; i
< ncases
; i
++)
1052 if (labelvec
[i
] == 0)
1055 labelvec
[i
] = gen_rtx_LABEL_REF (Pmode
, default_label
);
1060 /* There is at least one entry in the jump table that jumps
1061 to default label. The default label can either be reached
1062 through the indirect jump or the direct conditional jump
1063 before that. Split the probability of reaching the
1064 default label among these two jumps. */
1065 new_default_prob
= conditional_probability (default_prob
/2,
1068 base
-= default_prob
;
1072 base
-= default_prob
;
1077 default_edge
->probability
= default_prob
;
1079 /* We have altered the probability of the default edge. So the probabilities
1080 of all other edges need to be adjusted so that it sums up to
1081 REG_BR_PROB_BASE. */
1086 FOR_EACH_EDGE (e
, ei
, stmt_bb
->succs
)
1087 e
->probability
= GCOV_COMPUTE_SCALE (e
->probability
, base
);
1090 if (try_with_tablejump
)
1092 bool ok
= try_tablejump (index_type
, index_expr
, minval
, range
,
1093 table_label
, default_label
, new_default_prob
);
1096 /* Output the table. */
1097 emit_label (table_label
);
1099 if (CASE_VECTOR_PC_RELATIVE
|| flag_pic
)
1100 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE
,
1101 gen_rtx_LABEL_REF (Pmode
,
1103 gen_rtvec_v (ncases
, labelvec
),
1104 const0_rtx
, const0_rtx
));
1106 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE
,
1107 gen_rtvec_v (ncases
, labelvec
)));
1109 /* Record no drop-through after the table. */
1113 /* Reset the aux field of all outgoing edges of basic block BB. */
1116 reset_out_edges_aux (basic_block bb
)
1120 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1124 /* Compute the number of case labels that correspond to each outgoing edge of
1125 STMT. Record this information in the aux field of the edge. */
1128 compute_cases_per_edge (gswitch
*stmt
)
1130 basic_block bb
= gimple_bb (stmt
);
1131 reset_out_edges_aux (bb
);
1132 int ncases
= gimple_switch_num_labels (stmt
);
1133 for (int i
= ncases
- 1; i
>= 1; --i
)
1135 tree elt
= gimple_switch_label (stmt
, i
);
1136 tree lab
= CASE_LABEL (elt
);
1137 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1138 edge case_edge
= find_edge (bb
, case_bb
);
1139 case_edge
->aux
= (void *)((intptr_t)(case_edge
->aux
) + 1);
1143 /* Terminate a case (Pascal/Ada) or switch (C) statement
1144 in which ORIG_INDEX is the expression to be tested.
1145 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
1146 type as given in the source before any compiler conversions.
1147 Generate the code to test it and jump to the right place. */
1150 expand_case (gswitch
*stmt
)
1152 tree minval
= NULL_TREE
, maxval
= NULL_TREE
, range
= NULL_TREE
;
1153 rtx_code_label
*default_label
= NULL
;
1154 unsigned int count
, uniq
;
1156 int ncases
= gimple_switch_num_labels (stmt
);
1157 tree index_expr
= gimple_switch_index (stmt
);
1158 tree index_type
= TREE_TYPE (index_expr
);
1160 basic_block bb
= gimple_bb (stmt
);
1162 /* A list of case labels; it is first built as a list and it may then
1163 be rearranged into a nearly balanced binary tree. */
1164 struct case_node
*case_list
= 0;
1166 /* A pool for case nodes. */
1167 alloc_pool case_node_pool
;
1169 /* An ERROR_MARK occurs for various reasons including invalid data type.
1170 ??? Can this still happen, with GIMPLE and all? */
1171 if (index_type
== error_mark_node
)
1174 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
1175 expressions being INTEGER_CST. */
1176 gcc_assert (TREE_CODE (index_expr
) != INTEGER_CST
);
1178 case_node_pool
= create_alloc_pool ("struct case_node pool",
1179 sizeof (struct case_node
),
1182 do_pending_stack_adjust ();
1184 /* Find the default case target label. */
1185 default_label
= jump_target_rtx
1186 (CASE_LABEL (gimple_switch_default_label (stmt
)));
1187 edge default_edge
= EDGE_SUCC (bb
, 0);
1188 int default_prob
= default_edge
->probability
;
1190 /* Get upper and lower bounds of case values. */
1191 elt
= gimple_switch_label (stmt
, 1);
1192 minval
= fold_convert (index_type
, CASE_LOW (elt
));
1193 elt
= gimple_switch_label (stmt
, ncases
- 1);
1194 if (CASE_HIGH (elt
))
1195 maxval
= fold_convert (index_type
, CASE_HIGH (elt
));
1197 maxval
= fold_convert (index_type
, CASE_LOW (elt
));
1199 /* Compute span of values. */
1200 range
= fold_build2 (MINUS_EXPR
, index_type
, maxval
, minval
);
1202 /* Listify the labels queue and gather some numbers to decide
1203 how to expand this switch(). */
1206 hash_set
<tree
> seen_labels
;
1207 compute_cases_per_edge (stmt
);
1209 for (i
= ncases
- 1; i
>= 1; --i
)
1211 elt
= gimple_switch_label (stmt
, i
);
1212 tree low
= CASE_LOW (elt
);
1214 tree high
= CASE_HIGH (elt
);
1215 gcc_assert (! high
|| tree_int_cst_lt (low
, high
));
1216 tree lab
= CASE_LABEL (elt
);
1218 /* Count the elements.
1219 A range counts double, since it requires two compares. */
1224 /* If we have not seen this label yet, then increase the
1225 number of unique case node targets seen. */
1226 if (!seen_labels
.add (lab
))
1229 /* The bounds on the case range, LOW and HIGH, have to be converted
1230 to case's index type TYPE. Note that the original type of the
1231 case index in the source code is usually "lost" during
1232 gimplification due to type promotion, but the case labels retain the
1233 original type. Make sure to drop overflow flags. */
1234 low
= fold_convert (index_type
, low
);
1235 if (TREE_OVERFLOW (low
))
1236 low
= wide_int_to_tree (index_type
, low
);
1238 /* The canonical from of a case label in GIMPLE is that a simple case
1239 has an empty CASE_HIGH. For the casesi and tablejump expanders,
1240 the back ends want simple cases to have high == low. */
1243 high
= fold_convert (index_type
, high
);
1244 if (TREE_OVERFLOW (high
))
1245 high
= wide_int_to_tree (index_type
, high
);
1247 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1248 edge case_edge
= find_edge (bb
, case_bb
);
1249 case_list
= add_case_node (
1250 case_list
, low
, high
, lab
,
1251 case_edge
->probability
/ (intptr_t)(case_edge
->aux
),
1254 reset_out_edges_aux (bb
);
1256 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
1257 destination, such as one with a default case only.
1258 It also removes cases that are out of range for the switch
1259 type, so we should never get a zero here. */
1260 gcc_assert (count
> 0);
1262 rtx_insn
*before_case
= get_last_insn ();
1264 /* Decide how to expand this switch.
1265 The two options at this point are a dispatch table (casesi or
1266 tablejump) or a decision tree. */
1268 if (expand_switch_as_decision_tree_p (range
, uniq
, count
))
1269 emit_case_decision_tree (index_expr
, index_type
,
1270 case_list
, default_label
,
1273 emit_case_dispatch_table (index_expr
, index_type
,
1274 case_list
, default_label
,
1275 minval
, maxval
, range
, bb
);
1277 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1280 free_alloc_pool (case_node_pool
);
1283 /* Expand the dispatch to a short decrement chain if there are few cases
1284 to dispatch to. Likewise if neither casesi nor tablejump is available,
1285 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
1286 tablejump. The index mode is always the mode of integer_type_node.
1287 Trap if no case matches the index.
1289 DISPATCH_INDEX is the index expression to switch on. It should be a
1290 memory or register operand.
1292 DISPATCH_TABLE is a set of case labels. The set should be sorted in
1293 ascending order, be contiguous, starting with value 0, and contain only
1294 single-valued case labels. */
1297 expand_sjlj_dispatch_table (rtx dispatch_index
,
1298 vec
<tree
> dispatch_table
)
1300 tree index_type
= integer_type_node
;
1301 machine_mode index_mode
= TYPE_MODE (index_type
);
1303 int ncases
= dispatch_table
.length ();
1305 do_pending_stack_adjust ();
1306 rtx_insn
*before_case
= get_last_insn ();
1308 /* Expand as a decrement-chain if there are 5 or fewer dispatch
1309 labels. This covers more than 98% of the cases in libjava,
1310 and seems to be a reasonable compromise between the "old way"
1311 of expanding as a decision tree or dispatch table vs. the "new
1312 way" with decrement chain or dispatch table. */
1313 if (dispatch_table
.length () <= 5
1314 || (!HAVE_casesi
&& !HAVE_tablejump
)
1315 || !flag_jump_tables
)
1317 /* Expand the dispatch as a decrement chain:
1319 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1323 if (index == 0) do_0; else index--;
1324 if (index == 0) do_1; else index--;
1326 if (index == 0) do_N; else index--;
1328 This is more efficient than a dispatch table on most machines.
1329 The last "index--" is redundant but the code is trivially dead
1330 and will be cleaned up by later passes. */
1331 rtx index
= copy_to_mode_reg (index_mode
, dispatch_index
);
1332 rtx zero
= CONST0_RTX (index_mode
);
1333 for (int i
= 0; i
< ncases
; i
++)
1335 tree elt
= dispatch_table
[i
];
1336 rtx_code_label
*lab
= jump_target_rtx (CASE_LABEL (elt
));
1337 do_jump_if_equal (index_mode
, index
, zero
, lab
, 0, -1);
1338 force_expand_binop (index_mode
, sub_optab
,
1339 index
, CONST1_RTX (index_mode
),
1340 index
, 0, OPTAB_DIRECT
);
1345 /* Similar to expand_case, but much simpler. */
1346 struct case_node
*case_list
= 0;
1347 alloc_pool case_node_pool
= create_alloc_pool ("struct sjlj_case pool",
1348 sizeof (struct case_node
),
1350 tree index_expr
= make_tree (index_type
, dispatch_index
);
1351 tree minval
= build_int_cst (index_type
, 0);
1352 tree maxval
= CASE_LOW (dispatch_table
.last ());
1353 tree range
= maxval
;
1354 rtx_code_label
*default_label
= gen_label_rtx ();
1356 for (int i
= ncases
- 1; i
>= 0; --i
)
1358 tree elt
= dispatch_table
[i
];
1359 tree low
= CASE_LOW (elt
);
1360 tree lab
= CASE_LABEL (elt
);
1361 case_list
= add_case_node (case_list
, low
, low
, lab
, 0, case_node_pool
);
1364 emit_case_dispatch_table (index_expr
, index_type
,
1365 case_list
, default_label
,
1366 minval
, maxval
, range
,
1367 BLOCK_FOR_INSN (before_case
));
1368 emit_label (default_label
);
1369 free_alloc_pool (case_node_pool
);
1372 /* Dispatching something not handled? Trap! */
1373 expand_builtin_trap ();
1375 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1381 /* Take an ordered list of case nodes
1382 and transform them into a near optimal binary tree,
1383 on the assumption that any target code selection value is as
1384 likely as any other.
1386 The transformation is performed by splitting the ordered
1387 list into two equal sections plus a pivot. The parts are
1388 then attached to the pivot as left and right branches. Each
1389 branch is then transformed recursively. */
1392 balance_case_nodes (case_node_ptr
*head
, case_node_ptr parent
)
1404 /* Count the number of entries on branch. Also count the ranges. */
1408 if (!tree_int_cst_equal (np
->low
, np
->high
))
1417 /* Split this list if it is long enough for that to help. */
1421 /* If there are just three nodes, split at the middle one. */
1423 npp
= &(*npp
)->right
;
1426 /* Find the place in the list that bisects the list's total cost,
1427 where ranges count as 2.
1428 Here I gets half the total cost. */
1429 i
= (i
+ ranges
+ 1) / 2;
1432 /* Skip nodes while their cost does not reach that amount. */
1433 if (!tree_int_cst_equal ((*npp
)->low
, (*npp
)->high
))
1438 npp
= &(*npp
)->right
;
1443 np
->parent
= parent
;
1446 /* Optimize each of the two split parts. */
1447 balance_case_nodes (&np
->left
, np
);
1448 balance_case_nodes (&np
->right
, np
);
1449 np
->subtree_prob
= np
->prob
;
1450 np
->subtree_prob
+= np
->left
->subtree_prob
;
1451 np
->subtree_prob
+= np
->right
->subtree_prob
;
1455 /* Else leave this branch as one level,
1456 but fill in `parent' fields. */
1458 np
->parent
= parent
;
1459 np
->subtree_prob
= np
->prob
;
1460 for (; np
->right
; np
= np
->right
)
1462 np
->right
->parent
= np
;
1463 (*head
)->subtree_prob
+= np
->right
->subtree_prob
;
1469 /* Search the parent sections of the case node tree
1470 to see if a test for the lower bound of NODE would be redundant.
1471 INDEX_TYPE is the type of the index expression.
1473 The instructions to generate the case decision tree are
1474 output in the same order as nodes are processed so it is
1475 known that if a parent node checks the range of the current
1476 node minus one that the current node is bounded at its lower
1477 span. Thus the test would be redundant. */
1480 node_has_low_bound (case_node_ptr node
, tree index_type
)
1483 case_node_ptr pnode
;
1485 /* If the lower bound of this node is the lowest value in the index type,
1486 we need not test it. */
1488 if (tree_int_cst_equal (node
->low
, TYPE_MIN_VALUE (index_type
)))
1491 /* If this node has a left branch, the value at the left must be less
1492 than that at this node, so it cannot be bounded at the bottom and
1493 we need not bother testing any further. */
1498 low_minus_one
= fold_build2 (MINUS_EXPR
, TREE_TYPE (node
->low
),
1500 build_int_cst (TREE_TYPE (node
->low
), 1));
1502 /* If the subtraction above overflowed, we can't verify anything.
1503 Otherwise, look for a parent that tests our value - 1. */
1505 if (! tree_int_cst_lt (low_minus_one
, node
->low
))
1508 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1509 if (tree_int_cst_equal (low_minus_one
, pnode
->high
))
1515 /* Search the parent sections of the case node tree
1516 to see if a test for the upper bound of NODE would be redundant.
1517 INDEX_TYPE is the type of the index expression.
1519 The instructions to generate the case decision tree are
1520 output in the same order as nodes are processed so it is
1521 known that if a parent node checks the range of the current
1522 node plus one that the current node is bounded at its upper
1523 span. Thus the test would be redundant. */
1526 node_has_high_bound (case_node_ptr node
, tree index_type
)
1529 case_node_ptr pnode
;
1531 /* If there is no upper bound, obviously no test is needed. */
1533 if (TYPE_MAX_VALUE (index_type
) == NULL
)
1536 /* If the upper bound of this node is the highest value in the type
1537 of the index expression, we need not test against it. */
1539 if (tree_int_cst_equal (node
->high
, TYPE_MAX_VALUE (index_type
)))
1542 /* If this node has a right branch, the value at the right must be greater
1543 than that at this node, so it cannot be bounded at the top and
1544 we need not bother testing any further. */
1549 high_plus_one
= fold_build2 (PLUS_EXPR
, TREE_TYPE (node
->high
),
1551 build_int_cst (TREE_TYPE (node
->high
), 1));
1553 /* If the addition above overflowed, we can't verify anything.
1554 Otherwise, look for a parent that tests our value + 1. */
1556 if (! tree_int_cst_lt (node
->high
, high_plus_one
))
1559 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1560 if (tree_int_cst_equal (high_plus_one
, pnode
->low
))
1566 /* Search the parent sections of the
1567 case node tree to see if both tests for the upper and lower
1568 bounds of NODE would be redundant. */
1571 node_is_bounded (case_node_ptr node
, tree index_type
)
1573 return (node_has_low_bound (node
, index_type
)
1574 && node_has_high_bound (node
, index_type
));
1578 /* Emit step-by-step code to select a case for the value of INDEX.
1579 The thus generated decision tree follows the form of the
1580 case-node binary tree NODE, whose nodes represent test conditions.
1581 INDEX_TYPE is the type of the index of the switch.
1583 Care is taken to prune redundant tests from the decision tree
1584 by detecting any boundary conditions already checked by
1585 emitted rtx. (See node_has_high_bound, node_has_low_bound
1586 and node_is_bounded, above.)
1588 Where the test conditions can be shown to be redundant we emit
1589 an unconditional jump to the target code. As a further
1590 optimization, the subordinates of a tree node are examined to
1591 check for bounded nodes. In this case conditional and/or
1592 unconditional jumps as a result of the boundary check for the
1593 current node are arranged to target the subordinates associated
1594 code for out of bound conditions on the current node.
1596 We can assume that when control reaches the code generated here,
1597 the index value has already been compared with the parents
1598 of this node, and determined to be on the same side of each parent
1599 as this node is. Thus, if this node tests for the value 51,
1600 and a parent tested for 52, we don't need to consider
1601 the possibility of a value greater than 51. If another parent
1602 tests for the value 50, then this node need not test anything. */
1605 emit_case_nodes (rtx index
, case_node_ptr node
, rtx_code_label
*default_label
,
1606 int default_prob
, tree index_type
)
1608 /* If INDEX has an unsigned type, we must make unsigned branches. */
1609 int unsignedp
= TYPE_UNSIGNED (index_type
);
1611 int prob
= node
->prob
, subtree_prob
= node
->subtree_prob
;
1612 machine_mode mode
= GET_MODE (index
);
1613 machine_mode imode
= TYPE_MODE (index_type
);
1615 /* Handle indices detected as constant during RTL expansion. */
1616 if (mode
== VOIDmode
)
1619 /* See if our parents have already tested everything for us.
1620 If they have, emit an unconditional jump for this node. */
1621 if (node_is_bounded (node
, index_type
))
1622 emit_jump (label_rtx (node
->code_label
));
1624 else if (tree_int_cst_equal (node
->low
, node
->high
))
1626 probability
= conditional_probability (prob
, subtree_prob
+ default_prob
);
1627 /* Node is single valued. First see if the index expression matches
1628 this node and then check our children, if any. */
1629 do_jump_if_equal (mode
, index
,
1630 convert_modes (mode
, imode
,
1631 expand_normal (node
->low
),
1633 jump_target_rtx (node
->code_label
),
1634 unsignedp
, probability
);
1635 /* Since this case is taken at this point, reduce its weight from
1637 subtree_prob
-= prob
;
1638 if (node
->right
!= 0 && node
->left
!= 0)
1640 /* This node has children on both sides.
1641 Dispatch to one side or the other
1642 by comparing the index value with this node's value.
1643 If one subtree is bounded, check that one first,
1644 so we can avoid real branches in the tree. */
1646 if (node_is_bounded (node
->right
, index_type
))
1648 probability
= conditional_probability (
1650 subtree_prob
+ default_prob
);
1651 emit_cmp_and_jump_insns (index
,
1654 expand_normal (node
->high
),
1656 GT
, NULL_RTX
, mode
, unsignedp
,
1657 label_rtx (node
->right
->code_label
),
1659 emit_case_nodes (index
, node
->left
, default_label
, default_prob
,
1663 else if (node_is_bounded (node
->left
, index_type
))
1665 probability
= conditional_probability (
1667 subtree_prob
+ default_prob
);
1668 emit_cmp_and_jump_insns (index
,
1671 expand_normal (node
->high
),
1673 LT
, NULL_RTX
, mode
, unsignedp
,
1674 label_rtx (node
->left
->code_label
),
1676 emit_case_nodes (index
, node
->right
, default_label
, default_prob
,
1680 /* If both children are single-valued cases with no
1681 children, finish up all the work. This way, we can save
1682 one ordered comparison. */
1683 else if (tree_int_cst_equal (node
->right
->low
, node
->right
->high
)
1684 && node
->right
->left
== 0
1685 && node
->right
->right
== 0
1686 && tree_int_cst_equal (node
->left
->low
, node
->left
->high
)
1687 && node
->left
->left
== 0
1688 && node
->left
->right
== 0)
1690 /* Neither node is bounded. First distinguish the two sides;
1691 then emit the code for one side at a time. */
1693 /* See if the value matches what the right hand side
1695 probability
= conditional_probability (
1697 subtree_prob
+ default_prob
);
1698 do_jump_if_equal (mode
, index
,
1699 convert_modes (mode
, imode
,
1700 expand_normal (node
->right
->low
),
1702 jump_target_rtx (node
->right
->code_label
),
1703 unsignedp
, probability
);
1705 /* See if the value matches what the left hand side
1707 probability
= conditional_probability (
1709 subtree_prob
+ default_prob
);
1710 do_jump_if_equal (mode
, index
,
1711 convert_modes (mode
, imode
,
1712 expand_normal (node
->left
->low
),
1714 jump_target_rtx (node
->left
->code_label
),
1715 unsignedp
, probability
);
1720 /* Neither node is bounded. First distinguish the two sides;
1721 then emit the code for one side at a time. */
1724 = build_decl (curr_insn_location (),
1725 LABEL_DECL
, NULL_TREE
, void_type_node
);
1727 /* The default label could be reached either through the right
1728 subtree or the left subtree. Divide the probability
1730 probability
= conditional_probability (
1731 node
->right
->subtree_prob
+ default_prob
/2,
1732 subtree_prob
+ default_prob
);
1733 /* See if the value is on the right. */
1734 emit_cmp_and_jump_insns (index
,
1737 expand_normal (node
->high
),
1739 GT
, NULL_RTX
, mode
, unsignedp
,
1740 label_rtx (test_label
),
1744 /* Value must be on the left.
1745 Handle the left-hand subtree. */
1746 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1747 /* If left-hand subtree does nothing,
1750 emit_jump (default_label
);
1752 /* Code branches here for the right-hand subtree. */
1753 expand_label (test_label
);
1754 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1758 else if (node
->right
!= 0 && node
->left
== 0)
1760 /* Here we have a right child but no left so we issue a conditional
1761 branch to default and process the right child.
1763 Omit the conditional branch to default if the right child
1764 does not have any children and is single valued; it would
1765 cost too much space to save so little time. */
1767 if (node
->right
->right
|| node
->right
->left
1768 || !tree_int_cst_equal (node
->right
->low
, node
->right
->high
))
1770 if (!node_has_low_bound (node
, index_type
))
1772 probability
= conditional_probability (
1774 subtree_prob
+ default_prob
);
1775 emit_cmp_and_jump_insns (index
,
1778 expand_normal (node
->high
),
1780 LT
, NULL_RTX
, mode
, unsignedp
,
1786 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1790 probability
= conditional_probability (
1791 node
->right
->subtree_prob
,
1792 subtree_prob
+ default_prob
);
1793 /* We cannot process node->right normally
1794 since we haven't ruled out the numbers less than
1795 this node's value. So handle node->right explicitly. */
1796 do_jump_if_equal (mode
, index
,
1799 expand_normal (node
->right
->low
),
1801 jump_target_rtx (node
->right
->code_label
),
1802 unsignedp
, probability
);
1806 else if (node
->right
== 0 && node
->left
!= 0)
1808 /* Just one subtree, on the left. */
1809 if (node
->left
->left
|| node
->left
->right
1810 || !tree_int_cst_equal (node
->left
->low
, node
->left
->high
))
1812 if (!node_has_high_bound (node
, index_type
))
1814 probability
= conditional_probability (
1816 subtree_prob
+ default_prob
);
1817 emit_cmp_and_jump_insns (index
,
1820 expand_normal (node
->high
),
1822 GT
, NULL_RTX
, mode
, unsignedp
,
1828 emit_case_nodes (index
, node
->left
, default_label
,
1829 default_prob
, index_type
);
1833 probability
= conditional_probability (
1834 node
->left
->subtree_prob
,
1835 subtree_prob
+ default_prob
);
1836 /* We cannot process node->left normally
1837 since we haven't ruled out the numbers less than
1838 this node's value. So handle node->left explicitly. */
1839 do_jump_if_equal (mode
, index
,
1842 expand_normal (node
->left
->low
),
1844 jump_target_rtx (node
->left
->code_label
),
1845 unsignedp
, probability
);
1851 /* Node is a range. These cases are very similar to those for a single
1852 value, except that we do not start by testing whether this node
1853 is the one to branch to. */
1855 if (node
->right
!= 0 && node
->left
!= 0)
1857 /* Node has subtrees on both sides.
1858 If the right-hand subtree is bounded,
1859 test for it first, since we can go straight there.
1860 Otherwise, we need to make a branch in the control structure,
1861 then handle the two subtrees. */
1862 tree test_label
= 0;
1864 if (node_is_bounded (node
->right
, index_type
))
1866 /* Right hand node is fully bounded so we can eliminate any
1867 testing and branch directly to the target code. */
1868 probability
= conditional_probability (
1869 node
->right
->subtree_prob
,
1870 subtree_prob
+ default_prob
);
1871 emit_cmp_and_jump_insns (index
,
1874 expand_normal (node
->high
),
1876 GT
, NULL_RTX
, mode
, unsignedp
,
1877 label_rtx (node
->right
->code_label
),
1882 /* Right hand node requires testing.
1883 Branch to a label where we will handle it later. */
1885 test_label
= build_decl (curr_insn_location (),
1886 LABEL_DECL
, NULL_TREE
, void_type_node
);
1887 probability
= conditional_probability (
1888 node
->right
->subtree_prob
+ default_prob
/2,
1889 subtree_prob
+ default_prob
);
1890 emit_cmp_and_jump_insns (index
,
1893 expand_normal (node
->high
),
1895 GT
, NULL_RTX
, mode
, unsignedp
,
1896 label_rtx (test_label
),
1901 /* Value belongs to this node or to the left-hand subtree. */
1903 probability
= conditional_probability (
1905 subtree_prob
+ default_prob
);
1906 emit_cmp_and_jump_insns (index
,
1909 expand_normal (node
->low
),
1911 GE
, NULL_RTX
, mode
, unsignedp
,
1912 label_rtx (node
->code_label
),
1915 /* Handle the left-hand subtree. */
1916 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1918 /* If right node had to be handled later, do that now. */
1922 /* If the left-hand subtree fell through,
1923 don't let it fall into the right-hand subtree. */
1925 emit_jump (default_label
);
1927 expand_label (test_label
);
1928 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1932 else if (node
->right
!= 0 && node
->left
== 0)
1934 /* Deal with values to the left of this node,
1935 if they are possible. */
1936 if (!node_has_low_bound (node
, index_type
))
1938 probability
= conditional_probability (
1940 subtree_prob
+ default_prob
);
1941 emit_cmp_and_jump_insns (index
,
1944 expand_normal (node
->low
),
1946 LT
, NULL_RTX
, mode
, unsignedp
,
1952 /* Value belongs to this node or to the right-hand subtree. */
1954 probability
= conditional_probability (
1956 subtree_prob
+ default_prob
);
1957 emit_cmp_and_jump_insns (index
,
1960 expand_normal (node
->high
),
1962 LE
, NULL_RTX
, mode
, unsignedp
,
1963 label_rtx (node
->code_label
),
1966 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1969 else if (node
->right
== 0 && node
->left
!= 0)
1971 /* Deal with values to the right of this node,
1972 if they are possible. */
1973 if (!node_has_high_bound (node
, index_type
))
1975 probability
= conditional_probability (
1977 subtree_prob
+ default_prob
);
1978 emit_cmp_and_jump_insns (index
,
1981 expand_normal (node
->high
),
1983 GT
, NULL_RTX
, mode
, unsignedp
,
1989 /* Value belongs to this node or to the left-hand subtree. */
1991 probability
= conditional_probability (
1993 subtree_prob
+ default_prob
);
1994 emit_cmp_and_jump_insns (index
,
1997 expand_normal (node
->low
),
1999 GE
, NULL_RTX
, mode
, unsignedp
,
2000 label_rtx (node
->code_label
),
2003 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
2008 /* Node has no children so we check low and high bounds to remove
2009 redundant tests. Only one of the bounds can exist,
2010 since otherwise this node is bounded--a case tested already. */
2011 int high_bound
= node_has_high_bound (node
, index_type
);
2012 int low_bound
= node_has_low_bound (node
, index_type
);
2014 if (!high_bound
&& low_bound
)
2016 probability
= conditional_probability (
2018 subtree_prob
+ default_prob
);
2019 emit_cmp_and_jump_insns (index
,
2022 expand_normal (node
->high
),
2024 GT
, NULL_RTX
, mode
, unsignedp
,
2029 else if (!low_bound
&& high_bound
)
2031 probability
= conditional_probability (
2033 subtree_prob
+ default_prob
);
2034 emit_cmp_and_jump_insns (index
,
2037 expand_normal (node
->low
),
2039 LT
, NULL_RTX
, mode
, unsignedp
,
2043 else if (!low_bound
&& !high_bound
)
2045 /* Widen LOW and HIGH to the same width as INDEX. */
2046 tree type
= lang_hooks
.types
.type_for_mode (mode
, unsignedp
);
2047 tree low
= build1 (CONVERT_EXPR
, type
, node
->low
);
2048 tree high
= build1 (CONVERT_EXPR
, type
, node
->high
);
2049 rtx low_rtx
, new_index
, new_bound
;
2051 /* Instead of doing two branches, emit one unsigned branch for
2052 (index-low) > (high-low). */
2053 low_rtx
= expand_expr (low
, NULL_RTX
, mode
, EXPAND_NORMAL
);
2054 new_index
= expand_simple_binop (mode
, MINUS
, index
, low_rtx
,
2055 NULL_RTX
, unsignedp
,
2057 new_bound
= expand_expr (fold_build2 (MINUS_EXPR
, type
,
2059 NULL_RTX
, mode
, EXPAND_NORMAL
);
2061 probability
= conditional_probability (
2063 subtree_prob
+ default_prob
);
2064 emit_cmp_and_jump_insns (new_index
, new_bound
, GT
, NULL_RTX
,
2065 mode
, 1, default_label
, probability
);
2068 emit_jump (jump_target_rtx (node
->code_label
));