This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] O(1) PHI argument look-up - Part 10/n
- From: Kazu Hirata <kazu at cs dot umass dot edu>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 23 Nov 2004 11:15:26 -0500 (EST)
- Subject: [patch] O(1) PHI argument look-up - Part 10/n
Hi,
Attached is a patch to part 10 of my O(1) PHI argument look-up patch.
This is the meat of my O(1) PHI argument look-up patch series. After
this patch, all I have left after this patch is a bunch of clean-up
patches.
With this patch, a PHI array and the corresponding edge vector are
lined up. In add_phi_arg, we use E->dest_idx to locate the PHI
argument.
Since a PHI array and the corresponding edge vector are lined up, we
*always* have a PHI argument for each edge. Sometimes we may not add
PHI arguments until long after adding or redirecting an edge. In
order to cope with this situation, I put NULL_TREE in the
corresponding slot to represent a "missing PHI argument". This change
affects ssa_remove_edge. Specifically, we can no longer expect -1
from phi_arg_from_edge. Instead, we need to check PHI_ARG_DEF to see
if it is NULL_TREE. (Other uses of phi_arg_from_edge that checks for
-1 will be visited in future patches because they are safe.)
Since a PHI array and the corresponding edge vector are lined up, we
no longer need an edge for each PHI argument. The patch removes edge
E from phi_arg_d and redefines PHI_ARG_EDGE in in terms of EDGE_PRED.
All write accesses to PHI_ARG_EDGE are eliminated.
Since a PHI array and the corresponding edge vector are lined up,
phi_arg_from_edge no longer has to do a linear search. We can just
return e->dest_idx.
verify_phi_args have several changes. Again, the patch introduces the
new way to represent a "missing PHI argument", so we cannot possibly
have two PHI arguments for any edge because a PHI array and the
corresponding edge vector are lined up. I hope changes to
verify_phi_args are self-explnatory.
Tested on i686-pc-linux-gnu. OK to apply?
Kazu Hirata
2004-11-23 Kazu Hirata <kazu@cs.umass.edu>
* tree-phinode.c (resize_phi_node): Abort when LEN is strictly
greater than PHI_ARG_CAPACITY.
(reserve_phi_args_for_new_edge): Initialize the new PHI
argument to NULL_TREE. Increment PHI_NUM_ARGS.
(add_phi_arg): Add a PHI argument to the slot given by
E->dest_idx.
(remove_phi_arg_num): Do not write to PHI_ARG_EDGE.
* tree-flow-inline (phi_arg_from_edge): Return E->dest_idx.
* tree-ssa.c (ssa_redirect_edge): Check for a missing PHI
argument by looking at PHI_ARG_DEF.
(verify_phi_args): Check for a missing PHI argument. Remove
the check for duplicate PHI arguments.
* tree.h (PHI_ARG_EDGE): Redefine in terms of EDGE_PRED.
(phi_arg_d): Remove e.
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow-inline.h,v
retrieving revision 2.25
diff -u -d -p -r2.25 tree-flow-inline.h
--- tree-flow-inline.h 27 Oct 2004 17:45:19 -0000 2.25
+++ tree-flow-inline.h 23 Nov 2004 13:46:31 -0000
@@ -393,15 +393,9 @@ set_phi_nodes (basic_block bb, tree l)
static inline int
phi_arg_from_edge (tree phi, edge e)
{
- int i;
gcc_assert (phi);
gcc_assert (TREE_CODE (phi) == PHI_NODE);
-
- for (i = 0; i < PHI_NUM_ARGS (phi); i++)
- if (PHI_ARG_EDGE (phi, i) == e)
- return i;
-
- return -1;
+ return e->dest_idx;
}
/* Mark VAR as used, so that it'll be preserved during rtl expansion. */
Index: tree-phinodes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-phinodes.c,v
retrieving revision 2.25
diff -u -d -p -r2.25 tree-phinodes.c
--- tree-phinodes.c 23 Nov 2004 13:44:22 -0000 2.25
+++ tree-phinodes.c 23 Nov 2004 13:46:31 -0000
@@ -212,13 +212,13 @@ make_phi_node (tree var, int len)
phi = allocate_phi_node (capacity);
- /* We do not have to clear a part of the PHI node that stores PHI
- arguments, which is safe because we tell the garbage collector to
- scan up to num_args elements in the array of PHI arguments. In
- other words, the garbage collector will not follow garbage
- pointers in the unused portion of the array. */
- memset (phi, 0, sizeof (struct tree_phi_node) - sizeof (struct phi_arg_d));
+ /* We need to clear the entire PHI node, including the argument
+ portion, because we represent a "missing PHI argument" by placing
+ NULL_TREE in PHI_ARG_DEF. */
+ memset (phi, 0, (sizeof (struct tree_phi_node) - sizeof (struct phi_arg_d)
+ + sizeof (struct phi_arg_d) * len));
TREE_SET_CODE (phi, PHI_NODE);
+ PHI_NUM_ARGS (phi) = len;
PHI_ARG_CAPACITY (phi) = capacity;
TREE_TYPE (phi) = TREE_TYPE (var);
if (TREE_CODE (var) == SSA_NAME)
@@ -253,7 +253,7 @@ resize_phi_node (tree *phi, int len)
int old_size;
tree new_phi;
- gcc_assert (len >= PHI_ARG_CAPACITY (*phi));
+ gcc_assert (len > PHI_ARG_CAPACITY (*phi));
/* The garbage collector will not look at the PHI node beyond the
first PHI_NUM_ARGS elements. Therefore, all we have to copy is a
@@ -294,6 +294,17 @@ reserve_phi_args_for_new_edge (basic_blo
release_phi_node (old_phi);
}
+
+ /* We represent a "missing PHI argument" by placing NULL_TREE in
+ the corresponding slot. If PHI arguments were added
+ immediately after an edge is created, this zeroing would not
+ be necessary, but unfortunately this is not the case. For
+ example, the loop optimizer duplicates several basic blocks,
+ redirects edges, and then fixes up PHI arguments later in
+ batch. */
+ SET_PHI_ARG_DEF (*loc, len - 1, NULL_TREE);
+
+ PHI_NUM_ARGS (*loc)++;
}
}
@@ -326,13 +337,16 @@ void
add_phi_arg (tree *phi, tree def, edge e)
{
basic_block bb = e->dest;
- int i = PHI_NUM_ARGS (*phi);
gcc_assert (bb == bb_for_stmt (*phi));
/* We resize PHI nodes upon edge creation. We should always have
enough room at this point. */
- gcc_assert (PHI_NUM_ARGS (*phi) < PHI_ARG_CAPACITY (*phi));
+ gcc_assert (PHI_NUM_ARGS (*phi) <= PHI_ARG_CAPACITY (*phi));
+
+ /* We resize PHI nodes upon edge creation. We should always have
+ enough room at this point. */
+ gcc_assert (e->dest_idx < (unsigned int) PHI_NUM_ARGS (*phi));
/* Copy propagation needs to know what object occur in abnormal
PHI nodes. This is a convenient place to record such information. */
@@ -342,10 +356,8 @@ add_phi_arg (tree *phi, tree def, edge e
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (*phi)) = 1;
}
- SET_PHI_ARG_DEF (*phi, i, def);
- PHI_ARG_EDGE (*phi, i) = e;
- PHI_ARG_NONZERO (*phi, i) = false;
- PHI_NUM_ARGS (*phi)++;
+ SET_PHI_ARG_DEF (*phi, e->dest_idx, def);
+ PHI_ARG_NONZERO (*phi, e->dest_idx) = false;
}
/* Remove the Ith argument from PHI's argument list. This routine assumes
@@ -365,14 +377,13 @@ remove_phi_arg_num (tree phi, int i)
if (i != num_elem - 1)
{
SET_PHI_ARG_DEF (phi, i, PHI_ARG_DEF (phi, num_elem - 1));
- PHI_ARG_EDGE (phi, i) = PHI_ARG_EDGE (phi, num_elem - 1);
PHI_ARG_NONZERO (phi, i) = PHI_ARG_NONZERO (phi, num_elem - 1);
}
/* Shrink the vector and return. Note that we do not have to clear
- PHI_ARG_DEF, PHI_ARG_EDGE, or PHI_ARG_NONZERO because the garbage
- collector will not look at those elements beyond the first
- PHI_NUM_ARGS elements of the array. */
+ PHI_ARG_DEF or PHI_ARG_NONZERO because the garbage collector will
+ not look at those elements beyond the first PHI_NUM_ARGS elements
+ of the array. */
PHI_NUM_ARGS (phi)--;
}
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa.c,v
retrieving revision 2.64
diff -u -d -p -r2.64 tree-ssa.c
--- tree-ssa.c 22 Nov 2004 22:12:58 -0000 2.64
+++ tree-ssa.c 23 Nov 2004 13:46:31 -0000
@@ -64,7 +64,7 @@ ssa_redirect_edge (edge e, basic_block d
next = PHI_CHAIN (phi);
i = phi_arg_from_edge (phi, e);
- if (i < 0)
+ if (PHI_ARG_DEF (phi, i) == NULL_TREE)
continue;
src = PHI_ARG_DEF (phi, i);
@@ -277,7 +277,6 @@ verify_phi_args (tree phi, basic_block b
edge e;
bool err = false;
unsigned i, phi_num_args = PHI_NUM_ARGS (phi);
- edge_iterator ei;
if (EDGE_COUNT (bb->preds) != phi_num_args)
{
@@ -286,22 +285,27 @@ verify_phi_args (tree phi, basic_block b
goto error;
}
- /* Mark all the incoming edges. */
- FOR_EACH_EDGE (e, ei, bb->preds)
- e->aux = (void *) 1;
-
for (i = 0; i < phi_num_args; i++)
{
tree op = PHI_ARG_DEF (phi, i);
+ e = PHI_ARG_EDGE (phi, i);
+
+ if (!op)
+ {
+ error ("PHI argument is missing for edge %d->%d\n",
+ e->src->index,
+ e->dest->index);
+ err = true;
+ goto error;
+ }
+
if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op))
{
error ("PHI argument is not SSA_NAME, or invariant");
err = true;
}
- e = PHI_ARG_EDGE (phi, i);
-
if (TREE_CODE (op) == SSA_NAME)
err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
phi, e->flags & EDGE_ABNORMAL,
@@ -315,21 +319,12 @@ verify_phi_args (tree phi, basic_block b
err = true;
}
- if (e->aux == (void *) 0)
- {
- error ("PHI argument flowing through dead or duplicated edge %d->%d\n",
- e->src->index, e->dest->index);
- err = true;
- }
-
if (err)
{
fprintf (stderr, "PHI argument\n");
print_generic_stmt (stderr, op, TDF_VOPS);
goto error;
}
-
- e->aux = (void *) 0;
}
error:
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.658
diff -u -d -p -r1.658 tree.h
--- tree.h 23 Nov 2004 01:27:41 -0000 1.658
+++ tree.h 23 Nov 2004 13:46:32 -0000
@@ -1374,7 +1374,7 @@ struct tree_ssa_name GTY(())
#define PHI_NUM_ARGS(NODE) PHI_NODE_CHECK (NODE)->phi.num_args
#define PHI_ARG_CAPACITY(NODE) PHI_NODE_CHECK (NODE)->phi.capacity
#define PHI_ARG_ELT(NODE, I) PHI_NODE_ELT_CHECK (NODE, I)
-#define PHI_ARG_EDGE(NODE, I) PHI_NODE_ELT_CHECK (NODE, I).e
+#define PHI_ARG_EDGE(NODE, I) (EDGE_PRED (bb_for_stmt ((NODE)), (I)))
#define PHI_ARG_NONZERO(NODE, I) PHI_NODE_ELT_CHECK (NODE, I).nonzero
#define PHI_BB(NODE) PHI_NODE_CHECK (NODE)->phi.bb
#define PHI_DF(NODE) PHI_NODE_CHECK (NODE)->phi.df
@@ -1384,7 +1384,6 @@ struct edge_def;
struct phi_arg_d GTY(())
{
tree def;
- struct edge_def * GTY((skip (""))) e;
bool nonzero;
};