/* Data flow analysis for GNU compiler.
- Copyright (C) 1987, 1988, 1992, 1993, 1994 Free Software Foundation, Inc.
+ Copyright (C) 1987, 88, 92, 93, 94, 95, 1996 Free Software Foundation, Inc.
This file is part of GNU CC.
You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING. If not, write to
-the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA. */
/* This file contains the data flow analysis pass of the compiler.
int *reg_n_refs;
-/* Indexed by N; says whether a psuedo register N was ever used
+/* Indexed by N; says whether a pseudo register N was ever used
within a SUBREG that changes the size of the reg. Some machines prohibit
such objects to be in certain (usually floating-point) registers. */
/* Forward declarations */
static void find_basic_blocks PROTO((rtx, rtx));
-static int uses_reg_or_mem PROTO((rtx));
+static int jmp_uses_reg_or_mem PROTO((rtx));
static void mark_label_ref PROTO((rtx, rtx, int));
static void life_analysis PROTO((rtx, int));
void allocate_for_life_analysis PROTO((void));
static void init_regset_vector PROTO((regset *, regset, int, int));
static void propagate_block PROTO((regset, rtx, rtx, int,
regset, int));
+static rtx flow_delete_insn PROTO((rtx));
static int insn_dead_p PROTO((rtx, regset, int));
static int libcall_dead_p PROTO((rtx, regset, rtx, rtx));
static void mark_set_regs PROTO((regset, regset, rtx,
register char *block_marked = (char *) alloca (n_basic_blocks);
/* List of label_refs to all labels whose addresses are taken
and used as data. */
- rtx label_value_list = 0;
+ rtx label_value_list;
rtx x, note;
enum rtx_code prev_code, code;
- int depth;
+ int depth, pass;
+ pass = 1;
+ restart:
+
+ label_value_list = 0;
block_live_static = block_live;
bzero (block_live, n_basic_blocks);
bzero (block_marked, n_basic_blocks);
prev_code = code;
}
- if (i + 1 != n_basic_blocks)
+ /* During the second pass, `n_basic_blocks' is only an upper bound.
+ Only perform the sanity check for the first pass, and on the second
+ pass ensure `n_basic_blocks' is set to the correct value. */
+ if (pass == 1 && i + 1 != n_basic_blocks)
abort ();
+ n_basic_blocks = i + 1;
/* Don't delete the labels (in this function)
that are referenced by non-jump instructions. */
if (n_basic_blocks > 0)
{
int something_marked = 1;
+ int deleted;
/* Find all indirect jump insns and mark them as possibly jumping to all
the labels whose addresses are explicitly used. This is because,
for (i = len - 1; i >= 0; i--)
if (GET_CODE (XVECEXP (pat, 0, i)) == SET
&& SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
- && uses_reg_or_mem (SET_SRC (XVECEXP (pat, 0, i))))
+ && jmp_uses_reg_or_mem (SET_SRC (XVECEXP (pat, 0, i))))
computed_jump = 1;
}
else if (GET_CODE (pat) == SET
&& SET_DEST (pat) == pc_rtx
- && uses_reg_or_mem (SET_SRC (pat)))
+ && jmp_uses_reg_or_mem (SET_SRC (pat)))
computed_jump = 1;
if (computed_jump)
if (GET_CODE (insn) == CALL_INSN)
{
for (x = nonlocal_label_list; x; x = XEXP (x, 1))
- /* Don't try marking labels that
- were deleted as unreferenced. */
- if (GET_CODE (XEXP (x, 0)) == CODE_LABEL)
- mark_label_ref (gen_rtx (LABEL_REF, VOIDmode, XEXP (x, 0)),
- insn, 0);
+ mark_label_ref (gen_rtx (LABEL_REF, VOIDmode, XEXP (x, 0)),
+ insn, 0);
/* ??? This could be made smarter:
in some cases it's possible to tell that certain
}
}
+ /* ??? See if we have a "live" basic block that is not reachable.
+ This can happen if it is headed by a label that is preserved or
+ in one of the label lists, but no call or computed jump is in
+ the loop. It's not clear if we can delete the block or not,
+ but don't for now. However, we will mess up register status if
+ it remains unreachable, so add a fake reachability from the
+ previous block. */
+
+ for (i = 1; i < n_basic_blocks; i++)
+ if (block_live[i] && ! basic_block_drops_in[i]
+ && GET_CODE (basic_block_head[i]) == CODE_LABEL
+ && LABEL_REFS (basic_block_head[i]) == basic_block_head[i])
+ basic_block_drops_in[i] = 1;
+
/* Now delete the code for any basic blocks that can't be reached.
They can occur because jump_optimize does not recognize
unreachable loops as unreachable. */
+ deleted = 0;
for (i = 0; i < n_basic_blocks; i++)
if (!block_live[i])
{
+ deleted++;
+
+ /* Delete the insns in a (non-live) block. We physically delete
+ every non-note insn except the start and end (so
+ basic_block_head/end needn't be updated), we turn the latter
+ into NOTE_INSN_DELETED notes.
+ We use to "delete" the insns by turning them into notes, but
+ we may be deleting lots of insns that subsequent passes would
+ otherwise have to process. Secondly, lots of deleted blocks in
+ a row can really slow down propagate_block since it will
+ otherwise process insn-turned-notes multiple times when it
+ looks for loop begin/end notes. */
+ if (basic_block_head[i] != basic_block_end[i])
+ {
+ /* It would be quicker to delete all of these with a single
+ unchaining, rather than one at a time, but we need to keep
+ the NOTE's. */
+ insn = NEXT_INSN (basic_block_head[i]);
+ while (insn != basic_block_end[i])
+ {
+ if (GET_CODE (insn) == BARRIER)
+ abort ();
+ else if (GET_CODE (insn) != NOTE)
+ insn = flow_delete_insn (insn);
+ else
+ insn = NEXT_INSN (insn);
+ }
+ }
insn = basic_block_head[i];
- while (1)
+ if (GET_CODE (insn) != NOTE)
{
+ /* Turn the head into a deleted insn note. */
if (GET_CODE (insn) == BARRIER)
abort ();
- if (GET_CODE (insn) != NOTE)
- {
- PUT_CODE (insn, NOTE);
- NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (insn) = 0;
- }
- if (insn == basic_block_end[i])
- {
- /* BARRIERs are between basic blocks, not part of one.
- Delete a BARRIER if the preceding jump is deleted.
- We cannot alter a BARRIER into a NOTE
- because it is too short; but we can really delete
- it because it is not part of a basic block. */
- if (NEXT_INSN (insn) != 0
- && GET_CODE (NEXT_INSN (insn)) == BARRIER)
- delete_insn (NEXT_INSN (insn));
- break;
- }
- insn = NEXT_INSN (insn);
+ PUT_CODE (insn, NOTE);
+ NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
+ NOTE_SOURCE_FILE (insn) = 0;
}
+ insn = basic_block_end[i];
+ if (GET_CODE (insn) != NOTE)
+ {
+ /* Turn the tail into a deleted insn note. */
+ if (GET_CODE (insn) == BARRIER)
+ abort ();
+ PUT_CODE (insn, NOTE);
+ NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
+ NOTE_SOURCE_FILE (insn) = 0;
+ }
+ /* BARRIERs are between basic blocks, not part of one.
+ Delete a BARRIER if the preceding jump is deleted.
+ We cannot alter a BARRIER into a NOTE
+ because it is too short; but we can really delete
+ it because it is not part of a basic block. */
+ if (NEXT_INSN (insn) != 0
+ && GET_CODE (NEXT_INSN (insn)) == BARRIER)
+ delete_insn (NEXT_INSN (insn));
+
/* Each time we delete some basic blocks,
see if there is a jump around them that is
being turned into a no-op. If so, delete it. */
if (block_live[i - 1])
{
register int j;
- for (j = i; j < n_basic_blocks; j++)
+ for (j = i + 1; j < n_basic_blocks; j++)
if (block_live[j])
{
rtx label;
}
}
}
+
+ /* There are pathological cases where one function calling hundreds of
+ nested inline functions can generate lots and lots of unreachable
+ blocks that jump can't delete. Since we don't use sparse matrices
+ a lot of memory will be needed to compile such functions.
+ Implementing sparse matrices is a fair bit of work and it is not
+ clear that they win more than they lose (we don't want to
+ unnecessarily slow down compilation of normal code). By making
+ another pass for the pathological case, we can greatly speed up
+ their compilation without hurting normal code. This works because
+ all the insns in the unreachable blocks have either been deleted or
+ turned into notes.
+ Note that we're talking about reducing memory usage by 10's of
+ megabytes and reducing compilation time by several minutes. */
+ /* ??? The choice of when to make another pass is a bit arbitrary,
+ and was derived from empirical data. */
+ if (pass == 1
+ && deleted > 200)
+ {
+ pass++;
+ n_basic_blocks -= deleted;
+ /* `n_basic_blocks' may not be correct at this point: two previously
+ separate blocks may now be merged. That's ok though as we
+ recalculate it during the second pass. It certainly can't be
+ any larger than the current value. */
+ goto restart;
+ }
}
}
\f
-/* Return 1 if X contain a REG or MEM that is not in the constant pool. */
+/* Subroutines of find_basic_blocks. */
+
+/* Return 1 if X, the SRC_SRC of SET of (pc) contain a REG or MEM that is
+ not in the constant pool and not in the condition of an IF_THEN_ELSE. */
static int
-uses_reg_or_mem (x)
+jmp_uses_reg_or_mem (x)
rtx x;
{
enum rtx_code code = GET_CODE (x);
int i, j;
char *fmt;
- if (code == REG
- || (code == MEM
- && ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
- && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))))
- return 1;
+ switch (code)
+ {
+ case CONST:
+ case LABEL_REF:
+ case PC:
+ return 0;
+
+ case REG:
+ return 1;
+
+ case MEM:
+ return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
+ && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
+
+ case IF_THEN_ELSE:
+ return (jmp_uses_reg_or_mem (XEXP (x, 1))
+ || jmp_uses_reg_or_mem (XEXP (x, 2)));
+
+ case PLUS: case MINUS: case MULT:
+ return (jmp_uses_reg_or_mem (XEXP (x, 0))
+ || jmp_uses_reg_or_mem (XEXP (x, 1)));
+ }
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e'
- && uses_reg_or_mem (XEXP (x, i)))
+ && jmp_uses_reg_or_mem (XEXP (x, i)))
return 1;
if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
- if (uses_reg_or_mem (XVECEXP (x, i, j)))
+ if (jmp_uses_reg_or_mem (XVECEXP (x, i, j)))
return 1;
}
return 0;
}
-\f
+
/* Check expression X for label references;
if one is found, add INSN to the label's chain of references.
}
}
}
+
+/* Delete INSN by patching it out.
+ Return the next insn. */
+
+static rtx
+flow_delete_insn (insn)
+ rtx insn;
+{
+ /* ??? For the moment we assume we don't have to watch for NULLs here
+ since the start/end of basic blocks aren't deleted like this. */
+ NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
+ PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
+ return NEXT_INSN (insn);
+}
\f
/* Determine which registers are live at the start of each
basic block of the function whose first insn is F.
{
register rtx jump, head;
+
/* Update the basic_block_new_live_at_end's of the block
that falls through into this one (if any). */
head = basic_block_head[i];
- jump = PREV_INSN (head);
if (basic_block_drops_in[i])
{
- register int from_block = BLOCK_NUM (jump);
register int j;
for (j = 0; j < regset_size; j++)
- basic_block_new_live_at_end[from_block][j]
+ basic_block_new_live_at_end[i-1][j]
|= basic_block_live_at_start[i][j];
}
+
/* Update the basic_block_new_live_at_end's of
all the blocks that jump to this one. */
if (GET_CODE (head) == CODE_LABEL)
{
prev = PREV_INSN (insn);
- /* Look for loop boundaries, remembering that we are going backwards. */
- if (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
- loop_depth++;
- else if (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
- loop_depth--;
-
- /* If we have LOOP_DEPTH == 0, there has been a bookkeeping error.
- Abort now rather than setting register status incorrectly. */
- if (loop_depth == 0)
- abort ();
+ if (GET_CODE (insn) == NOTE)
+ {
+ /* Look for loop boundaries, remembering that we are going
+ backwards. */
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
+ loop_depth++;
+ else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
+ loop_depth--;
+
+ /* If we have LOOP_DEPTH == 0, there has been a bookkeeping error.
+ Abort now rather than setting register status incorrectly. */
+ if (loop_depth == 0)
+ abort ();
- /* If this is a call to `setjmp' et al,
- warn if any non-volatile datum is live. */
+ /* If this is a call to `setjmp' et al,
+ warn if any non-volatile datum is live. */
- if (final && GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
- {
- int i;
- for (i = 0; i < regset_size; i++)
- regs_live_at_setjmp[i] |= old[i];
+ if (final && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
+ {
+ int i;
+ for (i = 0; i < regset_size; i++)
+ regs_live_at_setjmp[i] |= old[i];
+ }
}
/* Update the life-status of regs for this insn.
are those live after, with DEAD regs turned off,
and then LIVE regs turned on. */
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+ else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
{
register int i;
rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
final, insn);
/* Each call clobbers all call-clobbered regs that are not
- global. Note that the function-value reg is a
+ global or fixed. Note that the function-value reg is a
call-clobbered reg, and mark_set_regs has already had
a chance to handle it. */
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- if (call_used_regs[i] && ! global_regs[i])
+ if (call_used_regs[i] && ! global_regs[i]
+ && ! fixed_regs[i])
dead[i / REGSET_ELT_BITS]
|= ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS));
/* Calls may also reference any of the global registers,
so they are made live. */
-
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (global_regs[i])
- live[i / REGSET_ELT_BITS]
- |= ((REGSET_ELT_TYPE) 1 << (i % REGSET_ELT_BITS));
+ mark_used_regs (old, live,
+ gen_rtx (REG, reg_raw_mode[i], i),
+ final, insn);
/* Calls also clobber memory. */
last_mem_set = 0;
/* Return 1 if register REGNO was used before it was set.
In other words, if it is live at function entry.
- Don't count global regster variables, though. */
+ Don't count global register variables, though. */
int
regno_uninitialized (regno)
register int offset = regno / REGSET_ELT_BITS;
register REGSET_ELT_TYPE bit
= (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
- REGSET_ELT_TYPE all_needed = (needed[offset] & bit);
REGSET_ELT_TYPE some_needed = (needed[offset] & bit);
+ REGSET_ELT_TYPE some_not_needed = (~ needed[offset]) & bit;
/* Mark it as a significant register for this basic block. */
if (significant)
n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
while (--n > 0)
{
+ REGSET_ELT_TYPE n_bit
+ = (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS);
+
if (significant)
- significant[(regno + n) / REGSET_ELT_BITS]
- |= (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS);
- dead[(regno + n) / REGSET_ELT_BITS]
- |= (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS);
+ significant[(regno + n) / REGSET_ELT_BITS] |= n_bit;
+
+ dead[(regno + n) / REGSET_ELT_BITS] |= n_bit;
some_needed
- |= (needed[(regno + n) / REGSET_ELT_BITS]
- & (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS));
- all_needed
- &= (needed[(regno + n) / REGSET_ELT_BITS]
- & (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS));
+ |= (needed[(regno + n) / REGSET_ELT_BITS] & n_bit);
+ some_not_needed
+ |= ((~ needed[(regno + n) / REGSET_ELT_BITS]) & n_bit);
}
}
/* Additional data to record if this is the final pass. */
register rtx y = reg_next_use[regno];
register int blocknum = BLOCK_NUM (insn);
- /* The next use is no longer "next", since a store intervenes. */
- reg_next_use[regno] = 0;
-
/* If this is a hard reg, record this function uses the reg. */
if (regno < FIRST_PSEUDO_REGISTER)
for (i = regno; i < endregno; i++)
{
+ /* The next use is no longer "next", since a store
+ intervenes. */
+ reg_next_use[i] = 0;
+
regs_ever_live[i] = 1;
reg_n_sets[i]++;
}
}
else
{
+ /* The next use is no longer "next", since a store
+ intervenes. */
+ reg_next_use[regno] = 0;
+
/* Keep track of which basic blocks each reg appears in. */
if (reg_basic_block[regno] == REG_BLOCK_UNKNOWN)
reg_live_length[regno]++;
}
- if (all_needed)
+ if (! some_not_needed)
{
/* Make a logical link from the next following insn
that uses this register, back to this insn.
else if (GET_CODE (q) == REG
/* PREV_INSN used here to check the semi-open interval
[insn,incr). */
- && ! reg_used_between_p (q, PREV_INSN (insn), incr))
+ && ! reg_used_between_p (q, PREV_INSN (insn), incr)
+ /* We must also check for sets of q as q may be
+ a call clobbered hard register and there may
+ be a call between PREV_INSN (insn) and incr. */
+ && ! reg_set_between_p (q, PREV_INSN (insn), incr))
{
/* We have *p followed sometime later by q = p+size.
Both p and q must be live afterward,
if (GET_CODE (temp) == CALL_INSN)
reg_n_calls_crossed[regno]++;
}
+ else
+ return;
/* If we haven't returned, it means we were able to make the
auto-inc, so update the status. First, record that this insn
if (GET_CODE (SUBREG_REG (x)) == REG
&& REGNO (SUBREG_REG (x)) >= FIRST_PSEUDO_REGISTER
&& (GET_MODE_SIZE (GET_MODE (x))
- != GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
- && (INTEGRAL_MODE_P (GET_MODE (x))
- || INTEGRAL_MODE_P (GET_MODE (SUBREG_REG (x)))))
+ != GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))))
reg_changes_size[REGNO (SUBREG_REG (x))] = 1;
/* While we're here, optimize this case. */
x = SUBREG_REG (x);
+ /* In case the SUBREG is not of a register, don't optimize */
+ if (GET_CODE (x) != REG)
+ {
+ mark_used_regs (needed, live, x, final, insn);
+ return;
+ }
+
/* ... fall through ... */
case REG:
register int offset = regno / REGSET_ELT_BITS;
register REGSET_ELT_TYPE bit
= (REGSET_ELT_TYPE) 1 << (regno % REGSET_ELT_BITS);
- REGSET_ELT_TYPE all_needed = needed[offset] & bit;
REGSET_ELT_TYPE some_needed = needed[offset] & bit;
+ REGSET_ELT_TYPE some_not_needed = (~ needed[offset]) & bit;
live[offset] |= bit;
+
/* A hard reg in a wide mode may really be multiple registers.
If so, mark all of them just like the first. */
if (regno < FIRST_PSEUDO_REGISTER)
n = HARD_REGNO_NREGS (regno, GET_MODE (x));
while (--n > 0)
{
- live[(regno + n) / REGSET_ELT_BITS]
- |= (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS);
- some_needed
- |= (needed[(regno + n) / REGSET_ELT_BITS]
- & (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS));
- all_needed
- &= (needed[(regno + n) / REGSET_ELT_BITS]
- & (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS));
+ REGSET_ELT_TYPE n_bit
+ = (REGSET_ELT_TYPE) 1 << ((regno + n) % REGSET_ELT_BITS);
+
+ live[(regno + n) / REGSET_ELT_BITS] |= n_bit;
+ some_needed |= (needed[(regno + n) / REGSET_ELT_BITS] & n_bit);
+ some_not_needed
+ |= ((~ needed[(regno + n) / REGSET_ELT_BITS]) & n_bit);
}
}
if (final)
we do not make a REG_DEAD note; likewise if we already
made such a note. */
- if (! all_needed
+ if (some_not_needed
&& ! dead_or_set_p (insn, x)
#if 0
&& (regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
if (regno < FIRST_PSEUDO_REGISTER
&& HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
{
- int n = HARD_REGNO_NREGS (regno, GET_CODE (x));
+ int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
while (--n >= 0)
some_needed |= dead_or_set_regno_p (insn, regno + n);
}
|| GET_CODE (testreg) == SIGN_EXTRACT
|| GET_CODE (testreg) == SUBREG)
{
+ if (GET_CODE (testreg) == SUBREG
+ && GET_CODE (SUBREG_REG (testreg)) == REG
+ && REGNO (SUBREG_REG (testreg)) >= FIRST_PSEUDO_REGISTER
+ && (GET_MODE_SIZE (GET_MODE (testreg))
+ != GET_MODE_SIZE (GET_MODE (SUBREG_REG (testreg)))))
+ reg_changes_size[REGNO (SUBREG_REG (testreg))] = 1;
+
/* Modifying a single register in an alternate mode
does not use any of the old value. But these other
ways of storing in a register do use the old value. */
OSDN Git Service
