/* Move registers around to reduce number of move instructions needed.
Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
- 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
+ 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
Free Software Foundation, Inc.
This file is part of GCC.
<http://www.gnu.org/licenses/>. */
-/* This module looks for cases where matching constraints would force
- an instruction to need a reload, and this reload would be a register
- to register move. It then attempts to change the registers used by the
- instruction to avoid the move instruction. */
+/* This module makes some simple RTL code transformations which
+ improve the subsequent register allocation. */
#include "config.h"
#include "system.h"
#include "timevar.h"
#include "tree-pass.h"
#include "df.h"
+#include "ira.h"
-static int perhaps_ends_bb_p (rtx);
static int optimize_reg_copy_1 (rtx, rtx, rtx);
static void optimize_reg_copy_2 (rtx, rtx, rtx);
static void optimize_reg_copy_3 (rtx, rtx, rtx);
static void copy_src_to_dest (rtx, rtx, rtx);
+enum match_use
+{
+ READ,
+ WRITE,
+ READWRITE
+};
+
struct match {
int with[MAX_RECOG_OPERANDS];
- enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS];
+ enum match_use use[MAX_RECOG_OPERANDS];
int commutative[MAX_RECOG_OPERANDS];
int early_clobber[MAX_RECOG_OPERANDS];
};
-static rtx discover_flags_reg (void);
-static void mark_flags_life_zones (rtx);
-static void flags_set_1 (rtx, const_rtx, void *);
-
-static int try_auto_increment (rtx, rtx, rtx, rtx, HOST_WIDE_INT, int);
static int find_matches (rtx, struct match *);
-static void replace_in_call_usage (rtx *, unsigned int, rtx, rtx);
-static int fixup_match_1 (rtx, rtx, rtx, rtx, rtx, int, int, int);
-static int stable_and_no_regs_but_for_p (rtx, rtx, rtx);
-static int regclass_compatible_p (int, int);
-static int replacement_quality (rtx);
static int fixup_match_2 (rtx, rtx, rtx, rtx);
/* Return nonzero if registers with CLASS1 and CLASS2 can be merged without
causing too much register allocation problems. */
static int
-regclass_compatible_p (int class0, int class1)
+regclass_compatible_p (enum reg_class class0, enum reg_class class1)
{
return (class0 == class1
|| (reg_class_subset_p (class0, class1)
&& ! CLASS_LIKELY_SPILLED_P (class1)));
}
+\f
+#ifdef AUTO_INC_DEC
+
/* Find the place in the rtx X where REG is used as a memory address.
Return the MEM rtx that so uses it.
If PLUSCONST is nonzero, search instead for a memory address equivalent to
if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
&& XEXP (XEXP (x, 0), 0) == reg
- && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
+ && CONST_INT_P (XEXP (XEXP (x, 0), 1))
&& INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst)
return x;
&SET_SRC (inc_insn_set),
XEXP (SET_SRC (inc_insn_set), 0), 1);
validate_change (insn, &XEXP (use, 0),
- gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
+ gen_rtx_fmt_e (inc_code,
+ GET_MODE (XEXP (use, 0)), reg),
+ 1);
if (apply_change_group ())
{
/* If there is a REG_DEAD note on this insn, we must
change this not to REG_UNUSED meaning that the register
is set, but the value is dead. Failure to do so will
- result in a sched1 dieing -- when it recomputes lifetime
+ result in sched1 dying -- when it recomputes lifetime
information, the number of REG_DEAD notes will have
changed. */
rtx note = find_reg_note (insn, REG_DEAD, reg);
if (note)
- PUT_MODE (note, REG_UNUSED);
+ PUT_REG_NOTE_KIND (note, REG_UNUSED);
+
+ add_reg_note (insn, REG_INC, reg);
- REG_NOTES (insn)
- = gen_rtx_EXPR_LIST (REG_INC,
- reg, REG_NOTES (insn));
if (! inc_insn_set)
delete_insn (inc_insn);
return 1;
}
return 0;
}
-\f
-/* Determine if the pattern generated by add_optab has a clobber,
- such as might be issued for a flags hard register. To make the
- code elsewhere simpler, we handle cc0 in this same framework.
-
- Return the register if one was discovered. Return NULL_RTX if
- if no flags were found. Return pc_rtx if we got confused. */
-
-static rtx
-discover_flags_reg (void)
-{
- rtx tmp;
- tmp = gen_rtx_REG (word_mode, 10000);
- tmp = gen_add3_insn (tmp, tmp, const2_rtx);
-
- /* If we get something that isn't a simple set, or a
- [(set ..) (clobber ..)], this whole function will go wrong. */
- if (GET_CODE (tmp) == SET)
- return NULL_RTX;
- else if (GET_CODE (tmp) == PARALLEL)
- {
- int found;
-
- if (XVECLEN (tmp, 0) != 2)
- return pc_rtx;
- tmp = XVECEXP (tmp, 0, 1);
- if (GET_CODE (tmp) != CLOBBER)
- return pc_rtx;
- tmp = XEXP (tmp, 0);
-
- /* Don't do anything foolish if the md wanted to clobber a
- scratch or something. We only care about hard regs.
- Moreover we don't like the notion of subregs of hard regs. */
- if (GET_CODE (tmp) == SUBREG
- && REG_P (SUBREG_REG (tmp))
- && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
- return pc_rtx;
- found = (REG_P (tmp) && REGNO (tmp) < FIRST_PSEUDO_REGISTER);
-
- return (found ? tmp : NULL_RTX);
- }
-
- return pc_rtx;
-}
-
-/* It is a tedious task identifying when the flags register is live and
- when it is safe to optimize. Since we process the instruction stream
- multiple times, locate and record these live zones by marking the
- mode of the instructions --
-
- QImode is used on the instruction at which the flags becomes live.
-
- HImode is used within the range (exclusive) that the flags are
- live. Thus the user of the flags is not marked.
-
- All other instructions are cleared to VOIDmode. */
-
-/* Used to communicate with flags_set_1. */
-static rtx flags_set_1_rtx;
-static int flags_set_1_set;
-
-static void
-mark_flags_life_zones (rtx flags)
-{
- int flags_regno;
- int flags_nregs;
- basic_block block;
-
-#ifdef HAVE_cc0
- /* If we found a flags register on a cc0 host, bail. */
- if (flags == NULL_RTX)
- flags = cc0_rtx;
- else if (flags != cc0_rtx)
- flags = pc_rtx;
-#endif
-
- /* Simple cases first: if no flags, clear all modes. If confusing,
- mark the entire function as being in a flags shadow. */
- if (flags == NULL_RTX || flags == pc_rtx)
- {
- enum machine_mode mode = (flags ? HImode : VOIDmode);
- rtx insn;
- for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
- PUT_MODE (insn, mode);
- return;
- }
-
-#ifdef HAVE_cc0
- flags_regno = -1;
- flags_nregs = 1;
-#else
- flags_regno = REGNO (flags);
- flags_nregs = hard_regno_nregs[flags_regno][GET_MODE (flags)];
-#endif
- flags_set_1_rtx = flags;
-
- /* Process each basic block. */
- FOR_EACH_BB_REVERSE (block)
- {
- rtx insn, end;
- int live;
-
- insn = BB_HEAD (block);
- end = BB_END (block);
-
- /* Look out for the (unlikely) case of flags being live across
- basic block boundaries. */
- live = 0;
-#ifndef HAVE_cc0
- {
- int i;
- for (i = 0; i < flags_nregs; ++i)
- live |= REGNO_REG_SET_P (df_get_live_in (block), flags_regno + i);
- }
#endif
- while (1)
- {
- /* Process liveness in reverse order of importance --
- alive, death, birth. This lets more important info
- overwrite the mode of lesser info. */
-
- if (INSN_P (insn))
- {
-#ifdef HAVE_cc0
- /* In the cc0 case, death is not marked in reg notes,
- but is instead the mere use of cc0 when it is alive. */
- if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
- live = 0;
-#else
- /* In the hard reg case, we watch death notes. */
- if (live && find_regno_note (insn, REG_DEAD, flags_regno))
- live = 0;
-#endif
- PUT_MODE (insn, (live ? HImode : VOIDmode));
-
- /* In either case, birth is denoted simply by its presence
- as the destination of a set. */
- flags_set_1_set = 0;
- note_stores (PATTERN (insn), flags_set_1, NULL);
- if (flags_set_1_set)
- {
- live = 1;
- PUT_MODE (insn, QImode);
- }
- }
- else
- PUT_MODE (insn, (live ? HImode : VOIDmode));
-
- if (insn == end)
- break;
- insn = NEXT_INSN (insn);
- }
- }
-}
-
-/* A subroutine of mark_flags_life_zones, called through note_stores. */
-
-static void
-flags_set_1 (rtx x, const_rtx pat, void *data ATTRIBUTE_UNUSED)
-{
- if (GET_CODE (pat) == SET
- && reg_overlap_mentioned_p (x, flags_set_1_rtx))
- flags_set_1_set = 1;
-}
\f
static int *regno_src_regno;
-/* Indicate how good a choice REG (which appears as a source) is to replace
- a destination register with. The higher the returned value, the better
- the choice. The main objective is to avoid using a register that is
- a candidate for tying to a hard register, since the output might in
- turn be a candidate to be tied to a different hard register. */
-static int
-replacement_quality (rtx reg)
-{
- int src_regno;
-
- /* Bad if this isn't a register at all. */
- if (!REG_P (reg))
- return 0;
-
- /* If this register is not meant to get a hard register,
- it is a poor choice. */
- if (REG_LIVE_LENGTH (REGNO (reg)) < 0)
- return 0;
-
- src_regno = regno_src_regno[REGNO (reg)];
-
- /* If it was not copied from another register, it is fine. */
- if (src_regno < 0)
- return 3;
-
- /* Copied from a hard register? */
- if (src_regno < FIRST_PSEUDO_REGISTER)
- return 1;
-
- /* Copied from a pseudo register - not as bad as from a hard register,
- yet still cumbersome, since the register live length will be lengthened
- when the registers get tied. */
- return 2;
-}
-\f
-/* Return 1 if INSN might end a basic block. */
-
-static int perhaps_ends_bb_p (rtx insn)
-{
- switch (GET_CODE (insn))
- {
- case CODE_LABEL:
- case JUMP_INSN:
- /* These always end a basic block. */
- return 1;
-
- case CALL_INSN:
- /* A CALL_INSN might be the last insn of a basic block, if it is inside
- an EH region or if there are nonlocal gotos. Note that this test is
- very conservative. */
- if (nonlocal_goto_handler_labels)
- return 1;
- /* Fall through. */
- default:
- return can_throw_internal (insn);
- }
-}
-\f
/* INSN is a copy from SRC to DEST, both registers, and SRC does not die
in INSN.
rtx dest_death = 0;
int sregno = REGNO (src);
int dregno = REGNO (dest);
+ basic_block bb = BLOCK_FOR_INSN (insn);
/* We don't want to mess with hard regs if register classes are small. */
if (sregno == dregno
for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
{
- /* ??? We can't scan past the end of a basic block without updating
- the register lifetime info (REG_DEAD/basic_block_live_at_start). */
- if (perhaps_ends_bb_p (p))
- break;
- else if (! INSN_P (p))
+ if (! INSN_P (p))
continue;
+ if (BLOCK_FOR_INSN (p) != bb)
+ break;
if (reg_set_p (src, p) || reg_set_p (dest, p)
/* If SRC is an asm-declared register, it must not be replaced
int s_length = 0;
int d_n_calls = 0;
int s_n_calls = 0;
+ int s_freq_calls = 0;
+ int d_freq_calls = 0;
/* We can do the optimization. Scan forward from INSN again,
replacing regs as we go. Set FAILED if a replacement can't
/* For SREGNO, count the total number of insns scanned.
For DREGNO, count the total number of insns scanned after
passing the death note for DREGNO. */
- s_length++;
- if (dest_death)
- d_length++;
+ if (!DEBUG_INSN_P (p))
+ {
+ s_length++;
+ if (dest_death)
+ d_length++;
+ }
/* If the insn in which SRC dies is a CALL_INSN, don't count it
as a call that has been crossed. Otherwise, count it. */
/* Similarly, total calls for SREGNO, total calls beyond
the death note for DREGNO. */
s_n_calls++;
+ s_freq_calls += REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q));
if (dest_death)
- d_n_calls++;
+ {
+ d_n_calls++;
+ d_freq_calls += REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q));
+ }
}
/* If DEST dies here, remove the death note and save it for
}
REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
+ REG_FREQ_CALLS_CROSSED (sregno) -= s_freq_calls;
}
/* Move death note of SRC from P to INSN. */
if (REG_LIVE_LENGTH (dregno) >= 0)
REG_LIVE_LENGTH (dregno) += d_length;
REG_N_CALLS_CROSSED (dregno) += d_n_calls;
+ REG_FREQ_CALLS_CROSSED (dregno) += d_freq_calls;
}
}
rtx set;
int sregno = REGNO (src);
int dregno = REGNO (dest);
+ basic_block bb = BLOCK_FOR_INSN (insn);
for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
{
- /* ??? We can't scan past the end of a basic block without updating
- the register lifetime info (REG_DEAD/basic_block_live_at_start). */
- if (perhaps_ends_bb_p (p))
- break;
- else if (! INSN_P (p))
+ if (! INSN_P (p))
continue;
+ if (BLOCK_FOR_INSN (p) != bb)
+ break;
set = single_set (p);
if (set && SET_SRC (set) == dest && SET_DEST (set) == src
{
if (reg_mentioned_p (dest, PATTERN (q)))
{
+ rtx note;
+
PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
+ note = FIND_REG_INC_NOTE (q, dest);
+ if (note)
+ {
+ remove_note (q, note);
+ add_reg_note (q, REG_INC, src);
+ }
df_insn_rescan (q);
}
if (CALL_P (q))
{
+ int freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q));
REG_N_CALLS_CROSSED (dregno)--;
REG_N_CALLS_CROSSED (sregno)++;
+ REG_FREQ_CALLS_CROSSED (dregno) -= freq;
+ REG_FREQ_CALLS_CROSSED (sregno) += freq;
}
}
int dst_no = REGNO (dest);
rtx p, set;
enum machine_mode old_mode;
+ basic_block bb = BLOCK_FOR_INSN (insn);
if (src_no < FIRST_PSEUDO_REGISTER
|| dst_no < FIRST_PSEUDO_REGISTER
|| REG_N_DEATHS (src_no) != 1
|| REG_N_SETS (src_no) != 1)
return;
+
for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
- /* ??? We can't scan past the end of a basic block without updating
- the register lifetime info (REG_DEAD/basic_block_live_at_start). */
- if (perhaps_ends_bb_p (p))
+ if (INSN_P (p) && BLOCK_FOR_INSN (p) != bb)
break;
-
- if (! p)
+
+ if (! p || BLOCK_FOR_INSN (p) != bb)
return;
if (! (set = single_set (p))
/* reg_set_in_bb[REGNO] points to basic block iff the register is set
only once in the given block and has REG_EQUAL note. */
-basic_block *reg_set_in_bb;
+static basic_block *reg_set_in_bb;
/* Size of reg_set_in_bb array. */
static unsigned int max_reg_computed;
if (!reg_set_in_bb)
{
max_reg_computed = max = max_reg_num ();
- reg_set_in_bb = xcalloc (max, sizeof (*reg_set_in_bb));
+ reg_set_in_bb = XCNEWVEC (basic_block, max);
FOR_EACH_BB (bb)
FOR_BB_INSNS (bb, p)
fixup_match_2 (rtx insn, rtx dst, rtx src, rtx offset)
{
rtx p, dst_death = 0;
- int length, num_calls = 0;
+ int length, num_calls = 0, freq_calls = 0;
+ basic_block bb = BLOCK_FOR_INSN (insn);
/* If SRC dies in INSN, we'd have to move the death note. This is
considered to be very unlikely, so we just skip the optimization
{
rtx pset;
- /* ??? We can't scan past the end of a basic block without updating
- the register lifetime info (REG_DEAD/basic_block_live_at_start). */
- if (perhaps_ends_bb_p (p))
- break;
- else if (! INSN_P (p))
+ if (! INSN_P (p))
continue;
+ if (BLOCK_FOR_INSN (p) != bb)
+ break;
if (find_regno_note (p, REG_DEAD, REGNO (dst)))
dst_death = p;
- if (! dst_death)
+ if (! dst_death && !DEBUG_INSN_P (p))
length++;
pset = single_set (p);
if (pset && SET_DEST (pset) == dst
&& GET_CODE (SET_SRC (pset)) == PLUS
&& XEXP (SET_SRC (pset), 0) == src
- && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
+ && CONST_INT_P (XEXP (SET_SRC (pset), 1)))
{
HOST_WIDE_INT newconst
= INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
remove_death (REGNO (dst), dst_death);
REG_LIVE_LENGTH (REGNO (dst)) += length;
REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
+ REG_FREQ_CALLS_CROSSED (REGNO (dst)) += freq_calls;
}
if (dump_file)
#ifdef AUTO_INC_DEC
for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
{
- if (LABEL_P (p)
- || JUMP_P (p))
- break;
if (! INSN_P (p))
continue;
+ if (BLOCK_FOR_INSN (p) != bb)
+ break;
if (reg_overlap_mentioned_p (dst, PATTERN (p)))
{
if (try_auto_increment (p, insn, 0, dst, newconst, 0))
}
for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
{
- if (LABEL_P (p)
- || JUMP_P (p))
- break;
if (! INSN_P (p))
continue;
+ if (BLOCK_FOR_INSN (p) != bb)
+ break;
if (reg_overlap_mentioned_p (dst, PATTERN (p)))
{
try_auto_increment (p, insn, 0, dst, newconst, 1);
if (CALL_P (p))
{
if (! dst_death)
- num_calls++;
+ {
+ num_calls++;
+ freq_calls += REG_FREQ_FROM_BB (BLOCK_FOR_INSN (p));
+ }
if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
break;
return 0;
}
-/* Main entry for the register move optimization.
- F is the first instruction.
- NREGS is one plus the highest pseudo-reg number used in the instruction.
- REGMOVE_DUMP_FILE is a stream for output of a trace of actions taken
- (or 0 if none should be output). */
+/* A forward pass. Replace output operands with input operands. */
static void
-regmove_optimize (rtx f, int nregs)
+regmove_forward_pass (void)
{
+ basic_block bb;
rtx insn;
- struct match match;
- int pass;
- int i;
- rtx copy_src, copy_dst;
- /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
- confused by non-call exceptions ending blocks. */
- if (flag_non_call_exceptions)
+ if (! flag_expensive_optimizations)
return;
- df_note_add_problem ();
- df_analyze ();
-
- regstat_init_n_sets_and_refs ();
- regstat_compute_ri ();
-
- /* Find out where a potential flags register is live, and so that we
- can suppress some optimizations in those zones. */
- mark_flags_life_zones (discover_flags_reg ());
-
- regno_src_regno = XNEWVEC (int, nregs);
- for (i = nregs; --i >= 0; )
- regno_src_regno[i] = -1;
-
- /* A forward/backward pass. Replace output operands with input operands. */
+ if (dump_file)
+ fprintf (dump_file, "Starting forward pass...\n");
- for (pass = 0; pass <= 2; pass++)
+ FOR_EACH_BB (bb)
{
- if (! flag_regmove && pass >= flag_expensive_optimizations)
- goto done;
-
- if (dump_file)
- fprintf (dump_file, "Starting %s pass...\n",
- pass ? "backward" : "forward");
-
- for (insn = pass ? get_last_insn () : f; insn;
- insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
+ FOR_BB_INSNS (bb, insn)
{
- rtx set;
- int op_no, match_no;
-
- set = single_set (insn);
+ rtx set = single_set (insn);
if (! set)
continue;
- if (flag_expensive_optimizations && ! pass
- && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
- || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
+ if ((GET_CODE (SET_SRC (set)) == SIGN_EXTEND
+ || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
&& REG_P (XEXP (SET_SRC (set), 0))
&& REG_P (SET_DEST (set)))
optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
- if (flag_expensive_optimizations && ! pass
- && REG_P (SET_SRC (set))
+ if (REG_P (SET_SRC (set))
&& REG_P (SET_DEST (set)))
{
/* If this is a register-register copy where SRC is not dead,
}
}
}
- if (! flag_regmove)
- continue;
-
- if (! find_matches (insn, &match))
- continue;
-
- /* Now scan through the operands looking for a source operand
- which is supposed to match the destination operand.
- Then scan forward for an instruction which uses the dest
- operand.
- If it dies there, then replace the dest in both operands with
- the source operand. */
-
- for (op_no = 0; op_no < recog_data.n_operands; op_no++)
- {
- rtx src, dst, src_subreg;
- enum reg_class src_class, dst_class;
-
- match_no = match.with[op_no];
-
- /* Nothing to do if the two operands aren't supposed to match. */
- if (match_no < 0)
- continue;
-
- src = recog_data.operand[op_no];
- dst = recog_data.operand[match_no];
-
- if (!REG_P (src))
- continue;
-
- src_subreg = src;
- if (GET_CODE (dst) == SUBREG
- && GET_MODE_SIZE (GET_MODE (dst))
- >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
- {
- dst = SUBREG_REG (dst);
- src_subreg = lowpart_subreg (GET_MODE (dst),
- src, GET_MODE (src));
- if (!src_subreg)
- continue;
- }
- if (!REG_P (dst)
- || REGNO (dst) < FIRST_PSEUDO_REGISTER)
- continue;
-
- if (REGNO (src) < FIRST_PSEUDO_REGISTER)
- {
- if (match.commutative[op_no] < op_no)
- regno_src_regno[REGNO (dst)] = REGNO (src);
- continue;
- }
-
- if (REG_LIVE_LENGTH (REGNO (src)) < 0)
- continue;
-
- /* op_no/src must be a read-only operand, and
- match_operand/dst must be a write-only operand. */
- if (match.use[op_no] != READ
- || match.use[match_no] != WRITE)
- continue;
-
- if (match.early_clobber[match_no]
- && count_occurrences (PATTERN (insn), src, 0) > 1)
- continue;
-
- /* Make sure match_operand is the destination. */
- if (recog_data.operand[match_no] != SET_DEST (set))
- continue;
-
- /* If the operands already match, then there is nothing to do. */
- if (operands_match_p (src, dst))
- continue;
-
- /* But in the commutative case, we might find a better match. */
- if (match.commutative[op_no] >= 0)
- {
- rtx comm = recog_data.operand[match.commutative[op_no]];
- if (operands_match_p (comm, dst)
- && (replacement_quality (comm)
- >= replacement_quality (src)))
- continue;
- }
-
- src_class = reg_preferred_class (REGNO (src));
- dst_class = reg_preferred_class (REGNO (dst));
- if (! regclass_compatible_p (src_class, dst_class))
- continue;
-
- if (GET_MODE (src) != GET_MODE (dst))
- continue;
-
- if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
- op_no, match_no))
- break;
- }
}
}
+}
- /* A backward pass. Replace input operands with output operands. */
+/* A backward pass. Replace input operands with output operands. */
+
+static void
+regmove_backward_pass (void)
+{
+ basic_block bb;
+ rtx insn, prev;
if (dump_file)
fprintf (dump_file, "Starting backward pass...\n");
- for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
+ FOR_EACH_BB_REVERSE (bb)
{
- if (INSN_P (insn))
+ /* ??? Use the safe iterator because fixup_match_2 can remove
+ insns via try_auto_increment. */
+ FOR_BB_INSNS_REVERSE_SAFE (bb, insn, prev)
{
+ struct match match;
+ rtx copy_src, copy_dst;
int op_no, match_no;
int success = 0;
+ if (! INSN_P (insn))
+ continue;
+
if (! find_matches (insn, &match))
continue;
{
rtx set, p, src, dst;
rtx src_note, dst_note;
- int num_calls = 0;
+ int num_calls = 0, freq_calls = 0;
enum reg_class src_class, dst_class;
int length;
if (REGNO (src) < FIRST_PSEUDO_REGISTER)
{
if (GET_CODE (SET_SRC (set)) == PLUS
- && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
+ && CONST_INT_P (XEXP (SET_SRC (set), 1))
&& XEXP (SET_SRC (set), 0) == src
&& fixup_match_2 (insn, dst, src,
XEXP (SET_SRC (set), 1)))
{
rtx pset;
- /* ??? We can't scan past the end of a basic block without
- updating the register lifetime info
- (REG_DEAD/basic_block_live_at_start). */
- if (perhaps_ends_bb_p (p))
- break;
- else if (! INSN_P (p))
+ if (! INSN_P (p))
continue;
+ if (BLOCK_FOR_INSN (p) != bb)
+ break;
- length++;
+ if (!DEBUG_INSN_P (p))
+ length++;
/* ??? See if all of SRC is set in P. This test is much
more conservative than it needs to be. */
if (pset && SET_DEST (pset) == src)
{
/* We use validate_replace_rtx, in case there
- are multiple identical source operands. All of
- them have to be changed at the same time. */
+ are multiple identical source operands. All
+ of them have to be changed at the same time:
+ when validate_replace_rtx() calls
+ apply_change_group(). */
+ validate_change (p, &SET_DEST (pset), dst, 1);
if (validate_replace_rtx (src, dst, insn))
- {
- if (validate_change (p, &SET_DEST (pset),
- dst, 0))
- success = 1;
- else
- {
- /* Change all source operands back.
- This modifies the dst as a side-effect. */
- validate_replace_rtx (dst, src, insn);
- /* Now make sure the dst is right. */
- validate_change (insn,
- recog_data.operand_loc[match_no],
- dst, 0);
- }
- }
+ success = 1;
break;
}
- /* We can't make this change if SRC is read or
+ /* We can't make this change if DST is mentioned at
+ all in P, since we are going to change its value.
+ We can't make this change if SRC is read or
partially written in P, since we are going to
- eliminate SRC. We can't make this change
- if DST is mentioned at all in P,
- since we are going to change its value. */
- if (reg_overlap_mentioned_p (src, PATTERN (p))
- || reg_mentioned_p (dst, PATTERN (p)))
- break;
+ eliminate SRC. However, if it's a debug insn, we
+ can't refrain from making the change, for this
+ would cause codegen differences, so instead we
+ invalidate debug expressions that reference DST,
+ and adjust references to SRC in them so that they
+ become references to DST. */
+ if (reg_mentioned_p (dst, PATTERN (p)))
+ {
+ if (DEBUG_INSN_P (p))
+ validate_change (p, &INSN_VAR_LOCATION_LOC (p),
+ gen_rtx_UNKNOWN_VAR_LOC (), 1);
+ else
+ break;
+ }
+ if (reg_overlap_mentioned_p (src, PATTERN (p)))
+ {
+ if (DEBUG_INSN_P (p))
+ validate_replace_rtx_group (src, dst, p);
+ else
+ break;
+ }
/* If we have passed a call instruction, and the
pseudo-reg DST is not already live across a call,
if (CALL_P (p))
{
num_calls++;
+ freq_calls += REG_FREQ_FROM_BB (BLOCK_FOR_INSN (p));
if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
break;
REG_N_CALLS_CROSSED (dstno) += num_calls;
REG_N_CALLS_CROSSED (srcno) -= num_calls;
+ REG_FREQ_CALLS_CROSSED (dstno) += freq_calls;
+ REG_FREQ_CALLS_CROSSED (srcno) -= freq_calls;
REG_LIVE_LENGTH (dstno) += length;
if (REG_LIVE_LENGTH (srcno) >= 0)
break;
}
+ else if (num_changes_pending () > 0)
+ cancel_changes (0);
}
/* If we weren't able to replace any of the alternatives, try an
copy_src_to_dest (insn, copy_src, copy_dst);
}
}
+}
+
+/* Main entry for the register move optimization. */
+
+static unsigned int
+regmove_optimize (void)
+{
+ int i;
+ int nregs = max_reg_num ();
+
+ df_note_add_problem ();
+ df_analyze ();
+
+ if (flag_ira_loop_pressure)
+ ira_set_pseudo_classes (dump_file);
+
+ regstat_init_n_sets_and_refs ();
+ regstat_compute_ri ();
+
+ regno_src_regno = XNEWVEC (int, nregs);
+ for (i = nregs; --i >= 0; )
+ regno_src_regno[i] = -1;
+
+ /* A forward pass. Replace output operands with input operands. */
+ regmove_forward_pass ();
+
+ /* A backward pass. Replace input operands with output operands. */
+ regmove_backward_pass ();
- done:
/* Clean up. */
free (regno_src_regno);
if (reg_set_in_bb)
}
regstat_free_n_sets_and_refs ();
regstat_free_ri ();
+ if (flag_ira_loop_pressure)
+ free_reg_info ();
+ return 0;
}
/* Returns nonzero if INSN's pattern has matching constraints for any operand.
return any_matches;
}
-/* Try to replace all occurrences of DST_REG with SRC in LOC, that is
- assumed to be in INSN. */
-
-static void
-replace_in_call_usage (rtx *loc, unsigned int dst_reg, rtx src, rtx insn)
-{
- rtx x = *loc;
- enum rtx_code code;
- const char *fmt;
- int i, j;
-
- if (! x)
- return;
-
- code = GET_CODE (x);
- if (code == REG)
- {
- if (REGNO (x) != dst_reg)
- return;
-
- validate_change (insn, loc, src, 1);
-
- return;
- }
-
- /* Process each of our operands recursively. */
- fmt = GET_RTX_FORMAT (code);
- for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
- if (*fmt == 'e')
- replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
- else if (*fmt == 'E')
- for (j = 0; j < XVECLEN (x, i); j++)
- replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
-}
-
-/* Try to replace output operand DST in SET, with input operand SRC. SET is
- the only set in INSN. INSN has just been recognized and constrained.
- SRC is operand number OPERAND_NUMBER in INSN.
- DST is operand number MATCH_NUMBER in INSN.
- If BACKWARD is nonzero, we have been called in a backward pass.
- Return nonzero for success. */
-
-static int
-fixup_match_1 (rtx insn, rtx set, rtx src, rtx src_subreg, rtx dst,
- int backward, int operand_number, int match_number)
-{
- rtx p;
- rtx post_inc = 0, post_inc_set = 0, search_end = 0;
- int success = 0;
- int num_calls = 0, s_num_calls = 0;
- enum rtx_code code = NOTE;
- HOST_WIDE_INT insn_const = 0, newconst = 0;
- rtx overlap = 0; /* need to move insn ? */
- rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
- int length, s_length;
-
- if (! src_note)
- {
- /* Look for (set (regX) (op regA constX))
- (set (regY) (op regA constY))
- and change that to
- (set (regA) (op regA constX)).
- (set (regY) (op regA constY-constX)).
- This works for add and shift operations, if
- regA is dead after or set by the second insn. */
-
- code = GET_CODE (SET_SRC (set));
- if ((code == PLUS || code == LSHIFTRT
- || code == ASHIFT || code == ASHIFTRT)
- && XEXP (SET_SRC (set), 0) == src
- && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
- insn_const = INTVAL (XEXP (SET_SRC (set), 1));
- else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
- return 0;
- else
- /* We might find a src_note while scanning. */
- code = NOTE;
- }
-
- if (dump_file)
- fprintf (dump_file,
- "Could fix operand %d of insn %d matching operand %d.\n",
- operand_number, INSN_UID (insn), match_number);
-
- /* If SRC is equivalent to a constant set in a different basic block,
- then do not use it for this optimization. We want the equivalence
- so that if we have to reload this register, we can reload the
- constant, rather than extending the lifespan of the register. */
- if (reg_is_remote_constant_p (src, insn))
- return 0;
-
- /* Scan forward to find the next instruction that
- uses the output operand. If the operand dies here,
- then replace it in both instructions with
- operand_number. */
-
- for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
- {
- if (CALL_P (p))
- replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
- REGNO (dst), src, p);
-
- /* ??? We can't scan past the end of a basic block without updating
- the register lifetime info (REG_DEAD/basic_block_live_at_start). */
- if (perhaps_ends_bb_p (p))
- break;
- else if (! INSN_P (p))
- continue;
-
- length++;
- if (src_note)
- s_length++;
-
- if (reg_set_p (src, p) || reg_set_p (dst, p)
- || (GET_CODE (PATTERN (p)) == USE
- && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
- break;
-
- /* See if all of DST dies in P. This test is
- slightly more conservative than it needs to be. */
- if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
- && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
- {
- /* If we would be moving INSN, check that we won't move it
- into the shadow of a live a live flags register. */
- /* ??? We only try to move it in front of P, although
- we could move it anywhere between OVERLAP and P. */
- if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
- break;
-
- if (! src_note)
- {
- rtx q;
- rtx set2 = NULL_RTX;
-
- /* If an optimization is done, the value of SRC while P
- is executed will be changed. Check that this is OK. */
- if (reg_overlap_mentioned_p (src, PATTERN (p)))
- break;
- for (q = p; q; q = NEXT_INSN (q))
- {
- /* ??? We can't scan past the end of a basic block without
- updating the register lifetime info
- (REG_DEAD/basic_block_live_at_start). */
- if (perhaps_ends_bb_p (q))
- {
- q = 0;
- break;
- }
- else if (! INSN_P (q))
- continue;
- else if (reg_overlap_mentioned_p (src, PATTERN (q))
- || reg_set_p (src, q))
- break;
- }
- if (q)
- set2 = single_set (q);
- if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
- || XEXP (SET_SRC (set2), 0) != src
- || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
- || (SET_DEST (set2) != src
- && ! find_reg_note (q, REG_DEAD, src)))
- {
- /* If this is a PLUS, we can still save a register by doing
- src += insn_const;
- P;
- src -= insn_const; .
- This also gives opportunities for subsequent
- optimizations in the backward pass, so do it there. */
- if (code == PLUS && backward
- /* Don't do this if we can likely tie DST to SET_DEST
- of P later; we can't do this tying here if we got a
- hard register. */
- && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
- && single_set (p)
- && REG_P (SET_DEST (single_set (p)))
- && (REGNO (SET_DEST (single_set (p)))
- < FIRST_PSEUDO_REGISTER))
- /* We may only emit an insn directly after P if we
- are not in the shadow of a live flags register. */
- && GET_MODE (p) == VOIDmode)
- {
- search_end = q;
- q = insn;
- set2 = set;
- newconst = -insn_const;
- code = MINUS;
- }
- else
- break;
- }
- else
- {
- newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
- /* Reject out of range shifts. */
- if (code != PLUS
- && (newconst < 0
- || ((unsigned HOST_WIDE_INT) newconst
- >= (GET_MODE_BITSIZE (GET_MODE
- (SET_SRC (set2)))))))
- break;
- if (code == PLUS)
- {
- post_inc = q;
- if (SET_DEST (set2) != src)
- post_inc_set = set2;
- }
- }
- /* We use 1 as last argument to validate_change so that all
- changes are accepted or rejected together by apply_change_group
- when it is called by validate_replace_rtx . */
- validate_change (q, &XEXP (SET_SRC (set2), 1),
- GEN_INT (newconst), 1);
- }
- validate_change (insn, recog_data.operand_loc[match_number], src, 1);
- if (validate_replace_rtx (dst, src_subreg, p))
- success = 1;
- break;
- }
-
- if (reg_overlap_mentioned_p (dst, PATTERN (p)))
- break;
- if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
- {
- /* INSN was already checked to be movable wrt. the registers that it
- sets / uses when we found no REG_DEAD note for src on it, but it
- still might clobber the flags register. We'll have to check that
- we won't insert it into the shadow of a live flags register when
- we finally know where we are to move it. */
- overlap = p;
- src_note = find_reg_note (p, REG_DEAD, src);
- }
-
- /* If we have passed a call instruction, and the pseudo-reg SRC is not
- already live across a call, then don't perform the optimization. */
- if (CALL_P (p))
- {
- if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
- break;
-
- num_calls++;
-
- if (src_note)
- s_num_calls++;
-
- }
- }
-
- if (! success)
- return 0;
-
- /* Remove the death note for DST from P. */
- remove_note (p, dst_note);
- if (code == MINUS)
- {
- post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
- if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
- && search_end
- && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
- post_inc = 0;
- validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
- INC_REG_N_SETS (REGNO (src), 1);
- REG_LIVE_LENGTH (REGNO (src))++;
- }
- if (overlap)
- {
- /* The lifetime of src and dest overlap,
- but we can change this by moving insn. */
- rtx pat = PATTERN (insn);
- if (src_note)
- remove_note (overlap, src_note);
- if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
- && code == PLUS
- && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
- insn = overlap;
- else
- {
- rtx notes = REG_NOTES (insn);
-
- p = emit_insn_after_setloc (pat, PREV_INSN (p), INSN_LOCATOR (insn));
- delete_insn (insn);
- REG_NOTES (p) = notes;
- df_notes_rescan (p);
- }
- }
- /* Sometimes we'd generate src = const; src += n;
- if so, replace the instruction that set src
- in the first place. */
-
- if (! overlap && (code == PLUS || code == MINUS))
- {
- rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
- rtx q, set2 = NULL_RTX;
- int num_calls2 = 0, s_length2 = 0;
-
- if (note && CONSTANT_P (XEXP (note, 0)))
- {
- for (q = PREV_INSN (insn); q; q = PREV_INSN (q))
- {
- /* ??? We can't scan past the end of a basic block without
- updating the register lifetime info
- (REG_DEAD/basic_block_live_at_start). */
- if (perhaps_ends_bb_p (q))
- {
- q = 0;
- break;
- }
- else if (! INSN_P (q))
- continue;
-
- s_length2++;
- if (reg_set_p (src, q))
- {
- set2 = single_set (q);
- break;
- }
- if (reg_overlap_mentioned_p (src, PATTERN (q)))
- {
- q = 0;
- break;
- }
- if (CALL_P (p))
- num_calls2++;
- }
- if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
- && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
- {
- delete_insn (q);
- INC_REG_N_SETS (REGNO (src), -1);
- REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
- REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
- insn_const = 0;
- }
- }
- }
-
- if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
- && (code == PLUS || code == MINUS) && insn_const
- && try_auto_increment (p, insn, 0, src, insn_const, 1))
- insn = p;
- else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
- && post_inc
- && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
- post_inc = 0;
- /* If post_inc still prevails, try to find an
- insn where it can be used as a pre-in/decrement.
- If code is MINUS, this was already tried. */
- if (post_inc && code == PLUS
- /* Check that newconst is likely to be usable
- in a pre-in/decrement before starting the search. */
- && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
- || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
- && exact_log2 (newconst))
- {
- rtx q, inc_dest;
-
- inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
- for (q = post_inc; (q = NEXT_INSN (q)); )
- {
- /* ??? We can't scan past the end of a basic block without updating
- the register lifetime info
- (REG_DEAD/basic_block_live_at_start). */
- if (perhaps_ends_bb_p (q))
- break;
- else if (! INSN_P (q))
- continue;
- else if (src != inc_dest
- && (reg_overlap_mentioned_p (src, PATTERN (q))
- || reg_set_p (src, q)))
- break;
- else if (reg_set_p (inc_dest, q))
- break;
- else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
- {
- try_auto_increment (q, post_inc,
- post_inc_set, inc_dest, newconst, 1);
- break;
- }
- }
- }
-
- /* Move the death note for DST to INSN if it is used
- there. */
- if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
- {
- XEXP (dst_note, 1) = REG_NOTES (insn);
- REG_NOTES (insn) = dst_note;
- }
-
- if (src_note)
- {
- /* Move the death note for SRC from INSN to P. */
- if (! overlap)
- remove_note (insn, src_note);
- XEXP (src_note, 1) = REG_NOTES (p);
- REG_NOTES (p) = src_note;
-
- REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
- }
-
- INC_REG_N_SETS (REGNO (src), 1);
- INC_REG_N_SETS (REGNO (dst), -1);
-
- REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
-
- REG_LIVE_LENGTH (REGNO (src)) += s_length;
- if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
- {
- REG_LIVE_LENGTH (REGNO (dst)) -= length;
- /* REG_LIVE_LENGTH is only an approximation after
- combine if sched is not run, so make sure that we
- still have a reasonable value. */
- if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
- REG_LIVE_LENGTH (REGNO (dst)) = 2;
- }
- if (dump_file)
- fprintf (dump_file,
- "Fixed operand %d of insn %d matching operand %d.\n",
- operand_number, INSN_UID (insn), match_number);
- return 1;
-}
-
-
-/* Return nonzero if X is stable and mentions no registers but for
- mentioning SRC or mentioning / changing DST . If in doubt, presume
- it is unstable.
- The rationale is that we want to check if we can move an insn easily
- while just paying attention to SRC and DST. */
-static int
-stable_and_no_regs_but_for_p (rtx x, rtx src, rtx dst)
-{
- RTX_CODE code = GET_CODE (x);
- switch (GET_RTX_CLASS (code))
- {
- case RTX_UNARY:
- case RTX_BIN_ARITH:
- case RTX_COMM_ARITH:
- case RTX_COMPARE:
- case RTX_COMM_COMPARE:
- case RTX_TERNARY:
- case RTX_BITFIELD_OPS:
- {
- int i;
- const char *fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- if (fmt[i] == 'e'
- && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
- return 0;
- return 1;
- }
- case RTX_OBJ:
- if (code == REG)
- return x == src || x == dst;
- /* If this is a MEM, look inside - there might be a register hidden in
- the address of an unchanging MEM. */
- if (code == MEM
- && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
- return 0;
- /* Fall through. */
- default:
- return ! rtx_unstable_p (x);
- }
-}
\f
static bool
return (optimize > 0 && flag_regmove);
}
-/* Register allocation pre-pass, to reduce number of moves necessary
- for two-address machines. */
-static unsigned int
-rest_of_handle_regmove (void)
-{
- regmove_optimize (get_insns (), max_reg_num ());
- return 0;
-}
-struct tree_opt_pass pass_regmove =
+struct rtl_opt_pass pass_regmove =
{
+ {
+ RTL_PASS,
"regmove", /* name */
gate_handle_regmove, /* gate */
- rest_of_handle_regmove, /* execute */
+ regmove_optimize, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_df_finish |
+ TODO_df_finish | TODO_verify_rtl_sharing |
TODO_dump_func |
- TODO_ggc_collect, /* todo_flags_finish */
- 'N' /* letter */
+ TODO_ggc_collect /* todo_flags_finish */
+ }
};
-