#include "tree-pass.h"
#include "tree-ssa-propagate.h"
#include "langhooks.h"
-
+#include "varray.h"
+#include "vec.h"
/* This file implements a generic value propagation engine based on
the same propagation used by the SSA-CCP algorithm [1].
proceeds as follows:
1- Initially, all edges of the CFG are marked not executable and
- the CFG worklist seeded with all the statements in the entry
+ the CFG worklist is seeded with all the statements in the entry
basic block (block 0).
2- Every statement S is simulated with a call to the call-back
SSA_PROP_INTERESTING: S produces a value that can be computed
at compile time. Its result can be propagated into the
- statements that feed from S. Furhtermore, if S is a
+ statements that feed from S. Furthermore, if S is a
conditional jump, only the edge known to be taken is added
to the work list. Edges that are known not to execute are
never simulated.
3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
return value from SSA_PROP_VISIT_PHI has the same semantics as
- described in #3.
+ described in #2.
4- Three work lists are kept. Statements are only added to these
lists if they produce one of SSA_PROP_INTERESTING or
definition has changed. SSA edges are def-use edges in the SSA
web. For each D-U edge, we store the target statement or PHI node
U. */
-static GTY(()) varray_type interesting_ssa_edges;
+static GTY(()) VEC(tree) *interesting_ssa_edges;
/* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
list of SSA edges is split into two. One contains all SSA edges
don't use a separate worklist for VARYING edges, we end up with
situations where lattice values move from
UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
-static GTY(()) varray_type varying_ssa_edges;
+static GTY(()) VEC(tree) *varying_ssa_edges;
/* Return true if the block worklist empty. */
}
-/* Add a basic block to the worklist. */
+/* Add a basic block to the worklist. The block must not be already
+ in the worklist, and it must not be the ENTRY or EXIT block. */
static void
cfg_blocks_add (basic_block bb)
{
- if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
- return;
-
- if (TEST_BIT (bb_in_list, bb->index))
- return;
+ gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR);
+ gcc_assert (!TEST_BIT (bb_in_list, bb->index));
if (cfg_blocks_empty_p ())
{
bb = VARRAY_BB (cfg_blocks, cfg_blocks_head);
-#ifdef ENABLE_CHECKING
- if (cfg_blocks_empty_p () || !bb)
- abort ();
-#endif
+ gcc_assert (!cfg_blocks_empty_p ());
+ gcc_assert (bb);
cfg_blocks_head = (cfg_blocks_head + 1) % VARRAY_SIZE (cfg_blocks);
--cfg_blocks_num;
{
STMT_IN_SSA_EDGE_WORKLIST (use_stmt) = 1;
if (is_varying)
- VARRAY_PUSH_TREE (varying_ssa_edges, use_stmt);
+ VEC_safe_push (tree, varying_ssa_edges, use_stmt);
else
- VARRAY_PUSH_TREE (interesting_ssa_edges, use_stmt);
+ VEC_safe_push (tree, interesting_ssa_edges, use_stmt);
}
}
}
if (stmt_ends_bb_p (stmt))
{
edge e;
+ edge_iterator ei;
basic_block bb = bb_for_stmt (stmt);
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
add_control_edge (e);
}
}
/* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
drain. This pops statements off the given WORKLIST and processes
- them until there are no more statements on WORKLIST. */
+ them until there are no more statements on WORKLIST.
+ We take a pointer to WORKLIST because it may be reallocated when an
+ SSA edge is added to it in simulate_stmt. */
static void
-process_ssa_edge_worklist (varray_type *worklist)
+process_ssa_edge_worklist (VEC(tree) **worklist)
{
/* Drain the entire worklist. */
- while (VARRAY_ACTIVE_SIZE (*worklist) > 0)
+ while (VEC_length (tree, *worklist) > 0)
{
basic_block bb;
/* Pull the statement to simulate off the worklist. */
- tree stmt = VARRAY_TOP_TREE (*worklist);
- VARRAY_POP (*worklist);
+ tree stmt = VEC_pop (tree, *worklist);
/* If this statement was already visited by simulate_block, then
we don't need to visit it again here. */
block_stmt_iterator j;
unsigned int normal_edge_count;
edge e, normal_edge;
+ edge_iterator ei;
/* Note that we have simulated this block. */
SET_BIT (executable_blocks, block->index);
worklist. */
normal_edge_count = 0;
normal_edge = NULL;
- for (e = block->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, block->succs)
{
if (e->flags & EDGE_ABNORMAL)
add_control_edge (e);
ssa_prop_init (void)
{
edge e;
+ edge_iterator ei;
basic_block bb;
/* Worklists of SSA edges. */
- VARRAY_TREE_INIT (interesting_ssa_edges, 20, "interesting_ssa_edges");
- VARRAY_TREE_INIT (varying_ssa_edges, 20, "varying_ssa_edges");
+ interesting_ssa_edges = VEC_alloc (tree, 20);
+ varying_ssa_edges = VEC_alloc (tree, 20);
executable_blocks = sbitmap_alloc (last_basic_block);
sbitmap_zero (executable_blocks);
VARRAY_BB_INIT (cfg_blocks, 20, "cfg_blocks");
- /* Initially assume that every edge in the CFG is not executable. */
- FOR_EACH_BB (bb)
+ /* Initially assume that every edge in the CFG is not executable
+ (including the edges coming out of ENTRY_BLOCK_PTR). */
+ FOR_ALL_BB (bb)
{
block_stmt_iterator si;
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
STMT_IN_SSA_EDGE_WORKLIST (bsi_stmt (si)) = 0;
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
e->flags &= ~EDGE_EXECUTABLE;
}
/* Seed the algorithm by adding the successors of the entry block to the
edge worklist. */
- for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
- {
- if (e->dest != EXIT_BLOCK_PTR)
- {
- e->flags |= EDGE_EXECUTABLE;
- cfg_blocks_add (e->dest);
- }
- }
+ FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
+ add_control_edge (e);
}
static void
ssa_prop_fini (void)
{
- interesting_ssa_edges = NULL;
- varying_ssa_edges = NULL;
+ VEC_free (tree, interesting_ssa_edges);
+ VEC_free (tree, varying_ssa_edges);
cfg_blocks = NULL;
sbitmap_free (bb_in_list);
sbitmap_free (executable_blocks);
ssa_op_iter iter;
/* Verify the constant folded result is valid gimple. */
- if (TREE_CODE_CLASS (code) == '2')
+ if (TREE_CODE_CLASS (code) == tcc_binary)
{
if (!is_gimple_val (TREE_OPERAND (expr, 0))
|| !is_gimple_val (TREE_OPERAND (expr, 1)))
return false;
}
- else if (TREE_CODE_CLASS (code) == '1')
+ else if (TREE_CODE_CLASS (code) == tcc_unary)
{
if (!is_gimple_val (TREE_OPERAND (expr, 0)))
return false;
}
+ else if (code == COMPOUND_EXPR)
+ return false;
switch (TREE_CODE (stmt))
{
/* Iterate until the worklists are empty. */
while (!cfg_blocks_empty_p ()
- || VARRAY_ACTIVE_SIZE (interesting_ssa_edges) > 0
- || VARRAY_ACTIVE_SIZE (varying_ssa_edges) > 0)
+ || VEC_length (tree, interesting_ssa_edges) > 0
+ || VEC_length (tree, varying_ssa_edges) > 0)
{
if (!cfg_blocks_empty_p ())
{
OSDN Git Service
