1*404b540aSrobert /* Control flow optimization code for GNU compiler.
2*404b540aSrobert Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3*404b540aSrobert 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4*404b540aSrobert
5*404b540aSrobert This file is part of GCC.
6*404b540aSrobert
7*404b540aSrobert GCC is free software; you can redistribute it and/or modify it under
8*404b540aSrobert the terms of the GNU General Public License as published by the Free
9*404b540aSrobert Software Foundation; either version 2, or (at your option) any later
10*404b540aSrobert version.
11*404b540aSrobert
12*404b540aSrobert GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13*404b540aSrobert WARRANTY; without even the implied warranty of MERCHANTABILITY or
14*404b540aSrobert FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15*404b540aSrobert for more details.
16*404b540aSrobert
17*404b540aSrobert You should have received a copy of the GNU General Public License
18*404b540aSrobert along with GCC; see the file COPYING. If not, write to the Free
19*404b540aSrobert Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20*404b540aSrobert 02110-1301, USA. */
21*404b540aSrobert
22*404b540aSrobert /* Try to match two basic blocks - or their ends - for structural equivalence.
23*404b540aSrobert We scan the blocks from their ends backwards, and expect that insns are
24*404b540aSrobert identical, except for certain cases involving registers. A mismatch
25*404b540aSrobert We scan the blocks from their ends backwards, hoping to find a match, I.e.
26*404b540aSrobert insns are identical, except for certain cases involving registers. A
27*404b540aSrobert mismatch between register number RX (used in block X) and RY (used in the
28*404b540aSrobert same way in block Y) can be handled in one of the following cases:
29*404b540aSrobert 1. RX and RY are local to their respective blocks; they are set there and
30*404b540aSrobert die there. If so, they can effectively be ignored.
31*404b540aSrobert 2. RX and RY die in their blocks, but live at the start. If any path
32*404b540aSrobert gets redirected through X instead of Y, the caller must emit
33*404b540aSrobert compensation code to move RY to RX. If there are overlapping inputs,
34*404b540aSrobert the function resolve_input_conflict ensures that this can be done.
35*404b540aSrobert Information about these registers are tracked in the X_LOCAL, Y_LOCAL,
36*404b540aSrobert LOCAL_COUNT and LOCAL_RVALUE fields.
37*404b540aSrobert 3. RX and RY live throughout their blocks, including the start and the end.
38*404b540aSrobert Either RX and RY must be identical, or we have to replace all uses in
39*404b540aSrobert block X with a new pseudo, which is stored in the INPUT_REG field. The
40*404b540aSrobert caller can then use block X instead of block Y by copying RY to the new
41*404b540aSrobert pseudo.
42*404b540aSrobert
43*404b540aSrobert The main entry point to this file is struct_equiv_block_eq. This function
44*404b540aSrobert uses a struct equiv_info to accept some of its inputs, to keep track of its
45*404b540aSrobert internal state, to pass down to its helper functions, and to communicate
46*404b540aSrobert some of the results back to the caller.
47*404b540aSrobert
48*404b540aSrobert Most scans will result in a failure to match a sufficient number of insns
49*404b540aSrobert to make any optimization worth while, therefore the process is geared more
50*404b540aSrobert to quick scanning rather than the ability to exactly backtrack when we
51*404b540aSrobert find a mismatch. The information gathered is still meaningful to make a
52*404b540aSrobert preliminary decision if we want to do an optimization, we might only
53*404b540aSrobert slightly overestimate the number of matchable insns, and underestimate
54*404b540aSrobert the number of inputs an miss an input conflict. Sufficient information
55*404b540aSrobert is gathered so that when we make another pass, we won't have to backtrack
56*404b540aSrobert at the same point.
57*404b540aSrobert Another issue is that information in memory attributes and/or REG_NOTES
58*404b540aSrobert might have to be merged or discarded to make a valid match. We don't want
59*404b540aSrobert to discard such information when we are not certain that we want to merge
60*404b540aSrobert the two (partial) blocks.
61*404b540aSrobert For these reasons, struct_equiv_block_eq has to be called first with the
62*404b540aSrobert STRUCT_EQUIV_START bit set in the mode parameter. This will calculate the
63*404b540aSrobert number of matched insns and the number and types of inputs. If the
64*404b540aSrobert need_rerun field is set, the results are only tentative, and the caller
65*404b540aSrobert has to call again with STRUCT_EQUIV_RERUN till need_rerun is false in
66*404b540aSrobert order to get a reliable match.
67*404b540aSrobert To install the changes necessary for the match, the function has to be
68*404b540aSrobert called again with STRUCT_EQUIV_FINAL.
69*404b540aSrobert
70*404b540aSrobert While scanning an insn, we process first all the SET_DESTs, then the
71*404b540aSrobert SET_SRCes, then the REG_NOTES, in order to keep the register liveness
72*404b540aSrobert information consistent.
73*404b540aSrobert If we were to mix up the order for sources / destinations in an insn where
74*404b540aSrobert a source is also a destination, we'd end up being mistaken to think that
75*404b540aSrobert the register is not live in the preceding insn. */
76*404b540aSrobert
77*404b540aSrobert #include "config.h"
78*404b540aSrobert #include "system.h"
79*404b540aSrobert #include "coretypes.h"
80*404b540aSrobert #include "tm.h"
81*404b540aSrobert #include "rtl.h"
82*404b540aSrobert #include "regs.h"
83*404b540aSrobert #include "output.h"
84*404b540aSrobert #include "insn-config.h"
85*404b540aSrobert #include "flags.h"
86*404b540aSrobert #include "recog.h"
87*404b540aSrobert #include "tm_p.h"
88*404b540aSrobert #include "target.h"
89*404b540aSrobert #include "emit-rtl.h"
90*404b540aSrobert #include "reload.h"
91*404b540aSrobert
92*404b540aSrobert static void merge_memattrs (rtx, rtx);
93*404b540aSrobert static bool set_dest_equiv_p (rtx x, rtx y, struct equiv_info *info);
94*404b540aSrobert static bool set_dest_addr_equiv_p (rtx x, rtx y, struct equiv_info *info);
95*404b540aSrobert static void find_dying_inputs (struct equiv_info *info);
96*404b540aSrobert static bool resolve_input_conflict (struct equiv_info *info);
97*404b540aSrobert
98*404b540aSrobert /* After reload, some moves, as indicated by SECONDARY_RELOAD_CLASS and
99*404b540aSrobert SECONDARY_MEMORY_NEEDED, cannot be done directly. For our purposes, we
100*404b540aSrobert consider them impossible to generate after reload (even though some
101*404b540aSrobert might be synthesized when you throw enough code at them).
102*404b540aSrobert Since we don't know while processing a cross-jump if a local register
103*404b540aSrobert that is currently live will eventually be live and thus be an input,
104*404b540aSrobert we keep track of potential inputs that would require an impossible move
105*404b540aSrobert by using a prohibitively high cost for them.
106*404b540aSrobert This number, multiplied with the larger of STRUCT_EQUIV_MAX_LOCAL and
107*404b540aSrobert FIRST_PSEUDO_REGISTER, must fit in the input_cost field of
108*404b540aSrobert struct equiv_info. */
109*404b540aSrobert #define IMPOSSIBLE_MOVE_FACTOR 20000
110*404b540aSrobert
111*404b540aSrobert
112*404b540aSrobert
113*404b540aSrobert /* Removes the memory attributes of MEM expression
114*404b540aSrobert if they are not equal. */
115*404b540aSrobert
116*404b540aSrobert void
merge_memattrs(rtx x,rtx y)117*404b540aSrobert merge_memattrs (rtx x, rtx y)
118*404b540aSrobert {
119*404b540aSrobert int i;
120*404b540aSrobert int j;
121*404b540aSrobert enum rtx_code code;
122*404b540aSrobert const char *fmt;
123*404b540aSrobert
124*404b540aSrobert if (x == y)
125*404b540aSrobert return;
126*404b540aSrobert if (x == 0 || y == 0)
127*404b540aSrobert return;
128*404b540aSrobert
129*404b540aSrobert code = GET_CODE (x);
130*404b540aSrobert
131*404b540aSrobert if (code != GET_CODE (y))
132*404b540aSrobert return;
133*404b540aSrobert
134*404b540aSrobert if (GET_MODE (x) != GET_MODE (y))
135*404b540aSrobert return;
136*404b540aSrobert
137*404b540aSrobert if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y))
138*404b540aSrobert {
139*404b540aSrobert if (! MEM_ATTRS (x))
140*404b540aSrobert MEM_ATTRS (y) = 0;
141*404b540aSrobert else if (! MEM_ATTRS (y))
142*404b540aSrobert MEM_ATTRS (x) = 0;
143*404b540aSrobert else
144*404b540aSrobert {
145*404b540aSrobert rtx mem_size;
146*404b540aSrobert
147*404b540aSrobert if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
148*404b540aSrobert {
149*404b540aSrobert set_mem_alias_set (x, 0);
150*404b540aSrobert set_mem_alias_set (y, 0);
151*404b540aSrobert }
152*404b540aSrobert
153*404b540aSrobert if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
154*404b540aSrobert {
155*404b540aSrobert set_mem_expr (x, 0);
156*404b540aSrobert set_mem_expr (y, 0);
157*404b540aSrobert set_mem_offset (x, 0);
158*404b540aSrobert set_mem_offset (y, 0);
159*404b540aSrobert }
160*404b540aSrobert else if (MEM_OFFSET (x) != MEM_OFFSET (y))
161*404b540aSrobert {
162*404b540aSrobert set_mem_offset (x, 0);
163*404b540aSrobert set_mem_offset (y, 0);
164*404b540aSrobert }
165*404b540aSrobert
166*404b540aSrobert if (!MEM_SIZE (x))
167*404b540aSrobert mem_size = NULL_RTX;
168*404b540aSrobert else if (!MEM_SIZE (y))
169*404b540aSrobert mem_size = NULL_RTX;
170*404b540aSrobert else
171*404b540aSrobert mem_size = GEN_INT (MAX (INTVAL (MEM_SIZE (x)),
172*404b540aSrobert INTVAL (MEM_SIZE (y))));
173*404b540aSrobert set_mem_size (x, mem_size);
174*404b540aSrobert set_mem_size (y, mem_size);
175*404b540aSrobert
176*404b540aSrobert set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
177*404b540aSrobert set_mem_align (y, MEM_ALIGN (x));
178*404b540aSrobert }
179*404b540aSrobert }
180*404b540aSrobert
181*404b540aSrobert fmt = GET_RTX_FORMAT (code);
182*404b540aSrobert for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
183*404b540aSrobert {
184*404b540aSrobert switch (fmt[i])
185*404b540aSrobert {
186*404b540aSrobert case 'E':
187*404b540aSrobert /* Two vectors must have the same length. */
188*404b540aSrobert if (XVECLEN (x, i) != XVECLEN (y, i))
189*404b540aSrobert return;
190*404b540aSrobert
191*404b540aSrobert for (j = 0; j < XVECLEN (x, i); j++)
192*404b540aSrobert merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
193*404b540aSrobert
194*404b540aSrobert break;
195*404b540aSrobert
196*404b540aSrobert case 'e':
197*404b540aSrobert merge_memattrs (XEXP (x, i), XEXP (y, i));
198*404b540aSrobert }
199*404b540aSrobert }
200*404b540aSrobert return;
201*404b540aSrobert }
202*404b540aSrobert
203*404b540aSrobert /* In SET, assign the bit for the register number of REG the value VALUE.
204*404b540aSrobert If REG is a hard register, do so for all its constituent registers.
205*404b540aSrobert Return the number of registers that have become included (as a positive
206*404b540aSrobert number) or excluded (as a negative number). */
207*404b540aSrobert static int
assign_reg_reg_set(regset set,rtx reg,int value)208*404b540aSrobert assign_reg_reg_set (regset set, rtx reg, int value)
209*404b540aSrobert {
210*404b540aSrobert unsigned regno = REGNO (reg);
211*404b540aSrobert int nregs, i, old;
212*404b540aSrobert
213*404b540aSrobert if (regno >= FIRST_PSEUDO_REGISTER)
214*404b540aSrobert {
215*404b540aSrobert gcc_assert (!reload_completed);
216*404b540aSrobert nregs = 1;
217*404b540aSrobert }
218*404b540aSrobert else
219*404b540aSrobert nregs = hard_regno_nregs[regno][GET_MODE (reg)];
220*404b540aSrobert for (old = 0, i = nregs; --i >= 0; regno++)
221*404b540aSrobert {
222*404b540aSrobert if ((value != 0) == REGNO_REG_SET_P (set, regno))
223*404b540aSrobert continue;
224*404b540aSrobert if (value)
225*404b540aSrobert old++, SET_REGNO_REG_SET (set, regno);
226*404b540aSrobert else
227*404b540aSrobert old--, CLEAR_REGNO_REG_SET (set, regno);
228*404b540aSrobert }
229*404b540aSrobert return old;
230*404b540aSrobert }
231*404b540aSrobert
232*404b540aSrobert /* Record state about current inputs / local registers / liveness
233*404b540aSrobert in *P. */
234*404b540aSrobert static inline void
struct_equiv_make_checkpoint(struct struct_equiv_checkpoint * p,struct equiv_info * info)235*404b540aSrobert struct_equiv_make_checkpoint (struct struct_equiv_checkpoint *p,
236*404b540aSrobert struct equiv_info *info)
237*404b540aSrobert {
238*404b540aSrobert *p = info->cur;
239*404b540aSrobert }
240*404b540aSrobert
241*404b540aSrobert /* Call struct_equiv_make_checkpoint (P, INFO) if the current partial block
242*404b540aSrobert is suitable to split off - i.e. there is no dangling cc0 user - and
243*404b540aSrobert if the current cost of the common instructions, minus the cost for
244*404b540aSrobert setting up the inputs, is higher than what has been recorded before
245*404b540aSrobert in CHECKPOINT[N]. Also, if we do so, confirm or cancel any pending
246*404b540aSrobert changes. */
247*404b540aSrobert static void
struct_equiv_improve_checkpoint(struct struct_equiv_checkpoint * p,struct equiv_info * info)248*404b540aSrobert struct_equiv_improve_checkpoint (struct struct_equiv_checkpoint *p,
249*404b540aSrobert struct equiv_info *info)
250*404b540aSrobert {
251*404b540aSrobert #ifdef HAVE_cc0
252*404b540aSrobert if (reg_mentioned_p (cc0_rtx, info->cur.x_start)
253*404b540aSrobert && !sets_cc0_p (info->cur.x_start))
254*404b540aSrobert return;
255*404b540aSrobert #endif
256*404b540aSrobert if (info->cur.input_count >= IMPOSSIBLE_MOVE_FACTOR)
257*404b540aSrobert return;
258*404b540aSrobert if (info->input_cost >= 0
259*404b540aSrobert ? (COSTS_N_INSNS(info->cur.ninsns - p->ninsns)
260*404b540aSrobert > info->input_cost * (info->cur.input_count - p->input_count))
261*404b540aSrobert : info->cur.ninsns > p->ninsns && !info->cur.input_count)
262*404b540aSrobert {
263*404b540aSrobert if (info->check_input_conflict && ! resolve_input_conflict (info))
264*404b540aSrobert return;
265*404b540aSrobert /* We have a profitable set of changes. If this is the final pass,
266*404b540aSrobert commit them now. Otherwise, we don't know yet if we can make any
267*404b540aSrobert change, so put the old code back for now. */
268*404b540aSrobert if (info->mode & STRUCT_EQUIV_FINAL)
269*404b540aSrobert confirm_change_group ();
270*404b540aSrobert else
271*404b540aSrobert cancel_changes (0);
272*404b540aSrobert struct_equiv_make_checkpoint (p, info);
273*404b540aSrobert }
274*404b540aSrobert }
275*404b540aSrobert
276*404b540aSrobert /* Restore state about current inputs / local registers / liveness
277*404b540aSrobert from P. */
278*404b540aSrobert static void
struct_equiv_restore_checkpoint(struct struct_equiv_checkpoint * p,struct equiv_info * info)279*404b540aSrobert struct_equiv_restore_checkpoint (struct struct_equiv_checkpoint *p,
280*404b540aSrobert struct equiv_info *info)
281*404b540aSrobert {
282*404b540aSrobert info->cur.ninsns = p->ninsns;
283*404b540aSrobert info->cur.x_start = p->x_start;
284*404b540aSrobert info->cur.y_start = p->y_start;
285*404b540aSrobert info->cur.input_count = p->input_count;
286*404b540aSrobert info->cur.input_valid = p->input_valid;
287*404b540aSrobert while (info->cur.local_count > p->local_count)
288*404b540aSrobert {
289*404b540aSrobert info->cur.local_count--;
290*404b540aSrobert info->cur.version--;
291*404b540aSrobert if (REGNO_REG_SET_P (info->x_local_live,
292*404b540aSrobert REGNO (info->x_local[info->cur.local_count])))
293*404b540aSrobert {
294*404b540aSrobert assign_reg_reg_set (info->x_local_live,
295*404b540aSrobert info->x_local[info->cur.local_count], 0);
296*404b540aSrobert assign_reg_reg_set (info->y_local_live,
297*404b540aSrobert info->y_local[info->cur.local_count], 0);
298*404b540aSrobert info->cur.version--;
299*404b540aSrobert }
300*404b540aSrobert }
301*404b540aSrobert if (info->cur.version != p->version)
302*404b540aSrobert info->need_rerun = true;
303*404b540aSrobert }
304*404b540aSrobert
305*404b540aSrobert
306*404b540aSrobert /* Update register liveness to reflect that X is now life (if rvalue is
307*404b540aSrobert nonzero) or dead (if rvalue is zero) in INFO->x_block, and likewise Y
308*404b540aSrobert in INFO->y_block. Return the number of registers the liveness of which
309*404b540aSrobert changed in each block (as a negative number if registers became dead). */
310*404b540aSrobert static int
note_local_live(struct equiv_info * info,rtx x,rtx y,int rvalue)311*404b540aSrobert note_local_live (struct equiv_info *info, rtx x, rtx y, int rvalue)
312*404b540aSrobert {
313*404b540aSrobert unsigned x_regno = REGNO (x);
314*404b540aSrobert unsigned y_regno = REGNO (y);
315*404b540aSrobert int x_nominal_nregs = (x_regno >= FIRST_PSEUDO_REGISTER
316*404b540aSrobert ? 1 : hard_regno_nregs[x_regno][GET_MODE (x)]);
317*404b540aSrobert int y_nominal_nregs = (y_regno >= FIRST_PSEUDO_REGISTER
318*404b540aSrobert ? 1 : hard_regno_nregs[y_regno][GET_MODE (y)]);
319*404b540aSrobert int x_change = assign_reg_reg_set (info->x_local_live, x, rvalue);
320*404b540aSrobert int y_change = assign_reg_reg_set (info->y_local_live, y, rvalue);
321*404b540aSrobert
322*404b540aSrobert gcc_assert (x_nominal_nregs && y_nominal_nregs);
323*404b540aSrobert gcc_assert (x_change * y_nominal_nregs == y_change * x_nominal_nregs);
324*404b540aSrobert if (y_change)
325*404b540aSrobert {
326*404b540aSrobert if (reload_completed)
327*404b540aSrobert {
328*404b540aSrobert unsigned x_regno ATTRIBUTE_UNUSED = REGNO (x);
329*404b540aSrobert unsigned y_regno = REGNO (y);
330*404b540aSrobert enum machine_mode x_mode = GET_MODE (x);
331*404b540aSrobert
332*404b540aSrobert if (secondary_reload_class (0, REGNO_REG_CLASS (y_regno), x_mode, x)
333*404b540aSrobert != NO_REGS
334*404b540aSrobert #ifdef SECONDARY_MEMORY_NEEDED
335*404b540aSrobert || SECONDARY_MEMORY_NEEDED (REGNO_REG_CLASS (y_regno),
336*404b540aSrobert REGNO_REG_CLASS (x_regno), x_mode)
337*404b540aSrobert #endif
338*404b540aSrobert )
339*404b540aSrobert y_change *= IMPOSSIBLE_MOVE_FACTOR;
340*404b540aSrobert }
341*404b540aSrobert info->cur.input_count += y_change;
342*404b540aSrobert info->cur.version++;
343*404b540aSrobert }
344*404b540aSrobert return x_change;
345*404b540aSrobert }
346*404b540aSrobert
347*404b540aSrobert /* Check if *XP is equivalent to Y. Until an an unreconcilable difference is
348*404b540aSrobert found, use in-group changes with validate_change on *XP to make register
349*404b540aSrobert assignments agree. It is the (not necessarily direct) callers
350*404b540aSrobert responsibility to verify / confirm / cancel these changes, as appropriate.
351*404b540aSrobert RVALUE indicates if the processed piece of rtl is used as a destination, in
352*404b540aSrobert which case we can't have different registers being an input. Returns
353*404b540aSrobert nonzero if the two blocks have been identified as equivalent, zero otherwise.
354*404b540aSrobert RVALUE == 0: destination
355*404b540aSrobert RVALUE == 1: source
356*404b540aSrobert RVALUE == -1: source, ignore SET_DEST of SET / clobber. */
357*404b540aSrobert bool
rtx_equiv_p(rtx * xp,rtx y,int rvalue,struct equiv_info * info)358*404b540aSrobert rtx_equiv_p (rtx *xp, rtx y, int rvalue, struct equiv_info *info)
359*404b540aSrobert {
360*404b540aSrobert rtx x = *xp;
361*404b540aSrobert enum rtx_code code;
362*404b540aSrobert int length;
363*404b540aSrobert const char *format;
364*404b540aSrobert int i;
365*404b540aSrobert
366*404b540aSrobert if (!y || !x)
367*404b540aSrobert return x == y;
368*404b540aSrobert code = GET_CODE (y);
369*404b540aSrobert if (code != REG && x == y)
370*404b540aSrobert return true;
371*404b540aSrobert if (GET_CODE (x) != code
372*404b540aSrobert || GET_MODE (x) != GET_MODE (y))
373*404b540aSrobert return false;
374*404b540aSrobert
375*404b540aSrobert /* ??? could extend to allow CONST_INT inputs. */
376*404b540aSrobert switch (code)
377*404b540aSrobert {
378*404b540aSrobert case REG:
379*404b540aSrobert {
380*404b540aSrobert unsigned x_regno = REGNO (x);
381*404b540aSrobert unsigned y_regno = REGNO (y);
382*404b540aSrobert int x_common_live, y_common_live;
383*404b540aSrobert
384*404b540aSrobert if (reload_completed
385*404b540aSrobert && (x_regno >= FIRST_PSEUDO_REGISTER
386*404b540aSrobert || y_regno >= FIRST_PSEUDO_REGISTER))
387*404b540aSrobert {
388*404b540aSrobert /* We should only see this in REG_NOTEs. */
389*404b540aSrobert gcc_assert (!info->live_update);
390*404b540aSrobert /* Returning false will cause us to remove the notes. */
391*404b540aSrobert return false;
392*404b540aSrobert }
393*404b540aSrobert #ifdef STACK_REGS
394*404b540aSrobert /* After reg-stack, can only accept literal matches of stack regs. */
395*404b540aSrobert if (info->mode & CLEANUP_POST_REGSTACK
396*404b540aSrobert && (IN_RANGE (x_regno, FIRST_STACK_REG, LAST_STACK_REG)
397*404b540aSrobert || IN_RANGE (y_regno, FIRST_STACK_REG, LAST_STACK_REG)))
398*404b540aSrobert return x_regno == y_regno;
399*404b540aSrobert #endif
400*404b540aSrobert
401*404b540aSrobert /* If the register is a locally live one in one block, the
402*404b540aSrobert corresponding one must be locally live in the other, too, and
403*404b540aSrobert match of identical regnos doesn't apply. */
404*404b540aSrobert if (REGNO_REG_SET_P (info->x_local_live, x_regno))
405*404b540aSrobert {
406*404b540aSrobert if (!REGNO_REG_SET_P (info->y_local_live, y_regno))
407*404b540aSrobert return false;
408*404b540aSrobert }
409*404b540aSrobert else if (REGNO_REG_SET_P (info->y_local_live, y_regno))
410*404b540aSrobert return false;
411*404b540aSrobert else if (x_regno == y_regno)
412*404b540aSrobert {
413*404b540aSrobert if (!rvalue && info->cur.input_valid
414*404b540aSrobert && (reg_overlap_mentioned_p (x, info->x_input)
415*404b540aSrobert || reg_overlap_mentioned_p (x, info->y_input)))
416*404b540aSrobert return false;
417*404b540aSrobert
418*404b540aSrobert /* Update liveness information. */
419*404b540aSrobert if (info->live_update
420*404b540aSrobert && assign_reg_reg_set (info->common_live, x, rvalue))
421*404b540aSrobert info->cur.version++;
422*404b540aSrobert
423*404b540aSrobert return true;
424*404b540aSrobert }
425*404b540aSrobert
426*404b540aSrobert x_common_live = REGNO_REG_SET_P (info->common_live, x_regno);
427*404b540aSrobert y_common_live = REGNO_REG_SET_P (info->common_live, y_regno);
428*404b540aSrobert if (x_common_live != y_common_live)
429*404b540aSrobert return false;
430*404b540aSrobert else if (x_common_live)
431*404b540aSrobert {
432*404b540aSrobert if (! rvalue || info->input_cost < 0 || no_new_pseudos)
433*404b540aSrobert return false;
434*404b540aSrobert /* If info->live_update is not set, we are processing notes.
435*404b540aSrobert We then allow a match with x_input / y_input found in a
436*404b540aSrobert previous pass. */
437*404b540aSrobert if (info->live_update && !info->cur.input_valid)
438*404b540aSrobert {
439*404b540aSrobert info->cur.input_valid = true;
440*404b540aSrobert info->x_input = x;
441*404b540aSrobert info->y_input = y;
442*404b540aSrobert info->cur.input_count += optimize_size ? 2 : 1;
443*404b540aSrobert if (info->input_reg
444*404b540aSrobert && GET_MODE (info->input_reg) != GET_MODE (info->x_input))
445*404b540aSrobert info->input_reg = NULL_RTX;
446*404b540aSrobert if (!info->input_reg)
447*404b540aSrobert info->input_reg = gen_reg_rtx (GET_MODE (info->x_input));
448*404b540aSrobert }
449*404b540aSrobert else if ((info->live_update
450*404b540aSrobert ? ! info->cur.input_valid : ! info->x_input)
451*404b540aSrobert || ! rtx_equal_p (x, info->x_input)
452*404b540aSrobert || ! rtx_equal_p (y, info->y_input))
453*404b540aSrobert return false;
454*404b540aSrobert validate_change (info->cur.x_start, xp, info->input_reg, 1);
455*404b540aSrobert }
456*404b540aSrobert else
457*404b540aSrobert {
458*404b540aSrobert int x_nregs = (x_regno >= FIRST_PSEUDO_REGISTER
459*404b540aSrobert ? 1 : hard_regno_nregs[x_regno][GET_MODE (x)]);
460*404b540aSrobert int y_nregs = (y_regno >= FIRST_PSEUDO_REGISTER
461*404b540aSrobert ? 1 : hard_regno_nregs[y_regno][GET_MODE (y)]);
462*404b540aSrobert int size = GET_MODE_SIZE (GET_MODE (x));
463*404b540aSrobert enum machine_mode x_mode = GET_MODE (x);
464*404b540aSrobert unsigned x_regno_i, y_regno_i;
465*404b540aSrobert int x_nregs_i, y_nregs_i, size_i;
466*404b540aSrobert int local_count = info->cur.local_count;
467*404b540aSrobert
468*404b540aSrobert /* This might be a register local to each block. See if we have
469*404b540aSrobert it already registered. */
470*404b540aSrobert for (i = local_count - 1; i >= 0; i--)
471*404b540aSrobert {
472*404b540aSrobert x_regno_i = REGNO (info->x_local[i]);
473*404b540aSrobert x_nregs_i = (x_regno_i >= FIRST_PSEUDO_REGISTER
474*404b540aSrobert ? 1 : hard_regno_nregs[x_regno_i][GET_MODE (x)]);
475*404b540aSrobert y_regno_i = REGNO (info->y_local[i]);
476*404b540aSrobert y_nregs_i = (y_regno_i >= FIRST_PSEUDO_REGISTER
477*404b540aSrobert ? 1 : hard_regno_nregs[y_regno_i][GET_MODE (y)]);
478*404b540aSrobert size_i = GET_MODE_SIZE (GET_MODE (info->x_local[i]));
479*404b540aSrobert
480*404b540aSrobert /* If we have a new pair of registers that is wider than an
481*404b540aSrobert old pair and enclosing it with matching offsets,
482*404b540aSrobert remove the old pair. If we find a matching, wider, old
483*404b540aSrobert pair, use the old one. If the width is the same, use the
484*404b540aSrobert old one if the modes match, but the new if they don't.
485*404b540aSrobert We don't want to get too fancy with subreg_regno_offset
486*404b540aSrobert here, so we just test two straightforward cases each. */
487*404b540aSrobert if (info->live_update
488*404b540aSrobert && (x_mode != GET_MODE (info->x_local[i])
489*404b540aSrobert ? size >= size_i : size > size_i))
490*404b540aSrobert {
491*404b540aSrobert /* If the new pair is fully enclosing a matching
492*404b540aSrobert existing pair, remove the old one. N.B. because
493*404b540aSrobert we are removing one entry here, the check below
494*404b540aSrobert if we have space for a new entry will succeed. */
495*404b540aSrobert if ((x_regno <= x_regno_i
496*404b540aSrobert && x_regno + x_nregs >= x_regno_i + x_nregs_i
497*404b540aSrobert && x_nregs == y_nregs && x_nregs_i == y_nregs_i
498*404b540aSrobert && x_regno - x_regno_i == y_regno - y_regno_i)
499*404b540aSrobert || (x_regno == x_regno_i && y_regno == y_regno_i
500*404b540aSrobert && x_nregs >= x_nregs_i && y_nregs >= y_nregs_i))
501*404b540aSrobert {
502*404b540aSrobert info->cur.local_count = --local_count;
503*404b540aSrobert info->x_local[i] = info->x_local[local_count];
504*404b540aSrobert info->y_local[i] = info->y_local[local_count];
505*404b540aSrobert continue;
506*404b540aSrobert }
507*404b540aSrobert }
508*404b540aSrobert else
509*404b540aSrobert {
510*404b540aSrobert
511*404b540aSrobert /* If the new pair is fully enclosed within a matching
512*404b540aSrobert existing pair, succeed. */
513*404b540aSrobert if (x_regno >= x_regno_i
514*404b540aSrobert && x_regno + x_nregs <= x_regno_i + x_nregs_i
515*404b540aSrobert && x_nregs == y_nregs && x_nregs_i == y_nregs_i
516*404b540aSrobert && x_regno - x_regno_i == y_regno - y_regno_i)
517*404b540aSrobert break;
518*404b540aSrobert if (x_regno == x_regno_i && y_regno == y_regno_i
519*404b540aSrobert && x_nregs <= x_nregs_i && y_nregs <= y_nregs_i)
520*404b540aSrobert break;
521*404b540aSrobert }
522*404b540aSrobert
523*404b540aSrobert /* Any other overlap causes a match failure. */
524*404b540aSrobert if (x_regno + x_nregs > x_regno_i
525*404b540aSrobert && x_regno_i + x_nregs_i > x_regno)
526*404b540aSrobert return false;
527*404b540aSrobert if (y_regno + y_nregs > y_regno_i
528*404b540aSrobert && y_regno_i + y_nregs_i > y_regno)
529*404b540aSrobert return false;
530*404b540aSrobert }
531*404b540aSrobert if (i < 0)
532*404b540aSrobert {
533*404b540aSrobert /* Not found. Create a new entry if possible. */
534*404b540aSrobert if (!info->live_update
535*404b540aSrobert || info->cur.local_count >= STRUCT_EQUIV_MAX_LOCAL)
536*404b540aSrobert return false;
537*404b540aSrobert info->x_local[info->cur.local_count] = x;
538*404b540aSrobert info->y_local[info->cur.local_count] = y;
539*404b540aSrobert info->cur.local_count++;
540*404b540aSrobert info->cur.version++;
541*404b540aSrobert }
542*404b540aSrobert note_local_live (info, x, y, rvalue);
543*404b540aSrobert }
544*404b540aSrobert return true;
545*404b540aSrobert }
546*404b540aSrobert case SET:
547*404b540aSrobert gcc_assert (rvalue < 0);
548*404b540aSrobert /* Ignore the destinations role as a destination. Still, we have
549*404b540aSrobert to consider input registers embedded in the addresses of a MEM.
550*404b540aSrobert N.B., we process the rvalue aspect of STRICT_LOW_PART /
551*404b540aSrobert ZERO_EXTEND / SIGN_EXTEND along with their lvalue aspect. */
552*404b540aSrobert if(!set_dest_addr_equiv_p (SET_DEST (x), SET_DEST (y), info))
553*404b540aSrobert return false;
554*404b540aSrobert /* Process source. */
555*404b540aSrobert return rtx_equiv_p (&SET_SRC (x), SET_SRC (y), 1, info);
556*404b540aSrobert case PRE_MODIFY:
557*404b540aSrobert /* Process destination. */
558*404b540aSrobert if (!rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info))
559*404b540aSrobert return false;
560*404b540aSrobert /* Process source. */
561*404b540aSrobert return rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), 1, info);
562*404b540aSrobert case POST_MODIFY:
563*404b540aSrobert {
564*404b540aSrobert rtx x_dest0, x_dest1;
565*404b540aSrobert
566*404b540aSrobert /* Process destination. */
567*404b540aSrobert x_dest0 = XEXP (x, 0);
568*404b540aSrobert gcc_assert (REG_P (x_dest0));
569*404b540aSrobert if (!rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info))
570*404b540aSrobert return false;
571*404b540aSrobert x_dest1 = XEXP (x, 0);
572*404b540aSrobert /* validate_change might have changed the destination. Put it back
573*404b540aSrobert so that we can do a proper match for its role a an input. */
574*404b540aSrobert XEXP (x, 0) = x_dest0;
575*404b540aSrobert if (!rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 1, info))
576*404b540aSrobert return false;
577*404b540aSrobert gcc_assert (x_dest1 == XEXP (x, 0));
578*404b540aSrobert /* Process source. */
579*404b540aSrobert return rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), 1, info);
580*404b540aSrobert }
581*404b540aSrobert case CLOBBER:
582*404b540aSrobert gcc_assert (rvalue < 0);
583*404b540aSrobert return true;
584*404b540aSrobert /* Some special forms are also rvalues when they appear in lvalue
585*404b540aSrobert positions. However, we must ont try to match a register after we
586*404b540aSrobert have already altered it with validate_change, consider the rvalue
587*404b540aSrobert aspect while we process the lvalue. */
588*404b540aSrobert case STRICT_LOW_PART:
589*404b540aSrobert case ZERO_EXTEND:
590*404b540aSrobert case SIGN_EXTEND:
591*404b540aSrobert {
592*404b540aSrobert rtx x_inner, y_inner;
593*404b540aSrobert enum rtx_code code;
594*404b540aSrobert int change;
595*404b540aSrobert
596*404b540aSrobert if (rvalue)
597*404b540aSrobert break;
598*404b540aSrobert x_inner = XEXP (x, 0);
599*404b540aSrobert y_inner = XEXP (y, 0);
600*404b540aSrobert if (GET_MODE (x_inner) != GET_MODE (y_inner))
601*404b540aSrobert return false;
602*404b540aSrobert code = GET_CODE (x_inner);
603*404b540aSrobert if (code != GET_CODE (y_inner))
604*404b540aSrobert return false;
605*404b540aSrobert /* The address of a MEM is an input that will be processed during
606*404b540aSrobert rvalue == -1 processing. */
607*404b540aSrobert if (code == SUBREG)
608*404b540aSrobert {
609*404b540aSrobert if (SUBREG_BYTE (x_inner) != SUBREG_BYTE (y_inner))
610*404b540aSrobert return false;
611*404b540aSrobert x = x_inner;
612*404b540aSrobert x_inner = SUBREG_REG (x_inner);
613*404b540aSrobert y_inner = SUBREG_REG (y_inner);
614*404b540aSrobert if (GET_MODE (x_inner) != GET_MODE (y_inner))
615*404b540aSrobert return false;
616*404b540aSrobert code = GET_CODE (x_inner);
617*404b540aSrobert if (code != GET_CODE (y_inner))
618*404b540aSrobert return false;
619*404b540aSrobert }
620*404b540aSrobert if (code == MEM)
621*404b540aSrobert return true;
622*404b540aSrobert gcc_assert (code == REG);
623*404b540aSrobert if (! rtx_equiv_p (&XEXP (x, 0), y_inner, rvalue, info))
624*404b540aSrobert return false;
625*404b540aSrobert if (REGNO (x_inner) == REGNO (y_inner))
626*404b540aSrobert {
627*404b540aSrobert change = assign_reg_reg_set (info->common_live, x_inner, 1);
628*404b540aSrobert info->cur.version++;
629*404b540aSrobert }
630*404b540aSrobert else
631*404b540aSrobert change = note_local_live (info, x_inner, y_inner, 1);
632*404b540aSrobert gcc_assert (change);
633*404b540aSrobert return true;
634*404b540aSrobert }
635*404b540aSrobert /* The AUTO_INC / POST_MODIFY / PRE_MODIFY sets are modelled to take
636*404b540aSrobert place during input processing, however, that is benign, since they
637*404b540aSrobert are paired with reads. */
638*404b540aSrobert case MEM:
639*404b540aSrobert return !rvalue || rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), rvalue, info);
640*404b540aSrobert case POST_INC: case POST_DEC: case PRE_INC: case PRE_DEC:
641*404b540aSrobert return (rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info)
642*404b540aSrobert && rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 1, info));
643*404b540aSrobert case PARALLEL:
644*404b540aSrobert /* If this is a top-level PATTERN PARALLEL, we expect the caller to
645*404b540aSrobert have handled the SET_DESTs. A complex or vector PARALLEL can be
646*404b540aSrobert identified by having a mode. */
647*404b540aSrobert gcc_assert (rvalue < 0 || GET_MODE (x) != VOIDmode);
648*404b540aSrobert break;
649*404b540aSrobert case LABEL_REF:
650*404b540aSrobert /* Check special tablejump match case. */
651*404b540aSrobert if (XEXP (y, 0) == info->y_label)
652*404b540aSrobert return (XEXP (x, 0) == info->x_label);
653*404b540aSrobert /* We can't assume nonlocal labels have their following insns yet. */
654*404b540aSrobert if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
655*404b540aSrobert return XEXP (x, 0) == XEXP (y, 0);
656*404b540aSrobert
657*404b540aSrobert /* Two label-refs are equivalent if they point at labels
658*404b540aSrobert in the same position in the instruction stream. */
659*404b540aSrobert return (next_real_insn (XEXP (x, 0))
660*404b540aSrobert == next_real_insn (XEXP (y, 0)));
661*404b540aSrobert case SYMBOL_REF:
662*404b540aSrobert return XSTR (x, 0) == XSTR (y, 0);
663*404b540aSrobert /* Some rtl is guaranteed to be shared, or unique; If we didn't match
664*404b540aSrobert EQ equality above, they aren't the same. */
665*404b540aSrobert case CONST_INT:
666*404b540aSrobert case CODE_LABEL:
667*404b540aSrobert return false;
668*404b540aSrobert default:
669*404b540aSrobert break;
670*404b540aSrobert }
671*404b540aSrobert
672*404b540aSrobert /* For commutative operations, the RTX match if the operands match in any
673*404b540aSrobert order. */
674*404b540aSrobert if (targetm.commutative_p (x, UNKNOWN))
675*404b540aSrobert return ((rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), rvalue, info)
676*404b540aSrobert && rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), rvalue, info))
677*404b540aSrobert || (rtx_equiv_p (&XEXP (x, 0), XEXP (y, 1), rvalue, info)
678*404b540aSrobert && rtx_equiv_p (&XEXP (x, 1), XEXP (y, 0), rvalue, info)));
679*404b540aSrobert
680*404b540aSrobert /* Process subexpressions - this is similar to rtx_equal_p. */
681*404b540aSrobert length = GET_RTX_LENGTH (code);
682*404b540aSrobert format = GET_RTX_FORMAT (code);
683*404b540aSrobert
684*404b540aSrobert for (i = 0; i < length; ++i)
685*404b540aSrobert {
686*404b540aSrobert switch (format[i])
687*404b540aSrobert {
688*404b540aSrobert case 'w':
689*404b540aSrobert if (XWINT (x, i) != XWINT (y, i))
690*404b540aSrobert return false;
691*404b540aSrobert break;
692*404b540aSrobert case 'n':
693*404b540aSrobert case 'i':
694*404b540aSrobert if (XINT (x, i) != XINT (y, i))
695*404b540aSrobert return false;
696*404b540aSrobert break;
697*404b540aSrobert case 'V':
698*404b540aSrobert case 'E':
699*404b540aSrobert if (XVECLEN (x, i) != XVECLEN (y, i))
700*404b540aSrobert return false;
701*404b540aSrobert if (XVEC (x, i) != 0)
702*404b540aSrobert {
703*404b540aSrobert int j;
704*404b540aSrobert for (j = 0; j < XVECLEN (x, i); ++j)
705*404b540aSrobert {
706*404b540aSrobert if (! rtx_equiv_p (&XVECEXP (x, i, j), XVECEXP (y, i, j),
707*404b540aSrobert rvalue, info))
708*404b540aSrobert return false;
709*404b540aSrobert }
710*404b540aSrobert }
711*404b540aSrobert break;
712*404b540aSrobert case 'e':
713*404b540aSrobert if (! rtx_equiv_p (&XEXP (x, i), XEXP (y, i), rvalue, info))
714*404b540aSrobert return false;
715*404b540aSrobert break;
716*404b540aSrobert case 'S':
717*404b540aSrobert case 's':
718*404b540aSrobert if ((XSTR (x, i) || XSTR (y, i))
719*404b540aSrobert && (! XSTR (x, i) || ! XSTR (y, i)
720*404b540aSrobert || strcmp (XSTR (x, i), XSTR (y, i))))
721*404b540aSrobert return false;
722*404b540aSrobert break;
723*404b540aSrobert case 'u':
724*404b540aSrobert /* These are just backpointers, so they don't matter. */
725*404b540aSrobert break;
726*404b540aSrobert case '0':
727*404b540aSrobert case 't':
728*404b540aSrobert break;
729*404b540aSrobert /* It is believed that rtx's at this level will never
730*404b540aSrobert contain anything but integers and other rtx's,
731*404b540aSrobert except for within LABEL_REFs and SYMBOL_REFs. */
732*404b540aSrobert default:
733*404b540aSrobert gcc_unreachable ();
734*404b540aSrobert }
735*404b540aSrobert }
736*404b540aSrobert return true;
737*404b540aSrobert }
738*404b540aSrobert
739*404b540aSrobert /* Do only the rtx_equiv_p SET_DEST processing for SETs and CLOBBERs.
740*404b540aSrobert Since we are scanning backwards, this the first step in processing each
741*404b540aSrobert insn. Return true for success. */
742*404b540aSrobert static bool
set_dest_equiv_p(rtx x,rtx y,struct equiv_info * info)743*404b540aSrobert set_dest_equiv_p (rtx x, rtx y, struct equiv_info *info)
744*404b540aSrobert {
745*404b540aSrobert if (!x || !y)
746*404b540aSrobert return x == y;
747*404b540aSrobert if (GET_CODE (x) != GET_CODE (y))
748*404b540aSrobert return false;
749*404b540aSrobert else if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
750*404b540aSrobert return rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info);
751*404b540aSrobert else if (GET_CODE (x) == PARALLEL)
752*404b540aSrobert {
753*404b540aSrobert int j;
754*404b540aSrobert
755*404b540aSrobert if (XVECLEN (x, 0) != XVECLEN (y, 0))
756*404b540aSrobert return false;
757*404b540aSrobert for (j = 0; j < XVECLEN (x, 0); ++j)
758*404b540aSrobert {
759*404b540aSrobert rtx xe = XVECEXP (x, 0, j);
760*404b540aSrobert rtx ye = XVECEXP (y, 0, j);
761*404b540aSrobert
762*404b540aSrobert if (GET_CODE (xe) != GET_CODE (ye))
763*404b540aSrobert return false;
764*404b540aSrobert if ((GET_CODE (xe) == SET || GET_CODE (xe) == CLOBBER)
765*404b540aSrobert && ! rtx_equiv_p (&XEXP (xe, 0), XEXP (ye, 0), 0, info))
766*404b540aSrobert return false;
767*404b540aSrobert }
768*404b540aSrobert }
769*404b540aSrobert return true;
770*404b540aSrobert }
771*404b540aSrobert
772*404b540aSrobert /* Process MEMs in SET_DEST destinations. We must not process this together
773*404b540aSrobert with REG SET_DESTs, but must do it separately, lest when we see
774*404b540aSrobert [(set (reg:SI foo) (bar))
775*404b540aSrobert (set (mem:SI (reg:SI foo) (baz)))]
776*404b540aSrobert struct_equiv_block_eq could get confused to assume that (reg:SI foo)
777*404b540aSrobert is not live before this instruction. */
778*404b540aSrobert static bool
set_dest_addr_equiv_p(rtx x,rtx y,struct equiv_info * info)779*404b540aSrobert set_dest_addr_equiv_p (rtx x, rtx y, struct equiv_info *info)
780*404b540aSrobert {
781*404b540aSrobert enum rtx_code code = GET_CODE (x);
782*404b540aSrobert int length;
783*404b540aSrobert const char *format;
784*404b540aSrobert int i;
785*404b540aSrobert
786*404b540aSrobert if (code != GET_CODE (y))
787*404b540aSrobert return false;
788*404b540aSrobert if (code == MEM)
789*404b540aSrobert return rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 1, info);
790*404b540aSrobert
791*404b540aSrobert /* Process subexpressions. */
792*404b540aSrobert length = GET_RTX_LENGTH (code);
793*404b540aSrobert format = GET_RTX_FORMAT (code);
794*404b540aSrobert
795*404b540aSrobert for (i = 0; i < length; ++i)
796*404b540aSrobert {
797*404b540aSrobert switch (format[i])
798*404b540aSrobert {
799*404b540aSrobert case 'V':
800*404b540aSrobert case 'E':
801*404b540aSrobert if (XVECLEN (x, i) != XVECLEN (y, i))
802*404b540aSrobert return false;
803*404b540aSrobert if (XVEC (x, i) != 0)
804*404b540aSrobert {
805*404b540aSrobert int j;
806*404b540aSrobert for (j = 0; j < XVECLEN (x, i); ++j)
807*404b540aSrobert {
808*404b540aSrobert if (! set_dest_addr_equiv_p (XVECEXP (x, i, j),
809*404b540aSrobert XVECEXP (y, i, j), info))
810*404b540aSrobert return false;
811*404b540aSrobert }
812*404b540aSrobert }
813*404b540aSrobert break;
814*404b540aSrobert case 'e':
815*404b540aSrobert if (! set_dest_addr_equiv_p (XEXP (x, i), XEXP (y, i), info))
816*404b540aSrobert return false;
817*404b540aSrobert break;
818*404b540aSrobert default:
819*404b540aSrobert break;
820*404b540aSrobert }
821*404b540aSrobert }
822*404b540aSrobert return true;
823*404b540aSrobert }
824*404b540aSrobert
825*404b540aSrobert /* Check if the set of REG_DEAD notes attached to I1 and I2 allows us to
826*404b540aSrobert go ahead with merging I1 and I2, which otherwise look fine.
827*404b540aSrobert Inputs / local registers for the inputs of I1 and I2 have already been
828*404b540aSrobert set up. */
829*404b540aSrobert static bool
death_notes_match_p(rtx i1 ATTRIBUTE_UNUSED,rtx i2 ATTRIBUTE_UNUSED,struct equiv_info * info ATTRIBUTE_UNUSED)830*404b540aSrobert death_notes_match_p (rtx i1 ATTRIBUTE_UNUSED, rtx i2 ATTRIBUTE_UNUSED,
831*404b540aSrobert struct equiv_info *info ATTRIBUTE_UNUSED)
832*404b540aSrobert {
833*404b540aSrobert #ifdef STACK_REGS
834*404b540aSrobert /* If cross_jump_death_matters is not 0, the insn's mode
835*404b540aSrobert indicates whether or not the insn contains any stack-like regs. */
836*404b540aSrobert
837*404b540aSrobert if ((info->mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
838*404b540aSrobert {
839*404b540aSrobert /* If register stack conversion has already been done, then
840*404b540aSrobert death notes must also be compared before it is certain that
841*404b540aSrobert the two instruction streams match. */
842*404b540aSrobert
843*404b540aSrobert rtx note;
844*404b540aSrobert HARD_REG_SET i1_regset, i2_regset;
845*404b540aSrobert
846*404b540aSrobert CLEAR_HARD_REG_SET (i1_regset);
847*404b540aSrobert CLEAR_HARD_REG_SET (i2_regset);
848*404b540aSrobert
849*404b540aSrobert for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
850*404b540aSrobert if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
851*404b540aSrobert SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
852*404b540aSrobert
853*404b540aSrobert for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
854*404b540aSrobert if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
855*404b540aSrobert {
856*404b540aSrobert unsigned regno = REGNO (XEXP (note, 0));
857*404b540aSrobert int i;
858*404b540aSrobert
859*404b540aSrobert for (i = info->cur.local_count - 1; i >= 0; i--)
860*404b540aSrobert if (regno == REGNO (info->y_local[i]))
861*404b540aSrobert {
862*404b540aSrobert regno = REGNO (info->x_local[i]);
863*404b540aSrobert break;
864*404b540aSrobert }
865*404b540aSrobert SET_HARD_REG_BIT (i2_regset, regno);
866*404b540aSrobert }
867*404b540aSrobert
868*404b540aSrobert GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
869*404b540aSrobert
870*404b540aSrobert return false;
871*404b540aSrobert
872*404b540aSrobert done:
873*404b540aSrobert ;
874*404b540aSrobert }
875*404b540aSrobert #endif
876*404b540aSrobert return true;
877*404b540aSrobert }
878*404b540aSrobert
879*404b540aSrobert /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
880*404b540aSrobert
881*404b540aSrobert bool
insns_match_p(rtx i1,rtx i2,struct equiv_info * info)882*404b540aSrobert insns_match_p (rtx i1, rtx i2, struct equiv_info *info)
883*404b540aSrobert {
884*404b540aSrobert int rvalue_change_start;
885*404b540aSrobert struct struct_equiv_checkpoint before_rvalue_change;
886*404b540aSrobert
887*404b540aSrobert /* Verify that I1 and I2 are equivalent. */
888*404b540aSrobert if (GET_CODE (i1) != GET_CODE (i2))
889*404b540aSrobert return false;
890*404b540aSrobert
891*404b540aSrobert info->cur.x_start = i1;
892*404b540aSrobert info->cur.y_start = i2;
893*404b540aSrobert
894*404b540aSrobert /* If this is a CALL_INSN, compare register usage information.
895*404b540aSrobert If we don't check this on stack register machines, the two
896*404b540aSrobert CALL_INSNs might be merged leaving reg-stack.c with mismatching
897*404b540aSrobert numbers of stack registers in the same basic block.
898*404b540aSrobert If we don't check this on machines with delay slots, a delay slot may
899*404b540aSrobert be filled that clobbers a parameter expected by the subroutine.
900*404b540aSrobert
901*404b540aSrobert ??? We take the simple route for now and assume that if they're
902*404b540aSrobert equal, they were constructed identically. */
903*404b540aSrobert
904*404b540aSrobert if (CALL_P (i1))
905*404b540aSrobert {
906*404b540aSrobert if (SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)
907*404b540aSrobert || ! set_dest_equiv_p (PATTERN (i1), PATTERN (i2), info)
908*404b540aSrobert || ! set_dest_equiv_p (CALL_INSN_FUNCTION_USAGE (i1),
909*404b540aSrobert CALL_INSN_FUNCTION_USAGE (i2), info)
910*404b540aSrobert || ! rtx_equiv_p (&CALL_INSN_FUNCTION_USAGE (i1),
911*404b540aSrobert CALL_INSN_FUNCTION_USAGE (i2), -1, info))
912*404b540aSrobert {
913*404b540aSrobert cancel_changes (0);
914*404b540aSrobert return false;
915*404b540aSrobert }
916*404b540aSrobert }
917*404b540aSrobert else if (INSN_P (i1))
918*404b540aSrobert {
919*404b540aSrobert if (! set_dest_equiv_p (PATTERN (i1), PATTERN (i2), info))
920*404b540aSrobert {
921*404b540aSrobert cancel_changes (0);
922*404b540aSrobert return false;
923*404b540aSrobert }
924*404b540aSrobert }
925*404b540aSrobert rvalue_change_start = num_validated_changes ();
926*404b540aSrobert struct_equiv_make_checkpoint (&before_rvalue_change, info);
927*404b540aSrobert /* Check death_notes_match_p *after* the inputs have been processed,
928*404b540aSrobert so that local inputs will already have been set up. */
929*404b540aSrobert if (! INSN_P (i1)
930*404b540aSrobert || (!bitmap_bit_p (info->equiv_used, info->cur.ninsns)
931*404b540aSrobert && rtx_equiv_p (&PATTERN (i1), PATTERN (i2), -1, info)
932*404b540aSrobert && death_notes_match_p (i1, i2, info)
933*404b540aSrobert && verify_changes (0)))
934*404b540aSrobert return true;
935*404b540aSrobert
936*404b540aSrobert /* Do not do EQUIV substitution after reload. First, we're undoing the
937*404b540aSrobert work of reload_cse. Second, we may be undoing the work of the post-
938*404b540aSrobert reload splitting pass. */
939*404b540aSrobert /* ??? Possibly add a new phase switch variable that can be used by
940*404b540aSrobert targets to disallow the troublesome insns after splitting. */
941*404b540aSrobert if (!reload_completed)
942*404b540aSrobert {
943*404b540aSrobert rtx equiv1, equiv2;
944*404b540aSrobert
945*404b540aSrobert cancel_changes (rvalue_change_start);
946*404b540aSrobert struct_equiv_restore_checkpoint (&before_rvalue_change, info);
947*404b540aSrobert
948*404b540aSrobert /* The following code helps take care of G++ cleanups. */
949*404b540aSrobert equiv1 = find_reg_equal_equiv_note (i1);
950*404b540aSrobert equiv2 = find_reg_equal_equiv_note (i2);
951*404b540aSrobert if (equiv1 && equiv2
952*404b540aSrobert /* If the equivalences are not to a constant, they may
953*404b540aSrobert reference pseudos that no longer exist, so we can't
954*404b540aSrobert use them. */
955*404b540aSrobert && (! reload_completed
956*404b540aSrobert || (CONSTANT_P (XEXP (equiv1, 0))
957*404b540aSrobert && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
958*404b540aSrobert {
959*404b540aSrobert rtx s1 = single_set (i1);
960*404b540aSrobert rtx s2 = single_set (i2);
961*404b540aSrobert
962*404b540aSrobert if (s1 != 0 && s2 != 0)
963*404b540aSrobert {
964*404b540aSrobert validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
965*404b540aSrobert validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
966*404b540aSrobert /* Only inspecting the new SET_SRC is not good enough,
967*404b540aSrobert because there may also be bare USEs in a single_set
968*404b540aSrobert PARALLEL. */
969*404b540aSrobert if (rtx_equiv_p (&PATTERN (i1), PATTERN (i2), -1, info)
970*404b540aSrobert && death_notes_match_p (i1, i2, info)
971*404b540aSrobert && verify_changes (0))
972*404b540aSrobert {
973*404b540aSrobert /* Mark this insn so that we'll use the equivalence in
974*404b540aSrobert all subsequent passes. */
975*404b540aSrobert bitmap_set_bit (info->equiv_used, info->cur.ninsns);
976*404b540aSrobert return true;
977*404b540aSrobert }
978*404b540aSrobert }
979*404b540aSrobert }
980*404b540aSrobert }
981*404b540aSrobert
982*404b540aSrobert cancel_changes (0);
983*404b540aSrobert return false;
984*404b540aSrobert }
985*404b540aSrobert
986*404b540aSrobert /* Set up mode and register information in INFO. Return true for success. */
987*404b540aSrobert bool
struct_equiv_init(int mode,struct equiv_info * info)988*404b540aSrobert struct_equiv_init (int mode, struct equiv_info *info)
989*404b540aSrobert {
990*404b540aSrobert if ((info->x_block->flags | info->y_block->flags) & BB_DIRTY)
991*404b540aSrobert update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
992*404b540aSrobert (PROP_DEATH_NOTES
993*404b540aSrobert | ((mode & CLEANUP_POST_REGSTACK)
994*404b540aSrobert ? PROP_POST_REGSTACK : 0)));
995*404b540aSrobert if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
996*404b540aSrobert info->y_block->il.rtl->global_live_at_end))
997*404b540aSrobert {
998*404b540aSrobert #ifdef STACK_REGS
999*404b540aSrobert unsigned rn;
1000*404b540aSrobert
1001*404b540aSrobert if (!(mode & CLEANUP_POST_REGSTACK))
1002*404b540aSrobert return false;
1003*404b540aSrobert /* After reg-stack. Remove bogus live info about stack regs. N.B.
1004*404b540aSrobert these regs are not necessarily all dead - we swap random bogosity
1005*404b540aSrobert against constant bogosity. However, clearing these bits at
1006*404b540aSrobert least makes the regsets comparable. */
1007*404b540aSrobert for (rn = FIRST_STACK_REG; rn <= LAST_STACK_REG; rn++)
1008*404b540aSrobert {
1009*404b540aSrobert CLEAR_REGNO_REG_SET (info->x_block->il.rtl->global_live_at_end, rn);
1010*404b540aSrobert CLEAR_REGNO_REG_SET (info->y_block->il.rtl->global_live_at_end, rn);
1011*404b540aSrobert }
1012*404b540aSrobert if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
1013*404b540aSrobert info->y_block->il.rtl->global_live_at_end))
1014*404b540aSrobert #endif
1015*404b540aSrobert return false;
1016*404b540aSrobert }
1017*404b540aSrobert info->mode = mode;
1018*404b540aSrobert if (mode & STRUCT_EQUIV_START)
1019*404b540aSrobert {
1020*404b540aSrobert info->x_input = info->y_input = info->input_reg = NULL_RTX;
1021*404b540aSrobert info->equiv_used = ALLOC_REG_SET (®_obstack);
1022*404b540aSrobert info->check_input_conflict = false;
1023*404b540aSrobert }
1024*404b540aSrobert info->had_input_conflict = false;
1025*404b540aSrobert info->cur.ninsns = info->cur.version = 0;
1026*404b540aSrobert info->cur.local_count = info->cur.input_count = 0;
1027*404b540aSrobert info->cur.x_start = info->cur.y_start = NULL_RTX;
1028*404b540aSrobert info->x_label = info->y_label = NULL_RTX;
1029*404b540aSrobert info->need_rerun = false;
1030*404b540aSrobert info->live_update = true;
1031*404b540aSrobert info->cur.input_valid = false;
1032*404b540aSrobert info->common_live = ALLOC_REG_SET (®_obstack);
1033*404b540aSrobert info->x_local_live = ALLOC_REG_SET (®_obstack);
1034*404b540aSrobert info->y_local_live = ALLOC_REG_SET (®_obstack);
1035*404b540aSrobert COPY_REG_SET (info->common_live, info->x_block->il.rtl->global_live_at_end);
1036*404b540aSrobert struct_equiv_make_checkpoint (&info->best_match, info);
1037*404b540aSrobert return true;
1038*404b540aSrobert }
1039*404b540aSrobert
1040*404b540aSrobert /* Insns XI and YI have been matched. Merge memory attributes and reg
1041*404b540aSrobert notes. */
1042*404b540aSrobert static void
struct_equiv_merge(rtx xi,rtx yi,struct equiv_info * info)1043*404b540aSrobert struct_equiv_merge (rtx xi, rtx yi, struct equiv_info *info)
1044*404b540aSrobert {
1045*404b540aSrobert rtx equiv1, equiv2;
1046*404b540aSrobert
1047*404b540aSrobert merge_memattrs (xi, yi);
1048*404b540aSrobert
1049*404b540aSrobert /* If the merged insns have different REG_EQUAL notes, then
1050*404b540aSrobert remove them. */
1051*404b540aSrobert info->live_update = false;
1052*404b540aSrobert equiv1 = find_reg_equal_equiv_note (xi);
1053*404b540aSrobert equiv2 = find_reg_equal_equiv_note (yi);
1054*404b540aSrobert if (equiv1 && !equiv2)
1055*404b540aSrobert remove_note (xi, equiv1);
1056*404b540aSrobert else if (!equiv1 && equiv2)
1057*404b540aSrobert remove_note (yi, equiv2);
1058*404b540aSrobert else if (equiv1 && equiv2
1059*404b540aSrobert && !rtx_equiv_p (&XEXP (equiv1, 0), XEXP (equiv2, 0),
1060*404b540aSrobert 1, info))
1061*404b540aSrobert {
1062*404b540aSrobert remove_note (xi, equiv1);
1063*404b540aSrobert remove_note (yi, equiv2);
1064*404b540aSrobert }
1065*404b540aSrobert info->live_update = true;
1066*404b540aSrobert }
1067*404b540aSrobert
1068*404b540aSrobert /* Return number of matched insns.
1069*404b540aSrobert This function must be called up to three times for a successful cross-jump
1070*404b540aSrobert match:
1071*404b540aSrobert first to find out which instructions do match. While trying to match
1072*404b540aSrobert another instruction that doesn't match, we destroy information in info
1073*404b540aSrobert about the actual inputs. So if there have been any before the last
1074*404b540aSrobert match attempt, we need to call this function again to recompute the
1075*404b540aSrobert actual inputs up to the actual start of the matching sequence.
1076*404b540aSrobert When we are then satisfied that the cross-jump is worthwhile, we
1077*404b540aSrobert call this function a third time to make any changes needed to make the
1078*404b540aSrobert sequences match: apply equivalences, remove non-matching
1079*404b540aSrobert notes and merge memory attributes. */
1080*404b540aSrobert int
struct_equiv_block_eq(int mode,struct equiv_info * info)1081*404b540aSrobert struct_equiv_block_eq (int mode, struct equiv_info *info)
1082*404b540aSrobert {
1083*404b540aSrobert rtx x_stop, y_stop;
1084*404b540aSrobert rtx xi, yi;
1085*404b540aSrobert int i;
1086*404b540aSrobert
1087*404b540aSrobert if (mode & STRUCT_EQUIV_START)
1088*404b540aSrobert {
1089*404b540aSrobert x_stop = BB_HEAD (info->x_block);
1090*404b540aSrobert y_stop = BB_HEAD (info->y_block);
1091*404b540aSrobert if (!x_stop || !y_stop)
1092*404b540aSrobert return 0;
1093*404b540aSrobert }
1094*404b540aSrobert else
1095*404b540aSrobert {
1096*404b540aSrobert x_stop = info->cur.x_start;
1097*404b540aSrobert y_stop = info->cur.y_start;
1098*404b540aSrobert }
1099*404b540aSrobert if (!struct_equiv_init (mode, info))
1100*404b540aSrobert gcc_unreachable ();
1101*404b540aSrobert
1102*404b540aSrobert /* Skip simple jumps at the end of the blocks. Complex jumps still
1103*404b540aSrobert need to be compared for equivalence, which we'll do below. */
1104*404b540aSrobert
1105*404b540aSrobert xi = BB_END (info->x_block);
1106*404b540aSrobert if (onlyjump_p (xi)
1107*404b540aSrobert || (returnjump_p (xi) && !side_effects_p (PATTERN (xi))))
1108*404b540aSrobert {
1109*404b540aSrobert info->cur.x_start = xi;
1110*404b540aSrobert xi = PREV_INSN (xi);
1111*404b540aSrobert }
1112*404b540aSrobert
1113*404b540aSrobert yi = BB_END (info->y_block);
1114*404b540aSrobert if (onlyjump_p (yi)
1115*404b540aSrobert || (returnjump_p (yi) && !side_effects_p (PATTERN (yi))))
1116*404b540aSrobert {
1117*404b540aSrobert info->cur.y_start = yi;
1118*404b540aSrobert /* Count everything except for unconditional jump as insn. */
1119*404b540aSrobert /* ??? Is it right to count unconditional jumps with a clobber?
1120*404b540aSrobert Should we count conditional returns? */
1121*404b540aSrobert if (!simplejump_p (yi) && !returnjump_p (yi) && info->cur.x_start)
1122*404b540aSrobert info->cur.ninsns++;
1123*404b540aSrobert yi = PREV_INSN (yi);
1124*404b540aSrobert }
1125*404b540aSrobert
1126*404b540aSrobert if (mode & STRUCT_EQUIV_MATCH_JUMPS)
1127*404b540aSrobert {
1128*404b540aSrobert /* The caller is expected to have compared the jumps already, but we
1129*404b540aSrobert need to match them again to get any local registers and inputs. */
1130*404b540aSrobert gcc_assert (!info->cur.x_start == !info->cur.y_start);
1131*404b540aSrobert if (info->cur.x_start)
1132*404b540aSrobert {
1133*404b540aSrobert if (any_condjump_p (info->cur.x_start)
1134*404b540aSrobert ? !condjump_equiv_p (info, false)
1135*404b540aSrobert : !insns_match_p (info->cur.x_start, info->cur.y_start, info))
1136*404b540aSrobert gcc_unreachable ();
1137*404b540aSrobert }
1138*404b540aSrobert else if (any_condjump_p (xi) && any_condjump_p (yi))
1139*404b540aSrobert {
1140*404b540aSrobert info->cur.x_start = xi;
1141*404b540aSrobert info->cur.y_start = yi;
1142*404b540aSrobert xi = PREV_INSN (xi);
1143*404b540aSrobert yi = PREV_INSN (yi);
1144*404b540aSrobert info->cur.ninsns++;
1145*404b540aSrobert if (!condjump_equiv_p (info, false))
1146*404b540aSrobert gcc_unreachable ();
1147*404b540aSrobert }
1148*404b540aSrobert if (info->cur.x_start && info->mode & STRUCT_EQUIV_FINAL)
1149*404b540aSrobert struct_equiv_merge (info->cur.x_start, info->cur.y_start, info);
1150*404b540aSrobert }
1151*404b540aSrobert
1152*404b540aSrobert struct_equiv_improve_checkpoint (&info->best_match, info);
1153*404b540aSrobert info->x_end = xi;
1154*404b540aSrobert info->y_end = yi;
1155*404b540aSrobert if (info->cur.x_start != x_stop)
1156*404b540aSrobert for (;;)
1157*404b540aSrobert {
1158*404b540aSrobert /* Ignore notes. */
1159*404b540aSrobert while (!INSN_P (xi) && xi != x_stop)
1160*404b540aSrobert xi = PREV_INSN (xi);
1161*404b540aSrobert
1162*404b540aSrobert while (!INSN_P (yi) && yi != y_stop)
1163*404b540aSrobert yi = PREV_INSN (yi);
1164*404b540aSrobert
1165*404b540aSrobert if (!insns_match_p (xi, yi, info))
1166*404b540aSrobert break;
1167*404b540aSrobert if (INSN_P (xi))
1168*404b540aSrobert {
1169*404b540aSrobert if (info->mode & STRUCT_EQUIV_FINAL)
1170*404b540aSrobert struct_equiv_merge (xi, yi, info);
1171*404b540aSrobert info->cur.ninsns++;
1172*404b540aSrobert struct_equiv_improve_checkpoint (&info->best_match, info);
1173*404b540aSrobert }
1174*404b540aSrobert if (xi == x_stop || yi == y_stop)
1175*404b540aSrobert {
1176*404b540aSrobert /* If we reached the start of at least one of the blocks, but
1177*404b540aSrobert best_match hasn't been advanced back to the first valid insn
1178*404b540aSrobert yet, represent the increased benefit of completing the block
1179*404b540aSrobert as an increased instruction count. */
1180*404b540aSrobert if (info->best_match.x_start != info->cur.x_start
1181*404b540aSrobert && (xi == BB_HEAD (info->x_block)
1182*404b540aSrobert || yi == BB_HEAD (info->y_block)))
1183*404b540aSrobert {
1184*404b540aSrobert info->cur.ninsns++;
1185*404b540aSrobert struct_equiv_improve_checkpoint (&info->best_match, info);
1186*404b540aSrobert info->cur.ninsns--;
1187*404b540aSrobert if (info->best_match.ninsns > info->cur.ninsns)
1188*404b540aSrobert info->best_match.ninsns = info->cur.ninsns;
1189*404b540aSrobert }
1190*404b540aSrobert break;
1191*404b540aSrobert }
1192*404b540aSrobert xi = PREV_INSN (xi);
1193*404b540aSrobert yi = PREV_INSN (yi);
1194*404b540aSrobert }
1195*404b540aSrobert
1196*404b540aSrobert /* If we failed to match an insn, but had some changes registered from
1197*404b540aSrobert trying to make the insns match, we need to cancel these changes now. */
1198*404b540aSrobert cancel_changes (0);
1199*404b540aSrobert /* Restore to best_match to get the sequence with the best known-so-far
1200*404b540aSrobert cost-benefit difference. */
1201*404b540aSrobert struct_equiv_restore_checkpoint (&info->best_match, info);
1202*404b540aSrobert
1203*404b540aSrobert /* Include preceding notes and labels in the cross-jump / if-conversion.
1204*404b540aSrobert One, this may bring us to the head of the blocks.
1205*404b540aSrobert Two, it keeps line number notes as matched as may be. */
1206*404b540aSrobert if (info->cur.ninsns)
1207*404b540aSrobert {
1208*404b540aSrobert xi = info->cur.x_start;
1209*404b540aSrobert yi = info->cur.y_start;
1210*404b540aSrobert while (xi != x_stop && !INSN_P (PREV_INSN (xi)))
1211*404b540aSrobert xi = PREV_INSN (xi);
1212*404b540aSrobert
1213*404b540aSrobert while (yi != y_stop && !INSN_P (PREV_INSN (yi)))
1214*404b540aSrobert yi = PREV_INSN (yi);
1215*404b540aSrobert
1216*404b540aSrobert info->cur.x_start = xi;
1217*404b540aSrobert info->cur.y_start = yi;
1218*404b540aSrobert }
1219*404b540aSrobert
1220*404b540aSrobert if (!info->cur.input_valid)
1221*404b540aSrobert info->x_input = info->y_input = info->input_reg = NULL_RTX;
1222*404b540aSrobert if (!info->need_rerun)
1223*404b540aSrobert {
1224*404b540aSrobert find_dying_inputs (info);
1225*404b540aSrobert if (info->mode & STRUCT_EQUIV_FINAL)
1226*404b540aSrobert {
1227*404b540aSrobert if (info->check_input_conflict && ! resolve_input_conflict (info))
1228*404b540aSrobert gcc_unreachable ();
1229*404b540aSrobert }
1230*404b540aSrobert else
1231*404b540aSrobert {
1232*404b540aSrobert bool input_conflict = info->had_input_conflict;
1233*404b540aSrobert
1234*404b540aSrobert if (!input_conflict
1235*404b540aSrobert && info->dying_inputs > 1
1236*404b540aSrobert && bitmap_intersect_p (info->x_local_live, info->y_local_live))
1237*404b540aSrobert {
1238*404b540aSrobert regset_head clobbered_regs;
1239*404b540aSrobert
1240*404b540aSrobert INIT_REG_SET (&clobbered_regs);
1241*404b540aSrobert for (i = 0; i < info->cur.local_count; i++)
1242*404b540aSrobert {
1243*404b540aSrobert if (assign_reg_reg_set (&clobbered_regs, info->y_local[i], 0))
1244*404b540aSrobert {
1245*404b540aSrobert input_conflict = true;
1246*404b540aSrobert break;
1247*404b540aSrobert }
1248*404b540aSrobert assign_reg_reg_set (&clobbered_regs, info->x_local[i], 1);
1249*404b540aSrobert }
1250*404b540aSrobert CLEAR_REG_SET (&clobbered_regs);
1251*404b540aSrobert }
1252*404b540aSrobert if (input_conflict && !info->check_input_conflict)
1253*404b540aSrobert info->need_rerun = true;
1254*404b540aSrobert info->check_input_conflict = input_conflict;
1255*404b540aSrobert }
1256*404b540aSrobert }
1257*404b540aSrobert
1258*404b540aSrobert if (info->mode & STRUCT_EQUIV_NEED_FULL_BLOCK
1259*404b540aSrobert && (info->cur.x_start != x_stop || info->cur.y_start != y_stop))
1260*404b540aSrobert return 0;
1261*404b540aSrobert return info->cur.ninsns;
1262*404b540aSrobert }
1263*404b540aSrobert
1264*404b540aSrobert /* For each local register, set info->local_rvalue to true iff the register
1265*404b540aSrobert is a dying input. Store the total number of these in info->dying_inputs. */
1266*404b540aSrobert static void
find_dying_inputs(struct equiv_info * info)1267*404b540aSrobert find_dying_inputs (struct equiv_info *info)
1268*404b540aSrobert {
1269*404b540aSrobert int i;
1270*404b540aSrobert
1271*404b540aSrobert info->dying_inputs = 0;
1272*404b540aSrobert for (i = info->cur.local_count-1; i >=0; i--)
1273*404b540aSrobert {
1274*404b540aSrobert rtx x = info->x_local[i];
1275*404b540aSrobert unsigned regno = REGNO (x);
1276*404b540aSrobert int nregs = (regno >= FIRST_PSEUDO_REGISTER
1277*404b540aSrobert ? 1 : hard_regno_nregs[regno][GET_MODE (x)]);
1278*404b540aSrobert
1279*404b540aSrobert for (info->local_rvalue[i] = false; nregs > 0; regno++, --nregs)
1280*404b540aSrobert if (REGNO_REG_SET_P (info->x_local_live, regno))
1281*404b540aSrobert {
1282*404b540aSrobert info->dying_inputs++;
1283*404b540aSrobert info->local_rvalue[i] = true;
1284*404b540aSrobert break;
1285*404b540aSrobert }
1286*404b540aSrobert }
1287*404b540aSrobert }
1288*404b540aSrobert
1289*404b540aSrobert /* For each local register that is a dying input, y_local[i] will be
1290*404b540aSrobert copied to x_local[i]. We'll do this in ascending order. Try to
1291*404b540aSrobert re-order the locals to avoid conflicts like r3 = r2; r4 = r3; .
1292*404b540aSrobert Return true iff the re-ordering is successful, or not necessary. */
1293*404b540aSrobert static bool
resolve_input_conflict(struct equiv_info * info)1294*404b540aSrobert resolve_input_conflict (struct equiv_info *info)
1295*404b540aSrobert {
1296*404b540aSrobert int i, j, end;
1297*404b540aSrobert int nswaps = 0;
1298*404b540aSrobert rtx save_x_local[STRUCT_EQUIV_MAX_LOCAL];
1299*404b540aSrobert rtx save_y_local[STRUCT_EQUIV_MAX_LOCAL];
1300*404b540aSrobert
1301*404b540aSrobert find_dying_inputs (info);
1302*404b540aSrobert if (info->dying_inputs <= 1)
1303*404b540aSrobert return true;
1304*404b540aSrobert memcpy (save_x_local, info->x_local, sizeof save_x_local);
1305*404b540aSrobert memcpy (save_y_local, info->y_local, sizeof save_y_local);
1306*404b540aSrobert end = info->cur.local_count - 1;
1307*404b540aSrobert for (i = 0; i <= end; i++)
1308*404b540aSrobert {
1309*404b540aSrobert /* Cycle detection with regsets is expensive, so we just check that
1310*404b540aSrobert we don't exceed the maximum number of swaps needed in the acyclic
1311*404b540aSrobert case. */
1312*404b540aSrobert int max_swaps = end - i;
1313*404b540aSrobert
1314*404b540aSrobert /* Check if x_local[i] will be clobbered. */
1315*404b540aSrobert if (!info->local_rvalue[i])
1316*404b540aSrobert continue;
1317*404b540aSrobert /* Check if any later value needs to be copied earlier. */
1318*404b540aSrobert for (j = i + 1; j <= end; j++)
1319*404b540aSrobert {
1320*404b540aSrobert rtx tmp;
1321*404b540aSrobert
1322*404b540aSrobert if (!info->local_rvalue[j])
1323*404b540aSrobert continue;
1324*404b540aSrobert if (!reg_overlap_mentioned_p (info->x_local[i], info->y_local[j]))
1325*404b540aSrobert continue;
1326*404b540aSrobert if (--max_swaps < 0)
1327*404b540aSrobert {
1328*404b540aSrobert memcpy (info->x_local, save_x_local, sizeof save_x_local);
1329*404b540aSrobert memcpy (info->y_local, save_y_local, sizeof save_y_local);
1330*404b540aSrobert return false;
1331*404b540aSrobert }
1332*404b540aSrobert nswaps++;
1333*404b540aSrobert tmp = info->x_local[i];
1334*404b540aSrobert info->x_local[i] = info->x_local[j];
1335*404b540aSrobert info->x_local[j] = tmp;
1336*404b540aSrobert tmp = info->y_local[i];
1337*404b540aSrobert info->y_local[i] = info->y_local[j];
1338*404b540aSrobert info->y_local[j] = tmp;
1339*404b540aSrobert j = i;
1340*404b540aSrobert }
1341*404b540aSrobert }
1342*404b540aSrobert info->had_input_conflict = true;
1343*404b540aSrobert if (dump_file && nswaps)
1344*404b540aSrobert fprintf (dump_file, "Resolved input conflict, %d %s.\n",
1345*404b540aSrobert nswaps, nswaps == 1 ? "swap" : "swaps");
1346*404b540aSrobert return true;
1347*404b540aSrobert }
1348