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 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
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 It also creates the rtl expressions for parameters and auto variables
25 and has full responsibility for allocating stack slots.
27 The functions whose names start with `expand_' are called by the
28 parser to generate RTL instructions for various kinds of constructs.
30 Some control and binding constructs require calling several such
31 functions at different times. For example, a simple if-then
32 is expanded by calling `expand_start_cond' (with the condition-expression
33 as argument) before parsing the then-clause and calling `expand_end_cond'
34 after parsing the then-clause. */
38 #include "coretypes.h"
47 #include "insn-config.h"
50 #include "hard-reg-set.h"
57 #include "langhooks.h"
63 /* Functions and data structures for expanding case statements. */
65 /* Case label structure, used to hold info on labels within case
66 statements. We handle "range" labels; for a single-value label
67 as in C, the high and low limits are the same.
69 We start with a vector of case nodes sorted in ascending order, and
70 the default label as the last element in the vector. Before expanding
71 to RTL, we transform this vector into a list linked via the RIGHT
72 fields in the case_node struct. Nodes with higher case values are
75 Switch statements can be output in three forms. A branch table is
76 used if there are more than a few labels and the labels are dense
77 within the range between the smallest and largest case value. If a
78 branch table is used, no further manipulations are done with the case
81 The alternative to the use of a branch table is to generate a series
82 of compare and jump insns. When that is done, we use the LEFT, RIGHT,
83 and PARENT fields to hold a binary tree. Initially the tree is
84 totally unbalanced, with everything on the right. We balance the tree
85 with nodes on the left having lower case values than the parent
86 and nodes on the right having higher values. We then output the tree
89 For very small, suitable switch statements, we can generate a series
90 of simple bit test and branches instead. */
92 struct case_node GTY(())
94 struct case_node *left; /* Left son in binary tree */
95 struct case_node *right; /* Right son in binary tree; also node chain */
96 struct case_node *parent; /* Parent of node in binary tree */
97 tree low; /* Lowest index value for this label */
98 tree high; /* Highest index value for this label */
99 tree code_label; /* Label to jump to when node matches */
102 typedef struct case_node case_node;
103 typedef struct case_node *case_node_ptr;
105 /* These are used by estimate_case_costs and balance_case_nodes. */
107 /* This must be a signed type, and non-ANSI compilers lack signed char. */
108 static short cost_table_[129];
109 static int use_cost_table;
110 static int cost_table_initialized;
112 /* Special care is needed because we allow -1, but TREE_INT_CST_LOW
114 #define COST_TABLE(I) cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)]
116 /* Stack of control and binding constructs we are currently inside.
118 These constructs begin when you call `expand_start_WHATEVER'
119 and end when you call `expand_end_WHATEVER'. This stack records
120 info about how the construct began that tells the end-function
121 what to do. It also may provide information about the construct
122 to alter the behavior of other constructs within the body.
123 For example, they may affect the behavior of C `break' and `continue'.
125 Each construct gets one `struct nesting' object.
126 All of these objects are chained through the `all' field.
127 `nesting_stack' points to the first object (innermost construct).
128 The position of an entry on `nesting_stack' is in its `depth' field.
130 Each type of construct has its own individual stack.
131 For example, loops have `cond_stack'. Each object points to the
132 next object of the same type through the `next' field.
134 Some constructs are visible to `break' exit-statements and others
135 are not. Which constructs are visible depends on the language.
136 Therefore, the data structure allows each construct to be visible
137 or not, according to the args given when the construct is started.
138 The construct is visible if the `exit_label' field is non-null.
139 In that case, the value should be a CODE_LABEL rtx. */
141 struct nesting GTY(())
144 struct nesting *next;
154 /* For conds (if-then and if-then-else statements). */
157 /* Label for the end of the if construct.
158 There is none if EXITFLAG was not set
159 and no `else' has been seen yet. */
161 /* Label for the end of this alternative.
162 This may be the end of the if or the next else/elseif. */
164 } GTY ((tag ("COND_NESTING"))) cond;
165 /* For variable binding contours. */
168 /* Sequence number of this binding contour within the function,
169 in order of entry. */
170 int block_start_count;
171 /* The NOTE that starts this contour.
172 Used by expand_goto to check whether the destination
173 is within each contour or not. */
175 /* The saved target_temp_slot_level from our outer block.
176 We may reset target_temp_slot_level to be the level of
177 this block, if that is done, target_temp_slot_level
178 reverts to the saved target_temp_slot_level at the very
180 int block_target_temp_slot_level;
181 } GTY ((tag ("BLOCK_NESTING"))) block;
182 /* For switch (C) or case (Pascal) statements. */
185 /* The insn after which the case dispatch should finally
186 be emitted. Zero for a dummy. */
188 /* A list of case labels; it is first built as an AVL tree.
189 During expand_end_case, this is converted to a list, and may be
190 rearranged into a nearly balanced binary tree. */
191 struct case_node *case_list;
192 /* Label to jump to if no case matches. */
194 /* The expression to be dispatched on. */
196 } GTY ((tag ("CASE_NESTING"))) case_stmt;
197 } GTY ((desc ("%1.desc"))) data;
200 /* Allocate and return a new `struct nesting'. */
202 #define ALLOC_NESTING() ggc_alloc (sizeof (struct nesting))
204 /* Pop the nesting stack element by element until we pop off
205 the element which is at the top of STACK.
206 Update all the other stacks, popping off elements from them
207 as we pop them from nesting_stack. */
209 #define POPSTACK(STACK) \
210 do { struct nesting *target = STACK; \
211 struct nesting *this; \
212 do { this = nesting_stack; \
213 if (cond_stack == this) \
214 cond_stack = cond_stack->next; \
215 if (case_stack == this) \
216 case_stack = case_stack->next; \
217 nesting_depth = nesting_stack->depth - 1; \
218 nesting_stack = this->all; } \
219 while (this != target); } while (0)
222 struct stmt_status GTY(())
224 /* If any new stacks are added here, add them to POPSTACKS too. */
226 /* Chain of all pending conditional statements. */
227 struct nesting * x_cond_stack;
229 /* Chain of all pending case or switch statements. */
230 struct nesting * x_case_stack;
232 /* Separate chain including all of the above,
233 chained through the `all' field. */
234 struct nesting * x_nesting_stack;
236 /* Number of entries on nesting_stack now. */
239 /* Number of binding contours started so far in this function. */
240 int x_block_start_count;
242 /* Location of last line-number note, whether we actually
243 emitted it or not. */
244 location_t x_emit_locus;
247 #define cond_stack (cfun->stmt->x_cond_stack)
248 #define case_stack (cfun->stmt->x_case_stack)
249 #define nesting_stack (cfun->stmt->x_nesting_stack)
250 #define nesting_depth (cfun->stmt->x_nesting_depth)
251 #define current_block_start_count (cfun->stmt->x_block_start_count)
252 #define emit_locus (cfun->stmt->x_emit_locus)
254 static int n_occurrences (int, const char *);
255 static bool decl_conflicts_with_clobbers_p (tree, const HARD_REG_SET);
256 static void expand_nl_goto_receiver (void);
257 static bool check_operand_nalternatives (tree, tree);
258 static bool check_unique_operand_names (tree, tree);
259 static char *resolve_operand_name_1 (char *, tree, tree);
260 static void expand_null_return_1 (void);
261 static rtx shift_return_value (rtx);
262 static void expand_value_return (rtx);
263 static void do_jump_if_equal (rtx, rtx, rtx, int);
264 static int estimate_case_costs (case_node_ptr);
265 static bool same_case_target_p (rtx, rtx);
266 static bool lshift_cheap_p (void);
267 static int case_bit_test_cmp (const void *, const void *);
268 static void emit_case_bit_tests (tree, tree, tree, tree, case_node_ptr, rtx);
269 static void balance_case_nodes (case_node_ptr *, case_node_ptr);
270 static int node_has_low_bound (case_node_ptr, tree);
271 static int node_has_high_bound (case_node_ptr, tree);
272 static int node_is_bounded (case_node_ptr, tree);
273 static void emit_case_nodes (rtx, case_node_ptr, rtx, tree);
276 init_stmt_for_function (void)
278 cfun->stmt = ggc_alloc_cleared (sizeof (struct stmt_status));
281 /* Record the current file and line. Called from emit_line_note. */
284 set_file_and_line_for_stmt (location_t location)
286 /* If we're outputting an inline function, and we add a line note,
287 there may be no CFUN->STMT information. So, there's no need to
290 emit_locus = location;
293 /* Emit a no-op instruction. */
300 last_insn = get_last_insn ();
302 && (LABEL_P (last_insn)
303 || (NOTE_P (last_insn)
304 && prev_real_insn (last_insn) == 0)))
305 emit_insn (gen_nop ());
308 /* Return the rtx-label that corresponds to a LABEL_DECL,
309 creating it if necessary. */
312 label_rtx (tree label)
314 if (TREE_CODE (label) != LABEL_DECL)
317 if (!DECL_RTL_SET_P (label))
319 rtx r = gen_label_rtx ();
320 SET_DECL_RTL (label, r);
321 if (FORCED_LABEL (label) || DECL_NONLOCAL (label))
322 LABEL_PRESERVE_P (r) = 1;
325 return DECL_RTL (label);
328 /* As above, but also put it on the forced-reference list of the
329 function that contains it. */
331 force_label_rtx (tree label)
333 rtx ref = label_rtx (label);
334 tree function = decl_function_context (label);
340 if (function != current_function_decl)
341 p = find_function_data (function);
345 p->expr->x_forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref,
346 p->expr->x_forced_labels);
350 /* Add an unconditional jump to LABEL as the next sequential instruction. */
353 emit_jump (rtx label)
355 do_pending_stack_adjust ();
356 emit_jump_insn (gen_jump (label));
360 /* Emit code to jump to the address
361 specified by the pointer expression EXP. */
364 expand_computed_goto (tree exp)
366 rtx x = expand_expr (exp, NULL_RTX, VOIDmode, 0);
368 x = convert_memory_address (Pmode, x);
370 do_pending_stack_adjust ();
371 emit_indirect_jump (x);
374 /* Handle goto statements and the labels that they can go to. */
376 /* Specify the location in the RTL code of a label LABEL,
377 which is a LABEL_DECL tree node.
379 This is used for the kind of label that the user can jump to with a
380 goto statement, and for alternatives of a switch or case statement.
381 RTL labels generated for loops and conditionals don't go through here;
382 they are generated directly at the RTL level, by other functions below.
384 Note that this has nothing to do with defining label *names*.
385 Languages vary in how they do that and what that even means. */
388 expand_label (tree label)
390 rtx label_r = label_rtx (label);
392 do_pending_stack_adjust ();
393 emit_label (label_r);
394 if (DECL_NAME (label))
395 LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label));
397 if (DECL_NONLOCAL (label))
399 expand_nl_goto_receiver ();
400 nonlocal_goto_handler_labels
401 = gen_rtx_EXPR_LIST (VOIDmode, label_r,
402 nonlocal_goto_handler_labels);
405 if (FORCED_LABEL (label))
406 forced_labels = gen_rtx_EXPR_LIST (VOIDmode, label_r, forced_labels);
408 if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
409 maybe_set_first_label_num (label_r);
412 /* Generate RTL code for a `goto' statement with target label LABEL.
413 LABEL should be a LABEL_DECL tree node that was or will later be
414 defined with `expand_label'. */
417 expand_goto (tree label)
419 #ifdef ENABLE_CHECKING
420 /* Check for a nonlocal goto to a containing function. Should have
421 gotten translated to __builtin_nonlocal_goto. */
422 tree context = decl_function_context (label);
423 if (context != 0 && context != current_function_decl)
427 emit_jump (label_rtx (label));
430 /* Return the number of times character C occurs in string S. */
432 n_occurrences (int c, const char *s)
440 /* Generate RTL for an asm statement (explicit assembler code).
441 STRING is a STRING_CST node containing the assembler code text,
442 or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the
443 insn is volatile; don't optimize it. */
446 expand_asm (tree string, int vol)
450 if (TREE_CODE (string) == ADDR_EXPR)
451 string = TREE_OPERAND (string, 0);
453 body = gen_rtx_ASM_INPUT (VOIDmode, TREE_STRING_POINTER (string));
455 MEM_VOLATILE_P (body) = vol;
460 /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
461 OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
462 inputs and NOUTPUTS outputs to this extended-asm. Upon return,
463 *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
464 memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
465 constraint allows the use of a register operand. And, *IS_INOUT
466 will be true if the operand is read-write, i.e., if it is used as
467 an input as well as an output. If *CONSTRAINT_P is not in
468 canonical form, it will be made canonical. (Note that `+' will be
469 replaced with `=' as part of this process.)
471 Returns TRUE if all went well; FALSE if an error occurred. */
474 parse_output_constraint (const char **constraint_p, int operand_num,
475 int ninputs, int noutputs, bool *allows_mem,
476 bool *allows_reg, bool *is_inout)
478 const char *constraint = *constraint_p;
481 /* Assume the constraint doesn't allow the use of either a register
486 /* Allow the `=' or `+' to not be at the beginning of the string,
487 since it wasn't explicitly documented that way, and there is a
488 large body of code that puts it last. Swap the character to
489 the front, so as not to uglify any place else. */
490 p = strchr (constraint, '=');
492 p = strchr (constraint, '+');
494 /* If the string doesn't contain an `=', issue an error
498 error ("output operand constraint lacks `='");
502 /* If the constraint begins with `+', then the operand is both read
503 from and written to. */
504 *is_inout = (*p == '+');
506 /* Canonicalize the output constraint so that it begins with `='. */
507 if (p != constraint || is_inout)
510 size_t c_len = strlen (constraint);
513 warning ("output constraint `%c' for operand %d is not at the beginning",
516 /* Make a copy of the constraint. */
517 buf = alloca (c_len + 1);
518 strcpy (buf, constraint);
519 /* Swap the first character and the `=' or `+'. */
520 buf[p - constraint] = buf[0];
521 /* Make sure the first character is an `='. (Until we do this,
522 it might be a `+'.) */
524 /* Replace the constraint with the canonicalized string. */
525 *constraint_p = ggc_alloc_string (buf, c_len);
526 constraint = *constraint_p;
529 /* Loop through the constraint string. */
530 for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p))
535 error ("operand constraint contains incorrectly positioned '+' or '='");
539 if (operand_num + 1 == ninputs + noutputs)
541 error ("`%%' constraint used with last operand");
546 case 'V': case 'm': case 'o':
550 case '?': case '!': case '*': case '&': case '#':
551 case 'E': case 'F': case 'G': case 'H':
552 case 's': case 'i': case 'n':
553 case 'I': case 'J': case 'K': case 'L': case 'M':
554 case 'N': case 'O': case 'P': case ',':
557 case '0': case '1': case '2': case '3': case '4':
558 case '5': case '6': case '7': case '8': case '9':
560 error ("matching constraint not valid in output operand");
564 /* ??? Before flow, auto inc/dec insns are not supposed to exist,
565 excepting those that expand_call created. So match memory
582 if (REG_CLASS_FROM_CONSTRAINT (*p, p) != NO_REGS)
584 #ifdef EXTRA_CONSTRAINT_STR
585 else if (EXTRA_ADDRESS_CONSTRAINT (*p, p))
587 else if (EXTRA_MEMORY_CONSTRAINT (*p, p))
591 /* Otherwise we can't assume anything about the nature of
592 the constraint except that it isn't purely registers.
593 Treat it like "g" and hope for the best. */
604 /* Similar, but for input constraints. */
607 parse_input_constraint (const char **constraint_p, int input_num,
608 int ninputs, int noutputs, int ninout,
609 const char * const * constraints,
610 bool *allows_mem, bool *allows_reg)
612 const char *constraint = *constraint_p;
613 const char *orig_constraint = constraint;
614 size_t c_len = strlen (constraint);
616 bool saw_match = false;
618 /* Assume the constraint doesn't allow the use of either
619 a register or memory. */
623 /* Make sure constraint has neither `=', `+', nor '&'. */
625 for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
626 switch (constraint[j])
628 case '+': case '=': case '&':
629 if (constraint == orig_constraint)
631 error ("input operand constraint contains `%c'", constraint[j]);
637 if (constraint == orig_constraint
638 && input_num + 1 == ninputs - ninout)
640 error ("`%%' constraint used with last operand");
645 case 'V': case 'm': case 'o':
650 case '?': case '!': case '*': case '#':
651 case 'E': case 'F': case 'G': case 'H':
652 case 's': case 'i': case 'n':
653 case 'I': case 'J': case 'K': case 'L': case 'M':
654 case 'N': case 'O': case 'P': case ',':
657 /* Whether or not a numeric constraint allows a register is
658 decided by the matching constraint, and so there is no need
659 to do anything special with them. We must handle them in
660 the default case, so that we don't unnecessarily force
661 operands to memory. */
662 case '0': case '1': case '2': case '3': case '4':
663 case '5': case '6': case '7': case '8': case '9':
670 match = strtoul (constraint + j, &end, 10);
671 if (match >= (unsigned long) noutputs)
673 error ("matching constraint references invalid operand number");
677 /* Try and find the real constraint for this dup. Only do this
678 if the matching constraint is the only alternative. */
680 && (j == 0 || (j == 1 && constraint[0] == '%')))
682 constraint = constraints[match];
683 *constraint_p = constraint;
684 c_len = strlen (constraint);
686 /* ??? At the end of the loop, we will skip the first part of
687 the matched constraint. This assumes not only that the
688 other constraint is an output constraint, but also that
689 the '=' or '+' come first. */
693 j = end - constraint;
694 /* Anticipate increment at end of loop. */
709 if (! ISALPHA (constraint[j]))
711 error ("invalid punctuation `%c' in constraint", constraint[j]);
714 if (REG_CLASS_FROM_CONSTRAINT (constraint[j], constraint + j)
717 #ifdef EXTRA_CONSTRAINT_STR
718 else if (EXTRA_ADDRESS_CONSTRAINT (constraint[j], constraint + j))
720 else if (EXTRA_MEMORY_CONSTRAINT (constraint[j], constraint + j))
724 /* Otherwise we can't assume anything about the nature of
725 the constraint except that it isn't purely registers.
726 Treat it like "g" and hope for the best. */
734 if (saw_match && !*allows_reg)
735 warning ("matching constraint does not allow a register");
740 /* INPUT is one of the input operands from EXPR, an ASM_EXPR. Returns true
741 if it is an operand which must be passed in memory (i.e. an "m"
742 constraint), false otherwise. */
745 asm_op_is_mem_input (tree input, tree expr)
747 const char *constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (input)));
748 tree outputs = ASM_OUTPUTS (expr);
749 int noutputs = list_length (outputs);
750 const char **constraints
751 = (const char **) alloca ((noutputs) * sizeof (const char *));
753 bool allows_mem, allows_reg;
756 /* Collect output constraints. */
757 for (t = outputs; t ; t = TREE_CHAIN (t), i++)
758 constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
760 /* We pass 0 for input_num, ninputs and ninout; they are only used for
761 error checking which will be done at expand time. */
762 parse_input_constraint (&constraint, 0, 0, noutputs, 0, constraints,
763 &allows_mem, &allows_reg);
764 return (!allows_reg && allows_mem);
767 /* Check for overlap between registers marked in CLOBBERED_REGS and
768 anything inappropriate in DECL. Emit error and return TRUE for error,
772 decl_conflicts_with_clobbers_p (tree decl, const HARD_REG_SET clobbered_regs)
774 /* Conflicts between asm-declared register variables and the clobber
775 list are not allowed. */
776 if ((TREE_CODE (decl) == VAR_DECL || TREE_CODE (decl) == PARM_DECL)
777 && DECL_REGISTER (decl)
778 && REG_P (DECL_RTL (decl))
779 && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
781 rtx reg = DECL_RTL (decl);
784 for (regno = REGNO (reg);
786 + hard_regno_nregs[REGNO (reg)][GET_MODE (reg)]);
788 if (TEST_HARD_REG_BIT (clobbered_regs, regno))
790 error ("asm-specifier for variable `%s' conflicts with asm clobber list",
791 IDENTIFIER_POINTER (DECL_NAME (decl)));
793 /* Reset registerness to stop multiple errors emitted for a
795 DECL_REGISTER (decl) = 0;
802 /* Generate RTL for an asm statement with arguments.
803 STRING is the instruction template.
804 OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs.
805 Each output or input has an expression in the TREE_VALUE and
806 and a tree list in TREE_PURPOSE which in turn contains a constraint
807 name in TREE_VALUE (or NULL_TREE) and a constraint string
809 CLOBBERS is a list of STRING_CST nodes each naming a hard register
810 that is clobbered by this insn.
812 Not all kinds of lvalue that may appear in OUTPUTS can be stored directly.
813 Some elements of OUTPUTS may be replaced with trees representing temporary
814 values. The caller should copy those temporary values to the originally
817 VOL nonzero means the insn is volatile; don't optimize it. */
820 expand_asm_operands (tree string, tree outputs, tree inputs,
821 tree clobbers, int vol, location_t locus)
823 rtvec argvec, constraintvec;
825 int ninputs = list_length (inputs);
826 int noutputs = list_length (outputs);
829 HARD_REG_SET clobbered_regs;
830 int clobber_conflict_found = 0;
834 /* Vector of RTX's of evaluated output operands. */
835 rtx *output_rtx = alloca (noutputs * sizeof (rtx));
836 int *inout_opnum = alloca (noutputs * sizeof (int));
837 rtx *real_output_rtx = alloca (noutputs * sizeof (rtx));
838 enum machine_mode *inout_mode
839 = alloca (noutputs * sizeof (enum machine_mode));
840 const char **constraints
841 = alloca ((noutputs + ninputs) * sizeof (const char *));
842 int old_generating_concat_p = generating_concat_p;
844 /* An ASM with no outputs needs to be treated as volatile, for now. */
848 if (! check_operand_nalternatives (outputs, inputs))
851 string = resolve_asm_operand_names (string, outputs, inputs);
853 /* Collect constraints. */
855 for (t = outputs; t ; t = TREE_CHAIN (t), i++)
856 constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
857 for (t = inputs; t ; t = TREE_CHAIN (t), i++)
858 constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
860 /* Sometimes we wish to automatically clobber registers across an asm.
861 Case in point is when the i386 backend moved from cc0 to a hard reg --
862 maintaining source-level compatibility means automatically clobbering
863 the flags register. */
864 clobbers = targetm.md_asm_clobbers (clobbers);
866 /* Count the number of meaningful clobbered registers, ignoring what
867 we would ignore later. */
869 CLEAR_HARD_REG_SET (clobbered_regs);
870 for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
872 const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
874 i = decode_reg_name (regname);
875 if (i >= 0 || i == -4)
878 error ("unknown register name `%s' in `asm'", regname);
880 /* Mark clobbered registers. */
883 /* Clobbering the PIC register is an error */
884 if (i == (int) PIC_OFFSET_TABLE_REGNUM)
886 error ("PIC register `%s' clobbered in `asm'", regname);
890 SET_HARD_REG_BIT (clobbered_regs, i);
894 /* First pass over inputs and outputs checks validity and sets
895 mark_addressable if needed. */
898 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
900 tree val = TREE_VALUE (tail);
901 tree type = TREE_TYPE (val);
902 const char *constraint;
907 /* If there's an erroneous arg, emit no insn. */
908 if (type == error_mark_node)
911 /* Try to parse the output constraint. If that fails, there's
912 no point in going further. */
913 constraint = constraints[i];
914 if (!parse_output_constraint (&constraint, i, ninputs, noutputs,
915 &allows_mem, &allows_reg, &is_inout))
922 && REG_P (DECL_RTL (val))
923 && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))))
924 lang_hooks.mark_addressable (val);
931 if (ninputs + noutputs > MAX_RECOG_OPERANDS)
933 error ("more than %d operands in `asm'", MAX_RECOG_OPERANDS);
937 for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail))
939 bool allows_reg, allows_mem;
940 const char *constraint;
942 /* If there's an erroneous arg, emit no insn, because the ASM_INPUT
943 would get VOIDmode and that could cause a crash in reload. */
944 if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node)
947 constraint = constraints[i + noutputs];
948 if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
949 constraints, &allows_mem, &allows_reg))
952 if (! allows_reg && allows_mem)
953 lang_hooks.mark_addressable (TREE_VALUE (tail));
956 /* Second pass evaluates arguments. */
959 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
961 tree val = TREE_VALUE (tail);
962 tree type = TREE_TYPE (val);
968 if (!parse_output_constraint (&constraints[i], i, ninputs,
969 noutputs, &allows_mem, &allows_reg,
973 /* If an output operand is not a decl or indirect ref and our constraint
974 allows a register, make a temporary to act as an intermediate.
975 Make the asm insn write into that, then our caller will copy it to
976 the real output operand. Likewise for promoted variables. */
978 generating_concat_p = 0;
980 real_output_rtx[i] = NULL_RTX;
981 if ((TREE_CODE (val) == INDIRECT_REF
984 && (allows_mem || REG_P (DECL_RTL (val)))
985 && ! (REG_P (DECL_RTL (val))
986 && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))
990 op = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE);
992 op = validize_mem (op);
994 if (! allows_reg && !MEM_P (op))
995 error ("output number %d not directly addressable", i);
996 if ((! allows_mem && MEM_P (op))
997 || GET_CODE (op) == CONCAT)
999 real_output_rtx[i] = op;
1000 op = gen_reg_rtx (GET_MODE (op));
1002 emit_move_insn (op, real_output_rtx[i]);
1007 op = assign_temp (type, 0, 0, 1);
1008 op = validize_mem (op);
1009 TREE_VALUE (tail) = make_tree (type, op);
1013 generating_concat_p = old_generating_concat_p;
1017 inout_mode[ninout] = TYPE_MODE (type);
1018 inout_opnum[ninout++] = i;
1021 if (decl_conflicts_with_clobbers_p (val, clobbered_regs))
1022 clobber_conflict_found = 1;
1025 /* Make vectors for the expression-rtx, constraint strings,
1026 and named operands. */
1028 argvec = rtvec_alloc (ninputs);
1029 constraintvec = rtvec_alloc (ninputs);
1031 body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode
1032 : GET_MODE (output_rtx[0])),
1033 TREE_STRING_POINTER (string),
1034 empty_string, 0, argvec, constraintvec,
1037 MEM_VOLATILE_P (body) = vol;
1039 /* Eval the inputs and put them into ARGVEC.
1040 Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */
1042 for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i)
1044 bool allows_reg, allows_mem;
1045 const char *constraint;
1049 constraint = constraints[i + noutputs];
1050 if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
1051 constraints, &allows_mem, &allows_reg))
1054 generating_concat_p = 0;
1056 val = TREE_VALUE (tail);
1057 type = TREE_TYPE (val);
1058 op = expand_expr (val, NULL_RTX, VOIDmode,
1059 (allows_mem && !allows_reg
1060 ? EXPAND_MEMORY : EXPAND_NORMAL));
1062 /* Never pass a CONCAT to an ASM. */
1063 if (GET_CODE (op) == CONCAT)
1064 op = force_reg (GET_MODE (op), op);
1065 else if (MEM_P (op))
1066 op = validize_mem (op);
1068 if (asm_operand_ok (op, constraint) <= 0)
1071 op = force_reg (TYPE_MODE (type), op);
1072 else if (!allows_mem)
1073 warning ("asm operand %d probably doesn't match constraints",
1075 else if (MEM_P (op))
1077 /* We won't recognize either volatile memory or memory
1078 with a queued address as available a memory_operand
1079 at this point. Ignore it: clearly this *is* a memory. */
1083 warning ("use of memory input without lvalue in "
1084 "asm operand %d is deprecated", i + noutputs);
1086 if (CONSTANT_P (op))
1088 rtx mem = force_const_mem (TYPE_MODE (type), op);
1090 op = validize_mem (mem);
1092 op = force_reg (TYPE_MODE (type), op);
1095 || GET_CODE (op) == SUBREG
1096 || GET_CODE (op) == CONCAT)
1098 tree qual_type = build_qualified_type (type,
1100 | TYPE_QUAL_CONST));
1101 rtx memloc = assign_temp (qual_type, 1, 1, 1);
1102 memloc = validize_mem (memloc);
1103 emit_move_insn (memloc, op);
1109 generating_concat_p = old_generating_concat_p;
1110 ASM_OPERANDS_INPUT (body, i) = op;
1112 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i)
1113 = gen_rtx_ASM_INPUT (TYPE_MODE (type), constraints[i + noutputs]);
1115 if (decl_conflicts_with_clobbers_p (val, clobbered_regs))
1116 clobber_conflict_found = 1;
1119 /* Protect all the operands from the queue now that they have all been
1122 generating_concat_p = 0;
1124 /* For in-out operands, copy output rtx to input rtx. */
1125 for (i = 0; i < ninout; i++)
1127 int j = inout_opnum[i];
1130 ASM_OPERANDS_INPUT (body, ninputs - ninout + i)
1133 sprintf (buffer, "%d", j);
1134 ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i)
1135 = gen_rtx_ASM_INPUT (inout_mode[i], ggc_strdup (buffer));
1138 generating_concat_p = old_generating_concat_p;
1140 /* Now, for each output, construct an rtx
1141 (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER
1142 ARGVEC CONSTRAINTS OPNAMES))
1143 If there is more than one, put them inside a PARALLEL. */
1145 if (noutputs == 1 && nclobbers == 0)
1147 ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = constraints[0];
1148 emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body));
1151 else if (noutputs == 0 && nclobbers == 0)
1153 /* No output operands: put in a raw ASM_OPERANDS rtx. */
1165 body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers));
1167 /* For each output operand, store a SET. */
1168 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1170 XVECEXP (body, 0, i)
1171 = gen_rtx_SET (VOIDmode,
1173 gen_rtx_ASM_OPERANDS
1174 (GET_MODE (output_rtx[i]),
1175 TREE_STRING_POINTER (string),
1176 constraints[i], i, argvec, constraintvec,
1179 MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol;
1182 /* If there are no outputs (but there are some clobbers)
1183 store the bare ASM_OPERANDS into the PARALLEL. */
1186 XVECEXP (body, 0, i++) = obody;
1188 /* Store (clobber REG) for each clobbered register specified. */
1190 for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
1192 const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
1193 int j = decode_reg_name (regname);
1198 if (j == -3) /* `cc', which is not a register */
1201 if (j == -4) /* `memory', don't cache memory across asm */
1203 XVECEXP (body, 0, i++)
1204 = gen_rtx_CLOBBER (VOIDmode,
1207 gen_rtx_SCRATCH (VOIDmode)));
1211 /* Ignore unknown register, error already signaled. */
1215 /* Use QImode since that's guaranteed to clobber just one reg. */
1216 clobbered_reg = gen_rtx_REG (QImode, j);
1218 /* Do sanity check for overlap between clobbers and respectively
1219 input and outputs that hasn't been handled. Such overlap
1220 should have been detected and reported above. */
1221 if (!clobber_conflict_found)
1225 /* We test the old body (obody) contents to avoid tripping
1226 over the under-construction body. */
1227 for (opno = 0; opno < noutputs; opno++)
1228 if (reg_overlap_mentioned_p (clobbered_reg, output_rtx[opno]))
1229 internal_error ("asm clobber conflict with output operand");
1231 for (opno = 0; opno < ninputs - ninout; opno++)
1232 if (reg_overlap_mentioned_p (clobbered_reg,
1233 ASM_OPERANDS_INPUT (obody, opno)))
1234 internal_error ("asm clobber conflict with input operand");
1237 XVECEXP (body, 0, i++)
1238 = gen_rtx_CLOBBER (VOIDmode, clobbered_reg);
1244 /* For any outputs that needed reloading into registers, spill them
1245 back to where they belong. */
1246 for (i = 0; i < noutputs; ++i)
1247 if (real_output_rtx[i])
1248 emit_move_insn (real_output_rtx[i], output_rtx[i]);
1254 expand_asm_expr (tree exp)
1260 if (ASM_INPUT_P (exp))
1262 expand_asm (ASM_STRING (exp), ASM_VOLATILE_P (exp));
1266 outputs = ASM_OUTPUTS (exp);
1267 noutputs = list_length (outputs);
1268 /* o[I] is the place that output number I should be written. */
1269 o = (tree *) alloca (noutputs * sizeof (tree));
1271 /* Record the contents of OUTPUTS before it is modified. */
1272 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1273 o[i] = TREE_VALUE (tail);
1275 /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of
1276 OUTPUTS some trees for where the values were actually stored. */
1277 expand_asm_operands (ASM_STRING (exp), outputs, ASM_INPUTS (exp),
1278 ASM_CLOBBERS (exp), ASM_VOLATILE_P (exp),
1281 /* Copy all the intermediate outputs into the specified outputs. */
1282 for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1284 if (o[i] != TREE_VALUE (tail))
1286 expand_assignment (o[i], TREE_VALUE (tail), 0);
1289 /* Restore the original value so that it's correct the next
1290 time we expand this function. */
1291 TREE_VALUE (tail) = o[i];
1296 /* A subroutine of expand_asm_operands. Check that all operands have
1297 the same number of alternatives. Return true if so. */
1300 check_operand_nalternatives (tree outputs, tree inputs)
1302 if (outputs || inputs)
1304 tree tmp = TREE_PURPOSE (outputs ? outputs : inputs);
1306 = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp)));
1309 if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES)
1311 error ("too many alternatives in `asm'");
1318 const char *constraint
1319 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp)));
1321 if (n_occurrences (',', constraint) != nalternatives)
1323 error ("operand constraints for `asm' differ in number of alternatives");
1327 if (TREE_CHAIN (tmp))
1328 tmp = TREE_CHAIN (tmp);
1330 tmp = next, next = 0;
1337 /* A subroutine of expand_asm_operands. Check that all operand names
1338 are unique. Return true if so. We rely on the fact that these names
1339 are identifiers, and so have been canonicalized by get_identifier,
1340 so all we need are pointer comparisons. */
1343 check_unique_operand_names (tree outputs, tree inputs)
1347 for (i = outputs; i ; i = TREE_CHAIN (i))
1349 tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1353 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1354 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1358 for (i = inputs; i ; i = TREE_CHAIN (i))
1360 tree i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1364 for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1365 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1367 for (j = outputs; j ; j = TREE_CHAIN (j))
1368 if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1375 error ("duplicate asm operand name '%s'",
1376 TREE_STRING_POINTER (TREE_PURPOSE (TREE_PURPOSE (i))));
1380 /* A subroutine of expand_asm_operands. Resolve the names of the operands
1381 in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
1382 STRING and in the constraints to those numbers. */
1385 resolve_asm_operand_names (tree string, tree outputs, tree inputs)
1392 check_unique_operand_names (outputs, inputs);
1394 /* Substitute [<name>] in input constraint strings. There should be no
1395 named operands in output constraints. */
1396 for (t = inputs; t ; t = TREE_CHAIN (t))
1398 c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
1399 if (strchr (c, '[') != NULL)
1401 p = buffer = xstrdup (c);
1402 while ((p = strchr (p, '[')) != NULL)
1403 p = resolve_operand_name_1 (p, outputs, inputs);
1404 TREE_VALUE (TREE_PURPOSE (t))
1405 = build_string (strlen (buffer), buffer);
1410 /* Now check for any needed substitutions in the template. */
1411 c = TREE_STRING_POINTER (string);
1412 while ((c = strchr (c, '%')) != NULL)
1416 else if (ISALPHA (c[1]) && c[2] == '[')
1427 /* OK, we need to make a copy so we can perform the substitutions.
1428 Assume that we will not need extra space--we get to remove '['
1429 and ']', which means we cannot have a problem until we have more
1430 than 999 operands. */
1431 buffer = xstrdup (TREE_STRING_POINTER (string));
1432 p = buffer + (c - TREE_STRING_POINTER (string));
1434 while ((p = strchr (p, '%')) != NULL)
1438 else if (ISALPHA (p[1]) && p[2] == '[')
1446 p = resolve_operand_name_1 (p, outputs, inputs);
1449 string = build_string (strlen (buffer), buffer);
1456 /* A subroutine of resolve_operand_names. P points to the '[' for a
1457 potential named operand of the form [<name>]. In place, replace
1458 the name and brackets with a number. Return a pointer to the
1459 balance of the string after substitution. */
1462 resolve_operand_name_1 (char *p, tree outputs, tree inputs)
1469 /* Collect the operand name. */
1470 q = strchr (p, ']');
1473 error ("missing close brace for named operand");
1474 return strchr (p, '\0');
1478 /* Resolve the name to a number. */
1479 for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
1481 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1484 const char *c = TREE_STRING_POINTER (name);
1485 if (strncmp (c, p + 1, len) == 0 && c[len] == '\0')
1489 for (t = inputs; t ; t = TREE_CHAIN (t), op++)
1491 tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1494 const char *c = TREE_STRING_POINTER (name);
1495 if (strncmp (c, p + 1, len) == 0 && c[len] == '\0')
1501 error ("undefined named operand '%s'", p + 1);
1505 /* Replace the name with the number. Unfortunately, not all libraries
1506 get the return value of sprintf correct, so search for the end of the
1507 generated string by hand. */
1508 sprintf (p, "%d", op);
1509 p = strchr (p, '\0');
1511 /* Verify the no extra buffer space assumption. */
1515 /* Shift the rest of the buffer down to fill the gap. */
1516 memmove (p, q + 1, strlen (q + 1) + 1);
1521 /* Generate RTL to evaluate the expression EXP. */
1524 expand_expr_stmt (tree exp)
1529 value = expand_expr (exp, const0_rtx, VOIDmode, 0);
1530 type = TREE_TYPE (exp);
1532 /* If all we do is reference a volatile value in memory,
1533 copy it to a register to be sure it is actually touched. */
1534 if (value && MEM_P (value) && TREE_THIS_VOLATILE (exp))
1536 if (TYPE_MODE (type) == VOIDmode)
1538 else if (TYPE_MODE (type) != BLKmode)
1539 value = copy_to_reg (value);
1542 rtx lab = gen_label_rtx ();
1544 /* Compare the value with itself to reference it. */
1545 emit_cmp_and_jump_insns (value, value, EQ,
1546 expand_expr (TYPE_SIZE (type),
1547 NULL_RTX, VOIDmode, 0),
1553 /* Free any temporaries used to evaluate this expression. */
1557 /* Warn if EXP contains any computations whose results are not used.
1558 Return 1 if a warning is printed; 0 otherwise. LOCUS is the
1559 (potential) location of the expression. */
1562 warn_if_unused_value (tree exp, location_t locus)
1565 if (TREE_USED (exp))
1568 /* Don't warn about void constructs. This includes casting to void,
1569 void function calls, and statement expressions with a final cast
1571 if (VOID_TYPE_P (TREE_TYPE (exp)))
1574 if (EXPR_HAS_LOCATION (exp))
1575 locus = EXPR_LOCATION (exp);
1577 switch (TREE_CODE (exp))
1579 case PREINCREMENT_EXPR:
1580 case POSTINCREMENT_EXPR:
1581 case PREDECREMENT_EXPR:
1582 case POSTDECREMENT_EXPR:
1587 case TRY_CATCH_EXPR:
1588 case WITH_CLEANUP_EXPR:
1593 /* For a binding, warn if no side effect within it. */
1594 exp = BIND_EXPR_BODY (exp);
1598 exp = TREE_OPERAND (exp, 0);
1601 case TRUTH_ORIF_EXPR:
1602 case TRUTH_ANDIF_EXPR:
1603 /* In && or ||, warn if 2nd operand has no side effect. */
1604 exp = TREE_OPERAND (exp, 1);
1608 if (TREE_NO_WARNING (exp))
1610 if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus))
1612 /* Let people do `(foo (), 0)' without a warning. */
1613 if (TREE_CONSTANT (TREE_OPERAND (exp, 1)))
1615 exp = TREE_OPERAND (exp, 1);
1620 case NON_LVALUE_EXPR:
1621 /* Don't warn about conversions not explicit in the user's program. */
1622 if (TREE_NO_WARNING (exp))
1624 /* Assignment to a cast usually results in a cast of a modify.
1625 Don't complain about that. There can be an arbitrary number of
1626 casts before the modify, so we must loop until we find the first
1627 non-cast expression and then test to see if that is a modify. */
1629 tree tem = TREE_OPERAND (exp, 0);
1631 while (TREE_CODE (tem) == CONVERT_EXPR || TREE_CODE (tem) == NOP_EXPR)
1632 tem = TREE_OPERAND (tem, 0);
1634 if (TREE_CODE (tem) == MODIFY_EXPR || TREE_CODE (tem) == INIT_EXPR
1635 || TREE_CODE (tem) == CALL_EXPR)
1641 /* Don't warn about automatic dereferencing of references, since
1642 the user cannot control it. */
1643 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE)
1645 exp = TREE_OPERAND (exp, 0);
1651 /* Referencing a volatile value is a side effect, so don't warn. */
1653 || TREE_CODE_CLASS (TREE_CODE (exp)) == 'r')
1654 && TREE_THIS_VOLATILE (exp))
1657 /* If this is an expression which has no operands, there is no value
1658 to be unused. There are no such language-independent codes,
1659 but front ends may define such. */
1660 if (TREE_CODE_CLASS (TREE_CODE (exp)) == 'e'
1661 && TREE_CODE_LENGTH (TREE_CODE (exp)) == 0)
1665 /* If this is an expression with side effects, don't warn. */
1666 if (TREE_SIDE_EFFECTS (exp))
1669 warning ("%Hvalue computed is not used", &locus);
1674 /* Generate RTL for the start of an if-then. COND is the expression
1675 whose truth should be tested.
1677 If EXITFLAG is nonzero, this conditional is visible to
1678 `exit_something'. */
1681 expand_start_cond (tree cond, int exitflag)
1683 struct nesting *thiscond = ALLOC_NESTING ();
1685 /* Make an entry on cond_stack for the cond we are entering. */
1687 thiscond->desc = COND_NESTING;
1688 thiscond->next = cond_stack;
1689 thiscond->all = nesting_stack;
1690 thiscond->depth = ++nesting_depth;
1691 thiscond->data.cond.next_label = gen_label_rtx ();
1692 /* Before we encounter an `else', we don't need a separate exit label
1693 unless there are supposed to be exit statements
1694 to exit this conditional. */
1695 thiscond->exit_label = exitflag ? gen_label_rtx () : 0;
1696 thiscond->data.cond.endif_label = thiscond->exit_label;
1697 cond_stack = thiscond;
1698 nesting_stack = thiscond;
1700 do_jump (cond, thiscond->data.cond.next_label, NULL_RTX);
1703 /* Generate RTL between then-clause and the elseif-clause
1704 of an if-then-elseif-.... */
1707 expand_start_elseif (tree cond)
1709 if (cond_stack->data.cond.endif_label == 0)
1710 cond_stack->data.cond.endif_label = gen_label_rtx ();
1711 emit_jump (cond_stack->data.cond.endif_label);
1712 emit_label (cond_stack->data.cond.next_label);
1713 cond_stack->data.cond.next_label = gen_label_rtx ();
1714 do_jump (cond, cond_stack->data.cond.next_label, NULL_RTX);
1717 /* Generate RTL between the then-clause and the else-clause
1718 of an if-then-else. */
1721 expand_start_else (void)
1723 if (cond_stack->data.cond.endif_label == 0)
1724 cond_stack->data.cond.endif_label = gen_label_rtx ();
1726 emit_jump (cond_stack->data.cond.endif_label);
1727 emit_label (cond_stack->data.cond.next_label);
1728 cond_stack->data.cond.next_label = 0; /* No more _else or _elseif calls. */
1731 /* After calling expand_start_else, turn this "else" into an "else if"
1732 by providing another condition. */
1735 expand_elseif (tree cond)
1737 cond_stack->data.cond.next_label = gen_label_rtx ();
1738 do_jump (cond, cond_stack->data.cond.next_label, NULL_RTX);
1741 /* Generate RTL for the end of an if-then.
1742 Pop the record for it off of cond_stack. */
1745 expand_end_cond (void)
1747 struct nesting *thiscond = cond_stack;
1749 do_pending_stack_adjust ();
1750 if (thiscond->data.cond.next_label)
1751 emit_label (thiscond->data.cond.next_label);
1752 if (thiscond->data.cond.endif_label)
1753 emit_label (thiscond->data.cond.endif_label);
1755 POPSTACK (cond_stack);
1758 /* Return nonzero if we should preserve sub-expressions as separate
1759 pseudos. We never do so if we aren't optimizing. We always do so
1760 if -fexpensive-optimizations. */
1763 preserve_subexpressions_p (void)
1765 if (flag_expensive_optimizations)
1768 if (optimize == 0 || cfun == 0 || cfun->stmt == 0)
1775 /* Generate RTL to return from the current function, with no value.
1776 (That is, we do not do anything about returning any value.) */
1779 expand_null_return (void)
1781 /* If this function was declared to return a value, but we
1782 didn't, clobber the return registers so that they are not
1783 propagated live to the rest of the function. */
1784 clobber_return_register ();
1786 expand_null_return_1 ();
1789 /* Generate RTL to return directly from the current function.
1790 (That is, we bypass any return value.) */
1793 expand_naked_return (void)
1797 clear_pending_stack_adjust ();
1798 do_pending_stack_adjust ();
1800 end_label = naked_return_label;
1802 end_label = naked_return_label = gen_label_rtx ();
1804 emit_jump (end_label);
1807 /* If the current function returns values in the most significant part
1808 of a register, shift return value VAL appropriately. The mode of
1809 the function's return type is known not to be BLKmode. */
1812 shift_return_value (rtx val)
1816 type = TREE_TYPE (DECL_RESULT (current_function_decl));
1817 if (targetm.calls.return_in_msb (type))
1820 HOST_WIDE_INT shift;
1822 target = DECL_RTL (DECL_RESULT (current_function_decl));
1823 shift = (GET_MODE_BITSIZE (GET_MODE (target))
1824 - BITS_PER_UNIT * int_size_in_bytes (type));
1826 val = expand_shift (LSHIFT_EXPR, GET_MODE (target),
1827 gen_lowpart (GET_MODE (target), val),
1828 build_int_2 (shift, 0), target, 1);
1834 /* Generate RTL to return from the current function, with value VAL. */
1837 expand_value_return (rtx val)
1839 /* Copy the value to the return location
1840 unless it's already there. */
1842 rtx return_reg = DECL_RTL (DECL_RESULT (current_function_decl));
1843 if (return_reg != val)
1845 tree type = TREE_TYPE (DECL_RESULT (current_function_decl));
1846 if (targetm.calls.promote_function_return (TREE_TYPE (current_function_decl)))
1848 int unsignedp = TYPE_UNSIGNED (type);
1849 enum machine_mode old_mode
1850 = DECL_MODE (DECL_RESULT (current_function_decl));
1851 enum machine_mode mode
1852 = promote_mode (type, old_mode, &unsignedp, 1);
1854 if (mode != old_mode)
1855 val = convert_modes (mode, old_mode, val, unsignedp);
1857 if (GET_CODE (return_reg) == PARALLEL)
1858 emit_group_load (return_reg, val, type, int_size_in_bytes (type));
1860 emit_move_insn (return_reg, val);
1863 expand_null_return_1 ();
1866 /* Output a return with no value. */
1869 expand_null_return_1 (void)
1873 clear_pending_stack_adjust ();
1874 do_pending_stack_adjust ();
1876 end_label = return_label;
1878 end_label = return_label = gen_label_rtx ();
1879 emit_jump (end_label);
1882 /* Generate RTL to evaluate the expression RETVAL and return it
1883 from the current function. */
1886 expand_return (tree retval)
1892 /* If function wants no value, give it none. */
1893 if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE)
1895 expand_expr (retval, NULL_RTX, VOIDmode, 0);
1896 expand_null_return ();
1900 if (retval == error_mark_node)
1902 /* Treat this like a return of no value from a function that
1904 expand_null_return ();
1907 else if (TREE_CODE (retval) == RESULT_DECL)
1908 retval_rhs = retval;
1909 else if ((TREE_CODE (retval) == MODIFY_EXPR
1910 || TREE_CODE (retval) == INIT_EXPR)
1911 && TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL)
1912 retval_rhs = TREE_OPERAND (retval, 1);
1914 retval_rhs = retval;
1916 result_rtl = DECL_RTL (DECL_RESULT (current_function_decl));
1918 /* If the result is an aggregate that is being returned in one (or more)
1919 registers, load the registers here. The compiler currently can't handle
1920 copying a BLKmode value into registers. We could put this code in a
1921 more general area (for use by everyone instead of just function
1922 call/return), but until this feature is generally usable it is kept here
1923 (and in expand_call). */
1926 && TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode
1927 && REG_P (result_rtl))
1930 unsigned HOST_WIDE_INT bitpos, xbitpos;
1931 unsigned HOST_WIDE_INT padding_correction = 0;
1932 unsigned HOST_WIDE_INT bytes
1933 = int_size_in_bytes (TREE_TYPE (retval_rhs));
1934 int n_regs = (bytes + UNITS_PER_WORD - 1) / UNITS_PER_WORD;
1935 unsigned int bitsize
1936 = MIN (TYPE_ALIGN (TREE_TYPE (retval_rhs)), BITS_PER_WORD);
1937 rtx *result_pseudos = alloca (sizeof (rtx) * n_regs);
1938 rtx result_reg, src = NULL_RTX, dst = NULL_RTX;
1939 rtx result_val = expand_expr (retval_rhs, NULL_RTX, VOIDmode, 0);
1940 enum machine_mode tmpmode, result_reg_mode;
1944 expand_null_return ();
1948 /* If the structure doesn't take up a whole number of words, see
1949 whether the register value should be padded on the left or on
1950 the right. Set PADDING_CORRECTION to the number of padding
1951 bits needed on the left side.
1953 In most ABIs, the structure will be returned at the least end of
1954 the register, which translates to right padding on little-endian
1955 targets and left padding on big-endian targets. The opposite
1956 holds if the structure is returned at the most significant
1957 end of the register. */
1958 if (bytes % UNITS_PER_WORD != 0
1959 && (targetm.calls.return_in_msb (TREE_TYPE (retval_rhs))
1961 : BYTES_BIG_ENDIAN))
1962 padding_correction = (BITS_PER_WORD - ((bytes % UNITS_PER_WORD)
1965 /* Copy the structure BITSIZE bits at a time. */
1966 for (bitpos = 0, xbitpos = padding_correction;
1967 bitpos < bytes * BITS_PER_UNIT;
1968 bitpos += bitsize, xbitpos += bitsize)
1970 /* We need a new destination pseudo each time xbitpos is
1971 on a word boundary and when xbitpos == padding_correction
1972 (the first time through). */
1973 if (xbitpos % BITS_PER_WORD == 0
1974 || xbitpos == padding_correction)
1976 /* Generate an appropriate register. */
1977 dst = gen_reg_rtx (word_mode);
1978 result_pseudos[xbitpos / BITS_PER_WORD] = dst;
1980 /* Clear the destination before we move anything into it. */
1981 emit_move_insn (dst, CONST0_RTX (GET_MODE (dst)));
1984 /* We need a new source operand each time bitpos is on a word
1986 if (bitpos % BITS_PER_WORD == 0)
1987 src = operand_subword_force (result_val,
1988 bitpos / BITS_PER_WORD,
1991 /* Use bitpos for the source extraction (left justified) and
1992 xbitpos for the destination store (right justified). */
1993 store_bit_field (dst, bitsize, xbitpos % BITS_PER_WORD, word_mode,
1994 extract_bit_field (src, bitsize,
1995 bitpos % BITS_PER_WORD, 1,
1996 NULL_RTX, word_mode, word_mode));
1999 tmpmode = GET_MODE (result_rtl);
2000 if (tmpmode == BLKmode)
2002 /* Find the smallest integer mode large enough to hold the
2003 entire structure and use that mode instead of BLKmode
2004 on the USE insn for the return register. */
2005 for (tmpmode = GET_CLASS_NARROWEST_MODE (MODE_INT);
2006 tmpmode != VOIDmode;
2007 tmpmode = GET_MODE_WIDER_MODE (tmpmode))
2008 /* Have we found a large enough mode? */
2009 if (GET_MODE_SIZE (tmpmode) >= bytes)
2012 /* No suitable mode found. */
2013 if (tmpmode == VOIDmode)
2016 PUT_MODE (result_rtl, tmpmode);
2019 if (GET_MODE_SIZE (tmpmode) < GET_MODE_SIZE (word_mode))
2020 result_reg_mode = word_mode;
2022 result_reg_mode = tmpmode;
2023 result_reg = gen_reg_rtx (result_reg_mode);
2025 for (i = 0; i < n_regs; i++)
2026 emit_move_insn (operand_subword (result_reg, i, 0, result_reg_mode),
2029 if (tmpmode != result_reg_mode)
2030 result_reg = gen_lowpart (tmpmode, result_reg);
2032 expand_value_return (result_reg);
2034 else if (retval_rhs != 0
2035 && !VOID_TYPE_P (TREE_TYPE (retval_rhs))
2036 && (REG_P (result_rtl)
2037 || (GET_CODE (result_rtl) == PARALLEL)))
2039 /* Calculate the return value into a temporary (usually a pseudo
2041 tree ot = TREE_TYPE (DECL_RESULT (current_function_decl));
2042 tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST);
2044 val = assign_temp (nt, 0, 0, 1);
2045 val = expand_expr (retval_rhs, val, GET_MODE (val), 0);
2046 val = force_not_mem (val);
2047 /* Return the calculated value. */
2048 expand_value_return (shift_return_value (val));
2052 /* No hard reg used; calculate value into hard return reg. */
2053 expand_expr (retval, const0_rtx, VOIDmode, 0);
2054 expand_value_return (result_rtl);
2058 /* Given a pointer to a BLOCK node return nonzero if (and only if) the node
2059 in question represents the outermost pair of curly braces (i.e. the "body
2060 block") of a function or method.
2062 For any BLOCK node representing a "body block" of a function or method, the
2063 BLOCK_SUPERCONTEXT of the node will point to another BLOCK node which
2064 represents the outermost (function) scope for the function or method (i.e.
2065 the one which includes the formal parameters). The BLOCK_SUPERCONTEXT of
2066 *that* node in turn will point to the relevant FUNCTION_DECL node. */
2069 is_body_block (tree stmt)
2071 if (lang_hooks.no_body_blocks)
2074 if (TREE_CODE (stmt) == BLOCK)
2076 tree parent = BLOCK_SUPERCONTEXT (stmt);
2078 if (parent && TREE_CODE (parent) == BLOCK)
2080 tree grandparent = BLOCK_SUPERCONTEXT (parent);
2082 if (grandparent && TREE_CODE (grandparent) == FUNCTION_DECL)
2090 /* Emit code to restore vital registers at the beginning of a nonlocal goto
2093 expand_nl_goto_receiver (void)
2095 /* Clobber the FP when we get here, so we have to make sure it's
2096 marked as used by this function. */
2097 emit_insn (gen_rtx_USE (VOIDmode, hard_frame_pointer_rtx));
2099 /* Mark the static chain as clobbered here so life information
2100 doesn't get messed up for it. */
2101 emit_insn (gen_rtx_CLOBBER (VOIDmode, static_chain_rtx));
2103 #ifdef HAVE_nonlocal_goto
2104 if (! HAVE_nonlocal_goto)
2106 /* First adjust our frame pointer to its actual value. It was
2107 previously set to the start of the virtual area corresponding to
2108 the stacked variables when we branched here and now needs to be
2109 adjusted to the actual hardware fp value.
2111 Assignments are to virtual registers are converted by
2112 instantiate_virtual_regs into the corresponding assignment
2113 to the underlying register (fp in this case) that makes
2114 the original assignment true.
2115 So the following insn will actually be
2116 decrementing fp by STARTING_FRAME_OFFSET. */
2117 emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx);
2119 #if ARG_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2120 if (fixed_regs[ARG_POINTER_REGNUM])
2122 #ifdef ELIMINABLE_REGS
2123 /* If the argument pointer can be eliminated in favor of the
2124 frame pointer, we don't need to restore it. We assume here
2125 that if such an elimination is present, it can always be used.
2126 This is the case on all known machines; if we don't make this
2127 assumption, we do unnecessary saving on many machines. */
2128 static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS;
2131 for (i = 0; i < ARRAY_SIZE (elim_regs); i++)
2132 if (elim_regs[i].from == ARG_POINTER_REGNUM
2133 && elim_regs[i].to == HARD_FRAME_POINTER_REGNUM)
2136 if (i == ARRAY_SIZE (elim_regs))
2139 /* Now restore our arg pointer from the address at which it
2140 was saved in our stack frame. */
2141 emit_move_insn (virtual_incoming_args_rtx,
2142 copy_to_reg (get_arg_pointer_save_area (cfun)));
2147 #ifdef HAVE_nonlocal_goto_receiver
2148 if (HAVE_nonlocal_goto_receiver)
2149 emit_insn (gen_nonlocal_goto_receiver ());
2152 /* @@@ This is a kludge. Not all machine descriptions define a blockage
2153 insn, but we must not allow the code we just generated to be reordered
2154 by scheduling. Specifically, the update of the frame pointer must
2155 happen immediately, not later. So emit an ASM_INPUT to act as blockage
2157 emit_insn (gen_rtx_ASM_INPUT (VOIDmode, ""));
2160 /* Generate RTL for the automatic variable declaration DECL.
2161 (Other kinds of declarations are simply ignored if seen here.) */
2164 expand_decl (tree decl)
2168 type = TREE_TYPE (decl);
2170 /* For a CONST_DECL, set mode, alignment, and sizes from those of the
2171 type in case this node is used in a reference. */
2172 if (TREE_CODE (decl) == CONST_DECL)
2174 DECL_MODE (decl) = TYPE_MODE (type);
2175 DECL_ALIGN (decl) = TYPE_ALIGN (type);
2176 DECL_SIZE (decl) = TYPE_SIZE (type);
2177 DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type);
2181 /* Otherwise, only automatic variables need any expansion done. Static and
2182 external variables, and external functions, will be handled by
2183 `assemble_variable' (called from finish_decl). TYPE_DECL requires
2184 nothing. PARM_DECLs are handled in `assign_parms'. */
2185 if (TREE_CODE (decl) != VAR_DECL)
2188 if (TREE_STATIC (decl) || DECL_EXTERNAL (decl))
2191 /* Create the RTL representation for the variable. */
2193 if (type == error_mark_node)
2194 SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx));
2196 else if (DECL_SIZE (decl) == 0)
2197 /* Variable with incomplete type. */
2200 if (DECL_INITIAL (decl) == 0)
2201 /* Error message was already done; now avoid a crash. */
2202 x = gen_rtx_MEM (BLKmode, const0_rtx);
2204 /* An initializer is going to decide the size of this array.
2205 Until we know the size, represent its address with a reg. */
2206 x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode));
2208 set_mem_attributes (x, decl, 1);
2209 SET_DECL_RTL (decl, x);
2211 else if (use_register_for_decl (decl))
2213 /* Automatic variable that can go in a register. */
2214 int unsignedp = TYPE_UNSIGNED (type);
2215 enum machine_mode reg_mode
2216 = promote_mode (type, DECL_MODE (decl), &unsignedp, 0);
2218 SET_DECL_RTL (decl, gen_reg_rtx (reg_mode));
2220 /* Note if the object is a user variable. */
2221 if (!DECL_ARTIFICIAL (decl))
2223 mark_user_reg (DECL_RTL (decl));
2225 /* Trust user variables which have a pointer type to really
2226 be pointers. Do not trust compiler generated temporaries
2227 as our type system is totally busted as it relates to
2228 pointer arithmetic which translates into lots of compiler
2229 generated objects with pointer types, but which are not really
2231 if (POINTER_TYPE_P (type))
2232 mark_reg_pointer (DECL_RTL (decl),
2233 TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl))));
2236 maybe_set_unchanging (DECL_RTL (decl), decl);
2239 else if (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST
2240 && ! (flag_stack_check && ! STACK_CHECK_BUILTIN
2241 && 0 < compare_tree_int (DECL_SIZE_UNIT (decl),
2242 STACK_CHECK_MAX_VAR_SIZE)))
2244 /* Variable of fixed size that goes on the stack. */
2249 /* If we previously made RTL for this decl, it must be an array
2250 whose size was determined by the initializer.
2251 The old address was a register; set that register now
2252 to the proper address. */
2253 if (DECL_RTL_SET_P (decl))
2255 if (!MEM_P (DECL_RTL (decl))
2256 || !REG_P (XEXP (DECL_RTL (decl), 0)))
2258 oldaddr = XEXP (DECL_RTL (decl), 0);
2261 /* Set alignment we actually gave this decl. */
2262 DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT
2263 : GET_MODE_BITSIZE (DECL_MODE (decl)));
2264 DECL_USER_ALIGN (decl) = 0;
2266 x = assign_temp (decl, 1, 1, 1);
2267 set_mem_attributes (x, decl, 1);
2268 SET_DECL_RTL (decl, x);
2272 addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr);
2273 if (addr != oldaddr)
2274 emit_move_insn (oldaddr, addr);
2278 /* Dynamic-size object: must push space on the stack. */
2280 rtx address, size, x;
2282 /* Record the stack pointer on entry to block, if have
2283 not already done so. */
2284 do_pending_stack_adjust ();
2286 /* Compute the variable's size, in bytes. This will expand any
2287 needed SAVE_EXPRs for the first time. */
2288 size = expand_expr (DECL_SIZE_UNIT (decl), NULL_RTX, VOIDmode, 0);
2291 /* Allocate space on the stack for the variable. Note that
2292 DECL_ALIGN says how the variable is to be aligned and we
2293 cannot use it to conclude anything about the alignment of
2295 address = allocate_dynamic_stack_space (size, NULL_RTX,
2296 TYPE_ALIGN (TREE_TYPE (decl)));
2298 /* Reference the variable indirect through that rtx. */
2299 x = gen_rtx_MEM (DECL_MODE (decl), address);
2300 set_mem_attributes (x, decl, 1);
2301 SET_DECL_RTL (decl, x);
2304 /* Indicate the alignment we actually gave this variable. */
2305 #ifdef STACK_BOUNDARY
2306 DECL_ALIGN (decl) = STACK_BOUNDARY;
2308 DECL_ALIGN (decl) = BIGGEST_ALIGNMENT;
2310 DECL_USER_ALIGN (decl) = 0;
2314 /* Emit code to allocate T_SIZE bytes of dynamic stack space for ALLOC. */
2316 expand_stack_alloc (tree alloc, tree t_size)
2318 rtx address, dest, size;
2321 if (TREE_CODE (alloc) != ADDR_EXPR)
2323 var = TREE_OPERAND (alloc, 0);
2324 if (TREE_CODE (var) != VAR_DECL)
2327 type = TREE_TYPE (var);
2329 /* Compute the variable's size, in bytes. */
2330 size = expand_expr (t_size, NULL_RTX, VOIDmode, 0);
2333 /* Allocate space on the stack for the variable. */
2334 address = XEXP (DECL_RTL (var), 0);
2335 dest = allocate_dynamic_stack_space (size, address, TYPE_ALIGN (type));
2336 if (dest != address)
2337 emit_move_insn (address, dest);
2339 /* Indicate the alignment we actually gave this variable. */
2340 #ifdef STACK_BOUNDARY
2341 DECL_ALIGN (var) = STACK_BOUNDARY;
2343 DECL_ALIGN (var) = BIGGEST_ALIGNMENT;
2345 DECL_USER_ALIGN (var) = 0;
2348 /* Emit code to save the current value of stack. */
2350 expand_stack_save (void)
2354 do_pending_stack_adjust ();
2355 emit_stack_save (SAVE_BLOCK, &ret, NULL_RTX);
2359 /* Emit code to restore the current value of stack. */
2361 expand_stack_restore (tree var)
2363 rtx sa = DECL_RTL (var);
2365 emit_stack_restore (SAVE_BLOCK, sa, NULL_RTX);
2368 /* Emit code to perform the initialization of a declaration DECL. */
2371 expand_decl_init (tree decl)
2373 int was_used = TREE_USED (decl);
2375 /* If this is a CONST_DECL, we don't have to generate any code. Likewise
2376 for static decls. */
2377 if (TREE_CODE (decl) == CONST_DECL
2378 || TREE_STATIC (decl))
2381 /* Compute and store the initial value now. */
2385 if (DECL_INITIAL (decl) == error_mark_node)
2387 enum tree_code code = TREE_CODE (TREE_TYPE (decl));
2389 if (code == INTEGER_TYPE || code == REAL_TYPE || code == ENUMERAL_TYPE
2390 || code == POINTER_TYPE || code == REFERENCE_TYPE)
2391 expand_assignment (decl, convert (TREE_TYPE (decl), integer_zero_node),
2394 else if (DECL_INITIAL (decl) && TREE_CODE (DECL_INITIAL (decl)) != TREE_LIST)
2396 emit_line_note (DECL_SOURCE_LOCATION (decl));
2397 expand_assignment (decl, DECL_INITIAL (decl), 0);
2400 /* Don't let the initialization count as "using" the variable. */
2401 TREE_USED (decl) = was_used;
2403 /* Free any temporaries we made while initializing the decl. */
2404 preserve_temp_slots (NULL_RTX);
2410 /* DECL is an anonymous union. CLEANUP is a cleanup for DECL.
2411 DECL_ELTS is the list of elements that belong to DECL's type.
2412 In each, the TREE_VALUE is a VAR_DECL, and the TREE_PURPOSE a cleanup. */
2415 expand_anon_union_decl (tree decl, tree cleanup ATTRIBUTE_UNUSED,
2421 /* If any of the elements are addressable, so is the entire union. */
2422 for (t = decl_elts; t; t = TREE_CHAIN (t))
2423 if (TREE_ADDRESSABLE (TREE_VALUE (t)))
2425 TREE_ADDRESSABLE (decl) = 1;
2430 x = DECL_RTL (decl);
2432 /* Go through the elements, assigning RTL to each. */
2433 for (t = decl_elts; t; t = TREE_CHAIN (t))
2435 tree decl_elt = TREE_VALUE (t);
2436 enum machine_mode mode = TYPE_MODE (TREE_TYPE (decl_elt));
2438 /* If any of the elements are addressable, so is the entire
2440 if (TREE_USED (decl_elt))
2441 TREE_USED (decl) = 1;
2443 /* Propagate the union's alignment to the elements. */
2444 DECL_ALIGN (decl_elt) = DECL_ALIGN (decl);
2445 DECL_USER_ALIGN (decl_elt) = DECL_USER_ALIGN (decl);
2447 /* If the element has BLKmode and the union doesn't, the union is
2448 aligned such that the element doesn't need to have BLKmode, so
2449 change the element's mode to the appropriate one for its size. */
2450 if (mode == BLKmode && DECL_MODE (decl) != BLKmode)
2451 DECL_MODE (decl_elt) = mode
2452 = mode_for_size_tree (DECL_SIZE (decl_elt), MODE_INT, 1);
2454 /* (SUBREG (MEM ...)) at RTL generation time is invalid, so we
2455 instead create a new MEM rtx with the proper mode. */
2458 if (mode == GET_MODE (x))
2459 SET_DECL_RTL (decl_elt, x);
2461 SET_DECL_RTL (decl_elt, adjust_address_nv (x, mode, 0));
2465 if (mode == GET_MODE (x))
2466 SET_DECL_RTL (decl_elt, x);
2468 SET_DECL_RTL (decl_elt, gen_lowpart_SUBREG (mode, x));
2475 /* Enter a case (Pascal) or switch (C) statement.
2476 Push a block onto case_stack and nesting_stack
2477 to accumulate the case-labels that are seen
2478 and to record the labels generated for the statement.
2480 EXIT_FLAG is nonzero if `exit_something' should exit this case stmt.
2481 Otherwise, this construct is transparent for `exit_something'.
2483 EXPR is the index-expression to be dispatched on.
2484 TYPE is its nominal type. We could simply convert EXPR to this type,
2485 but instead we take short cuts. */
2488 expand_start_case (tree index_expr)
2490 struct nesting *thiscase = ALLOC_NESTING ();
2492 /* Make an entry on case_stack for the case we are entering. */
2494 thiscase->desc = CASE_NESTING;
2495 thiscase->next = case_stack;
2496 thiscase->all = nesting_stack;
2497 thiscase->depth = ++nesting_depth;
2498 thiscase->exit_label = 0;
2499 thiscase->data.case_stmt.case_list = 0;
2500 thiscase->data.case_stmt.index_expr = index_expr;
2501 thiscase->data.case_stmt.default_label = 0;
2502 case_stack = thiscase;
2503 nesting_stack = thiscase;
2505 do_pending_stack_adjust ();
2507 /* Make sure case_stmt.start points to something that won't
2508 need any transformation before expand_end_case. */
2509 if (!NOTE_P (get_last_insn ()))
2510 emit_note (NOTE_INSN_DELETED);
2512 thiscase->data.case_stmt.start = get_last_insn ();
2515 /* Do the insertion of a case label into
2516 case_stack->data.case_stmt.case_list. The labels are fed to us
2517 in descending order from the sorted vector of case labels used
2518 in the tree part of the middle end. So the list we construct is
2519 sorted in ascending order. */
2522 add_case_node (tree low, tree high, tree label)
2524 struct case_node *r;
2526 /* If there's no HIGH value, then this is not a case range; it's
2527 just a simple case label. But that's just a degenerate case
2529 If the bounds are equal, turn this into the one-value case. */
2530 if (!high || tree_int_cst_equal (low, high))
2533 /* Handle default labels specially. */
2536 #ifdef ENABLE_CHECKING
2537 if (case_stack->data.case_stmt.default_label != 0)
2540 case_stack->data.case_stmt.default_label = label;
2544 /* Add this label to the chain. */
2545 r = ggc_alloc (sizeof (struct case_node));
2548 r->code_label = label;
2549 r->parent = r->left = NULL;
2550 r->right = case_stack->data.case_stmt.case_list;
2551 case_stack->data.case_stmt.case_list = r;
2554 /* Maximum number of case bit tests. */
2555 #define MAX_CASE_BIT_TESTS 3
2557 /* By default, enable case bit tests on targets with ashlsi3. */
2558 #ifndef CASE_USE_BIT_TESTS
2559 #define CASE_USE_BIT_TESTS (ashl_optab->handlers[word_mode].insn_code \
2560 != CODE_FOR_nothing)
2564 /* A case_bit_test represents a set of case nodes that may be
2565 selected from using a bit-wise comparison. HI and LO hold
2566 the integer to be tested against, LABEL contains the label
2567 to jump to upon success and BITS counts the number of case
2568 nodes handled by this test, typically the number of bits
2571 struct case_bit_test
2579 /* Determine whether "1 << x" is relatively cheap in word_mode. */
2582 bool lshift_cheap_p (void)
2584 static bool init = false;
2585 static bool cheap = true;
2589 rtx reg = gen_rtx_REG (word_mode, 10000);
2590 int cost = rtx_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg), SET);
2591 cheap = cost < COSTS_N_INSNS (3);
2598 /* Comparison function for qsort to order bit tests by decreasing
2599 number of case nodes, i.e. the node with the most cases gets
2603 case_bit_test_cmp (const void *p1, const void *p2)
2605 const struct case_bit_test *d1 = p1;
2606 const struct case_bit_test *d2 = p2;
2608 return d2->bits - d1->bits;
2611 /* Expand a switch statement by a short sequence of bit-wise
2612 comparisons. "switch(x)" is effectively converted into
2613 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
2616 INDEX_EXPR is the value being switched on, which is of
2617 type INDEX_TYPE. MINVAL is the lowest case value of in
2618 the case nodes, of INDEX_TYPE type, and RANGE is highest
2619 value minus MINVAL, also of type INDEX_TYPE. NODES is
2620 the set of case nodes, and DEFAULT_LABEL is the label to
2621 branch to should none of the cases match.
2623 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
2627 emit_case_bit_tests (tree index_type, tree index_expr, tree minval,
2628 tree range, case_node_ptr nodes, rtx default_label)
2630 struct case_bit_test test[MAX_CASE_BIT_TESTS];
2631 enum machine_mode mode;
2632 rtx expr, index, label;
2633 unsigned int i,j,lo,hi;
2634 struct case_node *n;
2638 for (n = nodes; n; n = n->right)
2640 label = label_rtx (n->code_label);
2641 for (i = 0; i < count; i++)
2642 if (same_case_target_p (label, test[i].label))
2647 if (count >= MAX_CASE_BIT_TESTS)
2651 test[i].label = label;
2658 lo = tree_low_cst (fold (build (MINUS_EXPR, index_type,
2659 n->low, minval)), 1);
2660 hi = tree_low_cst (fold (build (MINUS_EXPR, index_type,
2661 n->high, minval)), 1);
2662 for (j = lo; j <= hi; j++)
2663 if (j >= HOST_BITS_PER_WIDE_INT)
2664 test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT);
2666 test[i].lo |= (HOST_WIDE_INT) 1 << j;
2669 qsort (test, count, sizeof(*test), case_bit_test_cmp);
2671 index_expr = fold (build (MINUS_EXPR, index_type,
2672 convert (index_type, index_expr),
2673 convert (index_type, minval)));
2674 index = expand_expr (index_expr, NULL_RTX, VOIDmode, 0);
2675 do_pending_stack_adjust ();
2677 mode = TYPE_MODE (index_type);
2678 expr = expand_expr (range, NULL_RTX, VOIDmode, 0);
2679 emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
2682 index = convert_to_mode (word_mode, index, 0);
2683 index = expand_binop (word_mode, ashl_optab, const1_rtx,
2684 index, NULL_RTX, 1, OPTAB_WIDEN);
2686 for (i = 0; i < count; i++)
2688 expr = immed_double_const (test[i].lo, test[i].hi, word_mode);
2689 expr = expand_binop (word_mode, and_optab, index, expr,
2690 NULL_RTX, 1, OPTAB_WIDEN);
2691 emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX,
2692 word_mode, 1, test[i].label);
2695 emit_jump (default_label);
2699 #define HAVE_casesi 0
2702 #ifndef HAVE_tablejump
2703 #define HAVE_tablejump 0
2706 /* Terminate a case (Pascal) or switch (C) statement
2707 in which ORIG_INDEX is the expression to be tested.
2708 If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
2709 type as given in the source before any compiler conversions.
2710 Generate the code to test it and jump to the right place. */
2713 expand_end_case_type (tree orig_index, tree orig_type)
2715 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
2716 rtx default_label = 0;
2717 struct case_node *n, *m;
2718 unsigned int count, uniq;
2724 rtx before_case, end, lab;
2725 struct nesting *thiscase = case_stack;
2726 tree index_expr, index_type;
2727 bool exit_done = false;
2730 /* Don't crash due to previous errors. */
2731 if (thiscase == NULL)
2734 index_expr = thiscase->data.case_stmt.index_expr;
2735 index_type = TREE_TYPE (index_expr);
2736 unsignedp = TYPE_UNSIGNED (index_type);
2737 if (orig_type == NULL)
2738 orig_type = TREE_TYPE (orig_index);
2740 do_pending_stack_adjust ();
2742 /* An ERROR_MARK occurs for various reasons including invalid data type. */
2743 if (index_type != error_mark_node)
2745 /* If we don't have a default-label, create one here,
2746 after the body of the switch. */
2747 if (thiscase->data.case_stmt.default_label == 0)
2749 thiscase->data.case_stmt.default_label
2750 = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
2751 /* Share the exit label if possible. */
2752 if (thiscase->exit_label)
2754 SET_DECL_RTL (thiscase->data.case_stmt.default_label,
2755 thiscase->exit_label);
2758 expand_label (thiscase->data.case_stmt.default_label);
2760 default_label = label_rtx (thiscase->data.case_stmt.default_label);
2762 before_case = get_last_insn ();
2764 /* Get upper and lower bounds of case values.
2765 Also convert all the case values to the index expr's data type. */
2769 for (n = thiscase->data.case_stmt.case_list; n; n = n->right)
2771 /* Check low and high label values are integers. */
2772 if (TREE_CODE (n->low) != INTEGER_CST)
2774 if (TREE_CODE (n->high) != INTEGER_CST)
2777 n->low = convert (index_type, n->low);
2778 n->high = convert (index_type, n->high);
2780 /* Count the elements and track the largest and smallest
2781 of them (treating them as signed even if they are not). */
2789 if (INT_CST_LT (n->low, minval))
2791 if (INT_CST_LT (maxval, n->high))
2794 /* A range counts double, since it requires two compares. */
2795 if (! tree_int_cst_equal (n->low, n->high))
2798 /* Count the number of unique case node targets. */
2800 lab = label_rtx (n->code_label);
2801 for (m = thiscase->data.case_stmt.case_list; m != n; m = m->right)
2802 if (same_case_target_p (label_rtx (m->code_label), lab))
2809 /* Compute span of values. */
2811 range = fold (build (MINUS_EXPR, index_type, maxval, minval));
2815 expand_expr (index_expr, const0_rtx, VOIDmode, 0);
2816 emit_jump (default_label);
2819 /* Try implementing this switch statement by a short sequence of
2820 bit-wise comparisons. However, we let the binary-tree case
2821 below handle constant index expressions. */
2822 else if (CASE_USE_BIT_TESTS
2823 && ! TREE_CONSTANT (index_expr)
2824 && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
2825 && compare_tree_int (range, 0) > 0
2826 && lshift_cheap_p ()
2827 && ((uniq == 1 && count >= 3)
2828 || (uniq == 2 && count >= 5)
2829 || (uniq == 3 && count >= 6)))
2831 /* Optimize the case where all the case values fit in a
2832 word without having to subtract MINVAL. In this case,
2833 we can optimize away the subtraction. */
2834 if (compare_tree_int (minval, 0) > 0
2835 && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
2837 minval = integer_zero_node;
2840 emit_case_bit_tests (index_type, index_expr, minval, range,
2841 thiscase->data.case_stmt.case_list,
2845 /* If range of values is much bigger than number of values,
2846 make a sequence of conditional branches instead of a dispatch.
2847 If the switch-index is a constant, do it this way
2848 because we can optimize it. */
2850 else if (count < case_values_threshold ()
2851 || compare_tree_int (range,
2852 (optimize_size ? 3 : 10) * count) > 0
2853 /* RANGE may be signed, and really large ranges will show up
2854 as negative numbers. */
2855 || compare_tree_int (range, 0) < 0
2856 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
2859 || TREE_CONSTANT (index_expr)
2860 /* If neither casesi or tablejump is available, we can
2861 only go this way. */
2862 || (!HAVE_casesi && !HAVE_tablejump))
2864 index = expand_expr (index_expr, NULL_RTX, VOIDmode, 0);
2866 /* If the index is a short or char that we do not have
2867 an insn to handle comparisons directly, convert it to
2868 a full integer now, rather than letting each comparison
2869 generate the conversion. */
2871 if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
2872 && ! have_insn_for (COMPARE, GET_MODE (index)))
2874 enum machine_mode wider_mode;
2875 for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
2876 wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2877 if (have_insn_for (COMPARE, wider_mode))
2879 index = convert_to_mode (wider_mode, index, unsignedp);
2884 do_pending_stack_adjust ();
2887 index = copy_to_reg (index);
2888 if (GET_CODE (index) == CONST_INT
2889 || TREE_CODE (index_expr) == INTEGER_CST)
2891 /* Make a tree node with the proper constant value
2892 if we don't already have one. */
2893 if (TREE_CODE (index_expr) != INTEGER_CST)
2896 = build_int_2 (INTVAL (index),
2897 unsignedp || INTVAL (index) >= 0 ? 0 : -1);
2898 index_expr = convert (index_type, index_expr);
2901 /* For constant index expressions we need only
2902 issue an unconditional branch to the appropriate
2903 target code. The job of removing any unreachable
2904 code is left to the optimization phase if the
2905 "-O" option is specified. */
2906 for (n = thiscase->data.case_stmt.case_list; n; n = n->right)
2907 if (! tree_int_cst_lt (index_expr, n->low)
2908 && ! tree_int_cst_lt (n->high, index_expr))
2912 emit_jump (label_rtx (n->code_label));
2914 emit_jump (default_label);
2918 /* If the index expression is not constant we generate
2919 a binary decision tree to select the appropriate
2920 target code. This is done as follows:
2922 The list of cases is rearranged into a binary tree,
2923 nearly optimal assuming equal probability for each case.
2925 The tree is transformed into RTL, eliminating
2926 redundant test conditions at the same time.
2928 If program flow could reach the end of the
2929 decision tree an unconditional jump to the
2930 default code is emitted. */
2933 = (TREE_CODE (orig_type) != ENUMERAL_TYPE
2934 && estimate_case_costs (thiscase->data.case_stmt.case_list));
2935 balance_case_nodes (&thiscase->data.case_stmt.case_list, NULL);
2936 emit_case_nodes (index, thiscase->data.case_stmt.case_list,
2937 default_label, index_type);
2938 emit_jump (default_label);
2943 table_label = gen_label_rtx ();
2944 if (! try_casesi (index_type, index_expr, minval, range,
2945 table_label, default_label))
2947 index_type = integer_type_node;
2949 /* Index jumptables from zero for suitable values of
2950 minval to avoid a subtraction. */
2952 && compare_tree_int (minval, 0) > 0
2953 && compare_tree_int (minval, 3) < 0)
2955 minval = integer_zero_node;
2959 if (! try_tablejump (index_type, index_expr, minval, range,
2960 table_label, default_label))
2964 /* Get table of labels to jump to, in order of case index. */
2966 ncases = tree_low_cst (range, 0) + 1;
2967 labelvec = alloca (ncases * sizeof (rtx));
2968 memset (labelvec, 0, ncases * sizeof (rtx));
2970 for (n = thiscase->data.case_stmt.case_list; n; n = n->right)
2972 /* Compute the low and high bounds relative to the minimum
2973 value since that should fit in a HOST_WIDE_INT while the
2974 actual values may not. */
2976 = tree_low_cst (fold (build (MINUS_EXPR, index_type,
2977 n->low, minval)), 1);
2978 HOST_WIDE_INT i_high
2979 = tree_low_cst (fold (build (MINUS_EXPR, index_type,
2980 n->high, minval)), 1);
2983 for (i = i_low; i <= i_high; i ++)
2985 = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
2988 /* Fill in the gaps with the default. */
2989 for (i = 0; i < ncases; i++)
2990 if (labelvec[i] == 0)
2991 labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
2993 /* Output the table. */
2994 emit_label (table_label);
2996 if (CASE_VECTOR_PC_RELATIVE || flag_pic)
2997 emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
2998 gen_rtx_LABEL_REF (Pmode, table_label),
2999 gen_rtvec_v (ncases, labelvec),
3000 const0_rtx, const0_rtx));
3002 emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
3003 gen_rtvec_v (ncases, labelvec)));
3005 /* If the case insn drops through the table,
3006 after the table we must jump to the default-label.
3007 Otherwise record no drop-through after the table. */
3008 #ifdef CASE_DROPS_THROUGH
3009 emit_jump (default_label);
3015 before_case = NEXT_INSN (before_case);
3016 end = get_last_insn ();
3017 if (squeeze_notes (&before_case, &end))
3019 reorder_insns (before_case, end,
3020 thiscase->data.case_stmt.start);
3023 if (thiscase->exit_label && !exit_done)
3024 emit_label (thiscase->exit_label);
3026 POPSTACK (case_stack);
3031 /* Generate code to jump to LABEL if OP1 and OP2 are equal. */
3034 do_jump_if_equal (rtx op1, rtx op2, rtx label, int unsignedp)
3036 if (GET_CODE (op1) == CONST_INT && GET_CODE (op2) == CONST_INT)
3042 emit_cmp_and_jump_insns (op1, op2, EQ, NULL_RTX,
3043 (GET_MODE (op1) == VOIDmode
3044 ? GET_MODE (op2) : GET_MODE (op1)),
3048 /* Not all case values are encountered equally. This function
3049 uses a heuristic to weight case labels, in cases where that
3050 looks like a reasonable thing to do.
3052 Right now, all we try to guess is text, and we establish the
3055 chars above space: 16
3064 If we find any cases in the switch that are not either -1 or in the range
3065 of valid ASCII characters, or are control characters other than those
3066 commonly used with "\", don't treat this switch scanning text.
3068 Return 1 if these nodes are suitable for cost estimation, otherwise
3072 estimate_case_costs (case_node_ptr node)
3074 tree min_ascii = integer_minus_one_node;
3075 tree max_ascii = convert (TREE_TYPE (node->high), build_int_2 (127, 0));
3079 /* If we haven't already made the cost table, make it now. Note that the
3080 lower bound of the table is -1, not zero. */
3082 if (! cost_table_initialized)
3084 cost_table_initialized = 1;
3086 for (i = 0; i < 128; i++)
3089 COST_TABLE (i) = 16;
3090 else if (ISPUNCT (i))
3092 else if (ISCNTRL (i))
3093 COST_TABLE (i) = -1;
3096 COST_TABLE (' ') = 8;
3097 COST_TABLE ('\t') = 4;
3098 COST_TABLE ('\0') = 4;
3099 COST_TABLE ('\n') = 2;
3100 COST_TABLE ('\f') = 1;
3101 COST_TABLE ('\v') = 1;
3102 COST_TABLE ('\b') = 1;
3105 /* See if all the case expressions look like text. It is text if the
3106 constant is >= -1 and the highest constant is <= 127. Do all comparisons
3107 as signed arithmetic since we don't want to ever access cost_table with a
3108 value less than -1. Also check that none of the constants in a range
3109 are strange control characters. */
3111 for (n = node; n; n = n->right)
3113 if ((INT_CST_LT (n->low, min_ascii)) || INT_CST_LT (max_ascii, n->high))
3116 for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low);
3117 i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++)
3118 if (COST_TABLE (i) < 0)
3122 /* All interesting values are within the range of interesting
3123 ASCII characters. */
3127 /* Determine whether two case labels branch to the same target.
3128 Since we now do tree optimizations, just comparing labels is
3132 same_case_target_p (rtx l1, rtx l2)
3137 /* Take an ordered list of case nodes
3138 and transform them into a near optimal binary tree,
3139 on the assumption that any target code selection value is as
3140 likely as any other.
3142 The transformation is performed by splitting the ordered
3143 list into two equal sections plus a pivot. The parts are
3144 then attached to the pivot as left and right branches. Each
3145 branch is then transformed recursively. */
3148 balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
3161 /* Count the number of entries on branch. Also count the ranges. */
3165 if (!tree_int_cst_equal (np->low, np->high))
3169 cost += COST_TABLE (TREE_INT_CST_LOW (np->high));
3173 cost += COST_TABLE (TREE_INT_CST_LOW (np->low));
3181 /* Split this list if it is long enough for that to help. */
3186 /* Find the place in the list that bisects the list's total cost,
3187 Here I gets half the total cost. */
3192 /* Skip nodes while their cost does not reach that amount. */
3193 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
3194 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high));
3195 i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low));
3198 npp = &(*npp)->right;
3203 /* Leave this branch lopsided, but optimize left-hand
3204 side and fill in `parent' fields for right-hand side. */
3206 np->parent = parent;
3207 balance_case_nodes (&np->left, np);
3208 for (; np->right; np = np->right)
3209 np->right->parent = np;
3213 /* If there are just three nodes, split at the middle one. */
3215 npp = &(*npp)->right;
3218 /* Find the place in the list that bisects the list's total cost,
3219 where ranges count as 2.
3220 Here I gets half the total cost. */
3221 i = (i + ranges + 1) / 2;
3224 /* Skip nodes while their cost does not reach that amount. */
3225 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
3230 npp = &(*npp)->right;
3235 np->parent = parent;
3238 /* Optimize each of the two split parts. */
3239 balance_case_nodes (&np->left, np);
3240 balance_case_nodes (&np->right, np);
3244 /* Else leave this branch as one level,
3245 but fill in `parent' fields. */
3247 np->parent = parent;
3248 for (; np->right; np = np->right)
3249 np->right->parent = np;
3254 /* Search the parent sections of the case node tree
3255 to see if a test for the lower bound of NODE would be redundant.
3256 INDEX_TYPE is the type of the index expression.
3258 The instructions to generate the case decision tree are
3259 output in the same order as nodes are processed so it is
3260 known that if a parent node checks the range of the current
3261 node minus one that the current node is bounded at its lower
3262 span. Thus the test would be redundant. */
3265 node_has_low_bound (case_node_ptr node, tree index_type)
3268 case_node_ptr pnode;
3270 /* If the lower bound of this node is the lowest value in the index type,
3271 we need not test it. */
3273 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
3276 /* If this node has a left branch, the value at the left must be less
3277 than that at this node, so it cannot be bounded at the bottom and
3278 we need not bother testing any further. */
3283 low_minus_one = fold (build (MINUS_EXPR, TREE_TYPE (node->low),
3284 node->low, integer_one_node));
3286 /* If the subtraction above overflowed, we can't verify anything.
3287 Otherwise, look for a parent that tests our value - 1. */
3289 if (! tree_int_cst_lt (low_minus_one, node->low))
3292 for (pnode = node->parent; pnode; pnode = pnode->parent)
3293 if (tree_int_cst_equal (low_minus_one, pnode->high))
3299 /* Search the parent sections of the case node tree
3300 to see if a test for the upper bound of NODE would be redundant.
3301 INDEX_TYPE is the type of the index expression.
3303 The instructions to generate the case decision tree are
3304 output in the same order as nodes are processed so it is
3305 known that if a parent node checks the range of the current
3306 node plus one that the current node is bounded at its upper
3307 span. Thus the test would be redundant. */
3310 node_has_high_bound (case_node_ptr node, tree index_type)
3313 case_node_ptr pnode;
3315 /* If there is no upper bound, obviously no test is needed. */
3317 if (TYPE_MAX_VALUE (index_type) == NULL)
3320 /* If the upper bound of this node is the highest value in the type
3321 of the index expression, we need not test against it. */
3323 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
3326 /* If this node has a right branch, the value at the right must be greater
3327 than that at this node, so it cannot be bounded at the top and
3328 we need not bother testing any further. */
3333 high_plus_one = fold (build (PLUS_EXPR, TREE_TYPE (node->high),
3334 node->high, integer_one_node));
3336 /* If the addition above overflowed, we can't verify anything.
3337 Otherwise, look for a parent that tests our value + 1. */
3339 if (! tree_int_cst_lt (node->high, high_plus_one))
3342 for (pnode = node->parent; pnode; pnode = pnode->parent)
3343 if (tree_int_cst_equal (high_plus_one, pnode->low))
3349 /* Search the parent sections of the
3350 case node tree to see if both tests for the upper and lower
3351 bounds of NODE would be redundant. */
3354 node_is_bounded (case_node_ptr node, tree index_type)
3356 return (node_has_low_bound (node, index_type)
3357 && node_has_high_bound (node, index_type));
3360 /* Emit step-by-step code to select a case for the value of INDEX.
3361 The thus generated decision tree follows the form of the
3362 case-node binary tree NODE, whose nodes represent test conditions.
3363 INDEX_TYPE is the type of the index of the switch.
3365 Care is taken to prune redundant tests from the decision tree
3366 by detecting any boundary conditions already checked by
3367 emitted rtx. (See node_has_high_bound, node_has_low_bound
3368 and node_is_bounded, above.)
3370 Where the test conditions can be shown to be redundant we emit
3371 an unconditional jump to the target code. As a further
3372 optimization, the subordinates of a tree node are examined to
3373 check for bounded nodes. In this case conditional and/or
3374 unconditional jumps as a result of the boundary check for the
3375 current node are arranged to target the subordinates associated
3376 code for out of bound conditions on the current node.
3378 We can assume that when control reaches the code generated here,
3379 the index value has already been compared with the parents
3380 of this node, and determined to be on the same side of each parent
3381 as this node is. Thus, if this node tests for the value 51,
3382 and a parent tested for 52, we don't need to consider
3383 the possibility of a value greater than 51. If another parent
3384 tests for the value 50, then this node need not test anything. */
3387 emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
3390 /* If INDEX has an unsigned type, we must make unsigned branches. */
3391 int unsignedp = TYPE_UNSIGNED (index_type);
3392 enum machine_mode mode = GET_MODE (index);
3393 enum machine_mode imode = TYPE_MODE (index_type);
3395 /* See if our parents have already tested everything for us.
3396 If they have, emit an unconditional jump for this node. */
3397 if (node_is_bounded (node, index_type))
3398 emit_jump (label_rtx (node->code_label));
3400 else if (tree_int_cst_equal (node->low, node->high))
3402 /* Node is single valued. First see if the index expression matches
3403 this node and then check our children, if any. */
3405 do_jump_if_equal (index,
3406 convert_modes (mode, imode,
3407 expand_expr (node->low, NULL_RTX,
3410 label_rtx (node->code_label), unsignedp);
3412 if (node->right != 0 && node->left != 0)
3414 /* This node has children on both sides.
3415 Dispatch to one side or the other
3416 by comparing the index value with this node's value.
3417 If one subtree is bounded, check that one first,
3418 so we can avoid real branches in the tree. */
3420 if (node_is_bounded (node->right, index_type))
3422 emit_cmp_and_jump_insns (index,
3425 expand_expr (node->high, NULL_RTX,
3428 GT, NULL_RTX, mode, unsignedp,
3429 label_rtx (node->right->code_label));
3430 emit_case_nodes (index, node->left, default_label, index_type);
3433 else if (node_is_bounded (node->left, index_type))
3435 emit_cmp_and_jump_insns (index,
3438 expand_expr (node->high, NULL_RTX,
3441 LT, NULL_RTX, mode, unsignedp,
3442 label_rtx (node->left->code_label));
3443 emit_case_nodes (index, node->right, default_label, index_type);
3446 /* If both children are single-valued cases with no
3447 children, finish up all the work. This way, we can save
3448 one ordered comparison. */
3449 else if (tree_int_cst_equal (node->right->low, node->right->high)
3450 && node->right->left == 0
3451 && node->right->right == 0
3452 && tree_int_cst_equal (node->left->low, node->left->high)
3453 && node->left->left == 0
3454 && node->left->right == 0)
3456 /* Neither node is bounded. First distinguish the two sides;
3457 then emit the code for one side at a time. */
3459 /* See if the value matches what the right hand side
3461 do_jump_if_equal (index,
3462 convert_modes (mode, imode,
3463 expand_expr (node->right->low,
3467 label_rtx (node->right->code_label),
3470 /* See if the value matches what the left hand side
3472 do_jump_if_equal (index,
3473 convert_modes (mode, imode,
3474 expand_expr (node->left->low,
3478 label_rtx (node->left->code_label),
3484 /* Neither node is bounded. First distinguish the two sides;
3485 then emit the code for one side at a time. */
3487 tree test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
3489 /* See if the value is on the right. */
3490 emit_cmp_and_jump_insns (index,
3493 expand_expr (node->high, NULL_RTX,
3496 GT, NULL_RTX, mode, unsignedp,
3497 label_rtx (test_label));
3499 /* Value must be on the left.
3500 Handle the left-hand subtree. */
3501 emit_case_nodes (index, node->left, default_label, index_type);
3502 /* If left-hand subtree does nothing,
3504 emit_jump (default_label);
3506 /* Code branches here for the right-hand subtree. */
3507 expand_label (test_label);
3508 emit_case_nodes (index, node->right, default_label, index_type);
3512 else if (node->right != 0 && node->left == 0)
3514 /* Here we have a right child but no left so we issue conditional
3515 branch to default and process the right child.
3517 Omit the conditional branch to default if we it avoid only one
3518 right child; it costs too much space to save so little time. */
3520 if (node->right->right || node->right->left
3521 || !tree_int_cst_equal (node->right->low, node->right->high))
3523 if (!node_has_low_bound (node, index_type))
3525 emit_cmp_and_jump_insns (index,
3528 expand_expr (node->high, NULL_RTX,
3531 LT, NULL_RTX, mode, unsignedp,
3535 emit_case_nodes (index, node->right, default_label, index_type);
3538 /* We cannot process node->right normally
3539 since we haven't ruled out the numbers less than
3540 this node's value. So handle node->right explicitly. */
3541 do_jump_if_equal (index,
3544 expand_expr (node->right->low, NULL_RTX,
3547 label_rtx (node->right->code_label), unsignedp);
3550 else if (node->right == 0 && node->left != 0)
3552 /* Just one subtree, on the left. */
3553 if (node->left->left || node->left->right
3554 || !tree_int_cst_equal (node->left->low, node->left->high))
3556 if (!node_has_high_bound (node, index_type))
3558 emit_cmp_and_jump_insns (index,
3561 expand_expr (node->high, NULL_RTX,
3564 GT, NULL_RTX, mode, unsignedp,
3568 emit_case_nodes (index, node->left, default_label, index_type);
3571 /* We cannot process node->left normally
3572 since we haven't ruled out the numbers less than
3573 this node's value. So handle node->left explicitly. */
3574 do_jump_if_equal (index,
3577 expand_expr (node->left->low, NULL_RTX,
3580 label_rtx (node->left->code_label), unsignedp);
3585 /* Node is a range. These cases are very similar to those for a single
3586 value, except that we do not start by testing whether this node
3587 is the one to branch to. */
3589 if (node->right != 0 && node->left != 0)
3591 /* Node has subtrees on both sides.
3592 If the right-hand subtree is bounded,
3593 test for it first, since we can go straight there.
3594 Otherwise, we need to make a branch in the control structure,
3595 then handle the two subtrees. */
3596 tree test_label = 0;
3598 if (node_is_bounded (node->right, index_type))
3599 /* Right hand node is fully bounded so we can eliminate any
3600 testing and branch directly to the target code. */
3601 emit_cmp_and_jump_insns (index,
3604 expand_expr (node->high, NULL_RTX,
3607 GT, NULL_RTX, mode, unsignedp,
3608 label_rtx (node->right->code_label));
3611 /* Right hand node requires testing.
3612 Branch to a label where we will handle it later. */
3614 test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
3615 emit_cmp_and_jump_insns (index,
3618 expand_expr (node->high, NULL_RTX,
3621 GT, NULL_RTX, mode, unsignedp,
3622 label_rtx (test_label));
3625 /* Value belongs to this node or to the left-hand subtree. */
3627 emit_cmp_and_jump_insns (index,
3630 expand_expr (node->low, NULL_RTX,
3633 GE, NULL_RTX, mode, unsignedp,
3634 label_rtx (node->code_label));
3636 /* Handle the left-hand subtree. */
3637 emit_case_nodes (index, node->left, default_label, index_type);
3639 /* If right node had to be handled later, do that now. */
3643 /* If the left-hand subtree fell through,
3644 don't let it fall into the right-hand subtree. */
3645 emit_jump (default_label);
3647 expand_label (test_label);
3648 emit_case_nodes (index, node->right, default_label, index_type);
3652 else if (node->right != 0 && node->left == 0)
3654 /* Deal with values to the left of this node,
3655 if they are possible. */
3656 if (!node_has_low_bound (node, index_type))
3658 emit_cmp_and_jump_insns (index,
3661 expand_expr (node->low, NULL_RTX,
3664 LT, NULL_RTX, mode, unsignedp,
3668 /* Value belongs to this node or to the right-hand subtree. */
3670 emit_cmp_and_jump_insns (index,
3673 expand_expr (node->high, NULL_RTX,
3676 LE, NULL_RTX, mode, unsignedp,
3677 label_rtx (node->code_label));
3679 emit_case_nodes (index, node->right, default_label, index_type);
3682 else if (node->right == 0 && node->left != 0)
3684 /* Deal with values to the right of this node,
3685 if they are possible. */
3686 if (!node_has_high_bound (node, index_type))
3688 emit_cmp_and_jump_insns (index,
3691 expand_expr (node->high, NULL_RTX,
3694 GT, NULL_RTX, mode, unsignedp,
3698 /* Value belongs to this node or to the left-hand subtree. */
3700 emit_cmp_and_jump_insns (index,
3703 expand_expr (node->low, NULL_RTX,
3706 GE, NULL_RTX, mode, unsignedp,
3707 label_rtx (node->code_label));
3709 emit_case_nodes (index, node->left, default_label, index_type);
3714 /* Node has no children so we check low and high bounds to remove
3715 redundant tests. Only one of the bounds can exist,
3716 since otherwise this node is bounded--a case tested already. */
3717 int high_bound = node_has_high_bound (node, index_type);
3718 int low_bound = node_has_low_bound (node, index_type);
3720 if (!high_bound && low_bound)
3722 emit_cmp_and_jump_insns (index,
3725 expand_expr (node->high, NULL_RTX,
3728 GT, NULL_RTX, mode, unsignedp,
3732 else if (!low_bound && high_bound)
3734 emit_cmp_and_jump_insns (index,
3737 expand_expr (node->low, NULL_RTX,
3740 LT, NULL_RTX, mode, unsignedp,
3743 else if (!low_bound && !high_bound)
3745 /* Widen LOW and HIGH to the same width as INDEX. */
3746 tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
3747 tree low = build1 (CONVERT_EXPR, type, node->low);
3748 tree high = build1 (CONVERT_EXPR, type, node->high);
3749 rtx low_rtx, new_index, new_bound;
3751 /* Instead of doing two branches, emit one unsigned branch for
3752 (index-low) > (high-low). */
3753 low_rtx = expand_expr (low, NULL_RTX, mode, 0);
3754 new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
3755 NULL_RTX, unsignedp,
3757 new_bound = expand_expr (fold (build (MINUS_EXPR, type,
3761 emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
3762 mode, 1, default_label);
3765 emit_jump (label_rtx (node->code_label));
3770 #include "gt-stmt.h"