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 2010 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"
44 #include "diagnostic-core.h"
48 #include "langhooks.h"
54 #include "alloc-pool.h"
55 #include "pretty-print.h"
59 /* Functions and data structures for expanding case statements. */
61 /* Case label structure, used to hold info on labels within case
62 statements. We handle "range" labels; for a single-value label
63 as in C, the high and low limits are the same.
65 We start with a vector of case nodes sorted in ascending order, and
66 the default label as the last element in the vector. Before expanding
67 to RTL, we transform this vector into a list linked via the RIGHT
68 fields in the case_node struct. Nodes with higher case values are
71 Switch statements can be output in three forms. A branch table is
72 used if there are more than a few labels and the labels are dense
73 within the range between the smallest and largest case value. If a
74 branch table is used, no further manipulations are done with the case
77 The alternative to the use of a branch table is to generate a series
78 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
79 and PARENT fields to hold a binary tree. Initially the tree is
80 totally unbalanced, with everything on the right. We balance the tree
81 with nodes on the left having lower case values than the parent
82 and nodes on the right having higher values. We then output the tree
85 For very small, suitable switch statements, we can generate a series
86 of simple bit test and branches instead. */
90 struct case_node *left; /* Left son in binary tree */
91 struct case_node *right; /* Right son in binary tree; also node chain */
92 struct case_node *parent; /* Parent of node in binary tree */
93 tree low; /* Lowest index value for this label */
94 tree high; /* Highest index value for this label */
95 tree code_label; /* Label to jump to when node matches */
98 typedef struct case_node case_node;
99 typedef struct case_node *case_node_ptr;
101 /* These are used by estimate_case_costs and balance_case_nodes. */
103 /* This must be a signed type, and non-ANSI compilers lack signed char. */
104 static short cost_table_[129];
105 static int use_cost_table;
106 static int cost_table_initialized;
108 /* Special care is needed because we allow -1, but TREE_INT_CST_LOW
110 #define COST_TABLE(I) cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)]
112 static int n_occurrences (int, const char *);
113 static bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *);
114 static void expand_nl_goto_receiver (void);
115 static bool check_operand_nalternatives (tree, tree);
116 static bool check_unique_operand_names (tree, tree, tree);
117 static char *resolve_operand_name_1 (char *, tree, tree, tree);
118 static void expand_null_return_1 (void);
119 static void expand_value_return (rtx);
120 static int estimate_case_costs (case_node_ptr);
121 static bool lshift_cheap_p (void);
122 static int case_bit_test_cmp (const void *, const void *);
123 static void emit_case_bit_tests (tree, tree, tree, tree, case_node_ptr, rtx);
124 static void balance_case_nodes (case_node_ptr *, case_node_ptr);
125 static int node_has_low_bound (case_node_ptr, tree);
126 static int node_has_high_bound (case_node_ptr, tree);
127 static int node_is_bounded (case_node_ptr, tree);
128 static void emit_case_nodes (rtx, case_node_ptr, rtx, tree);
129 static struct case_node *add_case_node (struct case_node *, tree,
130 tree, tree, tree, alloc_pool);
133 /* Return the rtx-label that corresponds to a LABEL_DECL,
134 creating it if necessary. */
137 label_rtx (tree label)
139 gcc_assert (TREE_CODE (label) == LABEL_DECL);
141 if (!DECL_RTL_SET_P (label))
143 rtx r = gen_label_rtx ();
144 SET_DECL_RTL (label, r);
145 if (FORCED_LABEL (label) || DECL_NONLOCAL (label))
146 LABEL_PRESERVE_P (r) = 1;
149 return DECL_RTL (label);
152 /* As above, but also put it on the forced-reference list of the
153 function that contains it. */
155 force_label_rtx (tree label)
157 rtx ref = label_rtx (label);
158 tree function = decl_function_context (label);
160 gcc_assert (function);
162 forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref, forced_labels);
166 /* Add an unconditional jump to LABEL as the next sequential instruction. */
169 emit_jump (rtx label)
171 do_pending_stack_adjust ();
172 emit_jump_insn (gen_jump (label));
176 /* Emit code to jump to the address
177 specified by the pointer expression EXP. */
180 expand_computed_goto (tree exp)
182 rtx x = expand_normal (exp);
184 x = convert_memory_address (Pmode, x);
186 do_pending_stack_adjust ();
187 emit_indirect_jump (x);
190 /* Handle goto statements and the labels that they can go to. */
192 /* Specify the location in the RTL code of a label LABEL,
193 which is a LABEL_DECL tree node.
195 This is used for the kind of label that the user can jump to with a
196 goto statement, and for alternatives of a switch or case statement.
197 RTL labels generated for loops and conditionals don't go through here;
198 they are generated directly at the RTL level, by other functions below.
200 Note that this has nothing to do with defining label *names*.
201 Languages vary in how they do that and what that even means. */
204 expand_label (tree label)
206 rtx label_r = label_rtx (label);
208 do_pending_stack_adjust ();
209 emit_label (label_r);
210 if (DECL_NAME (label))
211 LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label));
213 if (DECL_NONLOCAL (label))
215 expand_nl_goto_receiver ();
216 nonlocal_goto_handler_labels
217 = gen_rtx_EXPR_LIST (VOIDmode, label_r,
218 nonlocal_goto_handler_labels);
221 if (FORCED_LABEL (label))
222 forced_labels = gen_rtx_EXPR_LIST (VOIDmode, label_r, forced_labels);
224 if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
225 maybe_set_first_label_num (label_r);
228 /* Generate RTL code for a `goto' statement with target label LABEL.
229 LABEL should be a LABEL_DECL tree node that was or will later be
230 defined with `expand_label'. */
233 expand_goto (tree label)
235 #ifdef ENABLE_CHECKING
236 /* Check for a nonlocal goto to a containing function. Should have
237 gotten translated to __builtin_nonlocal_goto. */
238 tree context = decl_function_context (label);
239 gcc_assert (!context || context == current_function_decl);
242 emit_jump (label_rtx (label));
245 /* Return the number of times character C occurs in string S. */
247 n_occurrences (int c, const char *s)
255 /* Generate RTL for an asm statement (explicit assembler code).
256 STRING is a STRING_CST node containing the assembler code text,
257 or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the
258 insn is volatile; don't optimize it. */
261 expand_asm_loc (tree string, int vol, location_t locus)
265 if (TREE_CODE (string) == ADDR_EXPR)
266 string = TREE_OPERAND (string, 0);
268 body = gen_rtx_ASM_INPUT_loc (VOIDmode,
269 ggc_strdup (TREE_STRING_POINTER (string)),
272 MEM_VOLATILE_P (body) = vol;
277 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
278 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
279 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
280 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
281 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
282 constraint allows the use of a register operand. And, *IS_INOUT
283 will be true if the operand is read-write, i.e., if it is used as
284 an input as well as an output. If *CONSTRAINT_P is not in
285 canonical form, it will be made canonical. (Note that `+' will be
286 replaced with `=' as part of this process.)
288 Returns TRUE if all went well; FALSE if an error occurred. */
291 parse_output_constraint (const char **constraint_p, int operand_num,
292 int ninputs, int noutputs, bool *allows_mem,
293 bool *allows_reg, bool *is_inout)
295 const char *constraint = *constraint_p;
298 /* Assume the constraint doesn't allow the use of either a register
303 /* Allow the `=' or `+' to not be at the beginning of the string,
304 since it wasn't explicitly documented that way, and there is a
305 large body of code that puts it last. Swap the character to
306 the front, so as not to uglify any place else. */
307 p = strchr (constraint, '=');
309 p = strchr (constraint, '+');
311 /* If the string doesn't contain an `=', issue an error
315 error ("output operand constraint lacks %<=%>");
319 /* If the constraint begins with `+', then the operand is both read
320 from and written to. */
321 *is_inout = (*p == '+');
323 /* Canonicalize the output constraint so that it begins with `='. */
324 if (p != constraint || *is_inout)
327 size_t c_len = strlen (constraint);
330 warning (0, "output constraint %qc for operand %d "
331 "is not at the beginning",
334 /* Make a copy of the constraint. */
335 buf = XALLOCAVEC (char, c_len + 1);
336 strcpy (buf, constraint);
337 /* Swap the first character and the `=' or `+'. */
338 buf[p - constraint] = buf[0];
339 /* Make sure the first character is an `='. (Until we do this,
340 it might be a `+'.) */
342 /* Replace the constraint with the canonicalized string. */
343 *constraint_p = ggc_alloc_string (buf, c_len);
344 constraint = *constraint_p;
347 /* Loop through the constraint string. */
348 for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p))
353 error ("operand constraint contains incorrectly positioned "
358 if (operand_num + 1 == ninputs + noutputs)
360 error ("%<%%%> constraint used with last operand");
365 case 'V': case TARGET_MEM_CONSTRAINT: case 'o':
369 case '?': case '!': case '*': case '&': case '#':
370 case 'E': case 'F': case 'G': case 'H':
371 case 's': case 'i': case 'n':
372 case 'I': case 'J': case 'K': case 'L': case 'M':
373 case 'N': case 'O': case 'P': case ',':
376 case '0': case '1': case '2': case '3': case '4':
377 case '5': case '6': case '7': case '8': case '9':
379 error ("matching constraint not valid in output operand");
383 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
384 excepting those that expand_call created. So match memory
401 if (REG_CLASS_FROM_CONSTRAINT (*p, p) != NO_REGS)
403 #ifdef EXTRA_CONSTRAINT_STR
404 else if (EXTRA_ADDRESS_CONSTRAINT (*p, p))
406 else if (EXTRA_MEMORY_CONSTRAINT (*p, p))
410 /* Otherwise we can't assume anything about the nature of
411 the constraint except that it isn't purely registers.
412 Treat it like "g" and hope for the best. */
423 /* Similar, but for input constraints. */
426 parse_input_constraint (const char **constraint_p, int input_num,
427 int ninputs, int noutputs, int ninout,
428 const char * const * constraints,
429 bool *allows_mem, bool *allows_reg)
431 const char *constraint = *constraint_p;
432 const char *orig_constraint = constraint;
433 size_t c_len = strlen (constraint);
435 bool saw_match = false;
437 /* Assume the constraint doesn't allow the use of either
438 a register or memory. */
442 /* Make sure constraint has neither `=', `+', nor '&'. */
444 for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
445 switch (constraint[j])
447 case '+': case '=': case '&':
448 if (constraint == orig_constraint)
450 error ("input operand constraint contains %qc", constraint[j]);
456 if (constraint == orig_constraint
457 && input_num + 1 == ninputs - ninout)
459 error ("%<%%%> constraint used with last operand");
464 case 'V': case TARGET_MEM_CONSTRAINT: case 'o':
469 case '?': case '!': case '*': case '#':
470 case 'E': case 'F': case 'G': case 'H':
471 case 's': case 'i': case 'n':
472 case 'I': case 'J': case 'K': case 'L': case 'M':
473 case 'N': case 'O': case 'P': case ',':
476 /* Whether or not a numeric constraint allows a register is
477 decided by the matching constraint, and so there is no need
478 to do anything special with them. We must handle them in
479 the default case, so that we don't unnecessarily force
480 operands to memory. */
481 case '0': case '1': case '2': case '3': case '4':
482 case '5': case '6': case '7': case '8': case '9':
489 match = strtoul (constraint + j, &end, 10);
490 if (match >= (unsigned long) noutputs)
492 error ("matching constraint references invalid operand number");
496 /* Try and find the real constraint for this dup. Only do this
497 if the matching constraint is the only alternative. */
499 && (j == 0 || (j == 1 && constraint[0] == '%')))
501 constraint = constraints[match];
502 *constraint_p = constraint;
503 c_len = strlen (constraint);
505 /* ??? At the end of the loop, we will skip the first part of
506 the matched constraint. This assumes not only that the
507 other constraint is an output constraint, but also that
508 the '=' or '+' come first. */
512 j = end - constraint;
513 /* Anticipate increment at end of loop. */
528 if (! ISALPHA (constraint[j]))
530 error ("invalid punctuation %qc in constraint", constraint[j]);
533 if (REG_CLASS_FROM_CONSTRAINT (constraint[j], constraint + j)
536 #ifdef EXTRA_CONSTRAINT_STR
537 else if (EXTRA_ADDRESS_CONSTRAINT (constraint[j], constraint + j))
539 else if (EXTRA_MEMORY_CONSTRAINT (constraint[j], constraint + j))
543 /* Otherwise we can't assume anything about the nature of
544 the constraint except that it isn't purely registers.
545 Treat it like "g" and hope for the best. */
553 if (saw_match && !*allows_reg)
554 warning (0, "matching constraint does not allow a register");
559 /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
560 can be an asm-declared register. Called via walk_tree. */
563 decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED,
567 const HARD_REG_SET *const regs = (const HARD_REG_SET *) data;
569 if (TREE_CODE (decl) == VAR_DECL)
571 if (DECL_HARD_REGISTER (decl)
572 && REG_P (DECL_RTL (decl))
573 && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
575 rtx reg = DECL_RTL (decl);
577 if (overlaps_hard_reg_set_p (*regs, GET_MODE (reg), REGNO (reg)))
582 else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL)
587 /* If there is an overlap between *REGS and DECL, return the first overlap
590 tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs)
592 return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL);
595 /* Check for overlap between registers marked in CLOBBERED_REGS and
596 anything inappropriate in T. Emit error and return the register
597 variable definition for error, NULL_TREE for ok. */
600 tree_conflicts_with_clobbers_p (tree t, HARD_REG_SET *clobbered_regs)
602 /* Conflicts between asm-declared register variables and the clobber
603 list are not allowed. */
604 tree overlap = tree_overlaps_hard_reg_set (t, clobbered_regs);
608 error ("asm-specifier for variable %qE conflicts with asm clobber list",
609 DECL_NAME (overlap));
611 /* Reset registerness to stop multiple errors emitted for a single
613 DECL_REGISTER (overlap) = 0;
620 /* Generate RTL for an asm statement with arguments.
621 STRING is the instruction template.
622 OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs.
623 Each output or input has an expression in the TREE_VALUE and
624 a tree list in TREE_PURPOSE which in turn contains a constraint
625 name in TREE_VALUE (or NULL_TREE) and a constraint string
627 CLOBBERS is a list of STRING_CST nodes each naming a hard register
628 that is clobbered by this insn.
630 Not all kinds of lvalue that may appear in OUTPUTS can be stored directly.
631 Some elements of OUTPUTS may be replaced with trees representing temporary
632 values. The caller should copy those temporary values to the originally
635 VOL nonzero means the insn is volatile; don't optimize it. */
638 expand_asm_operands (tree string, tree outputs, tree inputs,
639 tree clobbers, tree labels, int vol, location_t locus)
641 rtvec argvec, constraintvec, labelvec;
643 int ninputs = list_length (inputs);
644 int noutputs = list_length (outputs);
645 int nlabels = list_length (labels);
648 HARD_REG_SET clobbered_regs;
649 int clobber_conflict_found = 0;
653 /* Vector of RTX's of evaluated output operands. */
654 rtx *output_rtx = XALLOCAVEC (rtx, noutputs);
655 int *inout_opnum = XALLOCAVEC (int, noutputs);
656 rtx *real_output_rtx = XALLOCAVEC (rtx, noutputs);
657 enum machine_mode *inout_mode = XALLOCAVEC (enum machine_mode, noutputs);
658 const char **constraints = XALLOCAVEC (const char *, noutputs + ninputs);
659 int old_generating_concat_p = generating_concat_p;
661 /* An ASM with no outputs needs to be treated as volatile, for now. */
665 if (! check_operand_nalternatives (outputs, inputs))
668 string = resolve_asm_operand_names (string, outputs, inputs, labels);
670 /* Collect constraints. */
672 for (t = outputs; t ; t = TREE_CHAIN (t), i++)
673 constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
674 for (t = inputs; t ; t = TREE_CHAIN (t), i++)
675 constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
677 /* Sometimes we wish to automatically clobber registers across an asm.
678 Case in point is when the i386 backend moved from cc0 to a hard reg --
679 maintaining source-level compatibility means automatically clobbering
680 the flags register. */
681 clobbers = targetm.md_asm_clobbers (outputs, inputs, clobbers);
683 /* Count the number of meaningful clobbered registers, ignoring what
684 we would ignore later. */
686 CLEAR_HARD_REG_SET (clobbered_regs);
687 for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
692 if (TREE_VALUE (tail) == error_mark_node)
694 regname = TREE_STRING_POINTER (TREE_VALUE (tail));
696 i = decode_reg_name_and_count (regname, &nregs);
700 error ("unknown register name %qs in %<asm%>", regname);
702 /* Mark clobbered registers. */
707 for (reg = i; reg < i + nregs; reg++)
711 /* Clobbering the PIC register is an error. */
712 if (reg == (int) PIC_OFFSET_TABLE_REGNUM)
714 error ("PIC register clobbered by %qs in %<asm%>", regname);
718 SET_HARD_REG_BIT (clobbered_regs, reg);
723 /* First pass over inputs and outputs checks validity and sets
724 mark_addressable if needed. */
727 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
729 tree val = TREE_VALUE (tail);
730 tree type = TREE_TYPE (val);
731 const char *constraint;
736 /* If there's an erroneous arg, emit no insn. */
737 if (type == error_mark_node)
740 /* Try to parse the output constraint. If that fails, there's
741 no point in going further. */
742 constraint = constraints[i];
743 if (!parse_output_constraint (&constraint, i, ninputs, noutputs,
744 &allows_mem, &allows_reg, &is_inout))
751 && REG_P (DECL_RTL (val))
752 && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))))
753 mark_addressable (val);
760 if (ninputs + noutputs > MAX_RECOG_OPERANDS)
762 error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS);
766 for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail))
768 bool allows_reg, allows_mem;
769 const char *constraint;
771 /* If there's an erroneous arg, emit no insn, because the ASM_INPUT
772 would get VOIDmode and that could cause a crash in reload. */
773 if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node)
776 constraint = constraints[i + noutputs];
777 if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
778 constraints, &allows_mem, &allows_reg))
781 if (! allows_reg && allows_mem)
782 mark_addressable (TREE_VALUE (tail));
785 /* Second pass evaluates arguments. */
787 /* Make sure stack is consistent for asm goto. */
789 do_pending_stack_adjust ();
792 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
794 tree val = TREE_VALUE (tail);
795 tree type = TREE_TYPE (val);
802 ok = parse_output_constraint (&constraints[i], i, ninputs,
803 noutputs, &allows_mem, &allows_reg,
807 /* If an output operand is not a decl or indirect ref and our constraint
808 allows a register, make a temporary to act as an intermediate.
809 Make the asm insn write into that, then our caller will copy it to
810 the real output operand. Likewise for promoted variables. */
812 generating_concat_p = 0;
814 real_output_rtx[i] = NULL_RTX;
815 if ((TREE_CODE (val) == INDIRECT_REF
818 && (allows_mem || REG_P (DECL_RTL (val)))
819 && ! (REG_P (DECL_RTL (val))
820 && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))
824 op = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE);
826 op = validize_mem (op);
828 if (! allows_reg && !MEM_P (op))
829 error ("output number %d not directly addressable", i);
830 if ((! allows_mem && MEM_P (op))
831 || GET_CODE (op) == CONCAT)
833 real_output_rtx[i] = op;
834 op = gen_reg_rtx (GET_MODE (op));
836 emit_move_insn (op, real_output_rtx[i]);
841 op = assign_temp (type, 0, 0, 1);
842 op = validize_mem (op);
843 if (!MEM_P (op) && TREE_CODE (TREE_VALUE (tail)) == SSA_NAME)
844 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (TREE_VALUE (tail)), op);
845 TREE_VALUE (tail) = make_tree (type, op);
849 generating_concat_p = old_generating_concat_p;
853 inout_mode[ninout] = TYPE_MODE (type);
854 inout_opnum[ninout++] = i;
857 if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
858 clobber_conflict_found = 1;
861 /* Make vectors for the expression-rtx, constraint strings,
862 and named operands. */
864 argvec = rtvec_alloc (ninputs);
865 constraintvec = rtvec_alloc (ninputs);
866 labelvec = rtvec_alloc (nlabels);
868 body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode
869 : GET_MODE (output_rtx[0])),
870 ggc_strdup (TREE_STRING_POINTER (string)),
871 empty_string, 0, argvec, constraintvec,
874 MEM_VOLATILE_P (body) = vol;
876 /* Eval the inputs and put them into ARGVEC.
877 Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */
879 for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i)
881 bool allows_reg, allows_mem;
882 const char *constraint;
887 constraint = constraints[i + noutputs];
888 ok = parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
889 constraints, &allows_mem, &allows_reg);
892 generating_concat_p = 0;
894 val = TREE_VALUE (tail);
895 type = TREE_TYPE (val);
896 /* EXPAND_INITIALIZER will not generate code for valid initializer
897 constants, but will still generate code for other types of operand.
898 This is the behavior we want for constant constraints. */
899 op = expand_expr (val, NULL_RTX, VOIDmode,
900 allows_reg ? EXPAND_NORMAL
901 : allows_mem ? EXPAND_MEMORY
902 : EXPAND_INITIALIZER);
904 /* Never pass a CONCAT to an ASM. */
905 if (GET_CODE (op) == CONCAT)
906 op = force_reg (GET_MODE (op), op);
908 op = validize_mem (op);
910 if (asm_operand_ok (op, constraint, NULL) <= 0)
912 if (allows_reg && TYPE_MODE (type) != BLKmode)
913 op = force_reg (TYPE_MODE (type), op);
914 else if (!allows_mem)
915 warning (0, "asm operand %d probably doesn%'t match constraints",
919 /* We won't recognize either volatile memory or memory
920 with a queued address as available a memory_operand
921 at this point. Ignore it: clearly this *is* a memory. */
925 warning (0, "use of memory input without lvalue in "
926 "asm operand %d is deprecated", i + noutputs);
930 rtx mem = force_const_mem (TYPE_MODE (type), op);
932 op = validize_mem (mem);
934 op = force_reg (TYPE_MODE (type), op);
937 || GET_CODE (op) == SUBREG
938 || GET_CODE (op) == CONCAT)
940 tree qual_type = build_qualified_type (type,
943 rtx memloc = assign_temp (qual_type, 1, 1, 1);
944 memloc = validize_mem (memloc);
945 emit_move_insn (memloc, op);
951 generating_concat_p = old_generating_concat_p;
952 ASM_OPERANDS_INPUT (body, i) = op;
954 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i)
955 = gen_rtx_ASM_INPUT (TYPE_MODE (type),
956 ggc_strdup (constraints[i + noutputs]));
958 if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
959 clobber_conflict_found = 1;
962 /* Protect all the operands from the queue now that they have all been
965 generating_concat_p = 0;
967 /* For in-out operands, copy output rtx to input rtx. */
968 for (i = 0; i < ninout; i++)
970 int j = inout_opnum[i];
973 ASM_OPERANDS_INPUT (body, ninputs - ninout + i)
976 sprintf (buffer, "%d", j);
977 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i)
978 = gen_rtx_ASM_INPUT (inout_mode[i], ggc_strdup (buffer));
981 /* Copy labels to the vector. */
982 for (i = 0, tail = labels; i < nlabels; ++i, tail = TREE_CHAIN (tail))
983 ASM_OPERANDS_LABEL (body, i)
984 = gen_rtx_LABEL_REF (Pmode, label_rtx (TREE_VALUE (tail)));
986 generating_concat_p = old_generating_concat_p;
988 /* Now, for each output, construct an rtx
989 (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER
990 ARGVEC CONSTRAINTS OPNAMES))
991 If there is more than one, put them inside a PARALLEL. */
993 if (nlabels > 0 && nclobbers == 0)
995 gcc_assert (noutputs == 0);
996 emit_jump_insn (body);
998 else if (noutputs == 0 && nclobbers == 0)
1000 /* No output operands: put in a raw ASM_OPERANDS rtx. */
1003 else if (noutputs == 1 && nclobbers == 0)
1005 ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = ggc_strdup (constraints[0]);
1006 emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body));
1016 body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers));
1018 /* For each output operand, store a SET. */
1019 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1021 XVECEXP (body, 0, i)
1022 = gen_rtx_SET (VOIDmode,
1024 gen_rtx_ASM_OPERANDS
1025 (GET_MODE (output_rtx[i]),
1026 ggc_strdup (TREE_STRING_POINTER (string)),
1027 ggc_strdup (constraints[i]),
1028 i, argvec, constraintvec, labelvec, locus));
1030 MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol;
1033 /* If there are no outputs (but there are some clobbers)
1034 store the bare ASM_OPERANDS into the PARALLEL. */
1037 XVECEXP (body, 0, i++) = obody;
1039 /* Store (clobber REG) for each clobbered register specified. */
1041 for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
1043 const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
1045 int j = decode_reg_name_and_count (regname, &nregs);
1050 if (j == -3) /* `cc', which is not a register */
1053 if (j == -4) /* `memory', don't cache memory across asm */
1055 XVECEXP (body, 0, i++)
1056 = gen_rtx_CLOBBER (VOIDmode,
1059 gen_rtx_SCRATCH (VOIDmode)));
1063 /* Ignore unknown register, error already signaled. */
1067 for (reg = j; reg < j + nregs; reg++)
1069 /* Use QImode since that's guaranteed to clobber just
1071 clobbered_reg = gen_rtx_REG (QImode, reg);
1073 /* Do sanity check for overlap between clobbers and
1074 respectively input and outputs that hasn't been
1075 handled. Such overlap should have been detected and
1077 if (!clobber_conflict_found)
1081 /* We test the old body (obody) contents to avoid
1082 tripping over the under-construction body. */
1083 for (opno = 0; opno < noutputs; opno++)
1084 if (reg_overlap_mentioned_p (clobbered_reg,
1087 ("asm clobber conflict with output operand");
1089 for (opno = 0; opno < ninputs - ninout; opno++)
1090 if (reg_overlap_mentioned_p (clobbered_reg,
1091 ASM_OPERANDS_INPUT (obody,
1094 ("asm clobber conflict with input operand");
1097 XVECEXP (body, 0, i++)
1098 = gen_rtx_CLOBBER (VOIDmode, clobbered_reg);
1103 emit_jump_insn (body);
1108 /* For any outputs that needed reloading into registers, spill them
1109 back to where they belong. */
1110 for (i = 0; i < noutputs; ++i)
1111 if (real_output_rtx[i])
1112 emit_move_insn (real_output_rtx[i], output_rtx[i]);
1114 crtl->has_asm_statement = 1;
1119 expand_asm_stmt (gimple stmt)
1122 tree outputs, tail, t;
1126 tree str, out, in, cl, labels;
1127 location_t locus = gimple_location (stmt);
1129 /* Meh... convert the gimple asm operands into real tree lists.
1130 Eventually we should make all routines work on the vectors instead
1131 of relying on TREE_CHAIN. */
1133 n = gimple_asm_noutputs (stmt);
1136 t = out = gimple_asm_output_op (stmt, 0);
1137 for (i = 1; i < n; i++)
1138 t = TREE_CHAIN (t) = gimple_asm_output_op (stmt, i);
1142 n = gimple_asm_ninputs (stmt);
1145 t = in = gimple_asm_input_op (stmt, 0);
1146 for (i = 1; i < n; i++)
1147 t = TREE_CHAIN (t) = gimple_asm_input_op (stmt, i);
1151 n = gimple_asm_nclobbers (stmt);
1154 t = cl = gimple_asm_clobber_op (stmt, 0);
1155 for (i = 1; i < n; i++)
1156 t = TREE_CHAIN (t) = gimple_asm_clobber_op (stmt, i);
1160 n = gimple_asm_nlabels (stmt);
1163 t = labels = gimple_asm_label_op (stmt, 0);
1164 for (i = 1; i < n; i++)
1165 t = TREE_CHAIN (t) = gimple_asm_label_op (stmt, i);
1168 s = gimple_asm_string (stmt);
1169 str = build_string (strlen (s), s);
1171 if (gimple_asm_input_p (stmt))
1173 expand_asm_loc (str, gimple_asm_volatile_p (stmt), locus);
1178 noutputs = gimple_asm_noutputs (stmt);
1179 /* o[I] is the place that output number I should be written. */
1180 o = (tree *) alloca (noutputs * sizeof (tree));
1182 /* Record the contents of OUTPUTS before it is modified. */
1183 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1184 o[i] = TREE_VALUE (tail);
1186 /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of
1187 OUTPUTS some trees for where the values were actually stored. */
1188 expand_asm_operands (str, outputs, in, cl, labels,
1189 gimple_asm_volatile_p (stmt), locus);
1191 /* Copy all the intermediate outputs into the specified outputs. */
1192 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1194 if (o[i] != TREE_VALUE (tail))
1196 expand_assignment (o[i], TREE_VALUE (tail), false);
1199 /* Restore the original value so that it's correct the next
1200 time we expand this function. */
1201 TREE_VALUE (tail) = o[i];
1206 /* A subroutine of expand_asm_operands. Check that all operands have
1207 the same number of alternatives. Return true if so. */
1210 check_operand_nalternatives (tree outputs, tree inputs)
1212 if (outputs || inputs)
1214 tree tmp = TREE_PURPOSE (outputs ? outputs : inputs);
1216 = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp)));
1219 if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES)
1221 error ("too many alternatives in %<asm%>");
1228 const char *constraint
1229 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp)));
1231 if (n_occurrences (',', constraint) != nalternatives)
1233 error ("operand constraints for %<asm%> differ "
1234 "in number of alternatives");
1238 if (TREE_CHAIN (tmp))
1239 tmp = TREE_CHAIN (tmp);
1241 tmp = next, next = 0;
1248 /* A subroutine of expand_asm_operands. Check that all operand names
1249 are unique. Return true if so. We rely on the fact that these names
1250 are identifiers, and so have been canonicalized by get_identifier,
1251 so all we need are pointer comparisons. */
1254 check_unique_operand_names (tree outputs, tree inputs, tree labels)
1258 for (i = outputs; i ; i = TREE_CHAIN (i))
1260 tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1264 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1265 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1269 for (i = inputs; i ; i = TREE_CHAIN (i))
1271 tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1275 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1276 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1278 for (j = outputs; j ; j = TREE_CHAIN (j))
1279 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1283 for (i = labels; i ; i = TREE_CHAIN (i))
1285 tree i_name = TREE_PURPOSE (i);
1289 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1290 if (simple_cst_equal (i_name, TREE_PURPOSE (j)))
1292 for (j = inputs; j ; j = TREE_CHAIN (j))
1293 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1300 error ("duplicate asm operand name %qs",
1301 TREE_STRING_POINTER (TREE_PURPOSE (TREE_PURPOSE (i))));
1305 /* A subroutine of expand_asm_operands. Resolve the names of the operands
1306 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
1307 STRING and in the constraints to those numbers. */
1310 resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels)
1317 check_unique_operand_names (outputs, inputs, labels);
1319 /* Substitute [<name>] in input constraint strings. There should be no
1320 named operands in output constraints. */
1321 for (t = inputs; t ; t = TREE_CHAIN (t))
1323 c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
1324 if (strchr (c, '[') != NULL)
1326 p = buffer = xstrdup (c);
1327 while ((p = strchr (p, '[')) != NULL)
1328 p = resolve_operand_name_1 (p, outputs, inputs, NULL);
1329 TREE_VALUE (TREE_PURPOSE (t))
1330 = build_string (strlen (buffer), buffer);
1335 /* Now check for any needed substitutions in the template. */
1336 c = TREE_STRING_POINTER (string);
1337 while ((c = strchr (c, '%')) != NULL)
1341 else if (ISALPHA (c[1]) && c[2] == '[')
1345 c += 1 + (c[1] == '%');
1352 /* OK, we need to make a copy so we can perform the substitutions.
1353 Assume that we will not need extra space--we get to remove '['
1354 and ']', which means we cannot have a problem until we have more
1355 than 999 operands. */
1356 buffer = xstrdup (TREE_STRING_POINTER (string));
1357 p = buffer + (c - TREE_STRING_POINTER (string));
1359 while ((p = strchr (p, '%')) != NULL)
1363 else if (ISALPHA (p[1]) && p[2] == '[')
1367 p += 1 + (p[1] == '%');
1371 p = resolve_operand_name_1 (p, outputs, inputs, labels);
1374 string = build_string (strlen (buffer), buffer);
1381 /* A subroutine of resolve_operand_names. P points to the '[' for a
1382 potential named operand of the form [<name>]. In place, replace
1383 the name and brackets with a number. Return a pointer to the
1384 balance of the string after substitution. */
1387 resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels)
1393 /* Collect the operand name. */
1394 q = strchr (++p, ']');
1397 error ("missing close brace for named operand");
1398 return strchr (p, '\0');
1402 /* Resolve the name to a number. */
1403 for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
1405 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1406 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1409 for (t = inputs; t ; t = TREE_CHAIN (t), op++)
1411 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1412 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1415 for (t = labels; t ; t = TREE_CHAIN (t), op++)
1417 tree name = TREE_PURPOSE (t);
1418 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1422 error ("undefined named operand %qs", identifier_to_locale (p));
1426 /* Replace the name with the number. Unfortunately, not all libraries
1427 get the return value of sprintf correct, so search for the end of the
1428 generated string by hand. */
1429 sprintf (--p, "%d", op);
1430 p = strchr (p, '\0');
1432 /* Verify the no extra buffer space assumption. */
1433 gcc_assert (p <= q);
1435 /* Shift the rest of the buffer down to fill the gap. */
1436 memmove (p, q + 1, strlen (q + 1) + 1);
1441 /* Generate RTL to evaluate the expression EXP. */
1444 expand_expr_stmt (tree exp)
1449 value = expand_expr (exp, const0_rtx, VOIDmode, EXPAND_NORMAL);
1450 type = TREE_TYPE (exp);
1452 /* If all we do is reference a volatile value in memory,
1453 copy it to a register to be sure it is actually touched. */
1454 if (value && MEM_P (value) && TREE_THIS_VOLATILE (exp))
1456 if (TYPE_MODE (type) == VOIDmode)
1458 else if (TYPE_MODE (type) != BLKmode)
1459 value = copy_to_reg (value);
1462 rtx lab = gen_label_rtx ();
1464 /* Compare the value with itself to reference it. */
1465 emit_cmp_and_jump_insns (value, value, EQ,
1466 expand_normal (TYPE_SIZE (type)),
1472 /* Free any temporaries used to evaluate this expression. */
1476 /* Warn if EXP contains any computations whose results are not used.
1477 Return 1 if a warning is printed; 0 otherwise. LOCUS is the
1478 (potential) location of the expression. */
1481 warn_if_unused_value (const_tree exp, location_t locus)
1484 if (TREE_USED (exp) || TREE_NO_WARNING (exp))
1487 /* Don't warn about void constructs. This includes casting to void,
1488 void function calls, and statement expressions with a final cast
1490 if (VOID_TYPE_P (TREE_TYPE (exp)))
1493 if (EXPR_HAS_LOCATION (exp))
1494 locus = EXPR_LOCATION (exp);
1496 switch (TREE_CODE (exp))
1498 case PREINCREMENT_EXPR:
1499 case POSTINCREMENT_EXPR:
1500 case PREDECREMENT_EXPR:
1501 case POSTDECREMENT_EXPR:
1506 case TRY_CATCH_EXPR:
1507 case WITH_CLEANUP_EXPR:
1513 /* For a binding, warn if no side effect within it. */
1514 exp = BIND_EXPR_BODY (exp);
1518 case NON_LVALUE_EXPR:
1519 exp = TREE_OPERAND (exp, 0);
1522 case TRUTH_ORIF_EXPR:
1523 case TRUTH_ANDIF_EXPR:
1524 /* In && or ||, warn if 2nd operand has no side effect. */
1525 exp = TREE_OPERAND (exp, 1);
1529 if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus))
1531 /* Let people do `(foo (), 0)' without a warning. */
1532 if (TREE_CONSTANT (TREE_OPERAND (exp, 1)))
1534 exp = TREE_OPERAND (exp, 1);
1538 /* If this is an expression with side effects, don't warn; this
1539 case commonly appears in macro expansions. */
1540 if (TREE_SIDE_EFFECTS (exp))
1545 /* Don't warn about automatic dereferencing of references, since
1546 the user cannot control it. */
1547 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE)
1549 exp = TREE_OPERAND (exp, 0);
1555 /* Referencing a volatile value is a side effect, so don't warn. */
1556 if ((DECL_P (exp) || REFERENCE_CLASS_P (exp))
1557 && TREE_THIS_VOLATILE (exp))
1560 /* If this is an expression which has no operands, there is no value
1561 to be unused. There are no such language-independent codes,
1562 but front ends may define such. */
1563 if (EXPRESSION_CLASS_P (exp) && TREE_OPERAND_LENGTH (exp) == 0)
1567 warning_at (locus, OPT_Wunused_value, "value computed is not used");
1573 /* Generate RTL to return from the current function, with no value.
1574 (That is, we do not do anything about returning any value.) */
1577 expand_null_return (void)
1579 /* If this function was declared to return a value, but we
1580 didn't, clobber the return registers so that they are not
1581 propagated live to the rest of the function. */
1582 clobber_return_register ();
1584 expand_null_return_1 ();
1587 /* Generate RTL to return directly from the current function.
1588 (That is, we bypass any return value.) */
1591 expand_naked_return (void)
1595 clear_pending_stack_adjust ();
1596 do_pending_stack_adjust ();
1598 end_label = naked_return_label;
1600 end_label = naked_return_label = gen_label_rtx ();
1602 emit_jump (end_label);
1605 /* Generate RTL to return from the current function, with value VAL. */
1608 expand_value_return (rtx val)
1610 /* Copy the value to the return location unless it's already there. */
1612 tree decl = DECL_RESULT (current_function_decl);
1613 rtx return_reg = DECL_RTL (decl);
1614 if (return_reg != val)
1616 tree funtype = TREE_TYPE (current_function_decl);
1617 tree type = TREE_TYPE (decl);
1618 int unsignedp = TYPE_UNSIGNED (type);
1619 enum machine_mode old_mode = DECL_MODE (decl);
1620 enum machine_mode mode;
1621 if (DECL_BY_REFERENCE (decl))
1622 mode = promote_function_mode (type, old_mode, &unsignedp, funtype, 2);
1624 mode = promote_function_mode (type, old_mode, &unsignedp, funtype, 1);
1626 if (mode != old_mode)
1627 val = convert_modes (mode, old_mode, val, unsignedp);
1629 if (GET_CODE (return_reg) == PARALLEL)
1630 emit_group_load (return_reg, val, type, int_size_in_bytes (type));
1632 emit_move_insn (return_reg, val);
1635 expand_null_return_1 ();
1638 /* Output a return with no value. */
1641 expand_null_return_1 (void)
1643 clear_pending_stack_adjust ();
1644 do_pending_stack_adjust ();
1645 emit_jump (return_label);
1648 /* Generate RTL to evaluate the expression RETVAL and return it
1649 from the current function. */
1652 expand_return (tree retval)
1658 /* If function wants no value, give it none. */
1659 if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE)
1661 expand_normal (retval);
1662 expand_null_return ();
1666 if (retval == error_mark_node)
1668 /* Treat this like a return of no value from a function that
1670 expand_null_return ();
1673 else if ((TREE_CODE (retval) == MODIFY_EXPR
1674 || TREE_CODE (retval) == INIT_EXPR)
1675 && TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL)
1676 retval_rhs = TREE_OPERAND (retval, 1);
1678 retval_rhs = retval;
1680 result_rtl = DECL_RTL (DECL_RESULT (current_function_decl));
1682 /* If we are returning the RESULT_DECL, then the value has already
1683 been stored into it, so we don't have to do anything special. */
1684 if (TREE_CODE (retval_rhs) == RESULT_DECL)
1685 expand_value_return (result_rtl);
1687 /* If the result is an aggregate that is being returned in one (or more)
1688 registers, load the registers here. The compiler currently can't handle
1689 copying a BLKmode value into registers. We could put this code in a
1690 more general area (for use by everyone instead of just function
1691 call/return), but until this feature is generally usable it is kept here
1692 (and in expand_call). */
1694 else if (retval_rhs != 0
1695 && TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode
1696 && REG_P (result_rtl))
1699 unsigned HOST_WIDE_INT bitpos, xbitpos;
1700 unsigned HOST_WIDE_INT padding_correction = 0;
1701 unsigned HOST_WIDE_INT bytes
1702 = int_size_in_bytes (TREE_TYPE (retval_rhs));
1703 int n_regs = (bytes + UNITS_PER_WORD - 1) / UNITS_PER_WORD;
1704 unsigned int bitsize
1705 = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)), BITS_PER_WORD);
1706 rtx *result_pseudos = XALLOCAVEC (rtx, n_regs);
1707 rtx result_reg, src = NULL_RTX, dst = NULL_RTX;
1708 rtx result_val = expand_normal (retval_rhs);
1709 enum machine_mode tmpmode, result_reg_mode;
1713 expand_null_return ();
1717 /* If the structure doesn't take up a whole number of words, see
1718 whether the register value should be padded on the left or on
1719 the right. Set PADDING_CORRECTION to the number of padding
1720 bits needed on the left side.
1722 In most ABIs, the structure will be returned at the least end of
1723 the register, which translates to right padding on little-endian
1724 targets and left padding on big-endian targets. The opposite
1725 holds if the structure is returned at the most significant
1726 end of the register. */
1727 if (bytes % UNITS_PER_WORD != 0
1728 && (targetm.calls.return_in_msb (TREE_TYPE (retval_rhs))
1730 : BYTES_BIG_ENDIAN))
1731 padding_correction = (BITS_PER_WORD - ((bytes % UNITS_PER_WORD)
1734 /* Copy the structure BITSIZE bits at a time. */
1735 for (bitpos = 0, xbitpos = padding_correction;
1736 bitpos < bytes * BITS_PER_UNIT;
1737 bitpos += bitsize, xbitpos += bitsize)
1739 /* We need a new destination pseudo each time xbitpos is
1740 on a word boundary and when xbitpos == padding_correction
1741 (the first time through). */
1742 if (xbitpos % BITS_PER_WORD == 0
1743 || xbitpos == padding_correction)
1745 /* Generate an appropriate register. */
1746 dst = gen_reg_rtx (word_mode);
1747 result_pseudos[xbitpos / BITS_PER_WORD] = dst;
1749 /* Clear the destination before we move anything into it. */
1750 emit_move_insn (dst, CONST0_RTX (GET_MODE (dst)));
1753 /* We need a new source operand each time bitpos is on a word
1755 if (bitpos % BITS_PER_WORD == 0)
1756 src = operand_subword_force (result_val,
1757 bitpos / BITS_PER_WORD,
1760 /* Use bitpos for the source extraction (left justified) and
1761 xbitpos for the destination store (right justified). */
1762 store_bit_field (dst, bitsize, xbitpos % BITS_PER_WORD, word_mode,
1763 extract_bit_field (src, bitsize,
1764 bitpos % BITS_PER_WORD, 1, false,
1765 NULL_RTX, word_mode, word_mode));
1768 tmpmode = GET_MODE (result_rtl);
1769 if (tmpmode == BLKmode)
1771 /* Find the smallest integer mode large enough to hold the
1772 entire structure and use that mode instead of BLKmode
1773 on the USE insn for the return register. */
1774 for (tmpmode = GET_CLASS_NARROWEST_MODE (MODE_INT);
1775 tmpmode != VOIDmode;
1776 tmpmode = GET_MODE_WIDER_MODE (tmpmode))
1777 /* Have we found a large enough mode? */
1778 if (GET_MODE_SIZE (tmpmode) >= bytes)
1781 /* A suitable mode should have been found. */
1782 gcc_assert (tmpmode != VOIDmode);
1784 PUT_MODE (result_rtl, tmpmode);
1787 if (GET_MODE_SIZE (tmpmode) < GET_MODE_SIZE (word_mode))
1788 result_reg_mode = word_mode;
1790 result_reg_mode = tmpmode;
1791 result_reg = gen_reg_rtx (result_reg_mode);
1793 for (i = 0; i < n_regs; i++)
1794 emit_move_insn (operand_subword (result_reg, i, 0, result_reg_mode),
1797 if (tmpmode != result_reg_mode)
1798 result_reg = gen_lowpart (tmpmode, result_reg);
1800 expand_value_return (result_reg);
1802 else if (retval_rhs != 0
1803 && !VOID_TYPE_P (TREE_TYPE (retval_rhs))
1804 && (REG_P (result_rtl)
1805 || (GET_CODE (result_rtl) == PARALLEL)))
1807 /* Calculate the return value into a temporary (usually a pseudo
1809 tree ot = TREE_TYPE (DECL_RESULT (current_function_decl));
1810 tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST);
1812 val = assign_temp (nt, 0, 0, 1);
1813 val = expand_expr (retval_rhs, val, GET_MODE (val), EXPAND_NORMAL);
1814 val = force_not_mem (val);
1815 /* Return the calculated value. */
1816 expand_value_return (val);
1820 /* No hard reg used; calculate value into hard return reg. */
1821 expand_expr (retval, const0_rtx, VOIDmode, EXPAND_NORMAL);
1822 expand_value_return (result_rtl);
1826 /* Emit code to restore vital registers at the beginning of a nonlocal goto
1829 expand_nl_goto_receiver (void)
1833 /* Clobber the FP when we get here, so we have to make sure it's
1834 marked as used by this function. */
1835 emit_use (hard_frame_pointer_rtx);
1837 /* Mark the static chain as clobbered here so life information
1838 doesn't get messed up for it. */
1839 chain = targetm.calls.static_chain (current_function_decl, true);
1840 if (chain && REG_P (chain))
1841 emit_clobber (chain);
1843 #ifdef HAVE_nonlocal_goto
1844 if (! HAVE_nonlocal_goto)
1846 /* First adjust our frame pointer to its actual value. It was
1847 previously set to the start of the virtual area corresponding to
1848 the stacked variables when we branched here and now needs to be
1849 adjusted to the actual hardware fp value.
1851 Assignments are to virtual registers are converted by
1852 instantiate_virtual_regs into the corresponding assignment
1853 to the underlying register (fp in this case) that makes
1854 the original assignment true.
1855 So the following insn will actually be
1856 decrementing fp by STARTING_FRAME_OFFSET. */
1857 emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx);
1859 #if !HARD_FRAME_POINTER_IS_ARG_POINTER
1860 if (fixed_regs[ARG_POINTER_REGNUM])
1862 #ifdef ELIMINABLE_REGS
1863 /* If the argument pointer can be eliminated in favor of the
1864 frame pointer, we don't need to restore it. We assume here
1865 that if such an elimination is present, it can always be used.
1866 This is the case on all known machines; if we don't make this
1867 assumption, we do unnecessary saving on many machines. */
1868 static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS;
1871 for (i = 0; i < ARRAY_SIZE (elim_regs); i++)
1872 if (elim_regs[i].from == ARG_POINTER_REGNUM
1873 && elim_regs[i].to == HARD_FRAME_POINTER_REGNUM)
1876 if (i == ARRAY_SIZE (elim_regs))
1879 /* Now restore our arg pointer from the address at which it
1880 was saved in our stack frame. */
1881 emit_move_insn (crtl->args.internal_arg_pointer,
1882 copy_to_reg (get_arg_pointer_save_area ()));
1887 #ifdef HAVE_nonlocal_goto_receiver
1888 if (HAVE_nonlocal_goto_receiver)
1889 emit_insn (gen_nonlocal_goto_receiver ());
1892 /* We must not allow the code we just generated to be reordered by
1893 scheduling. Specifically, the update of the frame pointer must
1894 happen immediately, not later. */
1895 emit_insn (gen_blockage ());
1898 /* Generate RTL for the automatic variable declaration DECL.
1899 (Other kinds of declarations are simply ignored if seen here.) */
1902 expand_decl (tree decl)
1906 type = TREE_TYPE (decl);
1908 /* For a CONST_DECL, set mode, alignment, and sizes from those of the
1909 type in case this node is used in a reference. */
1910 if (TREE_CODE (decl) == CONST_DECL)
1912 DECL_MODE (decl) = TYPE_MODE (type);
1913 DECL_ALIGN (decl) = TYPE_ALIGN (type);
1914 DECL_SIZE (decl) = TYPE_SIZE (type);
1915 DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type);
1919 /* Otherwise, only automatic variables need any expansion done. Static and
1920 external variables, and external functions, will be handled by
1921 `assemble_variable' (called from finish_decl). TYPE_DECL requires
1922 nothing. PARM_DECLs are handled in `assign_parms'. */
1923 if (TREE_CODE (decl) != VAR_DECL)
1926 if (TREE_STATIC (decl) || DECL_EXTERNAL (decl))
1929 /* Create the RTL representation for the variable. */
1931 if (type == error_mark_node)
1932 SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx));
1934 else if (DECL_SIZE (decl) == 0)
1936 /* Variable with incomplete type. */
1938 if (DECL_INITIAL (decl) == 0)
1939 /* Error message was already done; now avoid a crash. */
1940 x = gen_rtx_MEM (BLKmode, const0_rtx);
1942 /* An initializer is going to decide the size of this array.
1943 Until we know the size, represent its address with a reg. */
1944 x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode));
1946 set_mem_attributes (x, decl, 1);
1947 SET_DECL_RTL (decl, x);
1949 else if (use_register_for_decl (decl))
1951 /* Automatic variable that can go in a register. */
1952 enum machine_mode reg_mode = promote_decl_mode (decl, NULL);
1954 SET_DECL_RTL (decl, gen_reg_rtx (reg_mode));
1956 /* Note if the object is a user variable. */
1957 if (!DECL_ARTIFICIAL (decl))
1958 mark_user_reg (DECL_RTL (decl));
1960 if (POINTER_TYPE_P (type))
1961 mark_reg_pointer (DECL_RTL (decl),
1962 TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl))));
1971 /* Variable-sized decls are dealt with in the gimplifier. */
1972 gcc_assert (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST);
1974 /* If we previously made RTL for this decl, it must be an array
1975 whose size was determined by the initializer.
1976 The old address was a register; set that register now
1977 to the proper address. */
1978 if (DECL_RTL_SET_P (decl))
1980 gcc_assert (MEM_P (DECL_RTL (decl)));
1981 gcc_assert (REG_P (XEXP (DECL_RTL (decl), 0)));
1982 oldaddr = XEXP (DECL_RTL (decl), 0);
1985 /* Set alignment we actually gave this decl. */
1986 DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT
1987 : GET_MODE_BITSIZE (DECL_MODE (decl)));
1988 DECL_USER_ALIGN (decl) = 0;
1990 x = assign_temp (decl, 1, 1, 1);
1991 set_mem_attributes (x, decl, 1);
1992 SET_DECL_RTL (decl, x);
1996 addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr);
1997 if (addr != oldaddr)
1998 emit_move_insn (oldaddr, addr);
2003 /* Emit code to save the current value of stack. */
2005 expand_stack_save (void)
2009 do_pending_stack_adjust ();
2010 emit_stack_save (SAVE_BLOCK, &ret, NULL_RTX);
2014 /* Emit code to restore the current value of stack. */
2016 expand_stack_restore (tree var)
2018 rtx sa = expand_normal (var);
2020 sa = convert_memory_address (Pmode, sa);
2021 emit_stack_restore (SAVE_BLOCK, sa, NULL_RTX);
2024 /* Do the insertion of a case label into case_list. The labels are
2025 fed to us in descending order from the sorted vector of case labels used
2026 in the tree part of the middle end. So the list we construct is
2027 sorted in ascending order. The bounds on the case range, LOW and HIGH,
2028 are converted to case's index type TYPE. */
2030 static struct case_node *
2031 add_case_node (struct case_node *head, tree type, tree low, tree high,
2032 tree label, alloc_pool case_node_pool)
2034 tree min_value, max_value;
2035 struct case_node *r;
2037 gcc_assert (TREE_CODE (low) == INTEGER_CST);
2038 gcc_assert (!high || TREE_CODE (high) == INTEGER_CST);
2040 min_value = TYPE_MIN_VALUE (type);
2041 max_value = TYPE_MAX_VALUE (type);
2043 /* If there's no HIGH value, then this is not a case range; it's
2044 just a simple case label. But that's just a degenerate case
2046 If the bounds are equal, turn this into the one-value case. */
2047 if (!high || tree_int_cst_equal (low, high))
2049 /* If the simple case value is unreachable, ignore it. */
2050 if ((TREE_CODE (min_value) == INTEGER_CST
2051 && tree_int_cst_compare (low, min_value) < 0)
2052 || (TREE_CODE (max_value) == INTEGER_CST
2053 && tree_int_cst_compare (low, max_value) > 0))
2055 low = fold_convert (type, low);
2060 /* If the entire case range is unreachable, ignore it. */
2061 if ((TREE_CODE (min_value) == INTEGER_CST
2062 && tree_int_cst_compare (high, min_value) < 0)
2063 || (TREE_CODE (max_value) == INTEGER_CST
2064 && tree_int_cst_compare (low, max_value) > 0))
2067 /* If the lower bound is less than the index type's minimum
2068 value, truncate the range bounds. */
2069 if (TREE_CODE (min_value) == INTEGER_CST
2070 && tree_int_cst_compare (low, min_value) < 0)
2072 low = fold_convert (type, low);
2074 /* If the upper bound is greater than the index type's maximum
2075 value, truncate the range bounds. */
2076 if (TREE_CODE (max_value) == INTEGER_CST
2077 && tree_int_cst_compare (high, max_value) > 0)
2079 high = fold_convert (type, high);
2083 /* Add this label to the chain. Make sure to drop overflow flags. */
2084 r = (struct case_node *) pool_alloc (case_node_pool);
2085 r->low = build_int_cst_wide (TREE_TYPE (low), TREE_INT_CST_LOW (low),
2086 TREE_INT_CST_HIGH (low));
2087 r->high = build_int_cst_wide (TREE_TYPE (high), TREE_INT_CST_LOW (high),
2088 TREE_INT_CST_HIGH (high));
2089 r->code_label = label;
2090 r->parent = r->left = NULL;
2095 /* Maximum number of case bit tests. */
2096 #define MAX_CASE_BIT_TESTS 3
2098 /* By default, enable case bit tests on targets with ashlsi3. */
2099 #ifndef CASE_USE_BIT_TESTS
2100 #define CASE_USE_BIT_TESTS (optab_handler (ashl_optab, word_mode) \
2101 != CODE_FOR_nothing)
2105 /* A case_bit_test represents a set of case nodes that may be
2106 selected from using a bit-wise comparison. HI and LO hold
2107 the integer to be tested against, LABEL contains the label
2108 to jump to upon success and BITS counts the number of case
2109 nodes handled by this test, typically the number of bits
2112 struct case_bit_test
2120 /* Determine whether "1 << x" is relatively cheap in word_mode. */
2123 bool lshift_cheap_p (void)
2125 static bool init[2] = {false, false};
2126 static bool cheap[2] = {true, true};
2128 bool speed_p = optimize_insn_for_speed_p ();
2132 rtx reg = gen_rtx_REG (word_mode, 10000);
2133 int cost = rtx_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg), SET,
2135 cheap[speed_p] = cost < COSTS_N_INSNS (3);
2136 init[speed_p] = true;
2139 return cheap[speed_p];
2142 /* Comparison function for qsort to order bit tests by decreasing
2143 number of case nodes, i.e. the node with the most cases gets
2147 case_bit_test_cmp (const void *p1, const void *p2)
2149 const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
2150 const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
2152 if (d2->bits != d1->bits)
2153 return d2->bits - d1->bits;
2155 /* Stabilize the sort. */
2156 return CODE_LABEL_NUMBER (d2->label) - CODE_LABEL_NUMBER (d1->label);
2159 /* Expand a switch statement by a short sequence of bit-wise
2160 comparisons. "switch(x)" is effectively converted into
2161 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
2164 INDEX_EXPR is the value being switched on, which is of
2165 type INDEX_TYPE. MINVAL is the lowest case value of in
2166 the case nodes, of INDEX_TYPE type, and RANGE is highest
2167 value minus MINVAL, also of type INDEX_TYPE. NODES is
2168 the set of case nodes, and DEFAULT_LABEL is the label to
2169 branch to should none of the cases match.
2171 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
2175 emit_case_bit_tests (tree index_type, tree index_expr, tree minval,
2176 tree range, case_node_ptr nodes, rtx default_label)
2178 struct case_bit_test test[MAX_CASE_BIT_TESTS];
2179 enum machine_mode mode;
2180 rtx expr, index, label;
2181 unsigned int i,j,lo,hi;
2182 struct case_node *n;
2186 for (n = nodes; n; n = n->right)
2188 label = label_rtx (n->code_label);
2189 for (i = 0; i < count; i++)
2190 if (label == test[i].label)
2195 gcc_assert (count < MAX_CASE_BIT_TESTS);
2198 test[i].label = label;
2205 lo = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2206 n->low, minval), 1);
2207 hi = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2208 n->high, minval), 1);
2209 for (j = lo; j <= hi; j++)
2210 if (j >= HOST_BITS_PER_WIDE_INT)
2211 test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT);
2213 test[i].lo |= (HOST_WIDE_INT) 1 << j;
2216 qsort (test, count, sizeof(*test), case_bit_test_cmp);
2218 index_expr = fold_build2 (MINUS_EXPR, index_type,
2219 fold_convert (index_type, index_expr),
2220 fold_convert (index_type, minval));
2221 index = expand_normal (index_expr);
2222 do_pending_stack_adjust ();
2224 mode = TYPE_MODE (index_type);
2225 expr = expand_normal (range);
2227 emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
2230 index = convert_to_mode (word_mode, index, 0);
2231 index = expand_binop (word_mode, ashl_optab, const1_rtx,
2232 index, NULL_RTX, 1, OPTAB_WIDEN);
2234 for (i = 0; i < count; i++)
2236 expr = immed_double_const (test[i].lo, test[i].hi, word_mode);
2237 expr = expand_binop (word_mode, and_optab, index, expr,
2238 NULL_RTX, 1, OPTAB_WIDEN);
2239 emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX,
2240 word_mode, 1, test[i].label);
2244 emit_jump (default_label);
2248 #define HAVE_casesi 0
2251 #ifndef HAVE_tablejump
2252 #define HAVE_tablejump 0
2255 /* Return true if a switch should be expanded as a bit test.
2256 INDEX_EXPR is the index expression, RANGE is the difference between
2257 highest and lowest case, UNIQ is number of unique case node targets
2258 not counting the default case and COUNT is the number of comparisons
2259 needed, not counting the default case. */
2261 expand_switch_using_bit_tests_p (tree index_expr, tree range,
2262 unsigned int uniq, unsigned int count)
2264 return (CASE_USE_BIT_TESTS
2265 && ! TREE_CONSTANT (index_expr)
2266 && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
2267 && compare_tree_int (range, 0) > 0
2268 && lshift_cheap_p ()
2269 && ((uniq == 1 && count >= 3)
2270 || (uniq == 2 && count >= 5)
2271 || (uniq == 3 && count >= 6)));
2274 /* Terminate a case (Pascal/Ada) or switch (C) statement
2275 in which ORIG_INDEX is the expression to be tested.
2276 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
2277 type as given in the source before any compiler conversions.
2278 Generate the code to test it and jump to the right place. */
2281 expand_case (gimple stmt)
2283 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
2284 rtx default_label = 0;
2285 struct case_node *n;
2286 unsigned int count, uniq;
2292 rtx before_case, end, lab;
2294 tree index_expr = gimple_switch_index (stmt);
2295 tree index_type = TREE_TYPE (index_expr);
2296 int unsignedp = TYPE_UNSIGNED (index_type);
2298 /* The insn after which the case dispatch should finally
2299 be emitted. Zero for a dummy. */
2302 /* A list of case labels; it is first built as a list and it may then
2303 be rearranged into a nearly balanced binary tree. */
2304 struct case_node *case_list = 0;
2306 /* Label to jump to if no case matches. */
2307 tree default_label_decl = NULL_TREE;
2309 alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
2310 sizeof (struct case_node),
2313 do_pending_stack_adjust ();
2315 /* An ERROR_MARK occurs for various reasons including invalid data type. */
2316 if (index_type != error_mark_node)
2319 bitmap label_bitmap;
2322 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
2323 expressions being INTEGER_CST. */
2324 gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
2326 /* The default case, if ever taken, is the first element. */
2327 elt = gimple_switch_label (stmt, 0);
2328 if (!CASE_LOW (elt) && !CASE_HIGH (elt))
2330 default_label_decl = CASE_LABEL (elt);
2334 for (i = gimple_switch_num_labels (stmt) - 1; i >= stopi; --i)
2337 elt = gimple_switch_label (stmt, i);
2339 low = CASE_LOW (elt);
2341 high = CASE_HIGH (elt);
2343 /* Discard empty ranges. */
2344 if (high && tree_int_cst_lt (high, low))
2347 case_list = add_case_node (case_list, index_type, low, high,
2348 CASE_LABEL (elt), case_node_pool);
2352 before_case = start = get_last_insn ();
2353 if (default_label_decl)
2354 default_label = label_rtx (default_label_decl);
2356 /* Get upper and lower bounds of case values. */
2360 label_bitmap = BITMAP_ALLOC (NULL);
2361 for (n = case_list; n; n = n->right)
2363 /* Count the elements and track the largest and smallest
2364 of them (treating them as signed even if they are not). */
2372 if (tree_int_cst_lt (n->low, minval))
2374 if (tree_int_cst_lt (maxval, n->high))
2377 /* A range counts double, since it requires two compares. */
2378 if (! tree_int_cst_equal (n->low, n->high))
2381 /* If we have not seen this label yet, then increase the
2382 number of unique case node targets seen. */
2383 lab = label_rtx (n->code_label);
2384 if (bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab)))
2388 BITMAP_FREE (label_bitmap);
2390 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
2391 destination, such as one with a default case only. However,
2392 it doesn't remove cases that are out of range for the switch
2393 type, so we may still get a zero here. */
2397 emit_jump (default_label);
2398 free_alloc_pool (case_node_pool);
2402 /* Compute span of values. */
2403 range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
2405 /* Try implementing this switch statement by a short sequence of
2406 bit-wise comparisons. However, we let the binary-tree case
2407 below handle constant index expressions. */
2408 if (expand_switch_using_bit_tests_p (index_expr, range, uniq, count))
2410 /* Optimize the case where all the case values fit in a
2411 word without having to subtract MINVAL. In this case,
2412 we can optimize away the subtraction. */
2413 if (compare_tree_int (minval, 0) > 0
2414 && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
2416 minval = build_int_cst (index_type, 0);
2419 emit_case_bit_tests (index_type, index_expr, minval, range,
2420 case_list, default_label);
2423 /* If range of values is much bigger than number of values,
2424 make a sequence of conditional branches instead of a dispatch.
2425 If the switch-index is a constant, do it this way
2426 because we can optimize it. */
2428 else if (count < targetm.case_values_threshold ()
2429 || compare_tree_int (range,
2430 (optimize_insn_for_size_p () ? 3 : 10) * count) > 0
2431 /* RANGE may be signed, and really large ranges will show up
2432 as negative numbers. */
2433 || compare_tree_int (range, 0) < 0
2434 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
2437 || !flag_jump_tables
2438 || TREE_CONSTANT (index_expr)
2439 /* If neither casesi or tablejump is available, we can
2440 only go this way. */
2441 || (!HAVE_casesi && !HAVE_tablejump))
2443 index = expand_normal (index_expr);
2445 /* If the index is a short or char that we do not have
2446 an insn to handle comparisons directly, convert it to
2447 a full integer now, rather than letting each comparison
2448 generate the conversion. */
2450 if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
2451 && ! have_insn_for (COMPARE, GET_MODE (index)))
2453 enum machine_mode wider_mode;
2454 for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
2455 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2456 if (have_insn_for (COMPARE, wider_mode))
2458 index = convert_to_mode (wider_mode, index, unsignedp);
2463 do_pending_stack_adjust ();
2466 index = copy_to_reg (index);
2468 /* We generate a binary decision tree to select the
2469 appropriate target code. This is done as follows:
2471 The list of cases is rearranged into a binary tree,
2472 nearly optimal assuming equal probability for each case.
2474 The tree is transformed into RTL, eliminating
2475 redundant test conditions at the same time.
2477 If program flow could reach the end of the
2478 decision tree an unconditional jump to the
2479 default code is emitted. */
2481 use_cost_table = estimate_case_costs (case_list);
2482 balance_case_nodes (&case_list, NULL);
2483 emit_case_nodes (index, case_list, default_label, index_type);
2485 emit_jump (default_label);
2489 rtx fallback_label = label_rtx (case_list->code_label);
2490 table_label = gen_label_rtx ();
2491 if (! try_casesi (index_type, index_expr, minval, range,
2492 table_label, default_label, fallback_label))
2496 /* Index jumptables from zero for suitable values of
2497 minval to avoid a subtraction. */
2498 if (optimize_insn_for_speed_p ()
2499 && compare_tree_int (minval, 0) > 0
2500 && compare_tree_int (minval, 3) < 0)
2502 minval = build_int_cst (index_type, 0);
2506 ok = try_tablejump (index_type, index_expr, minval, range,
2507 table_label, default_label);
2511 /* Get table of labels to jump to, in order of case index. */
2513 ncases = tree_low_cst (range, 0) + 1;
2514 labelvec = XALLOCAVEC (rtx, ncases);
2515 memset (labelvec, 0, ncases * sizeof (rtx));
2517 for (n = case_list; n; n = n->right)
2519 /* Compute the low and high bounds relative to the minimum
2520 value since that should fit in a HOST_WIDE_INT while the
2521 actual values may not. */
2523 = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2524 n->low, minval), 1);
2525 HOST_WIDE_INT i_high
2526 = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2527 n->high, minval), 1);
2530 for (i = i_low; i <= i_high; i ++)
2532 = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
2535 /* Fill in the gaps with the default. We may have gaps at
2536 the beginning if we tried to avoid the minval subtraction,
2537 so substitute some label even if the default label was
2538 deemed unreachable. */
2540 default_label = fallback_label;
2541 for (i = 0; i < ncases; i++)
2542 if (labelvec[i] == 0)
2543 labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
2545 /* Output the table. */
2546 emit_label (table_label);
2548 if (CASE_VECTOR_PC_RELATIVE || flag_pic)
2549 emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
2550 gen_rtx_LABEL_REF (Pmode, table_label),
2551 gen_rtvec_v (ncases, labelvec),
2552 const0_rtx, const0_rtx));
2554 emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
2555 gen_rtvec_v (ncases, labelvec)));
2557 /* Record no drop-through after the table. */
2561 before_case = NEXT_INSN (before_case);
2562 end = get_last_insn ();
2563 reorder_insns (before_case, end, start);
2567 free_alloc_pool (case_node_pool);
2570 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */
2573 do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label,
2576 do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
2577 NULL_RTX, NULL_RTX, label, -1);
2580 /* Not all case values are encountered equally. This function
2581 uses a heuristic to weight case labels, in cases where that
2582 looks like a reasonable thing to do.
2584 Right now, all we try to guess is text, and we establish the
2587 chars above space: 16
2596 If we find any cases in the switch that are not either -1 or in the range
2597 of valid ASCII characters, or are control characters other than those
2598 commonly used with "\", don't treat this switch scanning text.
2600 Return 1 if these nodes are suitable for cost estimation, otherwise
2604 estimate_case_costs (case_node_ptr node)
2606 tree min_ascii = integer_minus_one_node;
2607 tree max_ascii = build_int_cst (TREE_TYPE (node->high), 127);
2611 /* If we haven't already made the cost table, make it now. Note that the
2612 lower bound of the table is -1, not zero. */
2614 if (! cost_table_initialized)
2616 cost_table_initialized = 1;
2618 for (i = 0; i < 128; i++)
2621 COST_TABLE (i) = 16;
2622 else if (ISPUNCT (i))
2624 else if (ISCNTRL (i))
2625 COST_TABLE (i) = -1;
2628 COST_TABLE (' ') = 8;
2629 COST_TABLE ('\t') = 4;
2630 COST_TABLE ('\0') = 4;
2631 COST_TABLE ('\n') = 2;
2632 COST_TABLE ('\f') = 1;
2633 COST_TABLE ('\v') = 1;
2634 COST_TABLE ('\b') = 1;
2637 /* See if all the case expressions look like text. It is text if the
2638 constant is >= -1 and the highest constant is <= 127. Do all comparisons
2639 as signed arithmetic since we don't want to ever access cost_table with a
2640 value less than -1. Also check that none of the constants in a range
2641 are strange control characters. */
2643 for (n = node; n; n = n->right)
2645 if (tree_int_cst_lt (n->low, min_ascii)
2646 || tree_int_cst_lt (max_ascii, n->high))
2649 for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low);
2650 i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++)
2651 if (COST_TABLE (i) < 0)
2655 /* All interesting values are within the range of interesting
2656 ASCII characters. */
2660 /* Take an ordered list of case nodes
2661 and transform them into a near optimal binary tree,
2662 on the assumption that any target code selection value is as
2663 likely as any other.
2665 The transformation is performed by splitting the ordered
2666 list into two equal sections plus a pivot. The parts are
2667 then attached to the pivot as left and right branches. Each
2668 branch is then transformed recursively. */
2671 balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
2684 /* Count the number of entries on branch. Also count the ranges. */
2688 if (!tree_int_cst_equal (np->low, np->high))
2692 cost += COST_TABLE (TREE_INT_CST_LOW (np->high));
2696 cost += COST_TABLE (TREE_INT_CST_LOW (np->low));
2704 /* Split this list if it is long enough for that to help. */
2709 /* Find the place in the list that bisects the list's total cost,
2710 Here I gets half the total cost. */
2715 /* Skip nodes while their cost does not reach that amount. */
2716 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
2717 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high));
2718 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low));
2721 npp = &(*npp)->right;
2726 /* Leave this branch lopsided, but optimize left-hand
2727 side and fill in `parent' fields for right-hand side. */
2729 np->parent = parent;
2730 balance_case_nodes (&np->left, np);
2731 for (; np->right; np = np->right)
2732 np->right->parent = np;
2736 /* If there are just three nodes, split at the middle one. */
2738 npp = &(*npp)->right;
2741 /* Find the place in the list that bisects the list's total cost,
2742 where ranges count as 2.
2743 Here I gets half the total cost. */
2744 i = (i + ranges + 1) / 2;
2747 /* Skip nodes while their cost does not reach that amount. */
2748 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
2753 npp = &(*npp)->right;
2758 np->parent = parent;
2761 /* Optimize each of the two split parts. */
2762 balance_case_nodes (&np->left, np);
2763 balance_case_nodes (&np->right, np);
2767 /* Else leave this branch as one level,
2768 but fill in `parent' fields. */
2770 np->parent = parent;
2771 for (; np->right; np = np->right)
2772 np->right->parent = np;
2777 /* Search the parent sections of the case node tree
2778 to see if a test for the lower bound of NODE would be redundant.
2779 INDEX_TYPE is the type of the index expression.
2781 The instructions to generate the case decision tree are
2782 output in the same order as nodes are processed so it is
2783 known that if a parent node checks the range of the current
2784 node minus one that the current node is bounded at its lower
2785 span. Thus the test would be redundant. */
2788 node_has_low_bound (case_node_ptr node, tree index_type)
2791 case_node_ptr pnode;
2793 /* If the lower bound of this node is the lowest value in the index type,
2794 we need not test it. */
2796 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
2799 /* If this node has a left branch, the value at the left must be less
2800 than that at this node, so it cannot be bounded at the bottom and
2801 we need not bother testing any further. */
2806 low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low),
2808 build_int_cst (TREE_TYPE (node->low), 1));
2810 /* If the subtraction above overflowed, we can't verify anything.
2811 Otherwise, look for a parent that tests our value - 1. */
2813 if (! tree_int_cst_lt (low_minus_one, node->low))
2816 for (pnode = node->parent; pnode; pnode = pnode->parent)
2817 if (tree_int_cst_equal (low_minus_one, pnode->high))
2823 /* Search the parent sections of the case node tree
2824 to see if a test for the upper bound of NODE would be redundant.
2825 INDEX_TYPE is the type of the index expression.
2827 The instructions to generate the case decision tree are
2828 output in the same order as nodes are processed so it is
2829 known that if a parent node checks the range of the current
2830 node plus one that the current node is bounded at its upper
2831 span. Thus the test would be redundant. */
2834 node_has_high_bound (case_node_ptr node, tree index_type)
2837 case_node_ptr pnode;
2839 /* If there is no upper bound, obviously no test is needed. */
2841 if (TYPE_MAX_VALUE (index_type) == NULL)
2844 /* If the upper bound of this node is the highest value in the type
2845 of the index expression, we need not test against it. */
2847 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
2850 /* If this node has a right branch, the value at the right must be greater
2851 than that at this node, so it cannot be bounded at the top and
2852 we need not bother testing any further. */
2857 high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high),
2859 build_int_cst (TREE_TYPE (node->high), 1));
2861 /* If the addition above overflowed, we can't verify anything.
2862 Otherwise, look for a parent that tests our value + 1. */
2864 if (! tree_int_cst_lt (node->high, high_plus_one))
2867 for (pnode = node->parent; pnode; pnode = pnode->parent)
2868 if (tree_int_cst_equal (high_plus_one, pnode->low))
2874 /* Search the parent sections of the
2875 case node tree to see if both tests for the upper and lower
2876 bounds of NODE would be redundant. */
2879 node_is_bounded (case_node_ptr node, tree index_type)
2881 return (node_has_low_bound (node, index_type)
2882 && node_has_high_bound (node, index_type));
2885 /* Emit step-by-step code to select a case for the value of INDEX.
2886 The thus generated decision tree follows the form of the
2887 case-node binary tree NODE, whose nodes represent test conditions.
2888 INDEX_TYPE is the type of the index of the switch.
2890 Care is taken to prune redundant tests from the decision tree
2891 by detecting any boundary conditions already checked by
2892 emitted rtx. (See node_has_high_bound, node_has_low_bound
2893 and node_is_bounded, above.)
2895 Where the test conditions can be shown to be redundant we emit
2896 an unconditional jump to the target code. As a further
2897 optimization, the subordinates of a tree node are examined to
2898 check for bounded nodes. In this case conditional and/or
2899 unconditional jumps as a result of the boundary check for the
2900 current node are arranged to target the subordinates associated
2901 code for out of bound conditions on the current node.
2903 We can assume that when control reaches the code generated here,
2904 the index value has already been compared with the parents
2905 of this node, and determined to be on the same side of each parent
2906 as this node is. Thus, if this node tests for the value 51,
2907 and a parent tested for 52, we don't need to consider
2908 the possibility of a value greater than 51. If another parent
2909 tests for the value 50, then this node need not test anything. */
2912 emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
2915 /* If INDEX has an unsigned type, we must make unsigned branches. */
2916 int unsignedp = TYPE_UNSIGNED (index_type);
2917 enum machine_mode mode = GET_MODE (index);
2918 enum machine_mode imode = TYPE_MODE (index_type);
2920 /* Handle indices detected as constant during RTL expansion. */
2921 if (mode == VOIDmode)
2924 /* See if our parents have already tested everything for us.
2925 If they have, emit an unconditional jump for this node. */
2926 if (node_is_bounded (node, index_type))
2927 emit_jump (label_rtx (node->code_label));
2929 else if (tree_int_cst_equal (node->low, node->high))
2931 /* Node is single valued. First see if the index expression matches
2932 this node and then check our children, if any. */
2934 do_jump_if_equal (mode, index,
2935 convert_modes (mode, imode,
2936 expand_normal (node->low),
2938 label_rtx (node->code_label), unsignedp);
2940 if (node->right != 0 && node->left != 0)
2942 /* This node has children on both sides.
2943 Dispatch to one side or the other
2944 by comparing the index value with this node's value.
2945 If one subtree is bounded, check that one first,
2946 so we can avoid real branches in the tree. */
2948 if (node_is_bounded (node->right, index_type))
2950 emit_cmp_and_jump_insns (index,
2953 expand_normal (node->high),
2955 GT, NULL_RTX, mode, unsignedp,
2956 label_rtx (node->right->code_label));
2957 emit_case_nodes (index, node->left, default_label, index_type);
2960 else if (node_is_bounded (node->left, index_type))
2962 emit_cmp_and_jump_insns (index,
2965 expand_normal (node->high),
2967 LT, NULL_RTX, mode, unsignedp,
2968 label_rtx (node->left->code_label));
2969 emit_case_nodes (index, node->right, default_label, index_type);
2972 /* If both children are single-valued cases with no
2973 children, finish up all the work. This way, we can save
2974 one ordered comparison. */
2975 else if (tree_int_cst_equal (node->right->low, node->right->high)
2976 && node->right->left == 0
2977 && node->right->right == 0
2978 && tree_int_cst_equal (node->left->low, node->left->high)
2979 && node->left->left == 0
2980 && node->left->right == 0)
2982 /* Neither node is bounded. First distinguish the two sides;
2983 then emit the code for one side at a time. */
2985 /* See if the value matches what the right hand side
2987 do_jump_if_equal (mode, index,
2988 convert_modes (mode, imode,
2989 expand_normal (node->right->low),
2991 label_rtx (node->right->code_label),
2994 /* See if the value matches what the left hand side
2996 do_jump_if_equal (mode, index,
2997 convert_modes (mode, imode,
2998 expand_normal (node->left->low),
3000 label_rtx (node->left->code_label),
3006 /* Neither node is bounded. First distinguish the two sides;
3007 then emit the code for one side at a time. */
3010 = build_decl (CURR_INSN_LOCATION,
3011 LABEL_DECL, NULL_TREE, NULL_TREE);
3013 /* See if the value is on the right. */
3014 emit_cmp_and_jump_insns (index,
3017 expand_normal (node->high),
3019 GT, NULL_RTX, mode, unsignedp,
3020 label_rtx (test_label));
3022 /* Value must be on the left.
3023 Handle the left-hand subtree. */
3024 emit_case_nodes (index, node->left, default_label, index_type);
3025 /* If left-hand subtree does nothing,
3028 emit_jump (default_label);
3030 /* Code branches here for the right-hand subtree. */
3031 expand_label (test_label);
3032 emit_case_nodes (index, node->right, default_label, index_type);
3036 else if (node->right != 0 && node->left == 0)
3038 /* Here we have a right child but no left so we issue a conditional
3039 branch to default and process the right child.
3041 Omit the conditional branch to default if the right child
3042 does not have any children and is single valued; it would
3043 cost too much space to save so little time. */
3045 if (node->right->right || node->right->left
3046 || !tree_int_cst_equal (node->right->low, node->right->high))
3048 if (!node_has_low_bound (node, index_type))
3050 emit_cmp_and_jump_insns (index,
3053 expand_normal (node->high),
3055 LT, NULL_RTX, mode, unsignedp,
3059 emit_case_nodes (index, node->right, default_label, index_type);
3062 /* We cannot process node->right normally
3063 since we haven't ruled out the numbers less than
3064 this node's value. So handle node->right explicitly. */
3065 do_jump_if_equal (mode, index,
3068 expand_normal (node->right->low),
3070 label_rtx (node->right->code_label), unsignedp);
3073 else if (node->right == 0 && node->left != 0)
3075 /* Just one subtree, on the left. */
3076 if (node->left->left || node->left->right
3077 || !tree_int_cst_equal (node->left->low, node->left->high))
3079 if (!node_has_high_bound (node, index_type))
3081 emit_cmp_and_jump_insns (index,
3084 expand_normal (node->high),
3086 GT, NULL_RTX, mode, unsignedp,
3090 emit_case_nodes (index, node->left, default_label, index_type);
3093 /* We cannot process node->left normally
3094 since we haven't ruled out the numbers less than
3095 this node's value. So handle node->left explicitly. */
3096 do_jump_if_equal (mode, index,
3099 expand_normal (node->left->low),
3101 label_rtx (node->left->code_label), unsignedp);
3106 /* Node is a range. These cases are very similar to those for a single
3107 value, except that we do not start by testing whether this node
3108 is the one to branch to. */
3110 if (node->right != 0 && node->left != 0)
3112 /* Node has subtrees on both sides.
3113 If the right-hand subtree is bounded,
3114 test for it first, since we can go straight there.
3115 Otherwise, we need to make a branch in the control structure,
3116 then handle the two subtrees. */
3117 tree test_label = 0;
3119 if (node_is_bounded (node->right, index_type))
3120 /* Right hand node is fully bounded so we can eliminate any
3121 testing and branch directly to the target code. */
3122 emit_cmp_and_jump_insns (index,
3125 expand_normal (node->high),
3127 GT, NULL_RTX, mode, unsignedp,
3128 label_rtx (node->right->code_label));
3131 /* Right hand node requires testing.
3132 Branch to a label where we will handle it later. */
3134 test_label = build_decl (CURR_INSN_LOCATION,
3135 LABEL_DECL, NULL_TREE, NULL_TREE);
3136 emit_cmp_and_jump_insns (index,
3139 expand_normal (node->high),
3141 GT, NULL_RTX, mode, unsignedp,
3142 label_rtx (test_label));
3145 /* Value belongs to this node or to the left-hand subtree. */
3147 emit_cmp_and_jump_insns (index,
3150 expand_normal (node->low),
3152 GE, NULL_RTX, mode, unsignedp,
3153 label_rtx (node->code_label));
3155 /* Handle the left-hand subtree. */
3156 emit_case_nodes (index, node->left, default_label, index_type);
3158 /* If right node had to be handled later, do that now. */
3162 /* If the left-hand subtree fell through,
3163 don't let it fall into the right-hand subtree. */
3165 emit_jump (default_label);
3167 expand_label (test_label);
3168 emit_case_nodes (index, node->right, default_label, index_type);
3172 else if (node->right != 0 && node->left == 0)
3174 /* Deal with values to the left of this node,
3175 if they are possible. */
3176 if (!node_has_low_bound (node, index_type))
3178 emit_cmp_and_jump_insns (index,
3181 expand_normal (node->low),
3183 LT, NULL_RTX, mode, unsignedp,
3187 /* Value belongs to this node or to the right-hand subtree. */
3189 emit_cmp_and_jump_insns (index,
3192 expand_normal (node->high),
3194 LE, NULL_RTX, mode, unsignedp,
3195 label_rtx (node->code_label));
3197 emit_case_nodes (index, node->right, default_label, index_type);
3200 else if (node->right == 0 && node->left != 0)
3202 /* Deal with values to the right of this node,
3203 if they are possible. */
3204 if (!node_has_high_bound (node, index_type))
3206 emit_cmp_and_jump_insns (index,
3209 expand_normal (node->high),
3211 GT, NULL_RTX, mode, unsignedp,
3215 /* Value belongs to this node or to the left-hand subtree. */
3217 emit_cmp_and_jump_insns (index,
3220 expand_normal (node->low),
3222 GE, NULL_RTX, mode, unsignedp,
3223 label_rtx (node->code_label));
3225 emit_case_nodes (index, node->left, default_label, index_type);
3230 /* Node has no children so we check low and high bounds to remove
3231 redundant tests. Only one of the bounds can exist,
3232 since otherwise this node is bounded--a case tested already. */
3233 int high_bound = node_has_high_bound (node, index_type);
3234 int low_bound = node_has_low_bound (node, index_type);
3236 if (!high_bound && low_bound)
3238 emit_cmp_and_jump_insns (index,
3241 expand_normal (node->high),
3243 GT, NULL_RTX, mode, unsignedp,
3247 else if (!low_bound && high_bound)
3249 emit_cmp_and_jump_insns (index,
3252 expand_normal (node->low),
3254 LT, NULL_RTX, mode, unsignedp,
3257 else if (!low_bound && !high_bound)
3259 /* Widen LOW and HIGH to the same width as INDEX. */
3260 tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
3261 tree low = build1 (CONVERT_EXPR, type, node->low);
3262 tree high = build1 (CONVERT_EXPR, type, node->high);
3263 rtx low_rtx, new_index, new_bound;
3265 /* Instead of doing two branches, emit one unsigned branch for
3266 (index-low) > (high-low). */
3267 low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL);
3268 new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
3269 NULL_RTX, unsignedp,
3271 new_bound = expand_expr (fold_build2 (MINUS_EXPR, type,
3273 NULL_RTX, mode, EXPAND_NORMAL);
3275 emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
3276 mode, 1, default_label);
3279 emit_jump (label_rtx (node->code_label));