1*e4b17023SJohn Marino /* Expands front end tree to back end RTL for GCC
2*e4b17023SJohn Marino Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
3*e4b17023SJohn Marino 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
4*e4b17023SJohn Marino 2010, 2011, 2012 Free Software Foundation, Inc.
5*e4b17023SJohn Marino
6*e4b17023SJohn Marino This file is part of GCC.
7*e4b17023SJohn Marino
8*e4b17023SJohn Marino GCC is free software; you can redistribute it and/or modify it under
9*e4b17023SJohn Marino the terms of the GNU General Public License as published by the Free
10*e4b17023SJohn Marino Software Foundation; either version 3, or (at your option) any later
11*e4b17023SJohn Marino version.
12*e4b17023SJohn Marino
13*e4b17023SJohn Marino GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14*e4b17023SJohn Marino WARRANTY; without even the implied warranty of MERCHANTABILITY or
15*e4b17023SJohn Marino FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16*e4b17023SJohn Marino for more details.
17*e4b17023SJohn Marino
18*e4b17023SJohn Marino You should have received a copy of the GNU General Public License
19*e4b17023SJohn Marino along with GCC; see the file COPYING3. If not see
20*e4b17023SJohn Marino <http://www.gnu.org/licenses/>. */
21*e4b17023SJohn Marino
22*e4b17023SJohn Marino /* This file handles the generation of rtl code from tree structure
23*e4b17023SJohn Marino above the level of expressions, using subroutines in exp*.c and emit-rtl.c.
24*e4b17023SJohn Marino The functions whose names start with `expand_' are called by the
25*e4b17023SJohn Marino expander to generate RTL instructions for various kinds of constructs. */
26*e4b17023SJohn Marino
27*e4b17023SJohn Marino #include "config.h"
28*e4b17023SJohn Marino #include "system.h"
29*e4b17023SJohn Marino #include "coretypes.h"
30*e4b17023SJohn Marino #include "tm.h"
31*e4b17023SJohn Marino
32*e4b17023SJohn Marino #include "rtl.h"
33*e4b17023SJohn Marino #include "hard-reg-set.h"
34*e4b17023SJohn Marino #include "tree.h"
35*e4b17023SJohn Marino #include "tm_p.h"
36*e4b17023SJohn Marino #include "flags.h"
37*e4b17023SJohn Marino #include "except.h"
38*e4b17023SJohn Marino #include "function.h"
39*e4b17023SJohn Marino #include "insn-config.h"
40*e4b17023SJohn Marino #include "expr.h"
41*e4b17023SJohn Marino #include "libfuncs.h"
42*e4b17023SJohn Marino #include "recog.h"
43*e4b17023SJohn Marino #include "machmode.h"
44*e4b17023SJohn Marino #include "diagnostic-core.h"
45*e4b17023SJohn Marino #include "output.h"
46*e4b17023SJohn Marino #include "ggc.h"
47*e4b17023SJohn Marino #include "langhooks.h"
48*e4b17023SJohn Marino #include "predict.h"
49*e4b17023SJohn Marino #include "optabs.h"
50*e4b17023SJohn Marino #include "target.h"
51*e4b17023SJohn Marino #include "gimple.h"
52*e4b17023SJohn Marino #include "regs.h"
53*e4b17023SJohn Marino #include "alloc-pool.h"
54*e4b17023SJohn Marino #include "pretty-print.h"
55*e4b17023SJohn Marino #include "bitmap.h"
56*e4b17023SJohn Marino #include "params.h"
57*e4b17023SJohn Marino
58*e4b17023SJohn Marino
59*e4b17023SJohn Marino /* Functions and data structures for expanding case statements. */
60*e4b17023SJohn Marino
61*e4b17023SJohn Marino /* Case label structure, used to hold info on labels within case
62*e4b17023SJohn Marino statements. We handle "range" labels; for a single-value label
63*e4b17023SJohn Marino as in C, the high and low limits are the same.
64*e4b17023SJohn Marino
65*e4b17023SJohn Marino We start with a vector of case nodes sorted in ascending order, and
66*e4b17023SJohn Marino the default label as the last element in the vector. Before expanding
67*e4b17023SJohn Marino to RTL, we transform this vector into a list linked via the RIGHT
68*e4b17023SJohn Marino fields in the case_node struct. Nodes with higher case values are
69*e4b17023SJohn Marino later in the list.
70*e4b17023SJohn Marino
71*e4b17023SJohn Marino Switch statements can be output in three forms. A branch table is
72*e4b17023SJohn Marino used if there are more than a few labels and the labels are dense
73*e4b17023SJohn Marino within the range between the smallest and largest case value. If a
74*e4b17023SJohn Marino branch table is used, no further manipulations are done with the case
75*e4b17023SJohn Marino node chain.
76*e4b17023SJohn Marino
77*e4b17023SJohn Marino The alternative to the use of a branch table is to generate a series
78*e4b17023SJohn Marino of compare and jump insns. When that is done, we use the LEFT, RIGHT,
79*e4b17023SJohn Marino and PARENT fields to hold a binary tree. Initially the tree is
80*e4b17023SJohn Marino totally unbalanced, with everything on the right. We balance the tree
81*e4b17023SJohn Marino with nodes on the left having lower case values than the parent
82*e4b17023SJohn Marino and nodes on the right having higher values. We then output the tree
83*e4b17023SJohn Marino in order.
84*e4b17023SJohn Marino
85*e4b17023SJohn Marino For very small, suitable switch statements, we can generate a series
86*e4b17023SJohn Marino of simple bit test and branches instead. */
87*e4b17023SJohn Marino
88*e4b17023SJohn Marino struct case_node
89*e4b17023SJohn Marino {
90*e4b17023SJohn Marino struct case_node *left; /* Left son in binary tree */
91*e4b17023SJohn Marino struct case_node *right; /* Right son in binary tree; also node chain */
92*e4b17023SJohn Marino struct case_node *parent; /* Parent of node in binary tree */
93*e4b17023SJohn Marino tree low; /* Lowest index value for this label */
94*e4b17023SJohn Marino tree high; /* Highest index value for this label */
95*e4b17023SJohn Marino tree code_label; /* Label to jump to when node matches */
96*e4b17023SJohn Marino };
97*e4b17023SJohn Marino
98*e4b17023SJohn Marino typedef struct case_node case_node;
99*e4b17023SJohn Marino typedef struct case_node *case_node_ptr;
100*e4b17023SJohn Marino
101*e4b17023SJohn Marino /* These are used by estimate_case_costs and balance_case_nodes. */
102*e4b17023SJohn Marino
103*e4b17023SJohn Marino /* This must be a signed type, and non-ANSI compilers lack signed char. */
104*e4b17023SJohn Marino static short cost_table_[129];
105*e4b17023SJohn Marino static int use_cost_table;
106*e4b17023SJohn Marino static int cost_table_initialized;
107*e4b17023SJohn Marino
108*e4b17023SJohn Marino /* Special care is needed because we allow -1, but TREE_INT_CST_LOW
109*e4b17023SJohn Marino is unsigned. */
110*e4b17023SJohn Marino #define COST_TABLE(I) cost_table_[(unsigned HOST_WIDE_INT) ((I) + 1)]
111*e4b17023SJohn Marino
112*e4b17023SJohn Marino static int n_occurrences (int, const char *);
113*e4b17023SJohn Marino static bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *);
114*e4b17023SJohn Marino static void expand_nl_goto_receiver (void);
115*e4b17023SJohn Marino static bool check_operand_nalternatives (tree, tree);
116*e4b17023SJohn Marino static bool check_unique_operand_names (tree, tree, tree);
117*e4b17023SJohn Marino static char *resolve_operand_name_1 (char *, tree, tree, tree);
118*e4b17023SJohn Marino static void expand_null_return_1 (void);
119*e4b17023SJohn Marino static void expand_value_return (rtx);
120*e4b17023SJohn Marino static int estimate_case_costs (case_node_ptr);
121*e4b17023SJohn Marino static bool lshift_cheap_p (void);
122*e4b17023SJohn Marino static int case_bit_test_cmp (const void *, const void *);
123*e4b17023SJohn Marino static void emit_case_bit_tests (tree, tree, tree, tree, case_node_ptr, rtx);
124*e4b17023SJohn Marino static void balance_case_nodes (case_node_ptr *, case_node_ptr);
125*e4b17023SJohn Marino static int node_has_low_bound (case_node_ptr, tree);
126*e4b17023SJohn Marino static int node_has_high_bound (case_node_ptr, tree);
127*e4b17023SJohn Marino static int node_is_bounded (case_node_ptr, tree);
128*e4b17023SJohn Marino static void emit_case_nodes (rtx, case_node_ptr, rtx, tree);
129*e4b17023SJohn Marino static struct case_node *add_case_node (struct case_node *, tree,
130*e4b17023SJohn Marino tree, tree, tree, alloc_pool);
131*e4b17023SJohn Marino
132*e4b17023SJohn Marino
133*e4b17023SJohn Marino /* Return the rtx-label that corresponds to a LABEL_DECL,
134*e4b17023SJohn Marino creating it if necessary. */
135*e4b17023SJohn Marino
136*e4b17023SJohn Marino rtx
label_rtx(tree label)137*e4b17023SJohn Marino label_rtx (tree label)
138*e4b17023SJohn Marino {
139*e4b17023SJohn Marino gcc_assert (TREE_CODE (label) == LABEL_DECL);
140*e4b17023SJohn Marino
141*e4b17023SJohn Marino if (!DECL_RTL_SET_P (label))
142*e4b17023SJohn Marino {
143*e4b17023SJohn Marino rtx r = gen_label_rtx ();
144*e4b17023SJohn Marino SET_DECL_RTL (label, r);
145*e4b17023SJohn Marino if (FORCED_LABEL (label) || DECL_NONLOCAL (label))
146*e4b17023SJohn Marino LABEL_PRESERVE_P (r) = 1;
147*e4b17023SJohn Marino }
148*e4b17023SJohn Marino
149*e4b17023SJohn Marino return DECL_RTL (label);
150*e4b17023SJohn Marino }
151*e4b17023SJohn Marino
152*e4b17023SJohn Marino /* As above, but also put it on the forced-reference list of the
153*e4b17023SJohn Marino function that contains it. */
154*e4b17023SJohn Marino rtx
force_label_rtx(tree label)155*e4b17023SJohn Marino force_label_rtx (tree label)
156*e4b17023SJohn Marino {
157*e4b17023SJohn Marino rtx ref = label_rtx (label);
158*e4b17023SJohn Marino tree function = decl_function_context (label);
159*e4b17023SJohn Marino
160*e4b17023SJohn Marino gcc_assert (function);
161*e4b17023SJohn Marino
162*e4b17023SJohn Marino forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref, forced_labels);
163*e4b17023SJohn Marino return ref;
164*e4b17023SJohn Marino }
165*e4b17023SJohn Marino
166*e4b17023SJohn Marino /* Add an unconditional jump to LABEL as the next sequential instruction. */
167*e4b17023SJohn Marino
168*e4b17023SJohn Marino void
emit_jump(rtx label)169*e4b17023SJohn Marino emit_jump (rtx label)
170*e4b17023SJohn Marino {
171*e4b17023SJohn Marino do_pending_stack_adjust ();
172*e4b17023SJohn Marino emit_jump_insn (gen_jump (label));
173*e4b17023SJohn Marino emit_barrier ();
174*e4b17023SJohn Marino }
175*e4b17023SJohn Marino
176*e4b17023SJohn Marino /* Emit code to jump to the address
177*e4b17023SJohn Marino specified by the pointer expression EXP. */
178*e4b17023SJohn Marino
179*e4b17023SJohn Marino void
expand_computed_goto(tree exp)180*e4b17023SJohn Marino expand_computed_goto (tree exp)
181*e4b17023SJohn Marino {
182*e4b17023SJohn Marino rtx x = expand_normal (exp);
183*e4b17023SJohn Marino
184*e4b17023SJohn Marino x = convert_memory_address (Pmode, x);
185*e4b17023SJohn Marino
186*e4b17023SJohn Marino do_pending_stack_adjust ();
187*e4b17023SJohn Marino emit_indirect_jump (x);
188*e4b17023SJohn Marino }
189*e4b17023SJohn Marino
190*e4b17023SJohn Marino /* Handle goto statements and the labels that they can go to. */
191*e4b17023SJohn Marino
192*e4b17023SJohn Marino /* Specify the location in the RTL code of a label LABEL,
193*e4b17023SJohn Marino which is a LABEL_DECL tree node.
194*e4b17023SJohn Marino
195*e4b17023SJohn Marino This is used for the kind of label that the user can jump to with a
196*e4b17023SJohn Marino goto statement, and for alternatives of a switch or case statement.
197*e4b17023SJohn Marino RTL labels generated for loops and conditionals don't go through here;
198*e4b17023SJohn Marino they are generated directly at the RTL level, by other functions below.
199*e4b17023SJohn Marino
200*e4b17023SJohn Marino Note that this has nothing to do with defining label *names*.
201*e4b17023SJohn Marino Languages vary in how they do that and what that even means. */
202*e4b17023SJohn Marino
203*e4b17023SJohn Marino void
expand_label(tree label)204*e4b17023SJohn Marino expand_label (tree label)
205*e4b17023SJohn Marino {
206*e4b17023SJohn Marino rtx label_r = label_rtx (label);
207*e4b17023SJohn Marino
208*e4b17023SJohn Marino do_pending_stack_adjust ();
209*e4b17023SJohn Marino emit_label (label_r);
210*e4b17023SJohn Marino if (DECL_NAME (label))
211*e4b17023SJohn Marino LABEL_NAME (DECL_RTL (label)) = IDENTIFIER_POINTER (DECL_NAME (label));
212*e4b17023SJohn Marino
213*e4b17023SJohn Marino if (DECL_NONLOCAL (label))
214*e4b17023SJohn Marino {
215*e4b17023SJohn Marino expand_nl_goto_receiver ();
216*e4b17023SJohn Marino nonlocal_goto_handler_labels
217*e4b17023SJohn Marino = gen_rtx_EXPR_LIST (VOIDmode, label_r,
218*e4b17023SJohn Marino nonlocal_goto_handler_labels);
219*e4b17023SJohn Marino }
220*e4b17023SJohn Marino
221*e4b17023SJohn Marino if (FORCED_LABEL (label))
222*e4b17023SJohn Marino forced_labels = gen_rtx_EXPR_LIST (VOIDmode, label_r, forced_labels);
223*e4b17023SJohn Marino
224*e4b17023SJohn Marino if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
225*e4b17023SJohn Marino maybe_set_first_label_num (label_r);
226*e4b17023SJohn Marino }
227*e4b17023SJohn Marino
228*e4b17023SJohn Marino /* Generate RTL code for a `goto' statement with target label LABEL.
229*e4b17023SJohn Marino LABEL should be a LABEL_DECL tree node that was or will later be
230*e4b17023SJohn Marino defined with `expand_label'. */
231*e4b17023SJohn Marino
232*e4b17023SJohn Marino void
expand_goto(tree label)233*e4b17023SJohn Marino expand_goto (tree label)
234*e4b17023SJohn Marino {
235*e4b17023SJohn Marino #ifdef ENABLE_CHECKING
236*e4b17023SJohn Marino /* Check for a nonlocal goto to a containing function. Should have
237*e4b17023SJohn Marino gotten translated to __builtin_nonlocal_goto. */
238*e4b17023SJohn Marino tree context = decl_function_context (label);
239*e4b17023SJohn Marino gcc_assert (!context || context == current_function_decl);
240*e4b17023SJohn Marino #endif
241*e4b17023SJohn Marino
242*e4b17023SJohn Marino emit_jump (label_rtx (label));
243*e4b17023SJohn Marino }
244*e4b17023SJohn Marino
245*e4b17023SJohn Marino /* Return the number of times character C occurs in string S. */
246*e4b17023SJohn Marino static int
n_occurrences(int c,const char * s)247*e4b17023SJohn Marino n_occurrences (int c, const char *s)
248*e4b17023SJohn Marino {
249*e4b17023SJohn Marino int n = 0;
250*e4b17023SJohn Marino while (*s)
251*e4b17023SJohn Marino n += (*s++ == c);
252*e4b17023SJohn Marino return n;
253*e4b17023SJohn Marino }
254*e4b17023SJohn Marino
255*e4b17023SJohn Marino /* Generate RTL for an asm statement (explicit assembler code).
256*e4b17023SJohn Marino STRING is a STRING_CST node containing the assembler code text,
257*e4b17023SJohn Marino or an ADDR_EXPR containing a STRING_CST. VOL nonzero means the
258*e4b17023SJohn Marino insn is volatile; don't optimize it. */
259*e4b17023SJohn Marino
260*e4b17023SJohn Marino static void
expand_asm_loc(tree string,int vol,location_t locus)261*e4b17023SJohn Marino expand_asm_loc (tree string, int vol, location_t locus)
262*e4b17023SJohn Marino {
263*e4b17023SJohn Marino rtx body;
264*e4b17023SJohn Marino
265*e4b17023SJohn Marino if (TREE_CODE (string) == ADDR_EXPR)
266*e4b17023SJohn Marino string = TREE_OPERAND (string, 0);
267*e4b17023SJohn Marino
268*e4b17023SJohn Marino body = gen_rtx_ASM_INPUT_loc (VOIDmode,
269*e4b17023SJohn Marino ggc_strdup (TREE_STRING_POINTER (string)),
270*e4b17023SJohn Marino locus);
271*e4b17023SJohn Marino
272*e4b17023SJohn Marino MEM_VOLATILE_P (body) = vol;
273*e4b17023SJohn Marino
274*e4b17023SJohn Marino emit_insn (body);
275*e4b17023SJohn Marino }
276*e4b17023SJohn Marino
277*e4b17023SJohn Marino /* Parse the output constraint pointed to by *CONSTRAINT_P. It is the
278*e4b17023SJohn Marino OPERAND_NUMth output operand, indexed from zero. There are NINPUTS
279*e4b17023SJohn Marino inputs and NOUTPUTS outputs to this extended-asm. Upon return,
280*e4b17023SJohn Marino *ALLOWS_MEM will be TRUE iff the constraint allows the use of a
281*e4b17023SJohn Marino memory operand. Similarly, *ALLOWS_REG will be TRUE iff the
282*e4b17023SJohn Marino constraint allows the use of a register operand. And, *IS_INOUT
283*e4b17023SJohn Marino will be true if the operand is read-write, i.e., if it is used as
284*e4b17023SJohn Marino an input as well as an output. If *CONSTRAINT_P is not in
285*e4b17023SJohn Marino canonical form, it will be made canonical. (Note that `+' will be
286*e4b17023SJohn Marino replaced with `=' as part of this process.)
287*e4b17023SJohn Marino
288*e4b17023SJohn Marino Returns TRUE if all went well; FALSE if an error occurred. */
289*e4b17023SJohn Marino
290*e4b17023SJohn Marino bool
parse_output_constraint(const char ** constraint_p,int operand_num,int ninputs,int noutputs,bool * allows_mem,bool * allows_reg,bool * is_inout)291*e4b17023SJohn Marino parse_output_constraint (const char **constraint_p, int operand_num,
292*e4b17023SJohn Marino int ninputs, int noutputs, bool *allows_mem,
293*e4b17023SJohn Marino bool *allows_reg, bool *is_inout)
294*e4b17023SJohn Marino {
295*e4b17023SJohn Marino const char *constraint = *constraint_p;
296*e4b17023SJohn Marino const char *p;
297*e4b17023SJohn Marino
298*e4b17023SJohn Marino /* Assume the constraint doesn't allow the use of either a register
299*e4b17023SJohn Marino or memory. */
300*e4b17023SJohn Marino *allows_mem = false;
301*e4b17023SJohn Marino *allows_reg = false;
302*e4b17023SJohn Marino
303*e4b17023SJohn Marino /* Allow the `=' or `+' to not be at the beginning of the string,
304*e4b17023SJohn Marino since it wasn't explicitly documented that way, and there is a
305*e4b17023SJohn Marino large body of code that puts it last. Swap the character to
306*e4b17023SJohn Marino the front, so as not to uglify any place else. */
307*e4b17023SJohn Marino p = strchr (constraint, '=');
308*e4b17023SJohn Marino if (!p)
309*e4b17023SJohn Marino p = strchr (constraint, '+');
310*e4b17023SJohn Marino
311*e4b17023SJohn Marino /* If the string doesn't contain an `=', issue an error
312*e4b17023SJohn Marino message. */
313*e4b17023SJohn Marino if (!p)
314*e4b17023SJohn Marino {
315*e4b17023SJohn Marino error ("output operand constraint lacks %<=%>");
316*e4b17023SJohn Marino return false;
317*e4b17023SJohn Marino }
318*e4b17023SJohn Marino
319*e4b17023SJohn Marino /* If the constraint begins with `+', then the operand is both read
320*e4b17023SJohn Marino from and written to. */
321*e4b17023SJohn Marino *is_inout = (*p == '+');
322*e4b17023SJohn Marino
323*e4b17023SJohn Marino /* Canonicalize the output constraint so that it begins with `='. */
324*e4b17023SJohn Marino if (p != constraint || *is_inout)
325*e4b17023SJohn Marino {
326*e4b17023SJohn Marino char *buf;
327*e4b17023SJohn Marino size_t c_len = strlen (constraint);
328*e4b17023SJohn Marino
329*e4b17023SJohn Marino if (p != constraint)
330*e4b17023SJohn Marino warning (0, "output constraint %qc for operand %d "
331*e4b17023SJohn Marino "is not at the beginning",
332*e4b17023SJohn Marino *p, operand_num);
333*e4b17023SJohn Marino
334*e4b17023SJohn Marino /* Make a copy of the constraint. */
335*e4b17023SJohn Marino buf = XALLOCAVEC (char, c_len + 1);
336*e4b17023SJohn Marino strcpy (buf, constraint);
337*e4b17023SJohn Marino /* Swap the first character and the `=' or `+'. */
338*e4b17023SJohn Marino buf[p - constraint] = buf[0];
339*e4b17023SJohn Marino /* Make sure the first character is an `='. (Until we do this,
340*e4b17023SJohn Marino it might be a `+'.) */
341*e4b17023SJohn Marino buf[0] = '=';
342*e4b17023SJohn Marino /* Replace the constraint with the canonicalized string. */
343*e4b17023SJohn Marino *constraint_p = ggc_alloc_string (buf, c_len);
344*e4b17023SJohn Marino constraint = *constraint_p;
345*e4b17023SJohn Marino }
346*e4b17023SJohn Marino
347*e4b17023SJohn Marino /* Loop through the constraint string. */
348*e4b17023SJohn Marino for (p = constraint + 1; *p; p += CONSTRAINT_LEN (*p, p))
349*e4b17023SJohn Marino switch (*p)
350*e4b17023SJohn Marino {
351*e4b17023SJohn Marino case '+':
352*e4b17023SJohn Marino case '=':
353*e4b17023SJohn Marino error ("operand constraint contains incorrectly positioned "
354*e4b17023SJohn Marino "%<+%> or %<=%>");
355*e4b17023SJohn Marino return false;
356*e4b17023SJohn Marino
357*e4b17023SJohn Marino case '%':
358*e4b17023SJohn Marino if (operand_num + 1 == ninputs + noutputs)
359*e4b17023SJohn Marino {
360*e4b17023SJohn Marino error ("%<%%%> constraint used with last operand");
361*e4b17023SJohn Marino return false;
362*e4b17023SJohn Marino }
363*e4b17023SJohn Marino break;
364*e4b17023SJohn Marino
365*e4b17023SJohn Marino case 'V': case TARGET_MEM_CONSTRAINT: case 'o':
366*e4b17023SJohn Marino *allows_mem = true;
367*e4b17023SJohn Marino break;
368*e4b17023SJohn Marino
369*e4b17023SJohn Marino case '?': case '!': case '*': case '&': case '#':
370*e4b17023SJohn Marino case 'E': case 'F': case 'G': case 'H':
371*e4b17023SJohn Marino case 's': case 'i': case 'n':
372*e4b17023SJohn Marino case 'I': case 'J': case 'K': case 'L': case 'M':
373*e4b17023SJohn Marino case 'N': case 'O': case 'P': case ',':
374*e4b17023SJohn Marino break;
375*e4b17023SJohn Marino
376*e4b17023SJohn Marino case '0': case '1': case '2': case '3': case '4':
377*e4b17023SJohn Marino case '5': case '6': case '7': case '8': case '9':
378*e4b17023SJohn Marino case '[':
379*e4b17023SJohn Marino error ("matching constraint not valid in output operand");
380*e4b17023SJohn Marino return false;
381*e4b17023SJohn Marino
382*e4b17023SJohn Marino case '<': case '>':
383*e4b17023SJohn Marino /* ??? Before flow, auto inc/dec insns are not supposed to exist,
384*e4b17023SJohn Marino excepting those that expand_call created. So match memory
385*e4b17023SJohn Marino and hope. */
386*e4b17023SJohn Marino *allows_mem = true;
387*e4b17023SJohn Marino break;
388*e4b17023SJohn Marino
389*e4b17023SJohn Marino case 'g': case 'X':
390*e4b17023SJohn Marino *allows_reg = true;
391*e4b17023SJohn Marino *allows_mem = true;
392*e4b17023SJohn Marino break;
393*e4b17023SJohn Marino
394*e4b17023SJohn Marino case 'p': case 'r':
395*e4b17023SJohn Marino *allows_reg = true;
396*e4b17023SJohn Marino break;
397*e4b17023SJohn Marino
398*e4b17023SJohn Marino default:
399*e4b17023SJohn Marino if (!ISALPHA (*p))
400*e4b17023SJohn Marino break;
401*e4b17023SJohn Marino if (REG_CLASS_FROM_CONSTRAINT (*p, p) != NO_REGS)
402*e4b17023SJohn Marino *allows_reg = true;
403*e4b17023SJohn Marino #ifdef EXTRA_CONSTRAINT_STR
404*e4b17023SJohn Marino else if (EXTRA_ADDRESS_CONSTRAINT (*p, p))
405*e4b17023SJohn Marino *allows_reg = true;
406*e4b17023SJohn Marino else if (EXTRA_MEMORY_CONSTRAINT (*p, p))
407*e4b17023SJohn Marino *allows_mem = true;
408*e4b17023SJohn Marino else
409*e4b17023SJohn Marino {
410*e4b17023SJohn Marino /* Otherwise we can't assume anything about the nature of
411*e4b17023SJohn Marino the constraint except that it isn't purely registers.
412*e4b17023SJohn Marino Treat it like "g" and hope for the best. */
413*e4b17023SJohn Marino *allows_reg = true;
414*e4b17023SJohn Marino *allows_mem = true;
415*e4b17023SJohn Marino }
416*e4b17023SJohn Marino #endif
417*e4b17023SJohn Marino break;
418*e4b17023SJohn Marino }
419*e4b17023SJohn Marino
420*e4b17023SJohn Marino return true;
421*e4b17023SJohn Marino }
422*e4b17023SJohn Marino
423*e4b17023SJohn Marino /* Similar, but for input constraints. */
424*e4b17023SJohn Marino
425*e4b17023SJohn Marino bool
parse_input_constraint(const char ** constraint_p,int input_num,int ninputs,int noutputs,int ninout,const char * const * constraints,bool * allows_mem,bool * allows_reg)426*e4b17023SJohn Marino parse_input_constraint (const char **constraint_p, int input_num,
427*e4b17023SJohn Marino int ninputs, int noutputs, int ninout,
428*e4b17023SJohn Marino const char * const * constraints,
429*e4b17023SJohn Marino bool *allows_mem, bool *allows_reg)
430*e4b17023SJohn Marino {
431*e4b17023SJohn Marino const char *constraint = *constraint_p;
432*e4b17023SJohn Marino const char *orig_constraint = constraint;
433*e4b17023SJohn Marino size_t c_len = strlen (constraint);
434*e4b17023SJohn Marino size_t j;
435*e4b17023SJohn Marino bool saw_match = false;
436*e4b17023SJohn Marino
437*e4b17023SJohn Marino /* Assume the constraint doesn't allow the use of either
438*e4b17023SJohn Marino a register or memory. */
439*e4b17023SJohn Marino *allows_mem = false;
440*e4b17023SJohn Marino *allows_reg = false;
441*e4b17023SJohn Marino
442*e4b17023SJohn Marino /* Make sure constraint has neither `=', `+', nor '&'. */
443*e4b17023SJohn Marino
444*e4b17023SJohn Marino for (j = 0; j < c_len; j += CONSTRAINT_LEN (constraint[j], constraint+j))
445*e4b17023SJohn Marino switch (constraint[j])
446*e4b17023SJohn Marino {
447*e4b17023SJohn Marino case '+': case '=': case '&':
448*e4b17023SJohn Marino if (constraint == orig_constraint)
449*e4b17023SJohn Marino {
450*e4b17023SJohn Marino error ("input operand constraint contains %qc", constraint[j]);
451*e4b17023SJohn Marino return false;
452*e4b17023SJohn Marino }
453*e4b17023SJohn Marino break;
454*e4b17023SJohn Marino
455*e4b17023SJohn Marino case '%':
456*e4b17023SJohn Marino if (constraint == orig_constraint
457*e4b17023SJohn Marino && input_num + 1 == ninputs - ninout)
458*e4b17023SJohn Marino {
459*e4b17023SJohn Marino error ("%<%%%> constraint used with last operand");
460*e4b17023SJohn Marino return false;
461*e4b17023SJohn Marino }
462*e4b17023SJohn Marino break;
463*e4b17023SJohn Marino
464*e4b17023SJohn Marino case 'V': case TARGET_MEM_CONSTRAINT: case 'o':
465*e4b17023SJohn Marino *allows_mem = true;
466*e4b17023SJohn Marino break;
467*e4b17023SJohn Marino
468*e4b17023SJohn Marino case '<': case '>':
469*e4b17023SJohn Marino case '?': case '!': case '*': case '#':
470*e4b17023SJohn Marino case 'E': case 'F': case 'G': case 'H':
471*e4b17023SJohn Marino case 's': case 'i': case 'n':
472*e4b17023SJohn Marino case 'I': case 'J': case 'K': case 'L': case 'M':
473*e4b17023SJohn Marino case 'N': case 'O': case 'P': case ',':
474*e4b17023SJohn Marino break;
475*e4b17023SJohn Marino
476*e4b17023SJohn Marino /* Whether or not a numeric constraint allows a register is
477*e4b17023SJohn Marino decided by the matching constraint, and so there is no need
478*e4b17023SJohn Marino to do anything special with them. We must handle them in
479*e4b17023SJohn Marino the default case, so that we don't unnecessarily force
480*e4b17023SJohn Marino operands to memory. */
481*e4b17023SJohn Marino case '0': case '1': case '2': case '3': case '4':
482*e4b17023SJohn Marino case '5': case '6': case '7': case '8': case '9':
483*e4b17023SJohn Marino {
484*e4b17023SJohn Marino char *end;
485*e4b17023SJohn Marino unsigned long match;
486*e4b17023SJohn Marino
487*e4b17023SJohn Marino saw_match = true;
488*e4b17023SJohn Marino
489*e4b17023SJohn Marino match = strtoul (constraint + j, &end, 10);
490*e4b17023SJohn Marino if (match >= (unsigned long) noutputs)
491*e4b17023SJohn Marino {
492*e4b17023SJohn Marino error ("matching constraint references invalid operand number");
493*e4b17023SJohn Marino return false;
494*e4b17023SJohn Marino }
495*e4b17023SJohn Marino
496*e4b17023SJohn Marino /* Try and find the real constraint for this dup. Only do this
497*e4b17023SJohn Marino if the matching constraint is the only alternative. */
498*e4b17023SJohn Marino if (*end == '\0'
499*e4b17023SJohn Marino && (j == 0 || (j == 1 && constraint[0] == '%')))
500*e4b17023SJohn Marino {
501*e4b17023SJohn Marino constraint = constraints[match];
502*e4b17023SJohn Marino *constraint_p = constraint;
503*e4b17023SJohn Marino c_len = strlen (constraint);
504*e4b17023SJohn Marino j = 0;
505*e4b17023SJohn Marino /* ??? At the end of the loop, we will skip the first part of
506*e4b17023SJohn Marino the matched constraint. This assumes not only that the
507*e4b17023SJohn Marino other constraint is an output constraint, but also that
508*e4b17023SJohn Marino the '=' or '+' come first. */
509*e4b17023SJohn Marino break;
510*e4b17023SJohn Marino }
511*e4b17023SJohn Marino else
512*e4b17023SJohn Marino j = end - constraint;
513*e4b17023SJohn Marino /* Anticipate increment at end of loop. */
514*e4b17023SJohn Marino j--;
515*e4b17023SJohn Marino }
516*e4b17023SJohn Marino /* Fall through. */
517*e4b17023SJohn Marino
518*e4b17023SJohn Marino case 'p': case 'r':
519*e4b17023SJohn Marino *allows_reg = true;
520*e4b17023SJohn Marino break;
521*e4b17023SJohn Marino
522*e4b17023SJohn Marino case 'g': case 'X':
523*e4b17023SJohn Marino *allows_reg = true;
524*e4b17023SJohn Marino *allows_mem = true;
525*e4b17023SJohn Marino break;
526*e4b17023SJohn Marino
527*e4b17023SJohn Marino default:
528*e4b17023SJohn Marino if (! ISALPHA (constraint[j]))
529*e4b17023SJohn Marino {
530*e4b17023SJohn Marino error ("invalid punctuation %qc in constraint", constraint[j]);
531*e4b17023SJohn Marino return false;
532*e4b17023SJohn Marino }
533*e4b17023SJohn Marino if (REG_CLASS_FROM_CONSTRAINT (constraint[j], constraint + j)
534*e4b17023SJohn Marino != NO_REGS)
535*e4b17023SJohn Marino *allows_reg = true;
536*e4b17023SJohn Marino #ifdef EXTRA_CONSTRAINT_STR
537*e4b17023SJohn Marino else if (EXTRA_ADDRESS_CONSTRAINT (constraint[j], constraint + j))
538*e4b17023SJohn Marino *allows_reg = true;
539*e4b17023SJohn Marino else if (EXTRA_MEMORY_CONSTRAINT (constraint[j], constraint + j))
540*e4b17023SJohn Marino *allows_mem = true;
541*e4b17023SJohn Marino else
542*e4b17023SJohn Marino {
543*e4b17023SJohn Marino /* Otherwise we can't assume anything about the nature of
544*e4b17023SJohn Marino the constraint except that it isn't purely registers.
545*e4b17023SJohn Marino Treat it like "g" and hope for the best. */
546*e4b17023SJohn Marino *allows_reg = true;
547*e4b17023SJohn Marino *allows_mem = true;
548*e4b17023SJohn Marino }
549*e4b17023SJohn Marino #endif
550*e4b17023SJohn Marino break;
551*e4b17023SJohn Marino }
552*e4b17023SJohn Marino
553*e4b17023SJohn Marino if (saw_match && !*allows_reg)
554*e4b17023SJohn Marino warning (0, "matching constraint does not allow a register");
555*e4b17023SJohn Marino
556*e4b17023SJohn Marino return true;
557*e4b17023SJohn Marino }
558*e4b17023SJohn Marino
559*e4b17023SJohn Marino /* Return DECL iff there's an overlap between *REGS and DECL, where DECL
560*e4b17023SJohn Marino can be an asm-declared register. Called via walk_tree. */
561*e4b17023SJohn Marino
562*e4b17023SJohn Marino static tree
decl_overlaps_hard_reg_set_p(tree * declp,int * walk_subtrees ATTRIBUTE_UNUSED,void * data)563*e4b17023SJohn Marino decl_overlaps_hard_reg_set_p (tree *declp, int *walk_subtrees ATTRIBUTE_UNUSED,
564*e4b17023SJohn Marino void *data)
565*e4b17023SJohn Marino {
566*e4b17023SJohn Marino tree decl = *declp;
567*e4b17023SJohn Marino const HARD_REG_SET *const regs = (const HARD_REG_SET *) data;
568*e4b17023SJohn Marino
569*e4b17023SJohn Marino if (TREE_CODE (decl) == VAR_DECL)
570*e4b17023SJohn Marino {
571*e4b17023SJohn Marino if (DECL_HARD_REGISTER (decl)
572*e4b17023SJohn Marino && REG_P (DECL_RTL (decl))
573*e4b17023SJohn Marino && REGNO (DECL_RTL (decl)) < FIRST_PSEUDO_REGISTER)
574*e4b17023SJohn Marino {
575*e4b17023SJohn Marino rtx reg = DECL_RTL (decl);
576*e4b17023SJohn Marino
577*e4b17023SJohn Marino if (overlaps_hard_reg_set_p (*regs, GET_MODE (reg), REGNO (reg)))
578*e4b17023SJohn Marino return decl;
579*e4b17023SJohn Marino }
580*e4b17023SJohn Marino walk_subtrees = 0;
581*e4b17023SJohn Marino }
582*e4b17023SJohn Marino else if (TYPE_P (decl) || TREE_CODE (decl) == PARM_DECL)
583*e4b17023SJohn Marino walk_subtrees = 0;
584*e4b17023SJohn Marino return NULL_TREE;
585*e4b17023SJohn Marino }
586*e4b17023SJohn Marino
587*e4b17023SJohn Marino /* If there is an overlap between *REGS and DECL, return the first overlap
588*e4b17023SJohn Marino found. */
589*e4b17023SJohn Marino tree
tree_overlaps_hard_reg_set(tree decl,HARD_REG_SET * regs)590*e4b17023SJohn Marino tree_overlaps_hard_reg_set (tree decl, HARD_REG_SET *regs)
591*e4b17023SJohn Marino {
592*e4b17023SJohn Marino return walk_tree (&decl, decl_overlaps_hard_reg_set_p, regs, NULL);
593*e4b17023SJohn Marino }
594*e4b17023SJohn Marino
595*e4b17023SJohn Marino /* Check for overlap between registers marked in CLOBBERED_REGS and
596*e4b17023SJohn Marino anything inappropriate in T. Emit error and return the register
597*e4b17023SJohn Marino variable definition for error, NULL_TREE for ok. */
598*e4b17023SJohn Marino
599*e4b17023SJohn Marino static bool
tree_conflicts_with_clobbers_p(tree t,HARD_REG_SET * clobbered_regs)600*e4b17023SJohn Marino tree_conflicts_with_clobbers_p (tree t, HARD_REG_SET *clobbered_regs)
601*e4b17023SJohn Marino {
602*e4b17023SJohn Marino /* Conflicts between asm-declared register variables and the clobber
603*e4b17023SJohn Marino list are not allowed. */
604*e4b17023SJohn Marino tree overlap = tree_overlaps_hard_reg_set (t, clobbered_regs);
605*e4b17023SJohn Marino
606*e4b17023SJohn Marino if (overlap)
607*e4b17023SJohn Marino {
608*e4b17023SJohn Marino error ("asm-specifier for variable %qE conflicts with asm clobber list",
609*e4b17023SJohn Marino DECL_NAME (overlap));
610*e4b17023SJohn Marino
611*e4b17023SJohn Marino /* Reset registerness to stop multiple errors emitted for a single
612*e4b17023SJohn Marino variable. */
613*e4b17023SJohn Marino DECL_REGISTER (overlap) = 0;
614*e4b17023SJohn Marino return true;
615*e4b17023SJohn Marino }
616*e4b17023SJohn Marino
617*e4b17023SJohn Marino return false;
618*e4b17023SJohn Marino }
619*e4b17023SJohn Marino
620*e4b17023SJohn Marino /* Generate RTL for an asm statement with arguments.
621*e4b17023SJohn Marino STRING is the instruction template.
622*e4b17023SJohn Marino OUTPUTS is a list of output arguments (lvalues); INPUTS a list of inputs.
623*e4b17023SJohn Marino Each output or input has an expression in the TREE_VALUE and
624*e4b17023SJohn Marino a tree list in TREE_PURPOSE which in turn contains a constraint
625*e4b17023SJohn Marino name in TREE_VALUE (or NULL_TREE) and a constraint string
626*e4b17023SJohn Marino in TREE_PURPOSE.
627*e4b17023SJohn Marino CLOBBERS is a list of STRING_CST nodes each naming a hard register
628*e4b17023SJohn Marino that is clobbered by this insn.
629*e4b17023SJohn Marino
630*e4b17023SJohn Marino Not all kinds of lvalue that may appear in OUTPUTS can be stored directly.
631*e4b17023SJohn Marino Some elements of OUTPUTS may be replaced with trees representing temporary
632*e4b17023SJohn Marino values. The caller should copy those temporary values to the originally
633*e4b17023SJohn Marino specified lvalues.
634*e4b17023SJohn Marino
635*e4b17023SJohn Marino VOL nonzero means the insn is volatile; don't optimize it. */
636*e4b17023SJohn Marino
637*e4b17023SJohn Marino static void
expand_asm_operands(tree string,tree outputs,tree inputs,tree clobbers,tree labels,int vol,location_t locus)638*e4b17023SJohn Marino expand_asm_operands (tree string, tree outputs, tree inputs,
639*e4b17023SJohn Marino tree clobbers, tree labels, int vol, location_t locus)
640*e4b17023SJohn Marino {
641*e4b17023SJohn Marino rtvec argvec, constraintvec, labelvec;
642*e4b17023SJohn Marino rtx body;
643*e4b17023SJohn Marino int ninputs = list_length (inputs);
644*e4b17023SJohn Marino int noutputs = list_length (outputs);
645*e4b17023SJohn Marino int nlabels = list_length (labels);
646*e4b17023SJohn Marino int ninout;
647*e4b17023SJohn Marino int nclobbers;
648*e4b17023SJohn Marino HARD_REG_SET clobbered_regs;
649*e4b17023SJohn Marino int clobber_conflict_found = 0;
650*e4b17023SJohn Marino tree tail;
651*e4b17023SJohn Marino tree t;
652*e4b17023SJohn Marino int i;
653*e4b17023SJohn Marino /* Vector of RTX's of evaluated output operands. */
654*e4b17023SJohn Marino rtx *output_rtx = XALLOCAVEC (rtx, noutputs);
655*e4b17023SJohn Marino int *inout_opnum = XALLOCAVEC (int, noutputs);
656*e4b17023SJohn Marino rtx *real_output_rtx = XALLOCAVEC (rtx, noutputs);
657*e4b17023SJohn Marino enum machine_mode *inout_mode = XALLOCAVEC (enum machine_mode, noutputs);
658*e4b17023SJohn Marino const char **constraints = XALLOCAVEC (const char *, noutputs + ninputs);
659*e4b17023SJohn Marino int old_generating_concat_p = generating_concat_p;
660*e4b17023SJohn Marino
661*e4b17023SJohn Marino /* An ASM with no outputs needs to be treated as volatile, for now. */
662*e4b17023SJohn Marino if (noutputs == 0)
663*e4b17023SJohn Marino vol = 1;
664*e4b17023SJohn Marino
665*e4b17023SJohn Marino if (! check_operand_nalternatives (outputs, inputs))
666*e4b17023SJohn Marino return;
667*e4b17023SJohn Marino
668*e4b17023SJohn Marino string = resolve_asm_operand_names (string, outputs, inputs, labels);
669*e4b17023SJohn Marino
670*e4b17023SJohn Marino /* Collect constraints. */
671*e4b17023SJohn Marino i = 0;
672*e4b17023SJohn Marino for (t = outputs; t ; t = TREE_CHAIN (t), i++)
673*e4b17023SJohn Marino constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
674*e4b17023SJohn Marino for (t = inputs; t ; t = TREE_CHAIN (t), i++)
675*e4b17023SJohn Marino constraints[i] = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
676*e4b17023SJohn Marino
677*e4b17023SJohn Marino /* Sometimes we wish to automatically clobber registers across an asm.
678*e4b17023SJohn Marino Case in point is when the i386 backend moved from cc0 to a hard reg --
679*e4b17023SJohn Marino maintaining source-level compatibility means automatically clobbering
680*e4b17023SJohn Marino the flags register. */
681*e4b17023SJohn Marino clobbers = targetm.md_asm_clobbers (outputs, inputs, clobbers);
682*e4b17023SJohn Marino
683*e4b17023SJohn Marino /* Count the number of meaningful clobbered registers, ignoring what
684*e4b17023SJohn Marino we would ignore later. */
685*e4b17023SJohn Marino nclobbers = 0;
686*e4b17023SJohn Marino CLEAR_HARD_REG_SET (clobbered_regs);
687*e4b17023SJohn Marino for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
688*e4b17023SJohn Marino {
689*e4b17023SJohn Marino const char *regname;
690*e4b17023SJohn Marino int nregs;
691*e4b17023SJohn Marino
692*e4b17023SJohn Marino if (TREE_VALUE (tail) == error_mark_node)
693*e4b17023SJohn Marino return;
694*e4b17023SJohn Marino regname = TREE_STRING_POINTER (TREE_VALUE (tail));
695*e4b17023SJohn Marino
696*e4b17023SJohn Marino i = decode_reg_name_and_count (regname, &nregs);
697*e4b17023SJohn Marino if (i == -4)
698*e4b17023SJohn Marino ++nclobbers;
699*e4b17023SJohn Marino else if (i == -2)
700*e4b17023SJohn Marino error ("unknown register name %qs in %<asm%>", regname);
701*e4b17023SJohn Marino
702*e4b17023SJohn Marino /* Mark clobbered registers. */
703*e4b17023SJohn Marino if (i >= 0)
704*e4b17023SJohn Marino {
705*e4b17023SJohn Marino int reg;
706*e4b17023SJohn Marino
707*e4b17023SJohn Marino for (reg = i; reg < i + nregs; reg++)
708*e4b17023SJohn Marino {
709*e4b17023SJohn Marino ++nclobbers;
710*e4b17023SJohn Marino
711*e4b17023SJohn Marino /* Clobbering the PIC register is an error. */
712*e4b17023SJohn Marino if (reg == (int) PIC_OFFSET_TABLE_REGNUM)
713*e4b17023SJohn Marino {
714*e4b17023SJohn Marino error ("PIC register clobbered by %qs in %<asm%>", regname);
715*e4b17023SJohn Marino return;
716*e4b17023SJohn Marino }
717*e4b17023SJohn Marino
718*e4b17023SJohn Marino SET_HARD_REG_BIT (clobbered_regs, reg);
719*e4b17023SJohn Marino }
720*e4b17023SJohn Marino }
721*e4b17023SJohn Marino }
722*e4b17023SJohn Marino
723*e4b17023SJohn Marino /* First pass over inputs and outputs checks validity and sets
724*e4b17023SJohn Marino mark_addressable if needed. */
725*e4b17023SJohn Marino
726*e4b17023SJohn Marino ninout = 0;
727*e4b17023SJohn Marino for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
728*e4b17023SJohn Marino {
729*e4b17023SJohn Marino tree val = TREE_VALUE (tail);
730*e4b17023SJohn Marino tree type = TREE_TYPE (val);
731*e4b17023SJohn Marino const char *constraint;
732*e4b17023SJohn Marino bool is_inout;
733*e4b17023SJohn Marino bool allows_reg;
734*e4b17023SJohn Marino bool allows_mem;
735*e4b17023SJohn Marino
736*e4b17023SJohn Marino /* If there's an erroneous arg, emit no insn. */
737*e4b17023SJohn Marino if (type == error_mark_node)
738*e4b17023SJohn Marino return;
739*e4b17023SJohn Marino
740*e4b17023SJohn Marino /* Try to parse the output constraint. If that fails, there's
741*e4b17023SJohn Marino no point in going further. */
742*e4b17023SJohn Marino constraint = constraints[i];
743*e4b17023SJohn Marino if (!parse_output_constraint (&constraint, i, ninputs, noutputs,
744*e4b17023SJohn Marino &allows_mem, &allows_reg, &is_inout))
745*e4b17023SJohn Marino return;
746*e4b17023SJohn Marino
747*e4b17023SJohn Marino if (! allows_reg
748*e4b17023SJohn Marino && (allows_mem
749*e4b17023SJohn Marino || is_inout
750*e4b17023SJohn Marino || (DECL_P (val)
751*e4b17023SJohn Marino && REG_P (DECL_RTL (val))
752*e4b17023SJohn Marino && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type))))
753*e4b17023SJohn Marino mark_addressable (val);
754*e4b17023SJohn Marino
755*e4b17023SJohn Marino if (is_inout)
756*e4b17023SJohn Marino ninout++;
757*e4b17023SJohn Marino }
758*e4b17023SJohn Marino
759*e4b17023SJohn Marino ninputs += ninout;
760*e4b17023SJohn Marino if (ninputs + noutputs > MAX_RECOG_OPERANDS)
761*e4b17023SJohn Marino {
762*e4b17023SJohn Marino error ("more than %d operands in %<asm%>", MAX_RECOG_OPERANDS);
763*e4b17023SJohn Marino return;
764*e4b17023SJohn Marino }
765*e4b17023SJohn Marino
766*e4b17023SJohn Marino for (i = 0, tail = inputs; tail; i++, tail = TREE_CHAIN (tail))
767*e4b17023SJohn Marino {
768*e4b17023SJohn Marino bool allows_reg, allows_mem;
769*e4b17023SJohn Marino const char *constraint;
770*e4b17023SJohn Marino
771*e4b17023SJohn Marino /* If there's an erroneous arg, emit no insn, because the ASM_INPUT
772*e4b17023SJohn Marino would get VOIDmode and that could cause a crash in reload. */
773*e4b17023SJohn Marino if (TREE_TYPE (TREE_VALUE (tail)) == error_mark_node)
774*e4b17023SJohn Marino return;
775*e4b17023SJohn Marino
776*e4b17023SJohn Marino constraint = constraints[i + noutputs];
777*e4b17023SJohn Marino if (! parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
778*e4b17023SJohn Marino constraints, &allows_mem, &allows_reg))
779*e4b17023SJohn Marino return;
780*e4b17023SJohn Marino
781*e4b17023SJohn Marino if (! allows_reg && allows_mem)
782*e4b17023SJohn Marino mark_addressable (TREE_VALUE (tail));
783*e4b17023SJohn Marino }
784*e4b17023SJohn Marino
785*e4b17023SJohn Marino /* Second pass evaluates arguments. */
786*e4b17023SJohn Marino
787*e4b17023SJohn Marino /* Make sure stack is consistent for asm goto. */
788*e4b17023SJohn Marino if (nlabels > 0)
789*e4b17023SJohn Marino do_pending_stack_adjust ();
790*e4b17023SJohn Marino
791*e4b17023SJohn Marino ninout = 0;
792*e4b17023SJohn Marino for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
793*e4b17023SJohn Marino {
794*e4b17023SJohn Marino tree val = TREE_VALUE (tail);
795*e4b17023SJohn Marino tree type = TREE_TYPE (val);
796*e4b17023SJohn Marino bool is_inout;
797*e4b17023SJohn Marino bool allows_reg;
798*e4b17023SJohn Marino bool allows_mem;
799*e4b17023SJohn Marino rtx op;
800*e4b17023SJohn Marino bool ok;
801*e4b17023SJohn Marino
802*e4b17023SJohn Marino ok = parse_output_constraint (&constraints[i], i, ninputs,
803*e4b17023SJohn Marino noutputs, &allows_mem, &allows_reg,
804*e4b17023SJohn Marino &is_inout);
805*e4b17023SJohn Marino gcc_assert (ok);
806*e4b17023SJohn Marino
807*e4b17023SJohn Marino /* If an output operand is not a decl or indirect ref and our constraint
808*e4b17023SJohn Marino allows a register, make a temporary to act as an intermediate.
809*e4b17023SJohn Marino Make the asm insn write into that, then our caller will copy it to
810*e4b17023SJohn Marino the real output operand. Likewise for promoted variables. */
811*e4b17023SJohn Marino
812*e4b17023SJohn Marino generating_concat_p = 0;
813*e4b17023SJohn Marino
814*e4b17023SJohn Marino real_output_rtx[i] = NULL_RTX;
815*e4b17023SJohn Marino if ((TREE_CODE (val) == INDIRECT_REF
816*e4b17023SJohn Marino && allows_mem)
817*e4b17023SJohn Marino || (DECL_P (val)
818*e4b17023SJohn Marino && (allows_mem || REG_P (DECL_RTL (val)))
819*e4b17023SJohn Marino && ! (REG_P (DECL_RTL (val))
820*e4b17023SJohn Marino && GET_MODE (DECL_RTL (val)) != TYPE_MODE (type)))
821*e4b17023SJohn Marino || ! allows_reg
822*e4b17023SJohn Marino || is_inout)
823*e4b17023SJohn Marino {
824*e4b17023SJohn Marino op = expand_expr (val, NULL_RTX, VOIDmode, EXPAND_WRITE);
825*e4b17023SJohn Marino if (MEM_P (op))
826*e4b17023SJohn Marino op = validize_mem (op);
827*e4b17023SJohn Marino
828*e4b17023SJohn Marino if (! allows_reg && !MEM_P (op))
829*e4b17023SJohn Marino error ("output number %d not directly addressable", i);
830*e4b17023SJohn Marino if ((! allows_mem && MEM_P (op))
831*e4b17023SJohn Marino || GET_CODE (op) == CONCAT)
832*e4b17023SJohn Marino {
833*e4b17023SJohn Marino real_output_rtx[i] = op;
834*e4b17023SJohn Marino op = gen_reg_rtx (GET_MODE (op));
835*e4b17023SJohn Marino if (is_inout)
836*e4b17023SJohn Marino emit_move_insn (op, real_output_rtx[i]);
837*e4b17023SJohn Marino }
838*e4b17023SJohn Marino }
839*e4b17023SJohn Marino else
840*e4b17023SJohn Marino {
841*e4b17023SJohn Marino op = assign_temp (type, 0, 0, 1);
842*e4b17023SJohn Marino op = validize_mem (op);
843*e4b17023SJohn Marino if (!MEM_P (op) && TREE_CODE (TREE_VALUE (tail)) == SSA_NAME)
844*e4b17023SJohn Marino set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (TREE_VALUE (tail)), op);
845*e4b17023SJohn Marino TREE_VALUE (tail) = make_tree (type, op);
846*e4b17023SJohn Marino }
847*e4b17023SJohn Marino output_rtx[i] = op;
848*e4b17023SJohn Marino
849*e4b17023SJohn Marino generating_concat_p = old_generating_concat_p;
850*e4b17023SJohn Marino
851*e4b17023SJohn Marino if (is_inout)
852*e4b17023SJohn Marino {
853*e4b17023SJohn Marino inout_mode[ninout] = TYPE_MODE (type);
854*e4b17023SJohn Marino inout_opnum[ninout++] = i;
855*e4b17023SJohn Marino }
856*e4b17023SJohn Marino
857*e4b17023SJohn Marino if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
858*e4b17023SJohn Marino clobber_conflict_found = 1;
859*e4b17023SJohn Marino }
860*e4b17023SJohn Marino
861*e4b17023SJohn Marino /* Make vectors for the expression-rtx, constraint strings,
862*e4b17023SJohn Marino and named operands. */
863*e4b17023SJohn Marino
864*e4b17023SJohn Marino argvec = rtvec_alloc (ninputs);
865*e4b17023SJohn Marino constraintvec = rtvec_alloc (ninputs);
866*e4b17023SJohn Marino labelvec = rtvec_alloc (nlabels);
867*e4b17023SJohn Marino
868*e4b17023SJohn Marino body = gen_rtx_ASM_OPERANDS ((noutputs == 0 ? VOIDmode
869*e4b17023SJohn Marino : GET_MODE (output_rtx[0])),
870*e4b17023SJohn Marino ggc_strdup (TREE_STRING_POINTER (string)),
871*e4b17023SJohn Marino empty_string, 0, argvec, constraintvec,
872*e4b17023SJohn Marino labelvec, locus);
873*e4b17023SJohn Marino
874*e4b17023SJohn Marino MEM_VOLATILE_P (body) = vol;
875*e4b17023SJohn Marino
876*e4b17023SJohn Marino /* Eval the inputs and put them into ARGVEC.
877*e4b17023SJohn Marino Put their constraints into ASM_INPUTs and store in CONSTRAINTS. */
878*e4b17023SJohn Marino
879*e4b17023SJohn Marino for (i = 0, tail = inputs; tail; tail = TREE_CHAIN (tail), ++i)
880*e4b17023SJohn Marino {
881*e4b17023SJohn Marino bool allows_reg, allows_mem;
882*e4b17023SJohn Marino const char *constraint;
883*e4b17023SJohn Marino tree val, type;
884*e4b17023SJohn Marino rtx op;
885*e4b17023SJohn Marino bool ok;
886*e4b17023SJohn Marino
887*e4b17023SJohn Marino constraint = constraints[i + noutputs];
888*e4b17023SJohn Marino ok = parse_input_constraint (&constraint, i, ninputs, noutputs, ninout,
889*e4b17023SJohn Marino constraints, &allows_mem, &allows_reg);
890*e4b17023SJohn Marino gcc_assert (ok);
891*e4b17023SJohn Marino
892*e4b17023SJohn Marino generating_concat_p = 0;
893*e4b17023SJohn Marino
894*e4b17023SJohn Marino val = TREE_VALUE (tail);
895*e4b17023SJohn Marino type = TREE_TYPE (val);
896*e4b17023SJohn Marino /* EXPAND_INITIALIZER will not generate code for valid initializer
897*e4b17023SJohn Marino constants, but will still generate code for other types of operand.
898*e4b17023SJohn Marino This is the behavior we want for constant constraints. */
899*e4b17023SJohn Marino op = expand_expr (val, NULL_RTX, VOIDmode,
900*e4b17023SJohn Marino allows_reg ? EXPAND_NORMAL
901*e4b17023SJohn Marino : allows_mem ? EXPAND_MEMORY
902*e4b17023SJohn Marino : EXPAND_INITIALIZER);
903*e4b17023SJohn Marino
904*e4b17023SJohn Marino /* Never pass a CONCAT to an ASM. */
905*e4b17023SJohn Marino if (GET_CODE (op) == CONCAT)
906*e4b17023SJohn Marino op = force_reg (GET_MODE (op), op);
907*e4b17023SJohn Marino else if (MEM_P (op))
908*e4b17023SJohn Marino op = validize_mem (op);
909*e4b17023SJohn Marino
910*e4b17023SJohn Marino if (asm_operand_ok (op, constraint, NULL) <= 0)
911*e4b17023SJohn Marino {
912*e4b17023SJohn Marino if (allows_reg && TYPE_MODE (type) != BLKmode)
913*e4b17023SJohn Marino op = force_reg (TYPE_MODE (type), op);
914*e4b17023SJohn Marino else if (!allows_mem)
915*e4b17023SJohn Marino warning (0, "asm operand %d probably doesn%'t match constraints",
916*e4b17023SJohn Marino i + noutputs);
917*e4b17023SJohn Marino else if (MEM_P (op))
918*e4b17023SJohn Marino {
919*e4b17023SJohn Marino /* We won't recognize either volatile memory or memory
920*e4b17023SJohn Marino with a queued address as available a memory_operand
921*e4b17023SJohn Marino at this point. Ignore it: clearly this *is* a memory. */
922*e4b17023SJohn Marino }
923*e4b17023SJohn Marino else
924*e4b17023SJohn Marino {
925*e4b17023SJohn Marino warning (0, "use of memory input without lvalue in "
926*e4b17023SJohn Marino "asm operand %d is deprecated", i + noutputs);
927*e4b17023SJohn Marino
928*e4b17023SJohn Marino if (CONSTANT_P (op))
929*e4b17023SJohn Marino {
930*e4b17023SJohn Marino rtx mem = force_const_mem (TYPE_MODE (type), op);
931*e4b17023SJohn Marino if (mem)
932*e4b17023SJohn Marino op = validize_mem (mem);
933*e4b17023SJohn Marino else
934*e4b17023SJohn Marino op = force_reg (TYPE_MODE (type), op);
935*e4b17023SJohn Marino }
936*e4b17023SJohn Marino if (REG_P (op)
937*e4b17023SJohn Marino || GET_CODE (op) == SUBREG
938*e4b17023SJohn Marino || GET_CODE (op) == CONCAT)
939*e4b17023SJohn Marino {
940*e4b17023SJohn Marino tree qual_type = build_qualified_type (type,
941*e4b17023SJohn Marino (TYPE_QUALS (type)
942*e4b17023SJohn Marino | TYPE_QUAL_CONST));
943*e4b17023SJohn Marino rtx memloc = assign_temp (qual_type, 1, 1, 1);
944*e4b17023SJohn Marino memloc = validize_mem (memloc);
945*e4b17023SJohn Marino emit_move_insn (memloc, op);
946*e4b17023SJohn Marino op = memloc;
947*e4b17023SJohn Marino }
948*e4b17023SJohn Marino }
949*e4b17023SJohn Marino }
950*e4b17023SJohn Marino
951*e4b17023SJohn Marino generating_concat_p = old_generating_concat_p;
952*e4b17023SJohn Marino ASM_OPERANDS_INPUT (body, i) = op;
953*e4b17023SJohn Marino
954*e4b17023SJohn Marino ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, i)
955*e4b17023SJohn Marino = gen_rtx_ASM_INPUT (TYPE_MODE (type),
956*e4b17023SJohn Marino ggc_strdup (constraints[i + noutputs]));
957*e4b17023SJohn Marino
958*e4b17023SJohn Marino if (tree_conflicts_with_clobbers_p (val, &clobbered_regs))
959*e4b17023SJohn Marino clobber_conflict_found = 1;
960*e4b17023SJohn Marino }
961*e4b17023SJohn Marino
962*e4b17023SJohn Marino /* Protect all the operands from the queue now that they have all been
963*e4b17023SJohn Marino evaluated. */
964*e4b17023SJohn Marino
965*e4b17023SJohn Marino generating_concat_p = 0;
966*e4b17023SJohn Marino
967*e4b17023SJohn Marino /* For in-out operands, copy output rtx to input rtx. */
968*e4b17023SJohn Marino for (i = 0; i < ninout; i++)
969*e4b17023SJohn Marino {
970*e4b17023SJohn Marino int j = inout_opnum[i];
971*e4b17023SJohn Marino char buffer[16];
972*e4b17023SJohn Marino
973*e4b17023SJohn Marino ASM_OPERANDS_INPUT (body, ninputs - ninout + i)
974*e4b17023SJohn Marino = output_rtx[j];
975*e4b17023SJohn Marino
976*e4b17023SJohn Marino sprintf (buffer, "%d", j);
977*e4b17023SJohn Marino ASM_OPERANDS_INPUT_CONSTRAINT_EXP (body, ninputs - ninout + i)
978*e4b17023SJohn Marino = gen_rtx_ASM_INPUT (inout_mode[i], ggc_strdup (buffer));
979*e4b17023SJohn Marino }
980*e4b17023SJohn Marino
981*e4b17023SJohn Marino /* Copy labels to the vector. */
982*e4b17023SJohn Marino for (i = 0, tail = labels; i < nlabels; ++i, tail = TREE_CHAIN (tail))
983*e4b17023SJohn Marino ASM_OPERANDS_LABEL (body, i)
984*e4b17023SJohn Marino = gen_rtx_LABEL_REF (Pmode, label_rtx (TREE_VALUE (tail)));
985*e4b17023SJohn Marino
986*e4b17023SJohn Marino generating_concat_p = old_generating_concat_p;
987*e4b17023SJohn Marino
988*e4b17023SJohn Marino /* Now, for each output, construct an rtx
989*e4b17023SJohn Marino (set OUTPUT (asm_operands INSN OUTPUTCONSTRAINT OUTPUTNUMBER
990*e4b17023SJohn Marino ARGVEC CONSTRAINTS OPNAMES))
991*e4b17023SJohn Marino If there is more than one, put them inside a PARALLEL. */
992*e4b17023SJohn Marino
993*e4b17023SJohn Marino if (nlabels > 0 && nclobbers == 0)
994*e4b17023SJohn Marino {
995*e4b17023SJohn Marino gcc_assert (noutputs == 0);
996*e4b17023SJohn Marino emit_jump_insn (body);
997*e4b17023SJohn Marino }
998*e4b17023SJohn Marino else if (noutputs == 0 && nclobbers == 0)
999*e4b17023SJohn Marino {
1000*e4b17023SJohn Marino /* No output operands: put in a raw ASM_OPERANDS rtx. */
1001*e4b17023SJohn Marino emit_insn (body);
1002*e4b17023SJohn Marino }
1003*e4b17023SJohn Marino else if (noutputs == 1 && nclobbers == 0)
1004*e4b17023SJohn Marino {
1005*e4b17023SJohn Marino ASM_OPERANDS_OUTPUT_CONSTRAINT (body) = ggc_strdup (constraints[0]);
1006*e4b17023SJohn Marino emit_insn (gen_rtx_SET (VOIDmode, output_rtx[0], body));
1007*e4b17023SJohn Marino }
1008*e4b17023SJohn Marino else
1009*e4b17023SJohn Marino {
1010*e4b17023SJohn Marino rtx obody = body;
1011*e4b17023SJohn Marino int num = noutputs;
1012*e4b17023SJohn Marino
1013*e4b17023SJohn Marino if (num == 0)
1014*e4b17023SJohn Marino num = 1;
1015*e4b17023SJohn Marino
1016*e4b17023SJohn Marino body = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num + nclobbers));
1017*e4b17023SJohn Marino
1018*e4b17023SJohn Marino /* For each output operand, store a SET. */
1019*e4b17023SJohn Marino for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1020*e4b17023SJohn Marino {
1021*e4b17023SJohn Marino XVECEXP (body, 0, i)
1022*e4b17023SJohn Marino = gen_rtx_SET (VOIDmode,
1023*e4b17023SJohn Marino output_rtx[i],
1024*e4b17023SJohn Marino gen_rtx_ASM_OPERANDS
1025*e4b17023SJohn Marino (GET_MODE (output_rtx[i]),
1026*e4b17023SJohn Marino ggc_strdup (TREE_STRING_POINTER (string)),
1027*e4b17023SJohn Marino ggc_strdup (constraints[i]),
1028*e4b17023SJohn Marino i, argvec, constraintvec, labelvec, locus));
1029*e4b17023SJohn Marino
1030*e4b17023SJohn Marino MEM_VOLATILE_P (SET_SRC (XVECEXP (body, 0, i))) = vol;
1031*e4b17023SJohn Marino }
1032*e4b17023SJohn Marino
1033*e4b17023SJohn Marino /* If there are no outputs (but there are some clobbers)
1034*e4b17023SJohn Marino store the bare ASM_OPERANDS into the PARALLEL. */
1035*e4b17023SJohn Marino
1036*e4b17023SJohn Marino if (i == 0)
1037*e4b17023SJohn Marino XVECEXP (body, 0, i++) = obody;
1038*e4b17023SJohn Marino
1039*e4b17023SJohn Marino /* Store (clobber REG) for each clobbered register specified. */
1040*e4b17023SJohn Marino
1041*e4b17023SJohn Marino for (tail = clobbers; tail; tail = TREE_CHAIN (tail))
1042*e4b17023SJohn Marino {
1043*e4b17023SJohn Marino const char *regname = TREE_STRING_POINTER (TREE_VALUE (tail));
1044*e4b17023SJohn Marino int reg, nregs;
1045*e4b17023SJohn Marino int j = decode_reg_name_and_count (regname, &nregs);
1046*e4b17023SJohn Marino rtx clobbered_reg;
1047*e4b17023SJohn Marino
1048*e4b17023SJohn Marino if (j < 0)
1049*e4b17023SJohn Marino {
1050*e4b17023SJohn Marino if (j == -3) /* `cc', which is not a register */
1051*e4b17023SJohn Marino continue;
1052*e4b17023SJohn Marino
1053*e4b17023SJohn Marino if (j == -4) /* `memory', don't cache memory across asm */
1054*e4b17023SJohn Marino {
1055*e4b17023SJohn Marino XVECEXP (body, 0, i++)
1056*e4b17023SJohn Marino = gen_rtx_CLOBBER (VOIDmode,
1057*e4b17023SJohn Marino gen_rtx_MEM
1058*e4b17023SJohn Marino (BLKmode,
1059*e4b17023SJohn Marino gen_rtx_SCRATCH (VOIDmode)));
1060*e4b17023SJohn Marino continue;
1061*e4b17023SJohn Marino }
1062*e4b17023SJohn Marino
1063*e4b17023SJohn Marino /* Ignore unknown register, error already signaled. */
1064*e4b17023SJohn Marino continue;
1065*e4b17023SJohn Marino }
1066*e4b17023SJohn Marino
1067*e4b17023SJohn Marino for (reg = j; reg < j + nregs; reg++)
1068*e4b17023SJohn Marino {
1069*e4b17023SJohn Marino /* Use QImode since that's guaranteed to clobber just
1070*e4b17023SJohn Marino * one reg. */
1071*e4b17023SJohn Marino clobbered_reg = gen_rtx_REG (QImode, reg);
1072*e4b17023SJohn Marino
1073*e4b17023SJohn Marino /* Do sanity check for overlap between clobbers and
1074*e4b17023SJohn Marino respectively input and outputs that hasn't been
1075*e4b17023SJohn Marino handled. Such overlap should have been detected and
1076*e4b17023SJohn Marino reported above. */
1077*e4b17023SJohn Marino if (!clobber_conflict_found)
1078*e4b17023SJohn Marino {
1079*e4b17023SJohn Marino int opno;
1080*e4b17023SJohn Marino
1081*e4b17023SJohn Marino /* We test the old body (obody) contents to avoid
1082*e4b17023SJohn Marino tripping over the under-construction body. */
1083*e4b17023SJohn Marino for (opno = 0; opno < noutputs; opno++)
1084*e4b17023SJohn Marino if (reg_overlap_mentioned_p (clobbered_reg,
1085*e4b17023SJohn Marino output_rtx[opno]))
1086*e4b17023SJohn Marino internal_error
1087*e4b17023SJohn Marino ("asm clobber conflict with output operand");
1088*e4b17023SJohn Marino
1089*e4b17023SJohn Marino for (opno = 0; opno < ninputs - ninout; opno++)
1090*e4b17023SJohn Marino if (reg_overlap_mentioned_p (clobbered_reg,
1091*e4b17023SJohn Marino ASM_OPERANDS_INPUT (obody,
1092*e4b17023SJohn Marino opno)))
1093*e4b17023SJohn Marino internal_error
1094*e4b17023SJohn Marino ("asm clobber conflict with input operand");
1095*e4b17023SJohn Marino }
1096*e4b17023SJohn Marino
1097*e4b17023SJohn Marino XVECEXP (body, 0, i++)
1098*e4b17023SJohn Marino = gen_rtx_CLOBBER (VOIDmode, clobbered_reg);
1099*e4b17023SJohn Marino }
1100*e4b17023SJohn Marino }
1101*e4b17023SJohn Marino
1102*e4b17023SJohn Marino if (nlabels > 0)
1103*e4b17023SJohn Marino emit_jump_insn (body);
1104*e4b17023SJohn Marino else
1105*e4b17023SJohn Marino emit_insn (body);
1106*e4b17023SJohn Marino }
1107*e4b17023SJohn Marino
1108*e4b17023SJohn Marino /* For any outputs that needed reloading into registers, spill them
1109*e4b17023SJohn Marino back to where they belong. */
1110*e4b17023SJohn Marino for (i = 0; i < noutputs; ++i)
1111*e4b17023SJohn Marino if (real_output_rtx[i])
1112*e4b17023SJohn Marino emit_move_insn (real_output_rtx[i], output_rtx[i]);
1113*e4b17023SJohn Marino
1114*e4b17023SJohn Marino crtl->has_asm_statement = 1;
1115*e4b17023SJohn Marino free_temp_slots ();
1116*e4b17023SJohn Marino }
1117*e4b17023SJohn Marino
1118*e4b17023SJohn Marino void
expand_asm_stmt(gimple stmt)1119*e4b17023SJohn Marino expand_asm_stmt (gimple stmt)
1120*e4b17023SJohn Marino {
1121*e4b17023SJohn Marino int noutputs;
1122*e4b17023SJohn Marino tree outputs, tail, t;
1123*e4b17023SJohn Marino tree *o;
1124*e4b17023SJohn Marino size_t i, n;
1125*e4b17023SJohn Marino const char *s;
1126*e4b17023SJohn Marino tree str, out, in, cl, labels;
1127*e4b17023SJohn Marino location_t locus = gimple_location (stmt);
1128*e4b17023SJohn Marino
1129*e4b17023SJohn Marino /* Meh... convert the gimple asm operands into real tree lists.
1130*e4b17023SJohn Marino Eventually we should make all routines work on the vectors instead
1131*e4b17023SJohn Marino of relying on TREE_CHAIN. */
1132*e4b17023SJohn Marino out = NULL_TREE;
1133*e4b17023SJohn Marino n = gimple_asm_noutputs (stmt);
1134*e4b17023SJohn Marino if (n > 0)
1135*e4b17023SJohn Marino {
1136*e4b17023SJohn Marino t = out = gimple_asm_output_op (stmt, 0);
1137*e4b17023SJohn Marino for (i = 1; i < n; i++)
1138*e4b17023SJohn Marino t = TREE_CHAIN (t) = gimple_asm_output_op (stmt, i);
1139*e4b17023SJohn Marino }
1140*e4b17023SJohn Marino
1141*e4b17023SJohn Marino in = NULL_TREE;
1142*e4b17023SJohn Marino n = gimple_asm_ninputs (stmt);
1143*e4b17023SJohn Marino if (n > 0)
1144*e4b17023SJohn Marino {
1145*e4b17023SJohn Marino t = in = gimple_asm_input_op (stmt, 0);
1146*e4b17023SJohn Marino for (i = 1; i < n; i++)
1147*e4b17023SJohn Marino t = TREE_CHAIN (t) = gimple_asm_input_op (stmt, i);
1148*e4b17023SJohn Marino }
1149*e4b17023SJohn Marino
1150*e4b17023SJohn Marino cl = NULL_TREE;
1151*e4b17023SJohn Marino n = gimple_asm_nclobbers (stmt);
1152*e4b17023SJohn Marino if (n > 0)
1153*e4b17023SJohn Marino {
1154*e4b17023SJohn Marino t = cl = gimple_asm_clobber_op (stmt, 0);
1155*e4b17023SJohn Marino for (i = 1; i < n; i++)
1156*e4b17023SJohn Marino t = TREE_CHAIN (t) = gimple_asm_clobber_op (stmt, i);
1157*e4b17023SJohn Marino }
1158*e4b17023SJohn Marino
1159*e4b17023SJohn Marino labels = NULL_TREE;
1160*e4b17023SJohn Marino n = gimple_asm_nlabels (stmt);
1161*e4b17023SJohn Marino if (n > 0)
1162*e4b17023SJohn Marino {
1163*e4b17023SJohn Marino t = labels = gimple_asm_label_op (stmt, 0);
1164*e4b17023SJohn Marino for (i = 1; i < n; i++)
1165*e4b17023SJohn Marino t = TREE_CHAIN (t) = gimple_asm_label_op (stmt, i);
1166*e4b17023SJohn Marino }
1167*e4b17023SJohn Marino
1168*e4b17023SJohn Marino s = gimple_asm_string (stmt);
1169*e4b17023SJohn Marino str = build_string (strlen (s), s);
1170*e4b17023SJohn Marino
1171*e4b17023SJohn Marino if (gimple_asm_input_p (stmt))
1172*e4b17023SJohn Marino {
1173*e4b17023SJohn Marino expand_asm_loc (str, gimple_asm_volatile_p (stmt), locus);
1174*e4b17023SJohn Marino return;
1175*e4b17023SJohn Marino }
1176*e4b17023SJohn Marino
1177*e4b17023SJohn Marino outputs = out;
1178*e4b17023SJohn Marino noutputs = gimple_asm_noutputs (stmt);
1179*e4b17023SJohn Marino /* o[I] is the place that output number I should be written. */
1180*e4b17023SJohn Marino o = (tree *) alloca (noutputs * sizeof (tree));
1181*e4b17023SJohn Marino
1182*e4b17023SJohn Marino /* Record the contents of OUTPUTS before it is modified. */
1183*e4b17023SJohn Marino for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1184*e4b17023SJohn Marino o[i] = TREE_VALUE (tail);
1185*e4b17023SJohn Marino
1186*e4b17023SJohn Marino /* Generate the ASM_OPERANDS insn; store into the TREE_VALUEs of
1187*e4b17023SJohn Marino OUTPUTS some trees for where the values were actually stored. */
1188*e4b17023SJohn Marino expand_asm_operands (str, outputs, in, cl, labels,
1189*e4b17023SJohn Marino gimple_asm_volatile_p (stmt), locus);
1190*e4b17023SJohn Marino
1191*e4b17023SJohn Marino /* Copy all the intermediate outputs into the specified outputs. */
1192*e4b17023SJohn Marino for (i = 0, tail = outputs; tail; tail = TREE_CHAIN (tail), i++)
1193*e4b17023SJohn Marino {
1194*e4b17023SJohn Marino if (o[i] != TREE_VALUE (tail))
1195*e4b17023SJohn Marino {
1196*e4b17023SJohn Marino expand_assignment (o[i], TREE_VALUE (tail), false);
1197*e4b17023SJohn Marino free_temp_slots ();
1198*e4b17023SJohn Marino
1199*e4b17023SJohn Marino /* Restore the original value so that it's correct the next
1200*e4b17023SJohn Marino time we expand this function. */
1201*e4b17023SJohn Marino TREE_VALUE (tail) = o[i];
1202*e4b17023SJohn Marino }
1203*e4b17023SJohn Marino }
1204*e4b17023SJohn Marino }
1205*e4b17023SJohn Marino
1206*e4b17023SJohn Marino /* A subroutine of expand_asm_operands. Check that all operands have
1207*e4b17023SJohn Marino the same number of alternatives. Return true if so. */
1208*e4b17023SJohn Marino
1209*e4b17023SJohn Marino static bool
check_operand_nalternatives(tree outputs,tree inputs)1210*e4b17023SJohn Marino check_operand_nalternatives (tree outputs, tree inputs)
1211*e4b17023SJohn Marino {
1212*e4b17023SJohn Marino if (outputs || inputs)
1213*e4b17023SJohn Marino {
1214*e4b17023SJohn Marino tree tmp = TREE_PURPOSE (outputs ? outputs : inputs);
1215*e4b17023SJohn Marino int nalternatives
1216*e4b17023SJohn Marino = n_occurrences (',', TREE_STRING_POINTER (TREE_VALUE (tmp)));
1217*e4b17023SJohn Marino tree next = inputs;
1218*e4b17023SJohn Marino
1219*e4b17023SJohn Marino if (nalternatives + 1 > MAX_RECOG_ALTERNATIVES)
1220*e4b17023SJohn Marino {
1221*e4b17023SJohn Marino error ("too many alternatives in %<asm%>");
1222*e4b17023SJohn Marino return false;
1223*e4b17023SJohn Marino }
1224*e4b17023SJohn Marino
1225*e4b17023SJohn Marino tmp = outputs;
1226*e4b17023SJohn Marino while (tmp)
1227*e4b17023SJohn Marino {
1228*e4b17023SJohn Marino const char *constraint
1229*e4b17023SJohn Marino = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (tmp)));
1230*e4b17023SJohn Marino
1231*e4b17023SJohn Marino if (n_occurrences (',', constraint) != nalternatives)
1232*e4b17023SJohn Marino {
1233*e4b17023SJohn Marino error ("operand constraints for %<asm%> differ "
1234*e4b17023SJohn Marino "in number of alternatives");
1235*e4b17023SJohn Marino return false;
1236*e4b17023SJohn Marino }
1237*e4b17023SJohn Marino
1238*e4b17023SJohn Marino if (TREE_CHAIN (tmp))
1239*e4b17023SJohn Marino tmp = TREE_CHAIN (tmp);
1240*e4b17023SJohn Marino else
1241*e4b17023SJohn Marino tmp = next, next = 0;
1242*e4b17023SJohn Marino }
1243*e4b17023SJohn Marino }
1244*e4b17023SJohn Marino
1245*e4b17023SJohn Marino return true;
1246*e4b17023SJohn Marino }
1247*e4b17023SJohn Marino
1248*e4b17023SJohn Marino /* A subroutine of expand_asm_operands. Check that all operand names
1249*e4b17023SJohn Marino are unique. Return true if so. We rely on the fact that these names
1250*e4b17023SJohn Marino are identifiers, and so have been canonicalized by get_identifier,
1251*e4b17023SJohn Marino so all we need are pointer comparisons. */
1252*e4b17023SJohn Marino
1253*e4b17023SJohn Marino static bool
check_unique_operand_names(tree outputs,tree inputs,tree labels)1254*e4b17023SJohn Marino check_unique_operand_names (tree outputs, tree inputs, tree labels)
1255*e4b17023SJohn Marino {
1256*e4b17023SJohn Marino tree i, j, i_name = NULL_TREE;
1257*e4b17023SJohn Marino
1258*e4b17023SJohn Marino for (i = outputs; i ; i = TREE_CHAIN (i))
1259*e4b17023SJohn Marino {
1260*e4b17023SJohn Marino i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1261*e4b17023SJohn Marino if (! i_name)
1262*e4b17023SJohn Marino continue;
1263*e4b17023SJohn Marino
1264*e4b17023SJohn Marino for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1265*e4b17023SJohn Marino if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1266*e4b17023SJohn Marino goto failure;
1267*e4b17023SJohn Marino }
1268*e4b17023SJohn Marino
1269*e4b17023SJohn Marino for (i = inputs; i ; i = TREE_CHAIN (i))
1270*e4b17023SJohn Marino {
1271*e4b17023SJohn Marino i_name = TREE_PURPOSE (TREE_PURPOSE (i));
1272*e4b17023SJohn Marino if (! i_name)
1273*e4b17023SJohn Marino continue;
1274*e4b17023SJohn Marino
1275*e4b17023SJohn Marino for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1276*e4b17023SJohn Marino if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1277*e4b17023SJohn Marino goto failure;
1278*e4b17023SJohn Marino for (j = outputs; j ; j = TREE_CHAIN (j))
1279*e4b17023SJohn Marino if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1280*e4b17023SJohn Marino goto failure;
1281*e4b17023SJohn Marino }
1282*e4b17023SJohn Marino
1283*e4b17023SJohn Marino for (i = labels; i ; i = TREE_CHAIN (i))
1284*e4b17023SJohn Marino {
1285*e4b17023SJohn Marino i_name = TREE_PURPOSE (i);
1286*e4b17023SJohn Marino if (! i_name)
1287*e4b17023SJohn Marino continue;
1288*e4b17023SJohn Marino
1289*e4b17023SJohn Marino for (j = TREE_CHAIN (i); j ; j = TREE_CHAIN (j))
1290*e4b17023SJohn Marino if (simple_cst_equal (i_name, TREE_PURPOSE (j)))
1291*e4b17023SJohn Marino goto failure;
1292*e4b17023SJohn Marino for (j = inputs; j ; j = TREE_CHAIN (j))
1293*e4b17023SJohn Marino if (simple_cst_equal (i_name, TREE_PURPOSE (TREE_PURPOSE (j))))
1294*e4b17023SJohn Marino goto failure;
1295*e4b17023SJohn Marino }
1296*e4b17023SJohn Marino
1297*e4b17023SJohn Marino return true;
1298*e4b17023SJohn Marino
1299*e4b17023SJohn Marino failure:
1300*e4b17023SJohn Marino error ("duplicate asm operand name %qs", TREE_STRING_POINTER (i_name));
1301*e4b17023SJohn Marino return false;
1302*e4b17023SJohn Marino }
1303*e4b17023SJohn Marino
1304*e4b17023SJohn Marino /* A subroutine of expand_asm_operands. Resolve the names of the operands
1305*e4b17023SJohn Marino in *POUTPUTS and *PINPUTS to numbers, and replace the name expansions in
1306*e4b17023SJohn Marino STRING and in the constraints to those numbers. */
1307*e4b17023SJohn Marino
1308*e4b17023SJohn Marino tree
resolve_asm_operand_names(tree string,tree outputs,tree inputs,tree labels)1309*e4b17023SJohn Marino resolve_asm_operand_names (tree string, tree outputs, tree inputs, tree labels)
1310*e4b17023SJohn Marino {
1311*e4b17023SJohn Marino char *buffer;
1312*e4b17023SJohn Marino char *p;
1313*e4b17023SJohn Marino const char *c;
1314*e4b17023SJohn Marino tree t;
1315*e4b17023SJohn Marino
1316*e4b17023SJohn Marino check_unique_operand_names (outputs, inputs, labels);
1317*e4b17023SJohn Marino
1318*e4b17023SJohn Marino /* Substitute [<name>] in input constraint strings. There should be no
1319*e4b17023SJohn Marino named operands in output constraints. */
1320*e4b17023SJohn Marino for (t = inputs; t ; t = TREE_CHAIN (t))
1321*e4b17023SJohn Marino {
1322*e4b17023SJohn Marino c = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (t)));
1323*e4b17023SJohn Marino if (strchr (c, '[') != NULL)
1324*e4b17023SJohn Marino {
1325*e4b17023SJohn Marino p = buffer = xstrdup (c);
1326*e4b17023SJohn Marino while ((p = strchr (p, '[')) != NULL)
1327*e4b17023SJohn Marino p = resolve_operand_name_1 (p, outputs, inputs, NULL);
1328*e4b17023SJohn Marino TREE_VALUE (TREE_PURPOSE (t))
1329*e4b17023SJohn Marino = build_string (strlen (buffer), buffer);
1330*e4b17023SJohn Marino free (buffer);
1331*e4b17023SJohn Marino }
1332*e4b17023SJohn Marino }
1333*e4b17023SJohn Marino
1334*e4b17023SJohn Marino /* Now check for any needed substitutions in the template. */
1335*e4b17023SJohn Marino c = TREE_STRING_POINTER (string);
1336*e4b17023SJohn Marino while ((c = strchr (c, '%')) != NULL)
1337*e4b17023SJohn Marino {
1338*e4b17023SJohn Marino if (c[1] == '[')
1339*e4b17023SJohn Marino break;
1340*e4b17023SJohn Marino else if (ISALPHA (c[1]) && c[2] == '[')
1341*e4b17023SJohn Marino break;
1342*e4b17023SJohn Marino else
1343*e4b17023SJohn Marino {
1344*e4b17023SJohn Marino c += 1 + (c[1] == '%');
1345*e4b17023SJohn Marino continue;
1346*e4b17023SJohn Marino }
1347*e4b17023SJohn Marino }
1348*e4b17023SJohn Marino
1349*e4b17023SJohn Marino if (c)
1350*e4b17023SJohn Marino {
1351*e4b17023SJohn Marino /* OK, we need to make a copy so we can perform the substitutions.
1352*e4b17023SJohn Marino Assume that we will not need extra space--we get to remove '['
1353*e4b17023SJohn Marino and ']', which means we cannot have a problem until we have more
1354*e4b17023SJohn Marino than 999 operands. */
1355*e4b17023SJohn Marino buffer = xstrdup (TREE_STRING_POINTER (string));
1356*e4b17023SJohn Marino p = buffer + (c - TREE_STRING_POINTER (string));
1357*e4b17023SJohn Marino
1358*e4b17023SJohn Marino while ((p = strchr (p, '%')) != NULL)
1359*e4b17023SJohn Marino {
1360*e4b17023SJohn Marino if (p[1] == '[')
1361*e4b17023SJohn Marino p += 1;
1362*e4b17023SJohn Marino else if (ISALPHA (p[1]) && p[2] == '[')
1363*e4b17023SJohn Marino p += 2;
1364*e4b17023SJohn Marino else
1365*e4b17023SJohn Marino {
1366*e4b17023SJohn Marino p += 1 + (p[1] == '%');
1367*e4b17023SJohn Marino continue;
1368*e4b17023SJohn Marino }
1369*e4b17023SJohn Marino
1370*e4b17023SJohn Marino p = resolve_operand_name_1 (p, outputs, inputs, labels);
1371*e4b17023SJohn Marino }
1372*e4b17023SJohn Marino
1373*e4b17023SJohn Marino string = build_string (strlen (buffer), buffer);
1374*e4b17023SJohn Marino free (buffer);
1375*e4b17023SJohn Marino }
1376*e4b17023SJohn Marino
1377*e4b17023SJohn Marino return string;
1378*e4b17023SJohn Marino }
1379*e4b17023SJohn Marino
1380*e4b17023SJohn Marino /* A subroutine of resolve_operand_names. P points to the '[' for a
1381*e4b17023SJohn Marino potential named operand of the form [<name>]. In place, replace
1382*e4b17023SJohn Marino the name and brackets with a number. Return a pointer to the
1383*e4b17023SJohn Marino balance of the string after substitution. */
1384*e4b17023SJohn Marino
1385*e4b17023SJohn Marino static char *
resolve_operand_name_1(char * p,tree outputs,tree inputs,tree labels)1386*e4b17023SJohn Marino resolve_operand_name_1 (char *p, tree outputs, tree inputs, tree labels)
1387*e4b17023SJohn Marino {
1388*e4b17023SJohn Marino char *q;
1389*e4b17023SJohn Marino int op;
1390*e4b17023SJohn Marino tree t;
1391*e4b17023SJohn Marino
1392*e4b17023SJohn Marino /* Collect the operand name. */
1393*e4b17023SJohn Marino q = strchr (++p, ']');
1394*e4b17023SJohn Marino if (!q)
1395*e4b17023SJohn Marino {
1396*e4b17023SJohn Marino error ("missing close brace for named operand");
1397*e4b17023SJohn Marino return strchr (p, '\0');
1398*e4b17023SJohn Marino }
1399*e4b17023SJohn Marino *q = '\0';
1400*e4b17023SJohn Marino
1401*e4b17023SJohn Marino /* Resolve the name to a number. */
1402*e4b17023SJohn Marino for (op = 0, t = outputs; t ; t = TREE_CHAIN (t), op++)
1403*e4b17023SJohn Marino {
1404*e4b17023SJohn Marino tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1405*e4b17023SJohn Marino if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1406*e4b17023SJohn Marino goto found;
1407*e4b17023SJohn Marino }
1408*e4b17023SJohn Marino for (t = inputs; t ; t = TREE_CHAIN (t), op++)
1409*e4b17023SJohn Marino {
1410*e4b17023SJohn Marino tree name = TREE_PURPOSE (TREE_PURPOSE (t));
1411*e4b17023SJohn Marino if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1412*e4b17023SJohn Marino goto found;
1413*e4b17023SJohn Marino }
1414*e4b17023SJohn Marino for (t = labels; t ; t = TREE_CHAIN (t), op++)
1415*e4b17023SJohn Marino {
1416*e4b17023SJohn Marino tree name = TREE_PURPOSE (t);
1417*e4b17023SJohn Marino if (name && strcmp (TREE_STRING_POINTER (name), p) == 0)
1418*e4b17023SJohn Marino goto found;
1419*e4b17023SJohn Marino }
1420*e4b17023SJohn Marino
1421*e4b17023SJohn Marino error ("undefined named operand %qs", identifier_to_locale (p));
1422*e4b17023SJohn Marino op = 0;
1423*e4b17023SJohn Marino
1424*e4b17023SJohn Marino found:
1425*e4b17023SJohn Marino /* Replace the name with the number. Unfortunately, not all libraries
1426*e4b17023SJohn Marino get the return value of sprintf correct, so search for the end of the
1427*e4b17023SJohn Marino generated string by hand. */
1428*e4b17023SJohn Marino sprintf (--p, "%d", op);
1429*e4b17023SJohn Marino p = strchr (p, '\0');
1430*e4b17023SJohn Marino
1431*e4b17023SJohn Marino /* Verify the no extra buffer space assumption. */
1432*e4b17023SJohn Marino gcc_assert (p <= q);
1433*e4b17023SJohn Marino
1434*e4b17023SJohn Marino /* Shift the rest of the buffer down to fill the gap. */
1435*e4b17023SJohn Marino memmove (p, q + 1, strlen (q + 1) + 1);
1436*e4b17023SJohn Marino
1437*e4b17023SJohn Marino return p;
1438*e4b17023SJohn Marino }
1439*e4b17023SJohn Marino
1440*e4b17023SJohn Marino /* Generate RTL to evaluate the expression EXP. */
1441*e4b17023SJohn Marino
1442*e4b17023SJohn Marino void
expand_expr_stmt(tree exp)1443*e4b17023SJohn Marino expand_expr_stmt (tree exp)
1444*e4b17023SJohn Marino {
1445*e4b17023SJohn Marino rtx value;
1446*e4b17023SJohn Marino tree type;
1447*e4b17023SJohn Marino
1448*e4b17023SJohn Marino value = expand_expr (exp, const0_rtx, VOIDmode, EXPAND_NORMAL);
1449*e4b17023SJohn Marino type = TREE_TYPE (exp);
1450*e4b17023SJohn Marino
1451*e4b17023SJohn Marino /* If all we do is reference a volatile value in memory,
1452*e4b17023SJohn Marino copy it to a register to be sure it is actually touched. */
1453*e4b17023SJohn Marino if (value && MEM_P (value) && TREE_THIS_VOLATILE (exp))
1454*e4b17023SJohn Marino {
1455*e4b17023SJohn Marino if (TYPE_MODE (type) == VOIDmode)
1456*e4b17023SJohn Marino ;
1457*e4b17023SJohn Marino else if (TYPE_MODE (type) != BLKmode)
1458*e4b17023SJohn Marino copy_to_reg (value);
1459*e4b17023SJohn Marino else
1460*e4b17023SJohn Marino {
1461*e4b17023SJohn Marino rtx lab = gen_label_rtx ();
1462*e4b17023SJohn Marino
1463*e4b17023SJohn Marino /* Compare the value with itself to reference it. */
1464*e4b17023SJohn Marino emit_cmp_and_jump_insns (value, value, EQ,
1465*e4b17023SJohn Marino expand_normal (TYPE_SIZE (type)),
1466*e4b17023SJohn Marino BLKmode, 0, lab);
1467*e4b17023SJohn Marino emit_label (lab);
1468*e4b17023SJohn Marino }
1469*e4b17023SJohn Marino }
1470*e4b17023SJohn Marino
1471*e4b17023SJohn Marino /* Free any temporaries used to evaluate this expression. */
1472*e4b17023SJohn Marino free_temp_slots ();
1473*e4b17023SJohn Marino }
1474*e4b17023SJohn Marino
1475*e4b17023SJohn Marino /* Warn if EXP contains any computations whose results are not used.
1476*e4b17023SJohn Marino Return 1 if a warning is printed; 0 otherwise. LOCUS is the
1477*e4b17023SJohn Marino (potential) location of the expression. */
1478*e4b17023SJohn Marino
1479*e4b17023SJohn Marino int
warn_if_unused_value(const_tree exp,location_t locus)1480*e4b17023SJohn Marino warn_if_unused_value (const_tree exp, location_t locus)
1481*e4b17023SJohn Marino {
1482*e4b17023SJohn Marino restart:
1483*e4b17023SJohn Marino if (TREE_USED (exp) || TREE_NO_WARNING (exp))
1484*e4b17023SJohn Marino return 0;
1485*e4b17023SJohn Marino
1486*e4b17023SJohn Marino /* Don't warn about void constructs. This includes casting to void,
1487*e4b17023SJohn Marino void function calls, and statement expressions with a final cast
1488*e4b17023SJohn Marino to void. */
1489*e4b17023SJohn Marino if (VOID_TYPE_P (TREE_TYPE (exp)))
1490*e4b17023SJohn Marino return 0;
1491*e4b17023SJohn Marino
1492*e4b17023SJohn Marino if (EXPR_HAS_LOCATION (exp))
1493*e4b17023SJohn Marino locus = EXPR_LOCATION (exp);
1494*e4b17023SJohn Marino
1495*e4b17023SJohn Marino switch (TREE_CODE (exp))
1496*e4b17023SJohn Marino {
1497*e4b17023SJohn Marino case PREINCREMENT_EXPR:
1498*e4b17023SJohn Marino case POSTINCREMENT_EXPR:
1499*e4b17023SJohn Marino case PREDECREMENT_EXPR:
1500*e4b17023SJohn Marino case POSTDECREMENT_EXPR:
1501*e4b17023SJohn Marino case MODIFY_EXPR:
1502*e4b17023SJohn Marino case INIT_EXPR:
1503*e4b17023SJohn Marino case TARGET_EXPR:
1504*e4b17023SJohn Marino case CALL_EXPR:
1505*e4b17023SJohn Marino case TRY_CATCH_EXPR:
1506*e4b17023SJohn Marino case WITH_CLEANUP_EXPR:
1507*e4b17023SJohn Marino case EXIT_EXPR:
1508*e4b17023SJohn Marino case VA_ARG_EXPR:
1509*e4b17023SJohn Marino return 0;
1510*e4b17023SJohn Marino
1511*e4b17023SJohn Marino case BIND_EXPR:
1512*e4b17023SJohn Marino /* For a binding, warn if no side effect within it. */
1513*e4b17023SJohn Marino exp = BIND_EXPR_BODY (exp);
1514*e4b17023SJohn Marino goto restart;
1515*e4b17023SJohn Marino
1516*e4b17023SJohn Marino case SAVE_EXPR:
1517*e4b17023SJohn Marino case NON_LVALUE_EXPR:
1518*e4b17023SJohn Marino exp = TREE_OPERAND (exp, 0);
1519*e4b17023SJohn Marino goto restart;
1520*e4b17023SJohn Marino
1521*e4b17023SJohn Marino case TRUTH_ORIF_EXPR:
1522*e4b17023SJohn Marino case TRUTH_ANDIF_EXPR:
1523*e4b17023SJohn Marino /* In && or ||, warn if 2nd operand has no side effect. */
1524*e4b17023SJohn Marino exp = TREE_OPERAND (exp, 1);
1525*e4b17023SJohn Marino goto restart;
1526*e4b17023SJohn Marino
1527*e4b17023SJohn Marino case COMPOUND_EXPR:
1528*e4b17023SJohn Marino if (warn_if_unused_value (TREE_OPERAND (exp, 0), locus))
1529*e4b17023SJohn Marino return 1;
1530*e4b17023SJohn Marino /* Let people do `(foo (), 0)' without a warning. */
1531*e4b17023SJohn Marino if (TREE_CONSTANT (TREE_OPERAND (exp, 1)))
1532*e4b17023SJohn Marino return 0;
1533*e4b17023SJohn Marino exp = TREE_OPERAND (exp, 1);
1534*e4b17023SJohn Marino goto restart;
1535*e4b17023SJohn Marino
1536*e4b17023SJohn Marino case COND_EXPR:
1537*e4b17023SJohn Marino /* If this is an expression with side effects, don't warn; this
1538*e4b17023SJohn Marino case commonly appears in macro expansions. */
1539*e4b17023SJohn Marino if (TREE_SIDE_EFFECTS (exp))
1540*e4b17023SJohn Marino return 0;
1541*e4b17023SJohn Marino goto warn;
1542*e4b17023SJohn Marino
1543*e4b17023SJohn Marino case INDIRECT_REF:
1544*e4b17023SJohn Marino /* Don't warn about automatic dereferencing of references, since
1545*e4b17023SJohn Marino the user cannot control it. */
1546*e4b17023SJohn Marino if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == REFERENCE_TYPE)
1547*e4b17023SJohn Marino {
1548*e4b17023SJohn Marino exp = TREE_OPERAND (exp, 0);
1549*e4b17023SJohn Marino goto restart;
1550*e4b17023SJohn Marino }
1551*e4b17023SJohn Marino /* Fall through. */
1552*e4b17023SJohn Marino
1553*e4b17023SJohn Marino default:
1554*e4b17023SJohn Marino /* Referencing a volatile value is a side effect, so don't warn. */
1555*e4b17023SJohn Marino if ((DECL_P (exp) || REFERENCE_CLASS_P (exp))
1556*e4b17023SJohn Marino && TREE_THIS_VOLATILE (exp))
1557*e4b17023SJohn Marino return 0;
1558*e4b17023SJohn Marino
1559*e4b17023SJohn Marino /* If this is an expression which has no operands, there is no value
1560*e4b17023SJohn Marino to be unused. There are no such language-independent codes,
1561*e4b17023SJohn Marino but front ends may define such. */
1562*e4b17023SJohn Marino if (EXPRESSION_CLASS_P (exp) && TREE_OPERAND_LENGTH (exp) == 0)
1563*e4b17023SJohn Marino return 0;
1564*e4b17023SJohn Marino
1565*e4b17023SJohn Marino warn:
1566*e4b17023SJohn Marino warning_at (locus, OPT_Wunused_value, "value computed is not used");
1567*e4b17023SJohn Marino return 1;
1568*e4b17023SJohn Marino }
1569*e4b17023SJohn Marino }
1570*e4b17023SJohn Marino
1571*e4b17023SJohn Marino
1572*e4b17023SJohn Marino /* Generate RTL to return from the current function, with no value.
1573*e4b17023SJohn Marino (That is, we do not do anything about returning any value.) */
1574*e4b17023SJohn Marino
1575*e4b17023SJohn Marino void
expand_null_return(void)1576*e4b17023SJohn Marino expand_null_return (void)
1577*e4b17023SJohn Marino {
1578*e4b17023SJohn Marino /* If this function was declared to return a value, but we
1579*e4b17023SJohn Marino didn't, clobber the return registers so that they are not
1580*e4b17023SJohn Marino propagated live to the rest of the function. */
1581*e4b17023SJohn Marino clobber_return_register ();
1582*e4b17023SJohn Marino
1583*e4b17023SJohn Marino expand_null_return_1 ();
1584*e4b17023SJohn Marino }
1585*e4b17023SJohn Marino
1586*e4b17023SJohn Marino /* Generate RTL to return directly from the current function.
1587*e4b17023SJohn Marino (That is, we bypass any return value.) */
1588*e4b17023SJohn Marino
1589*e4b17023SJohn Marino void
expand_naked_return(void)1590*e4b17023SJohn Marino expand_naked_return (void)
1591*e4b17023SJohn Marino {
1592*e4b17023SJohn Marino rtx end_label;
1593*e4b17023SJohn Marino
1594*e4b17023SJohn Marino clear_pending_stack_adjust ();
1595*e4b17023SJohn Marino do_pending_stack_adjust ();
1596*e4b17023SJohn Marino
1597*e4b17023SJohn Marino end_label = naked_return_label;
1598*e4b17023SJohn Marino if (end_label == 0)
1599*e4b17023SJohn Marino end_label = naked_return_label = gen_label_rtx ();
1600*e4b17023SJohn Marino
1601*e4b17023SJohn Marino emit_jump (end_label);
1602*e4b17023SJohn Marino }
1603*e4b17023SJohn Marino
1604*e4b17023SJohn Marino /* Generate RTL to return from the current function, with value VAL. */
1605*e4b17023SJohn Marino
1606*e4b17023SJohn Marino static void
expand_value_return(rtx val)1607*e4b17023SJohn Marino expand_value_return (rtx val)
1608*e4b17023SJohn Marino {
1609*e4b17023SJohn Marino /* Copy the value to the return location unless it's already there. */
1610*e4b17023SJohn Marino
1611*e4b17023SJohn Marino tree decl = DECL_RESULT (current_function_decl);
1612*e4b17023SJohn Marino rtx return_reg = DECL_RTL (decl);
1613*e4b17023SJohn Marino if (return_reg != val)
1614*e4b17023SJohn Marino {
1615*e4b17023SJohn Marino tree funtype = TREE_TYPE (current_function_decl);
1616*e4b17023SJohn Marino tree type = TREE_TYPE (decl);
1617*e4b17023SJohn Marino int unsignedp = TYPE_UNSIGNED (type);
1618*e4b17023SJohn Marino enum machine_mode old_mode = DECL_MODE (decl);
1619*e4b17023SJohn Marino enum machine_mode mode;
1620*e4b17023SJohn Marino if (DECL_BY_REFERENCE (decl))
1621*e4b17023SJohn Marino mode = promote_function_mode (type, old_mode, &unsignedp, funtype, 2);
1622*e4b17023SJohn Marino else
1623*e4b17023SJohn Marino mode = promote_function_mode (type, old_mode, &unsignedp, funtype, 1);
1624*e4b17023SJohn Marino
1625*e4b17023SJohn Marino if (mode != old_mode)
1626*e4b17023SJohn Marino val = convert_modes (mode, old_mode, val, unsignedp);
1627*e4b17023SJohn Marino
1628*e4b17023SJohn Marino if (GET_CODE (return_reg) == PARALLEL)
1629*e4b17023SJohn Marino emit_group_load (return_reg, val, type, int_size_in_bytes (type));
1630*e4b17023SJohn Marino else
1631*e4b17023SJohn Marino emit_move_insn (return_reg, val);
1632*e4b17023SJohn Marino }
1633*e4b17023SJohn Marino
1634*e4b17023SJohn Marino expand_null_return_1 ();
1635*e4b17023SJohn Marino }
1636*e4b17023SJohn Marino
1637*e4b17023SJohn Marino /* Output a return with no value. */
1638*e4b17023SJohn Marino
1639*e4b17023SJohn Marino static void
expand_null_return_1(void)1640*e4b17023SJohn Marino expand_null_return_1 (void)
1641*e4b17023SJohn Marino {
1642*e4b17023SJohn Marino clear_pending_stack_adjust ();
1643*e4b17023SJohn Marino do_pending_stack_adjust ();
1644*e4b17023SJohn Marino emit_jump (return_label);
1645*e4b17023SJohn Marino }
1646*e4b17023SJohn Marino
1647*e4b17023SJohn Marino /* Generate RTL to evaluate the expression RETVAL and return it
1648*e4b17023SJohn Marino from the current function. */
1649*e4b17023SJohn Marino
1650*e4b17023SJohn Marino void
expand_return(tree retval)1651*e4b17023SJohn Marino expand_return (tree retval)
1652*e4b17023SJohn Marino {
1653*e4b17023SJohn Marino rtx result_rtl;
1654*e4b17023SJohn Marino rtx val = 0;
1655*e4b17023SJohn Marino tree retval_rhs;
1656*e4b17023SJohn Marino
1657*e4b17023SJohn Marino /* If function wants no value, give it none. */
1658*e4b17023SJohn Marino if (TREE_CODE (TREE_TYPE (TREE_TYPE (current_function_decl))) == VOID_TYPE)
1659*e4b17023SJohn Marino {
1660*e4b17023SJohn Marino expand_normal (retval);
1661*e4b17023SJohn Marino expand_null_return ();
1662*e4b17023SJohn Marino return;
1663*e4b17023SJohn Marino }
1664*e4b17023SJohn Marino
1665*e4b17023SJohn Marino if (retval == error_mark_node)
1666*e4b17023SJohn Marino {
1667*e4b17023SJohn Marino /* Treat this like a return of no value from a function that
1668*e4b17023SJohn Marino returns a value. */
1669*e4b17023SJohn Marino expand_null_return ();
1670*e4b17023SJohn Marino return;
1671*e4b17023SJohn Marino }
1672*e4b17023SJohn Marino else if ((TREE_CODE (retval) == MODIFY_EXPR
1673*e4b17023SJohn Marino || TREE_CODE (retval) == INIT_EXPR)
1674*e4b17023SJohn Marino && TREE_CODE (TREE_OPERAND (retval, 0)) == RESULT_DECL)
1675*e4b17023SJohn Marino retval_rhs = TREE_OPERAND (retval, 1);
1676*e4b17023SJohn Marino else
1677*e4b17023SJohn Marino retval_rhs = retval;
1678*e4b17023SJohn Marino
1679*e4b17023SJohn Marino result_rtl = DECL_RTL (DECL_RESULT (current_function_decl));
1680*e4b17023SJohn Marino
1681*e4b17023SJohn Marino /* If we are returning the RESULT_DECL, then the value has already
1682*e4b17023SJohn Marino been stored into it, so we don't have to do anything special. */
1683*e4b17023SJohn Marino if (TREE_CODE (retval_rhs) == RESULT_DECL)
1684*e4b17023SJohn Marino expand_value_return (result_rtl);
1685*e4b17023SJohn Marino
1686*e4b17023SJohn Marino /* If the result is an aggregate that is being returned in one (or more)
1687*e4b17023SJohn Marino registers, load the registers here. */
1688*e4b17023SJohn Marino
1689*e4b17023SJohn Marino else if (retval_rhs != 0
1690*e4b17023SJohn Marino && TYPE_MODE (TREE_TYPE (retval_rhs)) == BLKmode
1691*e4b17023SJohn Marino && REG_P (result_rtl))
1692*e4b17023SJohn Marino {
1693*e4b17023SJohn Marino val = copy_blkmode_to_reg (GET_MODE (result_rtl), retval_rhs);
1694*e4b17023SJohn Marino if (val)
1695*e4b17023SJohn Marino {
1696*e4b17023SJohn Marino /* Use the mode of the result value on the return register. */
1697*e4b17023SJohn Marino PUT_MODE (result_rtl, GET_MODE (val));
1698*e4b17023SJohn Marino expand_value_return (val);
1699*e4b17023SJohn Marino }
1700*e4b17023SJohn Marino else
1701*e4b17023SJohn Marino expand_null_return ();
1702*e4b17023SJohn Marino }
1703*e4b17023SJohn Marino else if (retval_rhs != 0
1704*e4b17023SJohn Marino && !VOID_TYPE_P (TREE_TYPE (retval_rhs))
1705*e4b17023SJohn Marino && (REG_P (result_rtl)
1706*e4b17023SJohn Marino || (GET_CODE (result_rtl) == PARALLEL)))
1707*e4b17023SJohn Marino {
1708*e4b17023SJohn Marino /* Calculate the return value into a temporary (usually a pseudo
1709*e4b17023SJohn Marino reg). */
1710*e4b17023SJohn Marino tree ot = TREE_TYPE (DECL_RESULT (current_function_decl));
1711*e4b17023SJohn Marino tree nt = build_qualified_type (ot, TYPE_QUALS (ot) | TYPE_QUAL_CONST);
1712*e4b17023SJohn Marino
1713*e4b17023SJohn Marino val = assign_temp (nt, 0, 0, 1);
1714*e4b17023SJohn Marino val = expand_expr (retval_rhs, val, GET_MODE (val), EXPAND_NORMAL);
1715*e4b17023SJohn Marino val = force_not_mem (val);
1716*e4b17023SJohn Marino /* Return the calculated value. */
1717*e4b17023SJohn Marino expand_value_return (val);
1718*e4b17023SJohn Marino }
1719*e4b17023SJohn Marino else
1720*e4b17023SJohn Marino {
1721*e4b17023SJohn Marino /* No hard reg used; calculate value into hard return reg. */
1722*e4b17023SJohn Marino expand_expr (retval, const0_rtx, VOIDmode, EXPAND_NORMAL);
1723*e4b17023SJohn Marino expand_value_return (result_rtl);
1724*e4b17023SJohn Marino }
1725*e4b17023SJohn Marino }
1726*e4b17023SJohn Marino
1727*e4b17023SJohn Marino /* Emit code to restore vital registers at the beginning of a nonlocal goto
1728*e4b17023SJohn Marino handler. */
1729*e4b17023SJohn Marino static void
expand_nl_goto_receiver(void)1730*e4b17023SJohn Marino expand_nl_goto_receiver (void)
1731*e4b17023SJohn Marino {
1732*e4b17023SJohn Marino rtx chain;
1733*e4b17023SJohn Marino
1734*e4b17023SJohn Marino /* Clobber the FP when we get here, so we have to make sure it's
1735*e4b17023SJohn Marino marked as used by this function. */
1736*e4b17023SJohn Marino emit_use (hard_frame_pointer_rtx);
1737*e4b17023SJohn Marino
1738*e4b17023SJohn Marino /* Mark the static chain as clobbered here so life information
1739*e4b17023SJohn Marino doesn't get messed up for it. */
1740*e4b17023SJohn Marino chain = targetm.calls.static_chain (current_function_decl, true);
1741*e4b17023SJohn Marino if (chain && REG_P (chain))
1742*e4b17023SJohn Marino emit_clobber (chain);
1743*e4b17023SJohn Marino
1744*e4b17023SJohn Marino #ifdef HAVE_nonlocal_goto
1745*e4b17023SJohn Marino if (! HAVE_nonlocal_goto)
1746*e4b17023SJohn Marino #endif
1747*e4b17023SJohn Marino /* First adjust our frame pointer to its actual value. It was
1748*e4b17023SJohn Marino previously set to the start of the virtual area corresponding to
1749*e4b17023SJohn Marino the stacked variables when we branched here and now needs to be
1750*e4b17023SJohn Marino adjusted to the actual hardware fp value.
1751*e4b17023SJohn Marino
1752*e4b17023SJohn Marino Assignments are to virtual registers are converted by
1753*e4b17023SJohn Marino instantiate_virtual_regs into the corresponding assignment
1754*e4b17023SJohn Marino to the underlying register (fp in this case) that makes
1755*e4b17023SJohn Marino the original assignment true.
1756*e4b17023SJohn Marino So the following insn will actually be
1757*e4b17023SJohn Marino decrementing fp by STARTING_FRAME_OFFSET. */
1758*e4b17023SJohn Marino emit_move_insn (virtual_stack_vars_rtx, hard_frame_pointer_rtx);
1759*e4b17023SJohn Marino
1760*e4b17023SJohn Marino #if !HARD_FRAME_POINTER_IS_ARG_POINTER
1761*e4b17023SJohn Marino if (fixed_regs[ARG_POINTER_REGNUM])
1762*e4b17023SJohn Marino {
1763*e4b17023SJohn Marino #ifdef ELIMINABLE_REGS
1764*e4b17023SJohn Marino /* If the argument pointer can be eliminated in favor of the
1765*e4b17023SJohn Marino frame pointer, we don't need to restore it. We assume here
1766*e4b17023SJohn Marino that if such an elimination is present, it can always be used.
1767*e4b17023SJohn Marino This is the case on all known machines; if we don't make this
1768*e4b17023SJohn Marino assumption, we do unnecessary saving on many machines. */
1769*e4b17023SJohn Marino static const struct elims {const int from, to;} elim_regs[] = ELIMINABLE_REGS;
1770*e4b17023SJohn Marino size_t i;
1771*e4b17023SJohn Marino
1772*e4b17023SJohn Marino for (i = 0; i < ARRAY_SIZE (elim_regs); i++)
1773*e4b17023SJohn Marino if (elim_regs[i].from == ARG_POINTER_REGNUM
1774*e4b17023SJohn Marino && elim_regs[i].to == HARD_FRAME_POINTER_REGNUM)
1775*e4b17023SJohn Marino break;
1776*e4b17023SJohn Marino
1777*e4b17023SJohn Marino if (i == ARRAY_SIZE (elim_regs))
1778*e4b17023SJohn Marino #endif
1779*e4b17023SJohn Marino {
1780*e4b17023SJohn Marino /* Now restore our arg pointer from the address at which it
1781*e4b17023SJohn Marino was saved in our stack frame. */
1782*e4b17023SJohn Marino emit_move_insn (crtl->args.internal_arg_pointer,
1783*e4b17023SJohn Marino copy_to_reg (get_arg_pointer_save_area ()));
1784*e4b17023SJohn Marino }
1785*e4b17023SJohn Marino }
1786*e4b17023SJohn Marino #endif
1787*e4b17023SJohn Marino
1788*e4b17023SJohn Marino #ifdef HAVE_nonlocal_goto_receiver
1789*e4b17023SJohn Marino if (HAVE_nonlocal_goto_receiver)
1790*e4b17023SJohn Marino emit_insn (gen_nonlocal_goto_receiver ());
1791*e4b17023SJohn Marino #endif
1792*e4b17023SJohn Marino
1793*e4b17023SJohn Marino /* We must not allow the code we just generated to be reordered by
1794*e4b17023SJohn Marino scheduling. Specifically, the update of the frame pointer must
1795*e4b17023SJohn Marino happen immediately, not later. */
1796*e4b17023SJohn Marino emit_insn (gen_blockage ());
1797*e4b17023SJohn Marino }
1798*e4b17023SJohn Marino
1799*e4b17023SJohn Marino /* Generate RTL for the automatic variable declaration DECL.
1800*e4b17023SJohn Marino (Other kinds of declarations are simply ignored if seen here.) */
1801*e4b17023SJohn Marino
1802*e4b17023SJohn Marino void
expand_decl(tree decl)1803*e4b17023SJohn Marino expand_decl (tree decl)
1804*e4b17023SJohn Marino {
1805*e4b17023SJohn Marino tree type;
1806*e4b17023SJohn Marino
1807*e4b17023SJohn Marino type = TREE_TYPE (decl);
1808*e4b17023SJohn Marino
1809*e4b17023SJohn Marino /* For a CONST_DECL, set mode, alignment, and sizes from those of the
1810*e4b17023SJohn Marino type in case this node is used in a reference. */
1811*e4b17023SJohn Marino if (TREE_CODE (decl) == CONST_DECL)
1812*e4b17023SJohn Marino {
1813*e4b17023SJohn Marino DECL_MODE (decl) = TYPE_MODE (type);
1814*e4b17023SJohn Marino DECL_ALIGN (decl) = TYPE_ALIGN (type);
1815*e4b17023SJohn Marino DECL_SIZE (decl) = TYPE_SIZE (type);
1816*e4b17023SJohn Marino DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (type);
1817*e4b17023SJohn Marino return;
1818*e4b17023SJohn Marino }
1819*e4b17023SJohn Marino
1820*e4b17023SJohn Marino /* Otherwise, only automatic variables need any expansion done. Static and
1821*e4b17023SJohn Marino external variables, and external functions, will be handled by
1822*e4b17023SJohn Marino `assemble_variable' (called from finish_decl). TYPE_DECL requires
1823*e4b17023SJohn Marino nothing. PARM_DECLs are handled in `assign_parms'. */
1824*e4b17023SJohn Marino if (TREE_CODE (decl) != VAR_DECL)
1825*e4b17023SJohn Marino return;
1826*e4b17023SJohn Marino
1827*e4b17023SJohn Marino if (TREE_STATIC (decl) || DECL_EXTERNAL (decl))
1828*e4b17023SJohn Marino return;
1829*e4b17023SJohn Marino
1830*e4b17023SJohn Marino /* Create the RTL representation for the variable. */
1831*e4b17023SJohn Marino
1832*e4b17023SJohn Marino if (type == error_mark_node)
1833*e4b17023SJohn Marino SET_DECL_RTL (decl, gen_rtx_MEM (BLKmode, const0_rtx));
1834*e4b17023SJohn Marino
1835*e4b17023SJohn Marino else if (DECL_SIZE (decl) == 0)
1836*e4b17023SJohn Marino {
1837*e4b17023SJohn Marino /* Variable with incomplete type. */
1838*e4b17023SJohn Marino rtx x;
1839*e4b17023SJohn Marino if (DECL_INITIAL (decl) == 0)
1840*e4b17023SJohn Marino /* Error message was already done; now avoid a crash. */
1841*e4b17023SJohn Marino x = gen_rtx_MEM (BLKmode, const0_rtx);
1842*e4b17023SJohn Marino else
1843*e4b17023SJohn Marino /* An initializer is going to decide the size of this array.
1844*e4b17023SJohn Marino Until we know the size, represent its address with a reg. */
1845*e4b17023SJohn Marino x = gen_rtx_MEM (BLKmode, gen_reg_rtx (Pmode));
1846*e4b17023SJohn Marino
1847*e4b17023SJohn Marino set_mem_attributes (x, decl, 1);
1848*e4b17023SJohn Marino SET_DECL_RTL (decl, x);
1849*e4b17023SJohn Marino }
1850*e4b17023SJohn Marino else if (use_register_for_decl (decl))
1851*e4b17023SJohn Marino {
1852*e4b17023SJohn Marino /* Automatic variable that can go in a register. */
1853*e4b17023SJohn Marino enum machine_mode reg_mode = promote_decl_mode (decl, NULL);
1854*e4b17023SJohn Marino
1855*e4b17023SJohn Marino SET_DECL_RTL (decl, gen_reg_rtx (reg_mode));
1856*e4b17023SJohn Marino
1857*e4b17023SJohn Marino /* Note if the object is a user variable. */
1858*e4b17023SJohn Marino if (!DECL_ARTIFICIAL (decl))
1859*e4b17023SJohn Marino mark_user_reg (DECL_RTL (decl));
1860*e4b17023SJohn Marino
1861*e4b17023SJohn Marino if (POINTER_TYPE_P (type))
1862*e4b17023SJohn Marino mark_reg_pointer (DECL_RTL (decl),
1863*e4b17023SJohn Marino TYPE_ALIGN (TREE_TYPE (TREE_TYPE (decl))));
1864*e4b17023SJohn Marino }
1865*e4b17023SJohn Marino
1866*e4b17023SJohn Marino else
1867*e4b17023SJohn Marino {
1868*e4b17023SJohn Marino rtx oldaddr = 0;
1869*e4b17023SJohn Marino rtx addr;
1870*e4b17023SJohn Marino rtx x;
1871*e4b17023SJohn Marino
1872*e4b17023SJohn Marino /* Variable-sized decls are dealt with in the gimplifier. */
1873*e4b17023SJohn Marino gcc_assert (TREE_CODE (DECL_SIZE_UNIT (decl)) == INTEGER_CST);
1874*e4b17023SJohn Marino
1875*e4b17023SJohn Marino /* If we previously made RTL for this decl, it must be an array
1876*e4b17023SJohn Marino whose size was determined by the initializer.
1877*e4b17023SJohn Marino The old address was a register; set that register now
1878*e4b17023SJohn Marino to the proper address. */
1879*e4b17023SJohn Marino if (DECL_RTL_SET_P (decl))
1880*e4b17023SJohn Marino {
1881*e4b17023SJohn Marino gcc_assert (MEM_P (DECL_RTL (decl)));
1882*e4b17023SJohn Marino gcc_assert (REG_P (XEXP (DECL_RTL (decl), 0)));
1883*e4b17023SJohn Marino oldaddr = XEXP (DECL_RTL (decl), 0);
1884*e4b17023SJohn Marino }
1885*e4b17023SJohn Marino
1886*e4b17023SJohn Marino /* Set alignment we actually gave this decl. */
1887*e4b17023SJohn Marino DECL_ALIGN (decl) = (DECL_MODE (decl) == BLKmode ? BIGGEST_ALIGNMENT
1888*e4b17023SJohn Marino : GET_MODE_BITSIZE (DECL_MODE (decl)));
1889*e4b17023SJohn Marino DECL_USER_ALIGN (decl) = 0;
1890*e4b17023SJohn Marino
1891*e4b17023SJohn Marino x = assign_temp (decl, 1, 1, 1);
1892*e4b17023SJohn Marino set_mem_attributes (x, decl, 1);
1893*e4b17023SJohn Marino SET_DECL_RTL (decl, x);
1894*e4b17023SJohn Marino
1895*e4b17023SJohn Marino if (oldaddr)
1896*e4b17023SJohn Marino {
1897*e4b17023SJohn Marino addr = force_operand (XEXP (DECL_RTL (decl), 0), oldaddr);
1898*e4b17023SJohn Marino if (addr != oldaddr)
1899*e4b17023SJohn Marino emit_move_insn (oldaddr, addr);
1900*e4b17023SJohn Marino }
1901*e4b17023SJohn Marino }
1902*e4b17023SJohn Marino }
1903*e4b17023SJohn Marino
1904*e4b17023SJohn Marino /* Emit code to save the current value of stack. */
1905*e4b17023SJohn Marino rtx
expand_stack_save(void)1906*e4b17023SJohn Marino expand_stack_save (void)
1907*e4b17023SJohn Marino {
1908*e4b17023SJohn Marino rtx ret = NULL_RTX;
1909*e4b17023SJohn Marino
1910*e4b17023SJohn Marino do_pending_stack_adjust ();
1911*e4b17023SJohn Marino emit_stack_save (SAVE_BLOCK, &ret);
1912*e4b17023SJohn Marino return ret;
1913*e4b17023SJohn Marino }
1914*e4b17023SJohn Marino
1915*e4b17023SJohn Marino /* Emit code to restore the current value of stack. */
1916*e4b17023SJohn Marino void
expand_stack_restore(tree var)1917*e4b17023SJohn Marino expand_stack_restore (tree var)
1918*e4b17023SJohn Marino {
1919*e4b17023SJohn Marino rtx prev, sa = expand_normal (var);
1920*e4b17023SJohn Marino
1921*e4b17023SJohn Marino sa = convert_memory_address (Pmode, sa);
1922*e4b17023SJohn Marino
1923*e4b17023SJohn Marino prev = get_last_insn ();
1924*e4b17023SJohn Marino emit_stack_restore (SAVE_BLOCK, sa);
1925*e4b17023SJohn Marino fixup_args_size_notes (prev, get_last_insn (), 0);
1926*e4b17023SJohn Marino }
1927*e4b17023SJohn Marino
1928*e4b17023SJohn Marino /* Do the insertion of a case label into case_list. The labels are
1929*e4b17023SJohn Marino fed to us in descending order from the sorted vector of case labels used
1930*e4b17023SJohn Marino in the tree part of the middle end. So the list we construct is
1931*e4b17023SJohn Marino sorted in ascending order. The bounds on the case range, LOW and HIGH,
1932*e4b17023SJohn Marino are converted to case's index type TYPE. */
1933*e4b17023SJohn Marino
1934*e4b17023SJohn Marino static struct case_node *
add_case_node(struct case_node * head,tree type,tree low,tree high,tree label,alloc_pool case_node_pool)1935*e4b17023SJohn Marino add_case_node (struct case_node *head, tree type, tree low, tree high,
1936*e4b17023SJohn Marino tree label, alloc_pool case_node_pool)
1937*e4b17023SJohn Marino {
1938*e4b17023SJohn Marino tree min_value, max_value;
1939*e4b17023SJohn Marino struct case_node *r;
1940*e4b17023SJohn Marino
1941*e4b17023SJohn Marino gcc_assert (TREE_CODE (low) == INTEGER_CST);
1942*e4b17023SJohn Marino gcc_assert (!high || TREE_CODE (high) == INTEGER_CST);
1943*e4b17023SJohn Marino
1944*e4b17023SJohn Marino min_value = TYPE_MIN_VALUE (type);
1945*e4b17023SJohn Marino max_value = TYPE_MAX_VALUE (type);
1946*e4b17023SJohn Marino
1947*e4b17023SJohn Marino /* If there's no HIGH value, then this is not a case range; it's
1948*e4b17023SJohn Marino just a simple case label. But that's just a degenerate case
1949*e4b17023SJohn Marino range.
1950*e4b17023SJohn Marino If the bounds are equal, turn this into the one-value case. */
1951*e4b17023SJohn Marino if (!high || tree_int_cst_equal (low, high))
1952*e4b17023SJohn Marino {
1953*e4b17023SJohn Marino /* If the simple case value is unreachable, ignore it. */
1954*e4b17023SJohn Marino if ((TREE_CODE (min_value) == INTEGER_CST
1955*e4b17023SJohn Marino && tree_int_cst_compare (low, min_value) < 0)
1956*e4b17023SJohn Marino || (TREE_CODE (max_value) == INTEGER_CST
1957*e4b17023SJohn Marino && tree_int_cst_compare (low, max_value) > 0))
1958*e4b17023SJohn Marino return head;
1959*e4b17023SJohn Marino low = fold_convert (type, low);
1960*e4b17023SJohn Marino high = low;
1961*e4b17023SJohn Marino }
1962*e4b17023SJohn Marino else
1963*e4b17023SJohn Marino {
1964*e4b17023SJohn Marino /* If the entire case range is unreachable, ignore it. */
1965*e4b17023SJohn Marino if ((TREE_CODE (min_value) == INTEGER_CST
1966*e4b17023SJohn Marino && tree_int_cst_compare (high, min_value) < 0)
1967*e4b17023SJohn Marino || (TREE_CODE (max_value) == INTEGER_CST
1968*e4b17023SJohn Marino && tree_int_cst_compare (low, max_value) > 0))
1969*e4b17023SJohn Marino return head;
1970*e4b17023SJohn Marino
1971*e4b17023SJohn Marino /* If the lower bound is less than the index type's minimum
1972*e4b17023SJohn Marino value, truncate the range bounds. */
1973*e4b17023SJohn Marino if (TREE_CODE (min_value) == INTEGER_CST
1974*e4b17023SJohn Marino && tree_int_cst_compare (low, min_value) < 0)
1975*e4b17023SJohn Marino low = min_value;
1976*e4b17023SJohn Marino low = fold_convert (type, low);
1977*e4b17023SJohn Marino
1978*e4b17023SJohn Marino /* If the upper bound is greater than the index type's maximum
1979*e4b17023SJohn Marino value, truncate the range bounds. */
1980*e4b17023SJohn Marino if (TREE_CODE (max_value) == INTEGER_CST
1981*e4b17023SJohn Marino && tree_int_cst_compare (high, max_value) > 0)
1982*e4b17023SJohn Marino high = max_value;
1983*e4b17023SJohn Marino high = fold_convert (type, high);
1984*e4b17023SJohn Marino }
1985*e4b17023SJohn Marino
1986*e4b17023SJohn Marino
1987*e4b17023SJohn Marino /* Add this label to the chain. Make sure to drop overflow flags. */
1988*e4b17023SJohn Marino r = (struct case_node *) pool_alloc (case_node_pool);
1989*e4b17023SJohn Marino r->low = build_int_cst_wide (TREE_TYPE (low), TREE_INT_CST_LOW (low),
1990*e4b17023SJohn Marino TREE_INT_CST_HIGH (low));
1991*e4b17023SJohn Marino r->high = build_int_cst_wide (TREE_TYPE (high), TREE_INT_CST_LOW (high),
1992*e4b17023SJohn Marino TREE_INT_CST_HIGH (high));
1993*e4b17023SJohn Marino r->code_label = label;
1994*e4b17023SJohn Marino r->parent = r->left = NULL;
1995*e4b17023SJohn Marino r->right = head;
1996*e4b17023SJohn Marino return r;
1997*e4b17023SJohn Marino }
1998*e4b17023SJohn Marino
1999*e4b17023SJohn Marino /* Maximum number of case bit tests. */
2000*e4b17023SJohn Marino #define MAX_CASE_BIT_TESTS 3
2001*e4b17023SJohn Marino
2002*e4b17023SJohn Marino /* By default, enable case bit tests on targets with ashlsi3. */
2003*e4b17023SJohn Marino #ifndef CASE_USE_BIT_TESTS
2004*e4b17023SJohn Marino #define CASE_USE_BIT_TESTS (optab_handler (ashl_optab, word_mode) \
2005*e4b17023SJohn Marino != CODE_FOR_nothing)
2006*e4b17023SJohn Marino #endif
2007*e4b17023SJohn Marino
2008*e4b17023SJohn Marino
2009*e4b17023SJohn Marino /* A case_bit_test represents a set of case nodes that may be
2010*e4b17023SJohn Marino selected from using a bit-wise comparison. HI and LO hold
2011*e4b17023SJohn Marino the integer to be tested against, LABEL contains the label
2012*e4b17023SJohn Marino to jump to upon success and BITS counts the number of case
2013*e4b17023SJohn Marino nodes handled by this test, typically the number of bits
2014*e4b17023SJohn Marino set in HI:LO. */
2015*e4b17023SJohn Marino
2016*e4b17023SJohn Marino struct case_bit_test
2017*e4b17023SJohn Marino {
2018*e4b17023SJohn Marino HOST_WIDE_INT hi;
2019*e4b17023SJohn Marino HOST_WIDE_INT lo;
2020*e4b17023SJohn Marino rtx label;
2021*e4b17023SJohn Marino int bits;
2022*e4b17023SJohn Marino };
2023*e4b17023SJohn Marino
2024*e4b17023SJohn Marino /* Determine whether "1 << x" is relatively cheap in word_mode. */
2025*e4b17023SJohn Marino
2026*e4b17023SJohn Marino static
lshift_cheap_p(void)2027*e4b17023SJohn Marino bool lshift_cheap_p (void)
2028*e4b17023SJohn Marino {
2029*e4b17023SJohn Marino static bool init[2] = {false, false};
2030*e4b17023SJohn Marino static bool cheap[2] = {true, true};
2031*e4b17023SJohn Marino
2032*e4b17023SJohn Marino bool speed_p = optimize_insn_for_speed_p ();
2033*e4b17023SJohn Marino
2034*e4b17023SJohn Marino if (!init[speed_p])
2035*e4b17023SJohn Marino {
2036*e4b17023SJohn Marino rtx reg = gen_rtx_REG (word_mode, 10000);
2037*e4b17023SJohn Marino int cost = set_src_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg),
2038*e4b17023SJohn Marino speed_p);
2039*e4b17023SJohn Marino cheap[speed_p] = cost < COSTS_N_INSNS (3);
2040*e4b17023SJohn Marino init[speed_p] = true;
2041*e4b17023SJohn Marino }
2042*e4b17023SJohn Marino
2043*e4b17023SJohn Marino return cheap[speed_p];
2044*e4b17023SJohn Marino }
2045*e4b17023SJohn Marino
2046*e4b17023SJohn Marino /* Comparison function for qsort to order bit tests by decreasing
2047*e4b17023SJohn Marino number of case nodes, i.e. the node with the most cases gets
2048*e4b17023SJohn Marino tested first. */
2049*e4b17023SJohn Marino
2050*e4b17023SJohn Marino static int
case_bit_test_cmp(const void * p1,const void * p2)2051*e4b17023SJohn Marino case_bit_test_cmp (const void *p1, const void *p2)
2052*e4b17023SJohn Marino {
2053*e4b17023SJohn Marino const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
2054*e4b17023SJohn Marino const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
2055*e4b17023SJohn Marino
2056*e4b17023SJohn Marino if (d2->bits != d1->bits)
2057*e4b17023SJohn Marino return d2->bits - d1->bits;
2058*e4b17023SJohn Marino
2059*e4b17023SJohn Marino /* Stabilize the sort. */
2060*e4b17023SJohn Marino return CODE_LABEL_NUMBER (d2->label) - CODE_LABEL_NUMBER (d1->label);
2061*e4b17023SJohn Marino }
2062*e4b17023SJohn Marino
2063*e4b17023SJohn Marino /* Expand a switch statement by a short sequence of bit-wise
2064*e4b17023SJohn Marino comparisons. "switch(x)" is effectively converted into
2065*e4b17023SJohn Marino "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
2066*e4b17023SJohn Marino integer constants.
2067*e4b17023SJohn Marino
2068*e4b17023SJohn Marino INDEX_EXPR is the value being switched on, which is of
2069*e4b17023SJohn Marino type INDEX_TYPE. MINVAL is the lowest case value of in
2070*e4b17023SJohn Marino the case nodes, of INDEX_TYPE type, and RANGE is highest
2071*e4b17023SJohn Marino value minus MINVAL, also of type INDEX_TYPE. NODES is
2072*e4b17023SJohn Marino the set of case nodes, and DEFAULT_LABEL is the label to
2073*e4b17023SJohn Marino branch to should none of the cases match.
2074*e4b17023SJohn Marino
2075*e4b17023SJohn Marino There *MUST* be MAX_CASE_BIT_TESTS or less unique case
2076*e4b17023SJohn Marino node targets. */
2077*e4b17023SJohn Marino
2078*e4b17023SJohn Marino static void
emit_case_bit_tests(tree index_type,tree index_expr,tree minval,tree range,case_node_ptr nodes,rtx default_label)2079*e4b17023SJohn Marino emit_case_bit_tests (tree index_type, tree index_expr, tree minval,
2080*e4b17023SJohn Marino tree range, case_node_ptr nodes, rtx default_label)
2081*e4b17023SJohn Marino {
2082*e4b17023SJohn Marino struct case_bit_test test[MAX_CASE_BIT_TESTS];
2083*e4b17023SJohn Marino enum machine_mode mode;
2084*e4b17023SJohn Marino rtx expr, index, label;
2085*e4b17023SJohn Marino unsigned int i,j,lo,hi;
2086*e4b17023SJohn Marino struct case_node *n;
2087*e4b17023SJohn Marino unsigned int count;
2088*e4b17023SJohn Marino
2089*e4b17023SJohn Marino count = 0;
2090*e4b17023SJohn Marino for (n = nodes; n; n = n->right)
2091*e4b17023SJohn Marino {
2092*e4b17023SJohn Marino label = label_rtx (n->code_label);
2093*e4b17023SJohn Marino for (i = 0; i < count; i++)
2094*e4b17023SJohn Marino if (label == test[i].label)
2095*e4b17023SJohn Marino break;
2096*e4b17023SJohn Marino
2097*e4b17023SJohn Marino if (i == count)
2098*e4b17023SJohn Marino {
2099*e4b17023SJohn Marino gcc_assert (count < MAX_CASE_BIT_TESTS);
2100*e4b17023SJohn Marino test[i].hi = 0;
2101*e4b17023SJohn Marino test[i].lo = 0;
2102*e4b17023SJohn Marino test[i].label = label;
2103*e4b17023SJohn Marino test[i].bits = 1;
2104*e4b17023SJohn Marino count++;
2105*e4b17023SJohn Marino }
2106*e4b17023SJohn Marino else
2107*e4b17023SJohn Marino test[i].bits++;
2108*e4b17023SJohn Marino
2109*e4b17023SJohn Marino lo = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2110*e4b17023SJohn Marino n->low, minval), 1);
2111*e4b17023SJohn Marino hi = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2112*e4b17023SJohn Marino n->high, minval), 1);
2113*e4b17023SJohn Marino for (j = lo; j <= hi; j++)
2114*e4b17023SJohn Marino if (j >= HOST_BITS_PER_WIDE_INT)
2115*e4b17023SJohn Marino test[i].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT);
2116*e4b17023SJohn Marino else
2117*e4b17023SJohn Marino test[i].lo |= (HOST_WIDE_INT) 1 << j;
2118*e4b17023SJohn Marino }
2119*e4b17023SJohn Marino
2120*e4b17023SJohn Marino qsort (test, count, sizeof(*test), case_bit_test_cmp);
2121*e4b17023SJohn Marino
2122*e4b17023SJohn Marino index_expr = fold_build2 (MINUS_EXPR, index_type,
2123*e4b17023SJohn Marino fold_convert (index_type, index_expr),
2124*e4b17023SJohn Marino fold_convert (index_type, minval));
2125*e4b17023SJohn Marino index = expand_normal (index_expr);
2126*e4b17023SJohn Marino do_pending_stack_adjust ();
2127*e4b17023SJohn Marino
2128*e4b17023SJohn Marino mode = TYPE_MODE (index_type);
2129*e4b17023SJohn Marino expr = expand_normal (range);
2130*e4b17023SJohn Marino if (default_label)
2131*e4b17023SJohn Marino emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
2132*e4b17023SJohn Marino default_label);
2133*e4b17023SJohn Marino
2134*e4b17023SJohn Marino index = convert_to_mode (word_mode, index, 0);
2135*e4b17023SJohn Marino index = expand_binop (word_mode, ashl_optab, const1_rtx,
2136*e4b17023SJohn Marino index, NULL_RTX, 1, OPTAB_WIDEN);
2137*e4b17023SJohn Marino
2138*e4b17023SJohn Marino for (i = 0; i < count; i++)
2139*e4b17023SJohn Marino {
2140*e4b17023SJohn Marino expr = immed_double_const (test[i].lo, test[i].hi, word_mode);
2141*e4b17023SJohn Marino expr = expand_binop (word_mode, and_optab, index, expr,
2142*e4b17023SJohn Marino NULL_RTX, 1, OPTAB_WIDEN);
2143*e4b17023SJohn Marino emit_cmp_and_jump_insns (expr, const0_rtx, NE, NULL_RTX,
2144*e4b17023SJohn Marino word_mode, 1, test[i].label);
2145*e4b17023SJohn Marino }
2146*e4b17023SJohn Marino
2147*e4b17023SJohn Marino if (default_label)
2148*e4b17023SJohn Marino emit_jump (default_label);
2149*e4b17023SJohn Marino }
2150*e4b17023SJohn Marino
2151*e4b17023SJohn Marino #ifndef HAVE_casesi
2152*e4b17023SJohn Marino #define HAVE_casesi 0
2153*e4b17023SJohn Marino #endif
2154*e4b17023SJohn Marino
2155*e4b17023SJohn Marino #ifndef HAVE_tablejump
2156*e4b17023SJohn Marino #define HAVE_tablejump 0
2157*e4b17023SJohn Marino #endif
2158*e4b17023SJohn Marino
2159*e4b17023SJohn Marino /* Return true if a switch should be expanded as a bit test.
2160*e4b17023SJohn Marino INDEX_EXPR is the index expression, RANGE is the difference between
2161*e4b17023SJohn Marino highest and lowest case, UNIQ is number of unique case node targets
2162*e4b17023SJohn Marino not counting the default case and COUNT is the number of comparisons
2163*e4b17023SJohn Marino needed, not counting the default case. */
2164*e4b17023SJohn Marino bool
expand_switch_using_bit_tests_p(tree index_expr,tree range,unsigned int uniq,unsigned int count)2165*e4b17023SJohn Marino expand_switch_using_bit_tests_p (tree index_expr, tree range,
2166*e4b17023SJohn Marino unsigned int uniq, unsigned int count)
2167*e4b17023SJohn Marino {
2168*e4b17023SJohn Marino return (CASE_USE_BIT_TESTS
2169*e4b17023SJohn Marino && ! TREE_CONSTANT (index_expr)
2170*e4b17023SJohn Marino && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
2171*e4b17023SJohn Marino && compare_tree_int (range, 0) > 0
2172*e4b17023SJohn Marino && lshift_cheap_p ()
2173*e4b17023SJohn Marino && ((uniq == 1 && count >= 3)
2174*e4b17023SJohn Marino || (uniq == 2 && count >= 5)
2175*e4b17023SJohn Marino || (uniq == 3 && count >= 6)));
2176*e4b17023SJohn Marino }
2177*e4b17023SJohn Marino
2178*e4b17023SJohn Marino /* Return the smallest number of different values for which it is best to use a
2179*e4b17023SJohn Marino jump-table instead of a tree of conditional branches. */
2180*e4b17023SJohn Marino
2181*e4b17023SJohn Marino static unsigned int
case_values_threshold(void)2182*e4b17023SJohn Marino case_values_threshold (void)
2183*e4b17023SJohn Marino {
2184*e4b17023SJohn Marino unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
2185*e4b17023SJohn Marino
2186*e4b17023SJohn Marino if (threshold == 0)
2187*e4b17023SJohn Marino threshold = targetm.case_values_threshold ();
2188*e4b17023SJohn Marino
2189*e4b17023SJohn Marino return threshold;
2190*e4b17023SJohn Marino }
2191*e4b17023SJohn Marino
2192*e4b17023SJohn Marino /* Terminate a case (Pascal/Ada) or switch (C) statement
2193*e4b17023SJohn Marino in which ORIG_INDEX is the expression to be tested.
2194*e4b17023SJohn Marino If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
2195*e4b17023SJohn Marino type as given in the source before any compiler conversions.
2196*e4b17023SJohn Marino Generate the code to test it and jump to the right place. */
2197*e4b17023SJohn Marino
2198*e4b17023SJohn Marino void
expand_case(gimple stmt)2199*e4b17023SJohn Marino expand_case (gimple stmt)
2200*e4b17023SJohn Marino {
2201*e4b17023SJohn Marino tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
2202*e4b17023SJohn Marino rtx default_label = 0;
2203*e4b17023SJohn Marino struct case_node *n;
2204*e4b17023SJohn Marino unsigned int count, uniq;
2205*e4b17023SJohn Marino rtx index;
2206*e4b17023SJohn Marino rtx table_label;
2207*e4b17023SJohn Marino int ncases;
2208*e4b17023SJohn Marino rtx *labelvec;
2209*e4b17023SJohn Marino int i;
2210*e4b17023SJohn Marino rtx before_case, end, lab;
2211*e4b17023SJohn Marino
2212*e4b17023SJohn Marino tree index_expr = gimple_switch_index (stmt);
2213*e4b17023SJohn Marino tree index_type = TREE_TYPE (index_expr);
2214*e4b17023SJohn Marino int unsignedp = TYPE_UNSIGNED (index_type);
2215*e4b17023SJohn Marino
2216*e4b17023SJohn Marino /* The insn after which the case dispatch should finally
2217*e4b17023SJohn Marino be emitted. Zero for a dummy. */
2218*e4b17023SJohn Marino rtx start;
2219*e4b17023SJohn Marino
2220*e4b17023SJohn Marino /* A list of case labels; it is first built as a list and it may then
2221*e4b17023SJohn Marino be rearranged into a nearly balanced binary tree. */
2222*e4b17023SJohn Marino struct case_node *case_list = 0;
2223*e4b17023SJohn Marino
2224*e4b17023SJohn Marino /* Label to jump to if no case matches. */
2225*e4b17023SJohn Marino tree default_label_decl = NULL_TREE;
2226*e4b17023SJohn Marino
2227*e4b17023SJohn Marino alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
2228*e4b17023SJohn Marino sizeof (struct case_node),
2229*e4b17023SJohn Marino 100);
2230*e4b17023SJohn Marino
2231*e4b17023SJohn Marino do_pending_stack_adjust ();
2232*e4b17023SJohn Marino
2233*e4b17023SJohn Marino /* An ERROR_MARK occurs for various reasons including invalid data type. */
2234*e4b17023SJohn Marino if (index_type != error_mark_node)
2235*e4b17023SJohn Marino {
2236*e4b17023SJohn Marino tree elt;
2237*e4b17023SJohn Marino bitmap label_bitmap;
2238*e4b17023SJohn Marino int stopi = 0;
2239*e4b17023SJohn Marino
2240*e4b17023SJohn Marino /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
2241*e4b17023SJohn Marino expressions being INTEGER_CST. */
2242*e4b17023SJohn Marino gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
2243*e4b17023SJohn Marino
2244*e4b17023SJohn Marino /* The default case, if ever taken, is the first element. */
2245*e4b17023SJohn Marino elt = gimple_switch_label (stmt, 0);
2246*e4b17023SJohn Marino if (!CASE_LOW (elt) && !CASE_HIGH (elt))
2247*e4b17023SJohn Marino {
2248*e4b17023SJohn Marino default_label_decl = CASE_LABEL (elt);
2249*e4b17023SJohn Marino stopi = 1;
2250*e4b17023SJohn Marino }
2251*e4b17023SJohn Marino
2252*e4b17023SJohn Marino for (i = gimple_switch_num_labels (stmt) - 1; i >= stopi; --i)
2253*e4b17023SJohn Marino {
2254*e4b17023SJohn Marino tree low, high;
2255*e4b17023SJohn Marino elt = gimple_switch_label (stmt, i);
2256*e4b17023SJohn Marino
2257*e4b17023SJohn Marino low = CASE_LOW (elt);
2258*e4b17023SJohn Marino gcc_assert (low);
2259*e4b17023SJohn Marino high = CASE_HIGH (elt);
2260*e4b17023SJohn Marino
2261*e4b17023SJohn Marino /* Discard empty ranges. */
2262*e4b17023SJohn Marino if (high && tree_int_cst_lt (high, low))
2263*e4b17023SJohn Marino continue;
2264*e4b17023SJohn Marino
2265*e4b17023SJohn Marino case_list = add_case_node (case_list, index_type, low, high,
2266*e4b17023SJohn Marino CASE_LABEL (elt), case_node_pool);
2267*e4b17023SJohn Marino }
2268*e4b17023SJohn Marino
2269*e4b17023SJohn Marino
2270*e4b17023SJohn Marino before_case = start = get_last_insn ();
2271*e4b17023SJohn Marino if (default_label_decl)
2272*e4b17023SJohn Marino default_label = label_rtx (default_label_decl);
2273*e4b17023SJohn Marino
2274*e4b17023SJohn Marino /* Get upper and lower bounds of case values. */
2275*e4b17023SJohn Marino
2276*e4b17023SJohn Marino uniq = 0;
2277*e4b17023SJohn Marino count = 0;
2278*e4b17023SJohn Marino label_bitmap = BITMAP_ALLOC (NULL);
2279*e4b17023SJohn Marino for (n = case_list; n; n = n->right)
2280*e4b17023SJohn Marino {
2281*e4b17023SJohn Marino /* Count the elements and track the largest and smallest
2282*e4b17023SJohn Marino of them (treating them as signed even if they are not). */
2283*e4b17023SJohn Marino if (count++ == 0)
2284*e4b17023SJohn Marino {
2285*e4b17023SJohn Marino minval = n->low;
2286*e4b17023SJohn Marino maxval = n->high;
2287*e4b17023SJohn Marino }
2288*e4b17023SJohn Marino else
2289*e4b17023SJohn Marino {
2290*e4b17023SJohn Marino if (tree_int_cst_lt (n->low, minval))
2291*e4b17023SJohn Marino minval = n->low;
2292*e4b17023SJohn Marino if (tree_int_cst_lt (maxval, n->high))
2293*e4b17023SJohn Marino maxval = n->high;
2294*e4b17023SJohn Marino }
2295*e4b17023SJohn Marino /* A range counts double, since it requires two compares. */
2296*e4b17023SJohn Marino if (! tree_int_cst_equal (n->low, n->high))
2297*e4b17023SJohn Marino count++;
2298*e4b17023SJohn Marino
2299*e4b17023SJohn Marino /* If we have not seen this label yet, then increase the
2300*e4b17023SJohn Marino number of unique case node targets seen. */
2301*e4b17023SJohn Marino lab = label_rtx (n->code_label);
2302*e4b17023SJohn Marino if (bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab)))
2303*e4b17023SJohn Marino uniq++;
2304*e4b17023SJohn Marino }
2305*e4b17023SJohn Marino
2306*e4b17023SJohn Marino BITMAP_FREE (label_bitmap);
2307*e4b17023SJohn Marino
2308*e4b17023SJohn Marino /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
2309*e4b17023SJohn Marino destination, such as one with a default case only. However,
2310*e4b17023SJohn Marino it doesn't remove cases that are out of range for the switch
2311*e4b17023SJohn Marino type, so we may still get a zero here. */
2312*e4b17023SJohn Marino if (count == 0)
2313*e4b17023SJohn Marino {
2314*e4b17023SJohn Marino if (default_label)
2315*e4b17023SJohn Marino emit_jump (default_label);
2316*e4b17023SJohn Marino free_alloc_pool (case_node_pool);
2317*e4b17023SJohn Marino return;
2318*e4b17023SJohn Marino }
2319*e4b17023SJohn Marino
2320*e4b17023SJohn Marino /* Compute span of values. */
2321*e4b17023SJohn Marino range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
2322*e4b17023SJohn Marino
2323*e4b17023SJohn Marino /* Try implementing this switch statement by a short sequence of
2324*e4b17023SJohn Marino bit-wise comparisons. However, we let the binary-tree case
2325*e4b17023SJohn Marino below handle constant index expressions. */
2326*e4b17023SJohn Marino if (expand_switch_using_bit_tests_p (index_expr, range, uniq, count))
2327*e4b17023SJohn Marino {
2328*e4b17023SJohn Marino /* Optimize the case where all the case values fit in a
2329*e4b17023SJohn Marino word without having to subtract MINVAL. In this case,
2330*e4b17023SJohn Marino we can optimize away the subtraction. */
2331*e4b17023SJohn Marino if (compare_tree_int (minval, 0) > 0
2332*e4b17023SJohn Marino && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
2333*e4b17023SJohn Marino {
2334*e4b17023SJohn Marino minval = build_int_cst (index_type, 0);
2335*e4b17023SJohn Marino range = maxval;
2336*e4b17023SJohn Marino }
2337*e4b17023SJohn Marino emit_case_bit_tests (index_type, index_expr, minval, range,
2338*e4b17023SJohn Marino case_list, default_label);
2339*e4b17023SJohn Marino }
2340*e4b17023SJohn Marino
2341*e4b17023SJohn Marino /* If range of values is much bigger than number of values,
2342*e4b17023SJohn Marino make a sequence of conditional branches instead of a dispatch.
2343*e4b17023SJohn Marino If the switch-index is a constant, do it this way
2344*e4b17023SJohn Marino because we can optimize it. */
2345*e4b17023SJohn Marino
2346*e4b17023SJohn Marino else if (count < case_values_threshold ()
2347*e4b17023SJohn Marino || compare_tree_int (range,
2348*e4b17023SJohn Marino (optimize_insn_for_size_p () ? 3 : 10) * count) > 0
2349*e4b17023SJohn Marino /* RANGE may be signed, and really large ranges will show up
2350*e4b17023SJohn Marino as negative numbers. */
2351*e4b17023SJohn Marino || compare_tree_int (range, 0) < 0
2352*e4b17023SJohn Marino #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
2353*e4b17023SJohn Marino || flag_pic
2354*e4b17023SJohn Marino #endif
2355*e4b17023SJohn Marino || !flag_jump_tables
2356*e4b17023SJohn Marino || TREE_CONSTANT (index_expr)
2357*e4b17023SJohn Marino /* If neither casesi or tablejump is available, we can
2358*e4b17023SJohn Marino only go this way. */
2359*e4b17023SJohn Marino || (!HAVE_casesi && !HAVE_tablejump))
2360*e4b17023SJohn Marino {
2361*e4b17023SJohn Marino index = expand_normal (index_expr);
2362*e4b17023SJohn Marino
2363*e4b17023SJohn Marino /* If the index is a short or char that we do not have
2364*e4b17023SJohn Marino an insn to handle comparisons directly, convert it to
2365*e4b17023SJohn Marino a full integer now, rather than letting each comparison
2366*e4b17023SJohn Marino generate the conversion. */
2367*e4b17023SJohn Marino
2368*e4b17023SJohn Marino if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
2369*e4b17023SJohn Marino && ! have_insn_for (COMPARE, GET_MODE (index)))
2370*e4b17023SJohn Marino {
2371*e4b17023SJohn Marino enum machine_mode wider_mode;
2372*e4b17023SJohn Marino for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
2373*e4b17023SJohn Marino wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2374*e4b17023SJohn Marino if (have_insn_for (COMPARE, wider_mode))
2375*e4b17023SJohn Marino {
2376*e4b17023SJohn Marino index = convert_to_mode (wider_mode, index, unsignedp);
2377*e4b17023SJohn Marino break;
2378*e4b17023SJohn Marino }
2379*e4b17023SJohn Marino }
2380*e4b17023SJohn Marino
2381*e4b17023SJohn Marino do_pending_stack_adjust ();
2382*e4b17023SJohn Marino
2383*e4b17023SJohn Marino if (MEM_P (index))
2384*e4b17023SJohn Marino index = copy_to_reg (index);
2385*e4b17023SJohn Marino
2386*e4b17023SJohn Marino /* We generate a binary decision tree to select the
2387*e4b17023SJohn Marino appropriate target code. This is done as follows:
2388*e4b17023SJohn Marino
2389*e4b17023SJohn Marino The list of cases is rearranged into a binary tree,
2390*e4b17023SJohn Marino nearly optimal assuming equal probability for each case.
2391*e4b17023SJohn Marino
2392*e4b17023SJohn Marino The tree is transformed into RTL, eliminating
2393*e4b17023SJohn Marino redundant test conditions at the same time.
2394*e4b17023SJohn Marino
2395*e4b17023SJohn Marino If program flow could reach the end of the
2396*e4b17023SJohn Marino decision tree an unconditional jump to the
2397*e4b17023SJohn Marino default code is emitted. */
2398*e4b17023SJohn Marino
2399*e4b17023SJohn Marino use_cost_table = estimate_case_costs (case_list);
2400*e4b17023SJohn Marino balance_case_nodes (&case_list, NULL);
2401*e4b17023SJohn Marino emit_case_nodes (index, case_list, default_label, index_type);
2402*e4b17023SJohn Marino if (default_label)
2403*e4b17023SJohn Marino emit_jump (default_label);
2404*e4b17023SJohn Marino }
2405*e4b17023SJohn Marino else
2406*e4b17023SJohn Marino {
2407*e4b17023SJohn Marino rtx fallback_label = label_rtx (case_list->code_label);
2408*e4b17023SJohn Marino table_label = gen_label_rtx ();
2409*e4b17023SJohn Marino if (! try_casesi (index_type, index_expr, minval, range,
2410*e4b17023SJohn Marino table_label, default_label, fallback_label))
2411*e4b17023SJohn Marino {
2412*e4b17023SJohn Marino bool ok;
2413*e4b17023SJohn Marino
2414*e4b17023SJohn Marino /* Index jumptables from zero for suitable values of
2415*e4b17023SJohn Marino minval to avoid a subtraction. */
2416*e4b17023SJohn Marino if (optimize_insn_for_speed_p ()
2417*e4b17023SJohn Marino && compare_tree_int (minval, 0) > 0
2418*e4b17023SJohn Marino && compare_tree_int (minval, 3) < 0)
2419*e4b17023SJohn Marino {
2420*e4b17023SJohn Marino minval = build_int_cst (index_type, 0);
2421*e4b17023SJohn Marino range = maxval;
2422*e4b17023SJohn Marino }
2423*e4b17023SJohn Marino
2424*e4b17023SJohn Marino ok = try_tablejump (index_type, index_expr, minval, range,
2425*e4b17023SJohn Marino table_label, default_label);
2426*e4b17023SJohn Marino gcc_assert (ok);
2427*e4b17023SJohn Marino }
2428*e4b17023SJohn Marino
2429*e4b17023SJohn Marino /* Get table of labels to jump to, in order of case index. */
2430*e4b17023SJohn Marino
2431*e4b17023SJohn Marino ncases = tree_low_cst (range, 0) + 1;
2432*e4b17023SJohn Marino labelvec = XALLOCAVEC (rtx, ncases);
2433*e4b17023SJohn Marino memset (labelvec, 0, ncases * sizeof (rtx));
2434*e4b17023SJohn Marino
2435*e4b17023SJohn Marino for (n = case_list; n; n = n->right)
2436*e4b17023SJohn Marino {
2437*e4b17023SJohn Marino /* Compute the low and high bounds relative to the minimum
2438*e4b17023SJohn Marino value since that should fit in a HOST_WIDE_INT while the
2439*e4b17023SJohn Marino actual values may not. */
2440*e4b17023SJohn Marino HOST_WIDE_INT i_low
2441*e4b17023SJohn Marino = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2442*e4b17023SJohn Marino n->low, minval), 1);
2443*e4b17023SJohn Marino HOST_WIDE_INT i_high
2444*e4b17023SJohn Marino = tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
2445*e4b17023SJohn Marino n->high, minval), 1);
2446*e4b17023SJohn Marino HOST_WIDE_INT i;
2447*e4b17023SJohn Marino
2448*e4b17023SJohn Marino for (i = i_low; i <= i_high; i ++)
2449*e4b17023SJohn Marino labelvec[i]
2450*e4b17023SJohn Marino = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
2451*e4b17023SJohn Marino }
2452*e4b17023SJohn Marino
2453*e4b17023SJohn Marino /* Fill in the gaps with the default. We may have gaps at
2454*e4b17023SJohn Marino the beginning if we tried to avoid the minval subtraction,
2455*e4b17023SJohn Marino so substitute some label even if the default label was
2456*e4b17023SJohn Marino deemed unreachable. */
2457*e4b17023SJohn Marino if (!default_label)
2458*e4b17023SJohn Marino default_label = fallback_label;
2459*e4b17023SJohn Marino for (i = 0; i < ncases; i++)
2460*e4b17023SJohn Marino if (labelvec[i] == 0)
2461*e4b17023SJohn Marino labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
2462*e4b17023SJohn Marino
2463*e4b17023SJohn Marino /* Output the table. */
2464*e4b17023SJohn Marino emit_label (table_label);
2465*e4b17023SJohn Marino
2466*e4b17023SJohn Marino if (CASE_VECTOR_PC_RELATIVE || flag_pic)
2467*e4b17023SJohn Marino emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
2468*e4b17023SJohn Marino gen_rtx_LABEL_REF (Pmode, table_label),
2469*e4b17023SJohn Marino gen_rtvec_v (ncases, labelvec),
2470*e4b17023SJohn Marino const0_rtx, const0_rtx));
2471*e4b17023SJohn Marino else
2472*e4b17023SJohn Marino emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
2473*e4b17023SJohn Marino gen_rtvec_v (ncases, labelvec)));
2474*e4b17023SJohn Marino
2475*e4b17023SJohn Marino /* Record no drop-through after the table. */
2476*e4b17023SJohn Marino emit_barrier ();
2477*e4b17023SJohn Marino }
2478*e4b17023SJohn Marino
2479*e4b17023SJohn Marino before_case = NEXT_INSN (before_case);
2480*e4b17023SJohn Marino end = get_last_insn ();
2481*e4b17023SJohn Marino reorder_insns (before_case, end, start);
2482*e4b17023SJohn Marino }
2483*e4b17023SJohn Marino
2484*e4b17023SJohn Marino free_temp_slots ();
2485*e4b17023SJohn Marino free_alloc_pool (case_node_pool);
2486*e4b17023SJohn Marino }
2487*e4b17023SJohn Marino
2488*e4b17023SJohn Marino /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */
2489*e4b17023SJohn Marino
2490*e4b17023SJohn Marino static void
do_jump_if_equal(enum machine_mode mode,rtx op0,rtx op1,rtx label,int unsignedp)2491*e4b17023SJohn Marino do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label,
2492*e4b17023SJohn Marino int unsignedp)
2493*e4b17023SJohn Marino {
2494*e4b17023SJohn Marino do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode,
2495*e4b17023SJohn Marino NULL_RTX, NULL_RTX, label, -1);
2496*e4b17023SJohn Marino }
2497*e4b17023SJohn Marino
2498*e4b17023SJohn Marino /* Not all case values are encountered equally. This function
2499*e4b17023SJohn Marino uses a heuristic to weight case labels, in cases where that
2500*e4b17023SJohn Marino looks like a reasonable thing to do.
2501*e4b17023SJohn Marino
2502*e4b17023SJohn Marino Right now, all we try to guess is text, and we establish the
2503*e4b17023SJohn Marino following weights:
2504*e4b17023SJohn Marino
2505*e4b17023SJohn Marino chars above space: 16
2506*e4b17023SJohn Marino digits: 16
2507*e4b17023SJohn Marino default: 12
2508*e4b17023SJohn Marino space, punct: 8
2509*e4b17023SJohn Marino tab: 4
2510*e4b17023SJohn Marino newline: 2
2511*e4b17023SJohn Marino other "\" chars: 1
2512*e4b17023SJohn Marino remaining chars: 0
2513*e4b17023SJohn Marino
2514*e4b17023SJohn Marino If we find any cases in the switch that are not either -1 or in the range
2515*e4b17023SJohn Marino of valid ASCII characters, or are control characters other than those
2516*e4b17023SJohn Marino commonly used with "\", don't treat this switch scanning text.
2517*e4b17023SJohn Marino
2518*e4b17023SJohn Marino Return 1 if these nodes are suitable for cost estimation, otherwise
2519*e4b17023SJohn Marino return 0. */
2520*e4b17023SJohn Marino
2521*e4b17023SJohn Marino static int
estimate_case_costs(case_node_ptr node)2522*e4b17023SJohn Marino estimate_case_costs (case_node_ptr node)
2523*e4b17023SJohn Marino {
2524*e4b17023SJohn Marino tree min_ascii = integer_minus_one_node;
2525*e4b17023SJohn Marino tree max_ascii = build_int_cst (TREE_TYPE (node->high), 127);
2526*e4b17023SJohn Marino case_node_ptr n;
2527*e4b17023SJohn Marino int i;
2528*e4b17023SJohn Marino
2529*e4b17023SJohn Marino /* If we haven't already made the cost table, make it now. Note that the
2530*e4b17023SJohn Marino lower bound of the table is -1, not zero. */
2531*e4b17023SJohn Marino
2532*e4b17023SJohn Marino if (! cost_table_initialized)
2533*e4b17023SJohn Marino {
2534*e4b17023SJohn Marino cost_table_initialized = 1;
2535*e4b17023SJohn Marino
2536*e4b17023SJohn Marino for (i = 0; i < 128; i++)
2537*e4b17023SJohn Marino {
2538*e4b17023SJohn Marino if (ISALNUM (i))
2539*e4b17023SJohn Marino COST_TABLE (i) = 16;
2540*e4b17023SJohn Marino else if (ISPUNCT (i))
2541*e4b17023SJohn Marino COST_TABLE (i) = 8;
2542*e4b17023SJohn Marino else if (ISCNTRL (i))
2543*e4b17023SJohn Marino COST_TABLE (i) = -1;
2544*e4b17023SJohn Marino }
2545*e4b17023SJohn Marino
2546*e4b17023SJohn Marino COST_TABLE (' ') = 8;
2547*e4b17023SJohn Marino COST_TABLE ('\t') = 4;
2548*e4b17023SJohn Marino COST_TABLE ('\0') = 4;
2549*e4b17023SJohn Marino COST_TABLE ('\n') = 2;
2550*e4b17023SJohn Marino COST_TABLE ('\f') = 1;
2551*e4b17023SJohn Marino COST_TABLE ('\v') = 1;
2552*e4b17023SJohn Marino COST_TABLE ('\b') = 1;
2553*e4b17023SJohn Marino }
2554*e4b17023SJohn Marino
2555*e4b17023SJohn Marino /* See if all the case expressions look like text. It is text if the
2556*e4b17023SJohn Marino constant is >= -1 and the highest constant is <= 127. Do all comparisons
2557*e4b17023SJohn Marino as signed arithmetic since we don't want to ever access cost_table with a
2558*e4b17023SJohn Marino value less than -1. Also check that none of the constants in a range
2559*e4b17023SJohn Marino are strange control characters. */
2560*e4b17023SJohn Marino
2561*e4b17023SJohn Marino for (n = node; n; n = n->right)
2562*e4b17023SJohn Marino {
2563*e4b17023SJohn Marino if (tree_int_cst_lt (n->low, min_ascii)
2564*e4b17023SJohn Marino || tree_int_cst_lt (max_ascii, n->high))
2565*e4b17023SJohn Marino return 0;
2566*e4b17023SJohn Marino
2567*e4b17023SJohn Marino for (i = (HOST_WIDE_INT) TREE_INT_CST_LOW (n->low);
2568*e4b17023SJohn Marino i <= (HOST_WIDE_INT) TREE_INT_CST_LOW (n->high); i++)
2569*e4b17023SJohn Marino if (COST_TABLE (i) < 0)
2570*e4b17023SJohn Marino return 0;
2571*e4b17023SJohn Marino }
2572*e4b17023SJohn Marino
2573*e4b17023SJohn Marino /* All interesting values are within the range of interesting
2574*e4b17023SJohn Marino ASCII characters. */
2575*e4b17023SJohn Marino return 1;
2576*e4b17023SJohn Marino }
2577*e4b17023SJohn Marino
2578*e4b17023SJohn Marino /* Take an ordered list of case nodes
2579*e4b17023SJohn Marino and transform them into a near optimal binary tree,
2580*e4b17023SJohn Marino on the assumption that any target code selection value is as
2581*e4b17023SJohn Marino likely as any other.
2582*e4b17023SJohn Marino
2583*e4b17023SJohn Marino The transformation is performed by splitting the ordered
2584*e4b17023SJohn Marino list into two equal sections plus a pivot. The parts are
2585*e4b17023SJohn Marino then attached to the pivot as left and right branches. Each
2586*e4b17023SJohn Marino branch is then transformed recursively. */
2587*e4b17023SJohn Marino
2588*e4b17023SJohn Marino static void
balance_case_nodes(case_node_ptr * head,case_node_ptr parent)2589*e4b17023SJohn Marino balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
2590*e4b17023SJohn Marino {
2591*e4b17023SJohn Marino case_node_ptr np;
2592*e4b17023SJohn Marino
2593*e4b17023SJohn Marino np = *head;
2594*e4b17023SJohn Marino if (np)
2595*e4b17023SJohn Marino {
2596*e4b17023SJohn Marino int cost = 0;
2597*e4b17023SJohn Marino int i = 0;
2598*e4b17023SJohn Marino int ranges = 0;
2599*e4b17023SJohn Marino case_node_ptr *npp;
2600*e4b17023SJohn Marino case_node_ptr left;
2601*e4b17023SJohn Marino
2602*e4b17023SJohn Marino /* Count the number of entries on branch. Also count the ranges. */
2603*e4b17023SJohn Marino
2604*e4b17023SJohn Marino while (np)
2605*e4b17023SJohn Marino {
2606*e4b17023SJohn Marino if (!tree_int_cst_equal (np->low, np->high))
2607*e4b17023SJohn Marino {
2608*e4b17023SJohn Marino ranges++;
2609*e4b17023SJohn Marino if (use_cost_table)
2610*e4b17023SJohn Marino cost += COST_TABLE (TREE_INT_CST_LOW (np->high));
2611*e4b17023SJohn Marino }
2612*e4b17023SJohn Marino
2613*e4b17023SJohn Marino if (use_cost_table)
2614*e4b17023SJohn Marino cost += COST_TABLE (TREE_INT_CST_LOW (np->low));
2615*e4b17023SJohn Marino
2616*e4b17023SJohn Marino i++;
2617*e4b17023SJohn Marino np = np->right;
2618*e4b17023SJohn Marino }
2619*e4b17023SJohn Marino
2620*e4b17023SJohn Marino if (i > 2)
2621*e4b17023SJohn Marino {
2622*e4b17023SJohn Marino /* Split this list if it is long enough for that to help. */
2623*e4b17023SJohn Marino npp = head;
2624*e4b17023SJohn Marino left = *npp;
2625*e4b17023SJohn Marino if (use_cost_table)
2626*e4b17023SJohn Marino {
2627*e4b17023SJohn Marino /* Find the place in the list that bisects the list's total cost,
2628*e4b17023SJohn Marino Here I gets half the total cost. */
2629*e4b17023SJohn Marino int n_moved = 0;
2630*e4b17023SJohn Marino i = (cost + 1) / 2;
2631*e4b17023SJohn Marino while (1)
2632*e4b17023SJohn Marino {
2633*e4b17023SJohn Marino /* Skip nodes while their cost does not reach that amount. */
2634*e4b17023SJohn Marino if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
2635*e4b17023SJohn Marino i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->high));
2636*e4b17023SJohn Marino i -= COST_TABLE (TREE_INT_CST_LOW ((*npp)->low));
2637*e4b17023SJohn Marino if (i <= 0)
2638*e4b17023SJohn Marino break;
2639*e4b17023SJohn Marino npp = &(*npp)->right;
2640*e4b17023SJohn Marino n_moved += 1;
2641*e4b17023SJohn Marino }
2642*e4b17023SJohn Marino if (n_moved == 0)
2643*e4b17023SJohn Marino {
2644*e4b17023SJohn Marino /* Leave this branch lopsided, but optimize left-hand
2645*e4b17023SJohn Marino side and fill in `parent' fields for right-hand side. */
2646*e4b17023SJohn Marino np = *head;
2647*e4b17023SJohn Marino np->parent = parent;
2648*e4b17023SJohn Marino balance_case_nodes (&np->left, np);
2649*e4b17023SJohn Marino for (; np->right; np = np->right)
2650*e4b17023SJohn Marino np->right->parent = np;
2651*e4b17023SJohn Marino return;
2652*e4b17023SJohn Marino }
2653*e4b17023SJohn Marino }
2654*e4b17023SJohn Marino /* If there are just three nodes, split at the middle one. */
2655*e4b17023SJohn Marino else if (i == 3)
2656*e4b17023SJohn Marino npp = &(*npp)->right;
2657*e4b17023SJohn Marino else
2658*e4b17023SJohn Marino {
2659*e4b17023SJohn Marino /* Find the place in the list that bisects the list's total cost,
2660*e4b17023SJohn Marino where ranges count as 2.
2661*e4b17023SJohn Marino Here I gets half the total cost. */
2662*e4b17023SJohn Marino i = (i + ranges + 1) / 2;
2663*e4b17023SJohn Marino while (1)
2664*e4b17023SJohn Marino {
2665*e4b17023SJohn Marino /* Skip nodes while their cost does not reach that amount. */
2666*e4b17023SJohn Marino if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
2667*e4b17023SJohn Marino i--;
2668*e4b17023SJohn Marino i--;
2669*e4b17023SJohn Marino if (i <= 0)
2670*e4b17023SJohn Marino break;
2671*e4b17023SJohn Marino npp = &(*npp)->right;
2672*e4b17023SJohn Marino }
2673*e4b17023SJohn Marino }
2674*e4b17023SJohn Marino *head = np = *npp;
2675*e4b17023SJohn Marino *npp = 0;
2676*e4b17023SJohn Marino np->parent = parent;
2677*e4b17023SJohn Marino np->left = left;
2678*e4b17023SJohn Marino
2679*e4b17023SJohn Marino /* Optimize each of the two split parts. */
2680*e4b17023SJohn Marino balance_case_nodes (&np->left, np);
2681*e4b17023SJohn Marino balance_case_nodes (&np->right, np);
2682*e4b17023SJohn Marino }
2683*e4b17023SJohn Marino else
2684*e4b17023SJohn Marino {
2685*e4b17023SJohn Marino /* Else leave this branch as one level,
2686*e4b17023SJohn Marino but fill in `parent' fields. */
2687*e4b17023SJohn Marino np = *head;
2688*e4b17023SJohn Marino np->parent = parent;
2689*e4b17023SJohn Marino for (; np->right; np = np->right)
2690*e4b17023SJohn Marino np->right->parent = np;
2691*e4b17023SJohn Marino }
2692*e4b17023SJohn Marino }
2693*e4b17023SJohn Marino }
2694*e4b17023SJohn Marino
2695*e4b17023SJohn Marino /* Search the parent sections of the case node tree
2696*e4b17023SJohn Marino to see if a test for the lower bound of NODE would be redundant.
2697*e4b17023SJohn Marino INDEX_TYPE is the type of the index expression.
2698*e4b17023SJohn Marino
2699*e4b17023SJohn Marino The instructions to generate the case decision tree are
2700*e4b17023SJohn Marino output in the same order as nodes are processed so it is
2701*e4b17023SJohn Marino known that if a parent node checks the range of the current
2702*e4b17023SJohn Marino node minus one that the current node is bounded at its lower
2703*e4b17023SJohn Marino span. Thus the test would be redundant. */
2704*e4b17023SJohn Marino
2705*e4b17023SJohn Marino static int
node_has_low_bound(case_node_ptr node,tree index_type)2706*e4b17023SJohn Marino node_has_low_bound (case_node_ptr node, tree index_type)
2707*e4b17023SJohn Marino {
2708*e4b17023SJohn Marino tree low_minus_one;
2709*e4b17023SJohn Marino case_node_ptr pnode;
2710*e4b17023SJohn Marino
2711*e4b17023SJohn Marino /* If the lower bound of this node is the lowest value in the index type,
2712*e4b17023SJohn Marino we need not test it. */
2713*e4b17023SJohn Marino
2714*e4b17023SJohn Marino if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
2715*e4b17023SJohn Marino return 1;
2716*e4b17023SJohn Marino
2717*e4b17023SJohn Marino /* If this node has a left branch, the value at the left must be less
2718*e4b17023SJohn Marino than that at this node, so it cannot be bounded at the bottom and
2719*e4b17023SJohn Marino we need not bother testing any further. */
2720*e4b17023SJohn Marino
2721*e4b17023SJohn Marino if (node->left)
2722*e4b17023SJohn Marino return 0;
2723*e4b17023SJohn Marino
2724*e4b17023SJohn Marino low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low),
2725*e4b17023SJohn Marino node->low,
2726*e4b17023SJohn Marino build_int_cst (TREE_TYPE (node->low), 1));
2727*e4b17023SJohn Marino
2728*e4b17023SJohn Marino /* If the subtraction above overflowed, we can't verify anything.
2729*e4b17023SJohn Marino Otherwise, look for a parent that tests our value - 1. */
2730*e4b17023SJohn Marino
2731*e4b17023SJohn Marino if (! tree_int_cst_lt (low_minus_one, node->low))
2732*e4b17023SJohn Marino return 0;
2733*e4b17023SJohn Marino
2734*e4b17023SJohn Marino for (pnode = node->parent; pnode; pnode = pnode->parent)
2735*e4b17023SJohn Marino if (tree_int_cst_equal (low_minus_one, pnode->high))
2736*e4b17023SJohn Marino return 1;
2737*e4b17023SJohn Marino
2738*e4b17023SJohn Marino return 0;
2739*e4b17023SJohn Marino }
2740*e4b17023SJohn Marino
2741*e4b17023SJohn Marino /* Search the parent sections of the case node tree
2742*e4b17023SJohn Marino to see if a test for the upper bound of NODE would be redundant.
2743*e4b17023SJohn Marino INDEX_TYPE is the type of the index expression.
2744*e4b17023SJohn Marino
2745*e4b17023SJohn Marino The instructions to generate the case decision tree are
2746*e4b17023SJohn Marino output in the same order as nodes are processed so it is
2747*e4b17023SJohn Marino known that if a parent node checks the range of the current
2748*e4b17023SJohn Marino node plus one that the current node is bounded at its upper
2749*e4b17023SJohn Marino span. Thus the test would be redundant. */
2750*e4b17023SJohn Marino
2751*e4b17023SJohn Marino static int
node_has_high_bound(case_node_ptr node,tree index_type)2752*e4b17023SJohn Marino node_has_high_bound (case_node_ptr node, tree index_type)
2753*e4b17023SJohn Marino {
2754*e4b17023SJohn Marino tree high_plus_one;
2755*e4b17023SJohn Marino case_node_ptr pnode;
2756*e4b17023SJohn Marino
2757*e4b17023SJohn Marino /* If there is no upper bound, obviously no test is needed. */
2758*e4b17023SJohn Marino
2759*e4b17023SJohn Marino if (TYPE_MAX_VALUE (index_type) == NULL)
2760*e4b17023SJohn Marino return 1;
2761*e4b17023SJohn Marino
2762*e4b17023SJohn Marino /* If the upper bound of this node is the highest value in the type
2763*e4b17023SJohn Marino of the index expression, we need not test against it. */
2764*e4b17023SJohn Marino
2765*e4b17023SJohn Marino if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
2766*e4b17023SJohn Marino return 1;
2767*e4b17023SJohn Marino
2768*e4b17023SJohn Marino /* If this node has a right branch, the value at the right must be greater
2769*e4b17023SJohn Marino than that at this node, so it cannot be bounded at the top and
2770*e4b17023SJohn Marino we need not bother testing any further. */
2771*e4b17023SJohn Marino
2772*e4b17023SJohn Marino if (node->right)
2773*e4b17023SJohn Marino return 0;
2774*e4b17023SJohn Marino
2775*e4b17023SJohn Marino high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high),
2776*e4b17023SJohn Marino node->high,
2777*e4b17023SJohn Marino build_int_cst (TREE_TYPE (node->high), 1));
2778*e4b17023SJohn Marino
2779*e4b17023SJohn Marino /* If the addition above overflowed, we can't verify anything.
2780*e4b17023SJohn Marino Otherwise, look for a parent that tests our value + 1. */
2781*e4b17023SJohn Marino
2782*e4b17023SJohn Marino if (! tree_int_cst_lt (node->high, high_plus_one))
2783*e4b17023SJohn Marino return 0;
2784*e4b17023SJohn Marino
2785*e4b17023SJohn Marino for (pnode = node->parent; pnode; pnode = pnode->parent)
2786*e4b17023SJohn Marino if (tree_int_cst_equal (high_plus_one, pnode->low))
2787*e4b17023SJohn Marino return 1;
2788*e4b17023SJohn Marino
2789*e4b17023SJohn Marino return 0;
2790*e4b17023SJohn Marino }
2791*e4b17023SJohn Marino
2792*e4b17023SJohn Marino /* Search the parent sections of the
2793*e4b17023SJohn Marino case node tree to see if both tests for the upper and lower
2794*e4b17023SJohn Marino bounds of NODE would be redundant. */
2795*e4b17023SJohn Marino
2796*e4b17023SJohn Marino static int
node_is_bounded(case_node_ptr node,tree index_type)2797*e4b17023SJohn Marino node_is_bounded (case_node_ptr node, tree index_type)
2798*e4b17023SJohn Marino {
2799*e4b17023SJohn Marino return (node_has_low_bound (node, index_type)
2800*e4b17023SJohn Marino && node_has_high_bound (node, index_type));
2801*e4b17023SJohn Marino }
2802*e4b17023SJohn Marino
2803*e4b17023SJohn Marino /* Emit step-by-step code to select a case for the value of INDEX.
2804*e4b17023SJohn Marino The thus generated decision tree follows the form of the
2805*e4b17023SJohn Marino case-node binary tree NODE, whose nodes represent test conditions.
2806*e4b17023SJohn Marino INDEX_TYPE is the type of the index of the switch.
2807*e4b17023SJohn Marino
2808*e4b17023SJohn Marino Care is taken to prune redundant tests from the decision tree
2809*e4b17023SJohn Marino by detecting any boundary conditions already checked by
2810*e4b17023SJohn Marino emitted rtx. (See node_has_high_bound, node_has_low_bound
2811*e4b17023SJohn Marino and node_is_bounded, above.)
2812*e4b17023SJohn Marino
2813*e4b17023SJohn Marino Where the test conditions can be shown to be redundant we emit
2814*e4b17023SJohn Marino an unconditional jump to the target code. As a further
2815*e4b17023SJohn Marino optimization, the subordinates of a tree node are examined to
2816*e4b17023SJohn Marino check for bounded nodes. In this case conditional and/or
2817*e4b17023SJohn Marino unconditional jumps as a result of the boundary check for the
2818*e4b17023SJohn Marino current node are arranged to target the subordinates associated
2819*e4b17023SJohn Marino code for out of bound conditions on the current node.
2820*e4b17023SJohn Marino
2821*e4b17023SJohn Marino We can assume that when control reaches the code generated here,
2822*e4b17023SJohn Marino the index value has already been compared with the parents
2823*e4b17023SJohn Marino of this node, and determined to be on the same side of each parent
2824*e4b17023SJohn Marino as this node is. Thus, if this node tests for the value 51,
2825*e4b17023SJohn Marino and a parent tested for 52, we don't need to consider
2826*e4b17023SJohn Marino the possibility of a value greater than 51. If another parent
2827*e4b17023SJohn Marino tests for the value 50, then this node need not test anything. */
2828*e4b17023SJohn Marino
2829*e4b17023SJohn Marino static void
emit_case_nodes(rtx index,case_node_ptr node,rtx default_label,tree index_type)2830*e4b17023SJohn Marino emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
2831*e4b17023SJohn Marino tree index_type)
2832*e4b17023SJohn Marino {
2833*e4b17023SJohn Marino /* If INDEX has an unsigned type, we must make unsigned branches. */
2834*e4b17023SJohn Marino int unsignedp = TYPE_UNSIGNED (index_type);
2835*e4b17023SJohn Marino enum machine_mode mode = GET_MODE (index);
2836*e4b17023SJohn Marino enum machine_mode imode = TYPE_MODE (index_type);
2837*e4b17023SJohn Marino
2838*e4b17023SJohn Marino /* Handle indices detected as constant during RTL expansion. */
2839*e4b17023SJohn Marino if (mode == VOIDmode)
2840*e4b17023SJohn Marino mode = imode;
2841*e4b17023SJohn Marino
2842*e4b17023SJohn Marino /* See if our parents have already tested everything for us.
2843*e4b17023SJohn Marino If they have, emit an unconditional jump for this node. */
2844*e4b17023SJohn Marino if (node_is_bounded (node, index_type))
2845*e4b17023SJohn Marino emit_jump (label_rtx (node->code_label));
2846*e4b17023SJohn Marino
2847*e4b17023SJohn Marino else if (tree_int_cst_equal (node->low, node->high))
2848*e4b17023SJohn Marino {
2849*e4b17023SJohn Marino /* Node is single valued. First see if the index expression matches
2850*e4b17023SJohn Marino this node and then check our children, if any. */
2851*e4b17023SJohn Marino
2852*e4b17023SJohn Marino do_jump_if_equal (mode, index,
2853*e4b17023SJohn Marino convert_modes (mode, imode,
2854*e4b17023SJohn Marino expand_normal (node->low),
2855*e4b17023SJohn Marino unsignedp),
2856*e4b17023SJohn Marino label_rtx (node->code_label), unsignedp);
2857*e4b17023SJohn Marino
2858*e4b17023SJohn Marino if (node->right != 0 && node->left != 0)
2859*e4b17023SJohn Marino {
2860*e4b17023SJohn Marino /* This node has children on both sides.
2861*e4b17023SJohn Marino Dispatch to one side or the other
2862*e4b17023SJohn Marino by comparing the index value with this node's value.
2863*e4b17023SJohn Marino If one subtree is bounded, check that one first,
2864*e4b17023SJohn Marino so we can avoid real branches in the tree. */
2865*e4b17023SJohn Marino
2866*e4b17023SJohn Marino if (node_is_bounded (node->right, index_type))
2867*e4b17023SJohn Marino {
2868*e4b17023SJohn Marino emit_cmp_and_jump_insns (index,
2869*e4b17023SJohn Marino convert_modes
2870*e4b17023SJohn Marino (mode, imode,
2871*e4b17023SJohn Marino expand_normal (node->high),
2872*e4b17023SJohn Marino unsignedp),
2873*e4b17023SJohn Marino GT, NULL_RTX, mode, unsignedp,
2874*e4b17023SJohn Marino label_rtx (node->right->code_label));
2875*e4b17023SJohn Marino emit_case_nodes (index, node->left, default_label, index_type);
2876*e4b17023SJohn Marino }
2877*e4b17023SJohn Marino
2878*e4b17023SJohn Marino else if (node_is_bounded (node->left, index_type))
2879*e4b17023SJohn Marino {
2880*e4b17023SJohn Marino emit_cmp_and_jump_insns (index,
2881*e4b17023SJohn Marino convert_modes
2882*e4b17023SJohn Marino (mode, imode,
2883*e4b17023SJohn Marino expand_normal (node->high),
2884*e4b17023SJohn Marino unsignedp),
2885*e4b17023SJohn Marino LT, NULL_RTX, mode, unsignedp,
2886*e4b17023SJohn Marino label_rtx (node->left->code_label));
2887*e4b17023SJohn Marino emit_case_nodes (index, node->right, default_label, index_type);
2888*e4b17023SJohn Marino }
2889*e4b17023SJohn Marino
2890*e4b17023SJohn Marino /* If both children are single-valued cases with no
2891*e4b17023SJohn Marino children, finish up all the work. This way, we can save
2892*e4b17023SJohn Marino one ordered comparison. */
2893*e4b17023SJohn Marino else if (tree_int_cst_equal (node->right->low, node->right->high)
2894*e4b17023SJohn Marino && node->right->left == 0
2895*e4b17023SJohn Marino && node->right->right == 0
2896*e4b17023SJohn Marino && tree_int_cst_equal (node->left->low, node->left->high)
2897*e4b17023SJohn Marino && node->left->left == 0
2898*e4b17023SJohn Marino && node->left->right == 0)
2899*e4b17023SJohn Marino {
2900*e4b17023SJohn Marino /* Neither node is bounded. First distinguish the two sides;
2901*e4b17023SJohn Marino then emit the code for one side at a time. */
2902*e4b17023SJohn Marino
2903*e4b17023SJohn Marino /* See if the value matches what the right hand side
2904*e4b17023SJohn Marino wants. */
2905*e4b17023SJohn Marino do_jump_if_equal (mode, index,
2906*e4b17023SJohn Marino convert_modes (mode, imode,
2907*e4b17023SJohn Marino expand_normal (node->right->low),
2908*e4b17023SJohn Marino unsignedp),
2909*e4b17023SJohn Marino label_rtx (node->right->code_label),
2910*e4b17023SJohn Marino unsignedp);
2911*e4b17023SJohn Marino
2912*e4b17023SJohn Marino /* See if the value matches what the left hand side
2913*e4b17023SJohn Marino wants. */
2914*e4b17023SJohn Marino do_jump_if_equal (mode, index,
2915*e4b17023SJohn Marino convert_modes (mode, imode,
2916*e4b17023SJohn Marino expand_normal (node->left->low),
2917*e4b17023SJohn Marino unsignedp),
2918*e4b17023SJohn Marino label_rtx (node->left->code_label),
2919*e4b17023SJohn Marino unsignedp);
2920*e4b17023SJohn Marino }
2921*e4b17023SJohn Marino
2922*e4b17023SJohn Marino else
2923*e4b17023SJohn Marino {
2924*e4b17023SJohn Marino /* Neither node is bounded. First distinguish the two sides;
2925*e4b17023SJohn Marino then emit the code for one side at a time. */
2926*e4b17023SJohn Marino
2927*e4b17023SJohn Marino tree test_label
2928*e4b17023SJohn Marino = build_decl (CURR_INSN_LOCATION,
2929*e4b17023SJohn Marino LABEL_DECL, NULL_TREE, NULL_TREE);
2930*e4b17023SJohn Marino
2931*e4b17023SJohn Marino /* See if the value is on the right. */
2932*e4b17023SJohn Marino emit_cmp_and_jump_insns (index,
2933*e4b17023SJohn Marino convert_modes
2934*e4b17023SJohn Marino (mode, imode,
2935*e4b17023SJohn Marino expand_normal (node->high),
2936*e4b17023SJohn Marino unsignedp),
2937*e4b17023SJohn Marino GT, NULL_RTX, mode, unsignedp,
2938*e4b17023SJohn Marino label_rtx (test_label));
2939*e4b17023SJohn Marino
2940*e4b17023SJohn Marino /* Value must be on the left.
2941*e4b17023SJohn Marino Handle the left-hand subtree. */
2942*e4b17023SJohn Marino emit_case_nodes (index, node->left, default_label, index_type);
2943*e4b17023SJohn Marino /* If left-hand subtree does nothing,
2944*e4b17023SJohn Marino go to default. */
2945*e4b17023SJohn Marino if (default_label)
2946*e4b17023SJohn Marino emit_jump (default_label);
2947*e4b17023SJohn Marino
2948*e4b17023SJohn Marino /* Code branches here for the right-hand subtree. */
2949*e4b17023SJohn Marino expand_label (test_label);
2950*e4b17023SJohn Marino emit_case_nodes (index, node->right, default_label, index_type);
2951*e4b17023SJohn Marino }
2952*e4b17023SJohn Marino }
2953*e4b17023SJohn Marino
2954*e4b17023SJohn Marino else if (node->right != 0 && node->left == 0)
2955*e4b17023SJohn Marino {
2956*e4b17023SJohn Marino /* Here we have a right child but no left so we issue a conditional
2957*e4b17023SJohn Marino branch to default and process the right child.
2958*e4b17023SJohn Marino
2959*e4b17023SJohn Marino Omit the conditional branch to default if the right child
2960*e4b17023SJohn Marino does not have any children and is single valued; it would
2961*e4b17023SJohn Marino cost too much space to save so little time. */
2962*e4b17023SJohn Marino
2963*e4b17023SJohn Marino if (node->right->right || node->right->left
2964*e4b17023SJohn Marino || !tree_int_cst_equal (node->right->low, node->right->high))
2965*e4b17023SJohn Marino {
2966*e4b17023SJohn Marino if (!node_has_low_bound (node, index_type))
2967*e4b17023SJohn Marino {
2968*e4b17023SJohn Marino emit_cmp_and_jump_insns (index,
2969*e4b17023SJohn Marino convert_modes
2970*e4b17023SJohn Marino (mode, imode,
2971*e4b17023SJohn Marino expand_normal (node->high),
2972*e4b17023SJohn Marino unsignedp),
2973*e4b17023SJohn Marino LT, NULL_RTX, mode, unsignedp,
2974*e4b17023SJohn Marino default_label);
2975*e4b17023SJohn Marino }
2976*e4b17023SJohn Marino
2977*e4b17023SJohn Marino emit_case_nodes (index, node->right, default_label, index_type);
2978*e4b17023SJohn Marino }
2979*e4b17023SJohn Marino else
2980*e4b17023SJohn Marino /* We cannot process node->right normally
2981*e4b17023SJohn Marino since we haven't ruled out the numbers less than
2982*e4b17023SJohn Marino this node's value. So handle node->right explicitly. */
2983*e4b17023SJohn Marino do_jump_if_equal (mode, index,
2984*e4b17023SJohn Marino convert_modes
2985*e4b17023SJohn Marino (mode, imode,
2986*e4b17023SJohn Marino expand_normal (node->right->low),
2987*e4b17023SJohn Marino unsignedp),
2988*e4b17023SJohn Marino label_rtx (node->right->code_label), unsignedp);
2989*e4b17023SJohn Marino }
2990*e4b17023SJohn Marino
2991*e4b17023SJohn Marino else if (node->right == 0 && node->left != 0)
2992*e4b17023SJohn Marino {
2993*e4b17023SJohn Marino /* Just one subtree, on the left. */
2994*e4b17023SJohn Marino if (node->left->left || node->left->right
2995*e4b17023SJohn Marino || !tree_int_cst_equal (node->left->low, node->left->high))
2996*e4b17023SJohn Marino {
2997*e4b17023SJohn Marino if (!node_has_high_bound (node, index_type))
2998*e4b17023SJohn Marino {
2999*e4b17023SJohn Marino emit_cmp_and_jump_insns (index,
3000*e4b17023SJohn Marino convert_modes
3001*e4b17023SJohn Marino (mode, imode,
3002*e4b17023SJohn Marino expand_normal (node->high),
3003*e4b17023SJohn Marino unsignedp),
3004*e4b17023SJohn Marino GT, NULL_RTX, mode, unsignedp,
3005*e4b17023SJohn Marino default_label);
3006*e4b17023SJohn Marino }
3007*e4b17023SJohn Marino
3008*e4b17023SJohn Marino emit_case_nodes (index, node->left, default_label, index_type);
3009*e4b17023SJohn Marino }
3010*e4b17023SJohn Marino else
3011*e4b17023SJohn Marino /* We cannot process node->left normally
3012*e4b17023SJohn Marino since we haven't ruled out the numbers less than
3013*e4b17023SJohn Marino this node's value. So handle node->left explicitly. */
3014*e4b17023SJohn Marino do_jump_if_equal (mode, index,
3015*e4b17023SJohn Marino convert_modes
3016*e4b17023SJohn Marino (mode, imode,
3017*e4b17023SJohn Marino expand_normal (node->left->low),
3018*e4b17023SJohn Marino unsignedp),
3019*e4b17023SJohn Marino label_rtx (node->left->code_label), unsignedp);
3020*e4b17023SJohn Marino }
3021*e4b17023SJohn Marino }
3022*e4b17023SJohn Marino else
3023*e4b17023SJohn Marino {
3024*e4b17023SJohn Marino /* Node is a range. These cases are very similar to those for a single
3025*e4b17023SJohn Marino value, except that we do not start by testing whether this node
3026*e4b17023SJohn Marino is the one to branch to. */
3027*e4b17023SJohn Marino
3028*e4b17023SJohn Marino if (node->right != 0 && node->left != 0)
3029*e4b17023SJohn Marino {
3030*e4b17023SJohn Marino /* Node has subtrees on both sides.
3031*e4b17023SJohn Marino If the right-hand subtree is bounded,
3032*e4b17023SJohn Marino test for it first, since we can go straight there.
3033*e4b17023SJohn Marino Otherwise, we need to make a branch in the control structure,
3034*e4b17023SJohn Marino then handle the two subtrees. */
3035*e4b17023SJohn Marino tree test_label = 0;
3036*e4b17023SJohn Marino
3037*e4b17023SJohn Marino if (node_is_bounded (node->right, index_type))
3038*e4b17023SJohn Marino /* Right hand node is fully bounded so we can eliminate any
3039*e4b17023SJohn Marino testing and branch directly to the target code. */
3040*e4b17023SJohn Marino emit_cmp_and_jump_insns (index,
3041*e4b17023SJohn Marino convert_modes
3042*e4b17023SJohn Marino (mode, imode,
3043*e4b17023SJohn Marino expand_normal (node->high),
3044*e4b17023SJohn Marino unsignedp),
3045*e4b17023SJohn Marino GT, NULL_RTX, mode, unsignedp,
3046*e4b17023SJohn Marino label_rtx (node->right->code_label));
3047*e4b17023SJohn Marino else
3048*e4b17023SJohn Marino {
3049*e4b17023SJohn Marino /* Right hand node requires testing.
3050*e4b17023SJohn Marino Branch to a label where we will handle it later. */
3051*e4b17023SJohn Marino
3052*e4b17023SJohn Marino test_label = build_decl (CURR_INSN_LOCATION,
3053*e4b17023SJohn Marino LABEL_DECL, NULL_TREE, NULL_TREE);
3054*e4b17023SJohn Marino emit_cmp_and_jump_insns (index,
3055*e4b17023SJohn Marino convert_modes
3056*e4b17023SJohn Marino (mode, imode,
3057*e4b17023SJohn Marino expand_normal (node->high),
3058*e4b17023SJohn Marino unsignedp),
3059*e4b17023SJohn Marino GT, NULL_RTX, mode, unsignedp,
3060*e4b17023SJohn Marino label_rtx (test_label));
3061*e4b17023SJohn Marino }
3062*e4b17023SJohn Marino
3063*e4b17023SJohn Marino /* Value belongs to this node or to the left-hand subtree. */
3064*e4b17023SJohn Marino
3065*e4b17023SJohn Marino emit_cmp_and_jump_insns (index,
3066*e4b17023SJohn Marino convert_modes
3067*e4b17023SJohn Marino (mode, imode,
3068*e4b17023SJohn Marino expand_normal (node->low),
3069*e4b17023SJohn Marino unsignedp),
3070*e4b17023SJohn Marino GE, NULL_RTX, mode, unsignedp,
3071*e4b17023SJohn Marino label_rtx (node->code_label));
3072*e4b17023SJohn Marino
3073*e4b17023SJohn Marino /* Handle the left-hand subtree. */
3074*e4b17023SJohn Marino emit_case_nodes (index, node->left, default_label, index_type);
3075*e4b17023SJohn Marino
3076*e4b17023SJohn Marino /* If right node had to be handled later, do that now. */
3077*e4b17023SJohn Marino
3078*e4b17023SJohn Marino if (test_label)
3079*e4b17023SJohn Marino {
3080*e4b17023SJohn Marino /* If the left-hand subtree fell through,
3081*e4b17023SJohn Marino don't let it fall into the right-hand subtree. */
3082*e4b17023SJohn Marino if (default_label)
3083*e4b17023SJohn Marino emit_jump (default_label);
3084*e4b17023SJohn Marino
3085*e4b17023SJohn Marino expand_label (test_label);
3086*e4b17023SJohn Marino emit_case_nodes (index, node->right, default_label, index_type);
3087*e4b17023SJohn Marino }
3088*e4b17023SJohn Marino }
3089*e4b17023SJohn Marino
3090*e4b17023SJohn Marino else if (node->right != 0 && node->left == 0)
3091*e4b17023SJohn Marino {
3092*e4b17023SJohn Marino /* Deal with values to the left of this node,
3093*e4b17023SJohn Marino if they are possible. */
3094*e4b17023SJohn Marino if (!node_has_low_bound (node, index_type))
3095*e4b17023SJohn Marino {
3096*e4b17023SJohn Marino emit_cmp_and_jump_insns (index,
3097*e4b17023SJohn Marino convert_modes
3098*e4b17023SJohn Marino (mode, imode,
3099*e4b17023SJohn Marino expand_normal (node->low),
3100*e4b17023SJohn Marino unsignedp),
3101*e4b17023SJohn Marino LT, NULL_RTX, mode, unsignedp,
3102*e4b17023SJohn Marino default_label);
3103*e4b17023SJohn Marino }
3104*e4b17023SJohn Marino
3105*e4b17023SJohn Marino /* Value belongs to this node or to the right-hand subtree. */
3106*e4b17023SJohn Marino
3107*e4b17023SJohn Marino emit_cmp_and_jump_insns (index,
3108*e4b17023SJohn Marino convert_modes
3109*e4b17023SJohn Marino (mode, imode,
3110*e4b17023SJohn Marino expand_normal (node->high),
3111*e4b17023SJohn Marino unsignedp),
3112*e4b17023SJohn Marino LE, NULL_RTX, mode, unsignedp,
3113*e4b17023SJohn Marino label_rtx (node->code_label));
3114*e4b17023SJohn Marino
3115*e4b17023SJohn Marino emit_case_nodes (index, node->right, default_label, index_type);
3116*e4b17023SJohn Marino }
3117*e4b17023SJohn Marino
3118*e4b17023SJohn Marino else if (node->right == 0 && node->left != 0)
3119*e4b17023SJohn Marino {
3120*e4b17023SJohn Marino /* Deal with values to the right of this node,
3121*e4b17023SJohn Marino if they are possible. */
3122*e4b17023SJohn Marino if (!node_has_high_bound (node, index_type))
3123*e4b17023SJohn Marino {
3124*e4b17023SJohn Marino emit_cmp_and_jump_insns (index,
3125*e4b17023SJohn Marino convert_modes
3126*e4b17023SJohn Marino (mode, imode,
3127*e4b17023SJohn Marino expand_normal (node->high),
3128*e4b17023SJohn Marino unsignedp),
3129*e4b17023SJohn Marino GT, NULL_RTX, mode, unsignedp,
3130*e4b17023SJohn Marino default_label);
3131*e4b17023SJohn Marino }
3132*e4b17023SJohn Marino
3133*e4b17023SJohn Marino /* Value belongs to this node or to the left-hand subtree. */
3134*e4b17023SJohn Marino
3135*e4b17023SJohn Marino emit_cmp_and_jump_insns (index,
3136*e4b17023SJohn Marino convert_modes
3137*e4b17023SJohn Marino (mode, imode,
3138*e4b17023SJohn Marino expand_normal (node->low),
3139*e4b17023SJohn Marino unsignedp),
3140*e4b17023SJohn Marino GE, NULL_RTX, mode, unsignedp,
3141*e4b17023SJohn Marino label_rtx (node->code_label));
3142*e4b17023SJohn Marino
3143*e4b17023SJohn Marino emit_case_nodes (index, node->left, default_label, index_type);
3144*e4b17023SJohn Marino }
3145*e4b17023SJohn Marino
3146*e4b17023SJohn Marino else
3147*e4b17023SJohn Marino {
3148*e4b17023SJohn Marino /* Node has no children so we check low and high bounds to remove
3149*e4b17023SJohn Marino redundant tests. Only one of the bounds can exist,
3150*e4b17023SJohn Marino since otherwise this node is bounded--a case tested already. */
3151*e4b17023SJohn Marino int high_bound = node_has_high_bound (node, index_type);
3152*e4b17023SJohn Marino int low_bound = node_has_low_bound (node, index_type);
3153*e4b17023SJohn Marino
3154*e4b17023SJohn Marino if (!high_bound && low_bound)
3155*e4b17023SJohn Marino {
3156*e4b17023SJohn Marino emit_cmp_and_jump_insns (index,
3157*e4b17023SJohn Marino convert_modes
3158*e4b17023SJohn Marino (mode, imode,
3159*e4b17023SJohn Marino expand_normal (node->high),
3160*e4b17023SJohn Marino unsignedp),
3161*e4b17023SJohn Marino GT, NULL_RTX, mode, unsignedp,
3162*e4b17023SJohn Marino default_label);
3163*e4b17023SJohn Marino }
3164*e4b17023SJohn Marino
3165*e4b17023SJohn Marino else if (!low_bound && high_bound)
3166*e4b17023SJohn Marino {
3167*e4b17023SJohn Marino emit_cmp_and_jump_insns (index,
3168*e4b17023SJohn Marino convert_modes
3169*e4b17023SJohn Marino (mode, imode,
3170*e4b17023SJohn Marino expand_normal (node->low),
3171*e4b17023SJohn Marino unsignedp),
3172*e4b17023SJohn Marino LT, NULL_RTX, mode, unsignedp,
3173*e4b17023SJohn Marino default_label);
3174*e4b17023SJohn Marino }
3175*e4b17023SJohn Marino else if (!low_bound && !high_bound)
3176*e4b17023SJohn Marino {
3177*e4b17023SJohn Marino /* Widen LOW and HIGH to the same width as INDEX. */
3178*e4b17023SJohn Marino tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
3179*e4b17023SJohn Marino tree low = build1 (CONVERT_EXPR, type, node->low);
3180*e4b17023SJohn Marino tree high = build1 (CONVERT_EXPR, type, node->high);
3181*e4b17023SJohn Marino rtx low_rtx, new_index, new_bound;
3182*e4b17023SJohn Marino
3183*e4b17023SJohn Marino /* Instead of doing two branches, emit one unsigned branch for
3184*e4b17023SJohn Marino (index-low) > (high-low). */
3185*e4b17023SJohn Marino low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL);
3186*e4b17023SJohn Marino new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
3187*e4b17023SJohn Marino NULL_RTX, unsignedp,
3188*e4b17023SJohn Marino OPTAB_WIDEN);
3189*e4b17023SJohn Marino new_bound = expand_expr (fold_build2 (MINUS_EXPR, type,
3190*e4b17023SJohn Marino high, low),
3191*e4b17023SJohn Marino NULL_RTX, mode, EXPAND_NORMAL);
3192*e4b17023SJohn Marino
3193*e4b17023SJohn Marino emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
3194*e4b17023SJohn Marino mode, 1, default_label);
3195*e4b17023SJohn Marino }
3196*e4b17023SJohn Marino
3197*e4b17023SJohn Marino emit_jump (label_rtx (node->code_label));
3198*e4b17023SJohn Marino }
3199*e4b17023SJohn Marino }
3200*e4b17023SJohn Marino }
3201