1 /* Expands front end tree to back end RTL for GCC
2 Copyright (C) 1987-2013 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"
37 #include "insn-config.h"
42 #include "diagnostic-core.h"
45 #include "langhooks.h"
51 #include "alloc-pool.h"
52 #include "pretty-print.h"
55 #include "pointer-set.h"
60 /* Functions and data structures for expanding case statements. */
62 /* Case label structure, used to hold info on labels within case
63 statements. We handle "range" labels; for a single-value label
64 as in C, the high and low limits are the same.
66 We start with a vector of case nodes sorted in ascending order, and
67 the default label as the last element in the vector. Before expanding
68 to RTL, we transform this vector into a list linked via the RIGHT
69 fields in the case_node struct. Nodes with higher case values are
72 Switch statements can be output in three forms. A branch table is
73 used if there are more than a few labels and the labels are dense
74 within the range between the smallest and largest case value. If a
75 branch table is used, no further manipulations are done with the case
78 The alternative to the use of a branch table is to generate a series
79 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
80 and PARENT fields to hold a binary tree. Initially the tree is
81 totally unbalanced, with everything on the right. We balance the tree
82 with nodes on the left having lower case values than the parent
83 and nodes on the right having higher values. We then output the tree
86 For very small, suitable switch statements, we can generate a series
87 of simple bit test and branches instead. */
91 struct case_node
*left
; /* Left son in binary tree */
92 struct case_node
*right
; /* Right son in binary tree; also node chain */
93 struct case_node
*parent
; /* Parent of node in binary tree */
94 tree low
; /* Lowest index value for this label */
95 tree high
; /* Highest index value for this label */
96 tree code_label
; /* Label to jump to when node matches */
97 int prob
; /* Probability of taking this case. */
98 /* Probability of reaching subtree rooted at this node */
102 typedef struct case_node case_node
;
103 typedef struct case_node
*case_node_ptr
;
105 extern basic_block
label_to_block_fn (struct function
*, tree
);
107 static int n_occurrences (int, const char *);
108 static bool tree_conflicts_with_clobbers_p (tree
, HARD_REG_SET
*);
109 static bool check_operand_nalternatives (tree
, tree
);
110 static bool check_unique_operand_names (tree
, tree
, tree
);
111 static char *resolve_operand_name_1 (char *, tree
, tree
, tree
);
112 static void expand_null_return_1 (void);
113 static void expand_value_return (rtx
);
114 static void balance_case_nodes (case_node_ptr
*, case_node_ptr
);
115 static int node_has_low_bound (case_node_ptr
, tree
);
116 static int node_has_high_bound (case_node_ptr
, tree
);
117 static int node_is_bounded (case_node_ptr
, tree
);
118 static void emit_case_nodes (rtx
, case_node_ptr
, rtx
, int, tree
);
120 /* Return the rtx-label that corresponds to a LABEL_DECL,
121 creating it if necessary. */
124 label_rtx (tree label
)
126 gcc_assert (TREE_CODE (label
) == LABEL_DECL
);
128 if (!DECL_RTL_SET_P (label
))
130 rtx r
= gen_label_rtx ();
131 SET_DECL_RTL (label
, r
);
132 if (FORCED_LABEL (label
) || DECL_NONLOCAL (label
))
133 LABEL_PRESERVE_P (r
) = 1;
136 return DECL_RTL (label
);
139 /* As above, but also put it on the forced-reference list of the
140 function that contains it. */
142 force_label_rtx (tree label
)
144 rtx ref
= label_rtx (label
);
145 tree function
= decl_function_context (label
);
147 gcc_assert (function
);
149 forced_labels
= gen_rtx_EXPR_LIST (VOIDmode
, ref
, forced_labels
);
153 /* Add an unconditional jump to LABEL as the next sequential instruction. */
156 emit_jump (rtx label
)
158 do_pending_stack_adjust ();
159 emit_jump_insn (gen_jump (label
));
163 /* Emit code to jump to the address
164 specified by the pointer expression EXP. */
167 expand_computed_goto (tree exp
)
169 rtx x
= expand_normal (exp
);
171 x
= convert_memory_address (Pmode
, x
);
173 do_pending_stack_adjust ();
174 emit_indirect_jump (x
);
177 /* Handle goto statements and the labels that they can go to. */
179 /* Specify the location in the RTL code of a label LABEL,
180 which is a LABEL_DECL tree node.
182 This is used for the kind of label that the user can jump to with a
183 goto statement, and for alternatives of a switch or case statement.
184 RTL labels generated for loops and conditionals don't go through here;
185 they are generated directly at the RTL level, by other functions below.
187 Note that this has nothing to do with defining label *names*.
188 Languages vary in how they do that and what that even means. */
191 expand_label (tree label
)
193 rtx label_r
= label_rtx (label
);
195 do_pending_stack_adjust ();
196 emit_label (label_r
);
197 if (DECL_NAME (label
))
198 LABEL_NAME (DECL_RTL (label
)) = IDENTIFIER_POINTER (DECL_NAME (label
));
200 if (DECL_NONLOCAL (label
))
202 expand_builtin_setjmp_receiver (NULL
);
203 nonlocal_goto_handler_labels
204 = gen_rtx_EXPR_LIST (VOIDmode
, label_r
,
205 nonlocal_goto_handler_labels
);
208 if (FORCED_LABEL (label
))
209 forced_labels
= gen_rtx_EXPR_LIST (VOIDmode
, label_r
, forced_labels
);
211 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
212 maybe_set_first_label_num (label_r
);
215 /* Generate RTL code for a `goto' statement with target label LABEL.
216 LABEL should be a LABEL_DECL tree node that was or will later be
217 defined with `expand_label'. */
220 expand_goto (tree label
)
222 #ifdef ENABLE_CHECKING
223 /* Check for a nonlocal goto to a containing function. Should have
224 gotten translated to __builtin_nonlocal_goto. */
225 tree context
= decl_function_context (label
);
226 gcc_assert (!context
|| context
== current_function_decl
);
229 emit_jump (label_rtx (label
));
232 /* Return the number of times character C occurs in string S. */
234 n_occurrences (int c
, const char *s
)
242 /* Generate RTL for an asm statement (explicit assembler code).
243 STRING is a STRING_CST node containing the assembler code text,
244 or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the
245 insn is volatile; don't optimize it. */
248 expand_asm_loc (tree string
, int vol
, location_t locus
)
252 if (TREE_CODE (string
) == ADDR_EXPR
)
253 string
= TREE_OPERAND (string
, 0);
255 body
= gen_rtx_ASM_INPUT_loc (VOIDmode
,
256 ggc_strdup (TREE_STRING_POINTER (string
)),
259 MEM_VOLATILE_P (body
) = vol
;
264 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
265 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
266 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
267 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
268 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
269 constraint allows the use of a register operand. And, *IS_INOUT
270 will be true if the operand is read-write, i.e., if it is used as
271 an input as well as an output. If *CONSTRAINT_P is not in
272 canonical form, it will be made canonical. (Note that `+' will be
273 replaced with `=' as part of this process.)
275 Returns TRUE if all went well; FALSE if an error occurred. */
278 parse_output_constraint (const char **constraint_p
, int operand_num
,
279 int ninputs
, int noutputs
, bool *allows_mem
,
280 bool *allows_reg
, bool *is_inout
)
282 const char *constraint
= *constraint_p
;
285 /* Assume the constraint doesn't allow the use of either a register
290 /* Allow the `=' or `+' to not be at the beginning of the string,
291 since it wasn't explicitly documented that way, and there is a
292 large body of code that puts it last. Swap the character to
293 the front, so as not to uglify any place else. */
294 p
= strchr (constraint
, '=');
296 p
= strchr (constraint
, '+');
298 /* If the string doesn't contain an `=', issue an error
302 error ("output operand constraint lacks %<=%>");
306 /* If the constraint begins with `+', then the operand is both read
307 from and written to. */
308 *is_inout
= (*p
== '+');
310 /* Canonicalize the output constraint so that it begins with `='. */
311 if (p
!= constraint
|| *is_inout
)
314 size_t c_len
= strlen (constraint
);
317 warning (0, "output constraint %qc for operand %d "
318 "is not at the beginning",
321 /* Make a copy of the constraint. */
322 buf
= XALLOCAVEC (char, c_len
+ 1);
323 strcpy (buf
, constraint
);
324 /* Swap the first character and the `=' or `+'. */
325 buf
[p
- constraint
] = buf
[0];
326 /* Make sure the first character is an `='. (Until we do this,
327 it might be a `+'.) */
329 /* Replace the constraint with the canonicalized string. */
330 *constraint_p
= ggc_alloc_string (buf
, c_len
);
331 constraint
= *constraint_p
;
334 /* Loop through the constraint string. */
335 for (p
= constraint
+ 1; *p
; p
+= CONSTRAINT_LEN (*p
, p
))
340 error ("operand constraint contains incorrectly positioned "
345 if (operand_num
+ 1 == ninputs
+ noutputs
)
347 error ("%<%%%> constraint used with last operand");
352 case 'V': case TARGET_MEM_CONSTRAINT
: case 'o':
356 case '?': case '!': case '*': case '&': case '#':
357 case 'E': case 'F': case 'G': case 'H':
358 case 's': case 'i': case 'n':
359 case 'I': case 'J': case 'K': case 'L': case 'M':
360 case 'N': case 'O': case 'P': case ',':
363 case '0': case '1': case '2': case '3': case '4':
364 case '5': case '6': case '7': case '8': case '9':
366 error ("matching constraint not valid in output operand");
370 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
371 excepting those that expand_call created. So match memory
388 if (REG_CLASS_FROM_CONSTRAINT (*p
, p
) != NO_REGS
)
390 #ifdef EXTRA_CONSTRAINT_STR
391 else if (EXTRA_ADDRESS_CONSTRAINT (*p
, p
))
393 else if (EXTRA_MEMORY_CONSTRAINT (*p
, p
))
397 /* Otherwise we can't assume anything about the nature of
398 the constraint except that it isn't purely registers.
399 Treat it like "g" and hope for the best. */
410 /* Similar, but for input constraints. */
413 parse_input_constraint (const char **constraint_p
, int input_num
,
414 int ninputs
, int noutputs
, int ninout
,
415 const char * const * constraints
,
416 bool *allows_mem
, bool *allows_reg
)
418 const char *constraint
= *constraint_p
;
419 const char *orig_constraint
= constraint
;
420 size_t c_len
= strlen (constraint
);
422 bool saw_match
= false;
424 /* Assume the constraint doesn't allow the use of either
425 a register or memory. */
429 /* Make sure constraint has neither `=', `+', nor '&'. */
431 for (j
= 0; j
< c_len
; j
+= CONSTRAINT_LEN (constraint
[j
], constraint
+j
))
432 switch (constraint
[j
])
434 case '+': case '=': case '&':
435 if (constraint
== orig_constraint
)
437 error ("input operand constraint contains %qc", constraint
[j
]);
443 if (constraint
== orig_constraint
444 && input_num
+ 1 == ninputs
- ninout
)
446 error ("%<%%%> constraint used with last operand");
451 case 'V': case TARGET_MEM_CONSTRAINT
: case 'o':
456 case '?': case '!': case '*': case '#':
457 case 'E': case 'F': case 'G': case 'H':
458 case 's': case 'i': case 'n':
459 case 'I': case 'J': case 'K': case 'L': case 'M':
460 case 'N': case 'O': case 'P': case ',':
463 /* Whether or not a numeric constraint allows a register is
464 decided by the matching constraint, and so there is no need
465 to do anything special with them. We must handle them in
466 the default case, so that we don't unnecessarily force
467 operands to memory. */
468 case '0': case '1': case '2': case '3': case '4':
469 case '5': case '6': case '7': case '8': case '9':
476 match
= strtoul (constraint
+ j
, &end
, 10);
477 if (match
>= (unsigned long) noutputs
)
479 error ("matching constraint references invalid operand number");
483 /* Try and find the real constraint for this dup. Only do this
484 if the matching constraint is the only alternative. */
486 && (j
== 0 || (j
== 1 && constraint
[0] == '%')))
488 constraint
= constraints
[match
];
489 *constraint_p
= constraint
;
490 c_len
= strlen (constraint
);
492 /* ??? At the end of the loop, we will skip the first part of
493 the matched constraint. This assumes not only that the
494 other constraint is an output constraint, but also that
495 the '=' or '+' come first. */
499 j
= end
- constraint
;
500 /* Anticipate increment at end of loop. */
515 if (! ISALPHA (constraint
[j
]))
517 error ("invalid punctuation %qc in constraint", constraint
[j
]);
520 if (REG_CLASS_FROM_CONSTRAINT (constraint
[j
], constraint
+ j
)
523 #ifdef EXTRA_CONSTRAINT_STR
524 else if (EXTRA_ADDRESS_CONSTRAINT (constraint
[j
], constraint
+ j
))
526 else if (EXTRA_MEMORY_CONSTRAINT (constraint
[j
], constraint
+ j
))
530 /* Otherwise we can't assume anything about the nature of
531 the constraint except that it isn't purely registers.
532 Treat it like "g" and hope for the best. */
540 if (saw_match
&& !*allows_reg
)
541 warning (0, "matching constraint does not allow a register");
546 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
547 can be an asm-declared register. Called via walk_tree. */
550 decl_overlaps_hard_reg_set_p (tree
*declp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
554 const HARD_REG_SET
*const regs
= (const HARD_REG_SET
*) data
;
556 if (TREE_CODE (decl
) == VAR_DECL
)
558 if (DECL_HARD_REGISTER (decl
)
559 && REG_P (DECL_RTL (decl
))
560 && REGNO (DECL_RTL (decl
)) < FIRST_PSEUDO_REGISTER
)
562 rtx reg
= DECL_RTL (decl
);
564 if (overlaps_hard_reg_set_p (*regs
, GET_MODE (reg
), REGNO (reg
)))
569 else if (TYPE_P (decl
) || TREE_CODE (decl
) == PARM_DECL
)
574 /* If there is an overlap between *REGS and DECL, return the first overlap
577 tree_overlaps_hard_reg_set (tree decl
, HARD_REG_SET
*regs
)
579 return walk_tree (&decl
, decl_overlaps_hard_reg_set_p
, regs
, NULL
);
582 /* Check for overlap between registers marked in CLOBBERED_REGS and
583 anything inappropriate in T. Emit error and return the register
584 variable definition for error, NULL_TREE for ok. */
587 tree_conflicts_with_clobbers_p (tree t
, HARD_REG_SET
*clobbered_regs
)
589 /* Conflicts between asm-declared register variables and the clobber
590 list are not allowed. */
591 tree overlap
= tree_overlaps_hard_reg_set (t
, clobbered_regs
);
595 error ("asm-specifier for variable %qE conflicts with asm clobber list",
596 DECL_NAME (overlap
));
598 /* Reset registerness to stop multiple errors emitted for a single
600 DECL_REGISTER (overlap
) = 0;
607 /* Generate RTL for an asm statement with arguments.
608 STRING is the instruction template.
609 OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs.
610 Each output or input has an expression in the TREE_VALUE and
611 a tree list in TREE_PURPOSE which in turn contains a constraint
612 name in TREE_VALUE (or NULL_TREE) and a constraint string
614 CLOBBERS is a list of STRING_CST nodes each naming a hard register
615 that is clobbered by this insn.
617 Not all kinds of lvalue that may appear in OUTPUTS can be stored directly.
618 Some elements of OUTPUTS may be replaced with trees representing temporary
619 values. The caller should copy those temporary values to the originally
622 VOL nonzero means the insn is volatile; don't optimize it. */
625 expand_asm_operands (tree string
, tree outputs
, tree inputs
,
626 tree clobbers
, tree labels
, int vol
, location_t locus
)
628 rtvec argvec
, constraintvec
, labelvec
;
630 int ninputs
= list_length (inputs
);
631 int noutputs
= list_length (outputs
);
632 int nlabels
= list_length (labels
);
635 HARD_REG_SET clobbered_regs
;
636 int clobber_conflict_found
= 0;
640 /* Vector of RTX's of evaluated output operands. */
641 rtx
*output_rtx
= XALLOCAVEC (rtx
, noutputs
);
642 int *inout_opnum
= XALLOCAVEC (int, noutputs
);
643 rtx
*real_output_rtx
= XALLOCAVEC (rtx
, noutputs
);
644 enum machine_mode
*inout_mode
= XALLOCAVEC (enum machine_mode
, noutputs
);
645 const char **constraints
= XALLOCAVEC (const char *, noutputs
+ ninputs
);
646 int old_generating_concat_p
= generating_concat_p
;
648 /* An ASM with no outputs needs to be treated as volatile, for now. */
652 if (! check_operand_nalternatives (outputs
, inputs
))
655 string
= resolve_asm_operand_names (string
, outputs
, inputs
, labels
);
657 /* Collect constraints. */
659 for (t
= outputs
; t
; t
= TREE_CHAIN (t
), i
++)
660 constraints
[i
] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
661 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), i
++)
662 constraints
[i
] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
664 /* Sometimes we wish to automatically clobber registers across an asm.
665 Case in point is when the i386 backend moved from cc0 to a hard reg --
666 maintaining source-level compatibility means automatically clobbering
667 the flags register. */
668 clobbers
= targetm
.md_asm_clobbers (outputs
, inputs
, clobbers
);
670 /* Count the number of meaningful clobbered registers, ignoring what
671 we would ignore later. */
673 CLEAR_HARD_REG_SET (clobbered_regs
);
674 for (tail
= clobbers
; tail
; tail
= TREE_CHAIN (tail
))
679 if (TREE_VALUE (tail
) == error_mark_node
)
681 regname
= TREE_STRING_POINTER (TREE_VALUE (tail
));
683 i
= decode_reg_name_and_count (regname
, &nregs
);
687 error ("unknown register name %qs in %<asm%>", regname
);
689 /* Mark clobbered registers. */
694 for (reg
= i
; reg
< i
+ nregs
; reg
++)
698 /* Clobbering the PIC register is an error. */
699 if (reg
== (int) PIC_OFFSET_TABLE_REGNUM
)
701 error ("PIC register clobbered by %qs in %<asm%>", regname
);
705 SET_HARD_REG_BIT (clobbered_regs
, reg
);
710 /* First pass over inputs and outputs checks validity and sets
711 mark_addressable if needed. */
714 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
716 tree val
= TREE_VALUE (tail
);
717 tree type
= TREE_TYPE (val
);
718 const char *constraint
;
723 /* If there's an erroneous arg, emit no insn. */
724 if (type
== error_mark_node
)
727 /* Try to parse the output constraint. If that fails, there's
728 no point in going further. */
729 constraint
= constraints
[i
];
730 if (!parse_output_constraint (&constraint
, i
, ninputs
, noutputs
,
731 &allows_mem
, &allows_reg
, &is_inout
))
738 && REG_P (DECL_RTL (val
))
739 && GET_MODE (DECL_RTL (val
)) != TYPE_MODE (type
))))
740 mark_addressable (val
);
747 if (ninputs
+ noutputs
> MAX_RECOG_OPERANDS
)
749 error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS
);
753 for (i
= 0, tail
= inputs
; tail
; i
++, tail
= TREE_CHAIN (tail
))
755 bool allows_reg
, allows_mem
;
756 const char *constraint
;
758 /* If there's an erroneous arg, emit no insn, because the ASM_INPUT
759 would get VOIDmode and that could cause a crash in reload. */
760 if (TREE_TYPE (TREE_VALUE (tail
)) == error_mark_node
)
763 constraint
= constraints
[i
+ noutputs
];
764 if (! parse_input_constraint (&constraint
, i
, ninputs
, noutputs
, ninout
,
765 constraints
, &allows_mem
, &allows_reg
))
768 if (! allows_reg
&& allows_mem
)
769 mark_addressable (TREE_VALUE (tail
));
772 /* Second pass evaluates arguments. */
774 /* Make sure stack is consistent for asm goto. */
776 do_pending_stack_adjust ();
779 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
781 tree val
= TREE_VALUE (tail
);
782 tree type
= TREE_TYPE (val
);
789 ok
= parse_output_constraint (&constraints
[i
], i
, ninputs
,
790 noutputs
, &allows_mem
, &allows_reg
,
794 /* If an output operand is not a decl or indirect ref and our constraint
795 allows a register, make a temporary to act as an intermediate.
796 Make the asm insn write into that, then our caller will copy it to
797 the real output operand. Likewise for promoted variables. */
799 generating_concat_p
= 0;
801 real_output_rtx
[i
] = NULL_RTX
;
802 if ((TREE_CODE (val
) == INDIRECT_REF
805 && (allows_mem
|| REG_P (DECL_RTL (val
)))
806 && ! (REG_P (DECL_RTL (val
))
807 && GET_MODE (DECL_RTL (val
)) != TYPE_MODE (type
)))
811 op
= expand_expr (val
, NULL_RTX
, VOIDmode
,
812 !allows_reg
? EXPAND_MEMORY
813 : !is_inout
? EXPAND_WRITE
816 op
= validize_mem (op
);
818 if (! allows_reg
&& !MEM_P (op
))
819 error ("output number %d not directly addressable", i
);
820 if ((! allows_mem
&& MEM_P (op
))
821 || GET_CODE (op
) == CONCAT
)
823 real_output_rtx
[i
] = op
;
824 op
= gen_reg_rtx (GET_MODE (op
));
826 emit_move_insn (op
, real_output_rtx
[i
]);
831 op
= assign_temp (type
, 0, 1);
832 op
= validize_mem (op
);
833 if (!MEM_P (op
) && TREE_CODE (TREE_VALUE (tail
)) == SSA_NAME
)
834 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (TREE_VALUE (tail
)), op
);
835 TREE_VALUE (tail
) = make_tree (type
, op
);
839 generating_concat_p
= old_generating_concat_p
;
843 inout_mode
[ninout
] = TYPE_MODE (type
);
844 inout_opnum
[ninout
++] = i
;
847 if (tree_conflicts_with_clobbers_p (val
, &clobbered_regs
))
848 clobber_conflict_found
= 1;
851 /* Make vectors for the expression-rtx, constraint strings,
852 and named operands. */
854 argvec
= rtvec_alloc (ninputs
);
855 constraintvec
= rtvec_alloc (ninputs
);
856 labelvec
= rtvec_alloc (nlabels
);
858 body
= gen_rtx_ASM_OPERANDS ((noutputs
== 0 ? VOIDmode
859 : GET_MODE (output_rtx
[0])),
860 ggc_strdup (TREE_STRING_POINTER (string
)),
861 empty_string
, 0, argvec
, constraintvec
,
864 MEM_VOLATILE_P (body
) = vol
;
866 /* Eval the inputs and put them into ARGVEC.
867 Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */
869 for (i
= 0, tail
= inputs
; tail
; tail
= TREE_CHAIN (tail
), ++i
)
871 bool allows_reg
, allows_mem
;
872 const char *constraint
;
877 constraint
= constraints
[i
+ noutputs
];
878 ok
= parse_input_constraint (&constraint
, i
, ninputs
, noutputs
, ninout
,
879 constraints
, &allows_mem
, &allows_reg
);
882 generating_concat_p
= 0;
884 val
= TREE_VALUE (tail
);
885 type
= TREE_TYPE (val
);
886 /* EXPAND_INITIALIZER will not generate code for valid initializer
887 constants, but will still generate code for other types of operand.
888 This is the behavior we want for constant constraints. */
889 op
= expand_expr (val
, NULL_RTX
, VOIDmode
,
890 allows_reg
? EXPAND_NORMAL
891 : allows_mem
? EXPAND_MEMORY
892 : EXPAND_INITIALIZER
);
894 /* Never pass a CONCAT to an ASM. */
895 if (GET_CODE (op
) == CONCAT
)
896 op
= force_reg (GET_MODE (op
), op
);
898 op
= validize_mem (op
);
900 if (asm_operand_ok (op
, constraint
, NULL
) <= 0)
902 if (allows_reg
&& TYPE_MODE (type
) != BLKmode
)
903 op
= force_reg (TYPE_MODE (type
), op
);
904 else if (!allows_mem
)
905 warning (0, "asm operand %d probably doesn%'t match constraints",
909 /* We won't recognize either volatile memory or memory
910 with a queued address as available a memory_operand
911 at this point. Ignore it: clearly this *is* a memory. */
917 generating_concat_p
= old_generating_concat_p
;
918 ASM_OPERANDS_INPUT (body
, i
) = op
;
920 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body
, i
)
921 = gen_rtx_ASM_INPUT (TYPE_MODE (type
),
922 ggc_strdup (constraints
[i
+ noutputs
]));
924 if (tree_conflicts_with_clobbers_p (val
, &clobbered_regs
))
925 clobber_conflict_found
= 1;
928 /* Protect all the operands from the queue now that they have all been
931 generating_concat_p
= 0;
933 /* For in-out operands, copy output rtx to input rtx. */
934 for (i
= 0; i
< ninout
; i
++)
936 int j
= inout_opnum
[i
];
939 ASM_OPERANDS_INPUT (body
, ninputs
- ninout
+ i
)
942 sprintf (buffer
, "%d", j
);
943 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body
, ninputs
- ninout
+ i
)
944 = gen_rtx_ASM_INPUT (inout_mode
[i
], ggc_strdup (buffer
));
947 /* Copy labels to the vector. */
948 for (i
= 0, tail
= labels
; i
< nlabels
; ++i
, tail
= TREE_CHAIN (tail
))
949 ASM_OPERANDS_LABEL (body
, i
)
950 = gen_rtx_LABEL_REF (Pmode
, label_rtx (TREE_VALUE (tail
)));
952 generating_concat_p
= old_generating_concat_p
;
954 /* Now, for each output, construct an rtx
955 (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER
956 ARGVEC CONSTRAINTS OPNAMES))
957 If there is more than one, put them inside a PARALLEL. */
959 if (nlabels
> 0 && nclobbers
== 0)
961 gcc_assert (noutputs
== 0);
962 emit_jump_insn (body
);
964 else if (noutputs
== 0 && nclobbers
== 0)
966 /* No output operands: put in a raw ASM_OPERANDS rtx. */
969 else if (noutputs
== 1 && nclobbers
== 0)
971 ASM_OPERANDS_OUTPUT_CONSTRAINT (body
) = ggc_strdup (constraints
[0]);
972 emit_insn (gen_rtx_SET (VOIDmode
, output_rtx
[0], body
));
982 body
= gen_rtx_PARALLEL (VOIDmode
, rtvec_alloc (num
+ nclobbers
));
984 /* For each output operand, store a SET. */
985 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
988 = gen_rtx_SET (VOIDmode
,
991 (GET_MODE (output_rtx
[i
]),
992 ggc_strdup (TREE_STRING_POINTER (string
)),
993 ggc_strdup (constraints
[i
]),
994 i
, argvec
, constraintvec
, labelvec
, locus
));
996 MEM_VOLATILE_P (SET_SRC (XVECEXP (body
, 0, i
))) = vol
;
999 /* If there are no outputs (but there are some clobbers)
1000 store the bare ASM_OPERANDS into the PARALLEL. */
1003 XVECEXP (body
, 0, i
++) = obody
;
1005 /* Store (clobber REG) for each clobbered register specified. */
1007 for (tail
= clobbers
; tail
; tail
= TREE_CHAIN (tail
))
1009 const char *regname
= TREE_STRING_POINTER (TREE_VALUE (tail
));
1011 int j
= decode_reg_name_and_count (regname
, &nregs
);
1016 if (j
== -3) /* `cc', which is not a register */
1019 if (j
== -4) /* `memory', don't cache memory across asm */
1021 XVECEXP (body
, 0, i
++)
1022 = gen_rtx_CLOBBER (VOIDmode
,
1025 gen_rtx_SCRATCH (VOIDmode
)));
1029 /* Ignore unknown register, error already signaled. */
1033 for (reg
= j
; reg
< j
+ nregs
; reg
++)
1035 /* Use QImode since that's guaranteed to clobber just
1037 clobbered_reg
= gen_rtx_REG (QImode
, reg
);
1039 /* Do sanity check for overlap between clobbers and
1040 respectively input and outputs that hasn't been
1041 handled. Such overlap should have been detected and
1043 if (!clobber_conflict_found
)
1047 /* We test the old body (obody) contents to avoid
1048 tripping over the under-construction body. */
1049 for (opno
= 0; opno
< noutputs
; opno
++)
1050 if (reg_overlap_mentioned_p (clobbered_reg
,
1053 ("asm clobber conflict with output operand");
1055 for (opno
= 0; opno
< ninputs
- ninout
; opno
++)
1056 if (reg_overlap_mentioned_p (clobbered_reg
,
1057 ASM_OPERANDS_INPUT (obody
,
1060 ("asm clobber conflict with input operand");
1063 XVECEXP (body
, 0, i
++)
1064 = gen_rtx_CLOBBER (VOIDmode
, clobbered_reg
);
1069 emit_jump_insn (body
);
1074 /* For any outputs that needed reloading into registers, spill them
1075 back to where they belong. */
1076 for (i
= 0; i
< noutputs
; ++i
)
1077 if (real_output_rtx
[i
])
1078 emit_move_insn (real_output_rtx
[i
], output_rtx
[i
]);
1080 crtl
->has_asm_statement
= 1;
1081 coverage_has_asm_stmt ();
1086 expand_asm_stmt (gimple stmt
)
1089 tree outputs
, tail
, t
;
1093 tree str
, out
, in
, cl
, labels
;
1094 location_t locus
= gimple_location (stmt
);
1096 /* Meh... convert the gimple asm operands into real tree lists.
1097 Eventually we should make all routines work on the vectors instead
1098 of relying on TREE_CHAIN. */
1100 n
= gimple_asm_noutputs (stmt
);
1103 t
= out
= gimple_asm_output_op (stmt
, 0);
1104 for (i
= 1; i
< n
; i
++)
1105 t
= TREE_CHAIN (t
) = gimple_asm_output_op (stmt
, i
);
1109 n
= gimple_asm_ninputs (stmt
);
1112 t
= in
= gimple_asm_input_op (stmt
, 0);
1113 for (i
= 1; i
< n
; i
++)
1114 t
= TREE_CHAIN (t
) = gimple_asm_input_op (stmt
, i
);
1118 n
= gimple_asm_nclobbers (stmt
);
1121 t
= cl
= gimple_asm_clobber_op (stmt
, 0);
1122 for (i
= 1; i
< n
; i
++)
1123 t
= TREE_CHAIN (t
) = gimple_asm_clobber_op (stmt
, i
);
1127 n
= gimple_asm_nlabels (stmt
);
1130 t
= labels
= gimple_asm_label_op (stmt
, 0);
1131 for (i
= 1; i
< n
; i
++)
1132 t
= TREE_CHAIN (t
) = gimple_asm_label_op (stmt
, i
);
1135 s
= gimple_asm_string (stmt
);
1136 str
= build_string (strlen (s
), s
);
1138 if (gimple_asm_input_p (stmt
))
1140 expand_asm_loc (str
, gimple_asm_volatile_p (stmt
), locus
);
1145 noutputs
= gimple_asm_noutputs (stmt
);
1146 /* o[I] is the place that output number I should be written. */
1147 o
= (tree
*) alloca (noutputs
* sizeof (tree
));
1149 /* Record the contents of OUTPUTS before it is modified. */
1150 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
1151 o
[i
] = TREE_VALUE (tail
);
1153 /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of
1154 OUTPUTS some trees for where the values were actually stored. */
1155 expand_asm_operands (str
, outputs
, in
, cl
, labels
,
1156 gimple_asm_volatile_p (stmt
), locus
);
1158 /* Copy all the intermediate outputs into the specified outputs. */
1159 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
1161 if (o
[i
] != TREE_VALUE (tail
))
1163 expand_assignment (o
[i
], TREE_VALUE (tail
), false);
1166 /* Restore the original value so that it's correct the next
1167 time we expand this function. */
1168 TREE_VALUE (tail
) = o
[i
];
1173 /* A subroutine of expand_asm_operands. Check that all operands have
1174 the same number of alternatives. Return true if so. */
1177 check_operand_nalternatives (tree outputs
, tree inputs
)
1179 if (outputs
|| inputs
)
1181 tree tmp
= TREE_PURPOSE (outputs
? outputs
: inputs
);
1183 = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp
)));
1186 if (nalternatives
+ 1 > MAX_RECOG_ALTERNATIVES
)
1188 error ("too many alternatives in %<asm%>");
1195 const char *constraint
1196 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp
)));
1198 if (n_occurrences (',', constraint
) != nalternatives
)
1200 error ("operand constraints for %<asm%> differ "
1201 "in number of alternatives");
1205 if (TREE_CHAIN (tmp
))
1206 tmp
= TREE_CHAIN (tmp
);
1208 tmp
= next
, next
= 0;
1215 /* A subroutine of expand_asm_operands. Check that all operand names
1216 are unique. Return true if so. We rely on the fact that these names
1217 are identifiers, and so have been canonicalized by get_identifier,
1218 so all we need are pointer comparisons. */
1221 check_unique_operand_names (tree outputs
, tree inputs
, tree labels
)
1223 tree i
, j
, i_name
= NULL_TREE
;
1225 for (i
= outputs
; i
; i
= TREE_CHAIN (i
))
1227 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
1231 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
1232 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
1236 for (i
= inputs
; i
; i
= TREE_CHAIN (i
))
1238 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
1242 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
1243 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
1245 for (j
= outputs
; j
; j
= TREE_CHAIN (j
))
1246 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
1250 for (i
= labels
; i
; i
= TREE_CHAIN (i
))
1252 i_name
= TREE_PURPOSE (i
);
1256 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
1257 if (simple_cst_equal (i_name
, TREE_PURPOSE (j
)))
1259 for (j
= inputs
; j
; j
= TREE_CHAIN (j
))
1260 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
1267 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name
));
1271 /* A subroutine of expand_asm_operands. Resolve the names of the operands
1272 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
1273 STRING and in the constraints to those numbers. */
1276 resolve_asm_operand_names (tree string
, tree outputs
, tree inputs
, tree labels
)
1283 check_unique_operand_names (outputs
, inputs
, labels
);
1285 /* Substitute [<name>] in input constraint strings. There should be no
1286 named operands in output constraints. */
1287 for (t
= inputs
; t
; t
= TREE_CHAIN (t
))
1289 c
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
1290 if (strchr (c
, '[') != NULL
)
1292 p
= buffer
= xstrdup (c
);
1293 while ((p
= strchr (p
, '[')) != NULL
)
1294 p
= resolve_operand_name_1 (p
, outputs
, inputs
, NULL
);
1295 TREE_VALUE (TREE_PURPOSE (t
))
1296 = build_string (strlen (buffer
), buffer
);
1301 /* Now check for any needed substitutions in the template. */
1302 c
= TREE_STRING_POINTER (string
);
1303 while ((c
= strchr (c
, '%')) != NULL
)
1307 else if (ISALPHA (c
[1]) && c
[2] == '[')
1311 c
+= 1 + (c
[1] == '%');
1318 /* OK, we need to make a copy so we can perform the substitutions.
1319 Assume that we will not need extra space--we get to remove '['
1320 and ']', which means we cannot have a problem until we have more
1321 than 999 operands. */
1322 buffer
= xstrdup (TREE_STRING_POINTER (string
));
1323 p
= buffer
+ (c
- TREE_STRING_POINTER (string
));
1325 while ((p
= strchr (p
, '%')) != NULL
)
1329 else if (ISALPHA (p
[1]) && p
[2] == '[')
1333 p
+= 1 + (p
[1] == '%');
1337 p
= resolve_operand_name_1 (p
, outputs
, inputs
, labels
);
1340 string
= build_string (strlen (buffer
), buffer
);
1347 /* A subroutine of resolve_operand_names. P points to the '[' for a
1348 potential named operand of the form [<name>]. In place, replace
1349 the name and brackets with a number. Return a pointer to the
1350 balance of the string after substitution. */
1353 resolve_operand_name_1 (char *p
, tree outputs
, tree inputs
, tree labels
)
1359 /* Collect the operand name. */
1360 q
= strchr (++p
, ']');
1363 error ("missing close brace for named operand");
1364 return strchr (p
, '\0');
1368 /* Resolve the name to a number. */
1369 for (op
= 0, t
= outputs
; t
; t
= TREE_CHAIN (t
), op
++)
1371 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
1372 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
1375 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), op
++)
1377 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
1378 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
1381 for (t
= labels
; t
; t
= TREE_CHAIN (t
), op
++)
1383 tree name
= TREE_PURPOSE (t
);
1384 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
1388 error ("undefined named operand %qs", identifier_to_locale (p
));
1392 /* Replace the name with the number. Unfortunately, not all libraries
1393 get the return value of sprintf correct, so search for the end of the
1394 generated string by hand. */
1395 sprintf (--p
, "%d", op
);
1396 p
= strchr (p
, '\0');
1398 /* Verify the no extra buffer space assumption. */
1399 gcc_assert (p
<= q
);
1401 /* Shift the rest of the buffer down to fill the gap. */
1402 memmove (p
, q
+ 1, strlen (q
+ 1) + 1);
1407 /* Generate RTL to return from the current function, with no value.
1408 (That is, we do not do anything about returning any value.) */
1411 expand_null_return (void)
1413 /* If this function was declared to return a value, but we
1414 didn't, clobber the return registers so that they are not
1415 propagated live to the rest of the function. */
1416 clobber_return_register ();
1418 expand_null_return_1 ();
1421 /* Generate RTL to return directly from the current function.
1422 (That is, we bypass any return value.) */
1425 expand_naked_return (void)
1429 clear_pending_stack_adjust ();
1430 do_pending_stack_adjust ();
1432 end_label
= naked_return_label
;
1434 end_label
= naked_return_label
= gen_label_rtx ();
1436 emit_jump (end_label
);
1439 /* Generate RTL to return from the current function, with value VAL. */
1442 expand_value_return (rtx val
)
1444 /* Copy the value to the return location unless it's already there. */
1446 tree decl
= DECL_RESULT (current_function_decl
);
1447 rtx return_reg
= DECL_RTL (decl
);
1448 if (return_reg
!= val
)
1450 tree funtype
= TREE_TYPE (current_function_decl
);
1451 tree type
= TREE_TYPE (decl
);
1452 int unsignedp
= TYPE_UNSIGNED (type
);
1453 enum machine_mode old_mode
= DECL_MODE (decl
);
1454 enum machine_mode mode
;
1455 if (DECL_BY_REFERENCE (decl
))
1456 mode
= promote_function_mode (type
, old_mode
, &unsignedp
, funtype
, 2);
1458 mode
= promote_function_mode (type
, old_mode
, &unsignedp
, funtype
, 1);
1460 if (mode
!= old_mode
)
1461 val
= convert_modes (mode
, old_mode
, val
, unsignedp
);
1463 if (GET_CODE (return_reg
) == PARALLEL
)
1464 emit_group_load (return_reg
, val
, type
, int_size_in_bytes (type
));
1466 emit_move_insn (return_reg
, val
);
1469 expand_null_return_1 ();
1472 /* Output a return with no value. */
1475 expand_null_return_1 (void)
1477 clear_pending_stack_adjust ();
1478 do_pending_stack_adjust ();
1479 emit_jump (return_label
);
1482 /* Generate RTL to evaluate the expression RETVAL and return it
1483 from the current function. */
1486 expand_return (tree retval
)
1492 /* If function wants no value, give it none. */
1493 if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl
))) == VOID_TYPE
)
1495 expand_normal (retval
);
1496 expand_null_return ();
1500 if (retval
== error_mark_node
)
1502 /* Treat this like a return of no value from a function that
1504 expand_null_return ();
1507 else if ((TREE_CODE (retval
) == MODIFY_EXPR
1508 || TREE_CODE (retval
) == INIT_EXPR
)
1509 && TREE_CODE (TREE_OPERAND (retval
, 0)) == RESULT_DECL
)
1510 retval_rhs
= TREE_OPERAND (retval
, 1);
1512 retval_rhs
= retval
;
1514 result_rtl
= DECL_RTL (DECL_RESULT (current_function_decl
));
1516 /* If we are returning the RESULT_DECL, then the value has already
1517 been stored into it, so we don't have to do anything special. */
1518 if (TREE_CODE (retval_rhs
) == RESULT_DECL
)
1519 expand_value_return (result_rtl
);
1521 /* If the result is an aggregate that is being returned in one (or more)
1522 registers, load the registers here. */
1524 else if (retval_rhs
!= 0
1525 && TYPE_MODE (TREE_TYPE (retval_rhs
)) == BLKmode
1526 && REG_P (result_rtl
))
1528 val
= copy_blkmode_to_reg (GET_MODE (result_rtl
), retval_rhs
);
1531 /* Use the mode of the result value on the return register. */
1532 PUT_MODE (result_rtl
, GET_MODE (val
));
1533 expand_value_return (val
);
1536 expand_null_return ();
1538 else if (retval_rhs
!= 0
1539 && !VOID_TYPE_P (TREE_TYPE (retval_rhs
))
1540 && (REG_P (result_rtl
)
1541 || (GET_CODE (result_rtl
) == PARALLEL
)))
1543 /* Calculate the return value into a temporary (usually a pseudo
1545 tree ot
= TREE_TYPE (DECL_RESULT (current_function_decl
));
1546 tree nt
= build_qualified_type (ot
, TYPE_QUALS (ot
) | TYPE_QUAL_CONST
);
1548 val
= assign_temp (nt
, 0, 1);
1549 val
= expand_expr (retval_rhs
, val
, GET_MODE (val
), EXPAND_NORMAL
);
1550 val
= force_not_mem (val
);
1551 /* Return the calculated value. */
1552 expand_value_return (val
);
1556 /* No hard reg used; calculate value into hard return reg. */
1557 expand_expr (retval
, const0_rtx
, VOIDmode
, EXPAND_NORMAL
);
1558 expand_value_return (result_rtl
);
1563 /* Emit code to save the current value of stack. */
1565 expand_stack_save (void)
1569 do_pending_stack_adjust ();
1570 emit_stack_save (SAVE_BLOCK
, &ret
);
1574 /* Emit code to restore the current value of stack. */
1576 expand_stack_restore (tree var
)
1578 rtx prev
, sa
= expand_normal (var
);
1580 sa
= convert_memory_address (Pmode
, sa
);
1582 prev
= get_last_insn ();
1583 emit_stack_restore (SAVE_BLOCK
, sa
);
1584 fixup_args_size_notes (prev
, get_last_insn (), 0);
1587 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
1588 is the probability of jumping to LABEL. */
1590 do_jump_if_equal (enum machine_mode mode
, rtx op0
, rtx op1
, rtx label
,
1591 int unsignedp
, int prob
)
1593 gcc_assert (prob
<= REG_BR_PROB_BASE
);
1594 do_compare_rtx_and_jump (op0
, op1
, EQ
, unsignedp
, mode
,
1595 NULL_RTX
, NULL_RTX
, label
, prob
);
1598 /* Do the insertion of a case label into case_list. The labels are
1599 fed to us in descending order from the sorted vector of case labels used
1600 in the tree part of the middle end. So the list we construct is
1601 sorted in ascending order.
1603 LABEL is the case label to be inserted. LOW and HIGH are the bounds
1604 against which the index is compared to jump to LABEL and PROB is the
1605 estimated probability LABEL is reached from the switch statement. */
1607 static struct case_node
*
1608 add_case_node (struct case_node
*head
, tree low
, tree high
,
1609 tree label
, int prob
, alloc_pool case_node_pool
)
1611 struct case_node
*r
;
1613 gcc_checking_assert (low
);
1614 gcc_checking_assert (high
&& (TREE_TYPE (low
) == TREE_TYPE (high
)));
1616 /* Add this label to the chain. */
1617 r
= (struct case_node
*) pool_alloc (case_node_pool
);
1620 r
->code_label
= label
;
1621 r
->parent
= r
->left
= NULL
;
1623 r
->subtree_prob
= prob
;
1628 /* Dump ROOT, a list or tree of case nodes, to file. */
1631 dump_case_nodes (FILE *f
, struct case_node
*root
,
1632 int indent_step
, int indent_level
)
1634 HOST_WIDE_INT low
, high
;
1640 dump_case_nodes (f
, root
->left
, indent_step
, indent_level
);
1642 low
= tree_low_cst (root
->low
, 0);
1643 high
= tree_low_cst (root
->high
, 0);
1647 fprintf (f
, "%*s" HOST_WIDE_INT_PRINT_DEC
,
1648 indent_step
* indent_level
, "", low
);
1650 fprintf (f
, "%*s" HOST_WIDE_INT_PRINT_DEC
" ... " HOST_WIDE_INT_PRINT_DEC
,
1651 indent_step
* indent_level
, "", low
, high
);
1654 dump_case_nodes (f
, root
->right
, indent_step
, indent_level
);
1658 #define HAVE_casesi 0
1661 #ifndef HAVE_tablejump
1662 #define HAVE_tablejump 0
1665 /* Return the smallest number of different values for which it is best to use a
1666 jump-table instead of a tree of conditional branches. */
1669 case_values_threshold (void)
1671 unsigned int threshold
= PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD
);
1674 threshold
= targetm
.case_values_threshold ();
1679 /* Return true if a switch should be expanded as a decision tree.
1680 RANGE is the difference between highest and lowest case.
1681 UNIQ is number of unique case node targets, not counting the default case.
1682 COUNT is the number of comparisons needed, not counting the default case. */
1685 expand_switch_as_decision_tree_p (tree range
,
1686 unsigned int uniq ATTRIBUTE_UNUSED
,
1691 /* If neither casesi or tablejump is available, or flag_jump_tables
1692 over-ruled us, we really have no choice. */
1693 if (!HAVE_casesi
&& !HAVE_tablejump
)
1695 if (!flag_jump_tables
)
1697 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
1702 /* If the switch is relatively small such that the cost of one
1703 indirect jump on the target are higher than the cost of a
1704 decision tree, go with the decision tree.
1706 If range of values is much bigger than number of values,
1707 or if it is too large to represent in a HOST_WIDE_INT,
1708 make a sequence of conditional branches instead of a dispatch.
1710 The definition of "much bigger" depends on whether we are
1711 optimizing for size or for speed. If the former, the maximum
1712 ratio range/count = 3, because this was found to be the optimal
1713 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
1714 10 is much older, and was probably selected after an extensive
1715 benchmarking investigation on numerous platforms. Or maybe it
1716 just made sense to someone at some point in the history of GCC,
1718 max_ratio
= optimize_insn_for_size_p () ? 3 : 10;
1719 if (count
< case_values_threshold ()
1720 || ! host_integerp (range
, /*pos=*/1)
1721 || compare_tree_int (range
, max_ratio
* count
) > 0)
1727 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
1728 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
1729 DEFAULT_PROB is the estimated probability that it jumps to
1732 We generate a binary decision tree to select the appropriate target
1733 code. This is done as follows:
1735 If the index is a short or char that we do not have
1736 an insn to handle comparisons directly, convert it to
1737 a full integer now, rather than letting each comparison
1738 generate the conversion.
1740 Load the index into a register.
1742 The list of cases is rearranged into a binary tree,
1743 nearly optimal assuming equal probability for each case.
1745 The tree is transformed into RTL, eliminating redundant
1746 test conditions at the same time.
1748 If program flow could reach the end of the decision tree
1749 an unconditional jump to the default code is emitted.
1751 The above process is unaware of the CFG. The caller has to fix up
1752 the CFG itself. This is done in cfgexpand.c. */
1755 emit_case_decision_tree (tree index_expr
, tree index_type
,
1756 struct case_node
*case_list
, rtx default_label
,
1759 rtx index
= expand_normal (index_expr
);
1761 if (GET_MODE_CLASS (GET_MODE (index
)) == MODE_INT
1762 && ! have_insn_for (COMPARE
, GET_MODE (index
)))
1764 int unsignedp
= TYPE_UNSIGNED (index_type
);
1765 enum machine_mode wider_mode
;
1766 for (wider_mode
= GET_MODE (index
); wider_mode
!= VOIDmode
;
1767 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
1768 if (have_insn_for (COMPARE
, wider_mode
))
1770 index
= convert_to_mode (wider_mode
, index
, unsignedp
);
1775 do_pending_stack_adjust ();
1779 index
= copy_to_reg (index
);
1780 if (TREE_CODE (index_expr
) == SSA_NAME
)
1781 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr
), index
);
1784 balance_case_nodes (&case_list
, NULL
);
1786 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1788 int indent_step
= ceil_log2 (TYPE_PRECISION (index_type
)) + 2;
1789 fprintf (dump_file
, ";; Expanding GIMPLE switch as decision tree:\n");
1790 dump_case_nodes (dump_file
, case_list
, indent_step
, 0);
1793 emit_case_nodes (index
, case_list
, default_label
, default_prob
, index_type
);
1795 emit_jump (default_label
);
1798 /* Return the sum of probabilities of outgoing edges of basic block BB. */
1801 get_outgoing_edge_probs (basic_block bb
)
1808 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1809 prob_sum
+= e
->probability
;
1813 /* Computes the conditional probability of jumping to a target if the branch
1814 instruction is executed.
1815 TARGET_PROB is the estimated probability of jumping to a target relative
1816 to some basic block BB.
1817 BASE_PROB is the probability of reaching the branch instruction relative
1818 to the same basic block BB. */
1821 conditional_probability (int target_prob
, int base_prob
)
1825 gcc_assert (target_prob
>= 0);
1826 gcc_assert (target_prob
<= base_prob
);
1827 return GCOV_COMPUTE_SCALE (target_prob
, base_prob
);
1832 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
1833 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
1834 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
1835 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
1837 First, a jump insn is emitted. First we try "casesi". If that
1838 fails, try "tablejump". A target *must* have one of them (or both).
1840 Then, a table with the target labels is emitted.
1842 The process is unaware of the CFG. The caller has to fix up
1843 the CFG itself. This is done in cfgexpand.c. */
1846 emit_case_dispatch_table (tree index_expr
, tree index_type
,
1847 struct case_node
*case_list
, rtx default_label
,
1848 tree minval
, tree maxval
, tree range
,
1849 basic_block stmt_bb
)
1852 struct case_node
*n
;
1854 rtx fallback_label
= label_rtx (case_list
->code_label
);
1855 rtx table_label
= gen_label_rtx ();
1856 bool has_gaps
= false;
1857 edge default_edge
= stmt_bb
? EDGE_SUCC (stmt_bb
, 0) : NULL
;
1858 int default_prob
= default_edge
? default_edge
->probability
: 0;
1859 int base
= get_outgoing_edge_probs (stmt_bb
);
1860 bool try_with_tablejump
= false;
1862 int new_default_prob
= conditional_probability (default_prob
,
1865 if (! try_casesi (index_type
, index_expr
, minval
, range
,
1866 table_label
, default_label
, fallback_label
,
1869 /* Index jumptables from zero for suitable values of minval to avoid
1870 a subtraction. For the rationale see:
1871 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
1872 if (optimize_insn_for_speed_p ()
1873 && compare_tree_int (minval
, 0) > 0
1874 && compare_tree_int (minval
, 3) < 0)
1876 minval
= build_int_cst (index_type
, 0);
1880 try_with_tablejump
= true;
1883 /* Get table of labels to jump to, in order of case index. */
1885 ncases
= tree_low_cst (range
, 0) + 1;
1886 labelvec
= XALLOCAVEC (rtx
, ncases
);
1887 memset (labelvec
, 0, ncases
* sizeof (rtx
));
1889 for (n
= case_list
; n
; n
= n
->right
)
1891 /* Compute the low and high bounds relative to the minimum
1892 value since that should fit in a HOST_WIDE_INT while the
1893 actual values may not. */
1895 = tree_low_cst (fold_build2 (MINUS_EXPR
, index_type
,
1896 n
->low
, minval
), 1);
1897 HOST_WIDE_INT i_high
1898 = tree_low_cst (fold_build2 (MINUS_EXPR
, index_type
,
1899 n
->high
, minval
), 1);
1902 for (i
= i_low
; i
<= i_high
; i
++)
1904 = gen_rtx_LABEL_REF (Pmode
, label_rtx (n
->code_label
));
1907 /* Fill in the gaps with the default. We may have gaps at
1908 the beginning if we tried to avoid the minval subtraction,
1909 so substitute some label even if the default label was
1910 deemed unreachable. */
1912 default_label
= fallback_label
;
1913 for (i
= 0; i
< ncases
; i
++)
1914 if (labelvec
[i
] == 0)
1917 labelvec
[i
] = gen_rtx_LABEL_REF (Pmode
, default_label
);
1922 /* There is at least one entry in the jump table that jumps
1923 to default label. The default label can either be reached
1924 through the indirect jump or the direct conditional jump
1925 before that. Split the probability of reaching the
1926 default label among these two jumps. */
1927 new_default_prob
= conditional_probability (default_prob
/2,
1930 base
-= default_prob
;
1934 base
-= default_prob
;
1939 default_edge
->probability
= default_prob
;
1941 /* We have altered the probability of the default edge. So the probabilities
1942 of all other edges need to be adjusted so that it sums up to
1943 REG_BR_PROB_BASE. */
1948 FOR_EACH_EDGE (e
, ei
, stmt_bb
->succs
)
1949 e
->probability
= GCOV_COMPUTE_SCALE (e
->probability
, base
);
1952 if (try_with_tablejump
)
1954 bool ok
= try_tablejump (index_type
, index_expr
, minval
, range
,
1955 table_label
, default_label
, new_default_prob
);
1958 /* Output the table. */
1959 emit_label (table_label
);
1961 if (CASE_VECTOR_PC_RELATIVE
|| flag_pic
)
1962 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE
,
1963 gen_rtx_LABEL_REF (Pmode
,
1965 gen_rtvec_v (ncases
, labelvec
),
1966 const0_rtx
, const0_rtx
));
1968 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE
,
1969 gen_rtvec_v (ncases
, labelvec
)));
1971 /* Record no drop-through after the table. */
1975 /* Reset the aux field of all outgoing edges of basic block BB. */
1978 reset_out_edges_aux (basic_block bb
)
1982 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1986 /* Compute the number of case labels that correspond to each outgoing edge of
1987 STMT. Record this information in the aux field of the edge. */
1990 compute_cases_per_edge (gimple stmt
)
1992 basic_block bb
= gimple_bb (stmt
);
1993 reset_out_edges_aux (bb
);
1994 int ncases
= gimple_switch_num_labels (stmt
);
1995 for (int i
= ncases
- 1; i
>= 1; --i
)
1997 tree elt
= gimple_switch_label (stmt
, i
);
1998 tree lab
= CASE_LABEL (elt
);
1999 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
2000 edge case_edge
= find_edge (bb
, case_bb
);
2001 case_edge
->aux
= (void *)((intptr_t)(case_edge
->aux
) + 1);
2005 /* Terminate a case (Pascal/Ada) or switch (C) statement
2006 in which ORIG_INDEX is the expression to be tested.
2007 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
2008 type as given in the source before any compiler conversions.
2009 Generate the code to test it and jump to the right place. */
2012 expand_case (gimple stmt
)
2014 tree minval
= NULL_TREE
, maxval
= NULL_TREE
, range
= NULL_TREE
;
2015 rtx default_label
= NULL_RTX
;
2016 unsigned int count
, uniq
;
2018 int ncases
= gimple_switch_num_labels (stmt
);
2019 tree index_expr
= gimple_switch_index (stmt
);
2020 tree index_type
= TREE_TYPE (index_expr
);
2022 basic_block bb
= gimple_bb (stmt
);
2024 /* A list of case labels; it is first built as a list and it may then
2025 be rearranged into a nearly balanced binary tree. */
2026 struct case_node
*case_list
= 0;
2028 /* A pool for case nodes. */
2029 alloc_pool case_node_pool
;
2031 /* An ERROR_MARK occurs for various reasons including invalid data type.
2032 ??? Can this still happen, with GIMPLE and all? */
2033 if (index_type
== error_mark_node
)
2036 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
2037 expressions being INTEGER_CST. */
2038 gcc_assert (TREE_CODE (index_expr
) != INTEGER_CST
);
2040 case_node_pool
= create_alloc_pool ("struct case_node pool",
2041 sizeof (struct case_node
),
2044 do_pending_stack_adjust ();
2046 /* Find the default case target label. */
2047 default_label
= label_rtx (CASE_LABEL (gimple_switch_default_label (stmt
)));
2048 edge default_edge
= EDGE_SUCC (bb
, 0);
2049 int default_prob
= default_edge
->probability
;
2051 /* Get upper and lower bounds of case values. */
2052 elt
= gimple_switch_label (stmt
, 1);
2053 minval
= fold_convert (index_type
, CASE_LOW (elt
));
2054 elt
= gimple_switch_label (stmt
, ncases
- 1);
2055 if (CASE_HIGH (elt
))
2056 maxval
= fold_convert (index_type
, CASE_HIGH (elt
));
2058 maxval
= fold_convert (index_type
, CASE_LOW (elt
));
2060 /* Compute span of values. */
2061 range
= fold_build2 (MINUS_EXPR
, index_type
, maxval
, minval
);
2063 /* Listify the labels queue and gather some numbers to decide
2064 how to expand this switch(). */
2067 struct pointer_set_t
*seen_labels
= pointer_set_create ();
2068 compute_cases_per_edge (stmt
);
2070 for (i
= ncases
- 1; i
>= 1; --i
)
2072 elt
= gimple_switch_label (stmt
, i
);
2073 tree low
= CASE_LOW (elt
);
2075 tree high
= CASE_HIGH (elt
);
2076 gcc_assert (! high
|| tree_int_cst_lt (low
, high
));
2077 tree lab
= CASE_LABEL (elt
);
2079 /* Count the elements.
2080 A range counts double, since it requires two compares. */
2085 /* If we have not seen this label yet, then increase the
2086 number of unique case node targets seen. */
2087 if (!pointer_set_insert (seen_labels
, lab
))
2090 /* The bounds on the case range, LOW and HIGH, have to be converted
2091 to case's index type TYPE. Note that the original type of the
2092 case index in the source code is usually "lost" during
2093 gimplification due to type promotion, but the case labels retain the
2094 original type. Make sure to drop overflow flags. */
2095 low
= fold_convert (index_type
, low
);
2096 if (TREE_OVERFLOW (low
))
2097 low
= build_int_cst_wide (index_type
,
2098 TREE_INT_CST_LOW (low
),
2099 TREE_INT_CST_HIGH (low
));
2101 /* The canonical from of a case label in GIMPLE is that a simple case
2102 has an empty CASE_HIGH. For the casesi and tablejump expanders,
2103 the back ends want simple cases to have high == low. */
2106 high
= fold_convert (index_type
, high
);
2107 if (TREE_OVERFLOW (high
))
2108 high
= build_int_cst_wide (index_type
,
2109 TREE_INT_CST_LOW (high
),
2110 TREE_INT_CST_HIGH (high
));
2112 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
2113 edge case_edge
= find_edge (bb
, case_bb
);
2114 case_list
= add_case_node (
2115 case_list
, low
, high
, lab
,
2116 case_edge
->probability
/ (intptr_t)(case_edge
->aux
),
2119 pointer_set_destroy (seen_labels
);
2120 reset_out_edges_aux (bb
);
2122 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
2123 destination, such as one with a default case only.
2124 It also removes cases that are out of range for the switch
2125 type, so we should never get a zero here. */
2126 gcc_assert (count
> 0);
2128 rtx before_case
= get_last_insn ();
2130 /* Decide how to expand this switch.
2131 The two options at this point are a dispatch table (casesi or
2132 tablejump) or a decision tree. */
2134 if (expand_switch_as_decision_tree_p (range
, uniq
, count
))
2135 emit_case_decision_tree (index_expr
, index_type
,
2136 case_list
, default_label
,
2139 emit_case_dispatch_table (index_expr
, index_type
,
2140 case_list
, default_label
,
2141 minval
, maxval
, range
, bb
);
2143 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
2146 free_alloc_pool (case_node_pool
);
2149 /* Expand the dispatch to a short decrement chain if there are few cases
2150 to dispatch to. Likewise if neither casesi nor tablejump is available,
2151 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
2152 tablejump. The index mode is always the mode of integer_type_node.
2153 Trap if no case matches the index.
2155 DISPATCH_INDEX is the index expression to switch on. It should be a
2156 memory or register operand.
2158 DISPATCH_TABLE is a set of case labels. The set should be sorted in
2159 ascending order, be contiguous, starting with value 0, and contain only
2160 single-valued case labels. */
2163 expand_sjlj_dispatch_table (rtx dispatch_index
,
2164 vec
<tree
> dispatch_table
)
2166 tree index_type
= integer_type_node
;
2167 enum machine_mode index_mode
= TYPE_MODE (index_type
);
2169 int ncases
= dispatch_table
.length ();
2171 do_pending_stack_adjust ();
2172 rtx before_case
= get_last_insn ();
2174 /* Expand as a decrement-chain if there are 5 or fewer dispatch
2175 labels. This covers more than 98% of the cases in libjava,
2176 and seems to be a reasonable compromise between the "old way"
2177 of expanding as a decision tree or dispatch table vs. the "new
2178 way" with decrement chain or dispatch table. */
2179 if (dispatch_table
.length () <= 5
2180 || (!HAVE_casesi
&& !HAVE_tablejump
)
2181 || !flag_jump_tables
)
2183 /* Expand the dispatch as a decrement chain:
2185 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
2189 if (index == 0) do_0; else index--;
2190 if (index == 0) do_1; else index--;
2192 if (index == 0) do_N; else index--;
2194 This is more efficient than a dispatch table on most machines.
2195 The last "index--" is redundant but the code is trivially dead
2196 and will be cleaned up by later passes. */
2197 rtx index
= copy_to_mode_reg (index_mode
, dispatch_index
);
2198 rtx zero
= CONST0_RTX (index_mode
);
2199 for (int i
= 0; i
< ncases
; i
++)
2201 tree elt
= dispatch_table
[i
];
2202 rtx lab
= label_rtx (CASE_LABEL (elt
));
2203 do_jump_if_equal (index_mode
, index
, zero
, lab
, 0, -1);
2204 force_expand_binop (index_mode
, sub_optab
,
2205 index
, CONST1_RTX (index_mode
),
2206 index
, 0, OPTAB_DIRECT
);
2211 /* Similar to expand_case, but much simpler. */
2212 struct case_node
*case_list
= 0;
2213 alloc_pool case_node_pool
= create_alloc_pool ("struct sjlj_case pool",
2214 sizeof (struct case_node
),
2216 tree index_expr
= make_tree (index_type
, dispatch_index
);
2217 tree minval
= build_int_cst (index_type
, 0);
2218 tree maxval
= CASE_LOW (dispatch_table
.last ());
2219 tree range
= maxval
;
2220 rtx default_label
= gen_label_rtx ();
2222 for (int i
= ncases
- 1; i
>= 0; --i
)
2224 tree elt
= dispatch_table
[i
];
2225 tree low
= CASE_LOW (elt
);
2226 tree lab
= CASE_LABEL (elt
);
2227 case_list
= add_case_node (case_list
, low
, low
, lab
, 0, case_node_pool
);
2230 emit_case_dispatch_table (index_expr
, index_type
,
2231 case_list
, default_label
,
2232 minval
, maxval
, range
,
2233 BLOCK_FOR_INSN (before_case
));
2234 emit_label (default_label
);
2235 free_alloc_pool (case_node_pool
);
2238 /* Dispatching something not handled? Trap! */
2239 expand_builtin_trap ();
2241 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
2247 /* Take an ordered list of case nodes
2248 and transform them into a near optimal binary tree,
2249 on the assumption that any target code selection value is as
2250 likely as any other.
2252 The transformation is performed by splitting the ordered
2253 list into two equal sections plus a pivot. The parts are
2254 then attached to the pivot as left and right branches. Each
2255 branch is then transformed recursively. */
2258 balance_case_nodes (case_node_ptr
*head
, case_node_ptr parent
)
2270 /* Count the number of entries on branch. Also count the ranges. */
2274 if (!tree_int_cst_equal (np
->low
, np
->high
))
2283 /* Split this list if it is long enough for that to help. */
2287 /* If there are just three nodes, split at the middle one. */
2289 npp
= &(*npp
)->right
;
2292 /* Find the place in the list that bisects the list's total cost,
2293 where ranges count as 2.
2294 Here I gets half the total cost. */
2295 i
= (i
+ ranges
+ 1) / 2;
2298 /* Skip nodes while their cost does not reach that amount. */
2299 if (!tree_int_cst_equal ((*npp
)->low
, (*npp
)->high
))
2304 npp
= &(*npp
)->right
;
2309 np
->parent
= parent
;
2312 /* Optimize each of the two split parts. */
2313 balance_case_nodes (&np
->left
, np
);
2314 balance_case_nodes (&np
->right
, np
);
2315 np
->subtree_prob
= np
->prob
;
2316 np
->subtree_prob
+= np
->left
->subtree_prob
;
2317 np
->subtree_prob
+= np
->right
->subtree_prob
;
2321 /* Else leave this branch as one level,
2322 but fill in `parent' fields. */
2324 np
->parent
= parent
;
2325 np
->subtree_prob
= np
->prob
;
2326 for (; np
->right
; np
= np
->right
)
2328 np
->right
->parent
= np
;
2329 (*head
)->subtree_prob
+= np
->right
->subtree_prob
;
2335 /* Search the parent sections of the case node tree
2336 to see if a test for the lower bound of NODE would be redundant.
2337 INDEX_TYPE is the type of the index expression.
2339 The instructions to generate the case decision tree are
2340 output in the same order as nodes are processed so it is
2341 known that if a parent node checks the range of the current
2342 node minus one that the current node is bounded at its lower
2343 span. Thus the test would be redundant. */
2346 node_has_low_bound (case_node_ptr node
, tree index_type
)
2349 case_node_ptr pnode
;
2351 /* If the lower bound of this node is the lowest value in the index type,
2352 we need not test it. */
2354 if (tree_int_cst_equal (node
->low
, TYPE_MIN_VALUE (index_type
)))
2357 /* If this node has a left branch, the value at the left must be less
2358 than that at this node, so it cannot be bounded at the bottom and
2359 we need not bother testing any further. */
2364 low_minus_one
= fold_build2 (MINUS_EXPR
, TREE_TYPE (node
->low
),
2366 build_int_cst (TREE_TYPE (node
->low
), 1));
2368 /* If the subtraction above overflowed, we can't verify anything.
2369 Otherwise, look for a parent that tests our value - 1. */
2371 if (! tree_int_cst_lt (low_minus_one
, node
->low
))
2374 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
2375 if (tree_int_cst_equal (low_minus_one
, pnode
->high
))
2381 /* Search the parent sections of the case node tree
2382 to see if a test for the upper bound of NODE would be redundant.
2383 INDEX_TYPE is the type of the index expression.
2385 The instructions to generate the case decision tree are
2386 output in the same order as nodes are processed so it is
2387 known that if a parent node checks the range of the current
2388 node plus one that the current node is bounded at its upper
2389 span. Thus the test would be redundant. */
2392 node_has_high_bound (case_node_ptr node
, tree index_type
)
2395 case_node_ptr pnode
;
2397 /* If there is no upper bound, obviously no test is needed. */
2399 if (TYPE_MAX_VALUE (index_type
) == NULL
)
2402 /* If the upper bound of this node is the highest value in the type
2403 of the index expression, we need not test against it. */
2405 if (tree_int_cst_equal (node
->high
, TYPE_MAX_VALUE (index_type
)))
2408 /* If this node has a right branch, the value at the right must be greater
2409 than that at this node, so it cannot be bounded at the top and
2410 we need not bother testing any further. */
2415 high_plus_one
= fold_build2 (PLUS_EXPR
, TREE_TYPE (node
->high
),
2417 build_int_cst (TREE_TYPE (node
->high
), 1));
2419 /* If the addition above overflowed, we can't verify anything.
2420 Otherwise, look for a parent that tests our value + 1. */
2422 if (! tree_int_cst_lt (node
->high
, high_plus_one
))
2425 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
2426 if (tree_int_cst_equal (high_plus_one
, pnode
->low
))
2432 /* Search the parent sections of the
2433 case node tree to see if both tests for the upper and lower
2434 bounds of NODE would be redundant. */
2437 node_is_bounded (case_node_ptr node
, tree index_type
)
2439 return (node_has_low_bound (node
, index_type
)
2440 && node_has_high_bound (node
, index_type
));
2444 /* Emit step-by-step code to select a case for the value of INDEX.
2445 The thus generated decision tree follows the form of the
2446 case-node binary tree NODE, whose nodes represent test conditions.
2447 INDEX_TYPE is the type of the index of the switch.
2449 Care is taken to prune redundant tests from the decision tree
2450 by detecting any boundary conditions already checked by
2451 emitted rtx. (See node_has_high_bound, node_has_low_bound
2452 and node_is_bounded, above.)
2454 Where the test conditions can be shown to be redundant we emit
2455 an unconditional jump to the target code. As a further
2456 optimization, the subordinates of a tree node are examined to
2457 check for bounded nodes. In this case conditional and/or
2458 unconditional jumps as a result of the boundary check for the
2459 current node are arranged to target the subordinates associated
2460 code for out of bound conditions on the current node.
2462 We can assume that when control reaches the code generated here,
2463 the index value has already been compared with the parents
2464 of this node, and determined to be on the same side of each parent
2465 as this node is. Thus, if this node tests for the value 51,
2466 and a parent tested for 52, we don't need to consider
2467 the possibility of a value greater than 51. If another parent
2468 tests for the value 50, then this node need not test anything. */
2471 emit_case_nodes (rtx index
, case_node_ptr node
, rtx default_label
,
2472 int default_prob
, tree index_type
)
2474 /* If INDEX has an unsigned type, we must make unsigned branches. */
2475 int unsignedp
= TYPE_UNSIGNED (index_type
);
2477 int prob
= node
->prob
, subtree_prob
= node
->subtree_prob
;
2478 enum machine_mode mode
= GET_MODE (index
);
2479 enum machine_mode imode
= TYPE_MODE (index_type
);
2481 /* Handle indices detected as constant during RTL expansion. */
2482 if (mode
== VOIDmode
)
2485 /* See if our parents have already tested everything for us.
2486 If they have, emit an unconditional jump for this node. */
2487 if (node_is_bounded (node
, index_type
))
2488 emit_jump (label_rtx (node
->code_label
));
2490 else if (tree_int_cst_equal (node
->low
, node
->high
))
2492 probability
= conditional_probability (prob
, subtree_prob
+ default_prob
);
2493 /* Node is single valued. First see if the index expression matches
2494 this node and then check our children, if any. */
2495 do_jump_if_equal (mode
, index
,
2496 convert_modes (mode
, imode
,
2497 expand_normal (node
->low
),
2499 label_rtx (node
->code_label
), unsignedp
, probability
);
2500 /* Since this case is taken at this point, reduce its weight from
2502 subtree_prob
-= prob
;
2503 if (node
->right
!= 0 && node
->left
!= 0)
2505 /* This node has children on both sides.
2506 Dispatch to one side or the other
2507 by comparing the index value with this node's value.
2508 If one subtree is bounded, check that one first,
2509 so we can avoid real branches in the tree. */
2511 if (node_is_bounded (node
->right
, index_type
))
2513 probability
= conditional_probability (
2515 subtree_prob
+ default_prob
);
2516 emit_cmp_and_jump_insns (index
,
2519 expand_normal (node
->high
),
2521 GT
, NULL_RTX
, mode
, unsignedp
,
2522 label_rtx (node
->right
->code_label
),
2524 emit_case_nodes (index
, node
->left
, default_label
, default_prob
,
2528 else if (node_is_bounded (node
->left
, index_type
))
2530 probability
= conditional_probability (
2532 subtree_prob
+ default_prob
);
2533 emit_cmp_and_jump_insns (index
,
2536 expand_normal (node
->high
),
2538 LT
, NULL_RTX
, mode
, unsignedp
,
2539 label_rtx (node
->left
->code_label
),
2541 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
2544 /* If both children are single-valued cases with no
2545 children, finish up all the work. This way, we can save
2546 one ordered comparison. */
2547 else if (tree_int_cst_equal (node
->right
->low
, node
->right
->high
)
2548 && node
->right
->left
== 0
2549 && node
->right
->right
== 0
2550 && tree_int_cst_equal (node
->left
->low
, node
->left
->high
)
2551 && node
->left
->left
== 0
2552 && node
->left
->right
== 0)
2554 /* Neither node is bounded. First distinguish the two sides;
2555 then emit the code for one side at a time. */
2557 /* See if the value matches what the right hand side
2559 probability
= conditional_probability (
2561 subtree_prob
+ default_prob
);
2562 do_jump_if_equal (mode
, index
,
2563 convert_modes (mode
, imode
,
2564 expand_normal (node
->right
->low
),
2566 label_rtx (node
->right
->code_label
),
2567 unsignedp
, probability
);
2569 /* See if the value matches what the left hand side
2571 probability
= conditional_probability (
2573 subtree_prob
+ default_prob
);
2574 do_jump_if_equal (mode
, index
,
2575 convert_modes (mode
, imode
,
2576 expand_normal (node
->left
->low
),
2578 label_rtx (node
->left
->code_label
),
2579 unsignedp
, probability
);
2584 /* Neither node is bounded. First distinguish the two sides;
2585 then emit the code for one side at a time. */
2588 = build_decl (curr_insn_location (),
2589 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
2591 /* The default label could be reached either through the right
2592 subtree or the left subtree. Divide the probability
2594 probability
= conditional_probability (
2595 node
->right
->subtree_prob
+ default_prob
/2,
2596 subtree_prob
+ default_prob
);
2597 /* See if the value is on the right. */
2598 emit_cmp_and_jump_insns (index
,
2601 expand_normal (node
->high
),
2603 GT
, NULL_RTX
, mode
, unsignedp
,
2604 label_rtx (test_label
),
2608 /* Value must be on the left.
2609 Handle the left-hand subtree. */
2610 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
2611 /* If left-hand subtree does nothing,
2614 emit_jump (default_label
);
2616 /* Code branches here for the right-hand subtree. */
2617 expand_label (test_label
);
2618 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
2622 else if (node
->right
!= 0 && node
->left
== 0)
2624 /* Here we have a right child but no left so we issue a conditional
2625 branch to default and process the right child.
2627 Omit the conditional branch to default if the right child
2628 does not have any children and is single valued; it would
2629 cost too much space to save so little time. */
2631 if (node
->right
->right
|| node
->right
->left
2632 || !tree_int_cst_equal (node
->right
->low
, node
->right
->high
))
2634 if (!node_has_low_bound (node
, index_type
))
2636 probability
= conditional_probability (
2638 subtree_prob
+ default_prob
);
2639 emit_cmp_and_jump_insns (index
,
2642 expand_normal (node
->high
),
2644 LT
, NULL_RTX
, mode
, unsignedp
,
2650 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
2654 probability
= conditional_probability (
2655 node
->right
->subtree_prob
,
2656 subtree_prob
+ default_prob
);
2657 /* We cannot process node->right normally
2658 since we haven't ruled out the numbers less than
2659 this node's value. So handle node->right explicitly. */
2660 do_jump_if_equal (mode
, index
,
2663 expand_normal (node
->right
->low
),
2665 label_rtx (node
->right
->code_label
), unsignedp
, probability
);
2669 else if (node
->right
== 0 && node
->left
!= 0)
2671 /* Just one subtree, on the left. */
2672 if (node
->left
->left
|| node
->left
->right
2673 || !tree_int_cst_equal (node
->left
->low
, node
->left
->high
))
2675 if (!node_has_high_bound (node
, index_type
))
2677 probability
= conditional_probability (
2679 subtree_prob
+ default_prob
);
2680 emit_cmp_and_jump_insns (index
,
2683 expand_normal (node
->high
),
2685 GT
, NULL_RTX
, mode
, unsignedp
,
2691 emit_case_nodes (index
, node
->left
, default_label
,
2692 default_prob
, index_type
);
2696 probability
= conditional_probability (
2697 node
->left
->subtree_prob
,
2698 subtree_prob
+ default_prob
);
2699 /* We cannot process node->left normally
2700 since we haven't ruled out the numbers less than
2701 this node's value. So handle node->left explicitly. */
2702 do_jump_if_equal (mode
, index
,
2705 expand_normal (node
->left
->low
),
2707 label_rtx (node
->left
->code_label
), unsignedp
, probability
);
2713 /* Node is a range. These cases are very similar to those for a single
2714 value, except that we do not start by testing whether this node
2715 is the one to branch to. */
2717 if (node
->right
!= 0 && node
->left
!= 0)
2719 /* Node has subtrees on both sides.
2720 If the right-hand subtree is bounded,
2721 test for it first, since we can go straight there.
2722 Otherwise, we need to make a branch in the control structure,
2723 then handle the two subtrees. */
2724 tree test_label
= 0;
2726 if (node_is_bounded (node
->right
, index_type
))
2728 /* Right hand node is fully bounded so we can eliminate any
2729 testing and branch directly to the target code. */
2730 probability
= conditional_probability (
2731 node
->right
->subtree_prob
,
2732 subtree_prob
+ default_prob
);
2733 emit_cmp_and_jump_insns (index
,
2736 expand_normal (node
->high
),
2738 GT
, NULL_RTX
, mode
, unsignedp
,
2739 label_rtx (node
->right
->code_label
),
2744 /* Right hand node requires testing.
2745 Branch to a label where we will handle it later. */
2747 test_label
= build_decl (curr_insn_location (),
2748 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
2749 probability
= conditional_probability (
2750 node
->right
->subtree_prob
+ default_prob
/2,
2751 subtree_prob
+ default_prob
);
2752 emit_cmp_and_jump_insns (index
,
2755 expand_normal (node
->high
),
2757 GT
, NULL_RTX
, mode
, unsignedp
,
2758 label_rtx (test_label
),
2763 /* Value belongs to this node or to the left-hand subtree. */
2765 probability
= conditional_probability (
2767 subtree_prob
+ default_prob
);
2768 emit_cmp_and_jump_insns (index
,
2771 expand_normal (node
->low
),
2773 GE
, NULL_RTX
, mode
, unsignedp
,
2774 label_rtx (node
->code_label
),
2777 /* Handle the left-hand subtree. */
2778 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
2780 /* If right node had to be handled later, do that now. */
2784 /* If the left-hand subtree fell through,
2785 don't let it fall into the right-hand subtree. */
2787 emit_jump (default_label
);
2789 expand_label (test_label
);
2790 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
2794 else if (node
->right
!= 0 && node
->left
== 0)
2796 /* Deal with values to the left of this node,
2797 if they are possible. */
2798 if (!node_has_low_bound (node
, index_type
))
2800 probability
= conditional_probability (
2802 subtree_prob
+ default_prob
);
2803 emit_cmp_and_jump_insns (index
,
2806 expand_normal (node
->low
),
2808 LT
, NULL_RTX
, mode
, unsignedp
,
2814 /* Value belongs to this node or to the right-hand subtree. */
2816 probability
= conditional_probability (
2818 subtree_prob
+ default_prob
);
2819 emit_cmp_and_jump_insns (index
,
2822 expand_normal (node
->high
),
2824 LE
, NULL_RTX
, mode
, unsignedp
,
2825 label_rtx (node
->code_label
),
2828 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
2831 else if (node
->right
== 0 && node
->left
!= 0)
2833 /* Deal with values to the right of this node,
2834 if they are possible. */
2835 if (!node_has_high_bound (node
, index_type
))
2837 probability
= conditional_probability (
2839 subtree_prob
+ default_prob
);
2840 emit_cmp_and_jump_insns (index
,
2843 expand_normal (node
->high
),
2845 GT
, NULL_RTX
, mode
, unsignedp
,
2851 /* Value belongs to this node or to the left-hand subtree. */
2853 probability
= conditional_probability (
2855 subtree_prob
+ default_prob
);
2856 emit_cmp_and_jump_insns (index
,
2859 expand_normal (node
->low
),
2861 GE
, NULL_RTX
, mode
, unsignedp
,
2862 label_rtx (node
->code_label
),
2865 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
2870 /* Node has no children so we check low and high bounds to remove
2871 redundant tests. Only one of the bounds can exist,
2872 since otherwise this node is bounded--a case tested already. */
2873 int high_bound
= node_has_high_bound (node
, index_type
);
2874 int low_bound
= node_has_low_bound (node
, index_type
);
2876 if (!high_bound
&& low_bound
)
2878 probability
= conditional_probability (
2880 subtree_prob
+ default_prob
);
2881 emit_cmp_and_jump_insns (index
,
2884 expand_normal (node
->high
),
2886 GT
, NULL_RTX
, mode
, unsignedp
,
2891 else if (!low_bound
&& high_bound
)
2893 probability
= conditional_probability (
2895 subtree_prob
+ default_prob
);
2896 emit_cmp_and_jump_insns (index
,
2899 expand_normal (node
->low
),
2901 LT
, NULL_RTX
, mode
, unsignedp
,
2905 else if (!low_bound
&& !high_bound
)
2907 /* Widen LOW and HIGH to the same width as INDEX. */
2908 tree type
= lang_hooks
.types
.type_for_mode (mode
, unsignedp
);
2909 tree low
= build1 (CONVERT_EXPR
, type
, node
->low
);
2910 tree high
= build1 (CONVERT_EXPR
, type
, node
->high
);
2911 rtx low_rtx
, new_index
, new_bound
;
2913 /* Instead of doing two branches, emit one unsigned branch for
2914 (index-low) > (high-low). */
2915 low_rtx
= expand_expr (low
, NULL_RTX
, mode
, EXPAND_NORMAL
);
2916 new_index
= expand_simple_binop (mode
, MINUS
, index
, low_rtx
,
2917 NULL_RTX
, unsignedp
,
2919 new_bound
= expand_expr (fold_build2 (MINUS_EXPR
, type
,
2921 NULL_RTX
, mode
, EXPAND_NORMAL
);
2923 probability
= conditional_probability (
2925 subtree_prob
+ default_prob
);
2926 emit_cmp_and_jump_insns (new_index
, new_bound
, GT
, NULL_RTX
,
2927 mode
, 1, default_label
, probability
);
2930 emit_jump (label_rtx (node
->code_label
));