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"
53 #include "pointer-set.h"
58 /* Functions and data structures for expanding case statements. */
60 /* Case label structure, used to hold info on labels within case
61 statements. We handle "range" labels; for a single-value label
62 as in C, the high and low limits are the same.
64 We start with a vector of case nodes sorted in ascending order, and
65 the default label as the last element in the vector. Before expanding
66 to RTL, we transform this vector into a list linked via the RIGHT
67 fields in the case_node struct. Nodes with higher case values are
70 Switch statements can be output in three forms. A branch table is
71 used if there are more than a few labels and the labels are dense
72 within the range between the smallest and largest case value. If a
73 branch table is used, no further manipulations are done with the case
76 The alternative to the use of a branch table is to generate a series
77 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
78 and PARENT fields to hold a binary tree. Initially the tree is
79 totally unbalanced, with everything on the right. We balance the tree
80 with nodes on the left having lower case values than the parent
81 and nodes on the right having higher values. We then output the tree
84 For very small, suitable switch statements, we can generate a series
85 of simple bit test and branches instead. */
89 struct case_node
*left
; /* Left son in binary tree */
90 struct case_node
*right
; /* Right son in binary tree; also node chain */
91 struct case_node
*parent
; /* Parent of node in binary tree */
92 tree low
; /* Lowest index value for this label */
93 tree high
; /* Highest index value for this label */
94 tree code_label
; /* Label to jump to when node matches */
95 int prob
; /* Probability of taking this case. */
96 /* Probability of reaching subtree rooted at this node */
100 typedef struct case_node case_node
;
101 typedef struct case_node
*case_node_ptr
;
103 extern basic_block
label_to_block_fn (struct function
*, tree
);
105 static int n_occurrences (int, const char *);
106 static bool tree_conflicts_with_clobbers_p (tree
, HARD_REG_SET
*);
107 static bool check_operand_nalternatives (tree
, tree
);
108 static bool check_unique_operand_names (tree
, tree
, tree
);
109 static char *resolve_operand_name_1 (char *, tree
, tree
, tree
);
110 static void expand_null_return_1 (void);
111 static void expand_value_return (rtx
);
112 static void balance_case_nodes (case_node_ptr
*, case_node_ptr
);
113 static int node_has_low_bound (case_node_ptr
, tree
);
114 static int node_has_high_bound (case_node_ptr
, tree
);
115 static int node_is_bounded (case_node_ptr
, tree
);
116 static void emit_case_nodes (rtx
, case_node_ptr
, rtx
, int, tree
);
118 /* Return the rtx-label that corresponds to a LABEL_DECL,
119 creating it if necessary. */
122 label_rtx (tree label
)
124 gcc_assert (TREE_CODE (label
) == LABEL_DECL
);
126 if (!DECL_RTL_SET_P (label
))
128 rtx r
= gen_label_rtx ();
129 SET_DECL_RTL (label
, r
);
130 if (FORCED_LABEL (label
) || DECL_NONLOCAL (label
))
131 LABEL_PRESERVE_P (r
) = 1;
134 return DECL_RTL (label
);
137 /* As above, but also put it on the forced-reference list of the
138 function that contains it. */
140 force_label_rtx (tree label
)
142 rtx ref
= label_rtx (label
);
143 tree function
= decl_function_context (label
);
145 gcc_assert (function
);
147 forced_labels
= gen_rtx_EXPR_LIST (VOIDmode
, ref
, forced_labels
);
151 /* Add an unconditional jump to LABEL as the next sequential instruction. */
154 emit_jump (rtx label
)
156 do_pending_stack_adjust ();
157 emit_jump_insn (gen_jump (label
));
161 /* Emit code to jump to the address
162 specified by the pointer expression EXP. */
165 expand_computed_goto (tree exp
)
167 rtx x
= expand_normal (exp
);
169 x
= convert_memory_address (Pmode
, x
);
171 do_pending_stack_adjust ();
172 emit_indirect_jump (x
);
175 /* Handle goto statements and the labels that they can go to. */
177 /* Specify the location in the RTL code of a label LABEL,
178 which is a LABEL_DECL tree node.
180 This is used for the kind of label that the user can jump to with a
181 goto statement, and for alternatives of a switch or case statement.
182 RTL labels generated for loops and conditionals don't go through here;
183 they are generated directly at the RTL level, by other functions below.
185 Note that this has nothing to do with defining label *names*.
186 Languages vary in how they do that and what that even means. */
189 expand_label (tree label
)
191 rtx label_r
= label_rtx (label
);
193 do_pending_stack_adjust ();
194 emit_label (label_r
);
195 if (DECL_NAME (label
))
196 LABEL_NAME (DECL_RTL (label
)) = IDENTIFIER_POINTER (DECL_NAME (label
));
198 if (DECL_NONLOCAL (label
))
200 expand_builtin_setjmp_receiver (NULL
);
201 nonlocal_goto_handler_labels
202 = gen_rtx_EXPR_LIST (VOIDmode
, label_r
,
203 nonlocal_goto_handler_labels
);
206 if (FORCED_LABEL (label
))
207 forced_labels
= gen_rtx_EXPR_LIST (VOIDmode
, label_r
, forced_labels
);
209 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
210 maybe_set_first_label_num (label_r
);
213 /* Generate RTL code for a `goto' statement with target label LABEL.
214 LABEL should be a LABEL_DECL tree node that was or will later be
215 defined with `expand_label'. */
218 expand_goto (tree label
)
220 #ifdef ENABLE_CHECKING
221 /* Check for a nonlocal goto to a containing function. Should have
222 gotten translated to __builtin_nonlocal_goto. */
223 tree context
= decl_function_context (label
);
224 gcc_assert (!context
|| context
== current_function_decl
);
227 emit_jump (label_rtx (label
));
230 /* Return the number of times character C occurs in string S. */
232 n_occurrences (int c
, const char *s
)
240 /* Generate RTL for an asm statement (explicit assembler code).
241 STRING is a STRING_CST node containing the assembler code text,
242 or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the
243 insn is volatile; don't optimize it. */
246 expand_asm_loc (tree string
, int vol
, location_t locus
)
250 if (TREE_CODE (string
) == ADDR_EXPR
)
251 string
= TREE_OPERAND (string
, 0);
253 body
= gen_rtx_ASM_INPUT_loc (VOIDmode
,
254 ggc_strdup (TREE_STRING_POINTER (string
)),
257 MEM_VOLATILE_P (body
) = vol
;
262 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
263 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
264 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
265 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
266 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
267 constraint allows the use of a register operand. And, *IS_INOUT
268 will be true if the operand is read-write, i.e., if it is used as
269 an input as well as an output. If *CONSTRAINT_P is not in
270 canonical form, it will be made canonical. (Note that `+' will be
271 replaced with `=' as part of this process.)
273 Returns TRUE if all went well; FALSE if an error occurred. */
276 parse_output_constraint (const char **constraint_p
, int operand_num
,
277 int ninputs
, int noutputs
, bool *allows_mem
,
278 bool *allows_reg
, bool *is_inout
)
280 const char *constraint
= *constraint_p
;
283 /* Assume the constraint doesn't allow the use of either a register
288 /* Allow the `=' or `+' to not be at the beginning of the string,
289 since it wasn't explicitly documented that way, and there is a
290 large body of code that puts it last. Swap the character to
291 the front, so as not to uglify any place else. */
292 p
= strchr (constraint
, '=');
294 p
= strchr (constraint
, '+');
296 /* If the string doesn't contain an `=', issue an error
300 error ("output operand constraint lacks %<=%>");
304 /* If the constraint begins with `+', then the operand is both read
305 from and written to. */
306 *is_inout
= (*p
== '+');
308 /* Canonicalize the output constraint so that it begins with `='. */
309 if (p
!= constraint
|| *is_inout
)
312 size_t c_len
= strlen (constraint
);
315 warning (0, "output constraint %qc for operand %d "
316 "is not at the beginning",
319 /* Make a copy of the constraint. */
320 buf
= XALLOCAVEC (char, c_len
+ 1);
321 strcpy (buf
, constraint
);
322 /* Swap the first character and the `=' or `+'. */
323 buf
[p
- constraint
] = buf
[0];
324 /* Make sure the first character is an `='. (Until we do this,
325 it might be a `+'.) */
327 /* Replace the constraint with the canonicalized string. */
328 *constraint_p
= ggc_alloc_string (buf
, c_len
);
329 constraint
= *constraint_p
;
332 /* Loop through the constraint string. */
333 for (p
= constraint
+ 1; *p
; p
+= CONSTRAINT_LEN (*p
, p
))
338 error ("operand constraint contains incorrectly positioned "
343 if (operand_num
+ 1 == ninputs
+ noutputs
)
345 error ("%<%%%> constraint used with last operand");
350 case 'V': case TARGET_MEM_CONSTRAINT
: case 'o':
354 case '?': case '!': case '*': case '&': case '#':
355 case 'E': case 'F': case 'G': case 'H':
356 case 's': case 'i': case 'n':
357 case 'I': case 'J': case 'K': case 'L': case 'M':
358 case 'N': case 'O': case 'P': case ',':
361 case '0': case '1': case '2': case '3': case '4':
362 case '5': case '6': case '7': case '8': case '9':
364 error ("matching constraint not valid in output operand");
368 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
369 excepting those that expand_call created. So match memory
386 if (REG_CLASS_FROM_CONSTRAINT (*p
, p
) != NO_REGS
)
388 #ifdef EXTRA_CONSTRAINT_STR
389 else if (EXTRA_ADDRESS_CONSTRAINT (*p
, p
))
391 else if (EXTRA_MEMORY_CONSTRAINT (*p
, p
))
395 /* Otherwise we can't assume anything about the nature of
396 the constraint except that it isn't purely registers.
397 Treat it like "g" and hope for the best. */
408 /* Similar, but for input constraints. */
411 parse_input_constraint (const char **constraint_p
, int input_num
,
412 int ninputs
, int noutputs
, int ninout
,
413 const char * const * constraints
,
414 bool *allows_mem
, bool *allows_reg
)
416 const char *constraint
= *constraint_p
;
417 const char *orig_constraint
= constraint
;
418 size_t c_len
= strlen (constraint
);
420 bool saw_match
= false;
422 /* Assume the constraint doesn't allow the use of either
423 a register or memory. */
427 /* Make sure constraint has neither `=', `+', nor '&'. */
429 for (j
= 0; j
< c_len
; j
+= CONSTRAINT_LEN (constraint
[j
], constraint
+j
))
430 switch (constraint
[j
])
432 case '+': case '=': case '&':
433 if (constraint
== orig_constraint
)
435 error ("input operand constraint contains %qc", constraint
[j
]);
441 if (constraint
== orig_constraint
442 && input_num
+ 1 == ninputs
- ninout
)
444 error ("%<%%%> constraint used with last operand");
449 case 'V': case TARGET_MEM_CONSTRAINT
: case 'o':
454 case '?': case '!': case '*': case '#':
455 case 'E': case 'F': case 'G': case 'H':
456 case 's': case 'i': case 'n':
457 case 'I': case 'J': case 'K': case 'L': case 'M':
458 case 'N': case 'O': case 'P': case ',':
461 /* Whether or not a numeric constraint allows a register is
462 decided by the matching constraint, and so there is no need
463 to do anything special with them. We must handle them in
464 the default case, so that we don't unnecessarily force
465 operands to memory. */
466 case '0': case '1': case '2': case '3': case '4':
467 case '5': case '6': case '7': case '8': case '9':
474 match
= strtoul (constraint
+ j
, &end
, 10);
475 if (match
>= (unsigned long) noutputs
)
477 error ("matching constraint references invalid operand number");
481 /* Try and find the real constraint for this dup. Only do this
482 if the matching constraint is the only alternative. */
484 && (j
== 0 || (j
== 1 && constraint
[0] == '%')))
486 constraint
= constraints
[match
];
487 *constraint_p
= constraint
;
488 c_len
= strlen (constraint
);
490 /* ??? At the end of the loop, we will skip the first part of
491 the matched constraint. This assumes not only that the
492 other constraint is an output constraint, but also that
493 the '=' or '+' come first. */
497 j
= end
- constraint
;
498 /* Anticipate increment at end of loop. */
513 if (! ISALPHA (constraint
[j
]))
515 error ("invalid punctuation %qc in constraint", constraint
[j
]);
518 if (REG_CLASS_FROM_CONSTRAINT (constraint
[j
], constraint
+ j
)
521 #ifdef EXTRA_CONSTRAINT_STR
522 else if (EXTRA_ADDRESS_CONSTRAINT (constraint
[j
], constraint
+ j
))
524 else if (EXTRA_MEMORY_CONSTRAINT (constraint
[j
], constraint
+ j
))
528 /* Otherwise we can't assume anything about the nature of
529 the constraint except that it isn't purely registers.
530 Treat it like "g" and hope for the best. */
538 if (saw_match
&& !*allows_reg
)
539 warning (0, "matching constraint does not allow a register");
544 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
545 can be an asm-declared register. Called via walk_tree. */
548 decl_overlaps_hard_reg_set_p (tree
*declp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
552 const HARD_REG_SET
*const regs
= (const HARD_REG_SET
*) data
;
554 if (TREE_CODE (decl
) == VAR_DECL
)
556 if (DECL_HARD_REGISTER (decl
)
557 && REG_P (DECL_RTL (decl
))
558 && REGNO (DECL_RTL (decl
)) < FIRST_PSEUDO_REGISTER
)
560 rtx reg
= DECL_RTL (decl
);
562 if (overlaps_hard_reg_set_p (*regs
, GET_MODE (reg
), REGNO (reg
)))
567 else if (TYPE_P (decl
) || TREE_CODE (decl
) == PARM_DECL
)
572 /* If there is an overlap between *REGS and DECL, return the first overlap
575 tree_overlaps_hard_reg_set (tree decl
, HARD_REG_SET
*regs
)
577 return walk_tree (&decl
, decl_overlaps_hard_reg_set_p
, regs
, NULL
);
580 /* Check for overlap between registers marked in CLOBBERED_REGS and
581 anything inappropriate in T. Emit error and return the register
582 variable definition for error, NULL_TREE for ok. */
585 tree_conflicts_with_clobbers_p (tree t
, HARD_REG_SET
*clobbered_regs
)
587 /* Conflicts between asm-declared register variables and the clobber
588 list are not allowed. */
589 tree overlap
= tree_overlaps_hard_reg_set (t
, clobbered_regs
);
593 error ("asm-specifier for variable %qE conflicts with asm clobber list",
594 DECL_NAME (overlap
));
596 /* Reset registerness to stop multiple errors emitted for a single
598 DECL_REGISTER (overlap
) = 0;
605 /* Generate RTL for an asm statement with arguments.
606 STRING is the instruction template.
607 OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs.
608 Each output or input has an expression in the TREE_VALUE and
609 a tree list in TREE_PURPOSE which in turn contains a constraint
610 name in TREE_VALUE (or NULL_TREE) and a constraint string
612 CLOBBERS is a list of STRING_CST nodes each naming a hard register
613 that is clobbered by this insn.
615 LABELS is a list of labels, and if LABELS is non-NULL, FALLTHRU_BB
616 should be the fallthru basic block of the asm goto.
618 Not all kinds of lvalue that may appear in OUTPUTS can be stored directly.
619 Some elements of OUTPUTS may be replaced with trees representing temporary
620 values. The caller should copy those temporary values to the originally
623 VOL nonzero means the insn is volatile; don't optimize it. */
626 expand_asm_operands (tree string
, tree outputs
, tree inputs
,
627 tree clobbers
, tree labels
, basic_block fallthru_bb
,
628 int vol
, location_t locus
)
630 rtvec argvec
, constraintvec
, labelvec
;
632 int ninputs
= list_length (inputs
);
633 int noutputs
= list_length (outputs
);
634 int nlabels
= list_length (labels
);
637 HARD_REG_SET clobbered_regs
;
638 int clobber_conflict_found
= 0;
642 /* Vector of RTX's of evaluated output operands. */
643 rtx
*output_rtx
= XALLOCAVEC (rtx
, noutputs
);
644 int *inout_opnum
= XALLOCAVEC (int, noutputs
);
645 rtx
*real_output_rtx
= XALLOCAVEC (rtx
, noutputs
);
646 enum machine_mode
*inout_mode
= XALLOCAVEC (enum machine_mode
, noutputs
);
647 const char **constraints
= XALLOCAVEC (const char *, noutputs
+ ninputs
);
648 int old_generating_concat_p
= generating_concat_p
;
649 rtx fallthru_label
= NULL_RTX
;
651 /* An ASM with no outputs needs to be treated as volatile, for now. */
655 if (! check_operand_nalternatives (outputs
, inputs
))
658 string
= resolve_asm_operand_names (string
, outputs
, inputs
, labels
);
660 /* Collect constraints. */
662 for (t
= outputs
; t
; t
= TREE_CHAIN (t
), i
++)
663 constraints
[i
] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
664 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), i
++)
665 constraints
[i
] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
667 /* Sometimes we wish to automatically clobber registers across an asm.
668 Case in point is when the i386 backend moved from cc0 to a hard reg --
669 maintaining source-level compatibility means automatically clobbering
670 the flags register. */
671 clobbers
= targetm
.md_asm_clobbers (outputs
, inputs
, clobbers
);
673 /* Count the number of meaningful clobbered registers, ignoring what
674 we would ignore later. */
676 CLEAR_HARD_REG_SET (clobbered_regs
);
677 for (tail
= clobbers
; tail
; tail
= TREE_CHAIN (tail
))
682 if (TREE_VALUE (tail
) == error_mark_node
)
684 regname
= TREE_STRING_POINTER (TREE_VALUE (tail
));
686 i
= decode_reg_name_and_count (regname
, &nregs
);
690 error ("unknown register name %qs in %<asm%>", regname
);
692 /* Mark clobbered registers. */
697 for (reg
= i
; reg
< i
+ nregs
; reg
++)
701 /* Clobbering the PIC register is an error. */
702 if (reg
== (int) PIC_OFFSET_TABLE_REGNUM
)
704 error ("PIC register clobbered by %qs in %<asm%>", regname
);
708 SET_HARD_REG_BIT (clobbered_regs
, reg
);
713 /* First pass over inputs and outputs checks validity and sets
714 mark_addressable if needed. */
717 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
719 tree val
= TREE_VALUE (tail
);
720 tree type
= TREE_TYPE (val
);
721 const char *constraint
;
726 /* If there's an erroneous arg, emit no insn. */
727 if (type
== error_mark_node
)
730 /* Try to parse the output constraint. If that fails, there's
731 no point in going further. */
732 constraint
= constraints
[i
];
733 if (!parse_output_constraint (&constraint
, i
, ninputs
, noutputs
,
734 &allows_mem
, &allows_reg
, &is_inout
))
741 && REG_P (DECL_RTL (val
))
742 && GET_MODE (DECL_RTL (val
)) != TYPE_MODE (type
))))
743 mark_addressable (val
);
750 if (ninputs
+ noutputs
> MAX_RECOG_OPERANDS
)
752 error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS
);
756 for (i
= 0, tail
= inputs
; tail
; i
++, tail
= TREE_CHAIN (tail
))
758 bool allows_reg
, allows_mem
;
759 const char *constraint
;
761 /* If there's an erroneous arg, emit no insn, because the ASM_INPUT
762 would get VOIDmode and that could cause a crash in reload. */
763 if (TREE_TYPE (TREE_VALUE (tail
)) == error_mark_node
)
766 constraint
= constraints
[i
+ noutputs
];
767 if (! parse_input_constraint (&constraint
, i
, ninputs
, noutputs
, ninout
,
768 constraints
, &allows_mem
, &allows_reg
))
771 if (! allows_reg
&& allows_mem
)
772 mark_addressable (TREE_VALUE (tail
));
775 /* Second pass evaluates arguments. */
777 /* Make sure stack is consistent for asm goto. */
779 do_pending_stack_adjust ();
782 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
784 tree val
= TREE_VALUE (tail
);
785 tree type
= TREE_TYPE (val
);
792 ok
= parse_output_constraint (&constraints
[i
], i
, ninputs
,
793 noutputs
, &allows_mem
, &allows_reg
,
797 /* If an output operand is not a decl or indirect ref and our constraint
798 allows a register, make a temporary to act as an intermediate.
799 Make the asm insn write into that, then our caller will copy it to
800 the real output operand. Likewise for promoted variables. */
802 generating_concat_p
= 0;
804 real_output_rtx
[i
] = NULL_RTX
;
805 if ((TREE_CODE (val
) == INDIRECT_REF
808 && (allows_mem
|| REG_P (DECL_RTL (val
)))
809 && ! (REG_P (DECL_RTL (val
))
810 && GET_MODE (DECL_RTL (val
)) != TYPE_MODE (type
)))
814 op
= expand_expr (val
, NULL_RTX
, VOIDmode
,
815 !allows_reg
? EXPAND_MEMORY
: EXPAND_WRITE
);
817 op
= validize_mem (op
);
819 if (! allows_reg
&& !MEM_P (op
))
820 error ("output number %d not directly addressable", i
);
821 if ((! allows_mem
&& MEM_P (op
))
822 || GET_CODE (op
) == CONCAT
)
824 real_output_rtx
[i
] = op
;
825 op
= gen_reg_rtx (GET_MODE (op
));
827 emit_move_insn (op
, real_output_rtx
[i
]);
832 op
= assign_temp (type
, 0, 1);
833 op
= validize_mem (op
);
834 if (!MEM_P (op
) && TREE_CODE (TREE_VALUE (tail
)) == SSA_NAME
)
835 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (TREE_VALUE (tail
)), op
);
836 TREE_VALUE (tail
) = make_tree (type
, op
);
840 generating_concat_p
= old_generating_concat_p
;
844 inout_mode
[ninout
] = TYPE_MODE (type
);
845 inout_opnum
[ninout
++] = i
;
848 if (tree_conflicts_with_clobbers_p (val
, &clobbered_regs
))
849 clobber_conflict_found
= 1;
852 /* Make vectors for the expression-rtx, constraint strings,
853 and named operands. */
855 argvec
= rtvec_alloc (ninputs
);
856 constraintvec
= rtvec_alloc (ninputs
);
857 labelvec
= rtvec_alloc (nlabels
);
859 body
= gen_rtx_ASM_OPERANDS ((noutputs
== 0 ? VOIDmode
860 : GET_MODE (output_rtx
[0])),
861 ggc_strdup (TREE_STRING_POINTER (string
)),
862 empty_string
, 0, argvec
, constraintvec
,
865 MEM_VOLATILE_P (body
) = vol
;
867 /* Eval the inputs and put them into ARGVEC.
868 Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */
870 for (i
= 0, tail
= inputs
; tail
; tail
= TREE_CHAIN (tail
), ++i
)
872 bool allows_reg
, allows_mem
;
873 const char *constraint
;
878 constraint
= constraints
[i
+ noutputs
];
879 ok
= parse_input_constraint (&constraint
, i
, ninputs
, noutputs
, ninout
,
880 constraints
, &allows_mem
, &allows_reg
);
883 generating_concat_p
= 0;
885 val
= TREE_VALUE (tail
);
886 type
= TREE_TYPE (val
);
887 /* EXPAND_INITIALIZER will not generate code for valid initializer
888 constants, but will still generate code for other types of operand.
889 This is the behavior we want for constant constraints. */
890 op
= expand_expr (val
, NULL_RTX
, VOIDmode
,
891 allows_reg
? EXPAND_NORMAL
892 : allows_mem
? EXPAND_MEMORY
893 : EXPAND_INITIALIZER
);
895 /* Never pass a CONCAT to an ASM. */
896 if (GET_CODE (op
) == CONCAT
)
897 op
= force_reg (GET_MODE (op
), op
);
899 op
= validize_mem (op
);
901 if (asm_operand_ok (op
, constraint
, NULL
) <= 0)
903 if (allows_reg
&& TYPE_MODE (type
) != BLKmode
)
904 op
= force_reg (TYPE_MODE (type
), op
);
905 else if (!allows_mem
)
906 warning (0, "asm operand %d probably doesn%'t match constraints",
910 /* We won't recognize either volatile memory or memory
911 with a queued address as available a memory_operand
912 at this point. Ignore it: clearly this *is* a memory. */
918 generating_concat_p
= old_generating_concat_p
;
919 ASM_OPERANDS_INPUT (body
, i
) = op
;
921 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body
, i
)
922 = gen_rtx_ASM_INPUT (TYPE_MODE (type
),
923 ggc_strdup (constraints
[i
+ noutputs
]));
925 if (tree_conflicts_with_clobbers_p (val
, &clobbered_regs
))
926 clobber_conflict_found
= 1;
929 /* Protect all the operands from the queue now that they have all been
932 generating_concat_p
= 0;
934 /* For in-out operands, copy output rtx to input rtx. */
935 for (i
= 0; i
< ninout
; i
++)
937 int j
= inout_opnum
[i
];
940 ASM_OPERANDS_INPUT (body
, ninputs
- ninout
+ i
)
943 sprintf (buffer
, "%d", j
);
944 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body
, ninputs
- ninout
+ i
)
945 = gen_rtx_ASM_INPUT (inout_mode
[i
], ggc_strdup (buffer
));
948 /* Copy labels to the vector. */
949 for (i
= 0, tail
= labels
; i
< nlabels
; ++i
, tail
= TREE_CHAIN (tail
))
952 /* If asm goto has any labels in the fallthru basic block, use
953 a label that we emit immediately after the asm goto. Expansion
954 may insert further instructions into the same basic block after
955 asm goto and if we don't do this, insertion of instructions on
956 the fallthru edge might misbehave. See PR58670. */
958 && label_to_block_fn (cfun
, TREE_VALUE (tail
)) == fallthru_bb
)
960 if (fallthru_label
== NULL_RTX
)
961 fallthru_label
= gen_label_rtx ();
965 r
= label_rtx (TREE_VALUE (tail
));
966 ASM_OPERANDS_LABEL (body
, i
) = gen_rtx_LABEL_REF (Pmode
, r
);
969 generating_concat_p
= old_generating_concat_p
;
971 /* Now, for each output, construct an rtx
972 (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER
973 ARGVEC CONSTRAINTS OPNAMES))
974 If there is more than one, put them inside a PARALLEL. */
976 if (nlabels
> 0 && nclobbers
== 0)
978 gcc_assert (noutputs
== 0);
979 emit_jump_insn (body
);
981 else if (noutputs
== 0 && nclobbers
== 0)
983 /* No output operands: put in a raw ASM_OPERANDS rtx. */
986 else if (noutputs
== 1 && nclobbers
== 0)
988 ASM_OPERANDS_OUTPUT_CONSTRAINT (body
) = ggc_strdup (constraints
[0]);
989 emit_insn (gen_rtx_SET (VOIDmode
, output_rtx
[0], body
));
999 body
= gen_rtx_PARALLEL (VOIDmode
, rtvec_alloc (num
+ nclobbers
));
1001 /* For each output operand, store a SET. */
1002 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
1004 XVECEXP (body
, 0, i
)
1005 = gen_rtx_SET (VOIDmode
,
1007 gen_rtx_ASM_OPERANDS
1008 (GET_MODE (output_rtx
[i
]),
1009 ggc_strdup (TREE_STRING_POINTER (string
)),
1010 ggc_strdup (constraints
[i
]),
1011 i
, argvec
, constraintvec
, labelvec
, locus
));
1013 MEM_VOLATILE_P (SET_SRC (XVECEXP (body
, 0, i
))) = vol
;
1016 /* If there are no outputs (but there are some clobbers)
1017 store the bare ASM_OPERANDS into the PARALLEL. */
1020 XVECEXP (body
, 0, i
++) = obody
;
1022 /* Store (clobber REG) for each clobbered register specified. */
1024 for (tail
= clobbers
; tail
; tail
= TREE_CHAIN (tail
))
1026 const char *regname
= TREE_STRING_POINTER (TREE_VALUE (tail
));
1028 int j
= decode_reg_name_and_count (regname
, &nregs
);
1033 if (j
== -3) /* `cc', which is not a register */
1036 if (j
== -4) /* `memory', don't cache memory across asm */
1038 XVECEXP (body
, 0, i
++)
1039 = gen_rtx_CLOBBER (VOIDmode
,
1042 gen_rtx_SCRATCH (VOIDmode
)));
1046 /* Ignore unknown register, error already signaled. */
1050 for (reg
= j
; reg
< j
+ nregs
; reg
++)
1052 /* Use QImode since that's guaranteed to clobber just
1054 clobbered_reg
= gen_rtx_REG (QImode
, reg
);
1056 /* Do sanity check for overlap between clobbers and
1057 respectively input and outputs that hasn't been
1058 handled. Such overlap should have been detected and
1060 if (!clobber_conflict_found
)
1064 /* We test the old body (obody) contents to avoid
1065 tripping over the under-construction body. */
1066 for (opno
= 0; opno
< noutputs
; opno
++)
1067 if (reg_overlap_mentioned_p (clobbered_reg
,
1070 ("asm clobber conflict with output operand");
1072 for (opno
= 0; opno
< ninputs
- ninout
; opno
++)
1073 if (reg_overlap_mentioned_p (clobbered_reg
,
1074 ASM_OPERANDS_INPUT (obody
,
1077 ("asm clobber conflict with input operand");
1080 XVECEXP (body
, 0, i
++)
1081 = gen_rtx_CLOBBER (VOIDmode
, clobbered_reg
);
1086 emit_jump_insn (body
);
1092 emit_label (fallthru_label
);
1094 /* For any outputs that needed reloading into registers, spill them
1095 back to where they belong. */
1096 for (i
= 0; i
< noutputs
; ++i
)
1097 if (real_output_rtx
[i
])
1098 emit_move_insn (real_output_rtx
[i
], output_rtx
[i
]);
1100 crtl
->has_asm_statement
= 1;
1105 expand_asm_stmt (gimple stmt
)
1108 tree outputs
, tail
, t
;
1112 tree str
, out
, in
, cl
, labels
;
1113 location_t locus
= gimple_location (stmt
);
1114 basic_block fallthru_bb
= NULL
;
1116 /* Meh... convert the gimple asm operands into real tree lists.
1117 Eventually we should make all routines work on the vectors instead
1118 of relying on TREE_CHAIN. */
1120 n
= gimple_asm_noutputs (stmt
);
1123 t
= out
= gimple_asm_output_op (stmt
, 0);
1124 for (i
= 1; i
< n
; i
++)
1125 t
= TREE_CHAIN (t
) = gimple_asm_output_op (stmt
, i
);
1129 n
= gimple_asm_ninputs (stmt
);
1132 t
= in
= gimple_asm_input_op (stmt
, 0);
1133 for (i
= 1; i
< n
; i
++)
1134 t
= TREE_CHAIN (t
) = gimple_asm_input_op (stmt
, i
);
1138 n
= gimple_asm_nclobbers (stmt
);
1141 t
= cl
= gimple_asm_clobber_op (stmt
, 0);
1142 for (i
= 1; i
< n
; i
++)
1143 t
= TREE_CHAIN (t
) = gimple_asm_clobber_op (stmt
, i
);
1147 n
= gimple_asm_nlabels (stmt
);
1150 edge fallthru
= find_fallthru_edge (gimple_bb (stmt
)->succs
);
1152 fallthru_bb
= fallthru
->dest
;
1153 t
= labels
= gimple_asm_label_op (stmt
, 0);
1154 for (i
= 1; i
< n
; i
++)
1155 t
= TREE_CHAIN (t
) = gimple_asm_label_op (stmt
, i
);
1158 s
= gimple_asm_string (stmt
);
1159 str
= build_string (strlen (s
), s
);
1161 if (gimple_asm_input_p (stmt
))
1163 expand_asm_loc (str
, gimple_asm_volatile_p (stmt
), locus
);
1168 noutputs
= gimple_asm_noutputs (stmt
);
1169 /* o[I] is the place that output number I should be written. */
1170 o
= (tree
*) alloca (noutputs
* sizeof (tree
));
1172 /* Record the contents of OUTPUTS before it is modified. */
1173 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
1174 o
[i
] = TREE_VALUE (tail
);
1176 /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of
1177 OUTPUTS some trees for where the values were actually stored. */
1178 expand_asm_operands (str
, outputs
, in
, cl
, labels
, fallthru_bb
,
1179 gimple_asm_volatile_p (stmt
), locus
);
1181 /* Copy all the intermediate outputs into the specified outputs. */
1182 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
1184 if (o
[i
] != TREE_VALUE (tail
))
1186 expand_assignment (o
[i
], TREE_VALUE (tail
), false);
1189 /* Restore the original value so that it's correct the next
1190 time we expand this function. */
1191 TREE_VALUE (tail
) = o
[i
];
1196 /* A subroutine of expand_asm_operands. Check that all operands have
1197 the same number of alternatives. Return true if so. */
1200 check_operand_nalternatives (tree outputs
, tree inputs
)
1202 if (outputs
|| inputs
)
1204 tree tmp
= TREE_PURPOSE (outputs
? outputs
: inputs
);
1206 = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp
)));
1209 if (nalternatives
+ 1 > MAX_RECOG_ALTERNATIVES
)
1211 error ("too many alternatives in %<asm%>");
1218 const char *constraint
1219 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp
)));
1221 if (n_occurrences (',', constraint
) != nalternatives
)
1223 error ("operand constraints for %<asm%> differ "
1224 "in number of alternatives");
1228 if (TREE_CHAIN (tmp
))
1229 tmp
= TREE_CHAIN (tmp
);
1231 tmp
= next
, next
= 0;
1238 /* A subroutine of expand_asm_operands. Check that all operand names
1239 are unique. Return true if so. We rely on the fact that these names
1240 are identifiers, and so have been canonicalized by get_identifier,
1241 so all we need are pointer comparisons. */
1244 check_unique_operand_names (tree outputs
, tree inputs
, tree labels
)
1246 tree i
, j
, i_name
= NULL_TREE
;
1248 for (i
= outputs
; i
; i
= TREE_CHAIN (i
))
1250 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
1254 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
1255 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
1259 for (i
= inputs
; i
; i
= TREE_CHAIN (i
))
1261 i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
1265 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
1266 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
1268 for (j
= outputs
; j
; j
= TREE_CHAIN (j
))
1269 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
1273 for (i
= labels
; i
; i
= TREE_CHAIN (i
))
1275 i_name
= TREE_PURPOSE (i
);
1279 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
1280 if (simple_cst_equal (i_name
, TREE_PURPOSE (j
)))
1282 for (j
= inputs
; j
; j
= TREE_CHAIN (j
))
1283 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
1290 error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name
));
1294 /* A subroutine of expand_asm_operands. Resolve the names of the operands
1295 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
1296 STRING and in the constraints to those numbers. */
1299 resolve_asm_operand_names (tree string
, tree outputs
, tree inputs
, tree labels
)
1306 check_unique_operand_names (outputs
, inputs
, labels
);
1308 /* Substitute [<name>] in input constraint strings. There should be no
1309 named operands in output constraints. */
1310 for (t
= inputs
; t
; t
= TREE_CHAIN (t
))
1312 c
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
1313 if (strchr (c
, '[') != NULL
)
1315 p
= buffer
= xstrdup (c
);
1316 while ((p
= strchr (p
, '[')) != NULL
)
1317 p
= resolve_operand_name_1 (p
, outputs
, inputs
, NULL
);
1318 TREE_VALUE (TREE_PURPOSE (t
))
1319 = build_string (strlen (buffer
), buffer
);
1324 /* Now check for any needed substitutions in the template. */
1325 c
= TREE_STRING_POINTER (string
);
1326 while ((c
= strchr (c
, '%')) != NULL
)
1330 else if (ISALPHA (c
[1]) && c
[2] == '[')
1334 c
+= 1 + (c
[1] == '%');
1341 /* OK, we need to make a copy so we can perform the substitutions.
1342 Assume that we will not need extra space--we get to remove '['
1343 and ']', which means we cannot have a problem until we have more
1344 than 999 operands. */
1345 buffer
= xstrdup (TREE_STRING_POINTER (string
));
1346 p
= buffer
+ (c
- TREE_STRING_POINTER (string
));
1348 while ((p
= strchr (p
, '%')) != NULL
)
1352 else if (ISALPHA (p
[1]) && p
[2] == '[')
1356 p
+= 1 + (p
[1] == '%');
1360 p
= resolve_operand_name_1 (p
, outputs
, inputs
, labels
);
1363 string
= build_string (strlen (buffer
), buffer
);
1370 /* A subroutine of resolve_operand_names. P points to the '[' for a
1371 potential named operand of the form [<name>]. In place, replace
1372 the name and brackets with a number. Return a pointer to the
1373 balance of the string after substitution. */
1376 resolve_operand_name_1 (char *p
, tree outputs
, tree inputs
, tree labels
)
1382 /* Collect the operand name. */
1383 q
= strchr (++p
, ']');
1386 error ("missing close brace for named operand");
1387 return strchr (p
, '\0');
1391 /* Resolve the name to a number. */
1392 for (op
= 0, t
= outputs
; t
; t
= TREE_CHAIN (t
), op
++)
1394 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
1395 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
1398 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), op
++)
1400 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
1401 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
1404 for (t
= labels
; t
; t
= TREE_CHAIN (t
), op
++)
1406 tree name
= TREE_PURPOSE (t
);
1407 if (name
&& strcmp (TREE_STRING_POINTER (name
), p
) == 0)
1411 error ("undefined named operand %qs", identifier_to_locale (p
));
1415 /* Replace the name with the number. Unfortunately, not all libraries
1416 get the return value of sprintf correct, so search for the end of the
1417 generated string by hand. */
1418 sprintf (--p
, "%d", op
);
1419 p
= strchr (p
, '\0');
1421 /* Verify the no extra buffer space assumption. */
1422 gcc_assert (p
<= q
);
1424 /* Shift the rest of the buffer down to fill the gap. */
1425 memmove (p
, q
+ 1, strlen (q
+ 1) + 1);
1430 /* Generate RTL to return from the current function, with no value.
1431 (That is, we do not do anything about returning any value.) */
1434 expand_null_return (void)
1436 /* If this function was declared to return a value, but we
1437 didn't, clobber the return registers so that they are not
1438 propagated live to the rest of the function. */
1439 clobber_return_register ();
1441 expand_null_return_1 ();
1444 /* Generate RTL to return directly from the current function.
1445 (That is, we bypass any return value.) */
1448 expand_naked_return (void)
1452 clear_pending_stack_adjust ();
1453 do_pending_stack_adjust ();
1455 end_label
= naked_return_label
;
1457 end_label
= naked_return_label
= gen_label_rtx ();
1459 emit_jump (end_label
);
1462 /* Generate RTL to return from the current function, with value VAL. */
1465 expand_value_return (rtx val
)
1467 /* Copy the value to the return location unless it's already there. */
1469 tree decl
= DECL_RESULT (current_function_decl
);
1470 rtx return_reg
= DECL_RTL (decl
);
1471 if (return_reg
!= val
)
1473 tree funtype
= TREE_TYPE (current_function_decl
);
1474 tree type
= TREE_TYPE (decl
);
1475 int unsignedp
= TYPE_UNSIGNED (type
);
1476 enum machine_mode old_mode
= DECL_MODE (decl
);
1477 enum machine_mode mode
;
1478 if (DECL_BY_REFERENCE (decl
))
1479 mode
= promote_function_mode (type
, old_mode
, &unsignedp
, funtype
, 2);
1481 mode
= promote_function_mode (type
, old_mode
, &unsignedp
, funtype
, 1);
1483 if (mode
!= old_mode
)
1484 val
= convert_modes (mode
, old_mode
, val
, unsignedp
);
1486 if (GET_CODE (return_reg
) == PARALLEL
)
1487 emit_group_load (return_reg
, val
, type
, int_size_in_bytes (type
));
1489 emit_move_insn (return_reg
, val
);
1492 expand_null_return_1 ();
1495 /* Output a return with no value. */
1498 expand_null_return_1 (void)
1500 clear_pending_stack_adjust ();
1501 do_pending_stack_adjust ();
1502 emit_jump (return_label
);
1505 /* Generate RTL to evaluate the expression RETVAL and return it
1506 from the current function. */
1509 expand_return (tree retval
)
1515 /* If function wants no value, give it none. */
1516 if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl
))) == VOID_TYPE
)
1518 expand_normal (retval
);
1519 expand_null_return ();
1523 if (retval
== error_mark_node
)
1525 /* Treat this like a return of no value from a function that
1527 expand_null_return ();
1530 else if ((TREE_CODE (retval
) == MODIFY_EXPR
1531 || TREE_CODE (retval
) == INIT_EXPR
)
1532 && TREE_CODE (TREE_OPERAND (retval
, 0)) == RESULT_DECL
)
1533 retval_rhs
= TREE_OPERAND (retval
, 1);
1535 retval_rhs
= retval
;
1537 result_rtl
= DECL_RTL (DECL_RESULT (current_function_decl
));
1539 /* If we are returning the RESULT_DECL, then the value has already
1540 been stored into it, so we don't have to do anything special. */
1541 if (TREE_CODE (retval_rhs
) == RESULT_DECL
)
1542 expand_value_return (result_rtl
);
1544 /* If the result is an aggregate that is being returned in one (or more)
1545 registers, load the registers here. */
1547 else if (retval_rhs
!= 0
1548 && TYPE_MODE (TREE_TYPE (retval_rhs
)) == BLKmode
1549 && REG_P (result_rtl
))
1551 val
= copy_blkmode_to_reg (GET_MODE (result_rtl
), retval_rhs
);
1554 /* Use the mode of the result value on the return register. */
1555 PUT_MODE (result_rtl
, GET_MODE (val
));
1556 expand_value_return (val
);
1559 expand_null_return ();
1561 else if (retval_rhs
!= 0
1562 && !VOID_TYPE_P (TREE_TYPE (retval_rhs
))
1563 && (REG_P (result_rtl
)
1564 || (GET_CODE (result_rtl
) == PARALLEL
)))
1566 /* Calculate the return value into a temporary (usually a pseudo
1568 tree ot
= TREE_TYPE (DECL_RESULT (current_function_decl
));
1569 tree nt
= build_qualified_type (ot
, TYPE_QUALS (ot
) | TYPE_QUAL_CONST
);
1571 val
= assign_temp (nt
, 0, 1);
1572 val
= expand_expr (retval_rhs
, val
, GET_MODE (val
), EXPAND_NORMAL
);
1573 val
= force_not_mem (val
);
1574 /* Return the calculated value. */
1575 expand_value_return (val
);
1579 /* No hard reg used; calculate value into hard return reg. */
1580 expand_expr (retval
, const0_rtx
, VOIDmode
, EXPAND_NORMAL
);
1581 expand_value_return (result_rtl
);
1586 /* Emit code to save the current value of stack. */
1588 expand_stack_save (void)
1592 do_pending_stack_adjust ();
1593 emit_stack_save (SAVE_BLOCK
, &ret
);
1597 /* Emit code to restore the current value of stack. */
1599 expand_stack_restore (tree var
)
1601 rtx prev
, sa
= expand_normal (var
);
1603 sa
= convert_memory_address (Pmode
, sa
);
1605 prev
= get_last_insn ();
1606 emit_stack_restore (SAVE_BLOCK
, sa
);
1607 fixup_args_size_notes (prev
, get_last_insn (), 0);
1610 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. PROB
1611 is the probability of jumping to LABEL. */
1613 do_jump_if_equal (enum machine_mode mode
, rtx op0
, rtx op1
, rtx label
,
1614 int unsignedp
, int prob
)
1616 gcc_assert (prob
<= REG_BR_PROB_BASE
);
1617 do_compare_rtx_and_jump (op0
, op1
, EQ
, unsignedp
, mode
,
1618 NULL_RTX
, NULL_RTX
, label
, prob
);
1621 /* Do the insertion of a case label into case_list. The labels are
1622 fed to us in descending order from the sorted vector of case labels used
1623 in the tree part of the middle end. So the list we construct is
1624 sorted in ascending order.
1626 LABEL is the case label to be inserted. LOW and HIGH are the bounds
1627 against which the index is compared to jump to LABEL and PROB is the
1628 estimated probability LABEL is reached from the switch statement. */
1630 static struct case_node
*
1631 add_case_node (struct case_node
*head
, tree low
, tree high
,
1632 tree label
, int prob
, alloc_pool case_node_pool
)
1634 struct case_node
*r
;
1636 gcc_checking_assert (low
);
1637 gcc_checking_assert (high
&& (TREE_TYPE (low
) == TREE_TYPE (high
)));
1639 /* Add this label to the chain. */
1640 r
= (struct case_node
*) pool_alloc (case_node_pool
);
1643 r
->code_label
= label
;
1644 r
->parent
= r
->left
= NULL
;
1646 r
->subtree_prob
= prob
;
1651 /* Dump ROOT, a list or tree of case nodes, to file. */
1654 dump_case_nodes (FILE *f
, struct case_node
*root
,
1655 int indent_step
, int indent_level
)
1657 HOST_WIDE_INT low
, high
;
1663 dump_case_nodes (f
, root
->left
, indent_step
, indent_level
);
1665 low
= tree_low_cst (root
->low
, 0);
1666 high
= tree_low_cst (root
->high
, 0);
1670 fprintf (f
, "%*s" HOST_WIDE_INT_PRINT_DEC
,
1671 indent_step
* indent_level
, "", low
);
1673 fprintf (f
, "%*s" HOST_WIDE_INT_PRINT_DEC
" ... " HOST_WIDE_INT_PRINT_DEC
,
1674 indent_step
* indent_level
, "", low
, high
);
1677 dump_case_nodes (f
, root
->right
, indent_step
, indent_level
);
1681 #define HAVE_casesi 0
1684 #ifndef HAVE_tablejump
1685 #define HAVE_tablejump 0
1688 /* Return the smallest number of different values for which it is best to use a
1689 jump-table instead of a tree of conditional branches. */
1692 case_values_threshold (void)
1694 unsigned int threshold
= PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD
);
1697 threshold
= targetm
.case_values_threshold ();
1702 /* Return true if a switch should be expanded as a decision tree.
1703 RANGE is the difference between highest and lowest case.
1704 UNIQ is number of unique case node targets, not counting the default case.
1705 COUNT is the number of comparisons needed, not counting the default case. */
1708 expand_switch_as_decision_tree_p (tree range
,
1709 unsigned int uniq ATTRIBUTE_UNUSED
,
1714 /* If neither casesi or tablejump is available, or flag_jump_tables
1715 over-ruled us, we really have no choice. */
1716 if (!HAVE_casesi
&& !HAVE_tablejump
)
1718 if (!flag_jump_tables
)
1720 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
1725 /* If the switch is relatively small such that the cost of one
1726 indirect jump on the target are higher than the cost of a
1727 decision tree, go with the decision tree.
1729 If range of values is much bigger than number of values,
1730 or if it is too large to represent in a HOST_WIDE_INT,
1731 make a sequence of conditional branches instead of a dispatch.
1733 The definition of "much bigger" depends on whether we are
1734 optimizing for size or for speed. If the former, the maximum
1735 ratio range/count = 3, because this was found to be the optimal
1736 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
1737 10 is much older, and was probably selected after an extensive
1738 benchmarking investigation on numerous platforms. Or maybe it
1739 just made sense to someone at some point in the history of GCC,
1741 max_ratio
= optimize_insn_for_size_p () ? 3 : 10;
1742 if (count
< case_values_threshold ()
1743 || ! host_integerp (range
, /*pos=*/1)
1744 || compare_tree_int (range
, max_ratio
* count
) > 0)
1750 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
1751 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
1752 DEFAULT_PROB is the estimated probability that it jumps to
1755 We generate a binary decision tree to select the appropriate target
1756 code. This is done as follows:
1758 If the index is a short or char that we do not have
1759 an insn to handle comparisons directly, convert it to
1760 a full integer now, rather than letting each comparison
1761 generate the conversion.
1763 Load the index into a register.
1765 The list of cases is rearranged into a binary tree,
1766 nearly optimal assuming equal probability for each case.
1768 The tree is transformed into RTL, eliminating redundant
1769 test conditions at the same time.
1771 If program flow could reach the end of the decision tree
1772 an unconditional jump to the default code is emitted.
1774 The above process is unaware of the CFG. The caller has to fix up
1775 the CFG itself. This is done in cfgexpand.c. */
1778 emit_case_decision_tree (tree index_expr
, tree index_type
,
1779 struct case_node
*case_list
, rtx default_label
,
1782 rtx index
= expand_normal (index_expr
);
1784 if (GET_MODE_CLASS (GET_MODE (index
)) == MODE_INT
1785 && ! have_insn_for (COMPARE
, GET_MODE (index
)))
1787 int unsignedp
= TYPE_UNSIGNED (index_type
);
1788 enum machine_mode wider_mode
;
1789 for (wider_mode
= GET_MODE (index
); wider_mode
!= VOIDmode
;
1790 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
1791 if (have_insn_for (COMPARE
, wider_mode
))
1793 index
= convert_to_mode (wider_mode
, index
, unsignedp
);
1798 do_pending_stack_adjust ();
1802 index
= copy_to_reg (index
);
1803 if (TREE_CODE (index_expr
) == SSA_NAME
)
1804 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr
), index
);
1807 balance_case_nodes (&case_list
, NULL
);
1809 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1811 int indent_step
= ceil_log2 (TYPE_PRECISION (index_type
)) + 2;
1812 fprintf (dump_file
, ";; Expanding GIMPLE switch as decision tree:\n");
1813 dump_case_nodes (dump_file
, case_list
, indent_step
, 0);
1816 emit_case_nodes (index
, case_list
, default_label
, default_prob
, index_type
);
1818 emit_jump (default_label
);
1821 /* Return the sum of probabilities of outgoing edges of basic block BB. */
1824 get_outgoing_edge_probs (basic_block bb
)
1831 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1832 prob_sum
+= e
->probability
;
1836 /* Computes the conditional probability of jumping to a target if the branch
1837 instruction is executed.
1838 TARGET_PROB is the estimated probability of jumping to a target relative
1839 to some basic block BB.
1840 BASE_PROB is the probability of reaching the branch instruction relative
1841 to the same basic block BB. */
1844 conditional_probability (int target_prob
, int base_prob
)
1848 gcc_assert (target_prob
>= 0);
1849 gcc_assert (target_prob
<= base_prob
);
1850 return GCOV_COMPUTE_SCALE (target_prob
, base_prob
);
1855 /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
1856 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
1857 MINVAL, MAXVAL, and RANGE are the extrema and range of the case
1858 labels in CASE_LIST. STMT_BB is the basic block containing the statement.
1860 First, a jump insn is emitted. First we try "casesi". If that
1861 fails, try "tablejump". A target *must* have one of them (or both).
1863 Then, a table with the target labels is emitted.
1865 The process is unaware of the CFG. The caller has to fix up
1866 the CFG itself. This is done in cfgexpand.c. */
1869 emit_case_dispatch_table (tree index_expr
, tree index_type
,
1870 struct case_node
*case_list
, rtx default_label
,
1871 tree minval
, tree maxval
, tree range
,
1872 basic_block stmt_bb
)
1875 struct case_node
*n
;
1877 rtx fallback_label
= label_rtx (case_list
->code_label
);
1878 rtx table_label
= gen_label_rtx ();
1879 bool has_gaps
= false;
1880 edge default_edge
= stmt_bb
? EDGE_SUCC (stmt_bb
, 0) : NULL
;
1881 int default_prob
= default_edge
? default_edge
->probability
: 0;
1882 int base
= get_outgoing_edge_probs (stmt_bb
);
1883 bool try_with_tablejump
= false;
1885 int new_default_prob
= conditional_probability (default_prob
,
1888 if (! try_casesi (index_type
, index_expr
, minval
, range
,
1889 table_label
, default_label
, fallback_label
,
1892 /* Index jumptables from zero for suitable values of minval to avoid
1893 a subtraction. For the rationale see:
1894 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */
1895 if (optimize_insn_for_speed_p ()
1896 && compare_tree_int (minval
, 0) > 0
1897 && compare_tree_int (minval
, 3) < 0)
1899 minval
= build_int_cst (index_type
, 0);
1903 try_with_tablejump
= true;
1906 /* Get table of labels to jump to, in order of case index. */
1908 ncases
= tree_low_cst (range
, 0) + 1;
1909 labelvec
= XALLOCAVEC (rtx
, ncases
);
1910 memset (labelvec
, 0, ncases
* sizeof (rtx
));
1912 for (n
= case_list
; n
; n
= n
->right
)
1914 /* Compute the low and high bounds relative to the minimum
1915 value since that should fit in a HOST_WIDE_INT while the
1916 actual values may not. */
1918 = tree_low_cst (fold_build2 (MINUS_EXPR
, index_type
,
1919 n
->low
, minval
), 1);
1920 HOST_WIDE_INT i_high
1921 = tree_low_cst (fold_build2 (MINUS_EXPR
, index_type
,
1922 n
->high
, minval
), 1);
1925 for (i
= i_low
; i
<= i_high
; i
++)
1927 = gen_rtx_LABEL_REF (Pmode
, label_rtx (n
->code_label
));
1930 /* Fill in the gaps with the default. We may have gaps at
1931 the beginning if we tried to avoid the minval subtraction,
1932 so substitute some label even if the default label was
1933 deemed unreachable. */
1935 default_label
= fallback_label
;
1936 for (i
= 0; i
< ncases
; i
++)
1937 if (labelvec
[i
] == 0)
1940 labelvec
[i
] = gen_rtx_LABEL_REF (Pmode
, default_label
);
1945 /* There is at least one entry in the jump table that jumps
1946 to default label. The default label can either be reached
1947 through the indirect jump or the direct conditional jump
1948 before that. Split the probability of reaching the
1949 default label among these two jumps. */
1950 new_default_prob
= conditional_probability (default_prob
/2,
1953 base
-= default_prob
;
1957 base
-= default_prob
;
1962 default_edge
->probability
= default_prob
;
1964 /* We have altered the probability of the default edge. So the probabilities
1965 of all other edges need to be adjusted so that it sums up to
1966 REG_BR_PROB_BASE. */
1971 FOR_EACH_EDGE (e
, ei
, stmt_bb
->succs
)
1972 e
->probability
= GCOV_COMPUTE_SCALE (e
->probability
, base
);
1975 if (try_with_tablejump
)
1977 bool ok
= try_tablejump (index_type
, index_expr
, minval
, range
,
1978 table_label
, default_label
, new_default_prob
);
1981 /* Output the table. */
1982 emit_label (table_label
);
1984 if (CASE_VECTOR_PC_RELATIVE
|| flag_pic
)
1985 emit_jump_table_data (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE
,
1986 gen_rtx_LABEL_REF (Pmode
,
1988 gen_rtvec_v (ncases
, labelvec
),
1989 const0_rtx
, const0_rtx
));
1991 emit_jump_table_data (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE
,
1992 gen_rtvec_v (ncases
, labelvec
)));
1994 /* Record no drop-through after the table. */
1998 /* Reset the aux field of all outgoing edges of basic block BB. */
2001 reset_out_edges_aux (basic_block bb
)
2005 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2009 /* Compute the number of case labels that correspond to each outgoing edge of
2010 STMT. Record this information in the aux field of the edge. */
2013 compute_cases_per_edge (gimple stmt
)
2015 basic_block bb
= gimple_bb (stmt
);
2016 reset_out_edges_aux (bb
);
2017 int ncases
= gimple_switch_num_labels (stmt
);
2018 for (int i
= ncases
- 1; i
>= 1; --i
)
2020 tree elt
= gimple_switch_label (stmt
, i
);
2021 tree lab
= CASE_LABEL (elt
);
2022 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
2023 edge case_edge
= find_edge (bb
, case_bb
);
2024 case_edge
->aux
= (void *)((intptr_t)(case_edge
->aux
) + 1);
2028 /* Terminate a case (Pascal/Ada) or switch (C) statement
2029 in which ORIG_INDEX is the expression to be tested.
2030 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
2031 type as given in the source before any compiler conversions.
2032 Generate the code to test it and jump to the right place. */
2035 expand_case (gimple stmt
)
2037 tree minval
= NULL_TREE
, maxval
= NULL_TREE
, range
= NULL_TREE
;
2038 rtx default_label
= NULL_RTX
;
2039 unsigned int count
, uniq
;
2041 int ncases
= gimple_switch_num_labels (stmt
);
2042 tree index_expr
= gimple_switch_index (stmt
);
2043 tree index_type
= TREE_TYPE (index_expr
);
2045 basic_block bb
= gimple_bb (stmt
);
2047 /* A list of case labels; it is first built as a list and it may then
2048 be rearranged into a nearly balanced binary tree. */
2049 struct case_node
*case_list
= 0;
2051 /* A pool for case nodes. */
2052 alloc_pool case_node_pool
;
2054 /* An ERROR_MARK occurs for various reasons including invalid data type.
2055 ??? Can this still happen, with GIMPLE and all? */
2056 if (index_type
== error_mark_node
)
2059 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
2060 expressions being INTEGER_CST. */
2061 gcc_assert (TREE_CODE (index_expr
) != INTEGER_CST
);
2063 case_node_pool
= create_alloc_pool ("struct case_node pool",
2064 sizeof (struct case_node
),
2067 do_pending_stack_adjust ();
2069 /* Find the default case target label. */
2070 default_label
= label_rtx (CASE_LABEL (gimple_switch_default_label (stmt
)));
2071 edge default_edge
= EDGE_SUCC (bb
, 0);
2072 int default_prob
= default_edge
->probability
;
2074 /* Get upper and lower bounds of case values. */
2075 elt
= gimple_switch_label (stmt
, 1);
2076 minval
= fold_convert (index_type
, CASE_LOW (elt
));
2077 elt
= gimple_switch_label (stmt
, ncases
- 1);
2078 if (CASE_HIGH (elt
))
2079 maxval
= fold_convert (index_type
, CASE_HIGH (elt
));
2081 maxval
= fold_convert (index_type
, CASE_LOW (elt
));
2083 /* Compute span of values. */
2084 range
= fold_build2 (MINUS_EXPR
, index_type
, maxval
, minval
);
2086 /* Listify the labels queue and gather some numbers to decide
2087 how to expand this switch(). */
2090 struct pointer_set_t
*seen_labels
= pointer_set_create ();
2091 compute_cases_per_edge (stmt
);
2093 for (i
= ncases
- 1; i
>= 1; --i
)
2095 elt
= gimple_switch_label (stmt
, i
);
2096 tree low
= CASE_LOW (elt
);
2098 tree high
= CASE_HIGH (elt
);
2099 gcc_assert (! high
|| tree_int_cst_lt (low
, high
));
2100 tree lab
= CASE_LABEL (elt
);
2102 /* Count the elements.
2103 A range counts double, since it requires two compares. */
2108 /* If we have not seen this label yet, then increase the
2109 number of unique case node targets seen. */
2110 if (!pointer_set_insert (seen_labels
, lab
))
2113 /* The bounds on the case range, LOW and HIGH, have to be converted
2114 to case's index type TYPE. Note that the original type of the
2115 case index in the source code is usually "lost" during
2116 gimplification due to type promotion, but the case labels retain the
2117 original type. Make sure to drop overflow flags. */
2118 low
= fold_convert (index_type
, low
);
2119 if (TREE_OVERFLOW (low
))
2120 low
= build_int_cst_wide (index_type
,
2121 TREE_INT_CST_LOW (low
),
2122 TREE_INT_CST_HIGH (low
));
2124 /* The canonical from of a case label in GIMPLE is that a simple case
2125 has an empty CASE_HIGH. For the casesi and tablejump expanders,
2126 the back ends want simple cases to have high == low. */
2129 high
= fold_convert (index_type
, high
);
2130 if (TREE_OVERFLOW (high
))
2131 high
= build_int_cst_wide (index_type
,
2132 TREE_INT_CST_LOW (high
),
2133 TREE_INT_CST_HIGH (high
));
2135 basic_block case_bb
= label_to_block_fn (cfun
, lab
);
2136 edge case_edge
= find_edge (bb
, case_bb
);
2137 case_list
= add_case_node (
2138 case_list
, low
, high
, lab
,
2139 case_edge
->probability
/ (intptr_t)(case_edge
->aux
),
2142 pointer_set_destroy (seen_labels
);
2143 reset_out_edges_aux (bb
);
2145 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
2146 destination, such as one with a default case only.
2147 It also removes cases that are out of range for the switch
2148 type, so we should never get a zero here. */
2149 gcc_assert (count
> 0);
2151 rtx before_case
= get_last_insn ();
2153 /* Decide how to expand this switch.
2154 The two options at this point are a dispatch table (casesi or
2155 tablejump) or a decision tree. */
2157 if (expand_switch_as_decision_tree_p (range
, uniq
, count
))
2158 emit_case_decision_tree (index_expr
, index_type
,
2159 case_list
, default_label
,
2162 emit_case_dispatch_table (index_expr
, index_type
,
2163 case_list
, default_label
,
2164 minval
, maxval
, range
, bb
);
2166 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
2169 free_alloc_pool (case_node_pool
);
2172 /* Expand the dispatch to a short decrement chain if there are few cases
2173 to dispatch to. Likewise if neither casesi nor tablejump is available,
2174 or if flag_jump_tables is set. Otherwise, expand as a casesi or a
2175 tablejump. The index mode is always the mode of integer_type_node.
2176 Trap if no case matches the index.
2178 DISPATCH_INDEX is the index expression to switch on. It should be a
2179 memory or register operand.
2181 DISPATCH_TABLE is a set of case labels. The set should be sorted in
2182 ascending order, be contiguous, starting with value 0, and contain only
2183 single-valued case labels. */
2186 expand_sjlj_dispatch_table (rtx dispatch_index
,
2187 vec
<tree
> dispatch_table
)
2189 tree index_type
= integer_type_node
;
2190 enum machine_mode index_mode
= TYPE_MODE (index_type
);
2192 int ncases
= dispatch_table
.length ();
2194 do_pending_stack_adjust ();
2195 rtx before_case
= get_last_insn ();
2197 /* Expand as a decrement-chain if there are 5 or fewer dispatch
2198 labels. This covers more than 98% of the cases in libjava,
2199 and seems to be a reasonable compromise between the "old way"
2200 of expanding as a decision tree or dispatch table vs. the "new
2201 way" with decrement chain or dispatch table. */
2202 if (dispatch_table
.length () <= 5
2203 || (!HAVE_casesi
&& !HAVE_tablejump
)
2204 || !flag_jump_tables
)
2206 /* Expand the dispatch as a decrement chain:
2208 "switch(index) {case 0: do_0; case 1: do_1; ...; case N: do_N;}"
2212 if (index == 0) do_0; else index--;
2213 if (index == 0) do_1; else index--;
2215 if (index == 0) do_N; else index--;
2217 This is more efficient than a dispatch table on most machines.
2218 The last "index--" is redundant but the code is trivially dead
2219 and will be cleaned up by later passes. */
2220 rtx index
= copy_to_mode_reg (index_mode
, dispatch_index
);
2221 rtx zero
= CONST0_RTX (index_mode
);
2222 for (int i
= 0; i
< ncases
; i
++)
2224 tree elt
= dispatch_table
[i
];
2225 rtx lab
= label_rtx (CASE_LABEL (elt
));
2226 do_jump_if_equal (index_mode
, index
, zero
, lab
, 0, -1);
2227 force_expand_binop (index_mode
, sub_optab
,
2228 index
, CONST1_RTX (index_mode
),
2229 index
, 0, OPTAB_DIRECT
);
2234 /* Similar to expand_case, but much simpler. */
2235 struct case_node
*case_list
= 0;
2236 alloc_pool case_node_pool
= create_alloc_pool ("struct sjlj_case pool",
2237 sizeof (struct case_node
),
2239 tree index_expr
= make_tree (index_type
, dispatch_index
);
2240 tree minval
= build_int_cst (index_type
, 0);
2241 tree maxval
= CASE_LOW (dispatch_table
.last ());
2242 tree range
= maxval
;
2243 rtx default_label
= gen_label_rtx ();
2245 for (int i
= ncases
- 1; i
>= 0; --i
)
2247 tree elt
= dispatch_table
[i
];
2248 tree low
= CASE_LOW (elt
);
2249 tree lab
= CASE_LABEL (elt
);
2250 case_list
= add_case_node (case_list
, low
, low
, lab
, 0, case_node_pool
);
2253 emit_case_dispatch_table (index_expr
, index_type
,
2254 case_list
, default_label
,
2255 minval
, maxval
, range
,
2256 BLOCK_FOR_INSN (before_case
));
2257 emit_label (default_label
);
2258 free_alloc_pool (case_node_pool
);
2261 /* Dispatching something not handled? Trap! */
2262 expand_builtin_trap ();
2264 reorder_insns (NEXT_INSN (before_case
), get_last_insn (), before_case
);
2270 /* Take an ordered list of case nodes
2271 and transform them into a near optimal binary tree,
2272 on the assumption that any target code selection value is as
2273 likely as any other.
2275 The transformation is performed by splitting the ordered
2276 list into two equal sections plus a pivot. The parts are
2277 then attached to the pivot as left and right branches. Each
2278 branch is then transformed recursively. */
2281 balance_case_nodes (case_node_ptr
*head
, case_node_ptr parent
)
2293 /* Count the number of entries on branch. Also count the ranges. */
2297 if (!tree_int_cst_equal (np
->low
, np
->high
))
2306 /* Split this list if it is long enough for that to help. */
2310 /* If there are just three nodes, split at the middle one. */
2312 npp
= &(*npp
)->right
;
2315 /* Find the place in the list that bisects the list's total cost,
2316 where ranges count as 2.
2317 Here I gets half the total cost. */
2318 i
= (i
+ ranges
+ 1) / 2;
2321 /* Skip nodes while their cost does not reach that amount. */
2322 if (!tree_int_cst_equal ((*npp
)->low
, (*npp
)->high
))
2327 npp
= &(*npp
)->right
;
2332 np
->parent
= parent
;
2335 /* Optimize each of the two split parts. */
2336 balance_case_nodes (&np
->left
, np
);
2337 balance_case_nodes (&np
->right
, np
);
2338 np
->subtree_prob
= np
->prob
;
2339 np
->subtree_prob
+= np
->left
->subtree_prob
;
2340 np
->subtree_prob
+= np
->right
->subtree_prob
;
2344 /* Else leave this branch as one level,
2345 but fill in `parent' fields. */
2347 np
->parent
= parent
;
2348 np
->subtree_prob
= np
->prob
;
2349 for (; np
->right
; np
= np
->right
)
2351 np
->right
->parent
= np
;
2352 (*head
)->subtree_prob
+= np
->right
->subtree_prob
;
2358 /* Search the parent sections of the case node tree
2359 to see if a test for the lower bound of NODE would be redundant.
2360 INDEX_TYPE is the type of the index expression.
2362 The instructions to generate the case decision tree are
2363 output in the same order as nodes are processed so it is
2364 known that if a parent node checks the range of the current
2365 node minus one that the current node is bounded at its lower
2366 span. Thus the test would be redundant. */
2369 node_has_low_bound (case_node_ptr node
, tree index_type
)
2372 case_node_ptr pnode
;
2374 /* If the lower bound of this node is the lowest value in the index type,
2375 we need not test it. */
2377 if (tree_int_cst_equal (node
->low
, TYPE_MIN_VALUE (index_type
)))
2380 /* If this node has a left branch, the value at the left must be less
2381 than that at this node, so it cannot be bounded at the bottom and
2382 we need not bother testing any further. */
2387 low_minus_one
= fold_build2 (MINUS_EXPR
, TREE_TYPE (node
->low
),
2389 build_int_cst (TREE_TYPE (node
->low
), 1));
2391 /* If the subtraction above overflowed, we can't verify anything.
2392 Otherwise, look for a parent that tests our value - 1. */
2394 if (! tree_int_cst_lt (low_minus_one
, node
->low
))
2397 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
2398 if (tree_int_cst_equal (low_minus_one
, pnode
->high
))
2404 /* Search the parent sections of the case node tree
2405 to see if a test for the upper bound of NODE would be redundant.
2406 INDEX_TYPE is the type of the index expression.
2408 The instructions to generate the case decision tree are
2409 output in the same order as nodes are processed so it is
2410 known that if a parent node checks the range of the current
2411 node plus one that the current node is bounded at its upper
2412 span. Thus the test would be redundant. */
2415 node_has_high_bound (case_node_ptr node
, tree index_type
)
2418 case_node_ptr pnode
;
2420 /* If there is no upper bound, obviously no test is needed. */
2422 if (TYPE_MAX_VALUE (index_type
) == NULL
)
2425 /* If the upper bound of this node is the highest value in the type
2426 of the index expression, we need not test against it. */
2428 if (tree_int_cst_equal (node
->high
, TYPE_MAX_VALUE (index_type
)))
2431 /* If this node has a right branch, the value at the right must be greater
2432 than that at this node, so it cannot be bounded at the top and
2433 we need not bother testing any further. */
2438 high_plus_one
= fold_build2 (PLUS_EXPR
, TREE_TYPE (node
->high
),
2440 build_int_cst (TREE_TYPE (node
->high
), 1));
2442 /* If the addition above overflowed, we can't verify anything.
2443 Otherwise, look for a parent that tests our value + 1. */
2445 if (! tree_int_cst_lt (node
->high
, high_plus_one
))
2448 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
2449 if (tree_int_cst_equal (high_plus_one
, pnode
->low
))
2455 /* Search the parent sections of the
2456 case node tree to see if both tests for the upper and lower
2457 bounds of NODE would be redundant. */
2460 node_is_bounded (case_node_ptr node
, tree index_type
)
2462 return (node_has_low_bound (node
, index_type
)
2463 && node_has_high_bound (node
, index_type
));
2467 /* Emit step-by-step code to select a case for the value of INDEX.
2468 The thus generated decision tree follows the form of the
2469 case-node binary tree NODE, whose nodes represent test conditions.
2470 INDEX_TYPE is the type of the index of the switch.
2472 Care is taken to prune redundant tests from the decision tree
2473 by detecting any boundary conditions already checked by
2474 emitted rtx. (See node_has_high_bound, node_has_low_bound
2475 and node_is_bounded, above.)
2477 Where the test conditions can be shown to be redundant we emit
2478 an unconditional jump to the target code. As a further
2479 optimization, the subordinates of a tree node are examined to
2480 check for bounded nodes. In this case conditional and/or
2481 unconditional jumps as a result of the boundary check for the
2482 current node are arranged to target the subordinates associated
2483 code for out of bound conditions on the current node.
2485 We can assume that when control reaches the code generated here,
2486 the index value has already been compared with the parents
2487 of this node, and determined to be on the same side of each parent
2488 as this node is. Thus, if this node tests for the value 51,
2489 and a parent tested for 52, we don't need to consider
2490 the possibility of a value greater than 51. If another parent
2491 tests for the value 50, then this node need not test anything. */
2494 emit_case_nodes (rtx index
, case_node_ptr node
, rtx default_label
,
2495 int default_prob
, tree index_type
)
2497 /* If INDEX has an unsigned type, we must make unsigned branches. */
2498 int unsignedp
= TYPE_UNSIGNED (index_type
);
2500 int prob
= node
->prob
, subtree_prob
= node
->subtree_prob
;
2501 enum machine_mode mode
= GET_MODE (index
);
2502 enum machine_mode imode
= TYPE_MODE (index_type
);
2504 /* Handle indices detected as constant during RTL expansion. */
2505 if (mode
== VOIDmode
)
2508 /* See if our parents have already tested everything for us.
2509 If they have, emit an unconditional jump for this node. */
2510 if (node_is_bounded (node
, index_type
))
2511 emit_jump (label_rtx (node
->code_label
));
2513 else if (tree_int_cst_equal (node
->low
, node
->high
))
2515 probability
= conditional_probability (prob
, subtree_prob
+ default_prob
);
2516 /* Node is single valued. First see if the index expression matches
2517 this node and then check our children, if any. */
2518 do_jump_if_equal (mode
, index
,
2519 convert_modes (mode
, imode
,
2520 expand_normal (node
->low
),
2522 label_rtx (node
->code_label
), unsignedp
, probability
);
2523 /* Since this case is taken at this point, reduce its weight from
2525 subtree_prob
-= prob
;
2526 if (node
->right
!= 0 && node
->left
!= 0)
2528 /* This node has children on both sides.
2529 Dispatch to one side or the other
2530 by comparing the index value with this node's value.
2531 If one subtree is bounded, check that one first,
2532 so we can avoid real branches in the tree. */
2534 if (node_is_bounded (node
->right
, index_type
))
2536 probability
= conditional_probability (
2538 subtree_prob
+ default_prob
);
2539 emit_cmp_and_jump_insns (index
,
2542 expand_normal (node
->high
),
2544 GT
, NULL_RTX
, mode
, unsignedp
,
2545 label_rtx (node
->right
->code_label
),
2547 emit_case_nodes (index
, node
->left
, default_label
, default_prob
,
2551 else if (node_is_bounded (node
->left
, index_type
))
2553 probability
= conditional_probability (
2555 subtree_prob
+ default_prob
);
2556 emit_cmp_and_jump_insns (index
,
2559 expand_normal (node
->high
),
2561 LT
, NULL_RTX
, mode
, unsignedp
,
2562 label_rtx (node
->left
->code_label
),
2564 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
2567 /* If both children are single-valued cases with no
2568 children, finish up all the work. This way, we can save
2569 one ordered comparison. */
2570 else if (tree_int_cst_equal (node
->right
->low
, node
->right
->high
)
2571 && node
->right
->left
== 0
2572 && node
->right
->right
== 0
2573 && tree_int_cst_equal (node
->left
->low
, node
->left
->high
)
2574 && node
->left
->left
== 0
2575 && node
->left
->right
== 0)
2577 /* Neither node is bounded. First distinguish the two sides;
2578 then emit the code for one side at a time. */
2580 /* See if the value matches what the right hand side
2582 probability
= conditional_probability (
2584 subtree_prob
+ default_prob
);
2585 do_jump_if_equal (mode
, index
,
2586 convert_modes (mode
, imode
,
2587 expand_normal (node
->right
->low
),
2589 label_rtx (node
->right
->code_label
),
2590 unsignedp
, probability
);
2592 /* See if the value matches what the left hand side
2594 probability
= conditional_probability (
2596 subtree_prob
+ default_prob
);
2597 do_jump_if_equal (mode
, index
,
2598 convert_modes (mode
, imode
,
2599 expand_normal (node
->left
->low
),
2601 label_rtx (node
->left
->code_label
),
2602 unsignedp
, probability
);
2607 /* Neither node is bounded. First distinguish the two sides;
2608 then emit the code for one side at a time. */
2611 = build_decl (curr_insn_location (),
2612 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
2614 /* The default label could be reached either through the right
2615 subtree or the left subtree. Divide the probability
2617 probability
= conditional_probability (
2618 node
->right
->subtree_prob
+ default_prob
/2,
2619 subtree_prob
+ default_prob
);
2620 /* See if the value is on the right. */
2621 emit_cmp_and_jump_insns (index
,
2624 expand_normal (node
->high
),
2626 GT
, NULL_RTX
, mode
, unsignedp
,
2627 label_rtx (test_label
),
2631 /* Value must be on the left.
2632 Handle the left-hand subtree. */
2633 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
2634 /* If left-hand subtree does nothing,
2637 emit_jump (default_label
);
2639 /* Code branches here for the right-hand subtree. */
2640 expand_label (test_label
);
2641 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
2645 else if (node
->right
!= 0 && node
->left
== 0)
2647 /* Here we have a right child but no left so we issue a conditional
2648 branch to default and process the right child.
2650 Omit the conditional branch to default if the right child
2651 does not have any children and is single valued; it would
2652 cost too much space to save so little time. */
2654 if (node
->right
->right
|| node
->right
->left
2655 || !tree_int_cst_equal (node
->right
->low
, node
->right
->high
))
2657 if (!node_has_low_bound (node
, index_type
))
2659 probability
= conditional_probability (
2661 subtree_prob
+ default_prob
);
2662 emit_cmp_and_jump_insns (index
,
2665 expand_normal (node
->high
),
2667 LT
, NULL_RTX
, mode
, unsignedp
,
2673 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
2677 probability
= conditional_probability (
2678 node
->right
->subtree_prob
,
2679 subtree_prob
+ default_prob
);
2680 /* We cannot process node->right normally
2681 since we haven't ruled out the numbers less than
2682 this node's value. So handle node->right explicitly. */
2683 do_jump_if_equal (mode
, index
,
2686 expand_normal (node
->right
->low
),
2688 label_rtx (node
->right
->code_label
), unsignedp
, probability
);
2692 else if (node
->right
== 0 && node
->left
!= 0)
2694 /* Just one subtree, on the left. */
2695 if (node
->left
->left
|| node
->left
->right
2696 || !tree_int_cst_equal (node
->left
->low
, node
->left
->high
))
2698 if (!node_has_high_bound (node
, index_type
))
2700 probability
= conditional_probability (
2702 subtree_prob
+ default_prob
);
2703 emit_cmp_and_jump_insns (index
,
2706 expand_normal (node
->high
),
2708 GT
, NULL_RTX
, mode
, unsignedp
,
2714 emit_case_nodes (index
, node
->left
, default_label
,
2715 default_prob
, index_type
);
2719 probability
= conditional_probability (
2720 node
->left
->subtree_prob
,
2721 subtree_prob
+ default_prob
);
2722 /* We cannot process node->left normally
2723 since we haven't ruled out the numbers less than
2724 this node's value. So handle node->left explicitly. */
2725 do_jump_if_equal (mode
, index
,
2728 expand_normal (node
->left
->low
),
2730 label_rtx (node
->left
->code_label
), unsignedp
, probability
);
2736 /* Node is a range. These cases are very similar to those for a single
2737 value, except that we do not start by testing whether this node
2738 is the one to branch to. */
2740 if (node
->right
!= 0 && node
->left
!= 0)
2742 /* Node has subtrees on both sides.
2743 If the right-hand subtree is bounded,
2744 test for it first, since we can go straight there.
2745 Otherwise, we need to make a branch in the control structure,
2746 then handle the two subtrees. */
2747 tree test_label
= 0;
2749 if (node_is_bounded (node
->right
, index_type
))
2751 /* Right hand node is fully bounded so we can eliminate any
2752 testing and branch directly to the target code. */
2753 probability
= conditional_probability (
2754 node
->right
->subtree_prob
,
2755 subtree_prob
+ default_prob
);
2756 emit_cmp_and_jump_insns (index
,
2759 expand_normal (node
->high
),
2761 GT
, NULL_RTX
, mode
, unsignedp
,
2762 label_rtx (node
->right
->code_label
),
2767 /* Right hand node requires testing.
2768 Branch to a label where we will handle it later. */
2770 test_label
= build_decl (curr_insn_location (),
2771 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
2772 probability
= conditional_probability (
2773 node
->right
->subtree_prob
+ default_prob
/2,
2774 subtree_prob
+ default_prob
);
2775 emit_cmp_and_jump_insns (index
,
2778 expand_normal (node
->high
),
2780 GT
, NULL_RTX
, mode
, unsignedp
,
2781 label_rtx (test_label
),
2786 /* Value belongs to this node or to the left-hand subtree. */
2788 probability
= conditional_probability (
2790 subtree_prob
+ default_prob
);
2791 emit_cmp_and_jump_insns (index
,
2794 expand_normal (node
->low
),
2796 GE
, NULL_RTX
, mode
, unsignedp
,
2797 label_rtx (node
->code_label
),
2800 /* Handle the left-hand subtree. */
2801 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
2803 /* If right node had to be handled later, do that now. */
2807 /* If the left-hand subtree fell through,
2808 don't let it fall into the right-hand subtree. */
2810 emit_jump (default_label
);
2812 expand_label (test_label
);
2813 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
2817 else if (node
->right
!= 0 && node
->left
== 0)
2819 /* Deal with values to the left of this node,
2820 if they are possible. */
2821 if (!node_has_low_bound (node
, index_type
))
2823 probability
= conditional_probability (
2825 subtree_prob
+ default_prob
);
2826 emit_cmp_and_jump_insns (index
,
2829 expand_normal (node
->low
),
2831 LT
, NULL_RTX
, mode
, unsignedp
,
2837 /* Value belongs to this node or to the right-hand subtree. */
2839 probability
= conditional_probability (
2841 subtree_prob
+ default_prob
);
2842 emit_cmp_and_jump_insns (index
,
2845 expand_normal (node
->high
),
2847 LE
, NULL_RTX
, mode
, unsignedp
,
2848 label_rtx (node
->code_label
),
2851 emit_case_nodes (index
, node
->right
, default_label
, default_prob
, index_type
);
2854 else if (node
->right
== 0 && node
->left
!= 0)
2856 /* Deal with values to the right of this node,
2857 if they are possible. */
2858 if (!node_has_high_bound (node
, index_type
))
2860 probability
= conditional_probability (
2862 subtree_prob
+ default_prob
);
2863 emit_cmp_and_jump_insns (index
,
2866 expand_normal (node
->high
),
2868 GT
, NULL_RTX
, mode
, unsignedp
,
2874 /* Value belongs to this node or to the left-hand subtree. */
2876 probability
= conditional_probability (
2878 subtree_prob
+ default_prob
);
2879 emit_cmp_and_jump_insns (index
,
2882 expand_normal (node
->low
),
2884 GE
, NULL_RTX
, mode
, unsignedp
,
2885 label_rtx (node
->code_label
),
2888 emit_case_nodes (index
, node
->left
, default_label
, default_prob
, index_type
);
2893 /* Node has no children so we check low and high bounds to remove
2894 redundant tests. Only one of the bounds can exist,
2895 since otherwise this node is bounded--a case tested already. */
2896 int high_bound
= node_has_high_bound (node
, index_type
);
2897 int low_bound
= node_has_low_bound (node
, index_type
);
2899 if (!high_bound
&& low_bound
)
2901 probability
= conditional_probability (
2903 subtree_prob
+ default_prob
);
2904 emit_cmp_and_jump_insns (index
,
2907 expand_normal (node
->high
),
2909 GT
, NULL_RTX
, mode
, unsignedp
,
2914 else if (!low_bound
&& high_bound
)
2916 probability
= conditional_probability (
2918 subtree_prob
+ default_prob
);
2919 emit_cmp_and_jump_insns (index
,
2922 expand_normal (node
->low
),
2924 LT
, NULL_RTX
, mode
, unsignedp
,
2928 else if (!low_bound
&& !high_bound
)
2930 /* Widen LOW and HIGH to the same width as INDEX. */
2931 tree type
= lang_hooks
.types
.type_for_mode (mode
, unsignedp
);
2932 tree low
= build1 (CONVERT_EXPR
, type
, node
->low
);
2933 tree high
= build1 (CONVERT_EXPR
, type
, node
->high
);
2934 rtx low_rtx
, new_index
, new_bound
;
2936 /* Instead of doing two branches, emit one unsigned branch for
2937 (index-low) > (high-low). */
2938 low_rtx
= expand_expr (low
, NULL_RTX
, mode
, EXPAND_NORMAL
);
2939 new_index
= expand_simple_binop (mode
, MINUS
, index
, low_rtx
,
2940 NULL_RTX
, unsignedp
,
2942 new_bound
= expand_expr (fold_build2 (MINUS_EXPR
, type
,
2944 NULL_RTX
, mode
, EXPAND_NORMAL
);
2946 probability
= conditional_probability (
2948 subtree_prob
+ default_prob
);
2949 emit_cmp_and_jump_insns (new_index
, new_bound
, GT
, NULL_RTX
,
2950 mode
, 1, default_label
, probability
);
2953 emit_jump (label_rtx (node
->code_label
));