1 /* Expands front end tree to back end RTL for GCC
2 Copyright (C) 1987-2017 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"
35 #include "alloc-pool.h"
41 #include "pretty-print.h"
42 #include "diagnostic-core.h"
44 #include "fold-const.h"
46 #include "stor-layout.h"
51 #include "langhooks.h"
59 /* Functions and data structures for expanding case statements. */
61 /* Case label structure, used to hold info on labels within case
62 statements. We handle "range" labels; for a single-value label
63 as in C, the high and low limits are the same.
65 We start with a vector of case nodes sorted in ascending order, and
66 the default label as the last element in the vector. Before expanding
67 to RTL, we transform this vector into a list linked via the RIGHT
68 fields in the case_node struct. Nodes with higher case values are
71 Switch statements can be output in three forms. A branch table is
72 used if there are more than a few labels and the labels are dense
73 within the range between the smallest and largest case value. If a
74 branch table is used, no further manipulations are done with the case
77 The alternative to the use of a branch table is to generate a series
78 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
79 and PARENT fields to hold a binary tree. Initially the tree is
80 totally unbalanced, with everything on the right. We balance the tree
81 with nodes on the left having lower case values than the parent
82 and nodes on the right having higher values. We then output the tree
85 For very small, suitable switch statements, we can generate a series
86 of simple bit test and branches instead. */
90 struct case_node
*left
; /* Left son in binary tree */
91 struct case_node
*right
; /* Right son in binary tree; also node chain */
92 struct case_node
*parent
; /* Parent of node in binary tree */
93 tree low
; /* Lowest index value for this label */
94 tree high
; /* Highest index value for this label */
95 tree code_label
; /* Label to jump to when node matches */
96 int prob
; /* Probability of taking this case. */
97 /* Probability of reaching subtree rooted at this node */
101 typedef struct case_node
*case_node_ptr
;
103 extern basic_block
label_to_block_fn (struct function
*, tree
);
105 static bool check_unique_operand_names (tree
, tree
, tree
);
106 static char *resolve_operand_name_1 (char *, tree
, tree
, tree
);
107 static void balance_case_nodes (case_node_ptr
*, case_node_ptr
);
108 static int node_has_low_bound (case_node_ptr
, tree
);
109 static int node_has_high_bound (case_node_ptr
, tree
);
110 static int node_is_bounded (case_node_ptr
, tree
);
111 static void emit_case_nodes (rtx
, case_node_ptr
, rtx_code_label
*, int, tree
);
113 /* Return the rtx-label that corresponds to a LABEL_DECL,
114 creating it if necessary. */
117 label_rtx (tree label
)
119 gcc_assert (TREE_CODE (label
) == LABEL_DECL
);
121 if (!DECL_RTL_SET_P (label
))
123 rtx_code_label
*r
= gen_label_rtx ();
124 SET_DECL_RTL (label
, r
);
125 if (FORCED_LABEL (label
) || DECL_NONLOCAL (label
))
126 LABEL_PRESERVE_P (r
) = 1;
129 return as_a
<rtx_insn
*> (DECL_RTL (label
));
132 /* As above, but also put it on the forced-reference list of the
133 function that contains it. */
135 force_label_rtx (tree label
)
137 rtx_insn
*ref
= label_rtx (label
);
138 tree function
= decl_function_context (label
);
140 gcc_assert (function
);
142 vec_safe_push (forced_labels
, ref
);
146 /* As label_rtx, but ensures (in check build), that returned value is
147 an existing label (i.e. rtx with code CODE_LABEL). */
149 jump_target_rtx (tree label
)
151 return as_a
<rtx_code_label
*> (label_rtx (label
));
154 /* Add an unconditional jump to LABEL as the next sequential instruction. */
157 emit_jump (rtx label
)
159 do_pending_stack_adjust ();
160 emit_jump_insn (targetm
.gen_jump (label
));
164 /* Handle goto statements and the labels that they can go to. */
166 /* Specify the location in the RTL code of a label LABEL,
167 which is a LABEL_DECL tree node.
169 This is used for the kind of label that the user can jump to with a
170 goto statement, and for alternatives of a switch or case statement.
171 RTL labels generated for loops and conditionals don't go through here;
172 they are generated directly at the RTL level, by other functions below.
174 Note that this has nothing to do with defining label *names*.
175 Languages vary in how they do that and what that even means. */
178 expand_label (tree label
)
180 rtx_code_label
*label_r
= jump_target_rtx (label
);
182 do_pending_stack_adjust ();
183 emit_label (label_r
);
184 if (DECL_NAME (label
))
185 LABEL_NAME (DECL_RTL (label
)) = IDENTIFIER_POINTER (DECL_NAME (label
));
187 if (DECL_NONLOCAL (label
))
189 expand_builtin_setjmp_receiver (NULL
);
190 nonlocal_goto_handler_labels
191 = gen_rtx_INSN_LIST (VOIDmode
, label_r
,
192 nonlocal_goto_handler_labels
);
195 if (FORCED_LABEL (label
))
196 vec_safe_push
<rtx_insn
*> (forced_labels
, label_r
);
198 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
199 maybe_set_first_label_num (label_r
);
202 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
203 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
204 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
205 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
206 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
207 constraint allows the use of a register operand. And, *IS_INOUT
208 will be true if the operand is read-write, i.e., if it is used as
209 an input as well as an output. If *CONSTRAINT_P is not in
210 canonical form, it will be made canonical. (Note that `+' will be
211 replaced with `=' as part of this process.)
213 Returns TRUE if all went well; FALSE if an error occurred. */
216 parse_output_constraint (const char **constraint_p
, int operand_num
,
217 int ninputs
, int noutputs
, bool *allows_mem
,
218 bool *allows_reg
, bool *is_inout
)
220 const char *constraint
= *constraint_p
;
223 /* Assume the constraint doesn't allow the use of either a register
228 /* Allow the `=' or `+' to not be at the beginning of the string,
229 since it wasn't explicitly documented that way, and there is a
230 large body of code that puts it last. Swap the character to
231 the front, so as not to uglify any place else. */
232 p
= strchr (constraint
, '=');
234 p
= strchr (constraint
, '+');
236 /* If the string doesn't contain an `=', issue an error
240 error ("output operand constraint lacks %<=%>");
244 /* If the constraint begins with `+', then the operand is both read
245 from and written to. */
246 *is_inout
= (*p
== '+');
248 /* Canonicalize the output constraint so that it begins with `='. */
249 if (p
!= constraint
|| *is_inout
)
252 size_t c_len
= strlen (constraint
);
255 warning (0, "output constraint %qc for operand %d "
256 "is not at the beginning",
259 /* Make a copy of the constraint. */
260 buf
= XALLOCAVEC (char, c_len
+ 1);
261 strcpy (buf
, constraint
);
262 /* Swap the first character and the `=' or `+'. */
263 buf
[p
- constraint
] = buf
[0];
264 /* Make sure the first character is an `='. (Until we do this,
265 it might be a `+'.) */
267 /* Replace the constraint with the canonicalized string. */
268 *constraint_p
= ggc_alloc_string (buf
, c_len
);
269 constraint
= *constraint_p
;
272 /* Loop through the constraint string. */
273 for (p
= constraint
+ 1; *p
; p
+= CONSTRAINT_LEN (*p
, p
))
278 error ("operand constraint contains incorrectly positioned "
283 if (operand_num
+ 1 == ninputs
+ noutputs
)
285 error ("%<%%%> constraint used with last operand");
290 case '?': case '!': case '*': case '&': case '#':
292 case 'E': case 'F': case 'G': case 'H':
293 case 's': case 'i': case 'n':
294 case 'I': case 'J': case 'K': case 'L': case 'M':
295 case 'N': case 'O': case 'P': case ',':
298 case '0': case '1': case '2': case '3': case '4':
299 case '5': case '6': case '7': case '8': case '9':
301 error ("matching constraint not valid in output operand");
305 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
306 excepting those that expand_call created. So match memory
319 enum constraint_num cn
= lookup_constraint (p
);
320 if (reg_class_for_constraint (cn
) != NO_REGS
321 || insn_extra_address_constraint (cn
))
323 else if (insn_extra_memory_constraint (cn
))
326 insn_extra_constraint_allows_reg_mem (cn
, allows_reg
, allows_mem
);
333 /* Similar, but for input constraints. */
336 parse_input_constraint (const char **constraint_p
, int input_num
,
337 int ninputs
, int noutputs
, int ninout
,
338 const char * const * constraints
,
339 bool *allows_mem
, bool *allows_reg
)
341 const char *constraint
= *constraint_p
;
342 const char *orig_constraint
= constraint
;
343 size_t c_len
= strlen (constraint
);
345 bool saw_match
= false;
347 /* Assume the constraint doesn't allow the use of either
348 a register or memory. */
352 /* Make sure constraint has neither `=', `+', nor '&'. */
354 for (j
= 0; j
< c_len
; j
+= CONSTRAINT_LEN (constraint
[j
], constraint
+j
))
355 switch (constraint
[j
])
357 case '+': case '=': case '&':
358 if (constraint
== orig_constraint
)
360 error ("input operand constraint contains %qc", constraint
[j
]);
366 if (constraint
== orig_constraint
367 && input_num
+ 1 == ninputs
- ninout
)
369 error ("%<%%%> constraint used with last operand");
375 case '?': case '!': case '*': case '#':
377 case 'E': case 'F': case 'G': case 'H':
378 case 's': case 'i': case 'n':
379 case 'I': case 'J': case 'K': case 'L': case 'M':
380 case 'N': case 'O': case 'P': case ',':
383 /* Whether or not a numeric constraint allows a register is
384 decided by the matching constraint, and so there is no need
385 to do anything special with them. We must handle them in
386 the default case, so that we don't unnecessarily force
387 operands to memory. */
388 case '0': case '1': case '2': case '3': case '4':
389 case '5': case '6': case '7': case '8': case '9':
396 match
= strtoul (constraint
+ j
, &end
, 10);
397 if (match
>= (unsigned long) noutputs
)
399 error ("matching constraint references invalid operand number");
403 /* Try and find the real constraint for this dup. Only do this
404 if the matching constraint is the only alternative. */
406 && (j
== 0 || (j
== 1 && constraint
[0] == '%')))
408 constraint
= constraints
[match
];
409 *constraint_p
= constraint
;
410 c_len
= strlen (constraint
);
412 /* ??? At the end of the loop, we will skip the first part of
413 the matched constraint. This assumes not only that the
414 other constraint is an output constraint, but also that
415 the '=' or '+' come first. */
419 j
= end
- constraint
;
420 /* Anticipate increment at end of loop. */
431 if (! ISALPHA (constraint
[j
]))
433 error ("invalid punctuation %qc in constraint", constraint
[j
]);
436 enum constraint_num cn
= lookup_constraint (constraint
+ j
);
437 if (reg_class_for_constraint (cn
) != NO_REGS
438 || insn_extra_address_constraint (cn
))
440 else if (insn_extra_memory_constraint (cn
)
441 || insn_extra_special_memory_constraint (cn
))
444 insn_extra_constraint_allows_reg_mem (cn
, allows_reg
, allows_mem
);
448 if (saw_match
&& !*allows_reg
)
449 warning (0, "matching constraint does not allow a register");
454 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
455 can be an asm-declared register. Called via walk_tree. */
458 decl_overlaps_hard_reg_set_p (tree
*declp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
462 const HARD_REG_SET
*const regs
= (const HARD_REG_SET
*) data
;
466 if (DECL_HARD_REGISTER (decl
)
467 && REG_P (DECL_RTL (decl
))
468 && REGNO (DECL_RTL (decl
)) < FIRST_PSEUDO_REGISTER
)
470 rtx reg
= DECL_RTL (decl
);
472 if (overlaps_hard_reg_set_p (*regs
, GET_MODE (reg
), REGNO (reg
)))
477 else if (TYPE_P (decl
) || TREE_CODE (decl
) == PARM_DECL
)
482 /* If there is an overlap between *REGS and DECL, return the first overlap
485 tree_overlaps_hard_reg_set (tree decl
, HARD_REG_SET
*regs
)
487 return walk_tree (&decl
, decl_overlaps_hard_reg_set_p
, regs
, NULL
);
491 /* A subroutine of expand_asm_operands. Check that all operand names
492 are unique. Return true if so. We rely on the fact that these names
493 are identifiers, and so have been canonicalized by get_identifier,
494 so all we need are pointer comparisons. */
497 check_unique_operand_names (tree outputs
, tree inputs
, tree labels
)
499 tree i
, j
, i_name
= NULL_TREE
;
501 for (i
= outputs
; i
; i
= TREE_CHAIN (i
))
503 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
507 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
508 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
512 for (i
= inputs
; i
; i
= TREE_CHAIN (i
))
514 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
518 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
519 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
521 for (j
= outputs
; j
; j
= TREE_CHAIN (j
))
522 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
526 for (i
= labels
; i
; i
= TREE_CHAIN (i
))
528 i_name
= TREE_PURPOSE (i
);
532 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
533 if (simple_cst_equal (i_name
, TREE_PURPOSE (j
)))
535 for (j
= inputs
; j
; j
= TREE_CHAIN (j
))
536 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
543 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name
));
547 /* Resolve the names of the operands in *POUTPUTS and *PINPUTS to numbers,
548 and replace the name expansions in STRING and in the constraints to
549 those numbers. This is generally done in the front end while creating
550 the ASM_EXPR generic tree that eventually becomes the GIMPLE_ASM. */
553 resolve_asm_operand_names (tree string
, tree outputs
, tree inputs
, tree labels
)
560 check_unique_operand_names (outputs
, inputs
, labels
);
562 /* Substitute [<name>] in input constraint strings. There should be no
563 named operands in output constraints. */
564 for (t
= inputs
; t
; t
= TREE_CHAIN (t
))
566 c
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
567 if (strchr (c
, '[') != NULL
)
569 p
= buffer
= xstrdup (c
);
570 while ((p
= strchr (p
, '[')) != NULL
)
571 p
= resolve_operand_name_1 (p
, outputs
, inputs
, NULL
);
572 TREE_VALUE (TREE_PURPOSE (t
))
573 = build_string (strlen (buffer
), buffer
);
578 /* Now check for any needed substitutions in the template. */
579 c
= TREE_STRING_POINTER (string
);
580 while ((c
= strchr (c
, '%')) != NULL
)
584 else if (ISALPHA (c
[1]) && c
[2] == '[')
588 c
+= 1 + (c
[1] == '%');
595 /* OK, we need to make a copy so we can perform the substitutions.
596 Assume that we will not need extra space--we get to remove '['
597 and ']', which means we cannot have a problem until we have more
598 than 999 operands. */
599 buffer
= xstrdup (TREE_STRING_POINTER (string
));
600 p
= buffer
+ (c
- TREE_STRING_POINTER (string
));
602 while ((p
= strchr (p
, '%')) != NULL
)
606 else if (ISALPHA (p
[1]) && p
[2] == '[')
610 p
+= 1 + (p
[1] == '%');
614 p
= resolve_operand_name_1 (p
, outputs
, inputs
, labels
);
617 string
= build_string (strlen (buffer
), buffer
);
624 /* A subroutine of resolve_operand_names. P points to the '[' for a
625 potential named operand of the form [<name>]. In place, replace
626 the name and brackets with a number. Return a pointer to the
627 balance of the string after substitution. */
630 resolve_operand_name_1 (char *p
, tree outputs
, tree inputs
, tree labels
)
636 /* Collect the operand name. */
637 q
= strchr (++p
, ']');
640 error ("missing close brace for named operand");
641 return strchr (p
, '\0');
645 /* Resolve the name to a number. */
646 for (op
= 0, t
= outputs
; t
; t
= TREE_CHAIN (t
), op
++)
648 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
649 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
652 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), op
++)
654 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
655 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
658 for (t
= labels
; t
; t
= TREE_CHAIN (t
), op
++)
660 tree name
= TREE_PURPOSE (t
);
661 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
665 error ("undefined named operand %qs", identifier_to_locale (p
));
669 /* Replace the name with the number. Unfortunately, not all libraries
670 get the return value of sprintf correct, so search for the end of the
671 generated string by hand. */
672 sprintf (--p
, "%d", op
);
673 p
= strchr (p
, '\0');
675 /* Verify the no extra buffer space assumption. */
678 /* Shift the rest of the buffer down to fill the gap. */
679 memmove (p
, q
+ 1, strlen (q
+ 1) + 1);
685 /* Generate RTL to return directly from the current function.
686 (That is, we bypass any return value.) */
689 expand_naked_return (void)
691 rtx_code_label
*end_label
;
693 clear_pending_stack_adjust ();
694 do_pending_stack_adjust ();
696 end_label
= naked_return_label
;
698 end_label
= naked_return_label
= gen_label_rtx ();
700 emit_jump (end_label
);
703 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
704 is the probability of jumping to LABEL. */
706 do_jump_if_equal (machine_mode mode
, rtx op0
, rtx op1
, rtx_code_label
*label
,
707 int unsignedp
, int prob
)
709 gcc_assert (prob
<= REG_BR_PROB_BASE
);
710 do_compare_rtx_and_jump (op0
, op1
, EQ
, unsignedp
, mode
,
711 NULL_RTX
, NULL
, label
, prob
);
714 /* Do the insertion of a case label into case_list. The labels are
715 fed to us in descending order from the sorted vector of case labels used
716 in the tree part of the middle end. So the list we construct is
717 sorted in ascending order.
719 LABEL is the case label to be inserted. LOW and HIGH are the bounds
720 against which the index is compared to jump to LABEL and PROB is the
721 estimated probability LABEL is reached from the switch statement. */
723 static struct case_node
*
724 add_case_node (struct case_node
*head
, tree low
, tree high
,
725 tree label
, int prob
,
726 object_allocator
<case_node
> &case_node_pool
)
730 gcc_checking_assert (low
);
731 gcc_checking_assert (high
&& (TREE_TYPE (low
) == TREE_TYPE (high
)));
733 /* Add this label to the chain. */
734 r
= case_node_pool
.allocate ();
737 r
->code_label
= label
;
738 r
->parent
= r
->left
= NULL
;
740 r
->subtree_prob
= prob
;
745 /* Dump ROOT, a list or tree of case nodes, to file. */
748 dump_case_nodes (FILE *f
, struct case_node
*root
,
749 int indent_step
, int indent_level
)
755 dump_case_nodes (f
, root
->left
, indent_step
, indent_level
);
758 fprintf (f
, "%*s", indent_step
* indent_level
, "");
759 print_dec (root
->low
, f
, TYPE_SIGN (TREE_TYPE (root
->low
)));
760 if (!tree_int_cst_equal (root
->low
, root
->high
))
762 fprintf (f
, " ... ");
763 print_dec (root
->high
, f
, TYPE_SIGN (TREE_TYPE (root
->high
)));
767 dump_case_nodes (f
, root
->right
, indent_step
, indent_level
);
770 /* Return the smallest number of different values for which it is best to use a
771 jump-table instead of a tree of conditional branches. */
774 case_values_threshold (void)
776 unsigned int threshold
= PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD
);
779 threshold
= targetm
.case_values_threshold ();
784 /* Return true if a switch should be expanded as a decision tree.
785 RANGE is the difference between highest and lowest case.
786 UNIQ is number of unique case node targets, not counting the default case.
787 COUNT is the number of comparisons needed, not counting the default case. */
790 expand_switch_as_decision_tree_p (tree range
,
791 unsigned int uniq ATTRIBUTE_UNUSED
,
796 /* If neither casesi or tablejump is available, or flag_jump_tables
797 over-ruled us, we really have no choice. */
798 if (!targetm
.have_casesi () && !targetm
.have_tablejump ())
800 if (!flag_jump_tables
)
802 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
807 /* If the switch is relatively small such that the cost of one
808 indirect jump on the target are higher than the cost of a
809 decision tree, go with the decision tree.
811 If range of values is much bigger than number of values,
812 or if it is too large to represent in a HOST_WIDE_INT,
813 make a sequence of conditional branches instead of a dispatch.
815 The definition of "much bigger" depends on whether we are
816 optimizing for size or for speed. If the former, the maximum
817 ratio range/count = 3, because this was found to be the optimal
818 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
819 10 is much older, and was probably selected after an extensive
820 benchmarking investigation on numerous platforms. Or maybe it
821 just made sense to someone at some point in the history of GCC,
823 max_ratio
= optimize_insn_for_size_p () ? 3 : 10;
824 if (count
< case_values_threshold ()
825 || ! tree_fits_uhwi_p (range
)
826 || compare_tree_int (range
, max_ratio
* count
) > 0)
832 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
833 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
834 DEFAULT_PROB is the estimated probability that it jumps to
837 We generate a binary decision tree to select the appropriate target
838 code. This is done as follows:
840 If the index is a short or char that we do not have
841 an insn to handle comparisons directly, convert it to
842 a full integer now, rather than letting each comparison
843 generate the conversion.
845 Load the index into a register.
847 The list of cases is rearranged into a binary tree,
848 nearly optimal assuming equal probability for each case.
850 The tree is transformed into RTL, eliminating redundant
851 test conditions at the same time.
853 If program flow could reach the end of the decision tree
854 an unconditional jump to the default code is emitted.
856 The above process is unaware of the CFG. The caller has to fix up
857 the CFG itself. This is done in cfgexpand.c. */
860 emit_case_decision_tree (tree index_expr
, tree index_type
,
861 case_node_ptr case_list
, rtx_code_label
*default_label
,
864 rtx index
= expand_normal (index_expr
);
866 if (GET_MODE_CLASS (GET_MODE (index
)) == MODE_INT
867 && ! have_insn_for (COMPARE
, GET_MODE (index
)))
869 int unsignedp
= TYPE_UNSIGNED (index_type
);
870 machine_mode wider_mode
;
871 for (wider_mode
= GET_MODE (index
); wider_mode
!= VOIDmode
;
872 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
873 if (have_insn_for (COMPARE
, wider_mode
))
875 index
= convert_to_mode (wider_mode
, index
, unsignedp
);
880 do_pending_stack_adjust ();
884 index
= copy_to_reg (index
);
885 if (TREE_CODE (index_expr
) == SSA_NAME
)
886 set_reg_attrs_for_decl_rtl (index_expr
, index
);
889 balance_case_nodes (&case_list
, NULL
);
891 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
893 int indent_step
= ceil_log2 (TYPE_PRECISION (index_type
)) + 2;
894 fprintf (dump_file
, ";; Expanding GIMPLE switch as decision tree:\n");
895 dump_case_nodes (dump_file
, case_list
, indent_step
, 0);
898 emit_case_nodes (index
, case_list
, default_label
, default_prob
, index_type
);
900 emit_jump (default_label
);
903 /* Return the sum of probabilities of outgoing edges of basic block BB. */
906 get_outgoing_edge_probs (basic_block bb
)
913 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
914 prob_sum
+= e
->probability
;
918 /* Computes the conditional probability of jumping to a target if the branch
919 instruction is executed.
920 TARGET_PROB is the estimated probability of jumping to a target relative
921 to some basic block BB.
922 BASE_PROB is the probability of reaching the branch instruction relative
923 to the same basic block BB. */
926 conditional_probability (int target_prob
, int base_prob
)
930 gcc_assert (target_prob
>= 0);
931 gcc_assert (target_prob
<= base_prob
);
932 return GCOV_COMPUTE_SCALE (target_prob
, base_prob
);
937 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
938 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
939 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
940 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
942 First, a jump insn is emitted. First we try "casesi". If that
943 fails, try "tablejump". A target *must* have one of them (or both).
945 Then, a table with the target labels is emitted.
947 The process is unaware of the CFG. The caller has to fix up
948 the CFG itself. This is done in cfgexpand.c. */
951 emit_case_dispatch_table (tree index_expr
, tree index_type
,
952 struct case_node
*case_list
, rtx default_label
,
953 tree minval
, tree maxval
, tree range
,
959 rtx_insn
*fallback_label
= label_rtx (case_list
->code_label
);
960 rtx_code_label
*table_label
= gen_label_rtx ();
961 bool has_gaps
= false;
962 edge default_edge
= stmt_bb
? EDGE_SUCC (stmt_bb
, 0) : NULL
;
963 int default_prob
= default_edge
? default_edge
->probability
: 0;
964 int base
= get_outgoing_edge_probs (stmt_bb
);
965 bool try_with_tablejump
= false;
967 int new_default_prob
= conditional_probability (default_prob
,
970 if (! try_casesi (index_type
, index_expr
, minval
, range
,
971 table_label
, default_label
, fallback_label
,
974 /* Index jumptables from zero for suitable values of minval to avoid
975 a subtraction. For the rationale see:
976 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
977 if (optimize_insn_for_speed_p ()
978 && compare_tree_int (minval
, 0) > 0
979 && compare_tree_int (minval
, 3) < 0)
981 minval
= build_int_cst (index_type
, 0);
985 try_with_tablejump
= true;
988 /* Get table of labels to jump to, in order of case index. */
990 ncases
= tree_to_shwi (range
) + 1;
991 labelvec
= XALLOCAVEC (rtx
, ncases
);
992 memset (labelvec
, 0, ncases
* sizeof (rtx
));
994 for (n
= case_list
; n
; n
= n
->right
)
996 /* Compute the low and high bounds relative to the minimum
997 value since that should fit in a HOST_WIDE_INT while the
998 actual values may not. */
1000 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1002 HOST_WIDE_INT i_high
1003 = tree_to_uhwi (fold_build2 (MINUS_EXPR
, index_type
,
1007 for (i
= i_low
; i
<= i_high
; i
++)
1009 = gen_rtx_LABEL_REF (Pmode
, label_rtx (n
->code_label
));
1012 /* The dispatch table may contain gaps, including at the beginning of
1013 the table if we tried to avoid the minval subtraction. We fill the
1014 dispatch table slots associated with the gaps with the default case label.
1015 However, in the event the default case is unreachable, we then use
1016 any label from one of the case statements. */
1017 rtx gap_label
= (default_label
) ? default_label
: fallback_label
;
1019 for (i
= 0; i
< ncases
; i
++)
1020 if (labelvec
[i
] == 0)
1023 labelvec
[i
] = gen_rtx_LABEL_REF (Pmode
, gap_label
);
1026 if (has_gaps
&& default_label
)
1028 /* There is at least one entry in the jump table that jumps
1029 to default label. The default label can either be reached
1030 through the indirect jump or the direct conditional jump
1031 before that. Split the probability of reaching the
1032 default label among these two jumps. */
1033 new_default_prob
= conditional_probability (default_prob
/2,
1036 base
-= default_prob
;
1040 base
-= default_prob
;
1045 default_edge
->probability
= default_prob
;
1047 /* We have altered the probability of the default edge. So the probabilities
1048 of all other edges need to be adjusted so that it sums up to
1049 REG_BR_PROB_BASE. */
1054 FOR_EACH_EDGE (e
, ei
, stmt_bb
->succs
)
1055 e
->probability
= GCOV_COMPUTE_SCALE (e
->probability
, base
);
1058 if (try_with_tablejump
)
1060 bool ok
= try_tablejump (index_type
, index_expr
, minval
, range
,
1061 table_label
, default_label
, new_default_prob
);
1064 /* Output the table. */
1065 emit_label (table_label
);
1067 if (CASE_VECTOR_PC_RELATIVE
|| flag_pic
)
1068 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE
,
1069 gen_rtx_LABEL_REF (Pmode
,
1071 gen_rtvec_v (ncases
, labelvec
),
1072 const0_rtx
, const0_rtx
));
1074 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE
,
1075 gen_rtvec_v (ncases
, labelvec
)));
1077 /* Record no drop-through after the table. */
1081 /* Reset the aux field of all outgoing edges of basic block BB. */
1084 reset_out_edges_aux (basic_block bb
)
1088 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1092 /* Compute the number of case labels that correspond to each outgoing edge of
1093 STMT. Record this information in the aux field of the edge. */
1096 compute_cases_per_edge (gswitch
*stmt
)
1098 basic_block bb
= gimple_bb (stmt
);
1099 reset_out_edges_aux (bb
);
1100 int ncases
= gimple_switch_num_labels (stmt
);
1101 for (int i
= ncases
- 1; i
>= 1; --i
)
1103 tree elt
= gimple_switch_label (stmt
, i
);
1104 tree lab
= CASE_LABEL (elt
);
1105 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1106 edge case_edge
= find_edge (bb
, case_bb
);
1107 case_edge
->aux
= (void *)((intptr_t)(case_edge
->aux
) + 1);
1111 /* Terminate a case (Pascal/Ada) or switch (C) statement
1112 in which ORIG_INDEX is the expression to be tested.
1113 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
1114 type as given in the source before any compiler conversions.
1115 Generate the code to test it and jump to the right place. */
1118 expand_case (gswitch
*stmt
)
1120 tree minval
= NULL_TREE
, maxval
= NULL_TREE
, range
= NULL_TREE
;
1121 rtx_code_label
*default_label
;
1122 unsigned int count
, uniq
;
1124 int ncases
= gimple_switch_num_labels (stmt
);
1125 tree index_expr
= gimple_switch_index (stmt
);
1126 tree index_type
= TREE_TYPE (index_expr
);
1128 basic_block bb
= gimple_bb (stmt
);
1130 /* A list of case labels; it is first built as a list and it may then
1131 be rearranged into a nearly balanced binary tree. */
1132 struct case_node
*case_list
= 0;
1134 /* A pool for case nodes. */
1135 object_allocator
<case_node
> case_node_pool ("struct case_node pool");
1137 /* An ERROR_MARK occurs for various reasons including invalid data type.
1138 ??? Can this still happen, with GIMPLE and all? */
1139 if (index_type
== error_mark_node
)
1142 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
1143 expressions being INTEGER_CST. */
1144 gcc_assert (TREE_CODE (index_expr
) != INTEGER_CST
);
1147 do_pending_stack_adjust ();
1149 /* Find the default case target label. */
1150 default_label
= jump_target_rtx
1151 (CASE_LABEL (gimple_switch_default_label (stmt
)));
1152 edge default_edge
= EDGE_SUCC (bb
, 0);
1153 int default_prob
= default_edge
->probability
;
1155 /* Get upper and lower bounds of case values. */
1156 elt
= gimple_switch_label (stmt
, 1);
1157 minval
= fold_convert (index_type
, CASE_LOW (elt
));
1158 elt
= gimple_switch_label (stmt
, ncases
- 1);
1159 if (CASE_HIGH (elt
))
1160 maxval
= fold_convert (index_type
, CASE_HIGH (elt
));
1162 maxval
= fold_convert (index_type
, CASE_LOW (elt
));
1164 /* Compute span of values. */
1165 range
= fold_build2 (MINUS_EXPR
, index_type
, maxval
, minval
);
1167 /* Listify the labels queue and gather some numbers to decide
1168 how to expand this switch(). */
1171 hash_set
<tree
> seen_labels
;
1172 compute_cases_per_edge (stmt
);
1174 for (i
= ncases
- 1; i
>= 1; --i
)
1176 elt
= gimple_switch_label (stmt
, i
);
1177 tree low
= CASE_LOW (elt
);
1179 tree high
= CASE_HIGH (elt
);
1180 gcc_assert (! high
|| tree_int_cst_lt (low
, high
));
1181 tree lab
= CASE_LABEL (elt
);
1183 /* Count the elements.
1184 A range counts double, since it requires two compares. */
1189 /* If we have not seen this label yet, then increase the
1190 number of unique case node targets seen. */
1191 if (!seen_labels
.add (lab
))
1194 /* The bounds on the case range, LOW and HIGH, have to be converted
1195 to case's index type TYPE. Note that the original type of the
1196 case index in the source code is usually "lost" during
1197 gimplification due to type promotion, but the case labels retain the
1198 original type. Make sure to drop overflow flags. */
1199 low
= fold_convert (index_type
, low
);
1200 if (TREE_OVERFLOW (low
))
1201 low
= wide_int_to_tree (index_type
, low
);
1203 /* The canonical from of a case label in GIMPLE is that a simple case
1204 has an empty CASE_HIGH. For the casesi and tablejump expanders,
1205 the back ends want simple cases to have high == low. */
1208 high
= fold_convert (index_type
, high
);
1209 if (TREE_OVERFLOW (high
))
1210 high
= wide_int_to_tree (index_type
, high
);
1212 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
1213 edge case_edge
= find_edge (bb
, case_bb
);
1214 case_list
= add_case_node (
1215 case_list
, low
, high
, lab
,
1216 case_edge
->probability
/ (intptr_t)(case_edge
->aux
),
1219 reset_out_edges_aux (bb
);
1221 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
1222 destination, such as one with a default case only.
1223 It also removes cases that are out of range for the switch
1224 type, so we should never get a zero here. */
1225 gcc_assert (count
> 0);
1227 rtx_insn
*before_case
= get_last_insn ();
1229 /* Decide how to expand this switch.
1230 The two options at this point are a dispatch table (casesi or
1231 tablejump) or a decision tree. */
1233 if (expand_switch_as_decision_tree_p (range
, uniq
, count
))
1234 emit_case_decision_tree (index_expr
, index_type
,
1235 case_list
, default_label
,
1239 /* If the default case is unreachable, then set default_label to NULL
1240 so that we omit the range check when generating the dispatch table.
1241 We also remove the edge to the unreachable default case. The block
1242 itself will be automatically removed later. */
1243 if (EDGE_COUNT (default_edge
->dest
->succs
) == 0
1244 && gimple_seq_unreachable_p (bb_seq (default_edge
->dest
)))
1246 default_label
= NULL
;
1247 remove_edge (default_edge
);
1249 emit_case_dispatch_table (index_expr
, index_type
,
1250 case_list
, default_label
,
1251 minval
, maxval
, range
, bb
);
1254 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1259 /* Expand the dispatch to a short decrement chain if there are few cases
1260 to dispatch to. Likewise if neither casesi nor tablejump is available,
1261 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
1262 tablejump. The index mode is always the mode of integer_type_node.
1263 Trap if no case matches the index.
1265 DISPATCH_INDEX is the index expression to switch on. It should be a
1266 memory or register operand.
1268 DISPATCH_TABLE is a set of case labels. The set should be sorted in
1269 ascending order, be contiguous, starting with value 0, and contain only
1270 single-valued case labels. */
1273 expand_sjlj_dispatch_table (rtx dispatch_index
,
1274 vec
<tree
> dispatch_table
)
1276 tree index_type
= integer_type_node
;
1277 machine_mode index_mode
= TYPE_MODE (index_type
);
1279 int ncases
= dispatch_table
.length ();
1281 do_pending_stack_adjust ();
1282 rtx_insn
*before_case
= get_last_insn ();
1284 /* Expand as a decrement-chain if there are 5 or fewer dispatch
1285 labels. This covers more than 98% of the cases in libjava,
1286 and seems to be a reasonable compromise between the "old way"
1287 of expanding as a decision tree or dispatch table vs. the "new
1288 way" with decrement chain or dispatch table. */
1289 if (dispatch_table
.length () <= 5
1290 || (!targetm
.have_casesi () && !targetm
.have_tablejump ())
1291 || !flag_jump_tables
)
1293 /* Expand the dispatch as a decrement chain:
1295 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
1299 if (index == 0) do_0; else index--;
1300 if (index == 0) do_1; else index--;
1302 if (index == 0) do_N; else index--;
1304 This is more efficient than a dispatch table on most machines.
1305 The last "index--" is redundant but the code is trivially dead
1306 and will be cleaned up by later passes. */
1307 rtx index
= copy_to_mode_reg (index_mode
, dispatch_index
);
1308 rtx zero
= CONST0_RTX (index_mode
);
1309 for (int i
= 0; i
< ncases
; i
++)
1311 tree elt
= dispatch_table
[i
];
1312 rtx_code_label
*lab
= jump_target_rtx (CASE_LABEL (elt
));
1313 do_jump_if_equal (index_mode
, index
, zero
, lab
, 0, -1);
1314 force_expand_binop (index_mode
, sub_optab
,
1315 index
, CONST1_RTX (index_mode
),
1316 index
, 0, OPTAB_DIRECT
);
1321 /* Similar to expand_case, but much simpler. */
1322 struct case_node
*case_list
= 0;
1323 object_allocator
<case_node
> case_node_pool ("struct sjlj_case pool");
1324 tree index_expr
= make_tree (index_type
, dispatch_index
);
1325 tree minval
= build_int_cst (index_type
, 0);
1326 tree maxval
= CASE_LOW (dispatch_table
.last ());
1327 tree range
= maxval
;
1328 rtx_code_label
*default_label
= gen_label_rtx ();
1330 for (int i
= ncases
- 1; i
>= 0; --i
)
1332 tree elt
= dispatch_table
[i
];
1333 tree low
= CASE_LOW (elt
);
1334 tree lab
= CASE_LABEL (elt
);
1335 case_list
= add_case_node (case_list
, low
, low
, lab
, 0, case_node_pool
);
1338 emit_case_dispatch_table (index_expr
, index_type
,
1339 case_list
, default_label
,
1340 minval
, maxval
, range
,
1341 BLOCK_FOR_INSN (before_case
));
1342 emit_label (default_label
);
1345 /* Dispatching something not handled? Trap! */
1346 expand_builtin_trap ();
1348 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
1354 /* Take an ordered list of case nodes
1355 and transform them into a near optimal binary tree,
1356 on the assumption that any target code selection value is as
1357 likely as any other.
1359 The transformation is performed by splitting the ordered
1360 list into two equal sections plus a pivot. The parts are
1361 then attached to the pivot as left and right branches. Each
1362 branch is then transformed recursively. */
1365 balance_case_nodes (case_node_ptr
*head
, case_node_ptr parent
)
1377 /* Count the number of entries on branch. Also count the ranges. */
1381 if (!tree_int_cst_equal (np
->low
, np
->high
))
1390 /* Split this list if it is long enough for that to help. */
1394 /* If there are just three nodes, split at the middle one. */
1396 npp
= &(*npp
)->right
;
1399 /* Find the place in the list that bisects the list's total cost,
1400 where ranges count as 2.
1401 Here I gets half the total cost. */
1402 i
= (i
+ ranges
+ 1) / 2;
1405 /* Skip nodes while their cost does not reach that amount. */
1406 if (!tree_int_cst_equal ((*npp
)->low
, (*npp
)->high
))
1411 npp
= &(*npp
)->right
;
1416 np
->parent
= parent
;
1419 /* Optimize each of the two split parts. */
1420 balance_case_nodes (&np
->left
, np
);
1421 balance_case_nodes (&np
->right
, np
);
1422 np
->subtree_prob
= np
->prob
;
1423 np
->subtree_prob
+= np
->left
->subtree_prob
;
1424 np
->subtree_prob
+= np
->right
->subtree_prob
;
1428 /* Else leave this branch as one level,
1429 but fill in `parent' fields. */
1431 np
->parent
= parent
;
1432 np
->subtree_prob
= np
->prob
;
1433 for (; np
->right
; np
= np
->right
)
1435 np
->right
->parent
= np
;
1436 (*head
)->subtree_prob
+= np
->right
->subtree_prob
;
1442 /* Search the parent sections of the case node tree
1443 to see if a test for the lower bound of NODE would be redundant.
1444 INDEX_TYPE is the type of the index expression.
1446 The instructions to generate the case decision tree are
1447 output in the same order as nodes are processed so it is
1448 known that if a parent node checks the range of the current
1449 node minus one that the current node is bounded at its lower
1450 span. Thus the test would be redundant. */
1453 node_has_low_bound (case_node_ptr node
, tree index_type
)
1456 case_node_ptr pnode
;
1458 /* If the lower bound of this node is the lowest value in the index type,
1459 we need not test it. */
1461 if (tree_int_cst_equal (node
->low
, TYPE_MIN_VALUE (index_type
)))
1464 /* If this node has a left branch, the value at the left must be less
1465 than that at this node, so it cannot be bounded at the bottom and
1466 we need not bother testing any further. */
1471 low_minus_one
= fold_build2 (MINUS_EXPR
, TREE_TYPE (node
->low
),
1473 build_int_cst (TREE_TYPE (node
->low
), 1));
1475 /* If the subtraction above overflowed, we can't verify anything.
1476 Otherwise, look for a parent that tests our value - 1. */
1478 if (! tree_int_cst_lt (low_minus_one
, node
->low
))
1481 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1482 if (tree_int_cst_equal (low_minus_one
, pnode
->high
))
1488 /* Search the parent sections of the case node tree
1489 to see if a test for the upper bound of NODE would be redundant.
1490 INDEX_TYPE is the type of the index expression.
1492 The instructions to generate the case decision tree are
1493 output in the same order as nodes are processed so it is
1494 known that if a parent node checks the range of the current
1495 node plus one that the current node is bounded at its upper
1496 span. Thus the test would be redundant. */
1499 node_has_high_bound (case_node_ptr node
, tree index_type
)
1502 case_node_ptr pnode
;
1504 /* If there is no upper bound, obviously no test is needed. */
1506 if (TYPE_MAX_VALUE (index_type
) == NULL
)
1509 /* If the upper bound of this node is the highest value in the type
1510 of the index expression, we need not test against it. */
1512 if (tree_int_cst_equal (node
->high
, TYPE_MAX_VALUE (index_type
)))
1515 /* If this node has a right branch, the value at the right must be greater
1516 than that at this node, so it cannot be bounded at the top and
1517 we need not bother testing any further. */
1522 high_plus_one
= fold_build2 (PLUS_EXPR
, TREE_TYPE (node
->high
),
1524 build_int_cst (TREE_TYPE (node
->high
), 1));
1526 /* If the addition above overflowed, we can't verify anything.
1527 Otherwise, look for a parent that tests our value + 1. */
1529 if (! tree_int_cst_lt (node
->high
, high_plus_one
))
1532 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
1533 if (tree_int_cst_equal (high_plus_one
, pnode
->low
))
1539 /* Search the parent sections of the
1540 case node tree to see if both tests for the upper and lower
1541 bounds of NODE would be redundant. */
1544 node_is_bounded (case_node_ptr node
, tree index_type
)
1546 return (node_has_low_bound (node
, index_type
)
1547 && node_has_high_bound (node
, index_type
));
1551 /* Emit step-by-step code to select a case for the value of INDEX.
1552 The thus generated decision tree follows the form of the
1553 case-node binary tree NODE, whose nodes represent test conditions.
1554 INDEX_TYPE is the type of the index of the switch.
1556 Care is taken to prune redundant tests from the decision tree
1557 by detecting any boundary conditions already checked by
1558 emitted rtx. (See node_has_high_bound, node_has_low_bound
1559 and node_is_bounded, above.)
1561 Where the test conditions can be shown to be redundant we emit
1562 an unconditional jump to the target code. As a further
1563 optimization, the subordinates of a tree node are examined to
1564 check for bounded nodes. In this case conditional and/or
1565 unconditional jumps as a result of the boundary check for the
1566 current node are arranged to target the subordinates associated
1567 code for out of bound conditions on the current node.
1569 We can assume that when control reaches the code generated here,
1570 the index value has already been compared with the parents
1571 of this node, and determined to be on the same side of each parent
1572 as this node is. Thus, if this node tests for the value 51,
1573 and a parent tested for 52, we don't need to consider
1574 the possibility of a value greater than 51. If another parent
1575 tests for the value 50, then this node need not test anything. */
1578 emit_case_nodes (rtx index
, case_node_ptr node
, rtx_code_label
*default_label
,
1579 int default_prob
, tree index_type
)
1581 /* If INDEX has an unsigned type, we must make unsigned branches. */
1582 int unsignedp
= TYPE_UNSIGNED (index_type
);
1584 int prob
= node
->prob
, subtree_prob
= node
->subtree_prob
;
1585 machine_mode mode
= GET_MODE (index
);
1586 machine_mode imode
= TYPE_MODE (index_type
);
1588 /* Handle indices detected as constant during RTL expansion. */
1589 if (mode
== VOIDmode
)
1592 /* See if our parents have already tested everything for us.
1593 If they have, emit an unconditional jump for this node. */
1594 if (node_is_bounded (node
, index_type
))
1595 emit_jump (label_rtx (node
->code_label
));
1597 else if (tree_int_cst_equal (node
->low
, node
->high
))
1599 probability
= conditional_probability (prob
, subtree_prob
+ default_prob
);
1600 /* Node is single valued. First see if the index expression matches
1601 this node and then check our children, if any. */
1602 do_jump_if_equal (mode
, index
,
1603 convert_modes (mode
, imode
,
1604 expand_normal (node
->low
),
1606 jump_target_rtx (node
->code_label
),
1607 unsignedp
, probability
);
1608 /* Since this case is taken at this point, reduce its weight from
1610 subtree_prob
-= prob
;
1611 if (node
->right
!= 0 && node
->left
!= 0)
1613 /* This node has children on both sides.
1614 Dispatch to one side or the other
1615 by comparing the index value with this node's value.
1616 If one subtree is bounded, check that one first,
1617 so we can avoid real branches in the tree. */
1619 if (node_is_bounded (node
->right
, index_type
))
1621 probability
= conditional_probability (
1623 subtree_prob
+ default_prob
);
1624 emit_cmp_and_jump_insns (index
,
1627 expand_normal (node
->high
),
1629 GT
, NULL_RTX
, mode
, unsignedp
,
1630 label_rtx (node
->right
->code_label
),
1632 emit_case_nodes (index
, node
->left
, default_label
, default_prob
,
1636 else if (node_is_bounded (node
->left
, index_type
))
1638 probability
= conditional_probability (
1640 subtree_prob
+ default_prob
);
1641 emit_cmp_and_jump_insns (index
,
1644 expand_normal (node
->high
),
1646 LT
, NULL_RTX
, mode
, unsignedp
,
1647 label_rtx (node
->left
->code_label
),
1649 emit_case_nodes (index
, node
->right
, default_label
, default_prob
,
1653 /* If both children are single-valued cases with no
1654 children, finish up all the work. This way, we can save
1655 one ordered comparison. */
1656 else if (tree_int_cst_equal (node
->right
->low
, node
->right
->high
)
1657 && node
->right
->left
== 0
1658 && node
->right
->right
== 0
1659 && tree_int_cst_equal (node
->left
->low
, node
->left
->high
)
1660 && node
->left
->left
== 0
1661 && node
->left
->right
== 0)
1663 /* Neither node is bounded. First distinguish the two sides;
1664 then emit the code for one side at a time. */
1666 /* See if the value matches what the right hand side
1668 probability
= conditional_probability (
1670 subtree_prob
+ default_prob
);
1671 do_jump_if_equal (mode
, index
,
1672 convert_modes (mode
, imode
,
1673 expand_normal (node
->right
->low
),
1675 jump_target_rtx (node
->right
->code_label
),
1676 unsignedp
, probability
);
1678 /* See if the value matches what the left hand side
1680 probability
= conditional_probability (
1682 subtree_prob
+ default_prob
);
1683 do_jump_if_equal (mode
, index
,
1684 convert_modes (mode
, imode
,
1685 expand_normal (node
->left
->low
),
1687 jump_target_rtx (node
->left
->code_label
),
1688 unsignedp
, probability
);
1693 /* Neither node is bounded. First distinguish the two sides;
1694 then emit the code for one side at a time. */
1697 = build_decl (curr_insn_location (),
1698 LABEL_DECL
, NULL_TREE
, void_type_node
);
1700 /* The default label could be reached either through the right
1701 subtree or the left subtree. Divide the probability
1703 probability
= conditional_probability (
1704 node
->right
->subtree_prob
+ default_prob
/2,
1705 subtree_prob
+ default_prob
);
1706 /* See if the value is on the right. */
1707 emit_cmp_and_jump_insns (index
,
1710 expand_normal (node
->high
),
1712 GT
, NULL_RTX
, mode
, unsignedp
,
1713 label_rtx (test_label
),
1717 /* Value must be on the left.
1718 Handle the left-hand subtree. */
1719 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1720 /* If left-hand subtree does nothing,
1723 emit_jump (default_label
);
1725 /* Code branches here for the right-hand subtree. */
1726 expand_label (test_label
);
1727 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1731 else if (node
->right
!= 0 && node
->left
== 0)
1733 /* Here we have a right child but no left so we issue a conditional
1734 branch to default and process the right child.
1736 Omit the conditional branch to default if the right child
1737 does not have any children and is single valued; it would
1738 cost too much space to save so little time. */
1740 if (node
->right
->right
|| node
->right
->left
1741 || !tree_int_cst_equal (node
->right
->low
, node
->right
->high
))
1743 if (!node_has_low_bound (node
, index_type
))
1745 probability
= conditional_probability (
1747 subtree_prob
+ default_prob
);
1748 emit_cmp_and_jump_insns (index
,
1751 expand_normal (node
->high
),
1753 LT
, NULL_RTX
, mode
, unsignedp
,
1759 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1763 probability
= conditional_probability (
1764 node
->right
->subtree_prob
,
1765 subtree_prob
+ default_prob
);
1766 /* We cannot process node->right normally
1767 since we haven't ruled out the numbers less than
1768 this node's value. So handle node->right explicitly. */
1769 do_jump_if_equal (mode
, index
,
1772 expand_normal (node
->right
->low
),
1774 jump_target_rtx (node
->right
->code_label
),
1775 unsignedp
, probability
);
1779 else if (node
->right
== 0 && node
->left
!= 0)
1781 /* Just one subtree, on the left. */
1782 if (node
->left
->left
|| node
->left
->right
1783 || !tree_int_cst_equal (node
->left
->low
, node
->left
->high
))
1785 if (!node_has_high_bound (node
, index_type
))
1787 probability
= conditional_probability (
1789 subtree_prob
+ default_prob
);
1790 emit_cmp_and_jump_insns (index
,
1793 expand_normal (node
->high
),
1795 GT
, NULL_RTX
, mode
, unsignedp
,
1801 emit_case_nodes (index
, node
->left
, default_label
,
1802 default_prob
, index_type
);
1806 probability
= conditional_probability (
1807 node
->left
->subtree_prob
,
1808 subtree_prob
+ default_prob
);
1809 /* We cannot process node->left normally
1810 since we haven't ruled out the numbers less than
1811 this node's value. So handle node->left explicitly. */
1812 do_jump_if_equal (mode
, index
,
1815 expand_normal (node
->left
->low
),
1817 jump_target_rtx (node
->left
->code_label
),
1818 unsignedp
, probability
);
1824 /* Node is a range. These cases are very similar to those for a single
1825 value, except that we do not start by testing whether this node
1826 is the one to branch to. */
1828 if (node
->right
!= 0 && node
->left
!= 0)
1830 /* Node has subtrees on both sides.
1831 If the right-hand subtree is bounded,
1832 test for it first, since we can go straight there.
1833 Otherwise, we need to make a branch in the control structure,
1834 then handle the two subtrees. */
1835 tree test_label
= 0;
1837 if (node_is_bounded (node
->right
, index_type
))
1839 /* Right hand node is fully bounded so we can eliminate any
1840 testing and branch directly to the target code. */
1841 probability
= conditional_probability (
1842 node
->right
->subtree_prob
,
1843 subtree_prob
+ default_prob
);
1844 emit_cmp_and_jump_insns (index
,
1847 expand_normal (node
->high
),
1849 GT
, NULL_RTX
, mode
, unsignedp
,
1850 label_rtx (node
->right
->code_label
),
1855 /* Right hand node requires testing.
1856 Branch to a label where we will handle it later. */
1858 test_label
= build_decl (curr_insn_location (),
1859 LABEL_DECL
, NULL_TREE
, void_type_node
);
1860 probability
= conditional_probability (
1861 node
->right
->subtree_prob
+ default_prob
/2,
1862 subtree_prob
+ default_prob
);
1863 emit_cmp_and_jump_insns (index
,
1866 expand_normal (node
->high
),
1868 GT
, NULL_RTX
, mode
, unsignedp
,
1869 label_rtx (test_label
),
1874 /* Value belongs to this node or to the left-hand subtree. */
1876 probability
= conditional_probability (
1878 subtree_prob
+ default_prob
);
1879 emit_cmp_and_jump_insns (index
,
1882 expand_normal (node
->low
),
1884 GE
, NULL_RTX
, mode
, unsignedp
,
1885 label_rtx (node
->code_label
),
1888 /* Handle the left-hand subtree. */
1889 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1891 /* If right node had to be handled later, do that now. */
1895 /* If the left-hand subtree fell through,
1896 don't let it fall into the right-hand subtree. */
1898 emit_jump (default_label
);
1900 expand_label (test_label
);
1901 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1905 else if (node
->right
!= 0 && node
->left
== 0)
1907 /* Deal with values to the left of this node,
1908 if they are possible. */
1909 if (!node_has_low_bound (node
, index_type
))
1911 probability
= conditional_probability (
1913 subtree_prob
+ default_prob
);
1914 emit_cmp_and_jump_insns (index
,
1917 expand_normal (node
->low
),
1919 LT
, NULL_RTX
, mode
, unsignedp
,
1925 /* Value belongs to this node or to the right-hand subtree. */
1927 probability
= conditional_probability (
1929 subtree_prob
+ default_prob
);
1930 emit_cmp_and_jump_insns (index
,
1933 expand_normal (node
->high
),
1935 LE
, NULL_RTX
, mode
, unsignedp
,
1936 label_rtx (node
->code_label
),
1939 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
1942 else if (node
->right
== 0 && node
->left
!= 0)
1944 /* Deal with values to the right of this node,
1945 if they are possible. */
1946 if (!node_has_high_bound (node
, index_type
))
1948 probability
= conditional_probability (
1950 subtree_prob
+ default_prob
);
1951 emit_cmp_and_jump_insns (index
,
1954 expand_normal (node
->high
),
1956 GT
, NULL_RTX
, mode
, unsignedp
,
1962 /* Value belongs to this node or to the left-hand subtree. */
1964 probability
= conditional_probability (
1966 subtree_prob
+ default_prob
);
1967 emit_cmp_and_jump_insns (index
,
1970 expand_normal (node
->low
),
1972 GE
, NULL_RTX
, mode
, unsignedp
,
1973 label_rtx (node
->code_label
),
1976 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
1981 /* Node has no children so we check low and high bounds to remove
1982 redundant tests. Only one of the bounds can exist,
1983 since otherwise this node is bounded--a case tested already. */
1984 int high_bound
= node_has_high_bound (node
, index_type
);
1985 int low_bound
= node_has_low_bound (node
, index_type
);
1987 if (!high_bound
&& low_bound
)
1989 probability
= conditional_probability (
1991 subtree_prob
+ default_prob
);
1992 emit_cmp_and_jump_insns (index
,
1995 expand_normal (node
->high
),
1997 GT
, NULL_RTX
, mode
, unsignedp
,
2002 else if (!low_bound
&& high_bound
)
2004 probability
= conditional_probability (
2006 subtree_prob
+ default_prob
);
2007 emit_cmp_and_jump_insns (index
,
2010 expand_normal (node
->low
),
2012 LT
, NULL_RTX
, mode
, unsignedp
,
2016 else if (!low_bound
&& !high_bound
)
2018 /* Widen LOW and HIGH to the same width as INDEX. */
2019 tree type
= lang_hooks
.types
.type_for_mode (mode
, unsignedp
);
2020 tree low
= build1 (CONVERT_EXPR
, type
, node
->low
);
2021 tree high
= build1 (CONVERT_EXPR
, type
, node
->high
);
2022 rtx low_rtx
, new_index
, new_bound
;
2024 /* Instead of doing two branches, emit one unsigned branch for
2025 (index-low) > (high-low). */
2026 low_rtx
= expand_expr (low
, NULL_RTX
, mode
, EXPAND_NORMAL
);
2027 new_index
= expand_simple_binop (mode
, MINUS
, index
, low_rtx
,
2028 NULL_RTX
, unsignedp
,
2030 new_bound
= expand_expr (fold_build2 (MINUS_EXPR
, type
,
2032 NULL_RTX
, mode
, EXPAND_NORMAL
);
2034 probability
= conditional_probability (
2036 subtree_prob
+ default_prob
);
2037 emit_cmp_and_jump_insns (new_index
, new_bound
, GT
, NULL_RTX
,
2038 mode
, 1, default_label
, probability
);
2041 emit_jump (jump_target_rtx (node
->code_label
));