#include "expr.h"
#include "obstack.h"
+#include "splay-tree.h"
#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free
varray_type reg_n_info;
-/* Size of the reg_n_info table. */
-
-unsigned int reg_n_max;
-
-/* Element N is the next insn that uses (hard or pseudo) register number N
- within the current basic block; or zero, if there is no such insn.
- This is valid only during the final backward scan in propagate_block. */
-
-static rtx *reg_next_use;
-
/* Size of a regset for the current function,
in (1) bytes and (2) elements. */
are another pair, etc. */
rtx regs_may_share;
-/* Depth within loops of basic block being scanned for lifetime analysis,
- plus one. This is the weight attached to references to registers. */
-
-static int loop_depth;
-
-/* During propagate_block, this is non-zero if the value of CC0 is live. */
-
-static int cc0_live;
-
-/* During propagate_block, this contains a list of all the MEMs we are
- tracking for dead store elimination. */
-
-static rtx mem_set_list;
-
/* Set of registers that may be eliminable. These are handled specially
in updating regs_ever_live. */
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. */
+
+struct propagate_block_info
+{
+ /* The basic block we're considering. */
+ basic_block bb;
+
+ /* Bit N is set if register N is conditionally or unconditionally live. */
+ regset reg_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. */
+ rtx *reg_next_use;
+
+ /* Contains a list of all the MEMs we are tracking for dead store
+ elimination. */
+ rtx mem_set_list;
+
+ /* 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;
+
+ /* Flags controling the set of information propagate_block collects. */
+ int flags;
+};
+
/* Forward declarations */
static int count_basic_blocks PARAMS ((rtx));
static rtx find_basic_blocks_1 PARAMS ((rtx));
static void delete_unreachable_blocks PARAMS ((void));
static void delete_eh_regions PARAMS ((void));
static int can_delete_note_p PARAMS ((rtx));
-static int delete_block PARAMS ((basic_block));
static void expunge_block PARAMS ((basic_block));
static int can_delete_label_p PARAMS ((rtx));
static int merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
basic_block));
static int merge_blocks_move_successor_nojumps PARAMS ((basic_block,
basic_block));
-static void merge_blocks_nomove PARAMS ((basic_block, basic_block));
static int merge_blocks PARAMS ((edge,basic_block,basic_block));
static void try_merge_blocks PARAMS ((void));
-static void tidy_fallthru_edge PARAMS ((edge,basic_block,basic_block));
static void tidy_fallthru_edges PARAMS ((void));
static int verify_wide_reg_1 PARAMS ((rtx *, void *));
static void verify_wide_reg PARAMS ((int, rtx, rtx));
static void notice_stack_pointer_modification PARAMS ((rtx));
static void mark_reg PARAMS ((rtx, void *));
static void mark_regs_live_at_end PARAMS ((regset));
+static int set_phi_alternative_reg PARAMS ((rtx, int, int, void *));
static void calculate_global_regs_live PARAMS ((sbitmap, sbitmap, int));
-static void propagate_block PARAMS ((basic_block, regset,
- regset, int));
-static int insn_dead_p PARAMS ((rtx, regset, int, rtx));
-static int libcall_dead_p PARAMS ((rtx, regset, rtx, rtx));
-static void mark_set_regs PARAMS ((regset, regset, rtx,
- rtx, regset, int));
-static void mark_set_1 PARAMS ((regset, regset, rtx,
- rtx, regset, int));
+static void propagate_block_delete_insn PARAMS ((basic_block, rtx));
+static rtx propagate_block_delete_libcall PARAMS ((basic_block, rtx, rtx));
+static int insn_dead_p PARAMS ((struct propagate_block_info *,
+ rtx, int, rtx));
+static int libcall_dead_p PARAMS ((struct propagate_block_info *,
+ rtx, rtx, rtx));
+static void mark_set_regs PARAMS ((struct propagate_block_info *,
+ rtx, rtx));
+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 ((regset, rtx, rtx));
-static int try_pre_increment_1 PARAMS ((rtx));
+static void find_auto_inc PARAMS ((struct propagate_block_info *,
+ rtx, rtx));
+static int try_pre_increment_1 PARAMS ((struct propagate_block_info *,
+ rtx));
static int try_pre_increment PARAMS ((rtx, rtx, HOST_WIDE_INT));
#endif
-static void mark_used_regs PARAMS ((regset, regset, rtx, int, rtx));
+static void mark_used_reg PARAMS ((struct propagate_block_info *,
+ rtx, rtx, rtx));
+static void mark_used_regs PARAMS ((struct propagate_block_info *,
+ rtx, rtx, rtx));
void dump_flow_info PARAMS ((FILE *));
void debug_flow_info PARAMS ((void));
static void dump_edge_info PARAMS ((FILE *, edge, int));
-static void count_reg_sets_1 PARAMS ((rtx));
-static void count_reg_sets PARAMS ((rtx));
-static void count_reg_references PARAMS ((rtx));
-static void invalidate_mems_from_autoinc PARAMS ((rtx));
+static void invalidate_mems_from_autoinc PARAMS ((struct propagate_block_info *,
+ rtx));
static void remove_fake_successors PARAMS ((basic_block));
static void flow_nodes_print PARAMS ((const char *, const sbitmap, FILE *));
static void flow_exits_print PARAMS ((const char *, const edge *, int, FILE *));
register int count = 0;
int eh_region = 0;
int call_had_abnormal_edge = 0;
- rtx prev_call = NULL_RTX;
prev_code = JUMP_INSN;
for (insn = f; insn; insn = NEXT_INSN (insn))
&& (prev_code == JUMP_INSN
|| prev_code == BARRIER
|| (prev_code == CALL_INSN && call_had_abnormal_edge))))
- {
- count++;
- }
+ count++;
/* Record whether this call created an edge. */
if (code == CALL_INSN)
{
rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
int region = (note ? INTVAL (XEXP (note, 0)) : 1);
- prev_call = insn;
+
call_had_abnormal_edge = 0;
/* If there is an EH region or rethrow, we have an edge. */
if ((eh_region && region > 0)
|| find_reg_note (insn, REG_EH_RETHROW, NULL_RTX))
call_had_abnormal_edge = 1;
- else
- {
- /* If there is a nonlocal goto label and the specified
- region number isn't -1, we have an edge. (0 means
- no throw, but might have a nonlocal goto). */
- if (nonlocal_goto_handler_labels && region >= 0)
- call_had_abnormal_edge = 1;
- }
+ else if (nonlocal_goto_handler_labels && region >= 0)
+ /* If there is a nonlocal goto label and the specified
+ region number isn't -1, we have an edge. (0 means
+ no throw, but might have a nonlocal goto). */
+ call_had_abnormal_edge = 1;
}
- else if (code != NOTE)
- prev_call = NULL_RTX;
if (code != NOTE)
prev_code = code;
++eh_region;
else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
--eh_region;
-
}
/* The rest of the compiler works a bit smoother when we don't have to
rtx f;
{
register rtx insn, next;
- int call_has_abnormal_edge = 0;
int i = 0;
rtx bb_note = NULL_RTX;
rtx eh_list = NULL_RTX;
next = NEXT_INSN (insn);
- if (code == CALL_INSN)
- {
- /* Record whether this call created an edge. */
- rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
- int region = (note ? INTVAL (XEXP (note, 0)) : 1);
- call_has_abnormal_edge = 0;
-
- /* If there is an EH region or rethrow, we have an edge. */
- if ((eh_list && region > 0)
- || find_reg_note (insn, REG_EH_RETHROW, NULL_RTX))
- call_has_abnormal_edge = 1;
- else
- {
- /* If there is a nonlocal goto label and the specified
- region number isn't -1, we have an edge. (0 means
- no throw, but might have a nonlocal goto). */
- if (nonlocal_goto_handler_labels && region >= 0)
- call_has_abnormal_edge = 1;
- }
- }
-
switch (code)
{
case NOTE:
else if (kind == NOTE_INSN_EH_REGION_END)
{
rtx t = eh_list;
+
eh_list = XEXP (eh_list, 1);
free_INSN_LIST_node (t);
}
{
if (bb_note == NULL_RTX)
bb_note = insn;
+
next = flow_delete_insn (insn);
}
-
break;
}
does not imply an abnormal edge, it will be a bit before
everything can be updated. So continue to emit a noop at
the end of such a block. */
- if (GET_CODE (end) == CALL_INSN
- && ! SIBLING_CALL_P (end))
+ if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
{
rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
end = emit_insn_after (nop, end);
create_basic_block (i++, head, end, bb_note);
bb_note = NULL_RTX;
}
+
head = end = insn;
break;
imply an abnormal edge, it will be a bit before everything can
be updated. So continue to emit a noop at the end of such a
block. */
- if (GET_CODE (end) == CALL_INSN
- && ! SIBLING_CALL_P (end))
+ if (GET_CODE (end) == CALL_INSN && ! SIBLING_CALL_P (end))
{
rtx nop = gen_rtx_USE (VOIDmode, const0_rtx);
end = emit_insn_after (nop, end);
goto new_bb_exclusive;
case CALL_INSN:
- /* A basic block ends at a call that can either throw or
- do a non-local goto. */
- if (call_has_abnormal_edge)
- {
- new_bb_inclusive:
- if (head == NULL_RTX)
- head = insn;
- end = insn;
+ {
+ /* Record whether this call created an edge. */
+ rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
+ int region = (note ? INTVAL (XEXP (note, 0)) : 1);
+ int call_has_abnormal_edge = 0;
+
+ /* If there is an EH region or rethrow, we have an edge. */
+ if ((eh_list && region > 0)
+ || find_reg_note (insn, REG_EH_RETHROW, NULL_RTX))
+ call_has_abnormal_edge = 1;
+ else if (nonlocal_goto_handler_labels && region >= 0)
+ /* If there is a nonlocal goto label and the specified
+ region number isn't -1, we have an edge. (0 means
+ no throw, but might have a nonlocal goto). */
+ call_has_abnormal_edge = 1;
- new_bb_exclusive:
- create_basic_block (i++, head, end, bb_note);
- head = end = NULL_RTX;
- bb_note = NULL_RTX;
- break;
+ /* A basic block ends at a call that can either throw or
+ do a non-local goto. */
+ if (call_has_abnormal_edge)
+ {
+ new_bb_inclusive:
+ if (head == NULL_RTX)
+ head = insn;
+ end = insn;
+
+ new_bb_exclusive:
+ create_basic_block (i++, head, end, bb_note);
+ head = end = NULL_RTX;
+ bb_note = NULL_RTX;
+ break;
+ }
}
/* FALLTHRU */
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_LABEL)
{
- rtx lab = XEXP (note, 0), next;
+ rtx lab = XEXP (note, 0), next;
if (lab == eh_return_stub_label)
- ;
+ ;
else if ((next = next_nonnote_insn (lab)) != NULL
&& GET_CODE (next) == JUMP_INSN
&& (GET_CODE (PATTERN (next)) == ADDR_VEC
}
/* Delete all unreachable basic blocks. Count down so that we don't
- interfere with the block renumbering that happens in delete_block. */
+ interfere with the block renumbering that happens in flow_delete_block. */
deleted_handler = 0;
/* This block was found. Tidy up the mark. */
b->aux = NULL;
else
- deleted_handler |= delete_block (b);
+ deleted_handler |= flow_delete_block (b);
}
tidy_fallthru_edges ();
/* ??? Preserving all such notes strikes me as wrong. It would be nice
to post-process the stream to remove empty blocks, loops, ranges, etc. */
-static int
-delete_block (b)
+int
+flow_delete_block (b)
basic_block b;
{
int deleted_handler = 0;
return 1;
}
+/* Blocks A and B are to be merged into a single block A. The insns
+ are already contiguous, hence `nomove'. */
+
+void
+merge_blocks_nomove (a, b)
+ basic_block a, b;
+{
+ edge e;
+ rtx b_head, b_end, a_end;
+ rtx del_first = NULL_RTX, del_last = NULL_RTX;
+ int b_empty = 0;
+
+ /* If there was a CODE_LABEL beginning B, delete it. */
+ b_head = b->head;
+ b_end = b->end;
+ if (GET_CODE (b_head) == CODE_LABEL)
+ {
+ /* Detect basic blocks with nothing but a label. This can happen
+ in particular at the end of a function. */
+ if (b_head == b_end)
+ b_empty = 1;
+ del_first = del_last = b_head;
+ b_head = NEXT_INSN (b_head);
+ }
+
+ /* Delete the basic block note. */
+ if (GET_CODE (b_head) == NOTE
+ && NOTE_LINE_NUMBER (b_head) == NOTE_INSN_BASIC_BLOCK)
+ {
+ if (b_head == b_end)
+ b_empty = 1;
+ if (! del_last)
+ del_first = b_head;
+ del_last = b_head;
+ b_head = NEXT_INSN (b_head);
+ }
+
+ /* If there was a jump out of A, delete it. */
+ a_end = a->end;
+ if (GET_CODE (a_end) == JUMP_INSN)
+ {
+ rtx prev;
+
+ prev = prev_nonnote_insn (a_end);
+ if (!prev)
+ prev = a->head;
+
+ del_first = a_end;
+
+#ifdef HAVE_cc0
+ /* If this was a conditional jump, we need to also delete
+ the insn that set cc0. */
+ if (prev && sets_cc0_p (prev))
+ {
+ rtx tmp = prev;
+ prev = prev_nonnote_insn (prev);
+ if (!prev)
+ prev = a->head;
+ del_first = tmp;
+ }
+#endif
+
+ a_end = prev;
+ }
+
+ /* Delete everything marked above as well as crap that might be
+ hanging out between the two blocks. */
+ flow_delete_insn_chain (del_first, del_last);
+
+ /* Normally there should only be one successor of A and that is B, but
+ partway though the merge of blocks for conditional_execution we'll
+ be merging a TEST block with THEN and ELSE successors. Free the
+ whole lot of them and hope the caller knows what they're doing. */
+ while (a->succ)
+ remove_edge (a->succ);
+
+ /* Adjust the edges out of B for the new owner. */
+ for (e = b->succ; e ; e = e->succ_next)
+ e->src = a;
+ a->succ = b->succ;
+
+ /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
+ b->pred = b->succ = NULL;
+
+ /* Reassociate the insns of B with A. */
+ if (!b_empty)
+ {
+ if (basic_block_for_insn)
+ {
+ BLOCK_FOR_INSN (b_head) = a;
+ while (b_head != b_end)
+ {
+ b_head = NEXT_INSN (b_head);
+ BLOCK_FOR_INSN (b_head) = a;
+ }
+ }
+ a_end = b_end;
+ }
+ a->end = a_end;
+
+ expunge_block (b);
+}
+
/* Blocks A and B are to be merged into a single block. A has no incoming
fallthru edge, so it can be moved before B without adding or modifying
any jumps (aside from the jump from A to B). */
return 1;
}
-/* Blocks A and B are to be merged into a single block. The insns
- are already contiguous, hence `nomove'. */
-
-static void
-merge_blocks_nomove (a, b)
- basic_block a, b;
-{
- edge e;
- rtx b_head, b_end, a_end;
- int b_empty = 0;
-
- /* If there was a CODE_LABEL beginning B, delete it. */
- b_head = b->head;
- b_end = b->end;
- if (GET_CODE (b_head) == CODE_LABEL)
- {
- /* Detect basic blocks with nothing but a label. This can happen
- in particular at the end of a function. */
- if (b_head == b_end)
- b_empty = 1;
- b_head = flow_delete_insn (b_head);
- }
-
- /* Delete the basic block note. */
- if (GET_CODE (b_head) == NOTE
- && NOTE_LINE_NUMBER (b_head) == NOTE_INSN_BASIC_BLOCK)
- {
- if (b_head == b_end)
- b_empty = 1;
- b_head = flow_delete_insn (b_head);
- }
-
- /* If there was a jump out of A, delete it. */
- a_end = a->end;
- if (GET_CODE (a_end) == JUMP_INSN)
- {
- rtx prev;
-
- prev = prev_nonnote_insn (a_end);
- if (!prev)
- prev = a->head;
-
-#ifdef HAVE_cc0
- /* If this was a conditional jump, we need to also delete
- the insn that set cc0. */
-
- if (prev && sets_cc0_p (prev))
- {
- rtx tmp = prev;
- prev = prev_nonnote_insn (prev);
- if (!prev)
- prev = a->head;
- flow_delete_insn (tmp);
- }
-#endif
-
- /* Note that a->head != a->end, since we should have at least a
- bb note plus the jump, so prev != insn. */
- flow_delete_insn (a_end);
- a_end = prev;
- }
-
- /* By definition, there should only be one successor of A, and that is
- B. Free that edge struct. */
- n_edges--;
- free (a->succ);
-
- /* Adjust the edges out of B for the new owner. */
- for (e = b->succ; e ; e = e->succ_next)
- e->src = a;
- a->succ = b->succ;
-
- /* Reassociate the insns of B with A. */
- if (!b_empty)
- {
- BLOCK_FOR_INSN (b_head) = a;
- while (b_head != b_end)
- {
- b_head = NEXT_INSN (b_head);
- BLOCK_FOR_INSN (b_head) = a;
- }
- a_end = b_head;
- }
- a->end = a_end;
-
- /* Compact the basic block array. */
- expunge_block (b);
-}
-
/* Attempt to merge basic blocks that are potentially non-adjacent.
Return true iff the attempt succeeded. */
/* The given edge should potentially be a fallthru edge. If that is in
fact true, delete the jump and barriers that are in the way. */
-static void
+void
tidy_fallthru_edge (e, b, c)
edge e;
basic_block b, c;
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 and NREGS the number of register numbers
- in use. */
+ F is the first insn of the function; FLAGS is a set of PROP_* flags
+ to be used in accumulating flow info. */
void
-life_analysis (f, nregs, file, remove_dead_code)
+life_analysis (f, file, flags)
rtx f;
- int nregs;
FILE *file;
- int remove_dead_code;
+ int flags;
{
#ifdef ELIMINABLE_REGS
register int i;
static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
#endif
- int flags;
- sbitmap all_blocks;
-
+
/* Record which registers will be eliminated. We use this in
mark_used_regs. */
SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
#endif
- /* We want alias analysis information for local dead store elimination. */
- init_alias_analysis ();
-
if (! optimize)
- flags = PROP_DEATH_NOTES | PROP_REG_INFO;
- else
- {
- flags = PROP_FINAL;
- if (! remove_dead_code)
- flags &= ~(PROP_SCAN_DEAD_CODE | PROP_KILL_DEAD_CODE);
- }
+ flags &= PROP_DEATH_NOTES | PROP_REG_INFO;
/* The post-reload life analysis have (on a global basis) the same
registers live as was computed by reload itself. elimination
if (reload_completed)
flags &= ~PROP_REG_INFO;
- max_regno = nregs;
+ /* We want alias analysis information for local dead store elimination. */
+ if (flags & PROP_SCAN_DEAD_CODE)
+ init_alias_analysis ();
/* Always remove no-op moves. Do this before other processing so
that we don't have to keep re-scanning them. */
data from lifetime analysis. */
allocate_reg_life_data ();
allocate_bb_life_data ();
- reg_next_use = (rtx *) xcalloc (nregs, sizeof (rtx));
- 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);
- free (reg_next_use);
- reg_next_use = NULL;
- end_alias_analysis ();
+ if (flags & PROP_SCAN_DEAD_CODE)
+ end_alias_analysis ();
if (file)
dump_flow_info (file);
}
/* 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.
generates subregs of a multi-word pseudo, current life analysis will
lose the kill. So we _can_ have a pseudo go live. How irritating.
- BLOCK_FOR_INSN is assumed to be correct.
-
- PROP_FLAGS should not contain PROP_LOG_LINKS unless the caller sets
- up reg_next_use. Including PROP_REG_INFO does not properly refresh
- regs_ever_live unless the caller resets it to zero. */
+ Including PROP_REG_INFO does not properly refresh regs_ever_live
+ unless the caller resets it to zero. */
void
update_life_info (blocks, extent, prop_flags)
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);
diddle_return_value (mark_reg, set);
}
+/* Callback function for for_each_successor_phi. DATA is a regset.
+ Sets the SRC_REGNO, the regno of the phi alternative for phi node
+ INSN, in the regset. */
+
+static int
+set_phi_alternative_reg (insn, dest_regno, src_regno, data)
+ rtx insn ATTRIBUTE_UNUSED;
+ int dest_regno ATTRIBUTE_UNUSED;
+ int src_regno;
+ void *data;
+{
+ regset live = (regset) data;
+ SET_REGNO_REG_SET (live, src_regno);
+ return 0;
+}
+
/* 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. */
+ if (in_ssa_form)
+ for_each_successor_phi (bb, &set_phi_alternative_reg,
+ new_live_at_end);
+
if (bb == ENTRY_BLOCK_PTR)
{
COPY_REG_SET (bb->global_live_at_end, new_live_at_end);
/* 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);
}
}
-/* Compute the registers live at the beginning of a basic block
- from those live at the end.
+/* Delete dead instructions for propagate_block. */
+
+static void
+propagate_block_delete_insn (bb, insn)
+ basic_block bb;
+ rtx insn;
+{
+ rtx inote = find_reg_note (insn, REG_LABEL, NULL_RTX);
+
+ /* If the insn referred to a label, and that label was attached to
+ an ADDR_VEC, it's safe to delete the ADDR_VEC. In fact, it's
+ pretty much mandatory to delete it, because the ADDR_VEC may be
+ referencing labels that no longer exist. */
+
+ if (inote)
+ {
+ rtx label = XEXP (inote, 0);
+ rtx next;
+
+ if (LABEL_NUSES (label) == 1
+ && (next = next_nonnote_insn (label)) != NULL
+ && GET_CODE (next) == JUMP_INSN
+ && (GET_CODE (PATTERN (next)) == ADDR_VEC
+ || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
+ {
+ rtx pat = PATTERN (next);
+ int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
+ int len = XVECLEN (pat, diff_vec_p);
+ int i;
- When called, OLD contains those live at the end.
- On return, it contains those live at the beginning.
- FIRST and LAST are the first and last insns of the basic block.
+ for (i = 0; i < len; i++)
+ LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
- FINAL is nonzero if we are doing the final pass which is not
- for computing the life info (since that has already been done)
- but for acting on it. On this pass, we delete dead stores,
- set up the logical links and dead-variables lists of instructions,
- and merge instructions for autoincrement and autodecrement addresses.
+ flow_delete_insn (next);
+ }
+ }
- SIGNIFICANT is nonzero only the first time for each basic block.
- If it is nonzero, it points to a regset in which we store
- a 1 for each register that is set within the block.
+ if (bb->end == insn)
+ bb->end = PREV_INSN (insn);
+ flow_delete_insn (insn);
+}
- BNUM is the number of the basic block. */
+/* Delete dead libcalls for propagate_block. Return the insn
+ before the libcall. */
-static void
-propagate_block (bb, old, significant, flags)
+static rtx
+propagate_block_delete_libcall (bb, insn, note)
basic_block bb;
- regset old;
- regset significant;
- int flags;
+ rtx insn, note;
{
- register rtx insn;
- rtx prev;
- regset live;
- regset_head live_head;
- regset dead;
- regset_head dead_head;
+ rtx first = XEXP (note, 0);
+ rtx before = PREV_INSN (first);
+
+ if (insn == bb->end)
+ bb->end = before;
+
+ flow_delete_insn_chain (first, insn);
+ return before;
+}
- /* Find the loop depth for this block. Ignore loop level changes in the
- middle of the basic block -- for register allocation purposes, the
- important uses will be in the blocks wholely contained within the loop
- not in the loop pre-header or post-trailer. */
- loop_depth = bb->loop_depth;
+/* Update the life-status of regs for one insn. Return the previous insn. */
- dead = INITIALIZE_REG_SET (live_head);
- live = INITIALIZE_REG_SET (dead_head);
+rtx
+propagate_one_insn (pbi, insn)
+ struct propagate_block_info *pbi;
+ rtx insn;
+{
+ rtx prev = PREV_INSN (insn);
+ int flags = pbi->flags;
+ int insn_is_dead = 0;
+ int libcall_is_dead = 0;
+ rtx note;
+ int i;
- cc0_live = 0;
+ if (! INSN_P (insn))
+ return prev;
- if (flags & PROP_REG_INFO)
+ note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
+ if (flags & PROP_SCAN_DEAD_CODE)
{
- register int i;
-
- /* Process the regs live at the end of the block.
- Mark them as not local to any one basic block. */
- EXECUTE_IF_SET_IN_REG_SET (old, 0, i,
- {
- REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL;
- });
+ insn_is_dead = insn_dead_p (pbi, PATTERN (insn), 0,
+ REG_NOTES (insn));
+ libcall_is_dead = (insn_is_dead && note != 0
+ && libcall_dead_p (pbi, PATTERN (insn),
+ note, insn));
}
- /* Scan the block an insn at a time from end to beginning. */
+ /* We almost certainly don't want to delete prologue or epilogue
+ instructions. Warn about probable compiler losage. */
+ if (insn_is_dead
+ && reload_completed
+ && (((HAVE_epilogue || HAVE_prologue)
+ && prologue_epilogue_contains (insn))
+ || (HAVE_sibcall_epilogue
+ && sibcall_epilogue_contains (insn))))
+ {
+ if (flags & PROP_KILL_DEAD_CODE)
+ {
+ warning ("ICE: would have deleted prologue/epilogue insn");
+ if (!inhibit_warnings)
+ debug_rtx (insn);
+ }
+ libcall_is_dead = insn_is_dead = 0;
+ }
- for (insn = bb->end; ; insn = prev)
+ /* If an instruction consists of just dead store(s) on final pass,
+ delete it. */
+ if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead)
{
- prev = PREV_INSN (insn);
+ /* 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);
- if (GET_CODE (insn) == NOTE)
+ /* 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)
{
- /* If this is a call to `setjmp' et al,
- warn if any non-volatile datum is live. */
+ prev = propagate_block_delete_libcall (pbi->bb, insn, note);
+ insn = NEXT_INSN (prev);
+ }
+ else
+ propagate_block_delete_insn (pbi->bb, insn);
+
+ return prev;
+ }
+
+ /* See if this is an increment or decrement that can be merged into
+ a following memory address. */
+#ifdef AUTO_INC_DEC
+ {
+ register rtx x = single_set (insn);
+
+ /* Does this instruction increment or decrement a register? */
+ if (!reload_completed
+ && (flags & PROP_AUTOINC)
+ && x != 0
+ && GET_CODE (SET_DEST (x)) == REG
+ && (GET_CODE (SET_SRC (x)) == PLUS
+ || GET_CODE (SET_SRC (x)) == MINUS)
+ && XEXP (SET_SRC (x), 0) == SET_DEST (x)
+ && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
+ /* Ok, look for a following memory ref we can combine with.
+ If one is found, change the memory ref to a PRE_INC
+ or PRE_DEC, cancel this insn, and return 1.
+ Return 0 if nothing has been done. */
+ && try_pre_increment_1 (pbi, insn))
+ return prev;
+ }
+#endif /* AUTO_INC_DEC */
- if ((flags & PROP_REG_INFO)
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
- IOR_REG_SET (regs_live_at_setjmp, old);
+ 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
+ library call, so that the call's arguments are not marked live. */
+ if (libcall_is_dead)
+ {
+ /* Record the death of the dest reg. */
+ mark_set_regs (pbi, PATTERN (insn), insn);
+
+ insn = XEXP (note, 0);
+ return PREV_INSN (insn);
+ }
+ else if (GET_CODE (PATTERN (insn)) == SET
+ && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
+ && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
+ && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
+ && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
+ /* We have an insn to pop a constant amount off the stack.
+ (Such insns use PLUS regardless of the direction of the stack,
+ and any insn to adjust the stack by a constant is always a pop.)
+ These insns, if not dead stores, have no effect on life. */
+ ;
+ else
+ {
+ /* Any regs live at the time of a call instruction must not go
+ in a register clobbered by calls. Find all regs now live and
+ record this for them. */
+
+ if (GET_CODE (insn) == CALL_INSN && (flags & PROP_REG_INFO))
+ EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i,
+ { REG_N_CALLS_CROSSED (i)++; });
+
+ /* 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);
+
+ if (GET_CODE (insn) == CALL_INSN)
+ {
+ register int i;
+ rtx note, cond;
+
+ cond = NULL_RTX;
+ if (GET_CODE (PATTERN (insn)) == COND_EXEC)
+ cond = COND_EXEC_TEST (PATTERN (insn));
+
+ /* Non-constant calls clobber memory. */
+ if (! CONST_CALL_P (insn))
+ free_EXPR_LIST_list (&pbi->mem_set_list);
+
+ /* There may be extra registers to be clobbered. */
+ for (note = CALL_INSN_FUNCTION_USAGE (insn);
+ note;
+ note = XEXP (note, 1))
+ if (GET_CODE (XEXP (note, 0)) == CLOBBER)
+ mark_set_1 (pbi, CLOBBER, XEXP (XEXP (note, 0), 0),
+ cond, insn, pbi->flags);
+
+ /* Calls change all call-used and global registers. */
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (call_used_regs[i] && ! global_regs[i]
+ && ! fixed_regs[i])
+ {
+ /* We do not want REG_UNUSED notes for these registers. */
+ mark_set_1 (pbi, CLOBBER, gen_rtx_REG (reg_raw_mode[i], i),
+ cond, insn, pbi->flags & ~PROP_DEATH_NOTES);
+ }
}
- /* Update the life-status of regs for this insn.
- First DEAD gets which regs are set in this insn
- then LIVE gets which regs are used in this insn.
- Then the regs live before the insn
- are those live after, with DEAD regs turned off,
- and then LIVE regs turned on. */
+ /* If an insn doesn't use CC0, it becomes dead since we assume
+ that every insn clobbers it. So show it dead here;
+ mark_used_regs will set it live if it is referenced. */
+ pbi->cc0_live = 0;
+
+ /* Record uses. */
+ if (! insn_is_dead)
+ mark_used_regs (pbi, PATTERN (insn), NULL_RTX, insn);
+
+ /* Sometimes we may have inserted something before INSN (such as a move)
+ when we make an auto-inc. So ensure we will scan those insns. */
+#ifdef AUTO_INC_DEC
+ prev = PREV_INSN (insn);
+#endif
- else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+ if (! insn_is_dead && GET_CODE (insn) == CALL_INSN)
{
register int i;
- rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
- int insn_is_dead = 0;
- int libcall_is_dead = 0;
+ rtx note, cond;
+
+ cond = NULL_RTX;
+ if (GET_CODE (PATTERN (insn)) == COND_EXEC)
+ cond = COND_EXEC_TEST (PATTERN (insn));
+
+ /* Calls use their arguments. */
+ for (note = CALL_INSN_FUNCTION_USAGE (insn);
+ note;
+ note = XEXP (note, 1))
+ if (GET_CODE (XEXP (note, 0)) == USE)
+ mark_used_regs (pbi, XEXP (XEXP (note, 0), 0),
+ cond, insn);
+
+ /* The stack ptr is used (honorarily) by a CALL insn. */
+ SET_REGNO_REG_SET (pbi->reg_live, STACK_POINTER_REGNUM);
+
+ /* 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])
+ mark_used_reg (pbi, gen_rtx_REG (reg_raw_mode[i], i),
+ cond, insn);
+ }
+ }
- if (flags & PROP_SCAN_DEAD_CODE)
- {
- insn_is_dead = insn_dead_p (PATTERN (insn), old, 0,
- REG_NOTES (insn));
- libcall_is_dead = (insn_is_dead && note != 0
- && libcall_dead_p (PATTERN (insn), old,
- note, insn));
- }
+ /* On final pass, update counts of how many insns in which each reg
+ is live. */
+ if (flags & PROP_REG_INFO)
+ EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i,
+ { REG_LIVE_LENGTH (i)++; });
- /* We almost certainly don't want to delete prologue or epilogue
- instructions. Warn about probable compiler losage. */
- if (insn_is_dead
- && reload_completed
- && (((HAVE_epilogue || HAVE_prologue)
- && prologue_epilogue_contains (insn))
- || (HAVE_sibcall_epilogue
- && sibcall_epilogue_contains (insn))))
- {
- if (flags & PROP_KILL_DEAD_CODE)
- {
- warning ("ICE: would have deleted prologue/epilogue insn");
- if (!inhibit_warnings)
- debug_rtx (insn);
- }
- libcall_is_dead = insn_is_dead = 0;
- }
+ return prev;
+}
- /* If an instruction consists of just dead store(s) on final pass,
- "delete" it by turning it into a NOTE of type NOTE_INSN_DELETED.
- We could really delete it with delete_insn, but that
- can cause trouble for first or last insn in a basic block. */
- if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead)
- {
- rtx inote;
- /* If the insn referred to a label, note that the label is
- now less used. */
- for (inote = REG_NOTES (insn); inote; inote = XEXP (inote, 1))
- {
- if (REG_NOTE_KIND (inote) == REG_LABEL)
- {
- rtx label = XEXP (inote, 0);
- rtx next;
- LABEL_NUSES (label)--;
-
- /* If this label was attached to an ADDR_VEC, it's
- safe to delete the ADDR_VEC. In fact, it's pretty
- much mandatory to delete it, because the ADDR_VEC may
- be referencing labels that no longer exist. */
- if (LABEL_NUSES (label) == 0
- && (next = next_nonnote_insn (label)) != NULL
- && GET_CODE (next) == JUMP_INSN
- && (GET_CODE (PATTERN (next)) == ADDR_VEC
- || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
- {
- rtx pat = PATTERN (next);
- int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
- int len = XVECLEN (pat, diff_vec_p);
- int i;
- for (i = 0; i < len; i++)
- LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
- PUT_CODE (next, NOTE);
- NOTE_LINE_NUMBER (next) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (next) = 0;
-
- if ((next = next_nonnote_insn (label)) != NULL
- && GET_CODE (next) == BARRIER)
- {
- PUT_CODE (next, NOTE);
- NOTE_LINE_NUMBER (next) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (next) = 0;
- }
- }
- }
- }
+/* Initialize a propagate_block_info struct for public consumption.
+ Note that the structure itself is opaque to this file, but that
+ the user can use the regsets provided here. */
- PUT_CODE (insn, NOTE);
- NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (insn) = 0;
+struct propagate_block_info *
+init_propagate_block_info (bb, live, local_set, flags)
+ basic_block bb;
+ regset live;
+ regset local_set;
+ int flags;
+{
+ struct propagate_block_info *pbi = xmalloc (sizeof(*pbi));
- /* 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. */
- cc0_live = 0;
+ pbi->bb = bb;
+ pbi->reg_live = live;
+ pbi->mem_set_list = NULL_RTX;
+ pbi->local_set = local_set;
+ pbi->cc0_live = 0;
+ pbi->flags = flags;
- /* If this insn is copying the return value from a library call,
- delete the entire library call. */
- if (libcall_is_dead)
- {
- rtx first = XEXP (note, 0);
- rtx p = insn;
- while (INSN_DELETED_P (first))
- first = NEXT_INSN (first);
- while (p != first)
- {
- p = PREV_INSN (p);
- PUT_CODE (p, NOTE);
- NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (p) = 0;
- }
- }
- goto flushed;
- }
+ if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
+ pbi->reg_next_use = (rtx *) xcalloc (max_reg_num (), sizeof (rtx));
+ else
+ pbi->reg_next_use = NULL;
+
+ 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;
- CLEAR_REG_SET (dead);
- CLEAR_REG_SET (live);
+ /* 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;
+ }
- /* See if this is an increment or decrement that can be
- merged into a following memory address. */
-#ifdef AUTO_INC_DEC
- {
- register rtx x = single_set (insn);
-
- /* Does this instruction increment or decrement a register? */
- if (!reload_completed
- && (flags & PROP_AUTOINC)
- && x != 0
- && GET_CODE (SET_DEST (x)) == REG
- && (GET_CODE (SET_SRC (x)) == PLUS
- || GET_CODE (SET_SRC (x)) == MINUS)
- && XEXP (SET_SRC (x), 0) == SET_DEST (x)
- && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
- /* Ok, look for a following memory ref we can combine with.
- If one is found, change the memory ref to a PRE_INC
- or PRE_DEC, cancel this insn, and return 1.
- Return 0 if nothing has been done. */
- && try_pre_increment_1 (insn))
- goto flushed;
- }
-#endif /* AUTO_INC_DEC */
+ /* 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);
+ });
+ }
- /* 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 library call, so that the call's
- arguments are not marked live. */
- if (libcall_is_dead)
- {
- /* Mark the dest reg as `significant'. */
- mark_set_regs (old, dead, PATTERN (insn), NULL_RTX,
- significant, flags);
+ FREE_REG_SET (diff);
+ }
+#endif
- insn = XEXP (note, 0);
- prev = PREV_INSN (insn);
- }
- else if (GET_CODE (PATTERN (insn)) == SET
- && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
- && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
- && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
- && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
- /* We have an insn to pop a constant amount off the stack.
- (Such insns use PLUS regardless of the direction of the stack,
- and any insn to adjust the stack by a constant is always a pop.)
- These insns, if not dead stores, have no effect on life. */
- ;
- else
- {
- /* Any regs live at the time of a call instruction
- must not go in a register clobbered by calls.
- Find all regs now live and record this for them. */
-
- if (GET_CODE (insn) == CALL_INSN
- && (flags & PROP_REG_INFO))
- EXECUTE_IF_SET_IN_REG_SET (old, 0, i,
- {
- REG_N_CALLS_CROSSED (i)++;
- });
-
- /* LIVE gets the regs used in INSN;
- DEAD gets those set by it. Dead insns don't make anything
- live. */
-
- mark_set_regs (old, dead, PATTERN (insn),
- insn, significant, flags);
-
- /* If an insn doesn't use CC0, it becomes dead since we
- assume that every insn clobbers it. So show it dead here;
- mark_used_regs will set it live if it is referenced. */
- cc0_live = 0;
-
- if (! insn_is_dead)
- mark_used_regs (old, live, PATTERN (insn), flags, insn);
-
- /* Sometimes we may have inserted something before INSN (such as
- a move) when we make an auto-inc. So ensure we will scan
- those insns. */
-#ifdef AUTO_INC_DEC
- prev = PREV_INSN (insn);
+ return pbi;
+}
+
+/* Release a propagate_block_info struct. */
+
+void
+free_propagate_block_info (pbi)
+ struct propagate_block_info *pbi;
+{
+ free_EXPR_LIST_list (&pbi->mem_set_list);
+
+ BITMAP_XFREE (pbi->new_set);
+
+#ifdef HAVE_conditional_execution
+ splay_tree_delete (pbi->reg_cond_dead);
+ BITMAP_XFREE (pbi->reg_cond_reg);
#endif
- if (! insn_is_dead && GET_CODE (insn) == CALL_INSN)
- {
- register int i;
-
- rtx note;
-
- for (note = CALL_INSN_FUNCTION_USAGE (insn);
- note;
- note = XEXP (note, 1))
- if (GET_CODE (XEXP (note, 0)) == USE)
- mark_used_regs (old, live, XEXP (XEXP (note, 0), 0),
- flags, insn);
-
- /* Each call clobbers all call-clobbered regs that are not
- 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]
- && ! fixed_regs[i])
- {
- SET_REGNO_REG_SET (dead, i);
- if (significant)
- SET_REGNO_REG_SET (significant, i);
- }
-
- /* The stack ptr is used (honorarily) by a CALL insn. */
- SET_REGNO_REG_SET (live, STACK_POINTER_REGNUM);
-
- /* 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])
- mark_used_regs (old, live,
- gen_rtx_REG (reg_raw_mode[i], i),
- flags, insn);
-
- /* Calls also clobber memory. */
- free_EXPR_LIST_list (&mem_set_list);
- }
+ if (pbi->reg_next_use)
+ free (pbi->reg_next_use);
- /* Update OLD for the registers used or set. */
- AND_COMPL_REG_SET (old, dead);
- IOR_REG_SET (old, live);
+ free (pbi);
+}
- }
+/* Compute the registers live at the beginning of a basic block BB from
+ those live at the end.
+
+ When called, REG_LIVE contains those live at the end. On return, it
+ contains those live at the beginning.
+
+ LOCAL_SET, if non-null, will be set with all registers killed by
+ this basic block. */
+
+void
+propagate_block (bb, live, local_set, flags)
+ basic_block bb;
+ regset live;
+ regset local_set;
+ int flags;
+{
+ struct propagate_block_info *pbi;
+ rtx insn, prev;
+
+ pbi = init_propagate_block_info (bb, live, local_set, flags);
+
+ if (flags & PROP_REG_INFO)
+ {
+ register int i;
+
+ /* Process the regs live at the end of the block.
+ Mark them as not local to any one basic block. */
+ EXECUTE_IF_SET_IN_REG_SET (live, 0, i,
+ { REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL; });
+ }
+
+ /* Scan the block an insn at a time from end to beginning. */
+
+ for (insn = bb->end; ; insn = prev)
+ {
+ /* If this is a call to `setjmp' et al, warn if any
+ non-volatile datum is live. */
+ if ((flags & PROP_REG_INFO)
+ && GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
+ IOR_REG_SET (regs_live_at_setjmp, pbi->reg_live);
+
+ prev = propagate_one_insn (pbi, insn);
- /* On final pass, update counts of how many insns in which
- each reg is live. */
- if (flags & PROP_REG_INFO)
- EXECUTE_IF_SET_IN_REG_SET (old, 0, i, { REG_LIVE_LENGTH (i)++; });
- }
- flushed:
if (insn == bb->head)
break;
}
- FREE_REG_SET (dead);
- FREE_REG_SET (live);
- free_EXPR_LIST_list (&mem_set_list);
+ free_propagate_block_info (pbi);
}
\f
/* Return 1 if X (the body of an insn, or part of it) is just dead stores
pertaining to the insn. */
static int
-insn_dead_p (x, needed, call_ok, notes)
+insn_dead_p (pbi, x, call_ok, notes)
+ struct propagate_block_info *pbi;
rtx x;
- regset needed;
int call_ok;
rtx notes ATTRIBUTE_UNUSED;
{
/* Don't delete insns to set global regs. */
if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
- || REGNO_REG_SET_P (needed, regno))
+ || REGNO_REG_SET_P (pbi->reg_live, regno))
return 0;
}
}
#ifdef HAVE_cc0
if (GET_CODE (r) == CC0)
- return ! cc0_live;
+ return ! pbi->cc0_live;
#endif
/* A SET that is a subroutine call cannot be dead. */
and see if one is an identical match to this memory location.
If so, this memory write is dead (remember, we're walking
backwards from the end of the block to the start. */
- temp = mem_set_list;
+ temp = pbi->mem_set_list;
while (temp)
{
if (rtx_equal_p (XEXP (temp, 0), r))
int regno = REGNO (r);
/* Obvious. */
- if (REGNO_REG_SET_P (needed, regno))
+ if (REGNO_REG_SET_P (pbi->reg_live, regno))
return 0;
/* If this is a hard register, verify that subsequent
int n = HARD_REGNO_NREGS (regno, GET_MODE (r));
while (--n > 0)
- if (REGNO_REG_SET_P (needed, regno+n))
+ if (REGNO_REG_SET_P (pbi->reg_live, regno+n))
return 0;
}
for (i--; i >= 0; i--)
if (GET_CODE (XVECEXP (x, 0, i)) != CLOBBER
&& GET_CODE (XVECEXP (x, 0, i)) != USE
- && ! insn_dead_p (XVECEXP (x, 0, i), needed, call_ok, NULL_RTX))
+ && ! insn_dead_p (pbi, XVECEXP (x, 0, i), call_ok, NULL_RTX))
return 0;
return 1;
is not necessarily true for hard registers. */
else if (code == CLOBBER && GET_CODE (XEXP (x, 0)) == REG
&& REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER
- && ! REGNO_REG_SET_P (needed, REGNO (XEXP (x, 0))))
+ && ! REGNO_REG_SET_P (pbi->reg_live, REGNO (XEXP (x, 0))))
return 1;
/* We do not check other CLOBBER or USE here. An insn consisting of just
NOTE is the REG_RETVAL note of the insn. INSN is the insn itself. */
static int
-libcall_dead_p (x, needed, note, insn)
+libcall_dead_p (pbi, x, note, insn)
+ struct propagate_block_info *pbi;
rtx x;
- regset needed;
rtx note;
rtx insn;
{
call_pat = XVECEXP (call_pat, 0, i);
}
- return insn_dead_p (call_pat, needed, 1, REG_NOTES (call));
+ return insn_dead_p (pbi, call_pat, 1, REG_NOTES (call));
}
}
return 1;
Find any entries on the mem_set_list that need to be invalidated due
to an address change. */
static void
-invalidate_mems_from_autoinc (insn)
+invalidate_mems_from_autoinc (pbi, insn)
+ struct propagate_block_info *pbi;
rtx insn;
{
rtx note = REG_NOTES (insn);
{
if (REG_NOTE_KIND (note) == REG_INC)
{
- rtx temp = mem_set_list;
+ rtx temp = pbi->mem_set_list;
rtx prev = NULL_RTX;
rtx next;
if (prev)
XEXP (prev, 1) = next;
else
- mem_set_list = next;
+ pbi->mem_set_list = next;
free_EXPR_LIST_node (temp);
}
else
FLAGS is the set of operations to perform. */
static void
-mark_set_regs (needed, dead, x, insn, significant, flags)
- regset needed;
- regset dead;
- rtx x;
- rtx insn;
- regset significant;
- int flags;
+mark_set_regs (pbi, x, insn)
+ struct propagate_block_info *pbi;
+ rtx x, insn;
{
- register RTX_CODE code = GET_CODE (x);
+ rtx cond = NULL_RTX;
+ enum rtx_code code;
- if (code == SET || code == CLOBBER)
- mark_set_1 (needed, dead, x, insn, significant, flags);
- else if (code == PARALLEL)
+ retry:
+ switch (code = GET_CODE (x))
{
- register int i;
- for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
- {
- code = GET_CODE (XVECEXP (x, 0, i));
- if (code == SET || code == CLOBBER)
- mark_set_1 (needed, dead, XVECEXP (x, 0, i), insn,
- significant, flags);
- }
+ case SET:
+ case CLOBBER:
+ mark_set_1 (pbi, code, SET_DEST (x), cond, insn, pbi->flags);
+ return;
+
+ case COND_EXEC:
+ cond = COND_EXEC_TEST (x);
+ x = COND_EXEC_CODE (x);
+ goto retry;
+
+ case PARALLEL:
+ {
+ register int i;
+ for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
+ {
+ rtx sub = XVECEXP (x, 0, i);
+ switch (code = GET_CODE (sub))
+ {
+ case COND_EXEC:
+ if (cond != NULL_RTX)
+ abort ();
+
+ cond = COND_EXEC_TEST (sub);
+ sub = COND_EXEC_CODE (sub);
+ if (GET_CODE (sub) != SET && GET_CODE (sub) != CLOBBER)
+ break;
+ /* FALLTHRU */
+
+ case SET:
+ case CLOBBER:
+ mark_set_1 (pbi, code, SET_DEST (sub), cond, insn, pbi->flags);
+ break;
+
+ default:
+ break;
+ }
+ }
+ break;
+ }
+
+ default:
+ break;
}
}
/* Process a single SET rtx, X. */
static void
-mark_set_1 (needed, dead, x, insn, significant, flags)
- regset needed;
- regset dead;
- rtx x;
- rtx insn;
- regset significant;
+mark_set_1 (pbi, code, reg, cond, insn, flags)
+ struct propagate_block_info *pbi;
+ enum rtx_code code;
+ rtx reg, cond, insn;
int flags;
{
- register int regno = -1;
- register rtx reg = SET_DEST (x);
+ int regno_first = -1, regno_last = -1;
+ int not_dead = 0;
+ int i;
/* Some targets place small structures in registers for
return values of functions. We have to detect this
if (GET_CODE (reg) == PARALLEL
&& GET_MODE (reg) == BLKmode)
{
- register int i;
-
for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
- mark_set_1 (needed, dead, XVECEXP (reg, 0, i), insn,
- significant, flags);
+ mark_set_1 (pbi, code, XVECEXP (reg, 0, i), cond, insn, flags);
return;
}
- /* 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.
+ /* 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. 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 */
+
+ 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));
+
+ /* Identify the range of registers affected. This is moderately
+ tricky for hard registers. See alter_subreg. */
- 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. */
+ 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 (flags & PROP_SCAN_DEAD_CODE)
{
- if (GET_CODE (reg) == MEM
- || GET_CODE (reg) == REG)
+ if (GET_CODE (reg) == MEM || GET_CODE (reg) == REG)
{
- rtx temp = mem_set_list;
+ rtx temp = pbi->mem_set_list;
rtx prev = NULL_RTX;
rtx next;
if (prev)
XEXP (prev, 1) = next;
else
- mem_set_list = next;
+ pbi->mem_set_list = next;
free_EXPR_LIST_node (temp);
}
else
address modes. Then we may need to kill some entries on the
memory set list. */
if (insn && GET_CODE (reg) == MEM)
- invalidate_mems_from_autoinc (insn);
+ invalidate_mems_from_autoinc (pbi, insn);
if (GET_CODE (reg) == MEM && ! side_effects_p (reg)
/* We do not know the size of a BLKmode store, so we do not track
everything that invalidates it. To be safe, don't eliminate any
stores though SP; none of them should be redundant anyway. */
&& ! reg_mentioned_p (stack_pointer_rtx, reg))
- mem_set_list = alloc_EXPR_LIST (0, reg, mem_set_list);
+ pbi->mem_set_list = alloc_EXPR_LIST (0, reg, pbi->mem_set_list);
}
if (GET_CODE (reg) == REG
- && (regno = REGNO (reg),
- ! (regno == 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 == HARD_FRAME_POINTER_REGNUM
+ && ! (regno_first == HARD_FRAME_POINTER_REGNUM
&& (! reload_completed || frame_pointer_needed))
#endif
#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
- && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
+ && ! (regno_first == ARG_POINTER_REGNUM && fixed_regs[regno_first])
#endif
- && ! (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]))
- /* && regno != STACK_POINTER_REGNUM) -- let's try without this. */
+ )
{
- int some_needed = REGNO_REG_SET_P (needed, regno);
- int some_not_needed = ! some_needed;
-
- /* Mark it as a significant register for this basic block. */
- if (significant)
- SET_REGNO_REG_SET (significant, regno);
+ int some_was_live = 0, some_was_dead = 0;
- /* Mark it as dead before this insn. */
- SET_REGNO_REG_SET (dead, regno);
-
- /* 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)
+ for (i = regno_first; i <= regno_last; ++i)
{
- int n;
-
- /* Nothing below is needed for the stack pointer; get out asap.
- Eg, log links aren't needed, since combine won't use them. */
- if (regno == STACK_POINTER_REGNUM)
- return;
+ 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;
+ }
- n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
- while (--n > 0)
- {
- int regno_n = regno + n;
- int needed_regno = REGNO_REG_SET_P (needed, regno_n);
- if (significant)
- SET_REGNO_REG_SET (significant, regno_n);
-
- SET_REGNO_REG_SET (dead, regno_n);
- some_needed |= needed_regno;
- some_not_needed |= ! 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))
{
register rtx y;
- register int blocknum = BLOCK_NUM (insn);
+ register int blocknum = pbi->bb->index;
y = NULL_RTX;
if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
- y = reg_next_use[regno];
-
- /* If this is a hard reg, record this function uses the reg. */
-
- if (regno < FIRST_PSEUDO_REGISTER)
{
- register int i;
- int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
-
- if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
- for (i = regno; i < endregno; i++)
- {
- /* The next use is no longer "next", since a store
- intervenes. */
- reg_next_use[i] = 0;
- }
+ y = pbi->reg_next_use[regno_first];
- if (flags & PROP_REG_INFO)
- for (i = regno; i < endregno; i++)
- {
- regs_ever_live[i] = 1;
- REG_N_SETS (i)++;
- }
+ /* The next use is no longer next, since a store intervenes. */
+ for (i = regno_first; i <= regno_last; ++i)
+ pbi->reg_next_use[i] = 0;
}
- else
- {
- /* The next use is no longer "next", since a store
- intervenes. */
- if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
- reg_next_use[regno] = 0;
-
- /* Keep track of which basic blocks each reg appears in. */
- if (flags & PROP_REG_INFO)
+ if (flags & PROP_REG_INFO)
+ {
+ for (i = regno_first; i <= regno_last; ++i)
{
- if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
- REG_BASIC_BLOCK (regno) = blocknum;
- else if (REG_BASIC_BLOCK (regno) != blocknum)
- REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
-
- /* Count (weighted) references, stores, etc. This counts a
+ /* 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;
-
+ REG_N_SETS (i) += 1;
+ REG_N_REFS (i) += (optimize_size ? 1
+ : pbi->bb->loop_depth + 1);
+
/* The insns where a reg is live are normally counted
elsewhere, but we want the count to include the insn
where the reg is set, and the normal counting mechanism
would not count it. */
- REG_LIVE_LENGTH (regno)++;
+ REG_LIVE_LENGTH (i) += 1;
+ }
+
+ /* If this is a hard reg, record this function uses the reg. */
+ if (regno_first < FIRST_PSEUDO_REGISTER)
+ {
+ for (i = regno_first; i <= regno_last; i++)
+ regs_ever_live[i] = 1;
+ }
+ else
+ {
+ /* Keep track of which basic blocks each reg appears in. */
+ if (REG_BASIC_BLOCK (regno_first) == REG_BLOCK_UNKNOWN)
+ REG_BASIC_BLOCK (regno_first) = blocknum;
+ else if (REG_BASIC_BLOCK (regno_first) != blocknum)
+ REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL;
}
}
- if (! some_not_needed)
+ if (! some_was_dead)
{
if (flags & PROP_LOG_LINKS)
{
even if reload can make what appear to be valid
assignments later. */
if (y && (BLOCK_NUM (y) == blocknum)
- && (regno >= FIRST_PSEUDO_REGISTER
+ && (regno_first >= FIRST_PSEUDO_REGISTER
|| asm_noperands (PATTERN (y)) < 0))
LOG_LINKS (y) = alloc_INSN_LIST (insn, LOG_LINKS (y));
}
}
- else if (! some_needed)
+ else if (not_dead)
+ ;
+ else if (! some_was_live)
{
if (flags & PROP_REG_INFO)
- REG_N_DEATHS (REGNO (reg))++;
+ REG_N_DEATHS (regno_first) += 1;
if (flags & PROP_DEATH_NOTES)
{
for those parts that were not needed. This case should
be rare. */
- int i;
-
- for (i = HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1;
- i >= 0; i--)
- if (!REGNO_REG_SET_P (needed, regno + i))
+ for (i = regno_first; i <= regno_last; ++i)
+ if (! REGNO_REG_SET_P (pbi->reg_live, i))
REG_NOTES (insn)
- = (alloc_EXPR_LIST
- (REG_UNUSED,
- gen_rtx_REG (reg_raw_mode[regno + i], regno + i),
- REG_NOTES (insn)));
+ = alloc_EXPR_LIST (REG_UNUSED,
+ gen_rtx_REG (reg_raw_mode[i], i),
+ REG_NOTES (insn));
}
}
}
+
+ /* Mark the register as being dead. */
+ 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)
+ CLEAR_REGNO_REG_SET (pbi->reg_live, i);
+ }
}
else if (GET_CODE (reg) == REG)
{
if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
- reg_next_use[regno] = 0;
+ pbi->reg_next_use[regno_first] = 0;
}
/* If this is the last pass and this is a SCRATCH, show it will be dying
}
}
\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
reference. */
static void
-find_auto_inc (needed, x, insn)
- regset needed;
+find_auto_inc (pbi, x, insn)
+ struct propagate_block_info *pbi;
rtx x;
rtx insn;
{
int regno = REGNO (addr);
/* Is the next use an increment that might make auto-increment? */
- if ((incr = reg_next_use[regno]) != 0
+ if ((incr = pbi->reg_next_use[regno]) != 0
&& (set = single_set (incr)) != 0
&& GET_CODE (set) == SET
&& BLOCK_NUM (incr) == BLOCK_NUM (insn)
? (offset ? PRE_INC : POST_INC)
: (offset ? PRE_DEC : POST_DEC));
- if (dead_or_set_p (incr, addr))
+ if (dead_or_set_p (incr, addr)
+ /* Mustn't autoinc an eliminable register. */
+ && (regno >= FIRST_PSEUDO_REGISTER
+ || ! TEST_HARD_REG_BIT (elim_reg_set, regno)))
{
/* This is the simple case. Try to make the auto-inc. If
we can't, we are done. Otherwise, we will do any
Change it to q = p, ...*q..., q = q+size.
Then fall into the usual case. */
rtx insns, temp;
- basic_block bb;
start_sequence ();
emit_move_insn (q, addr);
insns = get_insns ();
end_sequence ();
- bb = BLOCK_FOR_INSN (insn);
- for (temp = insns; temp; temp = NEXT_INSN (temp))
- set_block_for_insn (temp, bb);
+ if (basic_block_for_insn)
+ for (temp = insns; temp; temp = NEXT_INSN (temp))
+ set_block_for_insn (temp, pbi->bb);
/* If we can't make the auto-inc, or can't make the
replacement into Y, exit. There's no point in making
new insn(s) and do the updates. */
emit_insns_before (insns, insn);
- if (BLOCK_FOR_INSN (insn)->head == insn)
- BLOCK_FOR_INSN (insn)->head = insns;
+ if (pbi->bb->head == insn)
+ pbi->bb->head = insns;
/* INCR will become a NOTE and INSN won't contain a
use of ADDR. If a use of ADDR was just placed in
if (GET_CODE (PREV_INSN (insn)) == INSN
&& GET_CODE (PATTERN (PREV_INSN (insn))) == SET
&& SET_SRC (PATTERN (PREV_INSN (insn))) == addr)
- reg_next_use[regno] = PREV_INSN (insn);
+ pbi->reg_next_use[regno] = PREV_INSN (insn);
else
- reg_next_use[regno] = 0;
+ pbi->reg_next_use[regno] = 0;
addr = q;
regno = REGNO (q);
- /* REGNO is now used in INCR which is below INSN, but
- it previously wasn't live here. If we don't mark
- it as needed, we'll put a REG_DEAD note for it
- on this insn, which is incorrect. */
- SET_REGNO_REG_SET (needed, regno);
+ /* REGNO is now used in INCR which is below INSN, but it
+ previously wasn't live here. If we don't mark it as
+ live, we'll put a REG_DEAD note for it on this insn,
+ which is incorrect. */
+ SET_REGNO_REG_SET (pbi->reg_live, regno);
/* If there are any calls between INSN and INCR, show
that REGNO now crosses them. */
register. */
if (SET_DEST (set) == addr)
{
+ /* 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)
+ CLEAR_REGNO_REG_SET (pbi->reg_live, REGNO (XEXP (note, 0)));
+
PUT_CODE (incr, NOTE);
NOTE_LINE_NUMBER (incr) = NOTE_INSN_DELETED;
NOTE_SOURCE_FILE (incr) = 0;
/* Count an extra reference to the reg. When a reg is
incremented, spilling it is worse, so we want to make
that less likely. */
- REG_N_REFS (regno) += loop_depth + 1;
+ REG_N_REFS (regno) += pbi->bb->loop_depth + 1;
/* Count the increment as a setting of the register,
even though it isn't a SET in rtl. */
}
#endif /* AUTO_INC_DEC */
\f
-/* Scan expression X and store a 1-bit in LIVE for each reg it uses.
- This is done assuming the registers needed from X
- are those that have 1-bits in NEEDED.
+static void
+mark_used_reg (pbi, reg, cond, insn)
+ struct propagate_block_info *pbi;
+ rtx reg;
+ rtx cond ATTRIBUTE_UNUSED;
+ rtx insn;
+{
+ int regno = REGNO (reg);
+ int some_was_live = REGNO_REG_SET_P (pbi->reg_live, regno);
+ int some_was_dead = ! some_was_live;
+ 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)
+ {
+ n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ while (--n > 0)
+ {
+ int needed_regno = REGNO_REG_SET_P (pbi->reg_live, regno + n);
+ some_was_live |= needed_regno;
+ some_was_dead |= ! needed_regno;
+ }
+ }
+
+ if (pbi->flags & (PROP_LOG_LINKS | PROP_AUTOINC))
+ {
+ /* Record where each reg is used, so when the reg is set we know
+ the next insn that uses it. */
+ pbi->reg_next_use[regno] = insn;
+ }
- FLAGS is the set of enabled operations.
+ if (pbi->flags & PROP_REG_INFO)
+ {
+ if (regno < FIRST_PSEUDO_REGISTER)
+ {
+ /* If this is a register we are going to try to eliminate,
+ don't mark it live here. If we are successful in
+ eliminating it, it need not be live unless it is used for
+ pseudos, in which case it will have been set live when it
+ was allocated to the pseudos. If the register will not
+ be eliminated, reload will set it live at that point.
+
+ Otherwise, record that this function uses this register. */
+ /* ??? The PPC backend tries to "eliminate" on the pic
+ register to itself. This should be fixed. In the mean
+ time, hack around it. */
+
+ if (! (TEST_HARD_REG_BIT (elim_reg_set, regno)
+ && (regno == FRAME_POINTER_REGNUM
+ || regno == ARG_POINTER_REGNUM)))
+ {
+ int n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ do
+ regs_ever_live[regno + --n] = 1;
+ while (n > 0);
+ }
+ }
+ else
+ {
+ /* Keep track of which basic block each reg appears in. */
- INSN is the containing instruction. If INSN is dead, this function is not
- called. */
+ register int blocknum = pbi->bb->index;
+ if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
+ REG_BASIC_BLOCK (regno) = blocknum;
+ else if (REG_BASIC_BLOCK (regno) != blocknum)
+ REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
+
+ /* Count (weighted) number of uses of each reg. */
+ REG_N_REFS (regno) += pbi->bb->loop_depth + 1;
+ }
+ }
+
+ /* 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. */
+ if ((pbi->flags & (PROP_DEATH_NOTES | PROP_REG_INFO))
+ && some_was_dead
+ && some_not_set)
+ {
+ /* Check for the case where the register dying partially
+ overlaps the register set by this insn. */
+ if (regno < FIRST_PSEUDO_REGISTER
+ && HARD_REGNO_NREGS (regno, GET_MODE (reg)) > 1)
+ {
+ n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ while (--n >= 0)
+ 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)
+ {
+ 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
+ {
+ /* Don't make a REG_DEAD note for a part of a register
+ that is set in the insn. */
+
+ n = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1;
+ for (; n >= regno; 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,
+ gen_rtx_REG (reg_raw_mode[n], n),
+ 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.
+ This is done assuming the registers needed from X are those that
+ have 1-bits in PBI->REG_LIVE.
+
+ INSN is the containing instruction. If INSN is dead, this function
+ is not called. */
static void
-mark_used_regs (needed, live, x, flags, insn)
- regset needed;
- regset live;
- rtx x;
- int flags;
- rtx insn;
+mark_used_regs (pbi, x, cond, insn)
+ struct propagate_block_info *pbi;
+ rtx x, cond, insn;
{
register RTX_CODE code;
register int regno;
- int i;
+ int flags = pbi->flags;
retry:
code = GET_CODE (x);
#ifdef HAVE_cc0
case CC0:
- cc0_live = 1;
+ pbi->cc0_live = 1;
return;
#endif
/* If we are clobbering a MEM, mark any registers inside the address
as being used. */
if (GET_CODE (XEXP (x, 0)) == MEM)
- mark_used_regs (needed, live, XEXP (XEXP (x, 0), 0), flags, insn);
+ mark_used_regs (pbi, XEXP (XEXP (x, 0), 0), cond, insn);
return;
case MEM:
; /* needn't clear the memory set list */
else
{
- rtx temp = mem_set_list;
+ rtx temp = pbi->mem_set_list;
rtx prev = NULL_RTX;
rtx next;
if (prev)
XEXP (prev, 1) = next;
else
- mem_set_list = next;
+ pbi->mem_set_list = next;
free_EXPR_LIST_node (temp);
}
else
address modes. Then we may need to kill some entries on the
memory set list. */
if (insn)
- invalidate_mems_from_autoinc (insn);
+ invalidate_mems_from_autoinc (pbi, insn);
}
#ifdef AUTO_INC_DEC
if (flags & PROP_AUTOINC)
- find_auto_inc (needed, x, insn);
+ find_auto_inc (pbi, x, insn);
#endif
break;
/* 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, flags, insn);
- return;
- }
-
- /* ... fall through ... */
+ goto retry;
+ /* FALLTHRU */
case REG:
- /* See a register other than being set
- => mark it as needed. */
-
- regno = REGNO (x);
- {
- int some_needed = REGNO_REG_SET_P (needed, regno);
- int some_not_needed = ! some_needed;
-
- SET_REGNO_REG_SET (live, regno);
-
- /* 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;
-
- /* For stack ptr or fixed arg pointer,
- nothing below can be necessary, so waste no more time. */
- if (regno == STACK_POINTER_REGNUM
-#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
- || (regno == HARD_FRAME_POINTER_REGNUM
- && (! reload_completed || frame_pointer_needed))
-#endif
-#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
- || (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
-#endif
- || (regno == FRAME_POINTER_REGNUM
- && (! reload_completed || frame_pointer_needed)))
- {
- /* If this is a register we are going to try to eliminate,
- don't mark it live here. If we are successful in
- eliminating it, it need not be live unless it is used for
- pseudos, in which case it will have been set live when
- it was allocated to the pseudos. If the register will not
- be eliminated, reload will set it live at that point. */
-
- if ((flags & PROP_REG_INFO)
- && ! TEST_HARD_REG_BIT (elim_reg_set, regno))
- regs_ever_live[regno] = 1;
- return;
- }
- /* No death notes for global register variables;
- their values are live after this function exits. */
- if (global_regs[regno])
- {
- if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
- reg_next_use[regno] = insn;
- return;
- }
-
- n = HARD_REGNO_NREGS (regno, GET_MODE (x));
- while (--n > 0)
- {
- int regno_n = regno + n;
- int needed_regno = REGNO_REG_SET_P (needed, regno_n);
-
- SET_REGNO_REG_SET (live, regno_n);
- some_needed |= needed_regno;
- some_not_needed |= ! needed_regno;
- }
- }
-
- if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
- {
- /* Record where each reg is used, so when the reg
- is set we know the next insn that uses it. */
-
- reg_next_use[regno] = insn;
- }
- if (flags & PROP_REG_INFO)
- {
- if (regno < FIRST_PSEUDO_REGISTER)
- {
- /* If a hard reg is being used,
- record that this function does use it. */
-
- i = HARD_REGNO_NREGS (regno, GET_MODE (x));
- if (i == 0)
- i = 1;
- do
- regs_ever_live[regno + --i] = 1;
- while (i > 0);
- }
- else
- {
- /* Keep track of which basic block each reg appears in. */
-
- register int blocknum = BLOCK_NUM (insn);
-
- if (REG_BASIC_BLOCK (regno) == REG_BLOCK_UNKNOWN)
- REG_BASIC_BLOCK (regno) = blocknum;
- else if (REG_BASIC_BLOCK (regno) != blocknum)
- REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
-
- /* Count (weighted) number of uses of each reg. */
-
- REG_N_REFS (regno) += loop_depth + 1;
- }
- }
-
- /* 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. */
-
- if (flags & PROP_DEATH_NOTES)
- {
- if (some_not_needed
- && ! dead_or_set_p (insn, x)
-#if 0
- && (regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
-#endif
- )
- {
- /* Check for the case where the register dying partially
- overlaps the register set by this insn. */
- if (regno < FIRST_PSEUDO_REGISTER
- && HARD_REGNO_NREGS (regno, GET_MODE (x)) > 1)
- {
- int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
- while (--n >= 0)
- some_needed |= dead_or_set_regno_p (insn, 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_needed)
- {
- REG_NOTES (insn)
- = alloc_EXPR_LIST (REG_DEAD, x, REG_NOTES (insn));
- REG_N_DEATHS (regno)++;
- }
- else
- {
- int i;
-
- /* Don't make a REG_DEAD note for a part of a register
- that is set in the insn. */
-
- for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1;
- i >= 0; i--)
- if (!REGNO_REG_SET_P (needed, regno + i)
- && ! dead_or_set_regno_p (insn, regno + i))
- REG_NOTES (insn)
- = (alloc_EXPR_LIST
- (REG_DEAD, gen_rtx_REG (reg_raw_mode[regno + i],
- regno + i),
- REG_NOTES (insn)));
- }
- }
- }
- }
+ /* See a register other than being set => mark it as needed. */
+ mark_used_reg (pbi, x, cond, insn);
return;
case SET:
{
#ifdef AUTO_INC_DEC
if (flags & PROP_AUTOINC)
- find_auto_inc (needed, testreg, insn);
+ find_auto_inc (pbi, testreg, insn);
#endif
- mark_used_regs (needed, live, XEXP (testreg, 0), flags, insn);
- mark_used_regs (needed, live, SET_SRC (x), flags, insn);
+ mark_used_regs (pbi, XEXP (testreg, 0), cond, insn);
+ mark_used_regs (pbi, SET_SRC (x), cond, insn);
return;
}
testreg = XEXP (testreg, 0);
}
- /* If this is a store into a register,
- recursively scan the value being stored. */
+ /* 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
- && (regno = REGNO (testreg), ! (regno == FRAME_POINTER_REGNUM
- && (! reload_completed || frame_pointer_needed)))
+ && (regno = REGNO (testreg),
+ ! (regno == FRAME_POINTER_REGNUM
+ && (! reload_completed || frame_pointer_needed)))
#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
&& ! (regno == HARD_FRAME_POINTER_REGNUM
&& (! reload_completed || frame_pointer_needed))
&& ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
#endif
))
- /* We used to exclude global_regs here, but that seems wrong.
- Storing in them is like storing in mem. */
{
- mark_used_regs (needed, live, SET_SRC (x), flags, insn);
if (mark_dest)
- mark_used_regs (needed, live, SET_DEST (x), flags, insn);
+ mark_used_regs (pbi, SET_DEST (x), cond, insn);
+ mark_used_regs (pbi, SET_SRC (x), cond, insn);
return;
}
}
So for now, just clear the memory set list and mark any regs
we can find in ASM_OPERANDS as used. */
if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
- free_EXPR_LIST_list (&mem_set_list);
+ free_EXPR_LIST_list (&pbi->mem_set_list);
/* For all ASM_OPERANDS, we must traverse the vector of input operands.
We can not just fall through here since then we would be confused
int j;
for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
- mark_used_regs (needed, live, ASM_OPERANDS_INPUT (x, j),
- flags, insn);
+ mark_used_regs (pbi, ASM_OPERANDS_INPUT (x, j), cond, insn);
}
break;
}
+ case COND_EXEC:
+ if (cond != NULL_RTX)
+ abort ();
+
+ mark_used_regs (pbi, COND_EXEC_TEST (x), NULL_RTX, insn);
+
+ cond = COND_EXEC_TEST (x);
+ x = COND_EXEC_CODE (x);
+ goto retry;
+
+ case PHI:
+ /* We _do_not_ want to scan operands of phi nodes. Operands of
+ a phi function are evaluated only when control reaches this
+ block along a particular edge. Therefore, regs that appear
+ as arguments to phi should not be added to the global live at
+ start. */
+ return;
default:
break;
x = XEXP (x, 0);
goto retry;
}
- mark_used_regs (needed, live, XEXP (x, i), flags, insn);
+ mark_used_regs (pbi, XEXP (x, i), cond, insn);
}
else if (fmt[i] == 'E')
{
register int j;
for (j = 0; j < XVECLEN (x, i); j++)
- mark_used_regs (needed, live, XVECEXP (x, i, j), flags, insn);
+ mark_used_regs (pbi, XVECEXP (x, i, j), cond, insn);
}
}
}
#ifdef AUTO_INC_DEC
static int
-try_pre_increment_1 (insn)
+try_pre_increment_1 (pbi, insn)
+ struct propagate_block_info *pbi;
rtx insn;
{
/* Find the next use of this reg. If in same basic block,
HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
* INTVAL (XEXP (SET_SRC (x), 1)));
int regno = REGNO (SET_DEST (x));
- rtx y = reg_next_use[regno];
+ rtx y = pbi->reg_next_use[regno];
if (y != 0
&& BLOCK_NUM (y) == BLOCK_NUM (insn)
/* Don't do this if the reg dies, or gets set in y; a standard addressing
less likely. */
if (regno >= FIRST_PSEUDO_REGISTER)
{
- REG_N_REFS (regno) += loop_depth + 1;
+ REG_N_REFS (regno) += pbi->bb->loop_depth + 1;
REG_N_SETS (regno)++;
}
return 1;
edge e;
fprintf (outf, ";; Basic block %d, loop depth %d",
- bb->index, bb->loop_depth - 1);
+ bb->index, bb->loop_depth);
if (bb->eh_beg != -1 || bb->eh_end != -1)
fprintf (outf, ", eh regions %d/%d", bb->eh_beg, bb->eh_end);
putc ('\n', outf);
did_output = print_rtl_single (outf, tmp_rtx);
if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
- fprintf (outf, ";; End of basic block %d\n", bb->index);
+ {
+ fprintf (outf, ";; End of basic block %d, registers live:\n",
+ bb->index);
+ dump_regset (bb->global_live_at_end, outf);
+ putc ('\n', outf);
+ }
if (did_output)
putc ('\n', outf);
int bb;
sbitmap *temp_bitmap;
edge e;
- basic_block *worklist, *tos;
+ basic_block *worklist, *workend, *qin, *qout;
+ int qlen;
/* Allocate a worklist array/queue. Entries are only added to the
list if they were not already on the list. So the size is
bounded by the number of basic blocks. */
- tos = worklist = (basic_block *) xmalloc (sizeof (basic_block)
- * n_basic_blocks);
+ worklist = (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
+ workend = &worklist[n_basic_blocks];
temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
{
/* The optimistic setting of dominators requires us to put every
block on the work list initially. */
+ qin = qout = worklist;
for (bb = 0; bb < n_basic_blocks; bb++)
{
- *tos++ = BASIC_BLOCK (bb);
+ *qin++ = BASIC_BLOCK (bb);
BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
}
+ qlen = n_basic_blocks;
+ qin = worklist;
/* We want a maximal solution, so initially assume everything dominates
everything else. */
e->dest->aux = ENTRY_BLOCK_PTR;
/* Iterate until the worklist is empty. */
- while (tos != worklist)
+ while (qlen)
{
/* Take the first entry off the worklist. */
- basic_block b = *--tos;
+ basic_block b = *qout++;
+ if (qout >= workend)
+ qout = worklist;
+ qlen--;
+
bb = b->index;
/* Compute the intersection of the dominators of all the
{
if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
{
- *tos++ = e->dest;
+ *qin++ = e->dest;
+ if (qin >= workend)
+ qin = worklist;
+ qlen++;
+
e->dest->aux = e;
}
}
{
/* The optimistic setting of dominators requires us to put every
block on the work list initially. */
+ qin = qout = worklist;
for (bb = 0; bb < n_basic_blocks; bb++)
{
- *tos++ = BASIC_BLOCK (bb);
+ *qin++ = BASIC_BLOCK (bb);
BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
}
+ qlen = n_basic_blocks;
+ qin = worklist;
/* We want a maximal solution, so initially assume everything post
dominates everything else. */
e->src->aux = EXIT_BLOCK_PTR;
/* Iterate until the worklist is empty. */
- while (tos != worklist)
+ while (qlen)
{
/* Take the first entry off the worklist. */
- basic_block b = *--tos;
+ basic_block b = *qout++;
+ if (qout >= workend)
+ qout = worklist;
+ qlen--;
+
bb = b->index;
/* Compute the intersection of the post dominators of all the
{
if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
{
- *tos++ = e->src;
+ *qin++ = e->src;
+ if (qin >= workend)
+ qin = worklist;
+ qlen++;
+
e->src->aux = e;
}
}
}
}
}
+
+ free (worklist);
free (temp_bitmap);
}
sbitmap_vector_free (tmp);
}
-/* Count for a single SET rtx, X. */
-
-static void
-count_reg_sets_1 (x)
- rtx x;
-{
- 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));
- 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)
- rtx x;
-{
- register RTX_CODE code = GET_CODE (x);
-
- if (code == SET || code == CLOBBER)
- count_reg_sets_1 (x);
- 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));
- }
- }
-}
-
-/* Increment REG_N_REFS by the current loop depth each register reference
- found in X. */
-
-static void
-count_reg_references (x)
- rtx x;
-{
- 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));
- 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);
- 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));
- count_reg_references (SET_SRC (x));
- 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));
- if (mark_dest)
- count_reg_references (SET_DEST (x));
- 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));
- }
- else if (fmt[i] == 'E')
- {
- register int j;
- for (j = 0; j < XVECLEN (x, i); j++)
- count_reg_references (XVECEXP (x, i, j));
- }
- }
- }
-}
-
/* 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;
-
- /* 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));
-
- /* 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));
-
- /* 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));
- }
- }
- 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
