[tree-ssa] CCP speedups and improvements
Jeff Law
law@porcupine.slc.redhat.com
Fri Aug 23 09:54:00 GMT 2002
The SSA-CCP code (both tree & RTL versions) was making a number of
calls to find_index_edge which is *very* expensive and in some cases
these calls would dominate compile-time performance.
Those calls fall into two categories.
1. Get the index so that we can test the executable state of the
edge in a bitmap.
2. Management of the edge worklist.
#1 is addressed by moving the executable bit into the flags field of the
edge structure.
#2 is addressed by converting the worklist into a VARRAY of edges we need
to revisit.
Those changes drastically reduce the amount of time spent in SSA-CCP on
certain files.
Additionally, this change includes an implementation of
optimize_unexecutable_edges for tree-ssa-ccp. It basically simplifies
PHI nodes and the CFG when we find unexecutable edges.
I've bootstrapped the tree-ssa branch with tree ssa ccp enabled. There's
a comparison failure (insn-emit), but the comparison failure is unrelated
to my changes.
* basic-block.h (EDGE_EXECUTABLE): New edge flag.
* cfganal.c (find_edge): New function.
* ssa-ccp.c: Convert to use EDGE_EXECUTABLE bit in the
edge flags rather than a bitmap. Convert edge worklist
into a varray. Avoids expensive find_index_edge calls.
* tree-ssa-ccp.c: Likewise.
* tree-flow.h (tree_ssa_remove_phi_alternative): Declare.
* tree-ssa.c (tree_ssa_remove_phi_alternative): New function.
* tree-ssa-ccp.c (optimize_unexecutable_edges): Remove
PHI alternatives for unexecutable edges. Also remove
unexecutable edges from the CFG.
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.153.2.8
diff -c -3 -p -r1.153.2.8 basic-block.h
*** basic-block.h 16 Aug 2002 15:50:33 -0000 1.153.2.8
--- basic-block.h 23 Aug 2002 16:46:46 -0000
*************** typedef struct edge_def {
*** 149,154 ****
--- 149,156 ----
predicate is non zero. */
#define EDGE_FALSE_VALUE 256 /* Edge taken when controlling
predicate is zero. */
+ #define EDGE_EXECUTABLE 512 /* Edge is executable. Only
+ valid during SSA-CCP. */
#define EDGE_COMPLEX (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH)
*************** void print_edge_list PARAMS ((FILE *,
*** 629,634 ****
--- 631,637 ----
void verify_edge_list PARAMS ((FILE *, struct edge_list *));
int find_edge_index PARAMS ((struct edge_list *,
basic_block, basic_block));
+ edge find_edge PARAMS ((basic_block, basic_block));
enum update_life_extent
Index: cfganal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfganal.c,v
retrieving revision 1.25.2.1
diff -c -3 -p -r1.25.2.1 cfganal.c
*** cfganal.c 12 Aug 2002 01:33:11 -0000 1.25.2.1
--- cfganal.c 23 Aug 2002 16:46:51 -0000
*************** verify_edge_list (f, elist)
*** 573,578 ****
--- 573,594 ----
}
}
+ /* Given PRED and SUCC blocks, return the edge which connects the blocks.
+ If no such edge exists, return NULL. */
+
+ edge
+ find_edge (pred, succ)
+ basic_block pred, succ;
+ {
+ edge e;
+
+ for (e = pred->succ; e; e = e->succ_next)
+ if (e->dest == succ)
+ return e;
+
+ return NULL;
+ }
+
/* This routine will determine what, if any, edge there is between
a specified predecessor and successor. */
Index: ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ssa-ccp.c,v
retrieving revision 1.25.2.1
diff -c -3 -p -r1.25.2.1 ssa-ccp.c
*** ssa-ccp.c 31 Jul 2002 18:07:45 -0000 1.25.2.1
--- ssa-ccp.c 23 Aug 2002 16:46:53 -0000
*************** static value *values;
*** 99,109 ****
/* A bitmap to keep track of executable blocks in the CFG. */
static sbitmap executable_blocks;
- /* A bitmap for all executable edges in the CFG. */
- static sbitmap executable_edges;
-
/* Array of edges on the work list. */
! static edge *edge_info;
/* We need an edge list to be able to get indexes easily. */
static struct edge_list *edges;
--- 99,106 ----
/* A bitmap to keep track of executable blocks in the CFG. */
static sbitmap executable_blocks;
/* Array of edges on the work list. */
! static varray_type edge_info;
/* We need an edge list to be able to get indexes easily. */
static struct edge_list *edges;
*************** static struct edge_list *edges;
*** 111,126 ****
/* For building/following use-def and def-use chains. */
static struct df *df_analyzer;
- /* Current edge we are operating on, from the worklist */
- static edge flow_edges;
-
/* Bitmap of SSA edges which will need reexamination as their definition
has changed. */
static sbitmap ssa_edges;
/* Simple macros to simplify code */
#define SSA_NAME(x) REGNO (SET_DEST (x))
- #define EIE(x,y) EDGE_INDEX (edges, x, y)
static void visit_phi_node PARAMS ((rtx, basic_block));
static void visit_expression PARAMS ((rtx, basic_block));
--- 108,119 ----
*************** static void defs_to_varying P
*** 129,135 ****
static void examine_flow_edges PARAMS ((void));
static int mark_references PARAMS ((rtx *, void *));
static void follow_def_use_chains PARAMS ((void));
! static void optimize_unexecutable_edges PARAMS ((struct edge_list *,
sbitmap));
static void ssa_ccp_substitute_constants PARAMS ((void));
static void ssa_ccp_df_delete_unreachable_insns PARAMS ((void));
static void ssa_fast_dce PARAMS ((struct df *));
--- 122,128 ----
static void examine_flow_edges PARAMS ((void));
static int mark_references PARAMS ((rtx *, void *));
static void follow_def_use_chains PARAMS ((void));
! static void optimize_unexecutable_edges PARAMS ((struct edge_list *));
static void ssa_ccp_substitute_constants PARAMS ((void));
static void ssa_ccp_df_delete_unreachable_insns PARAMS ((void));
static void ssa_fast_dce PARAMS ((struct df *));
*************** visit_phi_node (phi_node, block)
*** 151,159 ****
for (i = 0; i < num_elem; i += 2)
{
! if (TEST_BIT (executable_edges,
! EIE (BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, i + 1))),
! block)))
{
unsigned int current_parm
= REGNO (RTVEC_ELT (phi_vec, i));
--- 144,153 ----
for (i = 0; i < num_elem; i += 2)
{
! edge e;
!
! e = find_edge (BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, i + 1))),
block);
! if (e->flags & EDGE_EXECUTABLE)
{
unsigned int current_parm
= REGNO (RTVEC_ELT (phi_vec, i));
*************** visit_expression (insn, block)
*** 258,271 ****
for (curredge = block->succ; curredge;
curredge = curredge->succ_next)
{
! int index = EIE (curredge->src, curredge->dest);
!
! if (TEST_BIT (executable_edges, index))
continue;
! SET_BIT (executable_edges, index);
! edge_info[index] = flow_edges;
! flow_edges = curredge;
}
}
--- 252,262 ----
for (curredge = block->succ; curredge;
curredge = curredge->succ_next)
{
! if (curredge->flags & EDGE_EXECUTABLE)
continue;
! curredge->flags |= EDGE_EXECUTABLE;
! VARRAY_PUSH_GENERIC_PTR (edge_info, curredge);
}
}
*************** visit_expression (insn, block)
*** 341,354 ****
for (curredge = block->succ; curredge;
curredge = curredge->succ_next)
{
! int index = EIE (curredge->src, curredge->dest);
!
! if (TEST_BIT (executable_edges, index))
continue;
! SET_BIT (executable_edges, index);
! edge_info[index] = flow_edges;
! flow_edges = curredge;
}
}
else
--- 332,342 ----
for (curredge = block->succ; curredge;
curredge = curredge->succ_next)
{
! if (curredge->flags & EDGE_EXECUTABLE)
continue;
! curredge->flags |= EDGE_EXECUTABLE;
! VARRAY_PUSH_GENERIC_PTR (edge_info, curredge);
}
}
else
*************** visit_expression (insn, block)
*** 381,394 ****
for (curredge = block->succ; curredge;
curredge = curredge->succ_next)
{
! int index = EIE (curredge->src, curredge->dest);
!
! if (TEST_BIT (executable_edges, index))
continue;
! SET_BIT (executable_edges, index);
! edge_info[index] = flow_edges;
! flow_edges = curredge;
}
return;
}
--- 369,379 ----
for (curredge = block->succ; curredge;
curredge = curredge->succ_next)
{
! if (curredge->flags & EDGE_EXECUTABLE)
continue;
! curredge->flags |= EDGE_EXECUTABLE;
! VARRAY_PUSH_GENERIC_PTR (edge_info, curredge);
}
return;
}
*************** visit_expression (insn, block)
*** 417,425 ****
for (curredge = block->succ; curredge;
curredge = curredge->succ_next)
{
! int index = EIE (curredge->src, curredge->dest);
!
! if (TEST_BIT (executable_edges, index))
continue;
/* If we were unable to simplify the expression at this
--- 402,408 ----
for (curredge = block->succ; curredge;
curredge = curredge->succ_next)
{
! if (curredge->flags & EDGE_EXECUTABLE)
continue;
/* If we were unable to simplify the expression at this
*************** visit_expression (insn, block)
*** 438,446 ****
|| (GET_CODE (x) == LABEL_REF
&& ! (curredge->flags & EDGE_FALLTHRU)))
{
! SET_BIT (executable_edges, index);
! edge_info[index] = flow_edges;
! flow_edges = curredge;
}
}
}
--- 421,428 ----
|| (GET_CODE (x) == LABEL_REF
&& ! (curredge->flags & EDGE_FALLTHRU)))
{
! curredge->flags |= EDGE_EXECUTABLE;
! VARRAY_PUSH_GENERIC_PTR (edge_info, curredge);
}
}
}
*************** visit_expression (insn, block)
*** 625,638 ****
static void
examine_flow_edges ()
{
! while (flow_edges != NULL)
{
basic_block succ_block;
rtx curr_phi_node;
/* Pull the next block to simulate off the worklist. */
! succ_block = flow_edges->dest;
! flow_edges = edge_info[EIE (flow_edges->src, flow_edges->dest)];
/* There is nothing to do for the exit block. */
if (succ_block == EXIT_BLOCK_PTR)
--- 607,620 ----
static void
examine_flow_edges ()
{
! while (VARRAY_ACTIVE_SIZE (edge_info) > 0)
{
basic_block succ_block;
rtx curr_phi_node;
/* Pull the next block to simulate off the worklist. */
! succ_block = ((edge)VARRAY_TOP_GENERIC_PTR (edge_info))->dest;
! VARRAY_POP (edge_info);
/* There is nothing to do for the exit block. */
if (succ_block == EXIT_BLOCK_PTR)
*************** examine_flow_edges ()
*** 675,687 ****
so we don't have to wait for cprop to tell us. */
if (succ_edge != NULL
&& succ_edge->succ_next == NULL
! && !TEST_BIT (executable_edges,
! EIE (succ_edge->src, succ_edge->dest)))
{
! SET_BIT (executable_edges,
! EIE (succ_edge->src, succ_edge->dest));
! edge_info[EIE (succ_edge->src, succ_edge->dest)] = flow_edges;
! flow_edges = succ_edge;
}
}
}
--- 657,666 ----
so we don't have to wait for cprop to tell us. */
if (succ_edge != NULL
&& succ_edge->succ_next == NULL
! && !(succ_edge->flags & EDGE_EXECUTABLE))
{
! succ_edge->flags |= EDGE_EXECUTABLE;
! VARRAY_PUSH_GENERIC_PTR (edge_info, succ_edge);
}
}
}
*************** follow_def_use_chains ()
*** 734,752 ****
the edge from the CFG. Note we do not delete unreachable blocks
yet as the DF analyzer can not deal with that yet. */
static void
! optimize_unexecutable_edges (edges, executable_edges)
struct edge_list *edges;
- sbitmap executable_edges;
{
int i;
basic_block bb;
for (i = 0; i < NUM_EDGES (edges); i++)
{
! if (!TEST_BIT (executable_edges, i))
! {
! edge edge = INDEX_EDGE (edges, i);
if (edge->flags & EDGE_ABNORMAL)
continue;
--- 713,730 ----
the edge from the CFG. Note we do not delete unreachable blocks
yet as the DF analyzer can not deal with that yet. */
static void
! optimize_unexecutable_edges (edges)
struct edge_list *edges;
{
int i;
basic_block bb;
for (i = 0; i < NUM_EDGES (edges); i++)
{
! edge edge = INDEX_EDGE (edges, i);
+ if (! (edge->flags & EDGE_EXECUTABLE))
+ {
if (edge->flags & EDGE_ABNORMAL)
continue;
*************** ssa_const_prop ()
*** 1015,1034 ****
executable_blocks = sbitmap_alloc (last_basic_block);
sbitmap_zero (executable_blocks);
! executable_edges = sbitmap_alloc (NUM_EDGES (edges));
! sbitmap_zero (executable_edges);
! edge_info = (edge *) xmalloc (NUM_EDGES (edges) * sizeof (edge));
! flow_edges = ENTRY_BLOCK_PTR->succ;
/* Add the successors of the entry block to the edge worklist. That
is enough of a seed to get SSA-CCP started. */
for (curredge = ENTRY_BLOCK_PTR->succ; curredge;
curredge = curredge->succ_next)
{
! int index = EIE (curredge->src, curredge->dest);
! SET_BIT (executable_edges, index);
! edge_info[index] = curredge->succ_next;
}
/* Iterate until until the worklists are empty. */
--- 993,1010 ----
executable_blocks = sbitmap_alloc (last_basic_block);
sbitmap_zero (executable_blocks);
! for (i = 0; i < NUM_EDGES (edges); i++)
! edges->index_to_edge[i]->flags &= ~EDGE_EXECUTABLE;
! VARRAY_GENERIC_PTR_INIT (edge_info, NUM_EDGES (edges) / 2, "edge_info");
/* Add the successors of the entry block to the edge worklist. That
is enough of a seed to get SSA-CCP started. */
for (curredge = ENTRY_BLOCK_PTR->succ; curredge;
curredge = curredge->succ_next)
{
! curredge->flags |= EDGE_EXECUTABLE;
! VARRAY_PUSH_GENERIC_PTR (edge_info, curredge);
}
/* Iterate until until the worklists are empty. */
*************** ssa_const_prop ()
*** 1037,1050 ****
examine_flow_edges ();
follow_def_use_chains ();
}
! while (flow_edges != NULL);
/* Now perform substitutions based on the known constant values. */
ssa_ccp_substitute_constants ();
/* Remove unexecutable edges from the CFG and make appropriate
adjustments to PHI nodes. */
! optimize_unexecutable_edges (edges, executable_edges);
/* Now remove all unreachable insns and update the DF information.
as appropriate. */
--- 1013,1026 ----
examine_flow_edges ();
follow_def_use_chains ();
}
! while (VARRAY_ACTIVE_SIZE (edge_info) > 0);
/* Now perform substitutions based on the known constant values. */
ssa_ccp_substitute_constants ();
/* Remove unexecutable edges from the CFG and make appropriate
adjustments to PHI nodes. */
! optimize_unexecutable_edges (edges);
/* Now remove all unreachable insns and update the DF information.
as appropriate. */
*************** ssa_const_prop ()
*** 1071,1079 ****
free (values);
values = NULL;
- free (edge_info);
- edge_info = NULL;
-
sbitmap_free (executable_blocks);
executable_blocks = NULL;
--- 1047,1052 ----
*************** ssa_const_prop ()
*** 1082,1090 ****
free_edge_list (edges);
edges = NULL;
-
- sbitmap_free (executable_edges);
- executable_edges = NULL;
df_finish (df_analyzer);
end_alias_analysis ();
--- 1055,1060 ----
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.11
diff -c -3 -p -r1.1.2.11 tree-ssa-ccp.c
*** tree-ssa-ccp.c 22 Aug 2002 19:21:35 -0000 1.1.2.11
--- tree-ssa-ccp.c 23 Aug 2002 16:47:24 -0000
*************** static value *values;
*** 94,111 ****
/* A bitmap to keep track of executable blocks in the CFG. */
static sbitmap executable_blocks;
- /* A bitmap for all executable edges in the CFG. */
- static sbitmap executable_edges;
-
/* Array of control flow edges on the worklist. */
! static edge *edge_info;
/* We need an control flow edge list to be able to get indexes easily. */
static struct edge_list *edges;
- /* Current control flow edge we are operating on, from the worklist. */
- static edge flow_edges;
-
/* Worklist of SSA edges which will need reexamination as their definition
has changed. SSA edges are def-use edges in the SSA web. For each
edge, we store the originating VARDEF/VARPHI reference D. The destination
--- 94,105 ----
/* A bitmap to keep track of executable blocks in the CFG. */
static sbitmap executable_blocks;
/* Array of control flow edges on the worklist. */
! static varray_type edge_info;
/* We need an control flow edge list to be able to get indexes easily. */
static struct edge_list *edges;
/* Worklist of SSA edges which will need reexamination as their definition
has changed. SSA edges are def-use edges in the SSA web. For each
edge, we store the originating VARDEF/VARPHI reference D. The destination
*************** static void def_to_varying P
*** 127,133 ****
static void set_lattice_value PARAMS ((varref, value));
static void simulate_block PARAMS ((basic_block));
static void simulate_def_use_chains PARAMS ((varref));
! static void optimize_unexecutable_edges PARAMS ((struct edge_list *,
sbitmap));
static void ssa_ccp_substitute_constants PARAMS ((void));
static void ssa_ccp_df_delete_unreachable_insns PARAMS ((void));
static value evaluate_expr PARAMS ((tree));
--- 121,127 ----
static void set_lattice_value PARAMS ((varref, value));
static void simulate_block PARAMS ((basic_block));
static void simulate_def_use_chains PARAMS ((varref));
! static void optimize_unexecutable_edges PARAMS ((struct edge_list *));
static void ssa_ccp_substitute_constants PARAMS ((void));
static void ssa_ccp_df_delete_unreachable_insns PARAMS ((void));
static value evaluate_expr PARAMS ((tree));
*************** tree_ssa_ccp (fndecl)
*** 161,173 ****
initialize ();
/* Iterate until the worklists are empty. */
! while (flow_edges != NULL || ssa_edges->last != NULL)
{
! if (flow_edges)
{
/* Pull the next block to simulate off the worklist. */
! basic_block dest_block = flow_edges->dest;
! flow_edges = edge_info[EIE (flow_edges->src, flow_edges->dest)];
simulate_block (dest_block);
}
--- 155,169 ----
initialize ();
/* Iterate until the worklists are empty. */
! while (VARRAY_ACTIVE_SIZE (edge_info) > 0 || ssa_edges->last != NULL)
{
! if (VARRAY_ACTIVE_SIZE (edge_info) > 0)
{
/* Pull the next block to simulate off the worklist. */
! basic_block dest_block;
!
! dest_block = ((edge)VARRAY_TOP_GENERIC_PTR (edge_info))->dest;
! VARRAY_POP (edge_info);
simulate_block (dest_block);
}
*************** tree_ssa_ccp (fndecl)
*** 184,192 ****
/* Now perform substitutions based on the known constant values. */
ssa_ccp_substitute_constants ();
/* Remove unexecutable edges from the CFG and make appropriate
adjustments to PHI nodes. */
! optimize_unexecutable_edges (edges, executable_edges);
/* Now remove all unreachable insns and update the DF information.
as appropriate. */
--- 180,190 ----
/* Now perform substitutions based on the known constant values. */
ssa_ccp_substitute_constants ();
+ #if 0
/* Remove unexecutable edges from the CFG and make appropriate
adjustments to PHI nodes. */
! optimize_unexecutable_edges (edges);
! #endif
/* Now remove all unreachable insns and update the DF information.
as appropriate. */
*************** simulate_block (block)
*** 263,285 ****
}
/* If we haven't looked at the next block, and it has a
! single successor, add it onto the worklist. This is because
! if we only have one successor, we know it gets executed,
! so we don't have to wait for cprop to tell us. */
if (succ_edge != NULL
&& succ_edge->succ_next == NULL
! && !TEST_BIT (executable_edges,
! EIE (succ_edge->src, succ_edge->dest)))
{
! int eix = EIE (succ_edge->src, succ_edge->dest);
!
! SET_BIT (executable_edges, eix);
! edge_info[eix] = flow_edges;
! flow_edges = succ_edge;
if (dump_file && (dump_flags & TDF_DETAILS))
! fprintf (dump_file, "Adding edge %d (%d -> %d) to worklist\n\n",
! eix, flow_edges->src->index, flow_edges->dest->index);
}
}
}
--- 261,279 ----
}
/* If we haven't looked at the next block, and it has a
! single successor, add it onto the worklist. This is because
! if we only have one successor, we know it gets executed,
! so we don't have to wait for cprop to tell us. */
if (succ_edge != NULL
&& succ_edge->succ_next == NULL
! && !(succ_edge->flags & EDGE_EXECUTABLE))
{
! succ_edge->flags |= EDGE_EXECUTABLE;
! VARRAY_PUSH_GENERIC_PTR (edge_info, succ_edge);
if (dump_file && (dump_flags & TDF_DETAILS))
! fprintf (dump_file, "Adding edge (%d -> %d) to worklist\n\n",
! succ_edge->src->index, succ_edge->dest->index);
}
}
}
*************** simulate_def_use_chains (def)
*** 323,332 ****
yet as the DF analyzer can not deal with that yet. */
static void
! optimize_unexecutable_edges (edges, executable_edges)
struct edge_list *edges ATTRIBUTE_UNUSED;
- sbitmap executable_edges ATTRIBUTE_UNUSED;
{
}
--- 317,356 ----
yet as the DF analyzer can not deal with that yet. */
static void
! optimize_unexecutable_edges (edges)
struct edge_list *edges ATTRIBUTE_UNUSED;
{
+ int i;
+
+ for (i = 0; i < NUM_EDGES (edges); i++)
+ {
+ edge edge = INDEX_EDGE (edges, i);
+
+ if (! (edge->flags & EDGE_EXECUTABLE))
+ {
+ if (edge->flags & EDGE_ABNORMAL)
+ continue;
+
+ /* We found an edge that is not executable. First simplify
+ the PHI nodes in the target block. This may make
+ simplifications possible in other optimizers. */
+ if (edge->dest != EXIT_BLOCK_PTR)
+ {
+ ref_list blockrefs = BB_REFS (edge->dest);
+ varref ref;
+ struct ref_list_node *tmp;
+
+ FOR_EACH_REF (ref, tmp, blockrefs)
+ {
+ if (VARREF_TYPE (ref) == VARPHI)
+ tree_ssa_remove_phi_alternative (ref, edge->src);
+ }
+ }
+
+ /* Since the edge was not executable, remove it from the CFG. */
+ remove_edge (edge);
+ }
+ }
}
*************** visit_phi_node (phi_node)
*** 454,464 ****
--- 478,491 ----
{
varref ref;
basic_block phiargbb, block;
+ edge e;
ref = (varref) VARRAY_GENERIC_PTR (phi_vec, i);
phiargbb = VARRAY_BB (VARDEF_PHI_CHAIN_BB (phi_node), i);
block = VARREF_BB (phi_node);
+ e = find_edge (phiargbb, block);
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\n Examining argument #%d: ", i);
*************** visit_phi_node (phi_node)
*** 467,479 ****
phiargbb->index);
fprintf (dump_file, " Edge (%d -> %d) is %sexecutable\n",
phiargbb->index, block->index,
! (TEST_BIT (executable_edges, EIE (phiargbb, block)))
? ""
: "not ");
}
/* Compute the meet operator for the current PHI argument. */
! if (TEST_BIT (executable_edges, EIE (phiargbb, block)))
{
latticevalue current_parm_lattice_val;
unsigned int current_parm = VARREF_ID (ref);
--- 494,506 ----
phiargbb->index);
fprintf (dump_file, " Edge (%d -> %d) is %sexecutable\n",
phiargbb->index, block->index,
! (e->flags & EDGE_EXECUTABLE)
? ""
: "not ");
}
/* Compute the meet operator for the current PHI argument. */
! if (e->flags & EDGE_EXECUTABLE)
{
latticevalue current_parm_lattice_val;
unsigned int current_parm = VARREF_ID (ref);
*************** visit_phi_node (phi_node)
*** 551,557 ****
- If the expression controls a conditional branch:
. If the expression evaluates to non-constant, add all edges to
! flow_edges.
. If the expression is constant, add the edge executed as the
result of the branch. */
--- 578,584 ----
- If the expression controls a conditional branch:
. If the expression evaluates to non-constant, add all edges to
! worklist.
. If the expression is constant, add the edge executed as the
result of the branch. */
*************** visit_condexpr_for (ref)
*** 710,716 ****
have not already been marked). */
for (curredge = block->succ; curredge; curredge = curredge->succ_next)
{
! int index = EIE (curredge->src, curredge->dest);
/* If this is an edge for TRUE values but the predicate is false,
then skip it. */
--- 737,743 ----
have not already been marked). */
for (curredge = block->succ; curredge; curredge = curredge->succ_next)
{
! int index;
/* If this is an edge for TRUE values but the predicate is false,
then skip it. */
*************** visit_condexpr_for (ref)
*** 724,739 ****
continue;
/* If the edge had already been added, skip it. */
! if (TEST_BIT (executable_edges, index))
continue;
! SET_BIT (executable_edges, index);
! edge_info[index] = flow_edges;
! flow_edges = curredge;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Adding edge %d (%d -> %d) to worklist\n\n",
! index, flow_edges->src->index, flow_edges->dest->index);
}
}
--- 751,765 ----
continue;
/* If the edge had already been added, skip it. */
! if (curredge->flags & EDGE_EXECUTABLE)
continue;
! curredge->flags |= EDGE_EXECUTABLE;
! VARRAY_PUSH_GENERIC_PTR (edge_info, curredge);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Adding edge %d (%d -> %d) to worklist\n\n",
! index, curredge->src->index, curredge->dest->index);
}
}
*************** initialize ()
*** 946,965 ****
executable_blocks = sbitmap_alloc (last_basic_block);
sbitmap_zero (executable_blocks);
! executable_edges = sbitmap_alloc (NUM_EDGES (edges));
! sbitmap_zero (executable_edges);
! edge_info = (edge *) xmalloc (NUM_EDGES (edges) * sizeof (edge));
! flow_edges = ENTRY_BLOCK_PTR->succ;
/* Add the successors of the entry block to the edge worklist. That
is enough of a seed to get SSA-CCP started. */
for (curredge = ENTRY_BLOCK_PTR->succ; curredge;
curredge = curredge->succ_next)
{
! int index = EIE (curredge->src, curredge->dest);
! SET_BIT (executable_edges, index);
! edge_info[index] = curredge->succ_next;
}
}
--- 972,989 ----
executable_blocks = sbitmap_alloc (last_basic_block);
sbitmap_zero (executable_blocks);
! for (i = 0; i < NUM_EDGES (edges); i++)
! edges->index_to_edge[i]->flags &= ~EDGE_EXECUTABLE;
! VARRAY_GENERIC_PTR_INIT (edge_info, NUM_EDGES (edges) / 2, "edge_info");
/* Add the successors of the entry block to the edge worklist. That
is enough of a seed to get SSA-CCP started. */
for (curredge = ENTRY_BLOCK_PTR->succ; curredge;
curredge = curredge->succ_next)
{
! curredge->flags |= EDGE_EXECUTABLE;
! VARRAY_PUSH_GENERIC_PTR (edge_info, curredge);
}
}
*************** finalize ()
*** 972,988 ****
free (values);
values = NULL;
- free (edge_info);
- edge_info = NULL;
-
- sbitmap_free (executable_blocks);
- executable_blocks = NULL;
-
free_edge_list (edges);
edges = NULL;
-
- sbitmap_free (executable_edges);
- executable_edges = NULL;
}
/* Set the lattice value for the variable defined by REF to UNDEFINED. */
--- 996,1003 ----
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.8
diff -c -3 -p -r1.1.4.8 tree-flow.h
*** tree-flow.h 22 Aug 2002 19:21:35 -0000 1.1.4.8
--- tree-flow.h 23 Aug 2002 16:47:24 -0000
*************** extern void tree_compute_rdefs PARAMS ((
*** 459,464 ****
--- 459,465 ----
extern void analyze_rdefs PARAMS ((void));
extern int is_upward_exposed PARAMS ((tree, sbitmap, int));
extern void delete_ssa PARAMS ((void));
+ extern void tree_ssa_remove_phi_alternative PARAMS ((varref, basic_block));
/* Functions in tree-alias-steen.c */
extern void create_alias_vars PARAMS ((void));
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.10
diff -c -3 -p -r1.1.4.10 tree-ssa.c
*** tree-ssa.c 22 Aug 2002 19:21:35 -0000 1.1.4.10
--- tree-ssa.c 23 Aug 2002 16:47:25 -0000
*************** is_upward_exposed (sym, bb_set, exclude_
*** 616,618 ****
--- 616,660 ----
return 0;
}
+
+
+ /* Remove the PHI alternative for the predecessor block BLOCK from
+ PHI_NODE.
+
+ This routine assumes ordering of alternatives in the vector is
+ not important and implements removal by swapping the last alternative
+ with the alternative we want to delete, then shrinking the vector. */
+
+ void
+ tree_ssa_remove_phi_alternative (phi_node, block)
+ varref phi_node;
+ basic_block block;
+ {
+ varray_type phi_vec = VARDEF_PHI_CHAIN (phi_node);
+ unsigned int num_elem = VARRAY_ACTIVE_SIZE (phi_vec);
+ unsigned int i;
+
+ for (i = 0; i < num_elem; i++)
+ {
+ varref ref;
+
+ ref = (varref)VARRAY_GENERIC_PTR (phi_vec, i);
+
+ if (VARRAY_BB (VARDEF_PHI_CHAIN_BB (phi_node), i) == block)
+ {
+ /* If we are not at the last element, switch the last element
+ with the element we want to delete. */
+ if (i != num_elem - 1)
+ {
+ VARRAY_GENERIC_PTR (phi_vec, i)
+ = VARRAY_GENERIC_PTR (phi_vec, num_elem - 1);
+ VARRAY_BB (VARDEF_PHI_CHAIN_BB (phi_node), i)
+ = VARRAY_BB (VARDEF_PHI_CHAIN_BB (phi_node), num_elem - 1);
+ }
+
+ /* Shrink the vector. */
+ VARRAY_ACTIVE_SIZE (phi_vec) -= 1;
+ }
+ }
+ }
+
More information about the Gcc-patches
mailing list