/* Data flow analysis for GNU compiler.
Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000 Free Software Foundation, Inc.
+ 1999, 2000, 2001 Free Software Foundation, Inc.
This file is part of GNU CC.
#define EPILOGUE_USES(REGNO) 0
#endif
-/* The contents of the current function definition are allocated
- in this obstack, and all are freed at the end of the function.
- For top-level functions, this is temporary_obstack.
- Separate obstacks are made for nested functions. */
+/* The obstack on which the flow graph components are allocated. */
-extern struct obstack *function_obstack;
+struct obstack flow_obstack;
+static char *flow_firstobj;
/* Number of basic blocks in the current function. */
NULL, /* pred */
NULL, /* succ */
NULL, /* local_set */
+ NULL, /* cond_local_set */
NULL, /* global_live_at_start */
NULL, /* global_live_at_end */
NULL, /* aux */
NULL, /* pred */
NULL, /* succ */
NULL, /* local_set */
+ NULL, /* cond_local_set */
NULL, /* global_live_at_start */
NULL, /* global_live_at_end */
NULL, /* aux */
are another pair, etc. */
rtx regs_may_share;
+/* Callback that determines if it's ok for a function to have no
+ noreturn attribute. */
+int (*lang_missing_noreturn_ok_p) PARAMS ((tree));
+
/* Set of registers that may be eliminable. These are handled specially
in updating regs_ever_live. */
elimination. */
rtx mem_set_list;
- /* If non-null, record the set of registers set in the basic block. */
+ /* If non-null, record the set of registers set unconditionally in the
+ basic block. */
regset local_set;
+ /* If non-null, record the set of registers set conditionally in the
+ basic block. */
+ regset cond_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. */
regset reg_cond_reg;
#endif
+ /* The length of mem_set_list. */
+ int mem_set_list_len;
+
/* Non-zero if the value of CC0 is live. */
int cc0_live;
int flags;
};
+/* Maximum length of pbi->mem_set_list before we start dropping
+ new elements on the floor. */
+#define MAX_MEM_SET_LIST_LEN 100
+
/* Store the data structures necessary for depth-first search. */
struct depth_first_search_dsS {
/* stack for backtracking during the algorithm */
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 elim_reg_cond PARAMS ((rtx, unsigned int));
+static rtx ior_reg_cond PARAMS ((rtx, rtx, int));
static rtx not_reg_cond PARAMS ((rtx));
-static rtx nand_reg_cond PARAMS ((rtx, rtx));
+static rtx and_reg_cond PARAMS ((rtx, rtx, int));
#endif
#ifdef AUTO_INC_DEC
static void attempt_auto_inc PARAMS ((struct propagate_block_info *,
void dump_flow_info PARAMS ((FILE *));
void debug_flow_info PARAMS ((void));
static void dump_edge_info PARAMS ((FILE *, edge, int));
+static void print_rtl_and_abort PARAMS ((void));
static void invalidate_mems_from_autoinc PARAMS ((struct propagate_block_info *,
rtx));
+static void invalidate_mems_from_set PARAMS ((struct propagate_block_info *,
+ rtx));
static void remove_fake_successors PARAMS ((basic_block));
-static void flow_nodes_print PARAMS ((const char *, const sbitmap,
+static void flow_nodes_print PARAMS ((const char *, const sbitmap,
FILE *));
static void flow_edge_list_print PARAMS ((const char *, const edge *,
int, FILE *));
static void flow_loops_cfg_dump PARAMS ((const struct loops *,
FILE *));
-static int flow_loop_nested_p PARAMS ((struct loop *,
+static int flow_loop_nested_p PARAMS ((struct loop *,
struct loop *));
-static int flow_loop_entry_edges_find PARAMS ((basic_block, const sbitmap,
+static int flow_loop_entry_edges_find PARAMS ((basic_block, const sbitmap,
edge **));
static int flow_loop_exit_edges_find PARAMS ((const sbitmap, edge **));
static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap));
PARAMS ((depth_first_search_ds));
static void flow_dfs_compute_reverse_finish
PARAMS ((depth_first_search_ds));
-static basic_block flow_loop_pre_header_find PARAMS ((basic_block, const sbitmap *));
+static void flow_loop_pre_header_scan PARAMS ((struct loop *));
+static basic_block flow_loop_pre_header_find PARAMS ((basic_block,
+ const sbitmap *));
static void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *));
static void flow_loops_tree_build PARAMS ((struct loops *));
static int flow_loop_level_compute PARAMS ((struct loop *, int));
static int flow_loops_level_compute PARAMS ((struct loops *));
+static void allocate_bb_life_data PARAMS ((void));
\f
/* Find basic blocks of the current function.
F is the first insn of the function and NREGS the number of register
#endif
}
+void
+check_function_return_warnings ()
+{
+ if (warn_missing_noreturn
+ && !TREE_THIS_VOLATILE (cfun->decl)
+ && EXIT_BLOCK_PTR->pred == NULL
+ && (lang_missing_noreturn_ok_p
+ && !lang_missing_noreturn_ok_p (cfun->decl)))
+ warning ("function might be possible candidate for attribute `noreturn'");
+
+ /* If we have a path to EXIT, then we do return. */
+ if (TREE_THIS_VOLATILE (cfun->decl)
+ && EXIT_BLOCK_PTR->pred != NULL)
+ warning ("`noreturn' function does return");
+
+ /* If the clobber_return_insn appears in some basic block, then we
+ do reach the end without returning a value. */
+ else if (warn_return_type
+ && cfun->x_clobber_return_insn != NULL
+ && EXIT_BLOCK_PTR->pred != NULL)
+ {
+ int max_uid = get_max_uid ();
+
+ /* If clobber_return_insn was excised by jump1, then renumber_insns
+ can make max_uid smaller than the number still recorded in our rtx.
+ That's fine, since this is a quick way of verifying that the insn
+ is no longer in the chain. */
+ if (INSN_UID (cfun->x_clobber_return_insn) < max_uid)
+ {
+ /* Recompute insn->block mapping, since the initial mapping is
+ set before we delete unreachable blocks. */
+ compute_bb_for_insn (max_uid);
+
+ if (BLOCK_FOR_INSN (cfun->x_clobber_return_insn) != NULL)
+ warning ("control reaches end of non-void function");
+ }
+ }
+}
+
/* Count the basic blocks of the function. */
static int
rtx insn;
for (insn = f; insn; insn = NEXT_INSN (insn))
- if (INSN_P (insn))
+ if (INSN_P (insn) && GET_CODE (insn) != JUMP_INSN)
{
rtx note;
as this would be a part of the tablejump setup code.
Make a special exception for the eh_return_stub_label, which
- we know isn't part of any otherwise visible control flow. */
+ we know isn't part of any otherwise visible control flow.
+
+ Make a special exception to registers loaded with label
+ values just before jump insns that use them. */
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_LABEL)
;
else if (GET_CODE (lab) == NOTE)
;
+ else if (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
+ && find_reg_note (NEXT_INSN (insn), REG_LABEL, lab))
+ ;
else
lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
}
break;
}
- if (GET_RTX_CLASS (code) == 'i')
+ if (GET_RTX_CLASS (code) == 'i'
+ && GET_CODE (insn) != JUMP_INSN)
{
rtx note;
- /* Make a list of all labels referred to other than by jumps
- (which just don't have the REG_LABEL notes).
+ /* Make a list of all labels referred to other than by jumps.
Make a special exception for labels followed by an ADDR*VEC,
as this would be a part of the tablejump setup code.
Make a special exception for the eh_return_stub_label, which
- we know isn't part of any otherwise visible control flow. */
+ we know isn't part of any otherwise visible control flow.
+
+ Make a special exception to registers loaded with label
+ values just before jump insns that use them. */
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_LABEL)
;
else if (GET_CODE (lab) == NOTE)
;
+ else if (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
+ && find_reg_note (NEXT_INSN (insn), REG_LABEL, lab))
+ ;
else
lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
}
the same lifetime by allocating it off the function obstack
rather than using malloc. */
- bb = (basic_block) obstack_alloc (function_obstack, sizeof (*bb));
+ bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*bb));
memset (bb, 0, sizeof (*bb));
if (GET_CODE (head) == CODE_LABEL)
{
rtx tmp;
+ /* Recognize a non-local goto as a branch outside the
+ current function. */
+ if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
+ ;
+
/* ??? Recognize a tablejump and do the right thing. */
- if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
- && (tmp = NEXT_INSN (tmp)) != NULL_RTX
- && GET_CODE (tmp) == JUMP_INSN
- && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
- || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
+ else if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
+ && (tmp = NEXT_INSN (tmp)) != NULL_RTX
+ && GET_CODE (tmp) == JUMP_INSN
+ && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
+ || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
{
rtvec vec;
int j;
if (code == CALL_INSN && SIBLING_CALL_P (insn))
make_edge (edge_cache, bb, EXIT_BLOCK_PTR,
EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
- else
/* If this is a CALL_INSN, then mark it as reaching the active EH
handler for this CALL_INSN. If we're handling asynchronous
Also mark the CALL_INSN as reaching any nonlocal goto handler. */
- if (code == CALL_INSN || asynchronous_exceptions)
+ else if (code == CALL_INSN || asynchronous_exceptions)
{
/* Add any appropriate EH edges. We do this unconditionally
since there may be a REG_EH_REGION or REG_EH_RETHROW note
&& dst != EXIT_BLOCK_PTR);
/* Make sure we don't add duplicate edges. */
- if (! use_edge_cache || TEST_BIT (edge_cache[src->index], dst->index))
- for (e = src->succ; e; e = e->succ_next)
- if (e->dest == dst)
- {
- e->flags |= flags;
- return;
- }
+ switch (use_edge_cache)
+ {
+ default:
+ /* Quick test for non-existance of the edge. */
+ if (! TEST_BIT (edge_cache[src->index], dst->index))
+ break;
+
+ /* The edge exists; early exit if no work to do. */
+ if (flags == 0)
+ return;
+
+ /* FALLTHRU */
+ case 0:
+ for (e = src->succ; e; e = e->succ_next)
+ if (e->dest == dst)
+ {
+ e->flags |= flags;
+ return;
+ }
+ break;
+ }
e = (edge) xcalloc (1, sizeof (*e));
n_edges++;
}
}
\f
+/* Split a block BB after insn INSN creating a new fallthru edge.
+ Return the new edge. Note that to keep other parts of the compiler happy,
+ this function renumbers all the basic blocks so that the new
+ one has a number one greater than the block split. */
+
+edge
+split_block (bb, insn)
+ basic_block bb;
+ rtx insn;
+{
+ basic_block new_bb;
+ edge new_edge;
+ edge e;
+ rtx bb_note;
+ int i, j;
+
+ /* There is no point splitting the block after its end. */
+ if (bb->end == insn)
+ return 0;
+
+ /* Create the new structures. */
+ new_bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*new_bb));
+ new_edge = (edge) xcalloc (1, sizeof (*new_edge));
+ n_edges++;
+
+ memset (new_bb, 0, sizeof (*new_bb));
+
+ new_bb->head = NEXT_INSN (insn);
+ new_bb->end = bb->end;
+ bb->end = insn;
+
+ new_bb->succ = bb->succ;
+ bb->succ = new_edge;
+ new_bb->pred = new_edge;
+ new_bb->count = bb->count;
+ new_bb->loop_depth = bb->loop_depth;
+
+ new_edge->src = bb;
+ new_edge->dest = new_bb;
+ new_edge->flags = EDGE_FALLTHRU;
+ new_edge->probability = REG_BR_PROB_BASE;
+ new_edge->count = bb->count;
+
+ /* Redirect the src of the successor edges of bb to point to new_bb. */
+ for (e = new_bb->succ; e; e = e->succ_next)
+ e->src = new_bb;
+
+ /* Place the new block just after the block being split. */
+ VARRAY_GROW (basic_block_info, ++n_basic_blocks);
+
+ /* Some parts of the compiler expect blocks to be number in
+ sequential order so insert the new block immediately after the
+ block being split.. */
+ j = bb->index;
+ for (i = n_basic_blocks - 1; i > j + 1; --i)
+ {
+ basic_block tmp = BASIC_BLOCK (i - 1);
+ BASIC_BLOCK (i) = tmp;
+ tmp->index = i;
+ }
+
+ BASIC_BLOCK (i) = new_bb;
+ new_bb->index = i;
+
+ /* Create the basic block note. */
+ bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK,
+ new_bb->head);
+ NOTE_BASIC_BLOCK (bb_note) = new_bb;
+ new_bb->head = bb_note;
+
+ update_bb_for_insn (new_bb);
+
+ if (bb->global_live_at_start)
+ {
+ new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+ new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+ COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
+
+ /* We now have to calculate which registers are live at the end
+ of the split basic block and at the start of the new basic
+ block. Start with those registers that are known to be live
+ at the end of the original basic block and get
+ propagate_block to determine which registers are live. */
+ COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_end);
+ propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0);
+ COPY_REG_SET (bb->global_live_at_end,
+ new_bb->global_live_at_start);
+ }
+
+ return new_edge;
+}
+
+
/* Split a (typically critical) edge. Return the new block.
Abort on abnormal edges.
}
/* Create the new structures. */
- bb = (basic_block) obstack_alloc (function_obstack, sizeof (*bb));
+ bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*bb));
edge_out = (edge) xcalloc (1, sizeof (*edge_out));
n_edges++;
/* ??? This info is likely going to be out of date very soon. */
if (old_succ->global_live_at_start)
{
- bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (function_obstack);
- bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_obstack);
+ bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+ bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
COPY_REG_SET (bb->global_live_at_start, old_succ->global_live_at_start);
COPY_REG_SET (bb->global_live_at_end, old_succ->global_live_at_start);
}
bb = BASIC_BLOCK (i);
}
}
+
+/* Add fake edges to the function exit for any non constant calls in
+ the bitmap of blocks specified by BLOCKS or to the whole CFG if
+ BLOCKS is zero. Return the nuber of blocks that were split. */
+
+int
+flow_call_edges_add (blocks)
+ sbitmap blocks;
+{
+ int i;
+ int blocks_split = 0;
+ int bb_num = 0;
+ basic_block *bbs;
+
+ /* Map bb indicies into basic block pointers since split_block
+ will renumber the basic blocks. */
+
+ bbs = xmalloc (n_basic_blocks * sizeof (*bbs));
+
+ if (! blocks)
+ {
+ for (i = 0; i < n_basic_blocks; i++)
+ bbs[bb_num++] = BASIC_BLOCK (i);
+ }
+ else
+ {
+ EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
+ {
+ bbs[bb_num++] = BASIC_BLOCK (i);
+ });
+ }
+
+
+ /* Now add fake edges to the function exit for any non constant
+ calls since there is no way that we can determine if they will
+ return or not... */
+
+ for (i = 0; i < bb_num; i++)
+ {
+ basic_block bb = bbs[i];
+ rtx insn;
+ rtx prev_insn;
+
+ for (insn = bb->end; ; insn = prev_insn)
+ {
+ prev_insn = PREV_INSN (insn);
+ if (GET_CODE (insn) == CALL_INSN && ! CONST_CALL_P (insn))
+ {
+ edge e;
+
+ /* Note that the following may create a new basic block
+ and renumber the existing basic blocks. */
+ e = split_block (bb, insn);
+ if (e)
+ blocks_split++;
+
+ make_edge (NULL, bb, EXIT_BLOCK_PTR, EDGE_FAKE);
+ }
+ if (insn == bb->head)
+ break;
+ }
+ }
+
+ if (blocks_split)
+ verify_flow_info ();
+
+ free (bbs);
+ return blocks_split;
+}
\f
/* Delete all unreachable basic blocks. */
NOTE_SOURCE_FILE (q) = 0;
}
else
- q = PREV_INSN (q);
+ {
+ q = PREV_INSN (q);
+
+ /* We don't want a block to end on a line-number note since that has
+ the potential of changing the code between -g and not -g. */
+ while (GET_CODE (q) == NOTE && NOTE_LINE_NUMBER (q) >= 0)
+ q = PREV_INSN (q);
+ }
b->end = q;
}
}
/* We didn't find the register at all. Something's way screwy. */
- abort ();
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Aborting in verify_wide_reg; reg %d\n", regno);
+ print_rtl_and_abort ();
}
/* A subroutine of update_life_info. Verify that there are no untoward
/* After reload, there are no pseudos, nor subregs of multi-word
registers. The regsets should exactly match. */
if (! REG_SET_EQUAL_P (new_live_at_start, bb->global_live_at_start))
- abort ();
+ {
+ if (rtl_dump_file)
+ {
+ fprintf (rtl_dump_file,
+ "live_at_start mismatch in bb %d, aborting\n",
+ bb->index);
+ debug_bitmap_file (rtl_dump_file, bb->global_live_at_start);
+ debug_bitmap_file (rtl_dump_file, new_live_at_start);
+ }
+ print_rtl_and_abort ();
+ }
}
else
{
{
/* No registers should die. */
if (REGNO_REG_SET_P (bb->global_live_at_start, i))
- abort ();
+ {
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file,
+ "Register %d died unexpectedly in block %d\n", i,
+ bb->index);
+ print_rtl_and_abort ();
+ }
+
/* Verify that the now-live register is wider than word_mode. */
verify_wide_reg (i, bb->head, bb->end);
});
basic_block bb = BASIC_BLOCK (i);
COPY_REG_SET (tmp, bb->global_live_at_end);
- propagate_block (bb, tmp, (regset) NULL, prop_flags);
+ propagate_block (bb, tmp, NULL, NULL, prop_flags);
if (extent == UPDATE_LIFE_LOCAL)
verify_local_live_at_start (tmp, bb);
basic_block bb = BASIC_BLOCK (i);
COPY_REG_SET (tmp, bb->global_live_at_end);
- propagate_block (bb, tmp, (regset) NULL, prop_flags);
+ propagate_block (bb, tmp, NULL, NULL, prop_flags);
if (extent == UPDATE_LIFE_LOCAL)
verify_local_live_at_start (tmp, bb);
of a push until later in flow. See the comments in rtl.texi
regarding Embedded Side-Effects on Addresses. */
|| (GET_CODE (x) == MEM
- && (GET_CODE (XEXP (x, 0)) == PRE_DEC
- || GET_CODE (XEXP (x, 0)) == PRE_INC
- || GET_CODE (XEXP (x, 0)) == POST_DEC
- || GET_CODE (XEXP (x, 0)) == POST_INC)
+ && GET_RTX_CLASS (GET_CODE (XEXP (x, 0))) == 'a'
&& XEXP (XEXP (x, 0), 0) == stack_pointer_rtx))
current_function_sp_is_unchanging = 0;
}
#endif
}
-#ifdef PIC_OFFSET_TABLE_REGNUM
#ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
/* Many architectures have a GP register even without flag_pic.
Assume the pic register is not in use, or will be handled by
other means, if it is not fixed. */
- if (fixed_regs[PIC_OFFSET_TABLE_REGNUM])
+ if (PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
+ && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
SET_REGNO_REG_SET (set, PIC_OFFSET_TABLE_REGNUM);
#endif
-#endif
/* Mark all global registers, and all registers used by the epilogue
as being live at the end of the function since they may be
qtail = queue;
qhead = qend = queue + n_basic_blocks + 2;
- /* Clear out the garbage that might be hanging out in bb->aux. */
- for (i = n_basic_blocks - 1; i >= 0; --i)
- BASIC_BLOCK (i)->aux = NULL;
-
/* 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. */
if (blocks_in)
{
+ /* Clear out the garbage that might be hanging out in bb->aux. */
+ for (i = n_basic_blocks - 1; i >= 0; --i)
+ BASIC_BLOCK (i)->aux = NULL;
+
EXECUTE_IF_SET_IN_SBITMAP (blocks_in, 0, i,
{
basic_block bb = BASIC_BLOCK (i);
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. */
+ /* The all-important stack pointer must always be live. */
SET_REGNO_REG_SET (new_live_at_end, STACK_POINTER_REGNUM);
- /* Similarly for the frame pointer before reload. Any reference
- to any pseudo before reload is a potential reference of the
- frame pointer. */
+ /* Before reload, there are a few registers that must be forced
+ live everywhere -- which might not already be the case for
+ blocks within infinite loops. */
if (! reload_completed)
- SET_REGNO_REG_SET (new_live_at_end, FRAME_POINTER_REGNUM);
+ {
+ /* Any reference to any pseudo before reload is a potential
+ reference of the frame pointer. */
+ SET_REGNO_REG_SET (new_live_at_end, FRAME_POINTER_REGNUM);
+
+#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
+ /* Pseudos with argument area equivalences may require
+ reloading via the argument pointer. */
+ if (fixed_regs[ARG_POINTER_REGNUM])
+ SET_REGNO_REG_SET (new_live_at_end, ARG_POINTER_REGNUM);
+#endif
+
+ /* Any constant, or pseudo with constant equivalences, may
+ require reloading from memory using the pic register. */
+ if (PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
+ && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
+ SET_REGNO_REG_SET (new_live_at_end, PIC_OFFSET_TABLE_REGNUM);
+ }
/* Regs used in phi nodes are not included in
global_live_at_start, since they are live only along a
if (bb->local_set == NULL)
{
- bb->local_set = OBSTACK_ALLOC_REG_SET (function_obstack);
+ bb->local_set = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+ bb->cond_local_set = OBSTACK_ALLOC_REG_SET (&flow_obstack);
rescan = 1;
}
else
if (! rescan)
{
+ /* If any of the registers in the new live_at_end set are
+ conditionally set in this basic block, we must rescan.
+ This is because conditional lifetimes at the end of the
+ block do not just take the live_at_end set into account,
+ but also the liveness at the start of each successor
+ block. We can miss changes in those sets if we only
+ compare the new live_at_end against the previous one. */
+ CLEAR_REG_SET (tmp);
+ rescan = bitmap_operation (tmp, new_live_at_end,
+ bb->cond_local_set, BITMAP_AND);
+ }
+
+ if (! rescan)
+ {
/* Find the set of changed bits. Take this opportunity
to notice that this set is empty and early out. */
CLEAR_REG_SET (tmp);
/* Rescan the block insn by insn to turn (a copy of) live_at_end
into live_at_start. */
- propagate_block (bb, new_live_at_end, bb->local_set, flags);
+ propagate_block (bb, new_live_at_end, bb->local_set,
+ bb->cond_local_set, flags);
/* If live_at start didn't change, no need to go farther. */
if (REG_SET_EQUAL_P (bb->global_live_at_start, new_live_at_end))
{
basic_block bb = BASIC_BLOCK (i);
FREE_REG_SET (bb->local_set);
+ FREE_REG_SET (bb->cond_local_set);
});
}
else
{
basic_block bb = BASIC_BLOCK (i);
FREE_REG_SET (bb->local_set);
+ FREE_REG_SET (bb->cond_local_set);
}
}
/* Allocate the permanent data structures that represent the results
of life analysis. Not static since used also for stupid life analysis. */
-void
+static void
allocate_bb_life_data ()
{
register int i;
{
basic_block bb = BASIC_BLOCK (i);
- bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (function_obstack);
- bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_obstack);
+ bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+ bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
}
ENTRY_BLOCK_PTR->global_live_at_end
- = OBSTACK_ALLOC_REG_SET (function_obstack);
+ = OBSTACK_ALLOC_REG_SET (&flow_obstack);
EXIT_BLOCK_PTR->global_live_at_start
- = OBSTACK_ALLOC_REG_SET (function_obstack);
+ = OBSTACK_ALLOC_REG_SET (&flow_obstack);
- regs_live_at_setjmp = OBSTACK_ALLOC_REG_SET (function_obstack);
+ regs_live_at_setjmp = OBSTACK_ALLOC_REG_SET (&flow_obstack);
}
void
note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
if (flags & PROP_SCAN_DEAD_CODE)
{
- insn_is_dead = insn_dead_p (pbi, PATTERN (insn), 0,
- REG_NOTES (insn));
+ 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, note, insn));
}
- /* 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)))
- && find_reg_note (insn, REG_MAYBE_DEAD, NULL_RTX) == 0)
- {
- 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;
- }
-
/* If an instruction consists of just dead store(s) on final pass,
delete it. */
if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead)
{
+ /* If we're trying to delete a prologue or epilogue instruction
+ that isn't flagged as possibly being dead, something is wrong.
+ But if we are keeping the stack pointer depressed, we might well
+ be deleting insns that are used to compute the amount to update
+ it by, so they are fine. */
+ if (reload_completed
+ && !(TREE_CODE (TREE_TYPE (current_function_decl)) == FUNCTION_TYPE
+ && (TYPE_RETURNS_STACK_DEPRESSED
+ (TREE_TYPE (current_function_decl))))
+ && (((HAVE_epilogue || HAVE_prologue)
+ && prologue_epilogue_contains (insn))
+ || (HAVE_sibcall_epilogue
+ && sibcall_epilogue_contains (insn)))
+ && find_reg_note (insn, REG_MAYBE_DEAD, NULL_RTX) == 0)
+ abort ();
+
/* 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);
/* Non-constant calls clobber memory. */
if (! CONST_CALL_P (insn))
- free_EXPR_LIST_list (&pbi->mem_set_list);
+ {
+ free_EXPR_LIST_list (&pbi->mem_set_list);
+ pbi->mem_set_list_len = 0;
+ }
/* There may be extra registers to be clobbered. */
for (note = CALL_INSN_FUNCTION_USAGE (insn);
the user can use the regsets provided here. */
struct propagate_block_info *
-init_propagate_block_info (bb, live, local_set, flags)
+init_propagate_block_info (bb, live, local_set, cond_local_set, flags)
basic_block bb;
- regset live;
- regset local_set;
+ regset live, local_set, cond_local_set;
int flags;
{
struct propagate_block_info *pbi = xmalloc (sizeof (*pbi));
pbi->bb = bb;
pbi->reg_live = live;
pbi->mem_set_list = NULL_RTX;
+ pbi->mem_set_list_len = 0;
pbi->local_set = local_set;
+ pbi->cond_local_set = cond_local_set;
pbi->cc0_live = 0;
pbi->flags = flags;
/* 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 ((flags & (PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE))
- && GET_CODE (bb->end) == JUMP_INSN
+ if (GET_CODE (bb->end) == JUMP_INSN
&& any_condjump_p (bb->end))
{
regset_head diff_head;
cond = cond_false;
else
cond = cond_true;
- rcli->condition = alloc_EXPR_LIST (0, cond, NULL_RTX);
+ rcli->condition = cond;
splay_tree_insert (pbi->reg_cond_dead, i,
(splay_tree_value) rcli);
{
rtx mem = SET_DEST (PATTERN (insn));
+ /* This optimization is performed by faking a store to the
+ memory at the end of the block. This doesn't work for
+ unchanging memories because multiple stores to unchanging
+ memory is illegal and alias analysis doesn't consider it. */
+ if (RTX_UNCHANGING_P (mem))
+ continue;
+
if (XEXP (mem, 0) == frame_pointer_rtx
|| (GET_CODE (XEXP (mem, 0)) == PLUS
&& XEXP (XEXP (mem, 0), 0) == frame_pointer_rtx
&& GET_CODE (XEXP (XEXP (mem, 0), 1)) == CONST_INT))
- pbi->mem_set_list = alloc_EXPR_LIST (0, mem, pbi->mem_set_list);
+ {
+#ifdef AUTO_INC_DEC
+ /* Store a copy of mem, otherwise the address may be scrogged
+ by find_auto_inc. This matters because insn_dead_p uses
+ an rtx_equal_p check to determine if two addresses are
+ the same. This works before find_auto_inc, but fails
+ after find_auto_inc, causing discrepencies between the
+ set of live registers calculated during the
+ calculate_global_regs_live phase and what actually exists
+ after flow completes, leading to aborts. */
+ if (flags & PROP_AUTOINC)
+ mem = shallow_copy_rtx (mem);
+#endif
+ pbi->mem_set_list = alloc_EXPR_LIST (0, mem, pbi->mem_set_list);
+ if (++pbi->mem_set_list_len >= MAX_MEM_SET_LIST_LEN)
+ break;
+ }
}
}
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. */
+ LOCAL_SET, if non-null, will be set with all registers killed
+ unconditionally by this basic block.
+ Likewise, COND_LOCAL_SET, if non-null, will be set with all registers
+ killed conditionally by this basic block. If there is any unconditional
+ set of a register, then the corresponding bit will be set in LOCAL_SET
+ and cleared in COND_LOCAL_SET.
+ It is valid for LOCAL_SET and COND_LOCAL_SET to be the same set. In this
+ case, the resulting set will be equal to the union of the two sets that
+ would otherwise be computed. */
void
-propagate_block (bb, live, local_set, flags)
+propagate_block (bb, live, local_set, cond_local_set, flags)
basic_block bb;
regset live;
regset local_set;
+ regset cond_local_set;
int flags;
{
struct propagate_block_info *pbi;
rtx insn, prev;
- pbi = init_propagate_block_info (bb, live, local_set, flags);
+ pbi = init_propagate_block_info (bb, live, local_set, cond_local_set, flags);
if (flags & PROP_REG_INFO)
{
#ifdef AUTO_INC_DEC
/* Check if memory reference matches an auto increment. Only
post increment/decrement or modify are valid. */
- if (GET_MODE (mem) == GET_MODE (r)
+ if (GET_MODE (mem) == GET_MODE (r)
&& (GET_CODE (XEXP (mem, 0)) == POST_DEC
|| GET_CODE (XEXP (mem, 0)) == POST_INC
|| GET_CODE (XEXP (mem, 0)) == POST_MODIFY)
if (regno == STACK_POINTER_REGNUM)
return 0;
+ /* ??? These bits might be redundant with the force live bits
+ in calculate_global_regs_live. We would delete from
+ sequential sets; whether this actually affects real code
+ for anything but the stack pointer I don't know. */
/* Make sure insns to set the frame pointer aren't deleted. */
if (regno == FRAME_POINTER_REGNUM
&& (! reload_completed || frame_pointer_needed))
return 0;
#endif
-#ifdef PIC_OFFSET_TABLE_REGNUM
- /* Before reload, do not allow sets of the pic register
- to be deleted. Reload can insert references to
- constant pool memory anywhere in the function, making
- the PIC register live where it wasn't before. */
- if (regno == PIC_OFFSET_TABLE_REGNUM && fixed_regs[regno]
- && ! reload_completed)
- return 0;
-#endif
-
/* Otherwise, the set is dead. */
return 1;
}
else
pbi->mem_set_list = next;
free_EXPR_LIST_node (temp);
+ pbi->mem_set_list_len--;
}
else
prev = temp;
}
}
+/* EXP is either a MEM or a REG. Remove any dependant entries
+ from pbi->mem_set_list. */
+
+static void
+invalidate_mems_from_set (pbi, exp)
+ struct propagate_block_info *pbi;
+ rtx exp;
+{
+ rtx temp = pbi->mem_set_list;
+ rtx prev = NULL_RTX;
+ rtx next;
+
+ while (temp)
+ {
+ next = XEXP (temp, 1);
+ if ((GET_CODE (exp) == MEM
+ && output_dependence (XEXP (temp, 0), exp))
+ || (GET_CODE (exp) == REG
+ && reg_overlap_mentioned_p (exp, XEXP (temp, 0))))
+ {
+ /* Splice this entry out of the list. */
+ if (prev)
+ XEXP (prev, 1) = next;
+ else
+ pbi->mem_set_list = next;
+ free_EXPR_LIST_node (temp);
+ pbi->mem_set_list_len--;
+ }
+ else
+ prev = temp;
+ temp = next;
+ }
+}
+
/* Process the registers that are set within X. Their bits are set to
1 in the regset DEAD, because they are dead prior to this insn.
int not_dead = 0;
int i;
- /* Some targets place small structures in registers for
- return values of functions. We have to detect this
- case specially here to get correct flow information. */
- if (GET_CODE (reg) == PARALLEL
- && GET_MODE (reg) == BLKmode)
- {
- for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
- 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. Of course, if it was dead after it's unused now. */
switch (GET_CODE (reg))
{
+ case PARALLEL:
+ /* Some targets place small structures in registers for return values of
+ functions. We have to detect this case specially here to get correct
+ flow information. */
+ for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
+ if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
+ mark_set_1 (pbi, code, XEXP (XVECEXP (reg, 0, i), 0), cond, insn,
+ flags);
+ return;
+
case ZERO_EXTRACT:
case SIGN_EXTRACT:
case STRICT_LOW_PART:
if (optimize && (flags & PROP_SCAN_DEAD_CODE))
{
if (GET_CODE (reg) == MEM || GET_CODE (reg) == REG)
- {
- rtx temp = pbi->mem_set_list;
- rtx prev = NULL_RTX;
- rtx next;
-
- while (temp)
- {
- next = XEXP (temp, 1);
- if ((GET_CODE (reg) == MEM
- && output_dependence (XEXP (temp, 0), reg))
- || (GET_CODE (reg) == REG
- && reg_overlap_mentioned_p (reg, XEXP (temp, 0))))
- {
- /* Splice this entry out of the list. */
- if (prev)
- XEXP (prev, 1) = next;
- else
- pbi->mem_set_list = next;
- free_EXPR_LIST_node (temp);
- }
- else
- prev = temp;
- temp = next;
- }
- }
+ invalidate_mems_from_set (pbi, reg);
/* If the memory reference had embedded side effects (autoincrement
address modes. Then we may need to kill some entries on the
if (insn && GET_CODE (reg) == MEM)
invalidate_mems_from_autoinc (pbi, insn);
- if (GET_CODE (reg) == MEM && ! side_effects_p (reg)
+ if (pbi->mem_set_list_len < MAX_MEM_SET_LIST_LEN
+ && GET_CODE (reg) == MEM && ! side_effects_p (reg)
/* ??? With more effort we could track conditional memory life. */
&& ! cond
/* 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))
- pbi->mem_set_list = alloc_EXPR_LIST (0, reg, pbi->mem_set_list);
+ {
+#ifdef AUTO_INC_DEC
+ /* Store a copy of mem, otherwise the address may be
+ scrogged by find_auto_inc. */
+ if (flags & PROP_AUTOINC)
+ reg = shallow_copy_rtx (reg);
+#endif
+ pbi->mem_set_list = alloc_EXPR_LIST (0, reg, pbi->mem_set_list);
+ pbi->mem_set_list_len++;
+ }
}
if (GET_CODE (reg) == REG
{
int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i);
if (pbi->local_set)
- SET_REGNO_REG_SET (pbi->local_set, i);
+ {
+ /* Order of the set operation matters here since both
+ sets may be the same. */
+ CLEAR_REGNO_REG_SET (pbi->cond_local_set, i);
+ if (cond != NULL_RTX
+ && ! REGNO_REG_SET_P (pbi->local_set, i))
+ SET_REGNO_REG_SET (pbi->cond_local_set, i);
+ else
+ SET_REGNO_REG_SET (pbi->local_set, i);
+ }
if (code != CLOBBER)
SET_REGNO_REG_SET (pbi->new_set, i);
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);
+ rcli->condition = cond;
splay_tree_insert (pbi->reg_cond_dead, regno,
(splay_tree_value) rcli);
Add the new condition to the old. */
rcli = (struct reg_cond_life_info *) node->value;
ncond = rcli->condition;
- ncond = ior_reg_cond (ncond, cond);
+ ncond = ior_reg_cond (ncond, cond, 1);
/* If the register is now unconditionally dead,
remove the entry in the splay_tree. */
splay_tree_value value;
{
struct reg_cond_life_info *rcli = (struct reg_cond_life_info *) value;
- free_EXPR_LIST_list (&rcli->condition);
free (rcli);
}
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. */
/* 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));
- }
+ rcli->condition = elim_reg_cond (rcli->condition, regno);
- /* If the entire condition is now NULL, signal the node to be removed. */
- if (! rcli->condition)
+ /* If the entire condition is now false, signal the node to be removed. */
+ if (rcli->condition == const0_rtx)
{
xdata[1] = node->key;
return -1;
}
- else
- return 0;
+ else if (rcli->condition == const1_rtx)
+ abort ();
+
+ return 0;
}
/* Flush all (sub) expressions referring to REGNO from REG_COND_LIVE. */
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. */
+/* Logical arithmetic on predicate conditions. IOR, NOT and AND.
+ For ior/and, the ADD flag determines whether we want to add the new
+ condition X to the old one unconditionally. If it is zero, we will
+ only return a new expression if X allows us to simplify part of
+ OLD, otherwise we return OLD unchanged to the caller.
+ If ADD is nonzero, we will return a new condition in all cases. The
+ toplevel caller of one of these functions should always pass 1 for
+ ADD. */
static rtx
-ior_reg_cond (old, x)
+ior_reg_cond (old, x, add)
rtx old, x;
+ int add;
{
- enum rtx_code x_code;
- rtx x_reg;
- rtx c;
+ rtx op0, op1;
- /* 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 ();
+ if (GET_RTX_CLASS (GET_CODE (old)) == '<')
+ {
+ if (GET_RTX_CLASS (GET_CODE (x)) == '<'
+ && GET_CODE (x) == reverse_condition (GET_CODE (old))
+ && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
+ return const1_rtx;
+ if (GET_CODE (x) == GET_CODE (old)
+ && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
+ return old;
+ if (! add)
+ return old;
+ return gen_rtx_IOR (0, old, x);
+ }
- /* Search the expression for an existing sub-expression of X_REG. */
- for (c = old; c; c = XEXP (c, 1))
+ switch (GET_CODE (old))
{
- rtx y = XEXP (c, 0);
- if (REGNO (XEXP (y, 0)) == REGNO (x_reg))
+ case IOR:
+ op0 = ior_reg_cond (XEXP (old, 0), x, 0);
+ op1 = ior_reg_cond (XEXP (old, 1), x, 0);
+ if (op0 != XEXP (old, 0) || op1 != XEXP (old, 1))
{
- /* 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))
+ if (op0 == const0_rtx)
+ return op1;
+ if (op1 == const0_rtx)
+ return op0;
+ if (op0 == const1_rtx || op1 == const1_rtx)
return const1_rtx;
+ if (op0 == XEXP (old, 0))
+ op0 = gen_rtx_IOR (0, op0, x);
+ else
+ op1 = gen_rtx_IOR (0, op1, x);
+ return gen_rtx_IOR (0, op0, op1);
}
- }
+ if (! add)
+ return old;
+ return gen_rtx_IOR (0, old, x);
+
+ case AND:
+ op0 = ior_reg_cond (XEXP (old, 0), x, 0);
+ op1 = ior_reg_cond (XEXP (old, 1), x, 0);
+ if (op0 != XEXP (old, 0) || op1 != XEXP (old, 1))
+ {
+ if (op0 == const1_rtx)
+ return op1;
+ if (op1 == const1_rtx)
+ return op0;
+ if (op0 == const0_rtx || op1 == const0_rtx)
+ return const0_rtx;
+ if (op0 == XEXP (old, 0))
+ op0 = gen_rtx_IOR (0, op0, x);
+ else
+ op1 = gen_rtx_IOR (0, op1, x);
+ return gen_rtx_AND (0, op0, op1);
+ }
+ if (! add)
+ return old;
+ return gen_rtx_IOR (0, old, x);
+
+ case NOT:
+ op0 = and_reg_cond (XEXP (old, 0), not_reg_cond (x), 0);
+ if (op0 != XEXP (old, 0))
+ return not_reg_cond (op0);
+ if (! add)
+ return old;
+ return gen_rtx_IOR (0, old, x);
- /* Otherwise just add to the chain. */
- return alloc_EXPR_LIST (0, x, old);
+ default:
+ abort ();
+ }
}
static rtx
rtx x;
{
enum rtx_code x_code;
- rtx x_reg;
- /* We expect these conditions to be of the form (eq reg 0). */
+ if (x == const0_rtx)
+ return const1_rtx;
+ else if (x == const1_rtx)
+ return const0_rtx;
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 ();
+ if (x_code == NOT)
+ return XEXP (x, 0);
+ if (GET_RTX_CLASS (x_code) == '<'
+ && GET_CODE (XEXP (x, 0)) == REG)
+ {
+ if (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);
+ return gen_rtx_fmt_ee (reverse_condition (x_code),
+ VOIDmode, XEXP (x, 0), const0_rtx);
+ }
+ return gen_rtx_NOT (0, x);
}
static rtx
-nand_reg_cond (old, x)
+and_reg_cond (old, x, add)
rtx old, x;
+ int add;
{
- 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 ();
+ rtx op0, op1;
- /* Search the expression for an existing sub-expression of X_REG. */
+ if (GET_RTX_CLASS (GET_CODE (old)) == '<')
+ {
+ if (GET_RTX_CLASS (GET_CODE (x)) == '<'
+ && GET_CODE (x) == reverse_condition (GET_CODE (old))
+ && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
+ return const0_rtx;
+ if (GET_CODE (x) == GET_CODE (old)
+ && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
+ return old;
+ if (! add)
+ return old;
+ return gen_rtx_AND (0, old, x);
+ }
- for (c = *(prev = &old); c; c = *(prev = &XEXP (c, 1)))
+ switch (GET_CODE (old))
{
- rtx y = XEXP (c, 0);
- if (REGNO (XEXP (y, 0)) == REGNO (x_reg))
+ case IOR:
+ op0 = and_reg_cond (XEXP (old, 0), x, 0);
+ op1 = and_reg_cond (XEXP (old, 1), x, 0);
+ if (op0 != XEXP (old, 0) || op1 != XEXP (old, 1))
{
- /* 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;
+ if (op0 == const0_rtx)
+ return op1;
+ if (op1 == const0_rtx)
+ return op0;
+ if (op0 == const1_rtx || op1 == const1_rtx)
+ return const1_rtx;
+ if (op0 == XEXP (old, 0))
+ op0 = gen_rtx_AND (0, op0, x);
+ else
+ op1 = gen_rtx_AND (0, op1, x);
+ return gen_rtx_IOR (0, op0, op1);
}
+ if (! add)
+ return old;
+ return gen_rtx_AND (0, old, x);
+
+ case AND:
+ op0 = and_reg_cond (XEXP (old, 0), x, 0);
+ op1 = and_reg_cond (XEXP (old, 1), x, 0);
+ if (op0 != XEXP (old, 0) || op1 != XEXP (old, 1))
+ {
+ if (op0 == const1_rtx)
+ return op1;
+ if (op1 == const1_rtx)
+ return op0;
+ if (op0 == const0_rtx || op1 == const0_rtx)
+ return const0_rtx;
+ if (op0 == XEXP (old, 0))
+ op0 = gen_rtx_AND (0, op0, x);
+ else
+ op1 = gen_rtx_AND (0, op1, x);
+ return gen_rtx_AND (0, op0, op1);
+ }
+ if (! add)
+ return old;
+ return gen_rtx_AND (0, old, x);
+
+ case NOT:
+ op0 = ior_reg_cond (XEXP (old, 0), not_reg_cond (x), 0);
+ if (op0 != XEXP (old, 0))
+ return not_reg_cond (op0);
+ if (! add)
+ return old;
+ return gen_rtx_AND (0, old, x);
+
+ default:
+ abort ();
}
+}
+
+/* Given a condition X, remove references to reg REGNO and return the
+ new condition. The removal will be done so that all conditions
+ involving REGNO are considered to evaluate to false. This function
+ is used when the value of REGNO changes. */
+
+static rtx
+elim_reg_cond (x, regno)
+ rtx x;
+ unsigned int regno;
+{
+ rtx op0, op1;
+
+ if (GET_RTX_CLASS (GET_CODE (x)) == '<')
+ {
+ if (REGNO (XEXP (x, 0)) == regno)
+ return const0_rtx;
+ return x;
+ }
+
+ switch (GET_CODE (x))
+ {
+ case AND:
+ op0 = elim_reg_cond (XEXP (x, 0), regno);
+ op1 = elim_reg_cond (XEXP (x, 1), regno);
+ if (op0 == const0_rtx || op1 == const0_rtx)
+ return const0_rtx;
+ if (op0 == const1_rtx)
+ return op1;
+ if (op1 == const1_rtx)
+ return op0;
+ if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
+ return x;
+ return gen_rtx_AND (0, op0, op1);
+
+ case IOR:
+ op0 = elim_reg_cond (XEXP (x, 0), regno);
+ op1 = elim_reg_cond (XEXP (x, 1), regno);
+ if (op0 == const1_rtx || op1 == const1_rtx)
+ return const1_rtx;
+ if (op0 == const0_rtx)
+ return op1;
+ if (op1 == const0_rtx)
+ return op0;
+ if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
+ return x;
+ return gen_rtx_IOR (0, op0, op1);
+
+ case NOT:
+ op0 = elim_reg_cond (XEXP (x, 0), regno);
+ if (op0 == const0_rtx)
+ return const1_rtx;
+ if (op0 == const1_rtx)
+ return const0_rtx;
+ if (op0 != XEXP (x, 0))
+ return not_reg_cond (op0);
+ return x;
- /* 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);
+ default:
+ abort ();
+ }
}
#endif /* HAVE_conditional_execution */
\f
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);
+ ncond = and_reg_cond (ncond, not_reg_cond (cond), 1);
/* If the register is now unconditionally live, remove the
entry in the splay_tree. */
else
pbi->mem_set_list = next;
free_EXPR_LIST_node (temp);
+ pbi->mem_set_list_len--;
}
else
prev = temp;
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 or group of registers,
+ recursively scan the value being stored. */
if ((GET_CODE (testreg) == PARALLEL
&& GET_MODE (testreg) == BLKmode)
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 (&pbi->mem_set_list);
+ {
+ free_EXPR_LIST_list (&pbi->mem_set_list);
+ pbi->mem_set_list_len = 0;
+ }
/* 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 regno = REGNO (SET_DEST (x));
rtx y = pbi->reg_next_use[regno];
if (y != 0
+ && SET_DEST (x) != stack_pointer_rtx
&& BLOCK_NUM (y) == BLOCK_NUM (insn)
/* Don't do this if the reg dies, or gets set in y; a standard addressing
mode would be better. */
&& ! dead_or_set_p (y, SET_DEST (x))
&& try_pre_increment (y, SET_DEST (x), amount))
{
- /* We have found a suitable auto-increment
- and already changed insn Y to do it.
- So flush this increment-instruction. */
- PUT_CODE (insn, NOTE);
- NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (insn) = 0;
- /* Count a reference to this reg for the increment
- insn we are deleting. When a reg is incremented.
- spilling it is worse, so we want to make that
- less likely. */
+ /* We have found a suitable auto-increment and already changed
+ insn Y to do it. So flush this increment instruction. */
+ propagate_block_delete_insn (pbi->bb, insn);
+
+ /* Count a reference to this reg for the increment insn we are
+ deleting. When a reg is incremented, spilling it is worse,
+ so we want to make that less likely. */
if (regno >= FIRST_PSEUDO_REGISTER)
{
REG_N_REFS (regno) += (optimize_size ? 1
: pbi->bb->loop_depth + 1);
REG_N_SETS (regno)++;
}
+
+ /* Flush any remembered memories depending on the value of
+ the incremented register. */
+ invalidate_mems_from_set (pbi, SET_DEST (x));
+
return 1;
}
return 0;
reg_class_names[(int) class],
reg_class_names[(int) altclass]);
}
- if (REGNO_POINTER_FLAG (i))
+ if (REG_POINTER (regno_reg_rtx[i]))
fprintf (file, "; pointer");
fprintf (file, ".\n");
}
}
}
-/* Compute dominator relationships using new flow graph structures. */
-
-void
-compute_flow_dominators (dominators, post_dominators)
- sbitmap *dominators;
- sbitmap *post_dominators;
-{
- int bb;
- sbitmap *temp_bitmap;
- edge e;
- 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. */
- 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);
-
- if (dominators)
- {
- /* 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++)
- {
- *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. */
- sbitmap_vector_ones (dominators, n_basic_blocks);
-
- /* Mark successors of the entry block so we can identify them below. */
- for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
- e->dest->aux = ENTRY_BLOCK_PTR;
-
- /* Iterate until the worklist is empty. */
- while (qlen)
- {
- /* Take the first entry off the worklist. */
- basic_block b = *qout++;
- if (qout >= workend)
- qout = worklist;
- qlen--;
-
- bb = b->index;
-
- /* Compute the intersection of the dominators of all the
- predecessor blocks.
-
- If one of the predecessor blocks is the ENTRY block, then the
- intersection of the dominators of the predecessor blocks is
- defined as the null set. We can identify such blocks by the
- special value in the AUX field in the block structure. */
- if (b->aux == ENTRY_BLOCK_PTR)
- {
- /* Do not clear the aux field for blocks which are
- successors of the ENTRY block. That way we never add
- them to the worklist again.
-
- The intersect of dominators of the preds of this block is
- defined as the null set. */
- sbitmap_zero (temp_bitmap[bb]);
- }
- else
- {
- /* Clear the aux field of this block so it can be added to
- the worklist again if necessary. */
- b->aux = NULL;
- sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb);
- }
-
- /* Make sure each block always dominates itself. */
- SET_BIT (temp_bitmap[bb], bb);
-
- /* If the out state of this block changed, then we need to
- add the successors of this block to the worklist if they
- are not already on the worklist. */
- if (sbitmap_a_and_b (dominators[bb], dominators[bb], temp_bitmap[bb]))
- {
- for (e = b->succ; e; e = e->succ_next)
- {
- if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
- {
- *qin++ = e->dest;
- if (qin >= workend)
- qin = worklist;
- qlen++;
-
- e->dest->aux = e;
- }
- }
- }
- }
- }
-
- if (post_dominators)
- {
- /* 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++)
- {
- *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. */
- sbitmap_vector_ones (post_dominators, n_basic_blocks);
-
- /* Mark predecessors of the exit block so we can identify them below. */
- for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
- e->src->aux = EXIT_BLOCK_PTR;
-
- /* Iterate until the worklist is empty. */
- while (qlen)
- {
- /* Take the first entry off the worklist. */
- basic_block b = *qout++;
- if (qout >= workend)
- qout = worklist;
- qlen--;
-
- bb = b->index;
-
- /* Compute the intersection of the post dominators of all the
- successor blocks.
-
- If one of the successor blocks is the EXIT block, then the
- intersection of the dominators of the successor blocks is
- defined as the null set. We can identify such blocks by the
- special value in the AUX field in the block structure. */
- if (b->aux == EXIT_BLOCK_PTR)
- {
- /* Do not clear the aux field for blocks which are
- predecessors of the EXIT block. That way we we never
- add them to the worklist again.
-
- The intersect of dominators of the succs of this block is
- defined as the null set. */
- sbitmap_zero (temp_bitmap[bb]);
- }
- else
- {
- /* Clear the aux field of this block so it can be added to
- the worklist again if necessary. */
- b->aux = NULL;
- sbitmap_intersection_of_succs (temp_bitmap[bb],
- post_dominators, bb);
- }
-
- /* Make sure each block always post dominates itself. */
- SET_BIT (temp_bitmap[bb], bb);
-
- /* If the out state of this block changed, then we need to
- add the successors of this block to the worklist if they
- are not already on the worklist. */
- if (sbitmap_a_and_b (post_dominators[bb],
- post_dominators[bb],
- temp_bitmap[bb]))
- {
- for (e = b->pred; e; e = e->pred_next)
- {
- if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
- {
- *qin++ = e->src;
- if (qin >= workend)
- qin = worklist;
- qlen++;
-
- e->src->aux = e;
- }
- }
- }
- }
- }
-
- free (worklist);
- free (temp_bitmap);
-}
-
-/* Given DOMINATORS, compute the immediate dominators into IDOM. If a
- block dominates only itself, its entry remains as INVALID_BLOCK. */
-
-void
-compute_immediate_dominators (idom, dominators)
- int *idom;
- sbitmap *dominators;
+/* Dump the rtl into the current debugging dump file, then abort. */
+static void
+print_rtl_and_abort ()
{
- sbitmap *tmp;
- int b;
-
- tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
-
- /* Begin with tmp(n) = dom(n) - { n }. */
- for (b = n_basic_blocks; --b >= 0;)
- {
- sbitmap_copy (tmp[b], dominators[b]);
- RESET_BIT (tmp[b], b);
- }
-
- /* Subtract out all of our dominator's dominators. */
- for (b = n_basic_blocks; --b >= 0;)
- {
- sbitmap tmp_b = tmp[b];
- int s;
-
- for (s = n_basic_blocks; --s >= 0;)
- if (TEST_BIT (tmp_b, s))
- sbitmap_difference (tmp_b, tmp_b, tmp[s]);
- }
-
- /* Find the one bit set in the bitmap and put it in the output array. */
- for (b = n_basic_blocks; --b >= 0;)
+ if (rtl_dump_file)
{
- int t;
- EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; });
+ print_rtl_with_bb (rtl_dump_file, get_insns ());
+ fclose (rtl_dump_file);
}
-
- sbitmap_vector_free (tmp);
-}
-
-/* Given POSTDOMINATORS, compute the immediate postdominators into
- IDOM. If a block is only dominated by itself, its entry remains as
- INVALID_BLOCK. */
-
-void
-compute_immediate_postdominators (idom, postdominators)
- int *idom;
- sbitmap *postdominators;
-{
- compute_immediate_dominators (idom, postdominators);
+ abort ();
}
/* Recompute register set/reference counts immediately prior to register
return count;
}
+
+/* Update insns block within BB. */
+
+void
+update_bb_for_insn (bb)
+ basic_block bb;
+{
+ rtx insn;
+
+ if (! basic_block_for_insn)
+ return;
+
+ for (insn = bb->head; ; insn = NEXT_INSN (insn))
+ {
+ set_block_for_insn (insn, bb);
+
+ if (insn == bb->end)
+ break;
+ }
+}
+
+
/* Record INSN's block as BB. */
void
basic_block bb = NOTE_BASIC_BLOCK (x);
num_bb_notes++;
if (bb->index != last_bb_num_seen + 1)
- fatal ("Basic blocks not numbered consecutively");
+ /* Basic blocks not numbered consecutively. */
+ abort ();
+
last_bb_num_seen = bb->index;
}
}
if (num_bb_notes != n_basic_blocks)
- fatal ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
- num_bb_notes, n_basic_blocks);
+ internal_error
+ ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
+ num_bb_notes, n_basic_blocks);
if (err)
abort ();
if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ))
!= EDGE_INDEX_NO_EDGE && found_edge == 0)
fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
- pred, succ, EDGE_INDEX (elist, BASIC_BLOCK (pred),
+ pred, succ, EDGE_INDEX (elist, BASIC_BLOCK (pred),
BASIC_BLOCK (succ)));
}
for (succ = 0; succ < n_basic_blocks; succ++)
\f
/* Dump the list of basic blocks in the bitmap NODES. */
-static void
+static void
flow_nodes_print (str, nodes, file)
const char *str;
const sbitmap nodes;
/* Dump the list of edges in the array EDGE_LIST. */
-static void
+static void
flow_edge_list_print (str, edge_list, num_edges, file)
const char *str;
const edge *edge_list;
flow_loop_dump (loop, file, loop_dump_aux, verbose)
const struct loop *loop;
FILE *file;
- void (*loop_dump_aux)(const struct loop *, FILE *, int);
+ void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
int verbose;
{
if (! loop || ! loop->header)
loop->depth, loop->level,
(long) (loop->outer ? loop->outer->num : -1));
- flow_edge_list_print (";; entry edges", loop->entry_edges,
+ if (loop->pre_header_edges)
+ flow_edge_list_print (";; pre-header edges", loop->pre_header_edges,
+ loop->num_pre_header_edges, file);
+ flow_edge_list_print (";; entry edges", loop->entry_edges,
loop->num_entries, file);
fprintf (file, ";; %d", loop->num_nodes);
flow_nodes_print (" nodes", loop->nodes, file);
- flow_edge_list_print (";; exit edges", loop->exit_edges,
+ flow_edge_list_print (";; exit edges", loop->exit_edges,
loop->num_exits, file);
-
+ if (loop->exits_doms)
+ flow_nodes_print (";; exit doms", loop->exits_doms, file);
if (loop_dump_aux)
loop_dump_aux (loop, file, verbose);
}
/* Dump the loop information specified by LOOPS to the stream FILE,
using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
-void
+void
flow_loops_dump (loops, file, loop_dump_aux, verbose)
const struct loops *loops;
FILE *file;
- void (*loop_dump_aux)(const struct loop *, FILE *, int);
+ void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
int verbose;
{
int i;
if (! num_loops || ! file)
return;
- fprintf (file, ";; %d loops found, %d levels\n",
+ fprintf (file, ";; %d loops found, %d levels\n",
num_loops, loops->levels);
for (i = 0; i < num_loops; i++)
must be disjoint. */
disjoint = ! flow_loop_nested_p (smaller ? loop : oloop,
smaller ? oloop : loop);
- fprintf (file,
+ fprintf (file,
";; loop header %d shared by loops %d, %d %s\n",
loop->header->index, i, j,
disjoint ? "disjoint" : "nested");
{
struct loop *loop = &loops->array[i];
+ if (loop->pre_header_edges)
+ free (loop->pre_header_edges);
if (loop->nodes)
sbitmap_free (loop->nodes);
if (loop->entry_edges)
free (loop->entry_edges);
if (loop->exit_edges)
free (loop->exit_edges);
+ if (loop->exits_doms)
+ sbitmap_free (loop->exits_doms);
}
free (loops->array);
loops->array = NULL;
if (loops->cfg.dfs_order)
free (loops->cfg.dfs_order);
- sbitmap_free (loops->shared_headers);
+ if (loops->shared_headers)
+ sbitmap_free (loops->shared_headers);
}
}
for (e = header->pred; e; e = e->pred_next)
{
basic_block src = e->src;
-
+
if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
num_entries++;
}
for (e = header->pred; e; e = e->pred_next)
{
basic_block src = e->src;
-
+
if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
(*entry_edges)[num_entries++] = e;
}
EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
{
- basic_block dest = e->dest;
+ basic_block dest = e->dest;
if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
num_exits++;
EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
{
- basic_block dest = e->dest;
+ basic_block dest = e->dest;
if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
(*exit_edges)[num_exits++] = e;
return;
}
+
+/* Find the root node of the loop pre-header extended basic block and
+ the edges along the trace from the root node to the loop header. */
+
+static void
+flow_loop_pre_header_scan (loop)
+ struct loop *loop;
+{
+ int num = 0;
+ basic_block ebb;
+
+ loop->num_pre_header_edges = 0;
+
+ if (loop->num_entries != 1)
+ return;
+
+ ebb = loop->entry_edges[0]->src;
+
+ if (ebb != ENTRY_BLOCK_PTR)
+ {
+ edge e;
+
+ /* Count number of edges along trace from loop header to
+ root of pre-header extended basic block. Usually this is
+ only one or two edges. */
+ num++;
+ while (ebb->pred->src != ENTRY_BLOCK_PTR && ! ebb->pred->pred_next)
+ {
+ ebb = ebb->pred->src;
+ num++;
+ }
+
+ loop->pre_header_edges = (edge *) xmalloc (num * sizeof (edge *));
+ loop->num_pre_header_edges = num;
+
+ /* Store edges in order that they are followed. The source
+ of the first edge is the root node of the pre-header extended
+ basic block and the destination of the last last edge is
+ the loop header. */
+ for (e = loop->entry_edges[0]; num; e = e->src->pred)
+ {
+ loop->pre_header_edges[--num] = e;
+ }
+ }
+}
+
+
/* Return the block for the pre-header of the loop with header
HEADER where DOM specifies the dominator information. Return NULL if
there is no pre-header. */
return levels;
}
+
+/* Scan a single natural loop specified by LOOP collecting information
+ about it specified by FLAGS. */
+
+int
+flow_loop_scan (loops, loop, flags)
+ struct loops *loops;
+ struct loop *loop;
+ int flags;
+{
+ /* Determine prerequisites. */
+ if ((flags & LOOP_EXITS_DOMS) && ! loop->exit_edges)
+ flags |= LOOP_EXIT_EDGES;
+
+ if (flags & LOOP_ENTRY_EDGES)
+ {
+ /* Find edges which enter the loop header.
+ Note that the entry edges should only
+ enter the header of a natural loop. */
+ loop->num_entries
+ = flow_loop_entry_edges_find (loop->header,
+ loop->nodes,
+ &loop->entry_edges);
+ }
+
+ if (flags & LOOP_EXIT_EDGES)
+ {
+ /* Find edges which exit the loop. */
+ loop->num_exits
+ = flow_loop_exit_edges_find (loop->nodes,
+ &loop->exit_edges);
+ }
+
+ if (flags & LOOP_EXITS_DOMS)
+ {
+ int j;
+
+ /* Determine which loop nodes dominate all the exits
+ of the loop. */
+ loop->exits_doms = sbitmap_alloc (n_basic_blocks);
+ sbitmap_copy (loop->exits_doms, loop->nodes);
+ for (j = 0; j < loop->num_exits; j++)
+ sbitmap_a_and_b (loop->exits_doms, loop->exits_doms,
+ loops->cfg.dom[loop->exit_edges[j]->src->index]);
+
+ /* The header of a natural loop must dominate
+ all exits. */
+ if (! TEST_BIT (loop->exits_doms, loop->header->index))
+ abort ();
+ }
+
+ if (flags & LOOP_PRE_HEADER)
+ {
+ /* Look to see if the loop has a pre-header node. */
+ loop->pre_header
+ = flow_loop_pre_header_find (loop->header, loops->cfg.dom);
+
+ /* Find the blocks within the extended basic block of
+ the loop pre-header. */
+ flow_loop_pre_header_scan (loop);
+ }
+ return 1;
+}
+
+
/* Find all the natural loops in the function and save in LOOPS structure
and recalculate loop_depth information in basic block structures.
+ FLAGS controls which loop information is collected.
Return the number of natural loops found. */
int
-flow_loops_find (loops)
+flow_loops_find (loops, flags)
struct loops *loops;
+ int flags;
{
int i;
int b;
int *dfs_order;
int *rc_order;
- loops->num = 0;
- loops->array = NULL;
- loops->tree = NULL;
- dfs_order = NULL;
- rc_order = NULL;
+ /* This function cannot be repeatedly called with different
+ flags to build up the loop information. The loop tree
+ must always be built if this function is called. */
+ if (! (flags & LOOP_TREE))
+ abort ();
+
+ memset (loops, 0, sizeof (*loops));
/* Taking care of this degenerate case makes the rest of
this code simpler. */
if (n_basic_blocks == 0)
return 0;
+ dfs_order = NULL;
+ rc_order = NULL;
+
/* Compute the dominators. */
dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
- compute_flow_dominators (dom, NULL);
+ calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
/* Count the number of loop edges (back edges). This should be the
- same as the number of natural loops. Also clear the loop_depth
- and as we work from inner->outer in a loop nest we call
- find_loop_nodes_find which will increment loop_depth for nodes
- within the current loop, which happens to enclose inner loops. */
+ same as the number of natural loops. */
num_loops = 0;
for (b = 0; b < n_basic_blocks; b++)
{
- BASIC_BLOCK (b)->loop_depth = 0;
- for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next)
+ basic_block header;
+
+ header = BASIC_BLOCK (b);
+ header->loop_depth = 0;
+
+ for (e = header->pred; e; e = e->pred_next)
{
basic_block latch = e->src;
loop. It also has single back edge to the header
from a latch node. Note that multiple natural loops
may share the same header. */
+ if (b != header->index)
+ abort ();
+
if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b))
num_loops++;
}
rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
flow_depth_first_order_compute (dfs_order, rc_order);
+ /* Save CFG derived information to avoid recomputing it. */
+ loops->cfg.dom = dom;
+ loops->cfg.dfs_order = dfs_order;
+ loops->cfg.rc_order = rc_order;
+
/* Allocate loop structures. */
loops->array
= (struct loop *) xcalloc (num_loops, sizeof (struct loop));
{
basic_block header;
- /* Search the nodes of the CFG in DFS order that we can find
- outer loops first. */
+ /* Search the nodes of the CFG in reverse completion order
+ so that we can find outer loops first. */
header = BASIC_BLOCK (rc_order[b]);
/* Look for all the possible latch blocks for this header. */
loop->latch = latch;
loop->num = num_loops;
- /* Keep track of blocks that are loop headers so
- that we can tell which loops should be merged. */
- if (TEST_BIT (headers, header->index))
- SET_BIT (loops->shared_headers, header->index);
- SET_BIT (headers, header->index);
-
- /* Find nodes contained within the loop. */
- loop->nodes = sbitmap_alloc (n_basic_blocks);
- loop->num_nodes
- = flow_loop_nodes_find (header, latch, loop->nodes);
-
- /* Compute first and last blocks within the loop.
- These are often the same as the loop header and
- loop latch respectively, but this is not always
- the case. */
- loop->first
- = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes));
- loop->last
- = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes));
-
- /* Find edges which enter the loop header.
- Note that the entry edges should only
- enter the header of a natural loop. */
- loop->num_entries
- = flow_loop_entry_edges_find (loop->header, loop->nodes,
- &loop->entry_edges);
-
- /* Find edges which exit the loop. */
- loop->num_exits
- = flow_loop_exit_edges_find (loop->nodes,
- &loop->exit_edges);
-
- /* Look to see if the loop has a pre-header node. */
- loop->pre_header = flow_loop_pre_header_find (header, dom);
-
num_loops++;
}
}
}
+ for (i = 0; i < num_loops; i++)
+ {
+ struct loop *loop = &loops->array[i];
+
+ /* Keep track of blocks that are loop headers so
+ that we can tell which loops should be merged. */
+ if (TEST_BIT (headers, loop->header->index))
+ SET_BIT (loops->shared_headers, loop->header->index);
+ SET_BIT (headers, loop->header->index);
+
+ /* Find nodes contained within the loop. */
+ loop->nodes = sbitmap_alloc (n_basic_blocks);
+ loop->num_nodes
+ = flow_loop_nodes_find (loop->header, loop->latch, loop->nodes);
+
+ /* Compute first and last blocks within the loop.
+ These are often the same as the loop header and
+ loop latch respectively, but this is not always
+ the case. */
+ loop->first
+ = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes));
+ loop->last
+ = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes));
+
+ flow_loop_scan (loops, loop, flags);
+ }
+
/* Natural loops with shared headers may either be disjoint or
nested. Disjoint loops with shared headers cannot be inner
loops and should be merged. For now just mark loops that share
loops->num = num_loops;
- /* Save CFG derived information to avoid recomputing it. */
- loops->cfg.dom = dom;
- loops->cfg.dfs_order = dfs_order;
- loops->cfg.rc_order = rc_order;
-
/* Build the loop hierarchy tree. */
flow_loops_tree_build (loops);
return num_loops;
}
+
+/* Update the information regarding the loops in the CFG
+ specified by LOOPS. */
+int
+flow_loops_update (loops, flags)
+ struct loops *loops;
+ int flags;
+{
+ /* One day we may want to update the current loop data. For now
+ throw away the old stuff and rebuild what we need. */
+ if (loops->array)
+ flow_loops_free (loops);
+
+ return flow_loops_find (loops, flags);
+}
+
+
/* Return non-zero if edge E enters header of LOOP from outside of LOOP. */
int
SET_HARD_REG_BIT (*to, i);
});
}
+
+/* Called once at intialization time. */
+
+void
+init_flow ()
+{
+ static int initialized;
+
+ if (!initialized)
+ {
+ gcc_obstack_init (&flow_obstack);
+ flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
+ initialized = 1;
+ }
+ else
+ {
+ obstack_free (&flow_obstack, flow_firstobj);
+ flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
+ }
+}
OSDN Git Service
