/* 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.
#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 find_matches (rtx, struct match *);
-static int regclass_compatible_p (int, int);
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)
}
\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;
-}
-
#ifdef AUTO_INC_DEC
/* Find the place in the rtx X where REG is used as a memory address.
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
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);
\f
static int *regno_src_regno;
-\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
if (sregno < FIRST_PSEUDO_REGISTER
&& reg_mentioned_p (dest, PATTERN (q)))
failed = 1;
-
+
/* Attempt to replace all uses. */
else if (!validate_replace_rtx (src, dest, q))
failed = 1;
/* 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. */
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
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))
rtx *p_move_notes;
int src_regno;
int dest_regno;
- int insn_uid;
- int move_uid;
/* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
*p_move_notes = NULL_RTX;
*p_insn_notes = NULL_RTX;
- insn_uid = INSN_UID (insn);
- move_uid = INSN_UID (move_insn);
-
/* Update the various register tables. */
dest_regno = REGNO (dest);
INC_REG_N_SETS (dest_regno, 1);
{
rtx p, dst_death = 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));
#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);
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;
-
- 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,
}
}
}
+}
- /* 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;
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,
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 (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 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 */
TODO_ggc_collect /* todo_flags_finish */
}
};
-