This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] More CCP/SSA fixes [patch]
- From: Diego Novillo <dnovillo at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 22 Aug 2002 15:38:24 -0400
- Subject: [tree-ssa] More CCP/SSA fixes [patch]
- Organization: Red Hat Canada
This patch fixes various tidbits in CCP and SSA. We're closer to
bootstrap with CCP enabled but the stage1 compiler is taking a
very long time to compile insn-recog.c (I lost my patience at 12
CPU minutes). I'm still not sure if it's a circularity problem
in the SSA representation or whether we're doing something
exponentially expensive.
Main changes:
- PHI nodes are not set to UNDEFINED when a non-executable edge
is found (remnant from old debugging code, thanks Jeff Law
for spotting it).
- SSA def-use edges were not being set by the SSA builder.
- Default definitions for incoming PARM_DECLs are set to VARYING.
- VARDEFs for anything other than an assignment expression (e.g.,
asm clobbers) are set to VARYING.
- Changed main loop for tree-ssa-ccp to alternate between flow
and SSA edges. This brings the implementation closer to the
published algorithms.
Diego.
* tree-dfa.c (find_refs_in_stmt): Look for VARUSE references in
initialization expressions.
(find_refs_in_expr): Reformat.
(remove_ref_from_list): Optimize for the common case of removing
the head or the tail of the list.
(add_ref_to_list_end): Reformat comment.
(create_ref): Store the reference to LHS of assignment expressions.
(dump_varref): Also dump immediate uses of PHI nodes.
* tree-flow.h (IS_GHOST_DEF): Rename to IS_DEFAULT_DEF. Update all
callers everywhere.
(struct tree_ann_def): Update comments for field 'currdef'.
* tree-ssa-ccp.c (ssa_edges): Change type to ref_list.
(SSA_NAME): Remove.
(initialize): New function
(finalize): New function.
(visit_expression): Rename to visit_expression_for. Update all
callers.
(visit_condexpr_for): New function.
(visit_assignment): Rename to visit_assignment_for. Update all
callers.
(examine_flow_edges): Rename to simulate_block. Update all
callers.
(follow_def_use_chains): Rename to simulate_def_use_chains. Update
all callers.
(evaluate_expr_for): Rename to evaluate_expr. Change argument to
'tree'.
(set_lattice_value): New function.
(tree_ssa_ccp): Change main loop to visit flow_edges and ssa_edges
alternately.
(visit_phi_node): Do not set the lattice value to UNDEFINED when we
find a non-executable edge.
(visit_expression_for): Default definitions for PARM_DECLs are
assigned a VARYING value.
Default definitions for any other local variables are assigned an
UNDEFINED value.
Clobber VARDEFs that are not the LHS of an assignment.
Clobber VARDEFs that initialize non-const static variables.
* tree-ssa.c (search_fud_chains): Set up def-use edges for PHI
nodes and regular definitions.
* tree.c (simple_cst_equal): Call simple_cst_list_equal to compare
CONSTRUCTOR_ELTS pointers.
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.8
diff -d -u -p -r1.1.4.8 tree-dfa.c
--- tree-dfa.c 19 Aug 2002 17:12:21 -0000 1.1.4.8
+++ tree-dfa.c 22 Aug 2002 16:56:10 -0000
@@ -189,8 +189,12 @@ find_refs_in_stmt (t, bb)
case DECL_STMT:
if (TREE_CODE (DECL_STMT_DECL (t)) == VAR_DECL
&& DECL_INITIAL (DECL_STMT_DECL (t)))
- find_refs_in_expr (&DECL_STMT_DECL (t), VARDEF, bb, t,
- DECL_STMT_DECL (t));
+ {
+ find_refs_in_expr (&DECL_INITIAL (DECL_STMT_DECL (t)), VARUSE, bb, t,
+ DECL_INITIAL (DECL_STMT_DECL (t)));
+ find_refs_in_expr (&DECL_STMT_DECL (t), VARDEF, bb, t,
+ DECL_STMT_DECL (t));
+ }
break;
case CLEANUP_STMT:
@@ -264,9 +268,9 @@ find_refs_in_expr (expr_p, ref_type, bb,
/* If this reference is associated with a non SIMPLE expression, then we
mark the parent expression non SIMPLE. This will cause all the
references associated with this expression to be marked as VARDEFs. */
- if (parent_expr &&
- TREE_ANN (expr) &&
- (TREE_FLAGS (expr) & TF_NOT_SIMPLE))
+ if (parent_expr
+ && TREE_ANN (expr)
+ && (TREE_FLAGS (expr) & TF_NOT_SIMPLE))
get_tree_ann (parent_expr)->flags |= TF_NOT_SIMPLE;
code = TREE_CODE (expr);
@@ -545,24 +549,32 @@ remove_ref_from_list (list, ref)
varref ref;
{
struct ref_list_node *tmp;
+
if (!list || !list->first || !list->last)
return;
- for (tmp = list->first; tmp; tmp = tmp->next)
+
+ if (ref == list->first->ref)
+ tmp = list->first;
+ else if (ref == list->last->ref)
+ tmp = list->last;
+ else
{
- if (tmp->ref == ref)
- {
- if (tmp == list->first)
- list->first = tmp->next;
- if (tmp == list->last)
- list->last = tmp->prev;
- if (tmp->next)
- tmp->next->prev = tmp->prev;
- if (tmp->prev)
- tmp->prev->next = tmp->next;
- free (tmp);
- return;
- }
+ for (tmp = list->first; tmp; tmp = tmp->next)
+ if (tmp->ref == ref)
+ break;
}
+
+ if (tmp == list->first)
+ list->first = tmp->next;
+ if (tmp == list->last)
+ list->last = tmp->prev;
+ if (tmp->next)
+ tmp->next->prev = tmp->prev;
+ if (tmp->prev)
+ tmp->prev->next = tmp->next;
+
+ free (tmp);
+ return;
}
@@ -618,7 +630,7 @@ add_ref_to_list_end (list, ref)
BB, PARENT_STMT, PARENT_EXPR and OPERAND_P give the exact location of the
reference. PARENT_STMT, PARENT_EXPR and OPERAND_P can be NULL in the
- case of artificial references (PHI nodes, ghost definitions, etc). */
+ case of artificial references (PHI nodes, default definitions, etc). */
varref
create_ref (sym, ref_type, bb, parent_stmt, parent_expr, operand_p)
@@ -702,11 +714,20 @@ create_ref (sym, ref_type, bb, parent_st
Make sure that PHI terms are added at the beginning of the list,
otherwise FUD chaining will fail to link local uses to the PHI term in
this basic block. */
- if (ref_type == VARPHI || ref_type == EXPRPHI || IS_GHOST_DEF (ref))
+ if (ref_type == VARPHI || ref_type == EXPRPHI || IS_DEFAULT_DEF (ref))
add_ref_to_list_begin (get_bb_ann (bb)->refs, ref);
else
add_ref_to_list_end (get_bb_ann (bb)->refs, ref);
+ /* If PARENT_EXPR is an assignment and SYM is the LHS of that assignment,
+ then store REF in TREE_CURRDEF. */
+ if (parent_expr
+ && (TREE_CODE (parent_expr) == MODIFY_EXPR
+ || TREE_CODE (parent_expr) == INIT_EXPR)
+ && TREE_OPERAND (parent_expr, 0) == sym)
+ TREE_CURRDEF (parent_expr) = ref;
+
+
return ref;
}
@@ -945,10 +966,21 @@ dump_varref (outf, prefix, ref, indent,
/* Dump specific contents for the different types of references. */
if (details)
{
- if (VARREF_TYPE (ref) == VARPHI && VARDEF_PHI_CHAIN (ref))
+ if (VARREF_TYPE (ref) == VARPHI)
{
- fputs (" phi-args:\n", outf);
- dump_varref_array (outf, prefix, VARDEF_PHI_CHAIN (ref), indent + 4, 0);
+ if (VARDEF_PHI_CHAIN (ref))
+ {
+ fputs (" phi-args:\n", outf);
+ dump_varref_array (outf, prefix, VARDEF_PHI_CHAIN (ref),
+ indent + 4, 0);
+ }
+
+ if (VARDEF_IMM_USES (ref))
+ {
+ fputs (" immediate uses:\n", outf);
+ dump_varref_list (outf, prefix, VARDEF_IMM_USES (ref),
+ indent + 4, 0);
+ }
}
else if (VARREF_TYPE (ref) == EXPRPHI && EXPRPHI_PHI_CHAIN (ref))
{
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.7
diff -d -u -p -r1.1.4.7 tree-flow.h
--- tree-flow.h 16 Aug 2002 15:50:33 -0000 1.1.4.7
+++ tree-flow.h 22 Aug 2002 16:56:10 -0000
@@ -171,7 +171,7 @@ struct varuse
{
struct exprref_common common;
- /* Definition chain. */
+ /* Definition chain (immediate reaching definition). */
union varref_def *chain;
/* Definitions reaching this use. */
@@ -234,13 +234,13 @@ typedef union varref_def *varref;
#define EXPRREF_SAVE(r) (r)->ecommon.save
#define EXPRREF_RELOAD(r) (r)->ecommon.reload
-/* Return nonzero if R is a ghost definition. Ghost definitions are
+/* Return nonzero if R is a default definition. Default definitions are
artificially created in the first basic block of the program. They
provide a convenient way of checking if a variable is used without being
assigned a value first. Their presence is not required, but they save
the code from having to consider special cases like nil PHI node
arguments. */
-#define IS_GHOST_DEF(R) \
+#define IS_DEFAULT_DEF(R) \
(R \
&& VARREF_TYPE (R) == VARDEF \
&& VARREF_EXPR (R) == NULL_TREE \
@@ -248,9 +248,9 @@ typedef union varref_def *varref;
&& VARREF_BB (R)->index == 0)
/* Return nonzero if R is an artificial definition (currently, a PHI term
- or a ghost definition). */
+ or a default definition). */
#define IS_ARTIFICIAL_REF(R) \
- (IS_GHOST_DEF (R) || VARREF_TYPE (R) == VARPHI)
+ (IS_DEFAULT_DEF (R) || VARREF_TYPE (R) == VARPHI)
/* Tree annotations stored in tree_common.aux. */
@@ -264,8 +264,12 @@ struct tree_ann_def
SIMPLE expression, list of references made in this expression. */
ref_list refs;
- /* Most recent definition for this symbol. Used when placing FUD
- chains. */
+ /* For _DECL trees this is the most recent definition for this symbol.
+ Used when placing FUD chains. For assignment expressions, this is the
+ VARDEF being defined on the LHS of the assignment. Note that
+ assignments may define more than one symbol (e.g., a.b = 5 defines
+ 'a.b' and 'a'). However, in this case currdef only holds the VARDEF
+ D for which VARREF_SYM (D) == TREE_OPERAND (assignment, 0). */
varref currdef;
/* Immediately enclosing compound statement to which this tree belongs. */
@@ -304,12 +308,14 @@ union header_blocks
basic_block do_cond_bb;
};
-ref_list create_ref_list (void);
-void empty_ref_list (ref_list);
-void delete_ref_list (ref_list);
-void add_ref_to_list_end (ref_list, varref);
-void add_ref_to_list_begin (ref_list, varref);
-void remove_ref_from_list (ref_list, varref);
+/* Functions to manipulate lists of references (ref_list). */
+ref_list create_ref_list PARAMS ((void));
+void empty_ref_list PARAMS ((ref_list));
+void delete_ref_list PARAMS ((ref_list));
+void add_ref_to_list_end PARAMS ((ref_list, varref));
+void add_ref_to_list_begin PARAMS ((ref_list, varref));
+void remove_ref_from_list PARAMS ((ref_list, varref));
+
#define FOR_REF_BETWEEN(REF, TMP, FROM, TO, DIR) \
if (FROM) \
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.10
diff -d -u -p -r1.1.2.10 tree-ssa-ccp.c
--- tree-ssa-ccp.c 19 Aug 2002 17:12:21 -0000 1.1.2.10
+++ tree-ssa-ccp.c 22 Aug 2002 16:56:10 -0000
@@ -97,36 +97,40 @@ static sbitmap executable_blocks;
/* A bitmap for all executable edges in the CFG. */
static sbitmap executable_edges;
-/* Array of edges on the work list. */
+/* Array of control flow edges on the worklist. */
static edge *edge_info;
-/* We need an edge list to be able to get indexes easily. */
+/* We need an control flow edge list to be able to get indexes easily. */
static struct edge_list *edges;
-/* Current edge we are operating on, from the worklist. */
+/* Current control flow edge we are operating on, from the worklist. */
static edge flow_edges;
-/* Stack of SSA edges which will need reexamination as their definition
+/* 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 definition. */
-static varray_type ssa_edges;
+ edge, we store the originating VARDEF/VARPHI reference D. The destination
+ nodes that need to be visited are accessed using VARDEF_IMM_USES (D). */
+ref_list ssa_edges;
-/* Simple macros to simplify code */
-#define SSA_NAME(x) VARREF_ID (x)
+/* Simple macros to simplify code. */
#define PHI_PARMS(x) VARDEF_PHI_CHAIN (x)
#define EIE(x,y) EDGE_INDEX (edges, x, y)
+static void initialize PARAMS ((void));
+static void finalize PARAMS ((void));
static void visit_phi_node PARAMS ((varref));
-static void visit_expression PARAMS ((varref));
-static void visit_assignment PARAMS ((varref));
+static void visit_expression_for PARAMS ((varref));
+static void visit_condexpr_for PARAMS ((varref));
+static void visit_assignment_for PARAMS ((varref));
static void def_to_undefined PARAMS ((varref));
static void def_to_varying PARAMS ((varref));
-static void examine_flow_edges PARAMS ((void));
-static void follow_def_use_chains PARAMS ((void));
+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_for PARAMS ((varref));
+static value evaluate_expr PARAMS ((tree));
static void dump_lattice_value PARAMS ((FILE *, const char *, value));
static tree widen_bitfield PARAMS ((tree, tree, tree));
@@ -145,8 +149,6 @@ void
tree_ssa_ccp (fndecl)
tree fndecl;
{
- unsigned int i;
- edge curredge;
tree fnbody;
fnbody = COMPOUND_BODY (DECL_SAVED_TREE (fndecl));
@@ -156,50 +158,28 @@ tree_ssa_ccp (fndecl)
abort ();
#endif
- /* Initialize debugging dumps. */
- dump_file = dump_begin (TDI_ccp, &dump_flags);
-
- /* Build an edge list from the CFG. */
- edges = create_edge_list ();
-
- /* Initialize the values array with everything as undefined. */
- values = (value *) xmalloc (next_varref_id * sizeof (value));
- for (i = 0; i < next_varref_id; i++)
- {
- values[i].lattice_val = UNDEFINED;
- values[i].const_value = NULL_TREE;
- }
-
- /* Stack of SSA (def-use) edges. FIXME: We shouldn't need more than a
- fraction of entries. See if we can get away with less than half. */
- VARRAY_GENERIC_PTR_INIT (ssa_edges, next_varref_id / 2, "ssa_edges");
-
- 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;
- }
+ initialize ();
/* Iterate until the worklists are empty. */
- do
+ while (flow_edges != NULL || ssa_edges->last != NULL)
{
- examine_flow_edges ();
- follow_def_use_chains ();
+ 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);
+ }
+
+ if (ssa_edges->last)
+ {
+ /* Pull the next reference off the worklist. The SSA edges
+ worklist stores the origination definition for each edge. */
+ varref def = ssa_edges->last->ref;
+ remove_ref_from_list (ssa_edges, def);
+ simulate_def_use_chains (def);
+ }
}
- while (flow_edges != NULL);
/* Now perform substitutions based on the known constant values. */
ssa_ccp_substitute_constants ();
@@ -226,20 +206,223 @@ tree_ssa_ccp (fndecl)
dump_end (TDI_ccp, dump_file);
}
- free (values);
- values = NULL;
+ finalize ();
+}
- free (edge_info);
- edge_info = NULL;
- sbitmap_free (executable_blocks);
- executable_blocks = NULL;
+/* Simulate the execution of BLOCK. Evaluate the expression associated
+ with each variable reference inside the block. */
- free_edge_list (edges);
- edges = NULL;
+static void
+simulate_block (block)
+ basic_block block;
+{
+ ref_list blockrefs;
+ varref ref;
+ struct ref_list_node *tmp;
- sbitmap_free (executable_edges);
- executable_edges = NULL;
+ /* There is nothing to do for the exit block. */
+ if (block == EXIT_BLOCK_PTR)
+ return;
+
+ /* Similarly, if the block contains no references, we have nothing to do. */
+ blockrefs = BB_REFS (block);
+ if (blockrefs == NULL)
+ return;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "\nSimulating block %d\n", block->index);
+
+ /* Always simulate PHI nodes, even if we have simulated this block
+ before. Note that all PHI nodes are consecutive within a block. */
+ FOR_EACH_REF (ref, tmp, blockrefs)
+ {
+ if (VARREF_TYPE (ref) == VARPHI)
+ visit_phi_node (ref);
+ }
+
+#if defined ENABLE_CHECKING
+ if (block->index < 0 || block->index > last_basic_block)
+ abort ();
+#endif
+
+ /* If this is the first time we've simulated this block, then we
+ must simulate each of its insns. */
+ if (!TEST_BIT (executable_blocks, block->index))
+ {
+ edge succ_edge = block->succ;
+
+ /* Note that we have simulated this block. */
+ SET_BIT (executable_blocks, block->index);
+
+ FOR_EACH_REF (ref, tmp, blockrefs)
+ {
+ /* Simulate each reference within the block. */
+ if (VARREF_TYPE (ref) != VARPHI)
+ visit_expression_for (ref);
+ }
+
+ /* 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);
+ }
+ }
+}
+
+
+/* Follow the def-use chains for definition DEF and simulate all the
+ expressions reached by it. */
+
+static void
+simulate_def_use_chains (def)
+ varref def;
+{
+ varref ref;
+ struct ref_list_node *tmp;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ dump_varref (dump_file, "\nSimulating def-use edges for definition: ",
+ def, 0, 0);
+
+ FOR_EACH_REF (ref, tmp, VARDEF_IMM_USES (def))
+ {
+ if (VARREF_TYPE (ref) == VARUSE
+ && TEST_BIT (executable_blocks, VARREF_BB (ref)->index))
+ visit_expression_for (ref);
+
+ /* PHI nodes are always visited, regardless of whether or not the
+ destination block is executable. */
+ else if (VARREF_TYPE (ref) == VARPHI)
+ visit_phi_node (ref);
+ }
+}
+
+
+/* Examine each edge to see if we were able to prove any were
+ not executable.
+
+ If an edge is not executable, then we can remove its alternative
+ in PHI nodes as the destination of the edge, we can simplify the
+ conditional branch at the source of the edge, and we can remove
+ 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 ATTRIBUTE_UNUSED;
+ sbitmap executable_edges ATTRIBUTE_UNUSED;
+{
+}
+
+
+/* Perform substitution and folding. */
+
+static void
+ssa_ccp_substitute_constants ()
+{
+ basic_block bb;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "\nSubstituing constants and folding expressions\n\n");
+
+ /* Substitute constants. */
+ FOR_EACH_BB (bb)
+ {
+ varref ref;
+ struct ref_list_node *tmp;
+
+ FOR_EACH_REF (ref, tmp, BB_REFS (bb))
+ {
+ varref rdef;
+ unsigned int id;
+
+ if (VARREF_TYPE (ref) != VARUSE)
+ continue;
+
+ rdef = VARUSE_CHAIN (ref);
+ id = VARREF_ID (rdef);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ dump_varref (dump_file, "Immediate reaching definition for ",
+ ref, 0, 0);
+ dump_varref (dump_file, ": ", rdef, 0, 0);
+ dump_lattice_value (dump_file, "Lattice value: ", values[id]);
+ fprintf (dump_file, "\n");
+ if (values[id].lattice_val == CONSTANT)
+ {
+ fprintf (dump_file, "Marking expression ");
+ print_c_node (dump_file, VARREF_EXPR (ref));
+ fprintf (dump_file, " for folding\n");
+ }
+ fprintf (dump_file, "\n");
+ }
+
+ if (values[id].lattice_val == CONSTANT)
+ {
+#if defined ENABLE_CHECKING
+ if (values[id].const_value == NULL_TREE)
+ abort ();
+#endif
+
+ /* Replace the constant inside the expression and mark the
+ expression for folding. */
+ *(VARREF_OPERAND_P (ref)) = values[id].const_value;
+ TREE_FLAGS (VARREF_EXPR (ref)) |= TF_FOLD;
+ }
+ }
+ }
+
+ /* Fold expressions. */
+ FOR_EACH_BB (bb)
+ {
+ varref ref;
+ struct ref_list_node *tmp;
+
+ FOR_EACH_REF (ref, tmp, BB_REFS (bb))
+ {
+ tree stmt = VARREF_STMT (ref);
+ tree expr = VARREF_EXPR (ref);
+
+ if (VARREF_TYPE (ref) == VARUSE
+ && (TREE_FLAGS (VARREF_EXPR (ref)) & TF_FOLD))
+ {
+ /* Fold the expression and clean the fold bit. */
+ TREE_FLAGS (VARREF_EXPR (ref)) &= ~TF_FOLD;
+
+ if (TREE_CODE (expr) == MODIFY_EXPR
+ || TREE_CODE (expr) == INIT_EXPR)
+ expr = TREE_OPERAND (expr, 1);
+
+ replace_expr_in_tree (stmt, expr, fold (expr));
+ }
+ }
+ }
+}
+
+
+/* Now find all unreachable basic blocks. All the insns in those
+ blocks are unreachable, so delete them and mark any necessary
+ updates for the DF analyzer. */
+
+static void
+ssa_ccp_df_delete_unreachable_insns ()
+{
}
@@ -258,7 +441,7 @@ visit_phi_node (phi_node)
{
unsigned int i;
- unsigned int phi_node_name = SSA_NAME (phi_node);
+ unsigned int phi_node_name = VARREF_ID (phi_node);
latticevalue phi_node_lattice_val = UNDEFINED;
varray_type phi_vec = PHI_PARMS (phi_node);
unsigned int num_elem = VARRAY_ACTIVE_SIZE (phi_vec);
@@ -293,7 +476,7 @@ visit_phi_node (phi_node)
if (TEST_BIT (executable_edges, EIE (phiargbb, block)))
{
latticevalue current_parm_lattice_val;
- unsigned int current_parm = SSA_NAME (ref);
+ unsigned int current_parm = VARREF_ID (ref);
current_parm_lattice_val = values[current_parm].lattice_val;
@@ -304,7 +487,7 @@ visit_phi_node (phi_node)
fprintf (dump_file, "\n");
}
- /* If any node is VARYING, then new value of PHI_NODE
+ /* If any parameter is VARYING, then the new value of PHI_NODE
is VARYING. */
if (current_parm_lattice_val == VARYING)
{
@@ -337,24 +520,18 @@ visit_phi_node (phi_node)
phi_node_expr = values[current_parm].const_value;
}
}
- else
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " Rescheduling this PHI expression into the queue\n");
-
- phi_node_lattice_val = UNDEFINED;
- phi_node_expr = NULL_TREE;
- break;
- }
}
- /* If the value of PHI_NODE changed, then we will
- need to re-execute uses of the output of PHI_NODE. */
+ /* If the value of PHI_NODE changed, then we will need to re-execute uses of
+ the output of PHI_NODE. */
if (phi_node_lattice_val != values[phi_node_name].lattice_val)
{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Lattice value changed. Adding PHI node to SSA edges.\n");
+
values[phi_node_name].lattice_val = phi_node_lattice_val;
values[phi_node_name].const_value = phi_node_expr;
- VARRAY_PUSH_GENERIC_PTR (ssa_edges, phi_node);
+ add_ref_to_list_end (ssa_edges, phi_node);
}
if (dump_file && (dump_flags & TDF_DETAILS))
@@ -379,27 +556,34 @@ visit_phi_node (phi_node)
result of the branch. */
static void
-visit_expression (ref)
+visit_expression_for (ref)
varref ref;
{
tree expr;
#if defined ENABLE_CHECKING
- /* PHI references should be dealt with by visit_phi_node. */
+ /* PHI references should be handled by visit_phi_node. */
if (VARREF_TYPE (ref) == VARPHI)
abort ();
#endif
- /* Special case for ghost definitions. Set their lattice value to
- VARYING. */
- if (IS_GHOST_DEF (ref))
+ expr = VARREF_EXPR (ref);
+ if (expr == NULL)
{
- values[SSA_NAME (ref)].lattice_val = VARYING;
+ /* If this is a definition with no associated expression, clobber the
+ reference. Except if this is a default definition for a local
+ variable (which should be considered UNDEFINED, not VARYING).
+
+ Note that we must clobber PARM_DECLs here. Their incoming value
+ may not change, but we don't know what it is. */
+ if (IS_DEFAULT_DEF (ref) && TREE_CODE (VARREF_SYM (ref)) != PARM_DECL)
+ def_to_undefined (ref);
+ else
+ def_to_varying (ref);
+
return;
}
- expr = VARREF_EXPR (ref);
-
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nVisiting expression: ");
@@ -407,399 +591,169 @@ visit_expression (ref)
dump_varref (dump_file, "\nfor reference: ", ref, 0, 0);
}
- /* If REF is a definition in an assignment expression, visit the
- assignment to determine the lattice value for the variable. */
- if (VARREF_TYPE (ref) == VARDEF)
+ /* If the expression is an assignment, evaluate its RHS to determine the
+ lattice value for the reference at the LHS of the assignment. */
+ if (TREE_CODE (expr) == MODIFY_EXPR || TREE_CODE (expr) == INIT_EXPR)
{
- if (TREE_CODE (expr) == MODIFY_EXPR || TREE_CODE (expr) == INIT_EXPR)
- visit_assignment (ref);
- else
+ if (VARREF_TYPE (ref) == VARDEF
+ && ref != TREE_CURRDEF (expr))
def_to_varying (ref);
+ else
+ visit_assignment_for (TREE_CURRDEF (expr));
}
/* If the expression is the predicate of a control statement, see if we
can determine which branch will be taken. */
else if (VARREF_BB (ref)->flags & BB_CONTROL_EXPR)
+ visit_condexpr_for (ref);
+
+ /* If this reference is the declaration of a static variable, set its
+ lattice value to VARYING. Static initializers are only executed the
+ first time the function is called. We could assume them constant if
+ there are no other definitions to the variable in the function, but
+ that hardly seems worth it. */
+ else if (VARREF_TYPE (ref) == VARDEF
+ && TREE_CODE (VARREF_STMT (ref)) == DECL_STMT
+ && TREE_STATIC (DECL_STMT_DECL (VARREF_STMT (ref))))
{
- edge curredge;
value val;
- basic_block block = VARREF_BB (ref);
-
- val.lattice_val = UNDEFINED;
- val.const_value = NULL_TREE;
+ tree decl = DECL_STMT_DECL (VARREF_STMT (ref));
- /* If the expression is the predicate for the control statement,
- evaluate it to see if we can determine whether the TRUE or FALSE
- branch will be taken. */
- if (is_simple_condexpr (expr))
- val = evaluate_expr_for (ref);
+ val.lattice_val = VARYING;
+ val.const_value = NULL;
- if (dump_file && (dump_flags & TDF_DETAILS))
+ /* Exception. If this is a 'const' declaration, use the value. */
+ if (TREE_READONLY (decl) && really_constant_p (DECL_INITIAL (decl)))
{
- fprintf (dump_file, "Predicate is for a control statement: %s\n",
- tree_code_name[TREE_CODE (VARREF_STMT (ref))]);
- dump_lattice_value (dump_file, "value: ", val);
- fprintf (dump_file, "\n");
+ val.lattice_val = CONSTANT;
+ val.const_value = DECL_INITIAL (VARREF_SYM (ref));
}
- /* Mark successor blocks on executable edges as executable (if they
- 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. */
- if ((curredge->flags & EDGE_TRUE_VALUE)
- && simple_cst_equal (val.const_value, integer_zero_node) == 1)
- continue;
-
- /* Similarly for FALSE edges. */
- if ((curredge->flags & EDGE_FALSE_VALUE)
- && simple_cst_equal (val.const_value, integer_one_node) == 1)
- 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);
- }
+ set_lattice_value (ref, val);
}
-}
-
-
-/* Visit an assignment statement for reference REF. */
-
-static void
-visit_assignment (ref)
- varref ref;
-{
- tree set, src, dest, base_sym;
- value val;
- dest = VARREF_SYM (ref);
- base_sym = get_base_symbol (dest);
- set = VARREF_EXPR (ref);
- src = TREE_OPERAND (set, 1);
-
- val = evaluate_expr_for (ref);
-
- if (val.lattice_val == UNDEFINED)
- def_to_undefined (ref);
- else if (val.lattice_val == VARYING)
+ /* Any other definition that we do not recognize clobbers the variable. */
+ else if (VARREF_TYPE (ref) == VARDEF)
def_to_varying (ref);
- else if (TREE_ADDRESSABLE (dest)
- || DECL_CONTEXT (base_sym) == NULL
- || TREE_THIS_VOLATILE (dest))
- {
- /* Certain types of variables cannot be proven constant even if they
- were assigned one. Examples include: globals, volatiles and
- variables that have had their address taken.
-
- FIXME: Additional analysis might help us make a better decision in
- the future. */
- def_to_varying (ref);
- }
- else
- {
- /* If the RHS is a constant value that is different from a previous
- value for this reference, add its SSA edge to the work list. */
- if (values[VARREF_ID (ref)].lattice_val != CONSTANT
- || !(simple_cst_equal (values[VARREF_ID (ref)].const_value,
- val.const_value)) == 1)
- VARRAY_PUSH_GENERIC_PTR (ssa_edges, ref);
-
- values[VARREF_ID (ref)].lattice_val = CONSTANT;
- values[VARREF_ID (ref)].const_value = val.const_value;
- }
}
-/* Iterate over the FLOW_EDGES work list. Simulate the target block
- for each edge. */
+/* Visit an assignment expression for DEF. This function evaluates the RHS
+ of the expression holding DEF. If it's found to be constant, it
+ modifies DEF's lattice value. */
static void
-examine_flow_edges (void)
+visit_assignment_for (def)
+ varref def;
{
- while (flow_edges != NULL)
- {
- basic_block succ_block;
- ref_list blockrefs;
- varref ref;
- struct ref_list_node *tmp;
-
- /* 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)
- continue;
+ tree assignment, lhs;
+ value val;
- blockrefs = BB_REFS (succ_block);
- if (!blockrefs)
- continue;
+ if (def == NULL)
+ return;
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\nSimulating block %d\n", succ_block->index);
+ assignment = VARREF_EXPR (def);
+ lhs = TREE_OPERAND (assignment, 0);
- /* Always simulate PHI nodes, even if we have simulated this block
- before. Note that all PHI nodes are consecutive within a block. */
- FOR_EACH_REF (ref, tmp, blockrefs)
- {
- if (VARREF_TYPE (ref) == VARPHI)
- visit_phi_node (ref);
- }
+ val = evaluate_expr (assignment);
-#if defined ENABLE_CHECKING
- if (succ_block->index < 0 || succ_block->index > last_basic_block)
- abort ();
-#endif
+ /* FIXME: Hack. If this was a definition of a bitfield, we need to
+ widen the constant value into the type of the destination
+ variable. This should not be necessary if GCC represented
+ bitfields properly. */
+ if (val.lattice_val == CONSTANT
+ && TREE_CODE (lhs) == COMPONENT_REF
+ && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
+ {
+ tree w = widen_bitfield (val.const_value, TREE_OPERAND (lhs, 1), lhs);
- /* If this is the first time we've simulated this block, then we
- must simulate each of its insns. */
- if (!TEST_BIT (executable_blocks, succ_block->index))
+ if (w)
+ val.const_value = w;
+ else
{
- edge succ_edge = succ_block->succ;
-
- /* Note that we have simulated this block. */
- SET_BIT (executable_blocks, succ_block->index);
-
- FOR_EACH_REF (ref, tmp, blockrefs)
- {
- /* Simulate each reference within the block. */
- if (VARREF_TYPE (ref) != VARPHI)
- visit_expression (ref);
- }
-
- /* 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);
- }
+ val.lattice_val = VARYING;
+ val.const_value = NULL;
}
}
-}
-
-
-/* Follow the def-use chains for each definition on the worklist and
- simulate the uses of the definition. */
-
-static void
-follow_def_use_chains ()
-{
- /* Iterate over all the entries on the SSA_EDGES worklist. */
- while (VARRAY_ACTIVE_SIZE (ssa_edges) > 0)
- {
- varref ref;
-
- /* Pick an entry off the worklist (it does not matter which
- entry we pick). */
- ref = (varref) VARRAY_TOP_GENERIC_PTR (ssa_edges);
- VARRAY_POP (ssa_edges);
- if (VARREF_TYPE (ref) == VARUSE
- && TEST_BIT (executable_blocks, VARREF_BB (ref)->index))
- visit_expression (ref);
- else if (VARREF_TYPE (ref) == VARPHI
- && TEST_BIT (executable_blocks, VARREF_BB (ref)->index))
- visit_phi_node (ref);
- }
+ set_lattice_value (def, val);
}
-/* Examine each edge to see if we were able to prove any were
- not executable.
-
- If an edge is not executable, then we can remove its alternative
- in PHI nodes as the destination of the edge, we can simplify the
- conditional branch at the source of the edge, and we can remove
- 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 ATTRIBUTE_UNUSED;
- sbitmap executable_edges ATTRIBUTE_UNUSED;
+visit_condexpr_for (ref)
+ varref ref;
{
-}
-
+ edge curredge;
+ value val;
+ basic_block block = VARREF_BB (ref);
+ tree expr = VARREF_EXPR (ref);
-/* Perform substitution and folding. */
+ val.lattice_val = UNDEFINED;
+ val.const_value = NULL_TREE;
-static void
-ssa_ccp_substitute_constants ()
-{
- basic_block bb;
+ /* If the expression is the predicate for the control statement,
+ evaluate it to see if we can determine whether the TRUE or FALSE
+ branch will be taken. */
+ if (is_simple_condexpr (expr))
+ val = evaluate_expr (expr);
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\nSubstituing constants and folding expressions\n\n");
-
- /* Substitute constants. */
- FOR_EACH_BB (bb)
{
- varref ref;
- struct ref_list_node *tmp;
-
- FOR_EACH_REF (ref, tmp, BB_REFS (bb))
- {
- varref rdef;
- unsigned int id;
-
- if (VARREF_TYPE (ref) != VARUSE)
- continue;
-
- rdef = VARUSE_CHAIN (ref);
- id = VARREF_ID (rdef);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- dump_varref (dump_file, "Immediate reaching definition for ",
- ref, 0, 0);
- dump_varref (dump_file, ": ", rdef, 0, 0);
- dump_lattice_value (dump_file, "Lattice value: ", values[id]);
- fprintf (dump_file, "\n");
- if (values[id].lattice_val == CONSTANT)
- {
- fprintf (dump_file, "Marking expression ");
- print_c_node (dump_file, VARREF_EXPR (ref));
- fprintf (dump_file, " for folding\n");
- }
- fprintf (dump_file, "\n");
- }
-
- if (values[id].lattice_val == CONSTANT)
- {
-#if defined ENABLE_CHECKING
- if (values[id].const_value == NULL_TREE)
- abort ();
-#endif
-
- /* Replace the constant inside the expression and mark the
- expression for folding. */
- *(VARREF_OPERAND_P (ref)) = values[id].const_value;
- TREE_FLAGS (VARREF_EXPR (ref)) |= TF_FOLD;
- }
- }
+ fprintf (dump_file, "Predicate is for a control statement: %s\n",
+ tree_code_name[TREE_CODE (VARREF_STMT (ref))]);
+ dump_lattice_value (dump_file, "value: ", val);
+ fprintf (dump_file, "\n");
}
- /* Fold expressions. */
- FOR_EACH_BB (bb)
+ /* Mark successor blocks on executable edges as executable (if they
+ have not already been marked). */
+ for (curredge = block->succ; curredge; curredge = curredge->succ_next)
{
- varref ref;
- struct ref_list_node *tmp;
-
- FOR_EACH_REF (ref, tmp, BB_REFS (bb))
- {
- tree stmt = VARREF_STMT (ref);
- tree expr = VARREF_EXPR (ref);
-
- if (VARREF_TYPE (ref) == VARUSE
- && (TREE_FLAGS (VARREF_EXPR (ref)) & TF_FOLD))
- {
- /* Fold the expression and clean the fold bit. */
- TREE_FLAGS (VARREF_EXPR (ref)) &= ~TF_FOLD;
-
- if (TREE_CODE (expr) == MODIFY_EXPR
- || TREE_CODE (expr) == INIT_EXPR)
- expr = TREE_OPERAND (expr, 1);
-
- replace_expr_in_tree (stmt, expr, fold (expr));
- }
- }
- }
-}
-
-
-/* Now find all unreachable basic blocks. All the insns in those
- blocks are unreachable, so delete them and mark any necessary
- updates for the DF analyzer. */
-
-static void
-ssa_ccp_df_delete_unreachable_insns ()
-{
-}
-
-
-/* Set the lattice value for the variable defined by REF to UNDEFINED. */
-
-static void
-def_to_undefined (ref)
- varref ref;
-{
- if (VARREF_TYPE (ref) != VARDEF)
- return;
-
- if (values[SSA_NAME (ref)].lattice_val != UNDEFINED)
- VARRAY_PUSH_GENERIC_PTR (ssa_edges, ref);
-
- values[SSA_NAME (ref)].lattice_val = UNDEFINED;
-}
+ int index = EIE (curredge->src, curredge->dest);
+ /* If this is an edge for TRUE values but the predicate is false,
+ then skip it. */
+ if ((curredge->flags & EDGE_TRUE_VALUE)
+ && simple_cst_equal (val.const_value, integer_zero_node) == 1)
+ continue;
-/* Set the lattice value for the variable defined by REF to VARYING. */
+ /* Similarly for FALSE edges. */
+ if ((curredge->flags & EDGE_FALSE_VALUE)
+ && simple_cst_equal (val.const_value, integer_one_node) == 1)
+ continue;
-static void
-def_to_varying (ref)
- varref ref;
-{
- if (VARREF_TYPE (ref) != VARDEF)
- return;
+ /* If the edge had already been added, skip it. */
+ if (TEST_BIT (executable_edges, index))
+ continue;
- if (values[SSA_NAME (ref)].lattice_val != VARYING)
- VARRAY_PUSH_GENERIC_PTR (ssa_edges, ref);
+ SET_BIT (executable_edges, index);
+ edge_info[index] = flow_edges;
+ flow_edges = curredge;
- values[SSA_NAME (ref)].lattice_val = VARYING;
+ 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);
+ }
}
-/* Evaluate the expression holding reference REF. */
+/* Evaluate the expression EXPR. */
static value
-evaluate_expr_for (ref)
- varref ref;
+evaluate_expr (expr)
+ tree expr;
{
value val;
struct ref_list_node *tmp;
varref r;
- tree var, expr, simplified;
+ tree simplified;
ref_list refs;
- refs = TREE_REFS (VARREF_EXPR (ref));
- expr = VARREF_EXPR (ref);
- var = VARREF_SYM (ref);
+ refs = TREE_REFS (expr);
val.lattice_val = VARYING;
val.const_value = NULL_TREE;
- /* If the expression and the referenced symbol are of different types,
- then the reference cannot be a constant. For instance, a.b = 5; is a
- constant only when considering reference 'a.b'. Although that
- expression also defines symbol 'a', we cannot assign the value 5 to
- symbol 'a'. */
- if (TREE_TYPE (expr) != TREE_TYPE (var))
- goto dont_fold;
-
/* If any USE reference in the expression is known to be VARYING or
UNDEFINED, then the expression is not a constant. */
FOR_EACH_REF (r, tmp, refs)
@@ -853,38 +807,13 @@ evaluate_expr_for (ref)
{
val.lattice_val = CONSTANT;
val.const_value = simplified;
-
- /* FIXME: Hack. If this was a definition of a bitfield, we need to
- widen the constant value into the type of the destination
- variable. This should not be necessary if GCC represented
- bitfields properly. */
- if (TREE_CODE (var) == COMPONENT_REF
- && DECL_BIT_FIELD (TREE_OPERAND (var, 1)))
- {
- tree w = widen_bitfield (simplified, TREE_OPERAND (var, 1), var);
-
- if (w)
- val.const_value = w;
- else
- {
- val.lattice_val = VARYING;
- val.const_value = NULL;
- }
- }
- }
-
- /* Restore the expression to its original form. */
- FOR_EACH_REF (r, tmp, refs)
- {
- if (VARREF_TYPE (r) == VARUSE)
- *(VARREF_OPERAND_P (r)) = VARREF_SYM (r);
}
dont_fold:
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Expression ");
- print_c_node (dump_file, VARREF_EXPR (ref));
+ print_c_node (dump_file, expr);
fprintf (dump_file, " evaluates to ");
print_c_node (dump_file, expr);
fprintf (dump_file, " which is ");
@@ -901,6 +830,13 @@ dont_fold:
fprintf (dump_file, "\n");
}
+ /* Restore the expression to its original form. */
+ FOR_EACH_REF (r, tmp, refs)
+ {
+ if (VARREF_TYPE (r) == VARUSE)
+ *(VARREF_OPERAND_P (r)) = VARREF_SYM (r);
+ }
+
return val;
}
@@ -935,8 +871,8 @@ widen_bitfield (val, field, var)
tree var;
{
unsigned var_size, field_size;
- tree ret, wide_val;
- unsigned HOST_WIDE_INT v, mask;
+ tree wide_val;
+ unsigned HOST_WIDE_INT mask;
unsigned i;
var_size = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE ((var))));
@@ -979,4 +915,166 @@ widen_bitfield (val, field, var)
}
return fold (wide_val);
+}
+
+
+/* Initialize local data structures and worklists for CCP. */
+
+static void
+initialize ()
+{
+ unsigned i;
+ edge curredge;
+
+ /* Initialize debugging dumps. */
+ dump_file = dump_begin (TDI_ccp, &dump_flags);
+
+ /* Build an edge list from the CFG. */
+ edges = create_edge_list ();
+
+ /* Initialize the values array with everything as undefined. */
+ values = (value *) xmalloc (next_varref_id * sizeof (value));
+ for (i = 0; i < next_varref_id; i++)
+ {
+ values[i].lattice_val = UNDEFINED;
+ values[i].const_value = NULL_TREE;
+ }
+
+ /* Worklist of SSA edges. */
+ ssa_edges = create_ref_list ();
+
+ 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;
+ }
+}
+
+
+/* Free allocated storage. */
+
+static void
+finalize ()
+{
+ 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. */
+
+static void
+def_to_undefined (ref)
+ varref ref;
+{
+ if (VARREF_TYPE (ref) != VARDEF)
+ return;
+
+ if (values[VARREF_ID (ref)].lattice_val != UNDEFINED)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Lattice value changed. Adding definition to SSA edges.\n");
+
+ add_ref_to_list_end (ssa_edges, ref);
+ }
+
+ values[VARREF_ID (ref)].lattice_val = UNDEFINED;
+}
+
+
+/* Set the lattice value for the variable defined by REF to VARYING. */
+
+static void
+def_to_varying (ref)
+ varref ref;
+{
+ if (VARREF_TYPE (ref) != VARDEF)
+ return;
+
+ if (values[VARREF_ID (ref)].lattice_val != VARYING)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Lattice value changed. Adding definition to SSA edges.\n");
+
+ add_ref_to_list_end (ssa_edges, ref);
+ }
+
+ values[VARREF_ID (ref)].lattice_val = VARYING;
+}
+
+
+/* Set the lattice value for reference DEF to VAL. */
+
+static void
+set_lattice_value (def, val)
+ varref def;
+ value val;
+{
+ tree base_sym;
+
+ base_sym = get_base_symbol (VARREF_SYM (def));
+
+ /* Certain types of variables cannot be proven constant even if they
+ were assigned one. Examples include: globals, volatiles and
+ variables that have had their address taken.
+
+ FIXME: Additional analysis might help us make a better decision in
+ the future. */
+ if (base_sym
+ && (TREE_ADDRESSABLE (base_sym)
+ || DECL_CONTEXT (base_sym) == NULL
+ || TREE_THIS_VOLATILE (base_sym)))
+ {
+ val.lattice_val = VARYING;
+ val.const_value = NULL;
+ }
+
+ if (val.lattice_val == UNDEFINED)
+ def_to_undefined (def);
+ else if (val.lattice_val == VARYING)
+ def_to_varying (def);
+ else
+ {
+ /* If the RHS is a constant value that is different from a previous
+ value for this reference, add its SSA edge to the worklist. */
+ if (values[VARREF_ID (def)].lattice_val != CONSTANT
+ || !(simple_cst_equal (values[VARREF_ID (def)].const_value,
+ val.const_value)) == 1)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Lattice value changed to ");
+ print_c_node (dump_file, val.const_value);
+ fprintf (dump_file, ". Adding definition to SSA edges.\n");
+ }
+
+ add_ref_to_list_end (ssa_edges, def);
+ values[VARREF_ID (def)].lattice_val = CONSTANT;
+ values[VARREF_ID (def)].const_value = val.const_value;
+ }
+ }
}
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.9
diff -d -u -p -r1.1.4.9 tree-ssa.c
--- tree-ssa.c 16 Aug 2002 15:50:33 -0000 1.1.4.9
+++ tree-ssa.c 22 Aug 2002 16:56:10 -0000
@@ -81,9 +81,9 @@ tree_build_ssa ()
dfs = sbitmap_vector_alloc (last_basic_block, last_basic_block);
compute_dominance_frontiers (dfs, idom);
- /* Insert default definitions (a.k.a. ghost definitions) for all the
- symbols referenced in the function. This allows the identification of
- variables that have been used without a preceding definition.
+ /* Insert default definitions for all the symbols referenced in the
+ function. This allows the identification of variables that have been
+ used without a preceding definition.
These definitions do not affect code generation, they are associated
with no statement or expression (to distinguish them from actual
@@ -245,7 +245,6 @@ search_fud_chains (bb, idom)
basic_block bb;
dominance_info idom;
{
-
edge e;
basic_block child_bb;
struct ref_list_node *tmp;
@@ -270,16 +269,15 @@ search_fud_chains (bb, idom)
if (VARREF_TYPE (ref) == VARUSE)
{
- VARUSE_CHAIN (ref) = currdef;
+ /* Set up a def-use chain between CURRDEF (the immediately
+ reaching definition for REF) and REF. Each definition may
+ have more than one immediate use. */
+ if (currdef && VARUSE_CHAIN (ref) != currdef)
+ add_ref_to_list_end (VARDEF_IMM_USES (currdef), ref);
- /* Besides setting a link back to our immediate reaching
- definition, we want to link that definition to its immediate
- use.
- If this use (ref) has a current definition (currdef), add
- 'ref' to the list of uses immediately reached by 'currdef'. */
- if (currdef)
- add_ref_to_list_end (VARDEF_IMM_USES (currdef), ref);
+ /* Set up a use-def chain between REF and CURRDEF. */
+ VARUSE_CHAIN (ref) = currdef;
}
else if (VARREF_TYPE (ref) == VARDEF || VARREF_TYPE (ref) == VARPHI)
{
@@ -326,6 +324,9 @@ search_fud_chains (bb, idom)
{
VARRAY_PUSH_GENERIC_PTR (VARDEF_PHI_CHAIN (phi), currdef);
VARRAY_PUSH_BB (VARDEF_PHI_CHAIN_BB (phi), bb);
+
+ /* Set a def-use edge between CURRDEF and this PHI node. */
+ add_ref_to_list_end (VARDEF_IMM_USES (currdef), phi);
}
}
}
@@ -490,32 +491,32 @@ analyze_rdefs ()
|| TREE_ADDRESSABLE (sym))
continue;
- /* For each use of SYM, if the use is reached by SYM's ghost
+ /* For each use of SYM, if the use is reached by SYM's default
definition, then the symbol may have been used uninitialized in
the function. */
FOR_EACH_REF (use, tmp, TREE_REFS (sym))
{
- int found_ghost;
+ int found_default;
varref def;
struct ref_list_node *tmp2;
if (VARREF_TYPE (use) != VARUSE)
continue;
- /* Check all the reaching definitions looking for the ghost
+ /* Check all the reaching definitions looking for the default
definition. */
- found_ghost = 0;
+ found_default = 0;
FOR_EACH_REF (def, tmp2, VARUSE_RDEFS (use))
{
- if (IS_GHOST_DEF (def))
- found_ghost = 1;
+ if (IS_DEFAULT_DEF (def))
+ found_default = 1;
}
- /* If we found a ghost definition for SYM, then the reference may
- be accessing an uninitialized symbol. If the ghost def is the
+ /* If we found a default definition for SYM, then the reference may
+ be accessing an uninitialized symbol. If the default def is the
only reaching definition, then the symbol _is_ used
uninitialized. Otherwise it _may_ be used uninitialized. */
- if (found_ghost)
+ if (found_default)
{
prep_stmt (VARREF_STMT (use));
if (VARUSE_RDEFS (use)->last == VARUSE_RDEFS (use)->first)
@@ -604,7 +605,7 @@ is_upward_exposed (sym, bb_set, exclude_
{
basic_block def_bb = VARREF_BB (def);
- if (IS_GHOST_DEF (def)
+ if (IS_DEFAULT_DEF (def)
|| (exclude_init_decl
&& TREE_CODE (VARREF_STMT (def)) == DECL_STMT)
|| ! TEST_BIT (bb_set, def_bb->index))
Index: tree.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.c,v
retrieving revision 1.263.2.6
diff -d -u -p -r1.263.2.6 tree.c
--- tree.c 12 Aug 2002 01:33:21 -0000 1.263.2.6
+++ tree.c 22 Aug 2002 16:56:11 -0000
@@ -3384,10 +3384,8 @@ simple_cst_equal (t1, t2)
TREE_STRING_LENGTH (t1)));
case CONSTRUCTOR:
- if (CONSTRUCTOR_ELTS (t1) == CONSTRUCTOR_ELTS (t2))
- return 1;
- else
- abort ();
+ return simple_cst_list_equal (CONSTRUCTOR_ELTS (t1),
+ CONSTRUCTOR_ELTS (t2));
case SAVE_EXPR:
return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));