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))
691 if (TREE_VALUE (tail) == error_mark_node)
693 regname = TREE_STRING_POINTER (TREE_VALUE (tail));
695 i = decode_reg_name (regname);
696 if (i >= 0 || i == -4)
699 error ("unknown register name %qs in %<asm%>", regname);
701 /* Mark clobbered registers. */
704 /* Clobbering the PIC register is an error. */
705 if (i == (int) PIC_OFFSET_TABLE_REGNUM)
707 error ("PIC register %qs clobbered in %<asm%>", regname);
711 SET_HARD_REG_BIT (clobbered_regs, i);
715 /* First pass over inputs and outputs checks validity and sets
716 mark_addressable if needed. */
719 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
721 tree val = TREE_VALUE (tail);
722 tree type = TREE_TYPE (val);
723 const char *constraint;
728 /* If there's an erroneous arg, emit no insn. */
729 if (type == error_mark_node)
732 /* Try to parse the output constraint. If that fails, there's
733 no point in going further. */
734 constraint = constraints[i];
735 if (!parse_output_constraint (&constraint, i, ninputs, noutputs,
736 &allows_mem, &allows_reg, &is_inout))
743 && REG_P (DECL_RTL (val))
744 && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))))
745 mark_addressable (val);
752 if (ninputs + noutputs > MAX_RECOG_OPERANDS)
754 error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS);
758 for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail))
760 bool allows_reg, allows_mem;
761 const char *constraint;
763 /* If there's an erroneous arg, emit no insn, because the ASM_INPUT
764 would get VOIDmode and that could cause a crash in reload. */
765 if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node)
768 constraint = constraints[i + noutputs];
769 if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
770 constraints, &allows_mem, &allows_reg))
773 if (! allows_reg && allows_mem)
774 mark_addressable (TREE_VALUE (tail));
777 /* Second pass evaluates arguments. */
779 /* Make sure stack is consistent for asm goto. */
781 do_pending_stack_adjust ();
784 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
786 tree val = TREE_VALUE (tail);
787 tree type = TREE_TYPE (val);
794 ok = parse_output_constraint (&constraints[i], i, ninputs,
795 noutputs, &allows_mem, &allows_reg,
799 /* If an output operand is not a decl or indirect ref and our constraint
800 allows a register, make a temporary to act as an intermediate.
801 Make the asm insn write into that, then our caller will copy it to
802 the real output operand. Likewise for promoted variables. */
804 generating_concat_p = 0;
806 real_output_rtx[i] = NULL_RTX;
807 if ((TREE_CODE (val) == INDIRECT_REF
810 && (allows_mem || REG_P (DECL_RTL (val)))
811 && ! (REG_P (DECL_RTL (val))
812 && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))
816 op = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE);
818 op = validize_mem (op);
820 if (! allows_reg && !MEM_P (op))
821 error ("output number %d not directly addressable", i);
822 if ((! allows_mem && MEM_P (op))
823 || GET_CODE (op) == CONCAT)
825 real_output_rtx[i] = op;
826 op = gen_reg_rtx (GET_MODE (op));
828 emit_move_insn (op, real_output_rtx[i]);
833 op = assign_temp (type, 0, 0, 1);
834 op = validize_mem (op);
835 if (!MEM_P (op) && TREE_CODE (TREE_VALUE (tail)) == SSA_NAME)
836 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (TREE_VALUE (tail)), op);
837 TREE_VALUE (tail) = make_tree (type, op);
841 generating_concat_p = old_generating_concat_p;
845 inout_mode[ninout] = TYPE_MODE (type);
846 inout_opnum[ninout++] = i;
849 if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
850 clobber_conflict_found = 1;
853 /* Make vectors for the expression-rtx, constraint strings,
854 and named operands. */
856 argvec = rtvec_alloc (ninputs);
857 constraintvec = rtvec_alloc (ninputs);
858 labelvec = rtvec_alloc (nlabels);
860 body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode
861 : GET_MODE (output_rtx[0])),
862 ggc_strdup (TREE_STRING_POINTER (string)),
863 empty_string, 0, argvec, constraintvec,
866 MEM_VOLATILE_P (body) = vol;
868 /* Eval the inputs and put them into ARGVEC.
869 Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */
871 for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i)
873 bool allows_reg, allows_mem;
874 const char *constraint;
879 constraint = constraints[i + noutputs];
880 ok = parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
881 constraints, &allows_mem, &allows_reg);
884 generating_concat_p = 0;
886 val = TREE_VALUE (tail);
887 type = TREE_TYPE (val);
888 /* EXPAND_INITIALIZER will not generate code for valid initializer
889 constants, but will still generate code for other types of operand.
890 This is the behavior we want for constant constraints. */
891 op = expand_expr (val, NULL_RTX, VOIDmode,
892 allows_reg ? EXPAND_NORMAL
893 : allows_mem ? EXPAND_MEMORY
894 : EXPAND_INITIALIZER);
896 /* Never pass a CONCAT to an ASM. */
897 if (GET_CODE (op) == CONCAT)
898 op = force_reg (GET_MODE (op), op);
900 op = validize_mem (op);
902 if (asm_operand_ok (op, constraint, NULL) <= 0)
904 if (allows_reg && TYPE_MODE (type) != BLKmode)
905 op = force_reg (TYPE_MODE (type), op);
906 else if (!allows_mem)
907 warning (0, "asm operand %d probably doesn%'t match constraints",
911 /* We won't recognize either volatile memory or memory
912 with a queued address as available a memory_operand
913 at this point. Ignore it: clearly this *is* a memory. */
917 warning (0, "use of memory input without lvalue in "
918 "asm operand %d is deprecated", i + noutputs);
922 rtx mem = force_const_mem (TYPE_MODE (type), op);
924 op = validize_mem (mem);
926 op = force_reg (TYPE_MODE (type), op);
929 || GET_CODE (op) == SUBREG
930 || GET_CODE (op) == CONCAT)
932 tree qual_type = build_qualified_type (type,
935 rtx memloc = assign_temp (qual_type, 1, 1, 1);
936 memloc = validize_mem (memloc);
937 emit_move_insn (memloc, op);
943 generating_concat_p = old_generating_concat_p;
944 ASM_OPERANDS_INPUT (body, i) = op;
946 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i)
947 = gen_rtx_ASM_INPUT (TYPE_MODE (type),
948 ggc_strdup (constraints[i + noutputs]));
950 if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
951 clobber_conflict_found = 1;
954 /* Protect all the operands from the queue now that they have all been
957 generating_concat_p = 0;
959 /* For in-out operands, copy output rtx to input rtx. */
960 for (i = 0; i < ninout; i++)
962 int j = inout_opnum[i];
965 ASM_OPERANDS_INPUT (body, ninputs - ninout + i)
968 sprintf (buffer, "%d", j);
969 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i)
970 = gen_rtx_ASM_INPUT (inout_mode[i], ggc_strdup (buffer));
973 /* Copy labels to the vector. */
974 for (i = 0, tail = labels; i < nlabels; ++i, tail = TREE_CHAIN (tail))
975 ASM_OPERANDS_LABEL (body, i)
976 = gen_rtx_LABEL_REF (Pmode, label_rtx (TREE_VALUE (tail)));
978 generating_concat_p = old_generating_concat_p;
980 /* Now, for each output, construct an rtx
981 (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER
982 ARGVEC CONSTRAINTS OPNAMES))
983 If there is more than one, put them inside a PARALLEL. */
985 if (nlabels > 0 && nclobbers == 0)
987 gcc_assert (noutputs == 0);
988 emit_jump_insn (body);
990 else if (noutputs == 0 && nclobbers == 0)
992 /* No output operands: put in a raw ASM_OPERANDS rtx. */
995 else if (noutputs == 1 && nclobbers == 0)
997 ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = ggc_strdup (constraints[0]);
998 emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body));
1008 body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers));
1010 /* For each output operand, store a SET. */
1011 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1013 XVECEXP (body, 0, i)
1014 = gen_rtx_SET (VOIDmode,
1016 gen_rtx_ASM_OPERANDS
1017 (GET_MODE (output_rtx[i]),
1018 ggc_strdup (TREE_STRING_POINTER (string)),
1019 ggc_strdup (constraints[i]),
1020 i, argvec, constraintvec, labelvec, locus));
1022 MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol;
1025 /* If there are no outputs (but there are some clobbers)
1026 store the bare ASM_OPERANDS into the PARALLEL. */
1029 XVECEXP (body, 0, i++) = obody;
1031 /* Store (clobber REG) for each clobbered register specified. */
1033 for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
1035 const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
1036 int j = decode_reg_name (regname);
1041 if (j == -3) /* `cc', which is not a register */
1044 if (j == -4) /* `memory', don't cache memory across asm */
1046 XVECEXP (body, 0, i++)
1047 = gen_rtx_CLOBBER (VOIDmode,
1050 gen_rtx_SCRATCH (VOIDmode)));
1054 /* Ignore unknown register, error already signaled. */
1058 /* Use QImode since that's guaranteed to clobber just one reg. */
1059 clobbered_reg = gen_rtx_REG (QImode, j);
1061 /* Do sanity check for overlap between clobbers and respectively
1062 input and outputs that hasn't been handled. Such overlap
1063 should have been detected and reported above. */
1064 if (!clobber_conflict_found)
1068 /* We test the old body (obody) contents to avoid tripping
1069 over the under-construction body. */
1070 for (opno = 0; opno < noutputs; opno++)
1071 if (reg_overlap_mentioned_p (clobbered_reg, output_rtx[opno]))
1072 internal_error ("asm clobber conflict with output operand");
1074 for (opno = 0; opno < ninputs - ninout; opno++)
1075 if (reg_overlap_mentioned_p (clobbered_reg,
1076 ASM_OPERANDS_INPUT (obody, opno)))
1077 internal_error ("asm clobber conflict with input operand");
1080 XVECEXP (body, 0, i++)
1081 = gen_rtx_CLOBBER (VOIDmode, clobbered_reg);
1085 emit_jump_insn (body);
1090 /* For any outputs that needed reloading into registers, spill them
1091 back to where they belong. */
1092 for (i = 0; i < noutputs; ++i)
1093 if (real_output_rtx[i])
1094 emit_move_insn (real_output_rtx[i], output_rtx[i]);
1096 crtl->has_asm_statement = 1;
1101 expand_asm_stmt (gimple stmt)
1104 tree outputs, tail, t;
1108 tree str, out, in, cl, labels;
1109 location_t locus = gimple_location (stmt);
1111 /* Meh... convert the gimple asm operands into real tree lists.
1112 Eventually we should make all routines work on the vectors instead
1113 of relying on TREE_CHAIN. */
1115 n = gimple_asm_noutputs (stmt);
1118 t = out = gimple_asm_output_op (stmt, 0);
1119 for (i = 1; i < n; i++)
1120 t = TREE_CHAIN (t) = gimple_asm_output_op (stmt, i);
1124 n = gimple_asm_ninputs (stmt);
1127 t = in = gimple_asm_input_op (stmt, 0);
1128 for (i = 1; i < n; i++)
1129 t = TREE_CHAIN (t) = gimple_asm_input_op (stmt, i);
1133 n = gimple_asm_nclobbers (stmt);
1136 t = cl = gimple_asm_clobber_op (stmt, 0);
1137 for (i = 1; i < n; i++)
1138 t = TREE_CHAIN (t) = gimple_asm_clobber_op (stmt, i);
1142 n = gimple_asm_nlabels (stmt);
1145 t = labels = gimple_asm_label_op (stmt, 0);
1146 for (i = 1; i < n; i++)
1147 t = TREE_CHAIN (t) = gimple_asm_label_op (stmt, i);
1150 s = gimple_asm_string (stmt);
1151 str = build_string (strlen (s), s);
1153 if (gimple_asm_input_p (stmt))
1155 expand_asm_loc (str, gimple_asm_volatile_p (stmt), locus);
1160 noutputs = gimple_asm_noutputs (stmt);
1161 /* o[I] is the place that output number I should be written. */
1162 o = (tree *) alloca (noutputs * sizeof (tree));
1164 /* Record the contents of OUTPUTS before it is modified. */
1165 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1166 o[i] = TREE_VALUE (tail);
1168 /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of
1169 OUTPUTS some trees for where the values were actually stored. */
1170 expand_asm_operands (str, outputs, in, cl, labels,
1171 gimple_asm_volatile_p (stmt), locus);
1173 /* Copy all the intermediate outputs into the specified outputs. */
1174 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1176 if (o[i] != TREE_VALUE (tail))
1178 expand_assignment (o[i], TREE_VALUE (tail), false);
1181 /* Restore the original value so that it's correct the next
1182 time we expand this function. */
1183 TREE_VALUE (tail) = o[i];
1188 /* A subroutine of expand_asm_operands. Check that all operands have
1189 the same number of alternatives. Return true if so. */
1192 check_operand_nalternatives (tree outputs, tree inputs)
1194 if (outputs || inputs)
1196 tree tmp = TREE_PURPOSE (outputs ? outputs : inputs);
1198 = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp)));
1201 if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES)
1203 error ("too many alternatives in %<asm%>");
1210 const char *constraint
1211 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp)));
1213 if (n_occurrences (',', constraint) != nalternatives)
1215 error ("operand constraints for %<asm%> differ "
1216 "in number of alternatives");
1220 if (TREE_CHAIN (tmp))
1221 tmp = TREE_CHAIN (tmp);
1223 tmp = next, next = 0;
1230 /* A subroutine of expand_asm_operands. Check that all operand names
1231 are unique. Return true if so. We rely on the fact that these names
1232 are identifiers, and so have been canonicalized by get_identifier,
1233 so all we need are pointer comparisons. */
1236 check_unique_operand_names (tree outputs, tree inputs, tree labels)
1240 for (i = outputs; i ; i = TREE_CHAIN (i))
1242 tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1246 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1247 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1251 for (i = inputs; i ; i = TREE_CHAIN (i))
1253 tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1257 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1258 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1260 for (j = outputs; j ; j = TREE_CHAIN (j))
1261 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1265 for (i = labels; i ; i = TREE_CHAIN (i))
1267 tree i_name = TREE_PURPOSE (i);
1271 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1272 if (simple_cst_equal (i_name, TREE_PURPOSE (j)))
1274 for (j = inputs; j ; j = TREE_CHAIN (j))
1275 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1282 error ("duplicate asm operand name %qs",
1283 TREE_STRING_POINTER (TREE_PURPOSE (TREE_PURPOSE (i))));
1287 /* A subroutine of expand_asm_operands. Resolve the names of the operands
1288 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
1289 STRING and in the constraints to those numbers. */
1292 resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels)
1299 check_unique_operand_names (outputs, inputs, labels);
1301 /* Substitute [<name>] in input constraint strings. There should be no
1302 named operands in output constraints. */
1303 for (t = inputs; t ; t = TREE_CHAIN (t))
1305 c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
1306 if (strchr (c, '[') != NULL)
1308 p = buffer = xstrdup (c);
1309 while ((p = strchr (p, '[')) != NULL)
1310 p = resolve_operand_name_1 (p, outputs, inputs, NULL);
1311 TREE_VALUE (TREE_PURPOSE (t))
1312 = build_string (strlen (buffer), buffer);
1317 /* Now check for any needed substitutions in the template. */
1318 c = TREE_STRING_POINTER (string);
1319 while ((c = strchr (c, '%')) != NULL)
1323 else if (ISALPHA (c[1]) && c[2] == '[')
1327 c += 1 + (c[1] == '%');
1334 /* OK, we need to make a copy so we can perform the substitutions.
1335 Assume that we will not need extra space--we get to remove '['
1336 and ']', which means we cannot have a problem until we have more
1337 than 999 operands. */
1338 buffer = xstrdup (TREE_STRING_POINTER (string));
1339 p = buffer + (c - TREE_STRING_POINTER (string));
1341 while ((p = strchr (p, '%')) != NULL)
1345 else if (ISALPHA (p[1]) && p[2] == '[')
1349 p += 1 + (p[1] == '%');
1353 p = resolve_operand_name_1 (p, outputs, inputs, labels);
1356 string = build_string (strlen (buffer), buffer);
1363 /* A subroutine of resolve_operand_names. P points to the '[' for a
1364 potential named operand of the form [<name>]. In place, replace
1365 the name and brackets with a number. Return a pointer to the
1366 balance of the string after substitution. */
1369 resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels)
1375 /* Collect the operand name. */
1376 q = strchr (++p, ']');
1379 error ("missing close brace for named operand");
1380 return strchr (p, '\0');
1384 /* Resolve the name to a number. */
1385 for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
1387 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1388 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1391 for (t = inputs; t ; t = TREE_CHAIN (t), op++)
1393 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1394 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1397 for (t = labels; t ; t = TREE_CHAIN (t), op++)
1399 tree name = TREE_PURPOSE (t);
1400 if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1404 error ("undefined named operand %qs", identifier_to_locale (p));
1408 /* Replace the name with the number. Unfortunately, not all libraries
1409 get the return value of sprintf correct, so search for the end of the
1410 generated string by hand. */
1411 sprintf (--p, "%d", op);
1412 p = strchr (p, '\0');
1414 /* Verify the no extra buffer space assumption. */
1415 gcc_assert (p <= q);
1417 /* Shift the rest of the buffer down to fill the gap. */
1418 memmove (p, q + 1, strlen (q + 1) + 1);
1423 /* Generate RTL to evaluate the expression EXP. */
1426 expand_expr_stmt (tree exp)
1431 value = expand_expr (exp, const0_rtx, VOIDmode, EXPAND_NORMAL);
1432 type = TREE_TYPE (exp);
1434 /* If all we do is reference a volatile value in memory,
1435 copy it to a register to be sure it is actually touched. */
1436 if (value && MEM_P (value) && TREE_THIS_VOLATILE (exp))
1438 if (TYPE_MODE (type) == VOIDmode)
1440 else if (TYPE_MODE (type) != BLKmode)
1441 value = copy_to_reg (value);
1444 rtx lab = gen_label_rtx ();
1446 /* Compare the value with itself to reference it. */
1447 emit_cmp_and_jump_insns (value, value, EQ,
1448 expand_normal (TYPE_SIZE (type)),
1454 /* Free any temporaries used to evaluate this expression. */
1458 /* Warn if EXP contains any computations whose results are not used.
1459 Return 1 if a warning is printed; 0 otherwise. LOCUS is the
1460 (potential) location of the expression. */
1463 warn_if_unused_value (const_tree exp, location_t locus)
1466 if (TREE_USED (exp) || TREE_NO_WARNING (exp))
1469 /* Don't warn about void constructs. This includes casting to void,
1470 void function calls, and statement expressions with a final cast
1472 if (VOID_TYPE_P (TREE_TYPE (exp)))
1475 if (EXPR_HAS_LOCATION (exp))
1476 locus = EXPR_LOCATION (exp);
1478 switch (TREE_CODE (exp))
1480 case PREINCREMENT_EXPR:
1481 case POSTINCREMENT_EXPR:
1482 case PREDECREMENT_EXPR:
1483 case POSTDECREMENT_EXPR:
1488 case TRY_CATCH_EXPR:
1489 case WITH_CLEANUP_EXPR:
1495 /* For a binding, warn if no side effect within it. */
1496 exp = BIND_EXPR_BODY (exp);
1500 case NON_LVALUE_EXPR:
1501 exp = TREE_OPERAND (exp, 0);
1504 case TRUTH_ORIF_EXPR:
1505 case TRUTH_ANDIF_EXPR:
1506 /* In && or ||, warn if 2nd operand has no side effect. */
1507 exp = TREE_OPERAND (exp, 1);
1511 if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus))
1513 /* Let people do `(foo (), 0)' without a warning. */
1514 if (TREE_CONSTANT (TREE_OPERAND (exp, 1)))
1516 exp = TREE_OPERAND (exp, 1);
1520 /* If this is an expression with side effects, don't warn; this
1521 case commonly appears in macro expansions. */
1522 if (TREE_SIDE_EFFECTS (exp))
1527 /* Don't warn about automatic dereferencing of references, since
1528 the user cannot control it. */
1529 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE)
1531 exp = TREE_OPERAND (exp, 0);
1537 /* Referencing a volatile value is a side effect, so don't warn. */
1538 if ((DECL_P (exp) || REFERENCE_CLASS_P (exp))
1539 && TREE_THIS_VOLATILE (exp))
1542 /* If this is an expression which has no operands, there is no value
1543 to be unused. There are no such language-independent codes,
1544 but front ends may define such. */
1545 if (EXPRESSION_CLASS_P (exp) && TREE_OPERAND_LENGTH (exp) == 0)
1549 warning_at (locus, OPT_Wunused_value, "value computed is not used");
1555 /* Generate RTL to return from the current function, with no value.
1556 (That is, we do not do anything about returning any value.) */
1559 expand_null_return (void)
1561 /* If this function was declared to return a value, but we
1562 didn't, clobber the return registers so that they are not
1563 propagated live to the rest of the function. */
1564 clobber_return_register ();
1566 expand_null_return_1 ();
1569 /* Generate RTL to return directly from the current function.
1570 (That is, we bypass any return value.) */
1573 expand_naked_return (void)
1577 clear_pending_stack_adjust ();
1578 do_pending_stack_adjust ();
1580 end_label = naked_return_label;
1582 end_label = naked_return_label = gen_label_rtx ();
1584 emit_jump (end_label);
1587 /* Generate RTL to return from the current function, with value VAL. */
1590 expand_value_return (rtx val)
1592 /* Copy the value to the return location unless it's already there. */
1594 tree decl = DECL_RESULT (current_function_decl);
1595 rtx return_reg = DECL_RTL (decl);
1596 if (return_reg != val)
1598 tree funtype = TREE_TYPE (current_function_decl);
1599 tree type = TREE_TYPE (decl);
1600 int unsignedp = TYPE_UNSIGNED (type);
1601 enum machine_mode old_mode = DECL_MODE (decl);
1602 enum machine_mode mode;
1603 if (DECL_BY_REFERENCE (decl))
1604 mode = promote_function_mode (type, old_mode, &unsignedp, funtype, 2);
1606 mode = promote_function_mode (type, old_mode, &unsignedp, funtype, 1);
1608 if (mode != old_mode)
1609 val = convert_modes (mode, old_mode, val, unsignedp);
1611 if (GET_CODE (return_reg) == PARALLEL)
1612 emit_group_load (return_reg, val, type, int_size_in_bytes (type));
1614 emit_move_insn (return_reg, val);
1617 expand_null_return_1 ();
1620 /* Output a return with no value. */
1623 expand_null_return_1 (void)
1625 clear_pending_stack_adjust ();
1626 do_pending_stack_adjust ();
1627 emit_jump (return_label);
1630 /* Generate RTL to evaluate the expression RETVAL and return it
1631 from the current function. */
1634 expand_return (tree retval)
1640 /* If function wants no value, give it none. */
1641 if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE)
1643 expand_normal (retval);
1644 expand_null_return ();
1648 if (retval == error_mark_node)
1650 /* Treat this like a return of no value from a function that
1652 expand_null_return ();
1655 else if ((TREE_CODE (retval) == MODIFY_EXPR
1656 || TREE_CODE (retval) == INIT_EXPR)
1657 && TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL)
1658 retval_rhs = TREE_OPERAND (retval, 1);
1660 retval_rhs = retval;
1662 result_rtl = DECL_RTL (DECL_RESULT (current_function_decl));
1664 /* If we are returning the RESULT_DECL, then the value has already
1665 been stored into it, so we don't have to do anything special. */
1666 if (TREE_CODE (retval_rhs) == RESULT_DECL)
1667 expand_value_return (result_rtl);
1669 /* If the result is an aggregate that is being returned in one (or more)
1670 registers, load the registers here. The compiler currently can't handle
1671 copying a BLKmode value into registers. We could put this code in a
1672 more general area (for use by everyone instead of just function
1673 call/return), but until this feature is generally usable it is kept here
1674 (and in expand_call). */
1676 else if (retval_rhs != 0
1677 && TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode
1678 && REG_P (result_rtl))
1681 unsigned HOST_WIDE_INT bitpos, xbitpos;
1682 unsigned HOST_WIDE_INT padding_correction = 0;
1683 unsigned HOST_WIDE_INT bytes
1684 = int_size_in_bytes (TREE_TYPE (retval_rhs));
1685 int n_regs = (bytes + UNITS_PER_WORD - 1) / UNITS_PER_WORD;
1686 unsigned int bitsize
1687 = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)), BITS_PER_WORD);
1688 rtx *result_pseudos = XALLOCAVEC (rtx, n_regs);
1689 rtx result_reg, src = NULL_RTX, dst = NULL_RTX;
1690 rtx result_val = expand_normal (retval_rhs);
1691 enum machine_mode tmpmode, result_reg_mode;
1695 expand_null_return ();
1699 /* If the structure doesn't take up a whole number of words, see
1700 whether the register value should be padded on the left or on
1701 the right. Set PADDING_CORRECTION to the number of padding
1702 bits needed on the left side.
1704 In most ABIs, the structure will be returned at the least end of
1705 the register, which translates to right padding on little-endian
1706 targets and left padding on big-endian targets. The opposite
1707 holds if the structure is returned at the most significant
1708 end of the register. */
1709 if (bytes % UNITS_PER_WORD != 0
1710 && (targetm.calls.return_in_msb (TREE_TYPE (retval_rhs))
1712 : BYTES_BIG_ENDIAN))
1713 padding_correction = (BITS_PER_WORD - ((bytes % UNITS_PER_WORD)
1716 /* Copy the structure BITSIZE bits at a time. */
1717 for (bitpos = 0, xbitpos = padding_correction;
1718 bitpos < bytes * BITS_PER_UNIT;
1719 bitpos += bitsize, xbitpos += bitsize)
1721 /* We need a new destination pseudo each time xbitpos is
1722 on a word boundary and when xbitpos == padding_correction
1723 (the first time through). */
1724 if (xbitpos % BITS_PER_WORD == 0
1725 || xbitpos == padding_correction)
1727 /* Generate an appropriate register. */
1728 dst = gen_reg_rtx (word_mode);
1729 result_pseudos[xbitpos / BITS_PER_WORD] = dst;
1731 /* Clear the destination before we move anything into it. */
1732 emit_move_insn (dst, CONST0_RTX (GET_MODE (dst)));
1735 /* We need a new source operand each time bitpos is on a word
1737 if (bitpos % BITS_PER_WORD == 0)
1738 src = operand_subword_force (result_val,
1739 bitpos / BITS_PER_WORD,
1742 /* Use bitpos for the source extraction (left justified) and
1743 xbitpos for the destination store (right justified). */
1744 store_bit_field (dst, bitsize, xbitpos % BITS_PER_WORD, word_mode,
1745 extract_bit_field (src, bitsize,
1746 bitpos % BITS_PER_WORD, 1, false,
1747 NULL_RTX, word_mode, word_mode));
1750 tmpmode = GET_MODE (result_rtl);
1751 if (tmpmode == BLKmode)
1753 /* Find the smallest integer mode large enough to hold the
1754 entire structure and use that mode instead of BLKmode
1755 on the USE insn for the return register. */
1756 for (tmpmode = GET_CLASS_NARROWEST_MODE (MODE_INT);
1757 tmpmode != VOIDmode;
1758 tmpmode = GET_MODE_WIDER_MODE (tmpmode))
1759 /* Have we found a large enough mode? */
1760 if (GET_MODE_SIZE (tmpmode) >= bytes)
1763 /* A suitable mode should have been found. */
1764 gcc_assert (tmpmode != VOIDmode);
1766 PUT_MODE (result_rtl, tmpmode);
1769 if (GET_MODE_SIZE (tmpmode) < GET_MODE_SIZE (word_mode))
1770 result_reg_mode = word_mode;
1772 result_reg_mode = tmpmode;
1773 result_reg = gen_reg_rtx (result_reg_mode);
1775 for (i = 0; i < n_regs; i++)
1776 emit_move_insn (operand_subword (result_reg, i, 0, result_reg_mode),
1779 if (tmpmode != result_reg_mode)
1780 result_reg = gen_lowpart (tmpmode, result_reg);
1782 expand_value_return (result_reg);
1784 else if (retval_rhs != 0
1785 && !VOID_TYPE_P (TREE_TYPE (retval_rhs))
1786 && (REG_P (result_rtl)
1787 || (GET_CODE (result_rtl) == PARALLEL)))
1789 /* Calculate the return value into a temporary (usually a pseudo
1791 tree ot = TREE_TYPE (DECL_RESULT (current_function_decl));
1792 tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST);
1794 val = assign_temp (nt, 0, 0, 1);
1795 val = expand_expr (retval_rhs, val, GET_MODE (val), EXPAND_NORMAL);
1796 val = force_not_mem (val);
1797 /* Return the calculated value. */
1798 expand_value_return (val);
1802 /* No hard reg used; calculate value into hard return reg. */
1803 expand_expr (retval, const0_rtx, VOIDmode, EXPAND_NORMAL);
1804 expand_value_return (result_rtl);
1808 /* Emit code to restore vital registers at the beginning of a nonlocal goto
1811 expand_nl_goto_receiver (void)
1815 /* Clobber the FP when we get here, so we have to make sure it's
1816 marked as used by this function. */
1817 emit_use (hard_frame_pointer_rtx);
1819 /* Mark the static chain as clobbered here so life information
1820 doesn't get messed up for it. */
1821 chain = targetm.calls.static_chain (current_function_decl, true);
1822 if (chain && REG_P (chain))
1823 emit_clobber (chain);
1825 #ifdef HAVE_nonlocal_goto
1826 if (! HAVE_nonlocal_goto)
1828 /* First adjust our frame pointer to its actual value. It was
1829 previously set to the start of the virtual area corresponding to
1830 the stacked variables when we branched here and now needs to be
1831 adjusted to the actual hardware fp value.
1833 Assignments are to virtual registers are converted by
1834 instantiate_virtual_regs into the corresponding assignment
1835 to the underlying register (fp in this case) that makes
1836 the original assignment true.
1837 So the following insn will actually be
1838 decrementing fp by STARTING_FRAME_OFFSET. */
1839 emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx);
1841 #if !HARD_FRAME_POINTER_IS_ARG_POINTER
1842 if (fixed_regs[ARG_POINTER_REGNUM])
1844 #ifdef ELIMINABLE_REGS
1845 /* If the argument pointer can be eliminated in favor of the
1846 frame pointer, we don't need to restore it. We assume here
1847 that if such an elimination is present, it can always be used.
1848 This is the case on all known machines; if we don't make this
1849 assumption, we do unnecessary saving on many machines. */
1850 static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS;
1853 for (i = 0; i < ARRAY_SIZE (elim_regs); i++)
1854 if (elim_regs[i].from == ARG_POINTER_REGNUM
1855 && elim_regs[i].to == HARD_FRAME_POINTER_REGNUM)
1858 if (i == ARRAY_SIZE (elim_regs))
1861 /* Now restore our arg pointer from the address at which it
1862 was saved in our stack frame. */
1863 emit_move_insn (crtl->args.internal_arg_pointer,
1864 copy_to_reg (get_arg_pointer_save_area ()));
1869 #ifdef HAVE_nonlocal_goto_receiver
1870 if (HAVE_nonlocal_goto_receiver)
1871 emit_insn (gen_nonlocal_goto_receiver ());
1874 /* We must not allow the code we just generated to be reordered by
1875 scheduling. Specifically, the update of the frame pointer must
1876 happen immediately, not later. */
1877 emit_insn (gen_blockage ());
1880 /* Generate RTL for the automatic variable declaration DECL.
1881 (Other kinds of declarations are simply ignored if seen here.) */
1884 expand_decl (tree decl)
1888 type = TREE_TYPE (decl);
1890 /* For a CONST_DECL, set mode, alignment, and sizes from those of the
1891 type in case this node is used in a reference. */
1892 if (TREE_CODE (decl) == CONST_DECL)
1894 DECL_MODE (decl) = TYPE_MODE (type);
1895 DECL_ALIGN (decl) = TYPE_ALIGN (type);
1896 DECL_SIZE (decl) = TYPE_SIZE (type);
1897 DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type);
1901 /* Otherwise, only automatic variables need any expansion done. Static and
1902 external variables, and external functions, will be handled by
1903 `assemble_variable' (called from finish_decl). TYPE_DECL requires
1904 nothing. PARM_DECLs are handled in `assign_parms'. */
1905 if (TREE_CODE (decl) != VAR_DECL)
1908 if (TREE_STATIC (decl) || DECL_EXTERNAL (decl))
1911 /* Create the RTL representation for the variable. */
1913 if (type == error_mark_node)
1914 SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx));
1916 else if (DECL_SIZE (decl) == 0)
1918 /* Variable with incomplete type. */
1920 if (DECL_INITIAL (decl) == 0)
1921 /* Error message was already done; now avoid a crash. */
1922 x = gen_rtx_MEM (BLKmode, const0_rtx);
1924 /* An initializer is going to decide the size of this array.
1925 Until we know the size, represent its address with a reg. */
1926 x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode));
1928 set_mem_attributes (x, decl, 1);
1929 SET_DECL_RTL (decl, x);
1931 else if (use_register_for_decl (decl))
1933 /* Automatic variable that can go in a register. */
1934 enum machine_mode reg_mode = promote_decl_mode (decl, NULL);
1936 SET_DECL_RTL (decl, gen_reg_rtx (reg_mode));
1938 /* Note if the object is a user variable. */
1939 if (!DECL_ARTIFICIAL (decl))
1940 mark_user_reg (DECL_RTL (decl));
1942 if (POINTER_TYPE_P (type))
1943 mark_reg_pointer (DECL_RTL (decl),
1944 TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl))));
1953 /* Variable-sized decls are dealt with in the gimplifier. */
1954 gcc_assert (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST);
1956 /* If we previously made RTL for this decl, it must be an array
1957 whose size was determined by the initializer.
1958 The old address was a register; set that register now
1959 to the proper address. */
1960 if (DECL_RTL_SET_P (decl))
1962 gcc_assert (MEM_P (DECL_RTL (decl)));
1963 gcc_assert (REG_P (XEXP (DECL_RTL (decl), 0)));
1964 oldaddr = XEXP (DECL_RTL (decl), 0);
1967 /* Set alignment we actually gave this decl. */
1968 DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT
1969 : GET_MODE_BITSIZE (DECL_MODE (decl)));
1970 DECL_USER_ALIGN (decl) = 0;
1972 x = assign_temp (decl, 1, 1, 1);
1973 set_mem_attributes (x, decl, 1);
1974 SET_DECL_RTL (decl, x);
1978 addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr);
1979 if (addr != oldaddr)
1980 emit_move_insn (oldaddr, addr);
1985 /* Emit code to save the current value of stack. */
1987 expand_stack_save (void)
1991 do_pending_stack_adjust ();
1992 emit_stack_save (SAVE_BLOCK, &ret, NULL_RTX);
1996 /* Emit code to restore the current value of stack. */
1998 expand_stack_restore (tree var)
2000 rtx sa = expand_normal (var);
2002 sa = convert_memory_address (Pmode, sa);
2003 emit_stack_restore (SAVE_BLOCK, sa, NULL_RTX);
2006 /* Do the insertion of a case label into case_list. The labels are
2007 fed to us in descending order from the sorted vector of case labels used
2008 in the tree part of the middle end. So the list we construct is
2009 sorted in ascending order. The bounds on the case range, LOW and HIGH,
2010 are converted to case's index type TYPE. */
2012 static struct case_node *
2013 add_case_node (struct case_node *head, tree type, tree low, tree high,
2014 tree label, alloc_pool case_node_pool)
2016 tree min_value, max_value;
2017 struct case_node *r;
2019 gcc_assert (TREE_CODE (low) == INTEGER_CST);
2020 gcc_assert (!high || TREE_CODE (high) == INTEGER_CST);
2022 min_value = TYPE_MIN_VALUE (type);
2023 max_value = TYPE_MAX_VALUE (type);
2025 /* If there's no HIGH value, then this is not a case range; it's
2026 just a simple case label. But that's just a degenerate case
2028 If the bounds are equal, turn this into the one-value case. */
2029 if (!high || tree_int_cst_equal (low, high))
2031 /* If the simple case value is unreachable, ignore it. */
2032 if ((TREE_CODE (min_value) == INTEGER_CST
2033 && tree_int_cst_compare (low, min_value) < 0)
2034 || (TREE_CODE (max_value) == INTEGER_CST
2035 && tree_int_cst_compare (low, max_value) > 0))
2037 low = fold_convert (type, low);
2042 /* If the entire case range is unreachable, ignore it. */
2043 if ((TREE_CODE (min_value) == INTEGER_CST
2044 && tree_int_cst_compare (high, min_value) < 0)
2045 || (TREE_CODE (max_value) == INTEGER_CST
2046 && tree_int_cst_compare (low, max_value) > 0))
2049 /* If the lower bound is less than the index type's minimum
2050 value, truncate the range bounds. */
2051 if (TREE_CODE (min_value) == INTEGER_CST
2052 && tree_int_cst_compare (low, min_value) < 0)
2054 low = fold_convert (type, low);
2056 /* If the upper bound is greater than the index type's maximum
2057 value, truncate the range bounds. */
2058 if (TREE_CODE (max_value) == INTEGER_CST
2059 && tree_int_cst_compare (high, max_value) > 0)
2061 high = fold_convert (type, high);
2065 /* Add this label to the chain. Make sure to drop overflow flags. */
2066 r = (struct case_node *) pool_alloc (case_node_pool);
2067 r->low = build_int_cst_wide (TREE_TYPE (low), TREE_INT_CST_LOW (low),
2068 TREE_INT_CST_HIGH (low));
2069 r->high = build_int_cst_wide (TREE_TYPE (high), TREE_INT_CST_LOW (high),
2070 TREE_INT_CST_HIGH (high));
2071 r->code_label = label;
2072 r->parent = r->left = NULL;
2077 /* Maximum number of case bit tests. */
2078 #define MAX_CASE_BIT_TESTS 3
2080 /* By default, enable case bit tests on targets with ashlsi3. */
2081 #ifndef CASE_USE_BIT_TESTS
2082 #define CASE_USE_BIT_TESTS (optab_handler (ashl_optab, word_mode) \
2083 != CODE_FOR_nothing)
2087 /* A case_bit_test represents a set of case nodes that may be
2088 selected from using a bit-wise comparison. HI and LO hold
2089 the integer to be tested against, LABEL contains the label
2090 to jump to upon success and BITS counts the number of case
2091 nodes handled by this test, typically the number of bits
2094 struct case_bit_test
2102 /* Determine whether "1 << x" is relatively cheap in word_mode. */
2105 bool lshift_cheap_p (void)
2107 static bool init = false;
2108 static bool cheap = true;
2112 rtx reg = gen_rtx_REG (word_mode, 10000);
2113 int cost = rtx_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg), SET,
2114 optimize_insn_for_speed_p ());
2115 cheap = cost < COSTS_N_INSNS (3);
2122 /* Comparison function for qsort to order bit tests by decreasing
2123 number of case nodes, i.e. the node with the most cases gets
2127 case_bit_test_cmp (const void *p1, const void *p2)
2129 const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
2130 const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
2132 if (d2->bits != d1->bits)
2133 return d2->bits - d1->bits;
2135 /* Stabilize the sort. */
2136 return CODE_LABEL_NUMBER (d2->label) - CODE_LABEL_NUMBER (d1->label);
2139 /* Expand a switch statement by a short sequence of bit-wise
2140 comparisons. "switch(x)" is effectively converted into
2141 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
2144 INDEX_EXPR is the value being switched on, which is of
2145 type INDEX_TYPE. MINVAL is the lowest case value of in
2146 the case nodes, of INDEX_TYPE type, and RANGE is highest
2147 value minus MINVAL, also of type INDEX_TYPE. NODES is
2148 the set of case nodes, and DEFAULT_LABEL is the label to
2149 branch to should none of the cases match.
2151 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
2155 emit_case_bit_tests (tree index_type, tree index_expr, tree minval,
2156 tree range, case_node_ptr nodes, rtx default_label)
2158 struct case_bit_test test[MAX_CASE_BIT_TESTS];
2159 enum machine_mode mode;
2160 rtx expr, index, label;
2161 unsigned int i,j,lo,hi;
2162 struct case_node *n;
2166 for (n = nodes; n; n = n->right)
2168 label = label_rtx (n->code_label);
2169 for (i = 0; i < count; i++)
2170 if (label == test[i].label)
2175 gcc_assert (count < MAX_CASE_BIT_TESTS);
2178 test[i].label = label;
2185 lo = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2186 n->low, minval), 1);
2187 hi = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2188 n->high, minval), 1);
2189 for (j = lo; j <= hi; j++)
2190 if (j >= HOST_BITS_PER_WIDE_INT)
2191 test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT);
2193 test[i].lo |= (HOST_WIDE_INT) 1 << j;
2196 qsort (test, count, sizeof(*test), case_bit_test_cmp);
2198 index_expr = fold_build2 (MINUS_EXPR, index_type,
2199 fold_convert (index_type, index_expr),
2200 fold_convert (index_type, minval));
2201 index = expand_normal (index_expr);
2202 do_pending_stack_adjust ();
2204 mode = TYPE_MODE (index_type);
2205 expr = expand_normal (range);
2207 emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
2210 index = convert_to_mode (word_mode, index, 0);
2211 index = expand_binop (word_mode, ashl_optab, const1_rtx,
2212 index, NULL_RTX, 1, OPTAB_WIDEN);
2214 for (i = 0; i < count; i++)
2216 expr = immed_double_const (test[i].lo, test[i].hi, word_mode);
2217 expr = expand_binop (word_mode, and_optab, index, expr,
2218 NULL_RTX, 1, OPTAB_WIDEN);
2219 emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX,
2220 word_mode, 1, test[i].label);
2224 emit_jump (default_label);
2228 #define HAVE_casesi 0
2231 #ifndef HAVE_tablejump
2232 #define HAVE_tablejump 0
2235 /* Terminate a case (Pascal/Ada) or switch (C) statement
2236 in which ORIG_INDEX is the expression to be tested.
2237 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
2238 type as given in the source before any compiler conversions.
2239 Generate the code to test it and jump to the right place. */
2242 expand_case (gimple stmt)
2244 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
2245 rtx default_label = 0;
2246 struct case_node *n;
2247 unsigned int count, uniq;
2253 rtx before_case, end, lab;
2255 tree index_expr = gimple_switch_index (stmt);
2256 tree index_type = TREE_TYPE (index_expr);
2257 int unsignedp = TYPE_UNSIGNED (index_type);
2259 /* The insn after which the case dispatch should finally
2260 be emitted. Zero for a dummy. */
2263 /* A list of case labels; it is first built as a list and it may then
2264 be rearranged into a nearly balanced binary tree. */
2265 struct case_node *case_list = 0;
2267 /* Label to jump to if no case matches. */
2268 tree default_label_decl = NULL_TREE;
2270 alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
2271 sizeof (struct case_node),
2274 do_pending_stack_adjust ();
2276 /* An ERROR_MARK occurs for various reasons including invalid data type. */
2277 if (index_type != error_mark_node)
2280 bitmap label_bitmap;
2283 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
2284 expressions being INTEGER_CST. */
2285 gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
2287 /* The default case, if ever taken, is the first element. */
2288 elt = gimple_switch_label (stmt, 0);
2289 if (!CASE_LOW (elt) && !CASE_HIGH (elt))
2291 default_label_decl = CASE_LABEL (elt);
2295 for (i = gimple_switch_num_labels (stmt) - 1; i >= stopi; --i)
2298 elt = gimple_switch_label (stmt, i);
2300 low = CASE_LOW (elt);
2302 high = CASE_HIGH (elt);
2304 /* Discard empty ranges. */
2305 if (high && tree_int_cst_lt (high, low))
2308 case_list = add_case_node (case_list, index_type, low, high,
2309 CASE_LABEL (elt), case_node_pool);
2313 before_case = start = get_last_insn ();
2314 if (default_label_decl)
2315 default_label = label_rtx (default_label_decl);
2317 /* Get upper and lower bounds of case values. */
2321 label_bitmap = BITMAP_ALLOC (NULL);
2322 for (n = case_list; n; n = n->right)
2324 /* Count the elements and track the largest and smallest
2325 of them (treating them as signed even if they are not). */
2333 if (tree_int_cst_lt (n->low, minval))
2335 if (tree_int_cst_lt (maxval, n->high))
2338 /* A range counts double, since it requires two compares. */
2339 if (! tree_int_cst_equal (n->low, n->high))
2342 /* If we have not seen this label yet, then increase the
2343 number of unique case node targets seen. */
2344 lab = label_rtx (n->code_label);
2345 if (bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab)))
2349 BITMAP_FREE (label_bitmap);
2351 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
2352 destination, such as one with a default case only. However,
2353 it doesn't remove cases that are out of range for the switch
2354 type, so we may still get a zero here. */
2358 emit_jump (default_label);
2359 free_alloc_pool (case_node_pool);
2363 /* Compute span of values. */
2364 range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
2366 /* Try implementing this switch statement by a short sequence of
2367 bit-wise comparisons. However, we let the binary-tree case
2368 below handle constant index expressions. */
2369 if (CASE_USE_BIT_TESTS
2370 && ! TREE_CONSTANT (index_expr)
2371 && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
2372 && compare_tree_int (range, 0) > 0
2373 && lshift_cheap_p ()
2374 && ((uniq == 1 && count >= 3)
2375 || (uniq == 2 && count >= 5)
2376 || (uniq == 3 && count >= 6)))
2378 /* Optimize the case where all the case values fit in a
2379 word without having to subtract MINVAL. In this case,
2380 we can optimize away the subtraction. */
2381 if (compare_tree_int (minval, 0) > 0
2382 && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
2384 minval = build_int_cst (index_type, 0);
2387 emit_case_bit_tests (index_type, index_expr, minval, range,
2388 case_list, default_label);
2391 /* If range of values is much bigger than number of values,
2392 make a sequence of conditional branches instead of a dispatch.
2393 If the switch-index is a constant, do it this way
2394 because we can optimize it. */
2396 else if (count < targetm.case_values_threshold ()
2397 || compare_tree_int (range,
2398 (optimize_insn_for_size_p () ? 3 : 10) * count) > 0
2399 /* RANGE may be signed, and really large ranges will show up
2400 as negative numbers. */
2401 || compare_tree_int (range, 0) < 0
2402 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
2405 || !flag_jump_tables
2406 || TREE_CONSTANT (index_expr)
2407 /* If neither casesi or tablejump is available, we can
2408 only go this way. */
2409 || (!HAVE_casesi && !HAVE_tablejump))
2411 index = expand_normal (index_expr);
2413 /* If the index is a short or char that we do not have
2414 an insn to handle comparisons directly, convert it to
2415 a full integer now, rather than letting each comparison
2416 generate the conversion. */
2418 if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
2419 && ! have_insn_for (COMPARE, GET_MODE (index)))
2421 enum machine_mode wider_mode;
2422 for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
2423 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2424 if (have_insn_for (COMPARE, wider_mode))
2426 index = convert_to_mode (wider_mode, index, unsignedp);
2431 do_pending_stack_adjust ();
2434 index = copy_to_reg (index);
2436 /* We generate a binary decision tree to select the
2437 appropriate target code. This is done as follows:
2439 The list of cases is rearranged into a binary tree,
2440 nearly optimal assuming equal probability for each case.
2442 The tree is transformed into RTL, eliminating
2443 redundant test conditions at the same time.
2445 If program flow could reach the end of the
2446 decision tree an unconditional jump to the
2447 default code is emitted. */
2449 use_cost_table = estimate_case_costs (case_list);
2450 balance_case_nodes (&case_list, NULL);
2451 emit_case_nodes (index, case_list, default_label, index_type);
2453 emit_jump (default_label);
2457 rtx fallback_label = label_rtx (case_list->code_label);
2458 table_label = gen_label_rtx ();
2459 if (! try_casesi (index_type, index_expr, minval, range,
2460 table_label, default_label, fallback_label))
2464 /* Index jumptables from zero for suitable values of
2465 minval to avoid a subtraction. */
2466 if (optimize_insn_for_speed_p ()
2467 && compare_tree_int (minval, 0) > 0
2468 && compare_tree_int (minval, 3) < 0)
2470 minval = build_int_cst (index_type, 0);
2474 ok = try_tablejump (index_type, index_expr, minval, range,
2475 table_label, default_label);
2479 /* Get table of labels to jump to, in order of case index. */
2481 ncases = tree_low_cst (range, 0) + 1;
2482 labelvec = XALLOCAVEC (rtx, ncases);
2483 memset (labelvec, 0, ncases * sizeof (rtx));
2485 for (n = case_list; n; n = n->right)
2487 /* Compute the low and high bounds relative to the minimum
2488 value since that should fit in a HOST_WIDE_INT while the
2489 actual values may not. */
2491 = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2492 n->low, minval), 1);
2493 HOST_WIDE_INT i_high
2494 = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2495 n->high, minval), 1);
2498 for (i = i_low; i <= i_high; i ++)
2500 = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
2503 /* Fill in the gaps with the default. We may have gaps at
2504 the beginning if we tried to avoid the minval subtraction,
2505 so substitute some label even if the default label was
2506 deemed unreachable. */
2508 default_label = fallback_label;
2509 for (i = 0; i < ncases; i++)
2510 if (labelvec[i] == 0)
2511 labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
2513 /* Output the table. */
2514 emit_label (table_label);
2516 if (CASE_VECTOR_PC_RELATIVE || flag_pic)
2517 emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
2518 gen_rtx_LABEL_REF (Pmode, table_label),
2519 gen_rtvec_v (ncases, labelvec),
2520 const0_rtx, const0_rtx));
2522 emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
2523 gen_rtvec_v (ncases, labelvec)));
2525 /* Record no drop-through after the table. */
2529 before_case = NEXT_INSN (before_case);
2530 end = get_last_insn ();
2531 reorder_insns (before_case, end, start);
2535 free_alloc_pool (case_node_pool);
2538 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */
2541 do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label,
2544 do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
2545 NULL_RTX, NULL_RTX, label, -1);
2548 /* Not all case values are encountered equally. This function
2549 uses a heuristic to weight case labels, in cases where that
2550 looks like a reasonable thing to do.
2552 Right now, all we try to guess is text, and we establish the
2555 chars above space: 16
2564 If we find any cases in the switch that are not either -1 or in the range
2565 of valid ASCII characters, or are control characters other than those
2566 commonly used with "\", don't treat this switch scanning text.
2568 Return 1 if these nodes are suitable for cost estimation, otherwise
2572 estimate_case_costs (case_node_ptr node)
2574 tree min_ascii = integer_minus_one_node;
2575 tree max_ascii = build_int_cst (TREE_TYPE (node->high), 127);
2579 /* If we haven't already made the cost table, make it now. Note that the
2580 lower bound of the table is -1, not zero. */
2582 if (! cost_table_initialized)
2584 cost_table_initialized = 1;
2586 for (i = 0; i < 128; i++)
2589 COST_TABLE (i) = 16;
2590 else if (ISPUNCT (i))
2592 else if (ISCNTRL (i))
2593 COST_TABLE (i) = -1;
2596 COST_TABLE (' ') = 8;
2597 COST_TABLE ('\t') = 4;
2598 COST_TABLE ('\0') = 4;
2599 COST_TABLE ('\n') = 2;
2600 COST_TABLE ('\f') = 1;
2601 COST_TABLE ('\v') = 1;
2602 COST_TABLE ('\b') = 1;
2605 /* See if all the case expressions look like text. It is text if the
2606 constant is >= -1 and the highest constant is <= 127. Do all comparisons
2607 as signed arithmetic since we don't want to ever access cost_table with a
2608 value less than -1. Also check that none of the constants in a range
2609 are strange control characters. */
2611 for (n = node; n; n = n->right)
2613 if (tree_int_cst_lt (n->low, min_ascii)
2614 || tree_int_cst_lt (max_ascii, n->high))
2617 for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low);
2618 i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++)
2619 if (COST_TABLE (i) < 0)
2623 /* All interesting values are within the range of interesting
2624 ASCII characters. */
2628 /* Take an ordered list of case nodes
2629 and transform them into a near optimal binary tree,
2630 on the assumption that any target code selection value is as
2631 likely as any other.
2633 The transformation is performed by splitting the ordered
2634 list into two equal sections plus a pivot. The parts are
2635 then attached to the pivot as left and right branches. Each
2636 branch is then transformed recursively. */
2639 balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
2652 /* Count the number of entries on branch. Also count the ranges. */
2656 if (!tree_int_cst_equal (np->low, np->high))
2660 cost += COST_TABLE (TREE_INT_CST_LOW (np->high));
2664 cost += COST_TABLE (TREE_INT_CST_LOW (np->low));
2672 /* Split this list if it is long enough for that to help. */
2677 /* Find the place in the list that bisects the list's total cost,
2678 Here I gets half the total cost. */
2683 /* Skip nodes while their cost does not reach that amount. */
2684 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
2685 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high));
2686 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low));
2689 npp = &(*npp)->right;
2694 /* Leave this branch lopsided, but optimize left-hand
2695 side and fill in `parent' fields for right-hand side. */
2697 np->parent = parent;
2698 balance_case_nodes (&np->left, np);
2699 for (; np->right; np = np->right)
2700 np->right->parent = np;
2704 /* If there are just three nodes, split at the middle one. */
2706 npp = &(*npp)->right;
2709 /* Find the place in the list that bisects the list's total cost,
2710 where ranges count as 2.
2711 Here I gets half the total cost. */
2712 i = (i + ranges + 1) / 2;
2715 /* Skip nodes while their cost does not reach that amount. */
2716 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
2721 npp = &(*npp)->right;
2726 np->parent = parent;
2729 /* Optimize each of the two split parts. */
2730 balance_case_nodes (&np->left, np);
2731 balance_case_nodes (&np->right, np);
2735 /* Else leave this branch as one level,
2736 but fill in `parent' fields. */
2738 np->parent = parent;
2739 for (; np->right; np = np->right)
2740 np->right->parent = np;
2745 /* Search the parent sections of the case node tree
2746 to see if a test for the lower bound of NODE would be redundant.
2747 INDEX_TYPE is the type of the index expression.
2749 The instructions to generate the case decision tree are
2750 output in the same order as nodes are processed so it is
2751 known that if a parent node checks the range of the current
2752 node minus one that the current node is bounded at its lower
2753 span. Thus the test would be redundant. */
2756 node_has_low_bound (case_node_ptr node, tree index_type)
2759 case_node_ptr pnode;
2761 /* If the lower bound of this node is the lowest value in the index type,
2762 we need not test it. */
2764 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
2767 /* If this node has a left branch, the value at the left must be less
2768 than that at this node, so it cannot be bounded at the bottom and
2769 we need not bother testing any further. */
2774 low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low),
2776 build_int_cst (TREE_TYPE (node->low), 1));
2778 /* If the subtraction above overflowed, we can't verify anything.
2779 Otherwise, look for a parent that tests our value - 1. */
2781 if (! tree_int_cst_lt (low_minus_one, node->low))
2784 for (pnode = node->parent; pnode; pnode = pnode->parent)
2785 if (tree_int_cst_equal (low_minus_one, pnode->high))
2791 /* Search the parent sections of the case node tree
2792 to see if a test for the upper bound of NODE would be redundant.
2793 INDEX_TYPE is the type of the index expression.
2795 The instructions to generate the case decision tree are
2796 output in the same order as nodes are processed so it is
2797 known that if a parent node checks the range of the current
2798 node plus one that the current node is bounded at its upper
2799 span. Thus the test would be redundant. */
2802 node_has_high_bound (case_node_ptr node, tree index_type)
2805 case_node_ptr pnode;
2807 /* If there is no upper bound, obviously no test is needed. */
2809 if (TYPE_MAX_VALUE (index_type) == NULL)
2812 /* If the upper bound of this node is the highest value in the type
2813 of the index expression, we need not test against it. */
2815 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
2818 /* If this node has a right branch, the value at the right must be greater
2819 than that at this node, so it cannot be bounded at the top and
2820 we need not bother testing any further. */
2825 high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high),
2827 build_int_cst (TREE_TYPE (node->high), 1));
2829 /* If the addition above overflowed, we can't verify anything.
2830 Otherwise, look for a parent that tests our value + 1. */
2832 if (! tree_int_cst_lt (node->high, high_plus_one))
2835 for (pnode = node->parent; pnode; pnode = pnode->parent)
2836 if (tree_int_cst_equal (high_plus_one, pnode->low))
2842 /* Search the parent sections of the
2843 case node tree to see if both tests for the upper and lower
2844 bounds of NODE would be redundant. */
2847 node_is_bounded (case_node_ptr node, tree index_type)
2849 return (node_has_low_bound (node, index_type)
2850 && node_has_high_bound (node, index_type));
2853 /* Emit step-by-step code to select a case for the value of INDEX.
2854 The thus generated decision tree follows the form of the
2855 case-node binary tree NODE, whose nodes represent test conditions.
2856 INDEX_TYPE is the type of the index of the switch.
2858 Care is taken to prune redundant tests from the decision tree
2859 by detecting any boundary conditions already checked by
2860 emitted rtx. (See node_has_high_bound, node_has_low_bound
2861 and node_is_bounded, above.)
2863 Where the test conditions can be shown to be redundant we emit
2864 an unconditional jump to the target code. As a further
2865 optimization, the subordinates of a tree node are examined to
2866 check for bounded nodes. In this case conditional and/or
2867 unconditional jumps as a result of the boundary check for the
2868 current node are arranged to target the subordinates associated
2869 code for out of bound conditions on the current node.
2871 We can assume that when control reaches the code generated here,
2872 the index value has already been compared with the parents
2873 of this node, and determined to be on the same side of each parent
2874 as this node is. Thus, if this node tests for the value 51,
2875 and a parent tested for 52, we don't need to consider
2876 the possibility of a value greater than 51. If another parent
2877 tests for the value 50, then this node need not test anything. */
2880 emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
2883 /* If INDEX has an unsigned type, we must make unsigned branches. */
2884 int unsignedp = TYPE_UNSIGNED (index_type);
2885 enum machine_mode mode = GET_MODE (index);
2886 enum machine_mode imode = TYPE_MODE (index_type);
2888 /* Handle indices detected as constant during RTL expansion. */
2889 if (mode == VOIDmode)
2892 /* See if our parents have already tested everything for us.
2893 If they have, emit an unconditional jump for this node. */
2894 if (node_is_bounded (node, index_type))
2895 emit_jump (label_rtx (node->code_label));
2897 else if (tree_int_cst_equal (node->low, node->high))
2899 /* Node is single valued. First see if the index expression matches
2900 this node and then check our children, if any. */
2902 do_jump_if_equal (mode, index,
2903 convert_modes (mode, imode,
2904 expand_normal (node->low),
2906 label_rtx (node->code_label), unsignedp);
2908 if (node->right != 0 && node->left != 0)
2910 /* This node has children on both sides.
2911 Dispatch to one side or the other
2912 by comparing the index value with this node's value.
2913 If one subtree is bounded, check that one first,
2914 so we can avoid real branches in the tree. */
2916 if (node_is_bounded (node->right, index_type))
2918 emit_cmp_and_jump_insns (index,
2921 expand_normal (node->high),
2923 GT, NULL_RTX, mode, unsignedp,
2924 label_rtx (node->right->code_label));
2925 emit_case_nodes (index, node->left, default_label, index_type);
2928 else if (node_is_bounded (node->left, index_type))
2930 emit_cmp_and_jump_insns (index,
2933 expand_normal (node->high),
2935 LT, NULL_RTX, mode, unsignedp,
2936 label_rtx (node->left->code_label));
2937 emit_case_nodes (index, node->right, default_label, index_type);
2940 /* If both children are single-valued cases with no
2941 children, finish up all the work. This way, we can save
2942 one ordered comparison. */
2943 else if (tree_int_cst_equal (node->right->low, node->right->high)
2944 && node->right->left == 0
2945 && node->right->right == 0
2946 && tree_int_cst_equal (node->left->low, node->left->high)
2947 && node->left->left == 0
2948 && node->left->right == 0)
2950 /* Neither node is bounded. First distinguish the two sides;
2951 then emit the code for one side at a time. */
2953 /* See if the value matches what the right hand side
2955 do_jump_if_equal (mode, index,
2956 convert_modes (mode, imode,
2957 expand_normal (node->right->low),
2959 label_rtx (node->right->code_label),
2962 /* See if the value matches what the left hand side
2964 do_jump_if_equal (mode, index,
2965 convert_modes (mode, imode,
2966 expand_normal (node->left->low),
2968 label_rtx (node->left->code_label),
2974 /* Neither node is bounded. First distinguish the two sides;
2975 then emit the code for one side at a time. */
2978 = build_decl (CURR_INSN_LOCATION,
2979 LABEL_DECL, NULL_TREE, NULL_TREE);
2981 /* See if the value is on the right. */
2982 emit_cmp_and_jump_insns (index,
2985 expand_normal (node->high),
2987 GT, NULL_RTX, mode, unsignedp,
2988 label_rtx (test_label));
2990 /* Value must be on the left.
2991 Handle the left-hand subtree. */
2992 emit_case_nodes (index, node->left, default_label, index_type);
2993 /* If left-hand subtree does nothing,
2996 emit_jump (default_label);
2998 /* Code branches here for the right-hand subtree. */
2999 expand_label (test_label);
3000 emit_case_nodes (index, node->right, default_label, index_type);
3004 else if (node->right != 0 && node->left == 0)
3006 /* Here we have a right child but no left so we issue a conditional
3007 branch to default and process the right child.
3009 Omit the conditional branch to default if the right child
3010 does not have any children and is single valued; it would
3011 cost too much space to save so little time. */
3013 if (node->right->right || node->right->left
3014 || !tree_int_cst_equal (node->right->low, node->right->high))
3016 if (!node_has_low_bound (node, index_type))
3018 emit_cmp_and_jump_insns (index,
3021 expand_normal (node->high),
3023 LT, NULL_RTX, mode, unsignedp,
3027 emit_case_nodes (index, node->right, default_label, index_type);
3030 /* We cannot process node->right normally
3031 since we haven't ruled out the numbers less than
3032 this node's value. So handle node->right explicitly. */
3033 do_jump_if_equal (mode, index,
3036 expand_normal (node->right->low),
3038 label_rtx (node->right->code_label), unsignedp);
3041 else if (node->right == 0 && node->left != 0)
3043 /* Just one subtree, on the left. */
3044 if (node->left->left || node->left->right
3045 || !tree_int_cst_equal (node->left->low, node->left->high))
3047 if (!node_has_high_bound (node, index_type))
3049 emit_cmp_and_jump_insns (index,
3052 expand_normal (node->high),
3054 GT, NULL_RTX, mode, unsignedp,
3058 emit_case_nodes (index, node->left, default_label, index_type);
3061 /* We cannot process node->left normally
3062 since we haven't ruled out the numbers less than
3063 this node's value. So handle node->left explicitly. */
3064 do_jump_if_equal (mode, index,
3067 expand_normal (node->left->low),
3069 label_rtx (node->left->code_label), unsignedp);
3074 /* Node is a range. These cases are very similar to those for a single
3075 value, except that we do not start by testing whether this node
3076 is the one to branch to. */
3078 if (node->right != 0 && node->left != 0)
3080 /* Node has subtrees on both sides.
3081 If the right-hand subtree is bounded,
3082 test for it first, since we can go straight there.
3083 Otherwise, we need to make a branch in the control structure,
3084 then handle the two subtrees. */
3085 tree test_label = 0;
3087 if (node_is_bounded (node->right, index_type))
3088 /* Right hand node is fully bounded so we can eliminate any
3089 testing and branch directly to the target code. */
3090 emit_cmp_and_jump_insns (index,
3093 expand_normal (node->high),
3095 GT, NULL_RTX, mode, unsignedp,
3096 label_rtx (node->right->code_label));
3099 /* Right hand node requires testing.
3100 Branch to a label where we will handle it later. */
3102 test_label = build_decl (CURR_INSN_LOCATION,
3103 LABEL_DECL, NULL_TREE, NULL_TREE);
3104 emit_cmp_and_jump_insns (index,
3107 expand_normal (node->high),
3109 GT, NULL_RTX, mode, unsignedp,
3110 label_rtx (test_label));
3113 /* Value belongs to this node or to the left-hand subtree. */
3115 emit_cmp_and_jump_insns (index,
3118 expand_normal (node->low),
3120 GE, NULL_RTX, mode, unsignedp,
3121 label_rtx (node->code_label));
3123 /* Handle the left-hand subtree. */
3124 emit_case_nodes (index, node->left, default_label, index_type);
3126 /* If right node had to be handled later, do that now. */
3130 /* If the left-hand subtree fell through,
3131 don't let it fall into the right-hand subtree. */
3133 emit_jump (default_label);
3135 expand_label (test_label);
3136 emit_case_nodes (index, node->right, default_label, index_type);
3140 else if (node->right != 0 && node->left == 0)
3142 /* Deal with values to the left of this node,
3143 if they are possible. */
3144 if (!node_has_low_bound (node, index_type))
3146 emit_cmp_and_jump_insns (index,
3149 expand_normal (node->low),
3151 LT, NULL_RTX, mode, unsignedp,
3155 /* Value belongs to this node or to the right-hand subtree. */
3157 emit_cmp_and_jump_insns (index,
3160 expand_normal (node->high),
3162 LE, NULL_RTX, mode, unsignedp,
3163 label_rtx (node->code_label));
3165 emit_case_nodes (index, node->right, default_label, index_type);
3168 else if (node->right == 0 && node->left != 0)
3170 /* Deal with values to the right of this node,
3171 if they are possible. */
3172 if (!node_has_high_bound (node, index_type))
3174 emit_cmp_and_jump_insns (index,
3177 expand_normal (node->high),
3179 GT, NULL_RTX, mode, unsignedp,
3183 /* Value belongs to this node or to the left-hand subtree. */
3185 emit_cmp_and_jump_insns (index,
3188 expand_normal (node->low),
3190 GE, NULL_RTX, mode, unsignedp,
3191 label_rtx (node->code_label));
3193 emit_case_nodes (index, node->left, default_label, index_type);
3198 /* Node has no children so we check low and high bounds to remove
3199 redundant tests. Only one of the bounds can exist,
3200 since otherwise this node is bounded--a case tested already. */
3201 int high_bound = node_has_high_bound (node, index_type);
3202 int low_bound = node_has_low_bound (node, index_type);
3204 if (!high_bound && low_bound)
3206 emit_cmp_and_jump_insns (index,
3209 expand_normal (node->high),
3211 GT, NULL_RTX, mode, unsignedp,
3215 else if (!low_bound && high_bound)
3217 emit_cmp_and_jump_insns (index,
3220 expand_normal (node->low),
3222 LT, NULL_RTX, mode, unsignedp,
3225 else if (!low_bound && !high_bound)
3227 /* Widen LOW and HIGH to the same width as INDEX. */
3228 tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
3229 tree low = build1 (CONVERT_EXPR, type, node->low);
3230 tree high = build1 (CONVERT_EXPR, type, node->high);
3231 rtx low_rtx, new_index, new_bound;
3233 /* Instead of doing two branches, emit one unsigned branch for
3234 (index-low) > (high-low). */
3235 low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL);
3236 new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
3237 NULL_RTX, unsignedp,
3239 new_bound = expand_expr (fold_build2 (MINUS_EXPR, type,
3241 NULL_RTX, mode, EXPAND_NORMAL);
3243 emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
3244 mode, 1, default_label);
3247 emit_jump (label_rtx (node->code_label));