1 /* Expands front end tree to back end RTL for GCC
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
3 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file handles the generation of rtl code from tree structure
23 above the level of expressions, using subroutines in exp*.c and emit-rtl.c.
24 The functions whose names start with `expand_' are called by the
25 expander to generate RTL instructions for various kinds of constructs. */
29 #include "coretypes.h"
33 #include "hard-reg-set.h"
39 #include "insn-config.h"
47 #include "langhooks.h"
52 #include "alloc-pool.h"
53 #include "pretty-print.h"
55 /* Functions and data structures for expanding case statements. */
57 /* Case label structure, used to hold info on labels within case
58 statements. We handle "range" labels; for a single-value label
59 as in C, the high and low limits are the same.
61 We start with a vector of case nodes sorted in ascending order, and
62 the default label as the last element in the vector. Before expanding
63 to RTL, we transform this vector into a list linked via the RIGHT
64 fields in the case_node struct. Nodes with higher case values are
67 Switch statements can be output in three forms. A branch table is
68 used if there are more than a few labels and the labels are dense
69 within the range between the smallest and largest case value. If a
70 branch table is used, no further manipulations are done with the case
73 The alternative to the use of a branch table is to generate a series
74 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
75 and PARENT fields to hold a binary tree. Initially the tree is
76 totally unbalanced, with everything on the right. We balance the tree
77 with nodes on the left having lower case values than the parent
78 and nodes on the right having higher values. We then output the tree
81 For very small, suitable switch statements, we can generate a series
82 of simple bit test and branches instead. */
86 struct case_node
*left
; /* Left son in binary tree */
87 struct case_node
*right
; /* Right son in binary tree; also node chain */
88 struct case_node
*parent
; /* Parent of node in binary tree */
89 tree low
; /* Lowest index value for this label */
90 tree high
; /* Highest index value for this label */
91 tree code_label
; /* Label to jump to when node matches */
94 typedef struct case_node case_node
;
95 typedef struct case_node
*case_node_ptr
;
97 /* These are used by estimate_case_costs and balance_case_nodes. */
99 /* This must be a signed type, and non-ANSI compilers lack signed char. */
100 static short cost_table_
[129];
101 static int use_cost_table
;
102 static int cost_table_initialized
;
104 /* Special care is needed because we allow -1, but TREE_INT_CST_LOW
106 #define COST_TABLE(I) cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)]
108 static int n_occurrences (int, const char *);
109 static bool tree_conflicts_with_clobbers_p (tree
, HARD_REG_SET
*);
110 static void expand_nl_goto_receiver (void);
111 static bool check_operand_nalternatives (tree
, tree
);
112 static bool check_unique_operand_names (tree
, tree
);
113 static char *resolve_operand_name_1 (char *, tree
, tree
);
114 static void expand_null_return_1 (void);
115 static void expand_value_return (rtx
);
116 static int estimate_case_costs (case_node_ptr
);
117 static bool lshift_cheap_p (void);
118 static int case_bit_test_cmp (const void *, const void *);
119 static void emit_case_bit_tests (tree
, tree
, tree
, tree
, case_node_ptr
, rtx
);
120 static void balance_case_nodes (case_node_ptr
*, case_node_ptr
);
121 static int node_has_low_bound (case_node_ptr
, tree
);
122 static int node_has_high_bound (case_node_ptr
, tree
);
123 static int node_is_bounded (case_node_ptr
, tree
);
124 static void emit_case_nodes (rtx
, case_node_ptr
, rtx
, tree
);
125 static struct case_node
*add_case_node (struct case_node
*, tree
,
126 tree
, tree
, tree
, alloc_pool
);
129 /* Return the rtx-label that corresponds to a LABEL_DECL,
130 creating it if necessary. */
133 label_rtx (tree label
)
135 gcc_assert (TREE_CODE (label
) == LABEL_DECL
);
137 if (!DECL_RTL_SET_P (label
))
139 rtx r
= gen_label_rtx ();
140 SET_DECL_RTL (label
, r
);
141 if (FORCED_LABEL (label
) || DECL_NONLOCAL (label
))
142 LABEL_PRESERVE_P (r
) = 1;
145 return DECL_RTL (label
);
148 /* As above, but also put it on the forced-reference list of the
149 function that contains it. */
151 force_label_rtx (tree label
)
153 rtx ref
= label_rtx (label
);
154 tree function
= decl_function_context (label
);
156 gcc_assert (function
);
158 forced_labels
= gen_rtx_EXPR_LIST (VOIDmode
, ref
, forced_labels
);
162 /* Add an unconditional jump to LABEL as the next sequential instruction. */
165 emit_jump (rtx label
)
167 do_pending_stack_adjust ();
168 emit_jump_insn (gen_jump (label
));
172 /* Emit code to jump to the address
173 specified by the pointer expression EXP. */
176 expand_computed_goto (tree exp
)
178 rtx x
= expand_normal (exp
);
180 x
= convert_memory_address (Pmode
, x
);
182 do_pending_stack_adjust ();
183 emit_indirect_jump (x
);
186 /* Handle goto statements and the labels that they can go to. */
188 /* Specify the location in the RTL code of a label LABEL,
189 which is a LABEL_DECL tree node.
191 This is used for the kind of label that the user can jump to with a
192 goto statement, and for alternatives of a switch or case statement.
193 RTL labels generated for loops and conditionals don't go through here;
194 they are generated directly at the RTL level, by other functions below.
196 Note that this has nothing to do with defining label *names*.
197 Languages vary in how they do that and what that even means. */
200 expand_label (tree label
)
202 rtx label_r
= label_rtx (label
);
204 do_pending_stack_adjust ();
205 emit_label (label_r
);
206 if (DECL_NAME (label
))
207 LABEL_NAME (DECL_RTL (label
)) = IDENTIFIER_POINTER (DECL_NAME (label
));
209 if (DECL_NONLOCAL (label
))
211 expand_nl_goto_receiver ();
212 nonlocal_goto_handler_labels
213 = gen_rtx_EXPR_LIST (VOIDmode
, label_r
,
214 nonlocal_goto_handler_labels
);
217 if (FORCED_LABEL (label
))
218 forced_labels
= gen_rtx_EXPR_LIST (VOIDmode
, label_r
, forced_labels
);
220 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
221 maybe_set_first_label_num (label_r
);
224 /* Generate RTL code for a `goto' statement with target label LABEL.
225 LABEL should be a LABEL_DECL tree node that was or will later be
226 defined with `expand_label'. */
229 expand_goto (tree label
)
231 #ifdef ENABLE_CHECKING
232 /* Check for a nonlocal goto to a containing function. Should have
233 gotten translated to __builtin_nonlocal_goto. */
234 tree context
= decl_function_context (label
);
235 gcc_assert (!context
|| context
== current_function_decl
);
238 emit_jump (label_rtx (label
));
241 /* Return the number of times character C occurs in string S. */
243 n_occurrences (int c
, const char *s
)
251 /* Generate RTL for an asm statement (explicit assembler code).
252 STRING is a STRING_CST node containing the assembler code text,
253 or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the
254 insn is volatile; don't optimize it. */
257 expand_asm_loc (tree string
, int vol
, location_t locus
)
261 if (TREE_CODE (string
) == ADDR_EXPR
)
262 string
= TREE_OPERAND (string
, 0);
264 body
= gen_rtx_ASM_INPUT_loc (VOIDmode
,
265 ggc_strdup (TREE_STRING_POINTER (string
)),
268 MEM_VOLATILE_P (body
) = vol
;
273 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
274 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
275 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
276 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
277 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
278 constraint allows the use of a register operand. And, *IS_INOUT
279 will be true if the operand is read-write, i.e., if it is used as
280 an input as well as an output. If *CONSTRAINT_P is not in
281 canonical form, it will be made canonical. (Note that `+' will be
282 replaced with `=' as part of this process.)
284 Returns TRUE if all went well; FALSE if an error occurred. */
287 parse_output_constraint (const char **constraint_p
, int operand_num
,
288 int ninputs
, int noutputs
, bool *allows_mem
,
289 bool *allows_reg
, bool *is_inout
)
291 const char *constraint
= *constraint_p
;
294 /* Assume the constraint doesn't allow the use of either a register
299 /* Allow the `=' or `+' to not be at the beginning of the string,
300 since it wasn't explicitly documented that way, and there is a
301 large body of code that puts it last. Swap the character to
302 the front, so as not to uglify any place else. */
303 p
= strchr (constraint
, '=');
305 p
= strchr (constraint
, '+');
307 /* If the string doesn't contain an `=', issue an error
311 error ("output operand constraint lacks %<=%>");
315 /* If the constraint begins with `+', then the operand is both read
316 from and written to. */
317 *is_inout
= (*p
== '+');
319 /* Canonicalize the output constraint so that it begins with `='. */
320 if (p
!= constraint
|| *is_inout
)
323 size_t c_len
= strlen (constraint
);
326 warning (0, "output constraint %qc for operand %d "
327 "is not at the beginning",
330 /* Make a copy of the constraint. */
331 buf
= XALLOCAVEC (char, c_len
+ 1);
332 strcpy (buf
, constraint
);
333 /* Swap the first character and the `=' or `+'. */
334 buf
[p
- constraint
] = buf
[0];
335 /* Make sure the first character is an `='. (Until we do this,
336 it might be a `+'.) */
338 /* Replace the constraint with the canonicalized string. */
339 *constraint_p
= ggc_alloc_string (buf
, c_len
);
340 constraint
= *constraint_p
;
343 /* Loop through the constraint string. */
344 for (p
= constraint
+ 1; *p
; p
+= CONSTRAINT_LEN (*p
, p
))
349 error ("operand constraint contains incorrectly positioned "
354 if (operand_num
+ 1 == ninputs
+ noutputs
)
356 error ("%<%%%> constraint used with last operand");
361 case 'V': case TARGET_MEM_CONSTRAINT
: case 'o':
365 case '?': case '!': case '*': case '&': case '#':
366 case 'E': case 'F': case 'G': case 'H':
367 case 's': case 'i': case 'n':
368 case 'I': case 'J': case 'K': case 'L': case 'M':
369 case 'N': case 'O': case 'P': case ',':
372 case '0': case '1': case '2': case '3': case '4':
373 case '5': case '6': case '7': case '8': case '9':
375 error ("matching constraint not valid in output operand");
379 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
380 excepting those that expand_call created. So match memory
397 if (REG_CLASS_FROM_CONSTRAINT (*p
, p
) != NO_REGS
)
399 #ifdef EXTRA_CONSTRAINT_STR
400 else if (EXTRA_ADDRESS_CONSTRAINT (*p
, p
))
402 else if (EXTRA_MEMORY_CONSTRAINT (*p
, p
))
406 /* Otherwise we can't assume anything about the nature of
407 the constraint except that it isn't purely registers.
408 Treat it like "g" and hope for the best. */
419 /* Similar, but for input constraints. */
422 parse_input_constraint (const char **constraint_p
, int input_num
,
423 int ninputs
, int noutputs
, int ninout
,
424 const char * const * constraints
,
425 bool *allows_mem
, bool *allows_reg
)
427 const char *constraint
= *constraint_p
;
428 const char *orig_constraint
= constraint
;
429 size_t c_len
= strlen (constraint
);
431 bool saw_match
= false;
433 /* Assume the constraint doesn't allow the use of either
434 a register or memory. */
438 /* Make sure constraint has neither `=', `+', nor '&'. */
440 for (j
= 0; j
< c_len
; j
+= CONSTRAINT_LEN (constraint
[j
], constraint
+j
))
441 switch (constraint
[j
])
443 case '+': case '=': case '&':
444 if (constraint
== orig_constraint
)
446 error ("input operand constraint contains %qc", constraint
[j
]);
452 if (constraint
== orig_constraint
453 && input_num
+ 1 == ninputs
- ninout
)
455 error ("%<%%%> constraint used with last operand");
460 case 'V': case TARGET_MEM_CONSTRAINT
: case 'o':
465 case '?': case '!': case '*': case '#':
466 case 'E': case 'F': case 'G': case 'H':
467 case 's': case 'i': case 'n':
468 case 'I': case 'J': case 'K': case 'L': case 'M':
469 case 'N': case 'O': case 'P': case ',':
472 /* Whether or not a numeric constraint allows a register is
473 decided by the matching constraint, and so there is no need
474 to do anything special with them. We must handle them in
475 the default case, so that we don't unnecessarily force
476 operands to memory. */
477 case '0': case '1': case '2': case '3': case '4':
478 case '5': case '6': case '7': case '8': case '9':
485 match
= strtoul (constraint
+ j
, &end
, 10);
486 if (match
>= (unsigned long) noutputs
)
488 error ("matching constraint references invalid operand number");
492 /* Try and find the real constraint for this dup. Only do this
493 if the matching constraint is the only alternative. */
495 && (j
== 0 || (j
== 1 && constraint
[0] == '%')))
497 constraint
= constraints
[match
];
498 *constraint_p
= constraint
;
499 c_len
= strlen (constraint
);
501 /* ??? At the end of the loop, we will skip the first part of
502 the matched constraint. This assumes not only that the
503 other constraint is an output constraint, but also that
504 the '=' or '+' come first. */
508 j
= end
- constraint
;
509 /* Anticipate increment at end of loop. */
524 if (! ISALPHA (constraint
[j
]))
526 error ("invalid punctuation %qc in constraint", constraint
[j
]);
529 if (REG_CLASS_FROM_CONSTRAINT (constraint
[j
], constraint
+ j
)
532 #ifdef EXTRA_CONSTRAINT_STR
533 else if (EXTRA_ADDRESS_CONSTRAINT (constraint
[j
], constraint
+ j
))
535 else if (EXTRA_MEMORY_CONSTRAINT (constraint
[j
], constraint
+ j
))
539 /* Otherwise we can't assume anything about the nature of
540 the constraint except that it isn't purely registers.
541 Treat it like "g" and hope for the best. */
549 if (saw_match
&& !*allows_reg
)
550 warning (0, "matching constraint does not allow a register");
555 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
556 can be an asm-declared register. Called via walk_tree. */
559 decl_overlaps_hard_reg_set_p (tree
*declp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
563 const HARD_REG_SET
*const regs
= (const HARD_REG_SET
*) data
;
565 if (TREE_CODE (decl
) == VAR_DECL
)
567 if (DECL_HARD_REGISTER (decl
)
568 && REG_P (DECL_RTL (decl
))
569 && REGNO (DECL_RTL (decl
)) < FIRST_PSEUDO_REGISTER
)
571 rtx reg
= DECL_RTL (decl
);
573 if (overlaps_hard_reg_set_p (*regs
, GET_MODE (reg
), REGNO (reg
)))
578 else if (TYPE_P (decl
) || TREE_CODE (decl
) == PARM_DECL
)
583 /* If there is an overlap between *REGS and DECL, return the first overlap
586 tree_overlaps_hard_reg_set (tree decl
, HARD_REG_SET
*regs
)
588 return walk_tree (&decl
, decl_overlaps_hard_reg_set_p
, regs
, NULL
);
591 /* Check for overlap between registers marked in CLOBBERED_REGS and
592 anything inappropriate in T. Emit error and return the register
593 variable definition for error, NULL_TREE for ok. */
596 tree_conflicts_with_clobbers_p (tree t
, HARD_REG_SET
*clobbered_regs
)
598 /* Conflicts between asm-declared register variables and the clobber
599 list are not allowed. */
600 tree overlap
= tree_overlaps_hard_reg_set (t
, clobbered_regs
);
604 error ("asm-specifier for variable %qE conflicts with asm clobber list",
605 DECL_NAME (overlap
));
607 /* Reset registerness to stop multiple errors emitted for a single
609 DECL_REGISTER (overlap
) = 0;
616 /* Generate RTL for an asm statement with arguments.
617 STRING is the instruction template.
618 OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs.
619 Each output or input has an expression in the TREE_VALUE and
620 a tree list in TREE_PURPOSE which in turn contains a constraint
621 name in TREE_VALUE (or NULL_TREE) and a constraint string
623 CLOBBERS is a list of STRING_CST nodes each naming a hard register
624 that is clobbered by this insn.
626 Not all kinds of lvalue that may appear in OUTPUTS can be stored directly.
627 Some elements of OUTPUTS may be replaced with trees representing temporary
628 values. The caller should copy those temporary values to the originally
631 VOL nonzero means the insn is volatile; don't optimize it. */
634 expand_asm_operands (tree string
, tree outputs
, tree inputs
,
635 tree clobbers
, int vol
, location_t locus
)
637 rtvec argvec
, constraintvec
;
639 int ninputs
= list_length (inputs
);
640 int noutputs
= list_length (outputs
);
643 HARD_REG_SET clobbered_regs
;
644 int clobber_conflict_found
= 0;
648 /* Vector of RTX's of evaluated output operands. */
649 rtx
*output_rtx
= XALLOCAVEC (rtx
, noutputs
);
650 int *inout_opnum
= XALLOCAVEC (int, noutputs
);
651 rtx
*real_output_rtx
= XALLOCAVEC (rtx
, noutputs
);
652 enum machine_mode
*inout_mode
= XALLOCAVEC (enum machine_mode
, noutputs
);
653 const char **constraints
= XALLOCAVEC (const char *, noutputs
+ ninputs
);
654 int old_generating_concat_p
= generating_concat_p
;
656 /* An ASM with no outputs needs to be treated as volatile, for now. */
660 if (! check_operand_nalternatives (outputs
, inputs
))
663 string
= resolve_asm_operand_names (string
, outputs
, inputs
);
665 /* Collect constraints. */
667 for (t
= outputs
; t
; t
= TREE_CHAIN (t
), i
++)
668 constraints
[i
] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
669 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), i
++)
670 constraints
[i
] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
672 /* Sometimes we wish to automatically clobber registers across an asm.
673 Case in point is when the i386 backend moved from cc0 to a hard reg --
674 maintaining source-level compatibility means automatically clobbering
675 the flags register. */
676 clobbers
= targetm
.md_asm_clobbers (outputs
, inputs
, clobbers
);
678 /* Count the number of meaningful clobbered registers, ignoring what
679 we would ignore later. */
681 CLEAR_HARD_REG_SET (clobbered_regs
);
682 for (tail
= clobbers
; tail
; tail
= TREE_CHAIN (tail
))
686 if (TREE_VALUE (tail
) == error_mark_node
)
688 regname
= TREE_STRING_POINTER (TREE_VALUE (tail
));
690 i
= decode_reg_name (regname
);
691 if (i
>= 0 || i
== -4)
694 error ("unknown register name %qs in %<asm%>", regname
);
696 /* Mark clobbered registers. */
699 /* Clobbering the PIC register is an error. */
700 if (i
== (int) PIC_OFFSET_TABLE_REGNUM
)
702 error ("PIC register %qs clobbered in %<asm%>", regname
);
706 SET_HARD_REG_BIT (clobbered_regs
, i
);
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 lang_hooks
.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 lang_hooks
.mark_addressable (TREE_VALUE (tail
));
772 /* Second pass evaluates arguments. */
775 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
777 tree val
= TREE_VALUE (tail
);
778 tree type
= TREE_TYPE (val
);
785 ok
= parse_output_constraint (&constraints
[i
], i
, ninputs
,
786 noutputs
, &allows_mem
, &allows_reg
,
790 /* If an output operand is not a decl or indirect ref and our constraint
791 allows a register, make a temporary to act as an intermediate.
792 Make the asm insn write into that, then our caller will copy it to
793 the real output operand. Likewise for promoted variables. */
795 generating_concat_p
= 0;
797 real_output_rtx
[i
] = NULL_RTX
;
798 if ((TREE_CODE (val
) == INDIRECT_REF
801 && (allows_mem
|| REG_P (DECL_RTL (val
)))
802 && ! (REG_P (DECL_RTL (val
))
803 && GET_MODE (DECL_RTL (val
)) != TYPE_MODE (type
)))
807 op
= expand_expr (val
, NULL_RTX
, VOIDmode
, EXPAND_WRITE
);
809 op
= validize_mem (op
);
811 if (! allows_reg
&& !MEM_P (op
))
812 error ("output number %d not directly addressable", i
);
813 if ((! allows_mem
&& MEM_P (op
))
814 || GET_CODE (op
) == CONCAT
)
816 real_output_rtx
[i
] = op
;
817 op
= gen_reg_rtx (GET_MODE (op
));
819 emit_move_insn (op
, real_output_rtx
[i
]);
824 op
= assign_temp (type
, 0, 0, 1);
825 op
= validize_mem (op
);
826 TREE_VALUE (tail
) = make_tree (type
, op
);
830 generating_concat_p
= old_generating_concat_p
;
834 inout_mode
[ninout
] = TYPE_MODE (type
);
835 inout_opnum
[ninout
++] = i
;
838 if (tree_conflicts_with_clobbers_p (val
, &clobbered_regs
))
839 clobber_conflict_found
= 1;
842 /* Make vectors for the expression-rtx, constraint strings,
843 and named operands. */
845 argvec
= rtvec_alloc (ninputs
);
846 constraintvec
= rtvec_alloc (ninputs
);
848 body
= gen_rtx_ASM_OPERANDS ((noutputs
== 0 ? VOIDmode
849 : GET_MODE (output_rtx
[0])),
850 ggc_strdup (TREE_STRING_POINTER (string
)),
851 empty_string
, 0, argvec
, constraintvec
,
854 MEM_VOLATILE_P (body
) = vol
;
856 /* Eval the inputs and put them into ARGVEC.
857 Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */
859 for (i
= 0, tail
= inputs
; tail
; tail
= TREE_CHAIN (tail
), ++i
)
861 bool allows_reg
, allows_mem
;
862 const char *constraint
;
867 constraint
= constraints
[i
+ noutputs
];
868 ok
= parse_input_constraint (&constraint
, i
, ninputs
, noutputs
, ninout
,
869 constraints
, &allows_mem
, &allows_reg
);
872 generating_concat_p
= 0;
874 val
= TREE_VALUE (tail
);
875 type
= TREE_TYPE (val
);
876 /* EXPAND_INITIALIZER will not generate code for valid initializer
877 constants, but will still generate code for other types of operand.
878 This is the behavior we want for constant constraints. */
879 op
= expand_expr (val
, NULL_RTX
, VOIDmode
,
880 allows_reg
? EXPAND_NORMAL
881 : allows_mem
? EXPAND_MEMORY
882 : EXPAND_INITIALIZER
);
884 /* Never pass a CONCAT to an ASM. */
885 if (GET_CODE (op
) == CONCAT
)
886 op
= force_reg (GET_MODE (op
), op
);
888 op
= validize_mem (op
);
890 if (asm_operand_ok (op
, constraint
, NULL
) <= 0)
892 if (allows_reg
&& TYPE_MODE (type
) != BLKmode
)
893 op
= force_reg (TYPE_MODE (type
), op
);
894 else if (!allows_mem
)
895 warning (0, "asm operand %d probably doesn%'t match constraints",
899 /* We won't recognize either volatile memory or memory
900 with a queued address as available a memory_operand
901 at this point. Ignore it: clearly this *is* a memory. */
905 warning (0, "use of memory input without lvalue in "
906 "asm operand %d is deprecated", i
+ noutputs
);
910 rtx mem
= force_const_mem (TYPE_MODE (type
), op
);
912 op
= validize_mem (mem
);
914 op
= force_reg (TYPE_MODE (type
), op
);
917 || GET_CODE (op
) == SUBREG
918 || GET_CODE (op
) == CONCAT
)
920 tree qual_type
= build_qualified_type (type
,
923 rtx memloc
= assign_temp (qual_type
, 1, 1, 1);
924 memloc
= validize_mem (memloc
);
925 emit_move_insn (memloc
, op
);
931 generating_concat_p
= old_generating_concat_p
;
932 ASM_OPERANDS_INPUT (body
, i
) = op
;
934 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body
, i
)
935 = gen_rtx_ASM_INPUT (TYPE_MODE (type
),
936 ggc_strdup (constraints
[i
+ noutputs
]));
938 if (tree_conflicts_with_clobbers_p (val
, &clobbered_regs
))
939 clobber_conflict_found
= 1;
942 /* Protect all the operands from the queue now that they have all been
945 generating_concat_p
= 0;
947 /* For in-out operands, copy output rtx to input rtx. */
948 for (i
= 0; i
< ninout
; i
++)
950 int j
= inout_opnum
[i
];
953 ASM_OPERANDS_INPUT (body
, ninputs
- ninout
+ i
)
956 sprintf (buffer
, "%d", j
);
957 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body
, ninputs
- ninout
+ i
)
958 = gen_rtx_ASM_INPUT (inout_mode
[i
], ggc_strdup (buffer
));
961 generating_concat_p
= old_generating_concat_p
;
963 /* Now, for each output, construct an rtx
964 (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER
965 ARGVEC CONSTRAINTS OPNAMES))
966 If there is more than one, put them inside a PARALLEL. */
968 if (noutputs
== 1 && nclobbers
== 0)
970 ASM_OPERANDS_OUTPUT_CONSTRAINT (body
) = ggc_strdup (constraints
[0]);
971 emit_insn (gen_rtx_SET (VOIDmode
, output_rtx
[0], body
));
974 else if (noutputs
== 0 && nclobbers
== 0)
976 /* No output operands: put in a raw ASM_OPERANDS rtx. */
988 body
= gen_rtx_PARALLEL (VOIDmode
, rtvec_alloc (num
+ nclobbers
));
990 /* For each output operand, store a SET. */
991 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
994 = gen_rtx_SET (VOIDmode
,
997 (GET_MODE (output_rtx
[i
]),
998 ggc_strdup (TREE_STRING_POINTER (string
)),
999 ggc_strdup (constraints
[i
]),
1000 i
, argvec
, constraintvec
, locus
));
1002 MEM_VOLATILE_P (SET_SRC (XVECEXP (body
, 0, i
))) = vol
;
1005 /* If there are no outputs (but there are some clobbers)
1006 store the bare ASM_OPERANDS into the PARALLEL. */
1009 XVECEXP (body
, 0, i
++) = obody
;
1011 /* Store (clobber REG) for each clobbered register specified. */
1013 for (tail
= clobbers
; tail
; tail
= TREE_CHAIN (tail
))
1015 const char *regname
= TREE_STRING_POINTER (TREE_VALUE (tail
));
1016 int j
= decode_reg_name (regname
);
1021 if (j
== -3) /* `cc', which is not a register */
1024 if (j
== -4) /* `memory', don't cache memory across asm */
1026 XVECEXP (body
, 0, i
++)
1027 = gen_rtx_CLOBBER (VOIDmode
,
1030 gen_rtx_SCRATCH (VOIDmode
)));
1034 /* Ignore unknown register, error already signaled. */
1038 /* Use QImode since that's guaranteed to clobber just one reg. */
1039 clobbered_reg
= gen_rtx_REG (QImode
, j
);
1041 /* Do sanity check for overlap between clobbers and respectively
1042 input and outputs that hasn't been handled. Such overlap
1043 should have been detected and reported above. */
1044 if (!clobber_conflict_found
)
1048 /* We test the old body (obody) contents to avoid tripping
1049 over the under-construction body. */
1050 for (opno
= 0; opno
< noutputs
; opno
++)
1051 if (reg_overlap_mentioned_p (clobbered_reg
, output_rtx
[opno
]))
1052 internal_error ("asm clobber conflict with output operand");
1054 for (opno
= 0; opno
< ninputs
- ninout
; opno
++)
1055 if (reg_overlap_mentioned_p (clobbered_reg
,
1056 ASM_OPERANDS_INPUT (obody
, opno
)))
1057 internal_error ("asm clobber conflict with input operand");
1060 XVECEXP (body
, 0, i
++)
1061 = gen_rtx_CLOBBER (VOIDmode
, clobbered_reg
);
1067 /* For any outputs that needed reloading into registers, spill them
1068 back to where they belong. */
1069 for (i
= 0; i
< noutputs
; ++i
)
1070 if (real_output_rtx
[i
])
1071 emit_move_insn (real_output_rtx
[i
], output_rtx
[i
]);
1073 crtl
->has_asm_statement
= 1;
1078 expand_asm_expr (tree exp
)
1084 if (ASM_INPUT_P (exp
))
1086 expand_asm_loc (ASM_STRING (exp
), ASM_VOLATILE_P (exp
), input_location
);
1090 outputs
= ASM_OUTPUTS (exp
);
1091 noutputs
= list_length (outputs
);
1092 /* o[I] is the place that output number I should be written. */
1093 o
= (tree
*) alloca (noutputs
* sizeof (tree
));
1095 /* Record the contents of OUTPUTS before it is modified. */
1096 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
1097 o
[i
] = TREE_VALUE (tail
);
1099 /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of
1100 OUTPUTS some trees for where the values were actually stored. */
1101 expand_asm_operands (ASM_STRING (exp
), outputs
, ASM_INPUTS (exp
),
1102 ASM_CLOBBERS (exp
), ASM_VOLATILE_P (exp
),
1105 /* Copy all the intermediate outputs into the specified outputs. */
1106 for (i
= 0, tail
= outputs
; tail
; tail
= TREE_CHAIN (tail
), i
++)
1108 if (o
[i
] != TREE_VALUE (tail
))
1110 expand_assignment (o
[i
], TREE_VALUE (tail
), false);
1113 /* Restore the original value so that it's correct the next
1114 time we expand this function. */
1115 TREE_VALUE (tail
) = o
[i
];
1120 /* A subroutine of expand_asm_operands. Check that all operands have
1121 the same number of alternatives. Return true if so. */
1124 check_operand_nalternatives (tree outputs
, tree inputs
)
1126 if (outputs
|| inputs
)
1128 tree tmp
= TREE_PURPOSE (outputs
? outputs
: inputs
);
1130 = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp
)));
1133 if (nalternatives
+ 1 > MAX_RECOG_ALTERNATIVES
)
1135 error ("too many alternatives in %<asm%>");
1142 const char *constraint
1143 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp
)));
1145 if (n_occurrences (',', constraint
) != nalternatives
)
1147 error ("operand constraints for %<asm%> differ "
1148 "in number of alternatives");
1152 if (TREE_CHAIN (tmp
))
1153 tmp
= TREE_CHAIN (tmp
);
1155 tmp
= next
, next
= 0;
1162 /* A subroutine of expand_asm_operands. Check that all operand names
1163 are unique. Return true if so. We rely on the fact that these names
1164 are identifiers, and so have been canonicalized by get_identifier,
1165 so all we need are pointer comparisons. */
1168 check_unique_operand_names (tree outputs
, tree inputs
)
1172 for (i
= outputs
; i
; i
= TREE_CHAIN (i
))
1174 tree i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
1178 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
1179 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
1183 for (i
= inputs
; i
; i
= TREE_CHAIN (i
))
1185 tree i_name
= TREE_PURPOSE (TREE_PURPOSE (i
));
1189 for (j
= TREE_CHAIN (i
); j
; j
= TREE_CHAIN (j
))
1190 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
1192 for (j
= outputs
; j
; j
= TREE_CHAIN (j
))
1193 if (simple_cst_equal (i_name
, TREE_PURPOSE (TREE_PURPOSE (j
))))
1200 error ("duplicate asm operand name %qs",
1201 TREE_STRING_POINTER (TREE_PURPOSE (TREE_PURPOSE (i
))));
1205 /* A subroutine of expand_asm_operands. Resolve the names of the operands
1206 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
1207 STRING and in the constraints to those numbers. */
1210 resolve_asm_operand_names (tree string
, tree outputs
, tree inputs
)
1217 check_unique_operand_names (outputs
, inputs
);
1219 /* Substitute [<name>] in input constraint strings. There should be no
1220 named operands in output constraints. */
1221 for (t
= inputs
; t
; t
= TREE_CHAIN (t
))
1223 c
= TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t
)));
1224 if (strchr (c
, '[') != NULL
)
1226 p
= buffer
= xstrdup (c
);
1227 while ((p
= strchr (p
, '[')) != NULL
)
1228 p
= resolve_operand_name_1 (p
, outputs
, inputs
);
1229 TREE_VALUE (TREE_PURPOSE (t
))
1230 = build_string (strlen (buffer
), buffer
);
1235 /* Now check for any needed substitutions in the template. */
1236 c
= TREE_STRING_POINTER (string
);
1237 while ((c
= strchr (c
, '%')) != NULL
)
1241 else if (ISALPHA (c
[1]) && c
[2] == '[')
1252 /* OK, we need to make a copy so we can perform the substitutions.
1253 Assume that we will not need extra space--we get to remove '['
1254 and ']', which means we cannot have a problem until we have more
1255 than 999 operands. */
1256 buffer
= xstrdup (TREE_STRING_POINTER (string
));
1257 p
= buffer
+ (c
- TREE_STRING_POINTER (string
));
1259 while ((p
= strchr (p
, '%')) != NULL
)
1263 else if (ISALPHA (p
[1]) && p
[2] == '[')
1271 p
= resolve_operand_name_1 (p
, outputs
, inputs
);
1274 string
= build_string (strlen (buffer
), buffer
);
1281 /* A subroutine of resolve_operand_names. P points to the '[' for a
1282 potential named operand of the form [<name>]. In place, replace
1283 the name and brackets with a number. Return a pointer to the
1284 balance of the string after substitution. */
1287 resolve_operand_name_1 (char *p
, tree outputs
, tree inputs
)
1294 /* Collect the operand name. */
1295 q
= strchr (p
, ']');
1298 error ("missing close brace for named operand");
1299 return strchr (p
, '\0');
1303 /* Resolve the name to a number. */
1304 for (op
= 0, t
= outputs
; t
; t
= TREE_CHAIN (t
), op
++)
1306 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
1309 const char *c
= TREE_STRING_POINTER (name
);
1310 if (strncmp (c
, p
+ 1, len
) == 0 && c
[len
] == '\0')
1314 for (t
= inputs
; t
; t
= TREE_CHAIN (t
), op
++)
1316 tree name
= TREE_PURPOSE (TREE_PURPOSE (t
));
1319 const char *c
= TREE_STRING_POINTER (name
);
1320 if (strncmp (c
, p
+ 1, len
) == 0 && c
[len
] == '\0')
1326 error ("undefined named operand %qs", identifier_to_locale (p
+ 1));
1330 /* Replace the name with the number. Unfortunately, not all libraries
1331 get the return value of sprintf correct, so search for the end of the
1332 generated string by hand. */
1333 sprintf (p
, "%d", op
);
1334 p
= strchr (p
, '\0');
1336 /* Verify the no extra buffer space assumption. */
1337 gcc_assert (p
<= q
);
1339 /* Shift the rest of the buffer down to fill the gap. */
1340 memmove (p
, q
+ 1, strlen (q
+ 1) + 1);
1345 /* Generate RTL to evaluate the expression EXP. */
1348 expand_expr_stmt (tree exp
)
1353 value
= expand_expr (exp
, const0_rtx
, VOIDmode
, EXPAND_NORMAL
);
1354 type
= TREE_TYPE (exp
);
1356 /* If all we do is reference a volatile value in memory,
1357 copy it to a register to be sure it is actually touched. */
1358 if (value
&& MEM_P (value
) && TREE_THIS_VOLATILE (exp
))
1360 if (TYPE_MODE (type
) == VOIDmode
)
1362 else if (TYPE_MODE (type
) != BLKmode
)
1363 value
= copy_to_reg (value
);
1366 rtx lab
= gen_label_rtx ();
1368 /* Compare the value with itself to reference it. */
1369 emit_cmp_and_jump_insns (value
, value
, EQ
,
1370 expand_normal (TYPE_SIZE (type
)),
1376 /* Free any temporaries used to evaluate this expression. */
1380 /* Warn if EXP contains any computations whose results are not used.
1381 Return 1 if a warning is printed; 0 otherwise. LOCUS is the
1382 (potential) location of the expression. */
1385 warn_if_unused_value (const_tree exp
, location_t locus
)
1388 if (TREE_USED (exp
) || TREE_NO_WARNING (exp
))
1391 /* Don't warn about void constructs. This includes casting to void,
1392 void function calls, and statement expressions with a final cast
1394 if (VOID_TYPE_P (TREE_TYPE (exp
)))
1397 if (EXPR_HAS_LOCATION (exp
))
1398 locus
= EXPR_LOCATION (exp
);
1400 switch (TREE_CODE (exp
))
1402 case PREINCREMENT_EXPR
:
1403 case POSTINCREMENT_EXPR
:
1404 case PREDECREMENT_EXPR
:
1405 case POSTDECREMENT_EXPR
:
1410 case TRY_CATCH_EXPR
:
1411 case WITH_CLEANUP_EXPR
:
1417 /* For a binding, warn if no side effect within it. */
1418 exp
= BIND_EXPR_BODY (exp
);
1422 case NON_LVALUE_EXPR
:
1423 exp
= TREE_OPERAND (exp
, 0);
1426 case TRUTH_ORIF_EXPR
:
1427 case TRUTH_ANDIF_EXPR
:
1428 /* In && or ||, warn if 2nd operand has no side effect. */
1429 exp
= TREE_OPERAND (exp
, 1);
1433 if (warn_if_unused_value (TREE_OPERAND (exp
, 0), locus
))
1435 /* Let people do `(foo (), 0)' without a warning. */
1436 if (TREE_CONSTANT (TREE_OPERAND (exp
, 1)))
1438 exp
= TREE_OPERAND (exp
, 1);
1442 /* If this is an expression with side effects, don't warn; this
1443 case commonly appears in macro expansions. */
1444 if (TREE_SIDE_EFFECTS (exp
))
1449 /* Don't warn about automatic dereferencing of references, since
1450 the user cannot control it. */
1451 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp
, 0))) == REFERENCE_TYPE
)
1453 exp
= TREE_OPERAND (exp
, 0);
1459 /* Referencing a volatile value is a side effect, so don't warn. */
1460 if ((DECL_P (exp
) || REFERENCE_CLASS_P (exp
))
1461 && TREE_THIS_VOLATILE (exp
))
1464 /* If this is an expression which has no operands, there is no value
1465 to be unused. There are no such language-independent codes,
1466 but front ends may define such. */
1467 if (EXPRESSION_CLASS_P (exp
) && TREE_OPERAND_LENGTH (exp
) == 0)
1471 warning_at (locus
, OPT_Wunused_value
, "value computed is not used");
1477 /* Generate RTL to return from the current function, with no value.
1478 (That is, we do not do anything about returning any value.) */
1481 expand_null_return (void)
1483 /* If this function was declared to return a value, but we
1484 didn't, clobber the return registers so that they are not
1485 propagated live to the rest of the function. */
1486 clobber_return_register ();
1488 expand_null_return_1 ();
1491 /* Generate RTL to return directly from the current function.
1492 (That is, we bypass any return value.) */
1495 expand_naked_return (void)
1499 clear_pending_stack_adjust ();
1500 do_pending_stack_adjust ();
1502 end_label
= naked_return_label
;
1504 end_label
= naked_return_label
= gen_label_rtx ();
1506 emit_jump (end_label
);
1509 /* Generate RTL to return from the current function, with value VAL. */
1512 expand_value_return (rtx val
)
1514 /* Copy the value to the return location unless it's already there. */
1516 tree decl
= DECL_RESULT (current_function_decl
);
1517 rtx return_reg
= DECL_RTL (decl
);
1518 if (return_reg
!= val
)
1520 tree funtype
= TREE_TYPE (current_function_decl
);
1521 tree type
= TREE_TYPE (decl
);
1522 int unsignedp
= TYPE_UNSIGNED (type
);
1523 enum machine_mode old_mode
= DECL_MODE (decl
);
1524 enum machine_mode mode
= promote_function_mode (type
, old_mode
,
1525 &unsignedp
, funtype
, 1);
1527 if (mode
!= old_mode
)
1528 val
= convert_modes (mode
, old_mode
, val
, unsignedp
);
1530 if (GET_CODE (return_reg
) == PARALLEL
)
1531 emit_group_load (return_reg
, val
, type
, int_size_in_bytes (type
));
1533 emit_move_insn (return_reg
, val
);
1536 expand_null_return_1 ();
1539 /* Output a return with no value. */
1542 expand_null_return_1 (void)
1544 clear_pending_stack_adjust ();
1545 do_pending_stack_adjust ();
1546 emit_jump (return_label
);
1549 /* Generate RTL to evaluate the expression RETVAL and return it
1550 from the current function. */
1553 expand_return (tree retval
)
1559 /* If function wants no value, give it none. */
1560 if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl
))) == VOID_TYPE
)
1562 expand_normal (retval
);
1563 expand_null_return ();
1567 if (retval
== error_mark_node
)
1569 /* Treat this like a return of no value from a function that
1571 expand_null_return ();
1574 else if ((TREE_CODE (retval
) == MODIFY_EXPR
1575 || TREE_CODE (retval
) == INIT_EXPR
)
1576 && TREE_CODE (TREE_OPERAND (retval
, 0)) == RESULT_DECL
)
1577 retval_rhs
= TREE_OPERAND (retval
, 1);
1579 retval_rhs
= retval
;
1581 result_rtl
= DECL_RTL (DECL_RESULT (current_function_decl
));
1583 /* If we are returning the RESULT_DECL, then the value has already
1584 been stored into it, so we don't have to do anything special. */
1585 if (TREE_CODE (retval_rhs
) == RESULT_DECL
)
1586 expand_value_return (result_rtl
);
1588 /* If the result is an aggregate that is being returned in one (or more)
1589 registers, load the registers here. The compiler currently can't handle
1590 copying a BLKmode value into registers. We could put this code in a
1591 more general area (for use by everyone instead of just function
1592 call/return), but until this feature is generally usable it is kept here
1593 (and in expand_call). */
1595 else if (retval_rhs
!= 0
1596 && TYPE_MODE (TREE_TYPE (retval_rhs
)) == BLKmode
1597 && REG_P (result_rtl
))
1600 unsigned HOST_WIDE_INT bitpos
, xbitpos
;
1601 unsigned HOST_WIDE_INT padding_correction
= 0;
1602 unsigned HOST_WIDE_INT bytes
1603 = int_size_in_bytes (TREE_TYPE (retval_rhs
));
1604 int n_regs
= (bytes
+ UNITS_PER_WORD
- 1) / UNITS_PER_WORD
;
1605 unsigned int bitsize
1606 = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs
)), BITS_PER_WORD
);
1607 rtx
*result_pseudos
= XALLOCAVEC (rtx
, n_regs
);
1608 rtx result_reg
, src
= NULL_RTX
, dst
= NULL_RTX
;
1609 rtx result_val
= expand_normal (retval_rhs
);
1610 enum machine_mode tmpmode
, result_reg_mode
;
1614 expand_null_return ();
1618 /* If the structure doesn't take up a whole number of words, see
1619 whether the register value should be padded on the left or on
1620 the right. Set PADDING_CORRECTION to the number of padding
1621 bits needed on the left side.
1623 In most ABIs, the structure will be returned at the least end of
1624 the register, which translates to right padding on little-endian
1625 targets and left padding on big-endian targets. The opposite
1626 holds if the structure is returned at the most significant
1627 end of the register. */
1628 if (bytes
% UNITS_PER_WORD
!= 0
1629 && (targetm
.calls
.return_in_msb (TREE_TYPE (retval_rhs
))
1631 : BYTES_BIG_ENDIAN
))
1632 padding_correction
= (BITS_PER_WORD
- ((bytes
% UNITS_PER_WORD
)
1635 /* Copy the structure BITSIZE bits at a time. */
1636 for (bitpos
= 0, xbitpos
= padding_correction
;
1637 bitpos
< bytes
* BITS_PER_UNIT
;
1638 bitpos
+= bitsize
, xbitpos
+= bitsize
)
1640 /* We need a new destination pseudo each time xbitpos is
1641 on a word boundary and when xbitpos == padding_correction
1642 (the first time through). */
1643 if (xbitpos
% BITS_PER_WORD
== 0
1644 || xbitpos
== padding_correction
)
1646 /* Generate an appropriate register. */
1647 dst
= gen_reg_rtx (word_mode
);
1648 result_pseudos
[xbitpos
/ BITS_PER_WORD
] = dst
;
1650 /* Clear the destination before we move anything into it. */
1651 emit_move_insn (dst
, CONST0_RTX (GET_MODE (dst
)));
1654 /* We need a new source operand each time bitpos is on a word
1656 if (bitpos
% BITS_PER_WORD
== 0)
1657 src
= operand_subword_force (result_val
,
1658 bitpos
/ BITS_PER_WORD
,
1661 /* Use bitpos for the source extraction (left justified) and
1662 xbitpos for the destination store (right justified). */
1663 store_bit_field (dst
, bitsize
, xbitpos
% BITS_PER_WORD
, word_mode
,
1664 extract_bit_field (src
, bitsize
,
1665 bitpos
% BITS_PER_WORD
, 1,
1666 NULL_RTX
, word_mode
, word_mode
));
1669 tmpmode
= GET_MODE (result_rtl
);
1670 if (tmpmode
== BLKmode
)
1672 /* Find the smallest integer mode large enough to hold the
1673 entire structure and use that mode instead of BLKmode
1674 on the USE insn for the return register. */
1675 for (tmpmode
= GET_CLASS_NARROWEST_MODE (MODE_INT
);
1676 tmpmode
!= VOIDmode
;
1677 tmpmode
= GET_MODE_WIDER_MODE (tmpmode
))
1678 /* Have we found a large enough mode? */
1679 if (GET_MODE_SIZE (tmpmode
) >= bytes
)
1682 /* A suitable mode should have been found. */
1683 gcc_assert (tmpmode
!= VOIDmode
);
1685 PUT_MODE (result_rtl
, tmpmode
);
1688 if (GET_MODE_SIZE (tmpmode
) < GET_MODE_SIZE (word_mode
))
1689 result_reg_mode
= word_mode
;
1691 result_reg_mode
= tmpmode
;
1692 result_reg
= gen_reg_rtx (result_reg_mode
);
1694 for (i
= 0; i
< n_regs
; i
++)
1695 emit_move_insn (operand_subword (result_reg
, i
, 0, result_reg_mode
),
1698 if (tmpmode
!= result_reg_mode
)
1699 result_reg
= gen_lowpart (tmpmode
, result_reg
);
1701 expand_value_return (result_reg
);
1703 else if (retval_rhs
!= 0
1704 && !VOID_TYPE_P (TREE_TYPE (retval_rhs
))
1705 && (REG_P (result_rtl
)
1706 || (GET_CODE (result_rtl
) == PARALLEL
)))
1708 /* Calculate the return value into a temporary (usually a pseudo
1710 tree ot
= TREE_TYPE (DECL_RESULT (current_function_decl
));
1711 tree nt
= build_qualified_type (ot
, TYPE_QUALS (ot
) | TYPE_QUAL_CONST
);
1713 val
= assign_temp (nt
, 0, 0, 1);
1714 val
= expand_expr (retval_rhs
, val
, GET_MODE (val
), EXPAND_NORMAL
);
1715 val
= force_not_mem (val
);
1716 /* Return the calculated value. */
1717 expand_value_return (val
);
1721 /* No hard reg used; calculate value into hard return reg. */
1722 expand_expr (retval
, const0_rtx
, VOIDmode
, EXPAND_NORMAL
);
1723 expand_value_return (result_rtl
);
1727 /* Emit code to restore vital registers at the beginning of a nonlocal goto
1730 expand_nl_goto_receiver (void)
1732 /* Clobber the FP when we get here, so we have to make sure it's
1733 marked as used by this function. */
1734 emit_use (hard_frame_pointer_rtx
);
1736 /* Mark the static chain as clobbered here so life information
1737 doesn't get messed up for it. */
1738 emit_clobber (static_chain_rtx
);
1740 #ifdef HAVE_nonlocal_goto
1741 if (! HAVE_nonlocal_goto
)
1743 /* First adjust our frame pointer to its actual value. It was
1744 previously set to the start of the virtual area corresponding to
1745 the stacked variables when we branched here and now needs to be
1746 adjusted to the actual hardware fp value.
1748 Assignments are to virtual registers are converted by
1749 instantiate_virtual_regs into the corresponding assignment
1750 to the underlying register (fp in this case) that makes
1751 the original assignment true.
1752 So the following insn will actually be
1753 decrementing fp by STARTING_FRAME_OFFSET. */
1754 emit_move_insn (virtual_stack_vars_rtx
, hard_frame_pointer_rtx
);
1756 #if ARG_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
1757 if (fixed_regs
[ARG_POINTER_REGNUM
])
1759 #ifdef ELIMINABLE_REGS
1760 /* If the argument pointer can be eliminated in favor of the
1761 frame pointer, we don't need to restore it. We assume here
1762 that if such an elimination is present, it can always be used.
1763 This is the case on all known machines; if we don't make this
1764 assumption, we do unnecessary saving on many machines. */
1765 static const struct elims
{const int from
, to
;} elim_regs
[] = ELIMINABLE_REGS
;
1768 for (i
= 0; i
< ARRAY_SIZE (elim_regs
); i
++)
1769 if (elim_regs
[i
].from
== ARG_POINTER_REGNUM
1770 && elim_regs
[i
].to
== HARD_FRAME_POINTER_REGNUM
)
1773 if (i
== ARRAY_SIZE (elim_regs
))
1776 /* Now restore our arg pointer from the address at which it
1777 was saved in our stack frame. */
1778 emit_move_insn (crtl
->args
.internal_arg_pointer
,
1779 copy_to_reg (get_arg_pointer_save_area ()));
1784 #ifdef HAVE_nonlocal_goto_receiver
1785 if (HAVE_nonlocal_goto_receiver
)
1786 emit_insn (gen_nonlocal_goto_receiver ());
1789 /* We must not allow the code we just generated to be reordered by
1790 scheduling. Specifically, the update of the frame pointer must
1791 happen immediately, not later. */
1792 emit_insn (gen_blockage ());
1795 /* Generate RTL for the automatic variable declaration DECL.
1796 (Other kinds of declarations are simply ignored if seen here.) */
1799 expand_decl (tree decl
)
1803 type
= TREE_TYPE (decl
);
1805 /* For a CONST_DECL, set mode, alignment, and sizes from those of the
1806 type in case this node is used in a reference. */
1807 if (TREE_CODE (decl
) == CONST_DECL
)
1809 DECL_MODE (decl
) = TYPE_MODE (type
);
1810 DECL_ALIGN (decl
) = TYPE_ALIGN (type
);
1811 DECL_SIZE (decl
) = TYPE_SIZE (type
);
1812 DECL_SIZE_UNIT (decl
) = TYPE_SIZE_UNIT (type
);
1816 /* Otherwise, only automatic variables need any expansion done. Static and
1817 external variables, and external functions, will be handled by
1818 `assemble_variable' (called from finish_decl). TYPE_DECL requires
1819 nothing. PARM_DECLs are handled in `assign_parms'. */
1820 if (TREE_CODE (decl
) != VAR_DECL
)
1823 if (TREE_STATIC (decl
) || DECL_EXTERNAL (decl
))
1826 /* Create the RTL representation for the variable. */
1828 if (type
== error_mark_node
)
1829 SET_DECL_RTL (decl
, gen_rtx_MEM (BLKmode
, const0_rtx
));
1831 else if (DECL_SIZE (decl
) == 0)
1833 /* Variable with incomplete type. */
1835 if (DECL_INITIAL (decl
) == 0)
1836 /* Error message was already done; now avoid a crash. */
1837 x
= gen_rtx_MEM (BLKmode
, const0_rtx
);
1839 /* An initializer is going to decide the size of this array.
1840 Until we know the size, represent its address with a reg. */
1841 x
= gen_rtx_MEM (BLKmode
, gen_reg_rtx (Pmode
));
1843 set_mem_attributes (x
, decl
, 1);
1844 SET_DECL_RTL (decl
, x
);
1846 else if (use_register_for_decl (decl
))
1848 /* Automatic variable that can go in a register. */
1849 enum machine_mode reg_mode
= promote_decl_mode (decl
, NULL
);
1851 SET_DECL_RTL (decl
, gen_reg_rtx (reg_mode
));
1853 /* Note if the object is a user variable. */
1854 if (!DECL_ARTIFICIAL (decl
))
1855 mark_user_reg (DECL_RTL (decl
));
1857 if (POINTER_TYPE_P (type
))
1858 mark_reg_pointer (DECL_RTL (decl
),
1859 TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl
))));
1868 /* Variable-sized decls are dealt with in the gimplifier. */
1869 gcc_assert (TREE_CODE (DECL_SIZE_UNIT (decl
)) == INTEGER_CST
);
1871 /* If we previously made RTL for this decl, it must be an array
1872 whose size was determined by the initializer.
1873 The old address was a register; set that register now
1874 to the proper address. */
1875 if (DECL_RTL_SET_P (decl
))
1877 gcc_assert (MEM_P (DECL_RTL (decl
)));
1878 gcc_assert (REG_P (XEXP (DECL_RTL (decl
), 0)));
1879 oldaddr
= XEXP (DECL_RTL (decl
), 0);
1882 /* Set alignment we actually gave this decl. */
1883 DECL_ALIGN (decl
) = (DECL_MODE (decl
) == BLKmode
? BIGGEST_ALIGNMENT
1884 : GET_MODE_BITSIZE (DECL_MODE (decl
)));
1885 DECL_USER_ALIGN (decl
) = 0;
1887 x
= assign_temp (decl
, 1, 1, 1);
1888 set_mem_attributes (x
, decl
, 1);
1889 SET_DECL_RTL (decl
, x
);
1893 addr
= force_operand (XEXP (DECL_RTL (decl
), 0), oldaddr
);
1894 if (addr
!= oldaddr
)
1895 emit_move_insn (oldaddr
, addr
);
1900 /* Emit code to save the current value of stack. */
1902 expand_stack_save (void)
1906 do_pending_stack_adjust ();
1907 emit_stack_save (SAVE_BLOCK
, &ret
, NULL_RTX
);
1911 /* Emit code to restore the current value of stack. */
1913 expand_stack_restore (tree var
)
1915 rtx sa
= expand_normal (var
);
1917 sa
= convert_memory_address (Pmode
, sa
);
1918 emit_stack_restore (SAVE_BLOCK
, sa
, NULL_RTX
);
1921 /* Do the insertion of a case label into case_list. The labels are
1922 fed to us in descending order from the sorted vector of case labels used
1923 in the tree part of the middle end. So the list we construct is
1924 sorted in ascending order. The bounds on the case range, LOW and HIGH,
1925 are converted to case's index type TYPE. */
1927 static struct case_node
*
1928 add_case_node (struct case_node
*head
, tree type
, tree low
, tree high
,
1929 tree label
, alloc_pool case_node_pool
)
1931 tree min_value
, max_value
;
1932 struct case_node
*r
;
1934 gcc_assert (TREE_CODE (low
) == INTEGER_CST
);
1935 gcc_assert (!high
|| TREE_CODE (high
) == INTEGER_CST
);
1937 min_value
= TYPE_MIN_VALUE (type
);
1938 max_value
= TYPE_MAX_VALUE (type
);
1940 /* If there's no HIGH value, then this is not a case range; it's
1941 just a simple case label. But that's just a degenerate case
1943 If the bounds are equal, turn this into the one-value case. */
1944 if (!high
|| tree_int_cst_equal (low
, high
))
1946 /* If the simple case value is unreachable, ignore it. */
1947 if ((TREE_CODE (min_value
) == INTEGER_CST
1948 && tree_int_cst_compare (low
, min_value
) < 0)
1949 || (TREE_CODE (max_value
) == INTEGER_CST
1950 && tree_int_cst_compare (low
, max_value
) > 0))
1952 low
= fold_convert (type
, low
);
1957 /* If the entire case range is unreachable, ignore it. */
1958 if ((TREE_CODE (min_value
) == INTEGER_CST
1959 && tree_int_cst_compare (high
, min_value
) < 0)
1960 || (TREE_CODE (max_value
) == INTEGER_CST
1961 && tree_int_cst_compare (low
, max_value
) > 0))
1964 /* If the lower bound is less than the index type's minimum
1965 value, truncate the range bounds. */
1966 if (TREE_CODE (min_value
) == INTEGER_CST
1967 && tree_int_cst_compare (low
, min_value
) < 0)
1969 low
= fold_convert (type
, low
);
1971 /* If the upper bound is greater than the index type's maximum
1972 value, truncate the range bounds. */
1973 if (TREE_CODE (max_value
) == INTEGER_CST
1974 && tree_int_cst_compare (high
, max_value
) > 0)
1976 high
= fold_convert (type
, high
);
1980 /* Add this label to the chain. Make sure to drop overflow flags. */
1981 r
= (struct case_node
*) pool_alloc (case_node_pool
);
1982 r
->low
= build_int_cst_wide (TREE_TYPE (low
), TREE_INT_CST_LOW (low
),
1983 TREE_INT_CST_HIGH (low
));
1984 r
->high
= build_int_cst_wide (TREE_TYPE (high
), TREE_INT_CST_LOW (high
),
1985 TREE_INT_CST_HIGH (high
));
1986 r
->code_label
= label
;
1987 r
->parent
= r
->left
= NULL
;
1992 /* Maximum number of case bit tests. */
1993 #define MAX_CASE_BIT_TESTS 3
1995 /* By default, enable case bit tests on targets with ashlsi3. */
1996 #ifndef CASE_USE_BIT_TESTS
1997 #define CASE_USE_BIT_TESTS (optab_handler (ashl_optab, word_mode)->insn_code \
1998 != CODE_FOR_nothing)
2002 /* A case_bit_test represents a set of case nodes that may be
2003 selected from using a bit-wise comparison. HI and LO hold
2004 the integer to be tested against, LABEL contains the label
2005 to jump to upon success and BITS counts the number of case
2006 nodes handled by this test, typically the number of bits
2009 struct case_bit_test
2017 /* Determine whether "1 << x" is relatively cheap in word_mode. */
2020 bool lshift_cheap_p (void)
2022 static bool init
= false;
2023 static bool cheap
= true;
2027 rtx reg
= gen_rtx_REG (word_mode
, 10000);
2028 int cost
= rtx_cost (gen_rtx_ASHIFT (word_mode
, const1_rtx
, reg
), SET
,
2029 optimize_insn_for_speed_p ());
2030 cheap
= cost
< COSTS_N_INSNS (3);
2037 /* Comparison function for qsort to order bit tests by decreasing
2038 number of case nodes, i.e. the node with the most cases gets
2042 case_bit_test_cmp (const void *p1
, const void *p2
)
2044 const struct case_bit_test
*const d1
= (const struct case_bit_test
*) p1
;
2045 const struct case_bit_test
*const d2
= (const struct case_bit_test
*) p2
;
2047 if (d2
->bits
!= d1
->bits
)
2048 return d2
->bits
- d1
->bits
;
2050 /* Stabilize the sort. */
2051 return CODE_LABEL_NUMBER (d2
->label
) - CODE_LABEL_NUMBER (d1
->label
);
2054 /* Expand a switch statement by a short sequence of bit-wise
2055 comparisons. "switch(x)" is effectively converted into
2056 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
2059 INDEX_EXPR is the value being switched on, which is of
2060 type INDEX_TYPE. MINVAL is the lowest case value of in
2061 the case nodes, of INDEX_TYPE type, and RANGE is highest
2062 value minus MINVAL, also of type INDEX_TYPE. NODES is
2063 the set of case nodes, and DEFAULT_LABEL is the label to
2064 branch to should none of the cases match.
2066 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
2070 emit_case_bit_tests (tree index_type
, tree index_expr
, tree minval
,
2071 tree range
, case_node_ptr nodes
, rtx default_label
)
2073 struct case_bit_test test
[MAX_CASE_BIT_TESTS
];
2074 enum machine_mode mode
;
2075 rtx expr
, index
, label
;
2076 unsigned int i
,j
,lo
,hi
;
2077 struct case_node
*n
;
2081 for (n
= nodes
; n
; n
= n
->right
)
2083 label
= label_rtx (n
->code_label
);
2084 for (i
= 0; i
< count
; i
++)
2085 if (label
== test
[i
].label
)
2090 gcc_assert (count
< MAX_CASE_BIT_TESTS
);
2093 test
[i
].label
= label
;
2100 lo
= tree_low_cst (fold_build2 (MINUS_EXPR
, index_type
,
2101 n
->low
, minval
), 1);
2102 hi
= tree_low_cst (fold_build2 (MINUS_EXPR
, index_type
,
2103 n
->high
, minval
), 1);
2104 for (j
= lo
; j
<= hi
; j
++)
2105 if (j
>= HOST_BITS_PER_WIDE_INT
)
2106 test
[i
].hi
|= (HOST_WIDE_INT
) 1 << (j
- HOST_BITS_PER_INT
);
2108 test
[i
].lo
|= (HOST_WIDE_INT
) 1 << j
;
2111 qsort (test
, count
, sizeof(*test
), case_bit_test_cmp
);
2113 index_expr
= fold_build2 (MINUS_EXPR
, index_type
,
2114 fold_convert (index_type
, index_expr
),
2115 fold_convert (index_type
, minval
));
2116 index
= expand_normal (index_expr
);
2117 do_pending_stack_adjust ();
2119 mode
= TYPE_MODE (index_type
);
2120 expr
= expand_normal (range
);
2122 emit_cmp_and_jump_insns (index
, expr
, GTU
, NULL_RTX
, mode
, 1,
2125 index
= convert_to_mode (word_mode
, index
, 0);
2126 index
= expand_binop (word_mode
, ashl_optab
, const1_rtx
,
2127 index
, NULL_RTX
, 1, OPTAB_WIDEN
);
2129 for (i
= 0; i
< count
; i
++)
2131 expr
= immed_double_const (test
[i
].lo
, test
[i
].hi
, word_mode
);
2132 expr
= expand_binop (word_mode
, and_optab
, index
, expr
,
2133 NULL_RTX
, 1, OPTAB_WIDEN
);
2134 emit_cmp_and_jump_insns (expr
, const0_rtx
, NE
, NULL_RTX
,
2135 word_mode
, 1, test
[i
].label
);
2139 emit_jump (default_label
);
2143 #define HAVE_casesi 0
2146 #ifndef HAVE_tablejump
2147 #define HAVE_tablejump 0
2150 /* Terminate a case (Pascal/Ada) or switch (C) statement
2151 in which ORIG_INDEX is the expression to be tested.
2152 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
2153 type as given in the source before any compiler conversions.
2154 Generate the code to test it and jump to the right place. */
2157 expand_case (tree exp
)
2159 tree minval
= NULL_TREE
, maxval
= NULL_TREE
, range
= NULL_TREE
;
2160 rtx default_label
= 0;
2161 struct case_node
*n
;
2162 unsigned int count
, uniq
;
2168 rtx before_case
, end
, lab
;
2170 tree vec
= SWITCH_LABELS (exp
);
2171 tree orig_type
= TREE_TYPE (exp
);
2172 tree index_expr
= SWITCH_COND (exp
);
2173 tree index_type
= TREE_TYPE (index_expr
);
2174 int unsignedp
= TYPE_UNSIGNED (index_type
);
2176 /* The insn after which the case dispatch should finally
2177 be emitted. Zero for a dummy. */
2180 /* A list of case labels; it is first built as a list and it may then
2181 be rearranged into a nearly balanced binary tree. */
2182 struct case_node
*case_list
= 0;
2184 /* Label to jump to if no case matches. */
2185 tree default_label_decl
= NULL_TREE
;
2187 alloc_pool case_node_pool
= create_alloc_pool ("struct case_node pool",
2188 sizeof (struct case_node
),
2191 /* The switch body is lowered in gimplify.c, we should never have
2192 switches with a non-NULL SWITCH_BODY here. */
2193 gcc_assert (!SWITCH_BODY (exp
));
2194 gcc_assert (SWITCH_LABELS (exp
));
2196 do_pending_stack_adjust ();
2198 /* An ERROR_MARK occurs for various reasons including invalid data type. */
2199 if (index_type
!= error_mark_node
)
2202 bitmap label_bitmap
;
2203 int vl
= TREE_VEC_LENGTH (vec
);
2205 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
2206 expressions being INTEGER_CST. */
2207 gcc_assert (TREE_CODE (index_expr
) != INTEGER_CST
);
2209 /* The default case, if ever taken, is at the end of TREE_VEC. */
2210 elt
= TREE_VEC_ELT (vec
, vl
- 1);
2211 if (!CASE_LOW (elt
) && !CASE_HIGH (elt
))
2213 default_label_decl
= CASE_LABEL (elt
);
2217 for (i
= vl
- 1; i
>= 0; --i
)
2220 elt
= TREE_VEC_ELT (vec
, i
);
2222 low
= CASE_LOW (elt
);
2224 high
= CASE_HIGH (elt
);
2226 /* Discard empty ranges. */
2227 if (high
&& tree_int_cst_lt (high
, low
))
2230 case_list
= add_case_node (case_list
, index_type
, low
, high
,
2231 CASE_LABEL (elt
), case_node_pool
);
2235 before_case
= start
= get_last_insn ();
2236 if (default_label_decl
)
2237 default_label
= label_rtx (default_label_decl
);
2239 /* Get upper and lower bounds of case values. */
2243 label_bitmap
= BITMAP_ALLOC (NULL
);
2244 for (n
= case_list
; n
; n
= n
->right
)
2246 /* Count the elements and track the largest and smallest
2247 of them (treating them as signed even if they are not). */
2255 if (tree_int_cst_lt (n
->low
, minval
))
2257 if (tree_int_cst_lt (maxval
, n
->high
))
2260 /* A range counts double, since it requires two compares. */
2261 if (! tree_int_cst_equal (n
->low
, n
->high
))
2264 /* If we have not seen this label yet, then increase the
2265 number of unique case node targets seen. */
2266 lab
= label_rtx (n
->code_label
);
2267 if (!bitmap_bit_p (label_bitmap
, CODE_LABEL_NUMBER (lab
)))
2269 bitmap_set_bit (label_bitmap
, CODE_LABEL_NUMBER (lab
));
2274 BITMAP_FREE (label_bitmap
);
2276 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
2277 destination, such as one with a default case only. However,
2278 it doesn't remove cases that are out of range for the switch
2279 type, so we may still get a zero here. */
2283 emit_jump (default_label
);
2284 free_alloc_pool (case_node_pool
);
2288 /* Compute span of values. */
2289 range
= fold_build2 (MINUS_EXPR
, index_type
, maxval
, minval
);
2291 /* Try implementing this switch statement by a short sequence of
2292 bit-wise comparisons. However, we let the binary-tree case
2293 below handle constant index expressions. */
2294 if (CASE_USE_BIT_TESTS
2295 && ! TREE_CONSTANT (index_expr
)
2296 && compare_tree_int (range
, GET_MODE_BITSIZE (word_mode
)) < 0
2297 && compare_tree_int (range
, 0) > 0
2298 && lshift_cheap_p ()
2299 && ((uniq
== 1 && count
>= 3)
2300 || (uniq
== 2 && count
>= 5)
2301 || (uniq
== 3 && count
>= 6)))
2303 /* Optimize the case where all the case values fit in a
2304 word without having to subtract MINVAL. In this case,
2305 we can optimize away the subtraction. */
2306 if (compare_tree_int (minval
, 0) > 0
2307 && compare_tree_int (maxval
, GET_MODE_BITSIZE (word_mode
)) < 0)
2309 minval
= build_int_cst (index_type
, 0);
2312 emit_case_bit_tests (index_type
, index_expr
, minval
, range
,
2313 case_list
, default_label
);
2316 /* If range of values is much bigger than number of values,
2317 make a sequence of conditional branches instead of a dispatch.
2318 If the switch-index is a constant, do it this way
2319 because we can optimize it. */
2321 else if (count
< targetm
.case_values_threshold ()
2322 || compare_tree_int (range
,
2323 (optimize_insn_for_size_p () ? 3 : 10) * count
) > 0
2324 /* RANGE may be signed, and really large ranges will show up
2325 as negative numbers. */
2326 || compare_tree_int (range
, 0) < 0
2327 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
2330 || !flag_jump_tables
2331 || TREE_CONSTANT (index_expr
)
2332 /* If neither casesi or tablejump is available, we can
2333 only go this way. */
2334 || (!HAVE_casesi
&& !HAVE_tablejump
))
2336 index
= expand_normal (index_expr
);
2338 /* If the index is a short or char that we do not have
2339 an insn to handle comparisons directly, convert it to
2340 a full integer now, rather than letting each comparison
2341 generate the conversion. */
2343 if (GET_MODE_CLASS (GET_MODE (index
)) == MODE_INT
2344 && ! have_insn_for (COMPARE
, GET_MODE (index
)))
2346 enum machine_mode wider_mode
;
2347 for (wider_mode
= GET_MODE (index
); wider_mode
!= VOIDmode
;
2348 wider_mode
= GET_MODE_WIDER_MODE (wider_mode
))
2349 if (have_insn_for (COMPARE
, wider_mode
))
2351 index
= convert_to_mode (wider_mode
, index
, unsignedp
);
2356 do_pending_stack_adjust ();
2359 index
= copy_to_reg (index
);
2361 /* We generate a binary decision tree to select the
2362 appropriate target code. This is done as follows:
2364 The list of cases is rearranged into a binary tree,
2365 nearly optimal assuming equal probability for each case.
2367 The tree is transformed into RTL, eliminating
2368 redundant test conditions at the same time.
2370 If program flow could reach the end of the
2371 decision tree an unconditional jump to the
2372 default code is emitted. */
2375 = (TREE_CODE (orig_type
) != ENUMERAL_TYPE
2376 && estimate_case_costs (case_list
));
2377 balance_case_nodes (&case_list
, NULL
);
2378 emit_case_nodes (index
, case_list
, default_label
, index_type
);
2380 emit_jump (default_label
);
2384 rtx fallback_label
= label_rtx (case_list
->code_label
);
2385 table_label
= gen_label_rtx ();
2386 if (! try_casesi (index_type
, index_expr
, minval
, range
,
2387 table_label
, default_label
, fallback_label
))
2391 /* Index jumptables from zero for suitable values of
2392 minval to avoid a subtraction. */
2393 if (optimize_insn_for_speed_p ()
2394 && compare_tree_int (minval
, 0) > 0
2395 && compare_tree_int (minval
, 3) < 0)
2397 minval
= build_int_cst (index_type
, 0);
2401 ok
= try_tablejump (index_type
, index_expr
, minval
, range
,
2402 table_label
, default_label
);
2406 /* Get table of labels to jump to, in order of case index. */
2408 ncases
= tree_low_cst (range
, 0) + 1;
2409 labelvec
= XALLOCAVEC (rtx
, ncases
);
2410 memset (labelvec
, 0, ncases
* sizeof (rtx
));
2412 for (n
= case_list
; n
; n
= n
->right
)
2414 /* Compute the low and high bounds relative to the minimum
2415 value since that should fit in a HOST_WIDE_INT while the
2416 actual values may not. */
2418 = tree_low_cst (fold_build2 (MINUS_EXPR
, index_type
,
2419 n
->low
, minval
), 1);
2420 HOST_WIDE_INT i_high
2421 = tree_low_cst (fold_build2 (MINUS_EXPR
, index_type
,
2422 n
->high
, minval
), 1);
2425 for (i
= i_low
; i
<= i_high
; i
++)
2427 = gen_rtx_LABEL_REF (Pmode
, label_rtx (n
->code_label
));
2430 /* Fill in the gaps with the default. We may have gaps at
2431 the beginning if we tried to avoid the minval subtraction,
2432 so substitute some label even if the default label was
2433 deemed unreachable. */
2435 default_label
= fallback_label
;
2436 for (i
= 0; i
< ncases
; i
++)
2437 if (labelvec
[i
] == 0)
2438 labelvec
[i
] = gen_rtx_LABEL_REF (Pmode
, default_label
);
2440 /* Output the table. */
2441 emit_label (table_label
);
2443 if (CASE_VECTOR_PC_RELATIVE
|| flag_pic
)
2444 emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE
,
2445 gen_rtx_LABEL_REF (Pmode
, table_label
),
2446 gen_rtvec_v (ncases
, labelvec
),
2447 const0_rtx
, const0_rtx
));
2449 emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE
,
2450 gen_rtvec_v (ncases
, labelvec
)));
2452 /* Record no drop-through after the table. */
2456 before_case
= NEXT_INSN (before_case
);
2457 end
= get_last_insn ();
2458 reorder_insns (before_case
, end
, start
);
2462 free_alloc_pool (case_node_pool
);
2465 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */
2468 do_jump_if_equal (enum machine_mode mode
, rtx op0
, rtx op1
, rtx label
,
2471 do_compare_rtx_and_jump (op0
, op1
, EQ
, unsignedp
, mode
,
2472 NULL_RTX
, NULL_RTX
, label
);
2475 /* Not all case values are encountered equally. This function
2476 uses a heuristic to weight case labels, in cases where that
2477 looks like a reasonable thing to do.
2479 Right now, all we try to guess is text, and we establish the
2482 chars above space: 16
2491 If we find any cases in the switch that are not either -1 or in the range
2492 of valid ASCII characters, or are control characters other than those
2493 commonly used with "\", don't treat this switch scanning text.
2495 Return 1 if these nodes are suitable for cost estimation, otherwise
2499 estimate_case_costs (case_node_ptr node
)
2501 tree min_ascii
= integer_minus_one_node
;
2502 tree max_ascii
= build_int_cst (TREE_TYPE (node
->high
), 127);
2506 /* If we haven't already made the cost table, make it now. Note that the
2507 lower bound of the table is -1, not zero. */
2509 if (! cost_table_initialized
)
2511 cost_table_initialized
= 1;
2513 for (i
= 0; i
< 128; i
++)
2516 COST_TABLE (i
) = 16;
2517 else if (ISPUNCT (i
))
2519 else if (ISCNTRL (i
))
2520 COST_TABLE (i
) = -1;
2523 COST_TABLE (' ') = 8;
2524 COST_TABLE ('\t') = 4;
2525 COST_TABLE ('\0') = 4;
2526 COST_TABLE ('\n') = 2;
2527 COST_TABLE ('\f') = 1;
2528 COST_TABLE ('\v') = 1;
2529 COST_TABLE ('\b') = 1;
2532 /* See if all the case expressions look like text. It is text if the
2533 constant is >= -1 and the highest constant is <= 127. Do all comparisons
2534 as signed arithmetic since we don't want to ever access cost_table with a
2535 value less than -1. Also check that none of the constants in a range
2536 are strange control characters. */
2538 for (n
= node
; n
; n
= n
->right
)
2540 if (tree_int_cst_lt (n
->low
, min_ascii
)
2541 || tree_int_cst_lt (max_ascii
, n
->high
))
2544 for (i
= (HOST_WIDE_INT
) TREE_INT_CST_LOW (n
->low
);
2545 i
<= (HOST_WIDE_INT
) TREE_INT_CST_LOW (n
->high
); i
++)
2546 if (COST_TABLE (i
) < 0)
2550 /* All interesting values are within the range of interesting
2551 ASCII characters. */
2555 /* Take an ordered list of case nodes
2556 and transform them into a near optimal binary tree,
2557 on the assumption that any target code selection value is as
2558 likely as any other.
2560 The transformation is performed by splitting the ordered
2561 list into two equal sections plus a pivot. The parts are
2562 then attached to the pivot as left and right branches. Each
2563 branch is then transformed recursively. */
2566 balance_case_nodes (case_node_ptr
*head
, case_node_ptr parent
)
2579 /* Count the number of entries on branch. Also count the ranges. */
2583 if (!tree_int_cst_equal (np
->low
, np
->high
))
2587 cost
+= COST_TABLE (TREE_INT_CST_LOW (np
->high
));
2591 cost
+= COST_TABLE (TREE_INT_CST_LOW (np
->low
));
2599 /* Split this list if it is long enough for that to help. */
2604 /* Find the place in the list that bisects the list's total cost,
2605 Here I gets half the total cost. */
2610 /* Skip nodes while their cost does not reach that amount. */
2611 if (!tree_int_cst_equal ((*npp
)->low
, (*npp
)->high
))
2612 i
-= COST_TABLE (TREE_INT_CST_LOW ((*npp
)->high
));
2613 i
-= COST_TABLE (TREE_INT_CST_LOW ((*npp
)->low
));
2616 npp
= &(*npp
)->right
;
2621 /* Leave this branch lopsided, but optimize left-hand
2622 side and fill in `parent' fields for right-hand side. */
2624 np
->parent
= parent
;
2625 balance_case_nodes (&np
->left
, np
);
2626 for (; np
->right
; np
= np
->right
)
2627 np
->right
->parent
= np
;
2631 /* If there are just three nodes, split at the middle one. */
2633 npp
= &(*npp
)->right
;
2636 /* Find the place in the list that bisects the list's total cost,
2637 where ranges count as 2.
2638 Here I gets half the total cost. */
2639 i
= (i
+ ranges
+ 1) / 2;
2642 /* Skip nodes while their cost does not reach that amount. */
2643 if (!tree_int_cst_equal ((*npp
)->low
, (*npp
)->high
))
2648 npp
= &(*npp
)->right
;
2653 np
->parent
= parent
;
2656 /* Optimize each of the two split parts. */
2657 balance_case_nodes (&np
->left
, np
);
2658 balance_case_nodes (&np
->right
, np
);
2662 /* Else leave this branch as one level,
2663 but fill in `parent' fields. */
2665 np
->parent
= parent
;
2666 for (; np
->right
; np
= np
->right
)
2667 np
->right
->parent
= np
;
2672 /* Search the parent sections of the case node tree
2673 to see if a test for the lower bound of NODE would be redundant.
2674 INDEX_TYPE is the type of the index expression.
2676 The instructions to generate the case decision tree are
2677 output in the same order as nodes are processed so it is
2678 known that if a parent node checks the range of the current
2679 node minus one that the current node is bounded at its lower
2680 span. Thus the test would be redundant. */
2683 node_has_low_bound (case_node_ptr node
, tree index_type
)
2686 case_node_ptr pnode
;
2688 /* If the lower bound of this node is the lowest value in the index type,
2689 we need not test it. */
2691 if (tree_int_cst_equal (node
->low
, TYPE_MIN_VALUE (index_type
)))
2694 /* If this node has a left branch, the value at the left must be less
2695 than that at this node, so it cannot be bounded at the bottom and
2696 we need not bother testing any further. */
2701 low_minus_one
= fold_build2 (MINUS_EXPR
, TREE_TYPE (node
->low
),
2703 build_int_cst (TREE_TYPE (node
->low
), 1));
2705 /* If the subtraction above overflowed, we can't verify anything.
2706 Otherwise, look for a parent that tests our value - 1. */
2708 if (! tree_int_cst_lt (low_minus_one
, node
->low
))
2711 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
2712 if (tree_int_cst_equal (low_minus_one
, pnode
->high
))
2718 /* Search the parent sections of the case node tree
2719 to see if a test for the upper bound of NODE would be redundant.
2720 INDEX_TYPE is the type of the index expression.
2722 The instructions to generate the case decision tree are
2723 output in the same order as nodes are processed so it is
2724 known that if a parent node checks the range of the current
2725 node plus one that the current node is bounded at its upper
2726 span. Thus the test would be redundant. */
2729 node_has_high_bound (case_node_ptr node
, tree index_type
)
2732 case_node_ptr pnode
;
2734 /* If there is no upper bound, obviously no test is needed. */
2736 if (TYPE_MAX_VALUE (index_type
) == NULL
)
2739 /* If the upper bound of this node is the highest value in the type
2740 of the index expression, we need not test against it. */
2742 if (tree_int_cst_equal (node
->high
, TYPE_MAX_VALUE (index_type
)))
2745 /* If this node has a right branch, the value at the right must be greater
2746 than that at this node, so it cannot be bounded at the top and
2747 we need not bother testing any further. */
2752 high_plus_one
= fold_build2 (PLUS_EXPR
, TREE_TYPE (node
->high
),
2754 build_int_cst (TREE_TYPE (node
->high
), 1));
2756 /* If the addition above overflowed, we can't verify anything.
2757 Otherwise, look for a parent that tests our value + 1. */
2759 if (! tree_int_cst_lt (node
->high
, high_plus_one
))
2762 for (pnode
= node
->parent
; pnode
; pnode
= pnode
->parent
)
2763 if (tree_int_cst_equal (high_plus_one
, pnode
->low
))
2769 /* Search the parent sections of the
2770 case node tree to see if both tests for the upper and lower
2771 bounds of NODE would be redundant. */
2774 node_is_bounded (case_node_ptr node
, tree index_type
)
2776 return (node_has_low_bound (node
, index_type
)
2777 && node_has_high_bound (node
, index_type
));
2780 /* Emit step-by-step code to select a case for the value of INDEX.
2781 The thus generated decision tree follows the form of the
2782 case-node binary tree NODE, whose nodes represent test conditions.
2783 INDEX_TYPE is the type of the index of the switch.
2785 Care is taken to prune redundant tests from the decision tree
2786 by detecting any boundary conditions already checked by
2787 emitted rtx. (See node_has_high_bound, node_has_low_bound
2788 and node_is_bounded, above.)
2790 Where the test conditions can be shown to be redundant we emit
2791 an unconditional jump to the target code. As a further
2792 optimization, the subordinates of a tree node are examined to
2793 check for bounded nodes. In this case conditional and/or
2794 unconditional jumps as a result of the boundary check for the
2795 current node are arranged to target the subordinates associated
2796 code for out of bound conditions on the current node.
2798 We can assume that when control reaches the code generated here,
2799 the index value has already been compared with the parents
2800 of this node, and determined to be on the same side of each parent
2801 as this node is. Thus, if this node tests for the value 51,
2802 and a parent tested for 52, we don't need to consider
2803 the possibility of a value greater than 51. If another parent
2804 tests for the value 50, then this node need not test anything. */
2807 emit_case_nodes (rtx index
, case_node_ptr node
, rtx default_label
,
2810 /* If INDEX has an unsigned type, we must make unsigned branches. */
2811 int unsignedp
= TYPE_UNSIGNED (index_type
);
2812 enum machine_mode mode
= GET_MODE (index
);
2813 enum machine_mode imode
= TYPE_MODE (index_type
);
2815 /* Handle indices detected as constant during RTL expansion. */
2816 if (mode
== VOIDmode
)
2819 /* See if our parents have already tested everything for us.
2820 If they have, emit an unconditional jump for this node. */
2821 if (node_is_bounded (node
, index_type
))
2822 emit_jump (label_rtx (node
->code_label
));
2824 else if (tree_int_cst_equal (node
->low
, node
->high
))
2826 /* Node is single valued. First see if the index expression matches
2827 this node and then check our children, if any. */
2829 do_jump_if_equal (mode
, index
,
2830 convert_modes (mode
, imode
,
2831 expand_normal (node
->low
),
2833 label_rtx (node
->code_label
), unsignedp
);
2835 if (node
->right
!= 0 && node
->left
!= 0)
2837 /* This node has children on both sides.
2838 Dispatch to one side or the other
2839 by comparing the index value with this node's value.
2840 If one subtree is bounded, check that one first,
2841 so we can avoid real branches in the tree. */
2843 if (node_is_bounded (node
->right
, index_type
))
2845 emit_cmp_and_jump_insns (index
,
2848 expand_normal (node
->high
),
2850 GT
, NULL_RTX
, mode
, unsignedp
,
2851 label_rtx (node
->right
->code_label
));
2852 emit_case_nodes (index
, node
->left
, default_label
, index_type
);
2855 else if (node_is_bounded (node
->left
, index_type
))
2857 emit_cmp_and_jump_insns (index
,
2860 expand_normal (node
->high
),
2862 LT
, NULL_RTX
, mode
, unsignedp
,
2863 label_rtx (node
->left
->code_label
));
2864 emit_case_nodes (index
, node
->right
, default_label
, index_type
);
2867 /* If both children are single-valued cases with no
2868 children, finish up all the work. This way, we can save
2869 one ordered comparison. */
2870 else if (tree_int_cst_equal (node
->right
->low
, node
->right
->high
)
2871 && node
->right
->left
== 0
2872 && node
->right
->right
== 0
2873 && tree_int_cst_equal (node
->left
->low
, node
->left
->high
)
2874 && node
->left
->left
== 0
2875 && node
->left
->right
== 0)
2877 /* Neither node is bounded. First distinguish the two sides;
2878 then emit the code for one side at a time. */
2880 /* See if the value matches what the right hand side
2882 do_jump_if_equal (mode
, index
,
2883 convert_modes (mode
, imode
,
2884 expand_normal (node
->right
->low
),
2886 label_rtx (node
->right
->code_label
),
2889 /* See if the value matches what the left hand side
2891 do_jump_if_equal (mode
, index
,
2892 convert_modes (mode
, imode
,
2893 expand_normal (node
->left
->low
),
2895 label_rtx (node
->left
->code_label
),
2901 /* Neither node is bounded. First distinguish the two sides;
2902 then emit the code for one side at a time. */
2905 = build_decl (CURR_INSN_LOCATION
,
2906 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
2908 /* See if the value is on the right. */
2909 emit_cmp_and_jump_insns (index
,
2912 expand_normal (node
->high
),
2914 GT
, NULL_RTX
, mode
, unsignedp
,
2915 label_rtx (test_label
));
2917 /* Value must be on the left.
2918 Handle the left-hand subtree. */
2919 emit_case_nodes (index
, node
->left
, default_label
, index_type
);
2920 /* If left-hand subtree does nothing,
2923 emit_jump (default_label
);
2925 /* Code branches here for the right-hand subtree. */
2926 expand_label (test_label
);
2927 emit_case_nodes (index
, node
->right
, default_label
, index_type
);
2931 else if (node
->right
!= 0 && node
->left
== 0)
2933 /* Here we have a right child but no left so we issue a conditional
2934 branch to default and process the right child.
2936 Omit the conditional branch to default if the right child
2937 does not have any children and is single valued; it would
2938 cost too much space to save so little time. */
2940 if (node
->right
->right
|| node
->right
->left
2941 || !tree_int_cst_equal (node
->right
->low
, node
->right
->high
))
2943 if (!node_has_low_bound (node
, index_type
))
2945 emit_cmp_and_jump_insns (index
,
2948 expand_normal (node
->high
),
2950 LT
, NULL_RTX
, mode
, unsignedp
,
2954 emit_case_nodes (index
, node
->right
, default_label
, index_type
);
2957 /* We cannot process node->right normally
2958 since we haven't ruled out the numbers less than
2959 this node's value. So handle node->right explicitly. */
2960 do_jump_if_equal (mode
, index
,
2963 expand_normal (node
->right
->low
),
2965 label_rtx (node
->right
->code_label
), unsignedp
);
2968 else if (node
->right
== 0 && node
->left
!= 0)
2970 /* Just one subtree, on the left. */
2971 if (node
->left
->left
|| node
->left
->right
2972 || !tree_int_cst_equal (node
->left
->low
, node
->left
->high
))
2974 if (!node_has_high_bound (node
, index_type
))
2976 emit_cmp_and_jump_insns (index
,
2979 expand_normal (node
->high
),
2981 GT
, NULL_RTX
, mode
, unsignedp
,
2985 emit_case_nodes (index
, node
->left
, default_label
, index_type
);
2988 /* We cannot process node->left normally
2989 since we haven't ruled out the numbers less than
2990 this node's value. So handle node->left explicitly. */
2991 do_jump_if_equal (mode
, index
,
2994 expand_normal (node
->left
->low
),
2996 label_rtx (node
->left
->code_label
), unsignedp
);
3001 /* Node is a range. These cases are very similar to those for a single
3002 value, except that we do not start by testing whether this node
3003 is the one to branch to. */
3005 if (node
->right
!= 0 && node
->left
!= 0)
3007 /* Node has subtrees on both sides.
3008 If the right-hand subtree is bounded,
3009 test for it first, since we can go straight there.
3010 Otherwise, we need to make a branch in the control structure,
3011 then handle the two subtrees. */
3012 tree test_label
= 0;
3014 if (node_is_bounded (node
->right
, index_type
))
3015 /* Right hand node is fully bounded so we can eliminate any
3016 testing and branch directly to the target code. */
3017 emit_cmp_and_jump_insns (index
,
3020 expand_normal (node
->high
),
3022 GT
, NULL_RTX
, mode
, unsignedp
,
3023 label_rtx (node
->right
->code_label
));
3026 /* Right hand node requires testing.
3027 Branch to a label where we will handle it later. */
3029 test_label
= build_decl (CURR_INSN_LOCATION
,
3030 LABEL_DECL
, NULL_TREE
, NULL_TREE
);
3031 emit_cmp_and_jump_insns (index
,
3034 expand_normal (node
->high
),
3036 GT
, NULL_RTX
, mode
, unsignedp
,
3037 label_rtx (test_label
));
3040 /* Value belongs to this node or to the left-hand subtree. */
3042 emit_cmp_and_jump_insns (index
,
3045 expand_normal (node
->low
),
3047 GE
, NULL_RTX
, mode
, unsignedp
,
3048 label_rtx (node
->code_label
));
3050 /* Handle the left-hand subtree. */
3051 emit_case_nodes (index
, node
->left
, default_label
, index_type
);
3053 /* If right node had to be handled later, do that now. */
3057 /* If the left-hand subtree fell through,
3058 don't let it fall into the right-hand subtree. */
3060 emit_jump (default_label
);
3062 expand_label (test_label
);
3063 emit_case_nodes (index
, node
->right
, default_label
, index_type
);
3067 else if (node
->right
!= 0 && node
->left
== 0)
3069 /* Deal with values to the left of this node,
3070 if they are possible. */
3071 if (!node_has_low_bound (node
, index_type
))
3073 emit_cmp_and_jump_insns (index
,
3076 expand_normal (node
->low
),
3078 LT
, NULL_RTX
, mode
, unsignedp
,
3082 /* Value belongs to this node or to the right-hand subtree. */
3084 emit_cmp_and_jump_insns (index
,
3087 expand_normal (node
->high
),
3089 LE
, NULL_RTX
, mode
, unsignedp
,
3090 label_rtx (node
->code_label
));
3092 emit_case_nodes (index
, node
->right
, default_label
, index_type
);
3095 else if (node
->right
== 0 && node
->left
!= 0)
3097 /* Deal with values to the right of this node,
3098 if they are possible. */
3099 if (!node_has_high_bound (node
, index_type
))
3101 emit_cmp_and_jump_insns (index
,
3104 expand_normal (node
->high
),
3106 GT
, NULL_RTX
, mode
, unsignedp
,
3110 /* Value belongs to this node or to the left-hand subtree. */
3112 emit_cmp_and_jump_insns (index
,
3115 expand_normal (node
->low
),
3117 GE
, NULL_RTX
, mode
, unsignedp
,
3118 label_rtx (node
->code_label
));
3120 emit_case_nodes (index
, node
->left
, default_label
, index_type
);
3125 /* Node has no children so we check low and high bounds to remove
3126 redundant tests. Only one of the bounds can exist,
3127 since otherwise this node is bounded--a case tested already. */
3128 int high_bound
= node_has_high_bound (node
, index_type
);
3129 int low_bound
= node_has_low_bound (node
, index_type
);
3131 if (!high_bound
&& low_bound
)
3133 emit_cmp_and_jump_insns (index
,
3136 expand_normal (node
->high
),
3138 GT
, NULL_RTX
, mode
, unsignedp
,
3142 else if (!low_bound
&& high_bound
)
3144 emit_cmp_and_jump_insns (index
,
3147 expand_normal (node
->low
),
3149 LT
, NULL_RTX
, mode
, unsignedp
,
3152 else if (!low_bound
&& !high_bound
)
3154 /* Widen LOW and HIGH to the same width as INDEX. */
3155 tree type
= lang_hooks
.types
.type_for_mode (mode
, unsignedp
);
3156 tree low
= build1 (CONVERT_EXPR
, type
, node
->low
);
3157 tree high
= build1 (CONVERT_EXPR
, type
, node
->high
);
3158 rtx low_rtx
, new_index
, new_bound
;
3160 /* Instead of doing two branches, emit one unsigned branch for
3161 (index-low) > (high-low). */
3162 low_rtx
= expand_expr (low
, NULL_RTX
, mode
, EXPAND_NORMAL
);
3163 new_index
= expand_simple_binop (mode
, MINUS
, index
, low_rtx
,
3164 NULL_RTX
, unsignedp
,
3166 new_bound
= expand_expr (fold_build2 (MINUS_EXPR
, type
,
3168 NULL_RTX
, mode
, EXPAND_NORMAL
);
3170 emit_cmp_and_jump_insns (new_index
, new_bound
, GT
, NULL_RTX
,
3171 mode
, 1, default_label
);
3174 emit_jump (label_rtx (node
->code_label
));