This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] O(1) PHI argument look-up - Part 1/n
Hi Diego,
> > Can I go with the original patch except that I address the comment
> > issues above?
> >
> Sure.
Here is the final patch that I committed.
Kazu Hirata
2004-11-19 Kazu Hirata <kazu@cs.umass.edu>
* basic-block.h (edge_def): Add dest_idx.
* cfg.c (unchecked_make_edge): Initialize dest_idx.
(remove_edge): Simplify the disconnection of an edge from its
destination.
(redirect_edge_succ): Likewise.
* cfghooks.c (verify_flow_info): Check the consistency of
dest_idx for each edge.
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.227
diff -u -d -p -r1.227 basic-block.h
--- basic-block.h 17 Nov 2004 22:05:58 -0000 1.227
+++ basic-block.h 19 Nov 2004 22:06:58 -0000
@@ -154,6 +154,10 @@ struct edge_def GTY(())
int probability; /* biased by REG_BR_PROB_BASE */
gcov_type count; /* Expected number of executions calculated
in profile.c */
+
+ /* The index number corresponding to this edge in the edge vector
+ dest->preds. */
+ unsigned int dest_idx;
};
typedef struct edge_def *edge;
Index: cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfg.c,v
retrieving revision 1.73
diff -u -d -p -r1.73 cfg.c
--- cfg.c 9 Nov 2004 04:21:49 -0000 1.73
+++ cfg.c 19 Nov 2004 22:06:58 -0000
@@ -276,6 +276,7 @@ unchecked_make_edge (basic_block src, ba
e->src = src;
e->dest = dst;
e->flags = flags;
+ e->dest_idx = EDGE_COUNT (dst->preds) - 1;
return e;
}
@@ -355,11 +356,13 @@ remove_edge (edge e)
{
edge tmp;
basic_block src, dest;
+ unsigned int dest_idx;
bool found = false;
edge_iterator ei;
src = e->src;
dest = e->dest;
+ dest_idx = e->dest_idx;
for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
{
@@ -375,20 +378,12 @@ remove_edge (edge e)
gcc_assert (found);
- found = false;
- for (ei = ei_start (dest->preds); (tmp = ei_safe_edge (ei)); )
- {
- if (tmp == e)
- {
- VEC_unordered_remove (edge, dest->preds, ei.index);
- found = true;
- break;
- }
- else
- ei_next (&ei);
- }
+ VEC_unordered_remove (edge, dest->preds, dest_idx);
- gcc_assert (found);
+ /* If we removed an edge in the middle of the edge vector, we need
+ to update dest_idx of the edge that moved into the "hole". */
+ if (dest_idx < EDGE_COUNT (dest->preds))
+ EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
free_edge (e);
}
@@ -398,28 +393,20 @@ remove_edge (edge e)
void
redirect_edge_succ (edge e, basic_block new_succ)
{
- edge tmp;
- edge_iterator ei;
- bool found = false;
+ basic_block dest = e->dest;
+ unsigned int dest_idx = e->dest_idx;
- /* Disconnect the edge from the old successor block. */
- for (ei = ei_start (e->dest->preds); (tmp = ei_safe_edge (ei)); )
- {
- if (tmp == e)
- {
- VEC_unordered_remove (edge, e->dest->preds, ei.index);
- found = true;
- break;
- }
- else
- ei_next (&ei);
- }
+ VEC_unordered_remove (edge, dest->preds, dest_idx);
- gcc_assert (found);
+ /* If we removed an edge in the middle of the edge vector, we need
+ to update dest_idx of the edge that moved into the "hole". */
+ if (dest_idx < EDGE_COUNT (dest->preds))
+ EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
/* Reconnect the edge to the new successor block. */
VEC_safe_push (edge, new_succ->preds, e);
e->dest = new_succ;
+ e->dest_idx = EDGE_COUNT (new_succ->preds) - 1;
}
/* Like previous but avoid possible duplicate edge. */
Index: cfghooks.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfghooks.c,v
retrieving revision 1.18
diff -u -d -p -r1.18 cfghooks.c
--- cfghooks.c 4 Nov 2004 22:02:55 -0000 1.18
+++ cfghooks.c 19 Nov 2004 22:06:58 -0000
@@ -178,6 +178,20 @@ verify_flow_info (void)
fputc ('\n', stderr);
err = 1;
}
+
+ if (ei.index != e->dest_idx)
+ {
+ error ("basic block %d pred edge is corrupted", bb->index);
+ error ("its dest_idx should be %d, not %d",
+ ei.index, e->dest_idx);
+ fputs ("Predecessor: ", stderr);
+ dump_edge_info (stderr, e, 0);
+ fputs ("\nSuccessor: ", stderr);
+ dump_edge_info (stderr, e, 1);
+ fputc ('\n', stderr);
+ err = 1;
+ }
+
edge_checksum[e->dest->index + 2] -= (size_t) e;
}
}