#include "expr.h"
#include "obstack.h"
+#include "splay-tree.h"
#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free
static rtx label_value_list;
+/* Holds information for tracking conditional register life information. */
+struct reg_cond_life_info
+{
+ /* An EXPR_LIST of conditions under which a register is dead. */
+ rtx condition;
+
+ /* ??? Could store mask of bytes that are dead, so that we could finally
+ track lifetimes of multi-word registers accessed via subregs. */
+};
+
/* For use in communicating between propagate_block and its subroutines.
Holds all information needed to compute life and def-use information. */
/* Bit N is set if register N is conditionally or unconditionally live. */
regset reg_live;
- /* Bit N is set if register N is unconditionally dead this insn. */
- regset new_dead;
-
- /* Bit N is set if register N is live this insn. */
- regset new_live;
+ /* Bit N is set if register N is set this insn. */
+ regset new_set;
/* Element N is the next insn that uses (hard or pseudo) register N
within the current basic block; or zero, if there is no such insn. */
/* If non-null, record the set of registers set in the basic block. */
regset local_set;
+#ifdef HAVE_conditional_execution
+ /* Indexed by register number, holds a reg_cond_life_info for each
+ register that is not unconditionally live or dead. */
+ splay_tree reg_cond_dead;
+
+ /* Bit N is set if register N is in an expression in reg_cond_dead. */
+ regset reg_cond_reg;
+#endif
+
/* Non-zero if the value of CC0 is live. */
int cc0_live;
static void mark_set_1 PARAMS ((struct propagate_block_info *,
enum rtx_code, rtx, rtx,
rtx, int));
+#ifdef HAVE_conditional_execution
+static int mark_regno_cond_dead PARAMS ((struct propagate_block_info *,
+ int, rtx));
+static void free_reg_cond_life_info PARAMS ((splay_tree_value));
+static int flush_reg_cond_reg_1 PARAMS ((splay_tree_node, void *));
+static void flush_reg_cond_reg PARAMS ((struct propagate_block_info *,
+ int));
+static rtx ior_reg_cond PARAMS ((rtx, rtx));
+static rtx not_reg_cond PARAMS ((rtx));
+static rtx nand_reg_cond PARAMS ((rtx, rtx));
+#endif
#ifdef AUTO_INC_DEC
static void find_auto_inc PARAMS ((struct propagate_block_info *,
rtx, rtx));
void debug_flow_info PARAMS ((void));
static void dump_edge_info PARAMS ((FILE *, edge, int));
-static void count_reg_sets_1 PARAMS ((rtx, int));
-static void count_reg_sets PARAMS ((rtx, int));
-static void count_reg_references PARAMS ((rtx, int));
static void invalidate_mems_from_autoinc PARAMS ((struct propagate_block_info *,
rtx));
static void remove_fake_successors PARAMS ((basic_block));
If block B consisted only of this single jump, turn it into a deleted
note. */
q = b->end;
- if (GET_CODE (q) == JUMP_INSN)
+ if (GET_CODE (q) == JUMP_INSN
+ && (simplejump_p (q)
+ || (b->succ == e && e->succ_next == NULL)))
{
#ifdef HAVE_cc0
/* If this was a conditional jump, we need to also delete
tidy_fallthru_edge (s, b, c);
}
}
-
-/* Discover and record the loop depth at the head of each basic block. */
-
-void
-calculate_loop_depth (dump)
- FILE *dump;
-{
- struct loops loops;
-
- /* The loop infrastructure does the real job for us. */
- flow_loops_find (&loops);
-
- if (dump)
- flow_loops_dump (&loops, dump, 0);
-
- flow_loops_free (&loops);
-}
\f
/* Perform data flow analysis.
F is the first insn of the function; FLAGS is a set of PROP_* flags
register int i;
static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
#endif
- sbitmap all_blocks;
/* Record which registers will be eliminated. We use this in
mark_used_regs. */
if (flags & PROP_SCAN_DEAD_CODE)
init_alias_analysis ();
- max_regno = max_reg_num ();
-
/* Always remove no-op moves. Do this before other processing so
that we don't have to keep re-scanning them. */
delete_noop_moves (f);
data from lifetime analysis. */
allocate_reg_life_data ();
allocate_bb_life_data ();
- all_blocks = sbitmap_alloc (n_basic_blocks);
- sbitmap_ones (all_blocks);
/* Find the set of registers live on function exit. */
mark_regs_live_at_end (EXIT_BLOCK_PTR->global_live_at_start);
if (flags & PROP_REG_INFO)
memset (regs_ever_live, 0, sizeof(regs_ever_live));
- update_life_info (all_blocks, UPDATE_LIFE_GLOBAL, flags);
+ update_life_info (NULL, UPDATE_LIFE_GLOBAL, flags);
/* Clean up. */
- sbitmap_free (all_blocks);
-
if (flags & PROP_SCAN_DEAD_CODE)
end_alias_analysis ();
}
/* Updates life information starting with the basic blocks set in BLOCKS.
+ If BLOCKS is null, consider it to be the universal set.
- If LOCAL_ONLY, such as after splitting or peepholeing, we are only
- expecting local modifications to basic blocks. If we find extra
- registers live at the beginning of a block, then we either killed
+ If EXTENT is UPDATE_LIFE_LOCAL, such as after splitting or peepholeing,
+ we are only expecting local modifications to basic blocks. If we find
+ extra registers live at the beginning of a block, then we either killed
useful data, or we have a broken split that wants data not provided.
If we find registers removed from live_at_start, that means we have
a broken peephole that is killing a register it shouldn't.
count_or_remove_death_notes (blocks, 1);
}
- EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
+ if (blocks)
{
- basic_block bb = BASIC_BLOCK (i);
+ EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
+ {
+ basic_block bb = BASIC_BLOCK (i);
- COPY_REG_SET (tmp, bb->global_live_at_end);
- propagate_block (bb, tmp, (regset) NULL, prop_flags);
+ COPY_REG_SET (tmp, bb->global_live_at_end);
+ propagate_block (bb, tmp, (regset) NULL, prop_flags);
- if (extent == UPDATE_LIFE_LOCAL)
- verify_local_live_at_start (tmp, bb);
- });
+ if (extent == UPDATE_LIFE_LOCAL)
+ verify_local_live_at_start (tmp, bb);
+ });
+ }
+ else
+ {
+ for (i = n_basic_blocks - 1; i >= 0; --i)
+ {
+ basic_block bb = BASIC_BLOCK (i);
+
+ COPY_REG_SET (tmp, bb->global_live_at_end);
+ propagate_block (bb, tmp, (regset) NULL, prop_flags);
+
+ if (extent == UPDATE_LIFE_LOCAL)
+ verify_local_live_at_start (tmp, bb);
+ }
+ }
FREE_REG_SET (tmp);
/* Propagate global life info around the graph of basic blocks. Begin
considering blocks with their corresponding bit set in BLOCKS_IN.
+ If BLOCKS_IN is null, consider it the universal set.
+
BLOCKS_OUT is set for every block that was changed. */
static void
/* Queue the blocks set in the initial mask. Do this in reverse block
number order so that we are more likely for the first round to do
useful work. We use AUX non-null to flag that the block is queued. */
- EXECUTE_IF_SET_IN_SBITMAP (blocks_in, 0, i,
+ if (blocks_in)
{
- basic_block bb = BASIC_BLOCK (i);
- *--qhead = bb;
- bb->aux = bb;
- });
+ EXECUTE_IF_SET_IN_SBITMAP (blocks_in, 0, i,
+ {
+ basic_block bb = BASIC_BLOCK (i);
+ *--qhead = bb;
+ bb->aux = bb;
+ });
+ }
+ else
+ {
+ for (i = 0; i < n_basic_blocks; ++i)
+ {
+ basic_block bb = BASIC_BLOCK (i);
+ *--qhead = bb;
+ bb->aux = bb;
+ }
+ }
- sbitmap_zero (blocks_out);
+ if (blocks_out)
+ sbitmap_zero (blocks_out);
while (qhead != qtail)
{
IOR_REG_SET (new_live_at_end, sb->global_live_at_start);
}
+ /* Force the stack pointer to be live -- which might not already be
+ the case for blocks within infinite loops. */
+ SET_REGNO_REG_SET (new_live_at_end, STACK_POINTER_REGNUM);
+
/* Regs used in phi nodes are not included in
global_live_at_start, since they are live only along a
particular edge. Set those regs that are live because of a
phi node alternative corresponding to this particular block. */
- for_each_successor_phi (bb, &set_phi_alternative_reg,
- new_live_at_end);
+ if (in_ssa_form)
+ for_each_successor_phi (bb, &set_phi_alternative_reg,
+ new_live_at_end);
if (bb == ENTRY_BLOCK_PTR)
{
/* Let our caller know that BB changed enough to require its
death notes updated. */
- SET_BIT (blocks_out, bb->index);
+ if (blocks_out)
+ SET_BIT (blocks_out, bb->index);
if (! rescan)
{
FREE_REG_SET (tmp);
FREE_REG_SET (new_live_at_end);
- EXECUTE_IF_SET_IN_SBITMAP (blocks_out, 0, i,
+ if (blocks_out)
{
- basic_block bb = BASIC_BLOCK (i);
- FREE_REG_SET (bb->local_set);
- });
+ EXECUTE_IF_SET_IN_SBITMAP (blocks_out, 0, i,
+ {
+ basic_block bb = BASIC_BLOCK (i);
+ FREE_REG_SET (bb->local_set);
+ });
+ }
+ else
+ {
+ for (i = n_basic_blocks - 1; i >= 0; --i)
+ {
+ basic_block bb = BASIC_BLOCK (i);
+ FREE_REG_SET (bb->local_set);
+ }
+ }
free (queue);
}
{
int i;
+ max_regno = max_reg_num ();
+
/* Recalculate the register space, in case it has grown. Old style
vector oriented regsets would set regset_{size,bytes} here also. */
allocate_reg_info (max_regno, FALSE, FALSE);
delete it. */
if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead)
{
+ /* Record sets. Do this even for dead instructions, since they
+ would have killed the values if they hadn't been deleted. */
+ mark_set_regs (pbi, PATTERN (insn), insn);
+
+ /* CC0 is now known to be dead. Either this insn used it,
+ in which case it doesn't anymore, or clobbered it,
+ so the next insn can't use it. */
+ pbi->cc0_live = 0;
+
if (libcall_is_dead)
{
prev = propagate_block_delete_libcall (pbi->bb, insn, note);
else
propagate_block_delete_insn (pbi->bb, insn);
- /* CC0 is now known to be dead. Either this insn used it,
- in which case it doesn't anymore, or clobbered it,
- so the next insn can't use it. */
- pbi->cc0_live = 0;
-
return prev;
}
}
#endif /* AUTO_INC_DEC */
- CLEAR_REG_SET (pbi->new_live);
- CLEAR_REG_SET (pbi->new_dead);
+ CLEAR_REG_SET (pbi->new_set);
/* If this is not the final pass, and this insn is copying the value of
a library call and it's dead, don't scan the insns that perform the
}
}
- /* Update reg_live for the registers killed and used. */
- AND_COMPL_REG_SET (pbi->reg_live, pbi->new_dead);
- IOR_REG_SET (pbi->reg_live, pbi->new_live);
-
/* On final pass, update counts of how many insns in which each reg
is live. */
if (flags & PROP_REG_INFO)
else
pbi->reg_next_use = NULL;
- pbi->new_live = BITMAP_XMALLOC ();
- pbi->new_dead = BITMAP_XMALLOC ();
+ pbi->new_set = BITMAP_XMALLOC ();
+
+#ifdef HAVE_conditional_execution
+ pbi->reg_cond_dead = splay_tree_new (splay_tree_compare_ints, NULL,
+ free_reg_cond_life_info);
+ pbi->reg_cond_reg = BITMAP_XMALLOC ();
+
+ /* If this block ends in a conditional branch, for each register live
+ from one side of the branch and not the other, record the register
+ as conditionally dead. */
+ if (GET_CODE (bb->end) == JUMP_INSN
+ && condjump_p (bb->end)
+ && ! simplejump_p (bb->end))
+ {
+ regset_head diff_head;
+ regset diff = INITIALIZE_REG_SET (diff_head);
+ basic_block bb_true, bb_false;
+ rtx cond_true, cond_false;
+ int i;
+
+ /* Identify the successor blocks. */
+ bb_false = bb->succ->succ_next->dest;
+ bb_true = bb->succ->dest;
+ if (bb->succ->flags & EDGE_FALLTHRU)
+ {
+ basic_block t = bb_false;
+ bb_false = bb_true;
+ bb_true = t;
+ }
+ else if (! (bb->succ->succ_next->flags & EDGE_FALLTHRU))
+ abort ();
+
+ /* Extract the condition from the branch. */
+ cond_true = XEXP (SET_SRC (PATTERN (bb->end)), 0);
+ cond_false = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond_true)),
+ GET_MODE (cond_true), XEXP (cond_true, 0),
+ XEXP (cond_true, 1));
+ if (GET_CODE (XEXP (SET_SRC (PATTERN (bb->end)), 1)) == PC)
+ {
+ rtx t = cond_false;
+ cond_false = cond_true;
+ cond_true = t;
+ }
+
+ /* Compute which register lead different lives in the successors. */
+ if (bitmap_operation (diff, bb_true->global_live_at_start,
+ bb_false->global_live_at_start, BITMAP_XOR))
+ {
+ if (GET_CODE (XEXP (cond_true, 0)) != REG)
+ abort ();
+ SET_REGNO_REG_SET (pbi.reg_cond_reg, REGNO (XEXP (cond_true, 0)));
+
+ /* For each such register, mark it conditionally dead. */
+ EXECUTE_IF_SET_IN_REG_SET
+ (diff, 0, i,
+ {
+ struct reg_cond_life_info *rcli;
+ rtx cond;
+
+ rcli = (struct reg_cond_life_info *) xmalloc (sizeof (*rcli));
+
+ if (REGNO_REG_SET_P (bb_true->global_live_at_start, i))
+ cond = cond_false;
+ else
+ cond = cond_true;
+ rcli->condition = alloc_EXPR_LIST (0, cond, NULL_RTX);
+
+ splay_tree_insert (pbi.reg_cond_dead, i,
+ (splay_tree_value) rcli);
+ });
+ }
+
+ FREE_REG_SET (diff);
+ }
+#endif
return pbi;
}
{
free_EXPR_LIST_list (&pbi->mem_set_list);
- BITMAP_XFREE (pbi->new_live);
- BITMAP_XFREE (pbi->new_dead);
+ BITMAP_XFREE (pbi->new_set);
+
+#ifdef HAVE_conditional_execution
+ splay_tree_delete (pbi->reg_cond_dead);
+ BITMAP_XFREE (pbi->reg_cond_reg);
+#endif
if (pbi->reg_next_use)
free (pbi->reg_next_use);
int flags;
{
int regno_first = -1, regno_last = -1;
+ int not_dead = 0;
int i;
/* Some targets place small structures in registers for
/* Modifying just one hardware register of a multi-reg value or just a
byte field of a register does not mean the value from before this insn
- is now dead. But it does mean liveness of that register at the end of
- the block is significant.
+ is now dead. Of course, if it was dead after it's unused now. */
+
+ switch (GET_CODE (reg))
+ {
+ case ZERO_EXTRACT:
+ case SIGN_EXTRACT:
+ case STRICT_LOW_PART:
+ /* ??? Assumes STRICT_LOW_PART not used on multi-word registers. */
+ do
+ reg = XEXP (reg, 0);
+ while (GET_CODE (reg) == SUBREG
+ || GET_CODE (reg) == ZERO_EXTRACT
+ || GET_CODE (reg) == SIGN_EXTRACT
+ || GET_CODE (reg) == STRICT_LOW_PART);
+ if (GET_CODE (reg) == MEM)
+ break;
+ not_dead = REGNO_REG_SET_P (pbi->reg_live, REGNO (reg));
+ /* FALLTHRU */
- Within mark_set_1, however, we treat it as if the register is indeed
- modified. mark_used_regs will, however, also treat this register as
- being used. Thus, we treat these insns as setting a new value for the
- register as a function of its old value. This cases LOG_LINKS to be
- made appropriately and this will help combine.
+ case REG:
+ regno_last = regno_first = REGNO (reg);
+ if (regno_first < FIRST_PSEUDO_REGISTER)
+ regno_last += HARD_REGNO_NREGS (regno_first, GET_MODE (reg)) - 1;
+ break;
+
+ case SUBREG:
+ if (GET_CODE (SUBREG_REG (reg)) == REG)
+ {
+ enum machine_mode outer_mode = GET_MODE (reg);
+ enum machine_mode inner_mode = GET_MODE (SUBREG_REG (reg));
- ??? This is all done incorrectly. We should not be setting bits in
- new_dead for these registers, since, as we just explained, they are
- not dead. We should be setting bits in local_set, and updating
- LOG_LINKS, but that is different. */
+ /* Identify the range of registers affected. This is moderately
+ tricky for hard registers. See alter_subreg. */
+
+ regno_last = regno_first = REGNO (SUBREG_REG (reg));
+ if (regno_first < FIRST_PSEUDO_REGISTER)
+ {
+#ifdef ALTER_HARD_SUBREG
+ regno_first = ALTER_HARD_SUBREG (outer_mode, SUBREG_WORD (reg),
+ inner_mode, regno_first);
+#else
+ regno_first += SUBREG_WORD (reg);
+#endif
+ regno_last = (regno_first
+ + HARD_REGNO_NREGS (regno_first, outer_mode) - 1);
+
+ /* Since we've just adjusted the register number ranges, make
+ sure REG matches. Otherwise some_was_live will be clear
+ when it shouldn't have been, and we'll create incorrect
+ REG_UNUSED notes. */
+ reg = gen_rtx_REG (outer_mode, regno_first);
+ }
+ else
+ {
+ /* If the number of words in the subreg is less than the number
+ of words in the full register, we have a well-defined partial
+ set. Otherwise the high bits are undefined.
+
+ This is only really applicable to pseudos, since we just took
+ care of multi-word hard registers. */
+ if (((GET_MODE_SIZE (outer_mode)
+ + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
+ < ((GET_MODE_SIZE (inner_mode)
+ + UNITS_PER_WORD - 1) / UNITS_PER_WORD))
+ not_dead = REGNO_REG_SET_P (pbi->reg_live, regno_first);
+
+ reg = SUBREG_REG (reg);
+ }
+ }
+ else
+ reg = SUBREG_REG (reg);
+ break;
- while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
- || GET_CODE (reg) == SIGN_EXTRACT
- || GET_CODE (reg) == STRICT_LOW_PART)
- reg = XEXP (reg, 0);
+ default:
+ break;
+ }
/* If this set is a MEM, then it kills any aliased writes.
If this set is a REG, then it kills any MEMs which use the reg. */
}
if (GET_CODE (reg) == REG
- && (regno_first = REGNO (reg),
- ! (regno_first == FRAME_POINTER_REGNUM
- && (! reload_completed || frame_pointer_needed)))
+ && ! (regno_first == FRAME_POINTER_REGNUM
+ && (! reload_completed || frame_pointer_needed))
#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
&& ! (regno_first == HARD_FRAME_POINTER_REGNUM
&& (! reload_completed || frame_pointer_needed))
{
int some_was_live = 0, some_was_dead = 0;
- if (regno_first < FIRST_PSEUDO_REGISTER)
- regno_last = (regno_first
- + HARD_REGNO_NREGS (regno_first, GET_MODE (reg)) - 1);
- else
- regno_last = regno_first;
-
for (i = regno_first; i <= regno_last; ++i)
{
int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i);
if (pbi->local_set)
SET_REGNO_REG_SET (pbi->local_set, i);
+ if (code != CLOBBER)
+ SET_REGNO_REG_SET (pbi->new_set, i);
some_was_live |= needed_regno;
some_was_dead |= ! needed_regno;
}
+#ifdef HAVE_conditional_execution
+ /* Consider conditional death in deciding that the register needs
+ a death note. */
+ if (some_was_live
+ /* The stack pointer is never dead. Well, not strictly true,
+ but it's very difficult to tell from here. Hopefully
+ combine_stack_adjustments will fix up the most egregious
+ errors. */
+ && regno_first != STACK_POINTER_REGNUM)
+ {
+ for (i = regno_first; i <= regno_last; ++i)
+ if (! mark_regno_cond_dead (pbi, i, cond))
+ not_dead = 1;
+ }
+#endif
+
/* Additional data to record if this is the final pass. */
if (flags & (PROP_LOG_LINKS | PROP_REG_INFO
| PROP_DEATH_NOTES | PROP_AUTOINC))
LOG_LINKS (y) = alloc_INSN_LIST (insn, LOG_LINKS (y));
}
}
+ else if (not_dead)
+ ;
else if (! some_was_live)
{
if (flags & PROP_REG_INFO)
&& regno_first != STACK_POINTER_REGNUM)
{
for (i = regno_first; i <= regno_last; ++i)
- SET_REGNO_REG_SET (pbi->new_dead, i);
+ CLEAR_REGNO_REG_SET (pbi->reg_live, i);
}
}
else if (GET_CODE (reg) == REG)
}
}
\f
+#ifdef HAVE_conditional_execution
+/* Mark REGNO conditionally dead. Return true if the register is
+ now unconditionally dead. */
+
+static int
+mark_regno_cond_dead (pbi, regno, cond)
+ struct propagate_block_info *pbi;
+ int regno;
+ rtx cond;
+{
+ /* If this is a store to a predicate register, the value of the
+ predicate is changing, we don't know that the predicate as seen
+ before is the same as that seen after. Flush all dependant
+ conditions from reg_cond_dead. This will make all such
+ conditionally live registers unconditionally live. */
+ if (REGNO_REG_SET_P (pbi->reg_cond_reg, regno))
+ flush_reg_cond_reg (pbi, regno);
+
+ /* If this is an unconditional store, remove any conditional
+ life that may have existed. */
+ if (cond == NULL_RTX)
+ splay_tree_remove (pbi->reg_cond_dead, regno);
+ else
+ {
+ splay_tree_node node;
+ struct reg_cond_life_info *rcli;
+ rtx ncond;
+
+ /* Otherwise this is a conditional set. Record that fact.
+ It may have been conditionally used, or there may be a
+ subsequent set with a complimentary condition. */
+
+ node = splay_tree_lookup (pbi->reg_cond_dead, regno);
+ if (node == NULL)
+ {
+ /* The register was unconditionally live previously.
+ Record the current condition as the condition under
+ which it is dead. */
+ rcli = (struct reg_cond_life_info *)
+ xmalloc (sizeof (*rcli));
+ rcli->condition = alloc_EXPR_LIST (0, cond, NULL_RTX);
+ splay_tree_insert (pbi->reg_cond_dead, regno,
+ (splay_tree_value) rcli);
+
+ SET_REGNO_REG_SET (pbi->reg_cond_reg,
+ REGNO (XEXP (cond, 0)));
+
+ /* Not unconditionaly dead. */
+ return 0;
+ }
+ else
+ {
+ /* The register was conditionally live previously.
+ Add the new condition to the old. */
+ rcli = (struct reg_cond_life_info *) node->value;
+ ncond = rcli->condition;
+ ncond = ior_reg_cond (ncond, cond);
+
+ /* If the register is now unconditionally dead,
+ remove the entry in the splay_tree. */
+ if (ncond == const1_rtx)
+ splay_tree_remove (pbi->reg_cond_dead, regno);
+ else
+ {
+ rcli->condition = ncond;
+
+ SET_REGNO_REG_SET (pbi->reg_cond_reg,
+ REGNO (XEXP (cond, 0)));
+
+ /* Not unconditionaly dead. */
+ return 0;
+ }
+ }
+ }
+
+ return 1;
+}
+
+/* Called from splay_tree_delete for pbi->reg_cond_life. */
+
+static void
+free_reg_cond_life_info (value)
+ splay_tree_value value;
+{
+ struct reg_cond_life_info *rcli = (struct reg_cond_life_info *) value;
+ free_EXPR_LIST_list (&rcli->condition);
+ free (rcli);
+}
+
+/* Helper function for flush_reg_cond_reg. */
+
+static int
+flush_reg_cond_reg_1 (node, data)
+ splay_tree_node node;
+ void *data;
+{
+ struct reg_cond_life_info *rcli;
+ int *xdata = (int *) data;
+ unsigned int regno = xdata[0];
+ rtx c, *prev;
+
+ /* Don't need to search if last flushed value was farther on in
+ the in-order traversal. */
+ if (xdata[1] >= (int) node->key)
+ return 0;
+
+ /* Splice out portions of the expression that refer to regno. */
+ rcli = (struct reg_cond_life_info *) node->value;
+ c = *(prev = &rcli->condition);
+ while (c)
+ {
+ if (regno == REGNO (XEXP (XEXP (c, 0), 0)))
+ {
+ rtx next = XEXP (c, 1);
+ free_EXPR_LIST_node (c);
+ c = *prev = next;
+ }
+ else
+ c = *(prev = &XEXP (c, 1));
+ }
+
+ /* If the entire condition is now NULL, signal the node to be removed. */
+ if (! rcli->condition)
+ {
+ xdata[1] = node->key;
+ return -1;
+ }
+ else
+ return 0;
+}
+
+/* Flush all (sub) expressions referring to REGNO from REG_COND_LIVE. */
+
+static void
+flush_reg_cond_reg (pbi, regno)
+ struct propagate_block_info *pbi;
+ int regno;
+{
+ int pair[2];
+
+ pair[0] = regno;
+ pair[1] = -1;
+ while (splay_tree_foreach (pbi->reg_cond_dead,
+ flush_reg_cond_reg_1, pair) == -1)
+ splay_tree_remove (pbi->reg_cond_dead, pair[1]);
+
+ CLEAR_REGNO_REG_SET (pbi->reg_cond_reg, regno);
+}
+
+/* Logical arithmetic on predicate conditions. IOR, NOT and NAND.
+ We actually use EXPR_LIST to chain the sub-expressions together
+ instead of IOR because it's easier to manipulate and we have
+ the lists.c functions to reuse nodes.
+
+ Return a new rtl expression as appropriate. */
+
+static rtx
+ior_reg_cond (old, x)
+ rtx old, x;
+{
+ enum rtx_code x_code;
+ rtx x_reg;
+ rtx c;
+
+ /* We expect these conditions to be of the form (eq reg 0). */
+ x_code = GET_CODE (x);
+ if (GET_RTX_CLASS (x_code) != '<'
+ || GET_CODE (x_reg = XEXP (x, 0)) != REG
+ || XEXP (x, 1) != const0_rtx)
+ abort ();
+
+ /* Search the expression for an existing sub-expression of X_REG. */
+ for (c = old; c ; c = XEXP (c, 1))
+ {
+ rtx y = XEXP (c, 0);
+ if (REGNO (XEXP (y, 0)) == REGNO (x_reg))
+ {
+ /* If we find X already present in OLD, we need do nothing. */
+ if (GET_CODE (y) == x_code)
+ return old;
+
+ /* If we find X being a compliment of a condition in OLD,
+ then the entire condition is true. */
+ if (GET_CODE (y) == reverse_condition (x_code))
+ return const1_rtx;
+ }
+ }
+
+ /* Otherwise just add to the chain. */
+ return alloc_EXPR_LIST (0, x, old);
+}
+
+static rtx
+not_reg_cond (x)
+ rtx x;
+{
+ enum rtx_code x_code;
+ rtx x_reg;
+
+ /* We expect these conditions to be of the form (eq reg 0). */
+ x_code = GET_CODE (x);
+ if (GET_RTX_CLASS (x_code) != '<'
+ || GET_CODE (x_reg = XEXP (x, 0)) != REG
+ || XEXP (x, 1) != const0_rtx)
+ abort ();
+
+ return alloc_EXPR_LIST (0, gen_rtx_fmt_ee (reverse_condition (x_code),
+ VOIDmode, x_reg, const0_rtx),
+ NULL_RTX);
+}
+
+static rtx
+nand_reg_cond (old, x)
+ rtx old, x;
+{
+ enum rtx_code x_code;
+ rtx x_reg;
+ rtx c, *prev;
+
+ /* We expect these conditions to be of the form (eq reg 0). */
+ x_code = GET_CODE (x);
+ if (GET_RTX_CLASS (x_code) != '<'
+ || GET_CODE (x_reg = XEXP (x, 0)) != REG
+ || XEXP (x, 1) != const0_rtx)
+ abort ();
+
+ /* Search the expression for an existing sub-expression of X_REG. */
+
+ for (c = *(prev = &old); c ; c = *(prev = &XEXP (c, 1)))
+ {
+ rtx y = XEXP (c, 0);
+ if (REGNO (XEXP (y, 0)) == REGNO (x_reg))
+ {
+ /* If we find X already present in OLD, then we need to
+ splice it out. */
+ if (GET_CODE (y) == x_code)
+ {
+ *prev = XEXP (c, 1);
+ free_EXPR_LIST_node (c);
+ return old ? old : const0_rtx;
+ }
+
+ /* If we find X being a compliment of a condition in OLD,
+ then we need do nothing. */
+ if (GET_CODE (y) == reverse_condition (x_code))
+ return old;
+ }
+ }
+
+ /* Otherwise, by implication, the register in question is now live for
+ the inverse of the condition X. */
+ return alloc_EXPR_LIST (0, gen_rtx_fmt_ee (reverse_condition (x_code),
+ VOIDmode, x_reg, const0_rtx),
+ old);
+}
+#endif /* HAVE_conditional_execution */
+\f
#ifdef AUTO_INC_DEC
/* X is a MEM found in INSN. See if we can convert it into an auto-increment
/* If the original source was dead, it's dead now. */
rtx note = find_reg_note (incr, REG_DEAD, NULL_RTX);
if (note && XEXP (note, 0) != addr)
- SET_REGNO_REG_SET (pbi->new_dead, REGNO (XEXP (note, 0)));
+ CLEAR_REGNO_REG_SET (pbi->reg_live, REGNO (XEXP (note, 0)));
PUT_CODE (incr, NOTE);
NOTE_LINE_NUMBER (incr) = NOTE_INSN_DELETED;
int regno = REGNO (reg);
int some_was_live = REGNO_REG_SET_P (pbi->reg_live, regno);
int some_was_dead = ! some_was_live;
-
- SET_REGNO_REG_SET (pbi->new_live, regno);
+ int some_not_set;
+ int n;
/* 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)
{
- int n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
while (--n > 0)
{
- int regno_n = regno + n;
- int needed_regno = REGNO_REG_SET_P (pbi->reg_live, regno_n);
-
- SET_REGNO_REG_SET (pbi->new_live, regno_n);
+ int needed_regno = REGNO_REG_SET_P (pbi->reg_live, regno + n);
some_was_live |= needed_regno;
some_was_dead |= ! needed_regno;
}
}
}
+ /* Find out if any of the register was set this insn. */
+ some_not_set = ! REGNO_REG_SET_P (pbi->new_set, regno);
+ if (regno < FIRST_PSEUDO_REGISTER)
+ {
+ n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ while (--n > 0)
+ some_not_set |= ! REGNO_REG_SET_P (pbi->new_set, regno + n);
+ }
+
/* Record and count the insns in which a reg dies. If it is used in
this insn and was dead below the insn then it dies in this insn.
If it was set in this insn, we do not make a REG_DEAD note;
- likewise if we already made such a note.
-
- ??? This could be done better. In new_dead we have a record of
- which registers are set or clobbered this insn (which in itself is
- slightly incorrect, see the commentary near strict_low_part in
- mark_set_1), which should be the set of registers that we do not
- wish to create death notes for under the above rule. Note that
- we have not yet processed the call-clobbered/call-used registers,
- and they do not quite follow the above rule, since we do want death
- notes for call-clobbered register arguments. Which begs the whole
- question of whether we should in fact have death notes for registers
- used and clobbered (but not set) in the same insn. The only useful
- thing we ought to be getting from dead_or_set_p is detection of
- duplicate death notes. */
-
- if ((pbi->flags & PROP_DEATH_NOTES)
+ likewise if we already made such a note. */
+ if ((pbi->flags & (PROP_DEATH_NOTES | PROP_REG_INFO))
&& some_was_dead
- && ! dead_or_set_p (insn, reg))
+ && some_not_set)
{
- int n;
-
/* Check for the case where the register dying partially
overlaps the register set by this insn. */
if (regno < FIRST_PSEUDO_REGISTER
{
n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
while (--n >= 0)
- some_was_live |= dead_or_set_regno_p (insn, regno + n);
+ some_was_live |= REGNO_REG_SET_P (pbi->new_set, regno + n);
}
/* If none of the words in X is needed, make a REG_DEAD note.
Otherwise, we must make partial REG_DEAD notes. */
if (! some_was_live)
{
- REG_NOTES (insn)
- = alloc_EXPR_LIST (REG_DEAD, reg, REG_NOTES (insn));
- REG_N_DEATHS (regno)++;
+ if ((pbi->flags & PROP_DEATH_NOTES)
+ && ! find_regno_note (insn, REG_DEAD, regno))
+ REG_NOTES (insn)
+ = alloc_EXPR_LIST (REG_DEAD, reg, REG_NOTES (insn));
+
+ if (pbi->flags & PROP_REG_INFO)
+ REG_N_DEATHS (regno)++;
}
else
{
n = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1;
for (; n >= regno; n--)
- if (!REGNO_REG_SET_P (pbi->reg_live, n)
+ if (! REGNO_REG_SET_P (pbi->reg_live, n)
&& ! dead_or_set_regno_p (insn, n))
REG_NOTES (insn)
= alloc_EXPR_LIST (REG_DEAD,
REG_NOTES (insn));
}
}
+
+ SET_REGNO_REG_SET (pbi->reg_live, regno);
+ if (regno < FIRST_PSEUDO_REGISTER)
+ {
+ n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ while (--n > 0)
+ SET_REGNO_REG_SET (pbi->reg_live, regno + n);
+ }
+
+#ifdef HAVE_conditional_execution
+ /* If this is a conditional use, record that fact. If it is later
+ conditionally set, we'll know to kill the register. */
+ if (cond != NULL_RTX)
+ {
+ splay_tree_node node;
+ struct reg_cond_life_info *rcli;
+ rtx ncond;
+
+ if (some_was_live)
+ {
+ node = splay_tree_lookup (pbi->reg_cond_dead, regno);
+ if (node == NULL)
+ {
+ /* The register was unconditionally live previously.
+ No need to do anything. */
+ }
+ else
+ {
+ /* The register was conditionally live previously.
+ Subtract the new life cond from the old death cond. */
+ rcli = (struct reg_cond_life_info *) node->value;
+ ncond = rcli->condition;
+ ncond = nand_reg_cond (ncond, cond);
+
+ /* If the register is now unconditionally live, remove the
+ entry in the splay_tree. */
+ if (ncond == const0_rtx)
+ {
+ rcli->condition = NULL_RTX;
+ splay_tree_remove (pbi->reg_cond_dead, regno);
+ }
+ else
+ rcli->condition = ncond;
+ }
+ }
+ else
+ {
+ /* The register was not previously live at all. Record
+ the condition under which it is still dead. */
+ rcli = (struct reg_cond_life_info *) xmalloc (sizeof (*rcli));
+ rcli->condition = not_reg_cond (cond);
+ splay_tree_insert (pbi->reg_cond_dead, regno,
+ (splay_tree_value) rcli);
+ }
+ }
+#endif
}
/* Scan expression X and store a 1-bit in NEW_LIVE for each reg it uses.
sbitmap_vector_free (tmp);
}
-/* Count for a single SET rtx, X. */
-
-static void
-count_reg_sets_1 (x, loop_depth)
- rtx x;
- int loop_depth;
-{
- register int regno;
- register rtx reg = SET_DEST (x);
-
- /* Find the register that's set/clobbered. */
- while (GET_CODE (reg) == SUBREG || GET_CODE (reg) == ZERO_EXTRACT
- || GET_CODE (reg) == SIGN_EXTRACT
- || GET_CODE (reg) == STRICT_LOW_PART)
- reg = XEXP (reg, 0);
-
- if (GET_CODE (reg) == PARALLEL
- && GET_MODE (reg) == BLKmode)
- {
- register int i;
- for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
- count_reg_sets_1 (XVECEXP (reg, 0, i), loop_depth);
- return;
- }
-
- if (GET_CODE (reg) == REG)
- {
- regno = REGNO (reg);
- if (regno >= FIRST_PSEUDO_REGISTER)
- {
- /* Count (weighted) references, stores, etc. This counts a
- register twice if it is modified, but that is correct. */
- REG_N_SETS (regno)++;
- REG_N_REFS (regno) += loop_depth + 1;
- }
- }
-}
-
-/* Increment REG_N_SETS for each SET or CLOBBER found in X; also increment
- REG_N_REFS by the current loop depth for each SET or CLOBBER found. */
-
-static void
-count_reg_sets (x, loop_depth)
- rtx x;
- int loop_depth;
-{
- register RTX_CODE code = GET_CODE (x);
-
- if (code == SET || code == CLOBBER)
- count_reg_sets_1 (x, loop_depth);
- else if (code == PARALLEL)
- {
- register int i;
- for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
- {
- code = GET_CODE (XVECEXP (x, 0, i));
- if (code == SET || code == CLOBBER)
- count_reg_sets_1 (XVECEXP (x, 0, i), loop_depth);
- }
- }
-}
-
-/* Increment REG_N_REFS by the current loop depth each register reference
- found in X. */
-
-static void
-count_reg_references (x, loop_depth)
- rtx x;
- int loop_depth;
-{
- register RTX_CODE code;
-
- retry:
- code = GET_CODE (x);
- switch (code)
- {
- case LABEL_REF:
- case SYMBOL_REF:
- case CONST_INT:
- case CONST:
- case CONST_DOUBLE:
- case PC:
- case ADDR_VEC:
- case ADDR_DIFF_VEC:
- case ASM_INPUT:
- return;
-
-#ifdef HAVE_cc0
- case CC0:
- return;
-#endif
-
- case CLOBBER:
- /* If we are clobbering a MEM, mark any registers inside the address
- as being used. */
- if (GET_CODE (XEXP (x, 0)) == MEM)
- count_reg_references (XEXP (XEXP (x, 0), 0), loop_depth);
- return;
-
- case SUBREG:
- /* 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)
- {
- count_reg_references (x, loop_depth);
- return;
- }
-
- /* ... fall through ... */
-
- case REG:
- if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
- REG_N_REFS (REGNO (x)) += loop_depth + 1;
- return;
-
- case SET:
- {
- register rtx testreg = SET_DEST (x);
- int mark_dest = 0;
-
- /* If storing into MEM, don't show it as being used. But do
- show the address as being used. */
- if (GET_CODE (testreg) == MEM)
- {
- count_reg_references (XEXP (testreg, 0), loop_depth);
- count_reg_references (SET_SRC (x), loop_depth);
- return;
- }
-
- /* Storing in STRICT_LOW_PART is like storing in a reg
- in that this SET might be dead, so ignore it in TESTREG.
- but in some other ways it is like using the reg.
-
- Storing in a SUBREG or a bit field is like storing the entire
- register in that if the register's value is not used
- then this SET is not needed. */
- while (GET_CODE (testreg) == STRICT_LOW_PART
- || GET_CODE (testreg) == ZERO_EXTRACT
- || GET_CODE (testreg) == SIGN_EXTRACT
- || GET_CODE (testreg) == SUBREG)
- {
- /* 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. */
- if (GET_CODE (testreg) == SUBREG
- && !(REG_SIZE (SUBREG_REG (testreg)) > REG_SIZE (testreg)))
- ;
- else
- mark_dest = 1;
-
- testreg = XEXP (testreg, 0);
- }
-
- /* If this is a store into a register,
- recursively scan the value being stored. */
-
- if ((GET_CODE (testreg) == PARALLEL
- && GET_MODE (testreg) == BLKmode)
- || GET_CODE (testreg) == REG)
- {
- count_reg_references (SET_SRC (x), loop_depth);
- if (mark_dest)
- count_reg_references (SET_DEST (x), loop_depth);
- return;
- }
- }
- break;
-
- default:
- break;
- }
-
- /* Recursively scan the operands of this expression. */
-
- {
- register const char *fmt = GET_RTX_FORMAT (code);
- register int i;
-
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- if (fmt[i] == 'e')
- {
- /* Tail recursive case: save a function call level. */
- if (i == 0)
- {
- x = XEXP (x, 0);
- goto retry;
- }
- count_reg_references (XEXP (x, i), loop_depth);
- }
- else if (fmt[i] == 'E')
- {
- register int j;
- for (j = 0; j < XVECLEN (x, i); j++)
- count_reg_references (XVECEXP (x, i, j), loop_depth);
- }
- }
- }
-}
-
/* Recompute register set/reference counts immediately prior to register
allocation.
rtx f ATTRIBUTE_UNUSED;
int loop_step ATTRIBUTE_UNUSED;
{
- rtx insn;
- int i, max_reg;
- int index;
- int loop_depth;
-
- /* Clear out the old data. */
- max_reg = max_reg_num ();
- for (i = FIRST_PSEUDO_REGISTER; i < max_reg; i++)
- {
- REG_N_SETS (i) = 0;
- REG_N_REFS (i) = 0;
- }
-
- /* Scan each insn in the chain and count how many times each register is
- set/used. */
- for (index = 0; index < n_basic_blocks; index++)
- {
- basic_block bb = BASIC_BLOCK (index);
- loop_depth = bb->loop_depth;
- for (insn = bb->head; insn; insn = NEXT_INSN (insn))
- {
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
- {
- rtx links;
-
- /* This call will increment REG_N_SETS for each SET or CLOBBER
- of a register in INSN. It will also increment REG_N_REFS
- by the loop depth for each set of a register in INSN. */
- count_reg_sets (PATTERN (insn), loop_depth);
-
- /* count_reg_sets does not detect autoincrement address modes, so
- detect them here by looking at the notes attached to INSN. */
- for (links = REG_NOTES (insn); links; links = XEXP (links, 1))
- {
- if (REG_NOTE_KIND (links) == REG_INC)
- /* Count (weighted) references, stores, etc. This
- counts a register twice if it is modified, but
- that is correct. */
- REG_N_SETS (REGNO (XEXP (links, 0)))++;
- }
-
- /* This call will increment REG_N_REFS by the current loop depth
- for each reference to a register in INSN. */
- count_reg_references (PATTERN (insn), loop_depth);
-
- /* count_reg_references will not include counts for arguments to
- function calls, so detect them here by examining the
- CALL_INSN_FUNCTION_USAGE data. */
- if (GET_CODE (insn) == CALL_INSN)
- {
- rtx note;
-
- for (note = CALL_INSN_FUNCTION_USAGE (insn);
- note;
- note = XEXP (note, 1))
- if (GET_CODE (XEXP (note, 0)) == USE)
- count_reg_references (XEXP (XEXP (note, 0), 0),
- loop_depth);
- }
- }
- if (insn == bb->end)
- break;
- }
- }
+ allocate_reg_life_data ();
+ update_life_info (NULL, UPDATE_LIFE_LOCAL, PROP_REG_INFO);
}
/* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of
OSDN Git Service
