This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[sa]: Implement bypassing and some alias analyzer updates
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 30 Sep 2004 18:58:15 -0400 (EDT)
- Subject: [sa]: Implement bypassing and some alias analyzer updates
This adds bypassing using the partial use info (of the same form as the
bypassing patch, it's just kept up to date automatically now, instead of
as a seperate pass), as well as some updates to the structure alias
analyzer.
In particular, i fixed a bug in constraint node collapsing, and made it
handle integer constraints much better.
The ivopts change is necessary because ivopts replaces something we
currently know the offset/size info for (a->b), with something we don't
know the info for (*p). In reality, it can't have changed where the access
is to, but we can't know that without hacking around, or rerunning
structure alias analysis on new variables so that we know where it points.
Bootstrapped on i686-pc-linux-gnu.
2004-09-30 Daniel Berlin <dberlin@dberlin.org>
* tree-ssa-loop-ivopts.c (rewrite_use_address): Mark new variables
for renaming.
(tree_ssa_iv_optimize): Call rewrite_into_ssa and
rewrite_into_loop_closed_ssa.
* tree-ssa-operands.c (add_stmt_operand): We don't want to deal
with type tags. Add support for trying to find partial use/def
info.
* tree-into-ssa.c (rewrite_stmt): Call
get_intersecting_reaching_def for partial uses.
(ssa_rewrite_stmt): Ditto.
(rewrite_operand): Inlined into caller and removed.
(find_may_def_for_use): New function.
(find_must_def_for_use): Ditto.
(find_partial_def_for_use): Ditto.
* tree-ssa-structalias.c (process_unification_queue): Fix bug in
determing whether variable merging changed the solution.
Print out names being unified.
(get_constraint_for_component_ref): Update for integer_id.
(get_constraint_for): Assignments from integers now get
the INTEGER constraint.
(create_alias_vars): Mark var_readonly as address taken.
Add in integer constraint.
(alias_get_name):Call alias_get_name, not get_name, to
get ssa variable name, since alias_get_name knows
what to do with unnamed variables.
Index: tree-into-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-into-ssa.c,v
retrieving revision 2.15.2.5
diff -u -p -r2.15.2.5 tree-into-ssa.c
--- tree-into-ssa.c 28 Sep 2004 17:04:18 -0000 2.15.2.5
+++ tree-into-ssa.c 30 Sep 2004 22:52:36 -0000
@@ -151,9 +151,10 @@ static bool prepare_def_operand_for_rena
static void insert_phi_nodes (bitmap *, bitmap);
static void rewrite_stmt (struct dom_walk_data *, basic_block,
block_stmt_iterator);
-static inline void rewrite_operand (use_operand_p);
static void insert_phi_nodes_for (tree, bitmap *, varray_type *);
static tree get_reaching_def (tree);
+static tree get_intersecting_reaching_def (tree, unsigned int, unsigned int);
+
static hashval_t def_blocks_hash (const void *);
static int def_blocks_eq (const void *, const void *);
static void def_blocks_free (void *);
@@ -976,6 +977,7 @@ rewrite_stmt (struct dom_walk_data *walk
{
stmt_ann_t ann;
tree stmt;
+ unsigned int offset, size;
use_operand_p use_p;
def_operand_p def_p;
ssa_op_iter iter;
@@ -995,9 +997,18 @@ rewrite_stmt (struct dom_walk_data *walk
gcc_assert (!ann->modified);
/* Step 1. Rewrite USES and VUSES in the statement. */
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
- rewrite_operand (use_p);
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VMAYUSE)
+ {
+ if (TREE_CODE (USE_FROM_PTR (use_p)) != SSA_NAME)
+ SET_USE (use_p, get_reaching_def (USE_FROM_PTR (use_p)));
+ }
+ FOR_EACH_SSA_PARTUSE_OPERAND (use_p, offset, size, stmt, iter)
+ {
+ if (TREE_CODE (USE_FROM_PTR (use_p)) != SSA_NAME)
+ SET_USE (use_p, get_intersecting_reaching_def (USE_FROM_PTR (use_p),
+ offset, size));
+ }
/* Step 2. Register the statement's DEF and VDEF operands. */
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
{
@@ -1022,6 +1033,8 @@ ssa_rewrite_stmt (struct dom_walk_data *
stmt_ann_t ann;
tree stmt, var;
ssa_op_iter iter;
+ unsigned int offset;
+ unsigned int size;
use_operand_p use_p;
def_operand_p def_p;
sbitmap names_to_rename = walk_data->global_data;
@@ -1041,12 +1054,19 @@ ssa_rewrite_stmt (struct dom_walk_data *
gcc_assert (!ann->modified);
/* Step 1. Rewrite USES and VUSES in the statement. */
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VMAYUSE)
{
if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (use_p))))
SET_USE (use_p, get_reaching_def (USE_FROM_PTR (use_p)));
}
+ FOR_EACH_SSA_PARTUSE_OPERAND (use_p, offset, size, stmt, iter)
+ {
+ if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (use_p))))
+ SET_USE (use_p, get_intersecting_reaching_def (USE_FROM_PTR (use_p),
+ offset, size));
+ }
+
/* Step 2. Register the statement's DEF and VDEF operands. */
FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
{
@@ -1060,16 +1080,6 @@ ssa_rewrite_stmt (struct dom_walk_data *
}
}
-/* Replace the operand pointed by OP_P with its immediate reaching
- definition. */
-
-static inline void
-rewrite_operand (use_operand_p op_p)
-{
- if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
- SET_USE (op_p, get_reaching_def (USE_FROM_PTR (op_p)));
-}
-
/* Register DEF (an SSA_NAME) to be a new definition for its underlying
variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
into the stack pointed by BLOCK_DEFS_P. */
@@ -1111,6 +1121,122 @@ register_new_def (tree var, tree def, va
set_current_def (var, def);
}
+
+/* Find the may_def in MAYDEFOPS that has USE as its result.
+ Fill in INDEX to be the index of that v_may_def.
+ Return false if we can't find such a may_def, or true if we did. */
+
+static bool
+find_may_def_for_use (v_may_def_optype maydefops, tree use,
+ unsigned int *index)
+{
+ unsigned int i;
+ for (i = 0; i < NUM_V_MAY_DEFS (maydefops); i++)
+ if (V_MAY_DEF_RESULT (maydefops, i) == use)
+ {
+ *index = i;
+ return true;
+ }
+ return false;
+}
+
+
+/* Find the must_def in MUSTDEFOPS that is a MUSTDEF of USE.
+ Fill in INDEX to be the index of that must_def.
+ Return false if we can't find such a must_def, or true if we did. */
+
+static bool
+find_must_def_for_use (v_must_def_optype mustdefops, tree use,
+ unsigned int *index)
+{
+ unsigned int i;
+ for (i = 0; i < NUM_V_MUST_DEFS (mustdefops); i++)
+ if (V_MUST_DEF_OP (mustdefops, i) == use)
+ {
+ *index = i;
+ return true;
+ }
+ return false;
+}
+
+/* Find the nearest definition of USE that overlaps UBITPOS and UBITSIZE */
+
+static tree
+find_partial_def_for_use (tree use,
+ unsigned int ubytepos,
+ unsigned int ubytesize)
+{
+ unsigned int bytesize, bytepos;
+ tree defstmt = SSA_NAME_DEF_STMT (use);
+ v_may_def_optype vmaydefs;
+ v_must_def_optype vmustdefs;
+ bool result;
+ unsigned int i = 0;
+
+ if (TREE_CODE (defstmt) != MODIFY_EXPR)
+ return use;
+ vmustdefs = STMT_V_MUST_DEF_OPS (defstmt);
+ result = find_must_def_for_use (vmustdefs, use, &i);
+ if (result)
+ return use;
+
+ vmaydefs = STMT_V_MAY_DEF_OPS (defstmt);
+ result = find_may_def_for_use (vmaydefs, use, &i);
+ /* If we can't find a may_def or must_def that has this as it's result,
+ the use-def chaining is broken. */
+ gcc_assert (result != false);
+
+ bytesize = V_MAY_DEF_SIZE (vmaydefs, i);
+ bytepos = V_MAY_DEF_OFFSET (vmaydefs, i);
+ if (bytepos + bytesize <= ubytepos
+ || ubytepos + ubytesize <= bytepos)
+ return find_partial_def_for_use (V_MAY_DEF_OP (vmaydefs, i),
+ ubytepos, ubytesize);
+ return use;
+}
+/* Return the current definition for variable VAR. If none is found,
+ create a new SSA name to act as the zeroth definition for VAR. If VAR
+ is call clobbered and there exists a more recent definition of
+ GLOBAL_VAR, return the definition for GLOBAL_VAR. This means that VAR
+ has been clobbered by a function call since its last assignment. */
+
+static tree
+get_intersecting_reaching_def (tree var, unsigned int offset,
+ unsigned int size)
+{
+ tree default_d, currdef_var, avar;
+
+ /* Lookup the current reaching definition for VAR. */
+ default_d = NULL_TREE;
+ currdef_var = get_current_def (var);
+
+ /* If there is no reaching definition for VAR, create and register a
+ default definition for it (if needed). */
+ if (currdef_var == NULL_TREE)
+ {
+ if (TREE_CODE (var) == SSA_NAME)
+ avar = SSA_NAME_VAR (var);
+ else
+ avar = var;
+
+ default_d = default_def (avar);
+ if (default_d == NULL_TREE)
+ {
+ default_d = make_ssa_name (avar, build_empty_stmt ());
+ set_default_def (avar, default_d);
+ }
+ set_current_def (var, default_d);
+ currdef_var = default_d;
+ }
+ else
+ {
+ currdef_var = find_partial_def_for_use (currdef_var,
+ offset, size);
+ }
+
+ return currdef_var;
+}
+
/* Return the current definition for variable VAR. If none is found,
create a new SSA name to act as the zeroth definition for VAR. If VAR
is call clobbered and there exists a more recent definition of
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.9.2.3
diff -u -p -r2.9.2.3 tree-ssa-loop-ivopts.c
--- tree-ssa-loop-ivopts.c 28 Sep 2004 17:04:24 -0000 2.9.2.3
+++ tree-ssa-loop-ivopts.c 30 Sep 2004 22:52:36 -0000
@@ -3983,7 +3983,7 @@ do_rewrite:
orig = unshare_and_remove_ssa_names (*op);
*op = build1 (INDIRECT_REF, TREE_TYPE (*op), with);
-
+
/* Record the original reference, for purposes of alias analysis. */
REF_ORIGINAL (*op) = orig;
}
@@ -4004,6 +4004,7 @@ rewrite_use_address (struct ivopts_data
bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
rewrite_address_base (&bsi, use->op_p, op);
+ mark_new_vars_to_rename (use->stmt, vars_to_rename);
}
/* Rewrites USE (the condition such that one of the arguments is an iv) using
@@ -4497,6 +4498,9 @@ tree_ssa_iv_optimize (struct loops *loop
flow_loop_dump (loop, dump_file, NULL, 1);
if (tree_ssa_iv_optimize_loop (&data, loop))
{
+ rewrite_into_ssa (false);
+ rewrite_into_loop_closed_ssa ();
+
#ifdef ENABLE_CHECKING
verify_loop_closed_ssa ();
verify_stmts ();
Index: tree-ssa-operands.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-operands.c,v
retrieving revision 2.32.2.6
diff -u -p -r2.32.2.6 tree-ssa-operands.c
--- tree-ssa-operands.c 28 Sep 2004 17:04:25 -0000 2.32.2.6
+++ tree-ssa-operands.c 30 Sep 2004 22:52:36 -0000
@@ -1605,7 +1605,7 @@ add_stmt_operand (tree *var_p, tree stmt
tree lhs = NULL;
if (TREE_CODE (stmt) == MODIFY_EXPR)
lhs = TREE_OPERAND (stmt, 0);
- if (v_ann->mem_tag_kind == NOT_A_TAG
+ if (v_ann->mem_tag_kind != TYPE_TAG
&& lhs
&& handled_component_p (lhs))
{
@@ -1640,7 +1640,7 @@ add_stmt_operand (tree *var_p, tree stmt
tree rhs = NULL;
if (TREE_CODE (stmt) == MODIFY_EXPR)
rhs = TREE_OPERAND (stmt, 1);
- if (v_ann->mem_tag_kind == NOT_A_TAG
+ if (v_ann->mem_tag_kind != TYPE_TAG
&& rhs
&& handled_component_p (rhs))
{
@@ -1682,34 +1682,90 @@ add_stmt_operand (tree *var_p, tree stmt
if (flags & opf_is_def)
{
+ tree lhs = NULL;
+ unsigned int bytepos = 0;
+ unsigned int bytesize = ~0;
+
+
/* If the variable is also an alias tag, add a virtual
operand for it, otherwise we will miss representing
references to the members of the variable's alias set.
This fixes the bug in gcc.c-torture/execute/20020503-1.c. */
if (v_ann->is_alias_tag)
append_v_may_def (var, 0, ~0);
-
+
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
+ lhs = TREE_OPERAND (stmt, 0);
+
+ if (v_ann->mem_tag_kind != TYPE_TAG
+ && lhs
+ && handled_component_p (lhs))
+ {
+ HOST_WIDE_INT bitsize;
+ HOST_WIDE_INT bitpos;
+ tree offset;
+ enum machine_mode mode;
+ int unsignedp;
+ int volatilep;
+
+ get_inner_reference (lhs, &bitsize,
+ &bitpos, &offset,
+ &mode, &unsignedp, &volatilep);
+ if (offset == NULL && bitsize != -1)
+ {
+ bytepos = bitpos / BITS_PER_UNIT;
+ bytesize = bitsize / BITS_PER_UNIT;
+
+ }
+ }
+
for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++)
{
tree alias = VARRAY_TREE (aliases, i);
- if (var_ann (alias)->is_alias_tag)
- append_v_may_def (alias, 0, ~0);
- else
- append_v_may_def (alias, 0, tree_low_cst (DECL_SIZE_UNIT (alias), 1));
+ append_v_may_def (alias, bytepos, bytesize);
}
if (s_ann)
s_ann->makes_aliased_stores = 1;
}
else
{
+ tree rhs = NULL;
+ unsigned int bytepos = 0;
+ unsigned int bytesize = ~0;
/* Similarly, append a virtual uses for VAR itself, when
it is an alias tag. */
if (v_ann->is_alias_tag)
append_vuse (var, 0, ~0);
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
+ rhs = TREE_OPERAND (stmt, 1);
+
+ if (v_ann->mem_tag_kind != TYPE_TAG
+ && rhs
+ && handled_component_p (rhs))
+ {
+ HOST_WIDE_INT bitsize;
+ HOST_WIDE_INT bitpos;
+ tree offset;
+ enum machine_mode mode;
+ int unsignedp;
+ int volatilep;
+
+ get_inner_reference (rhs, &bitsize,
+ &bitpos, &offset,
+ &mode, &unsignedp, &volatilep);
+ if (offset == NULL && bitsize != -1)
+ {
+ bytepos = bitpos / BITS_PER_UNIT;
+ bytesize = bitsize / BITS_PER_UNIT;
+ }
+ }
+
for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++)
- append_vuse (VARRAY_TREE (aliases, i), 0, ~0);
-
+ {
+ tree alias = VARRAY_TREE (aliases, i);
+ append_vuse (alias, bytepos, bytesize);
+ }
if (s_ann)
s_ann->makes_aliased_loads = 1;
}
Index: tree-ssa-structalias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-structalias.c,v
retrieving revision 1.1.2.3
diff -u -p -r1.1.2.3 tree-ssa-structalias.c
--- tree-ssa-structalias.c 28 Sep 2004 17:04:26 -0000 1.1.2.3
+++ tree-ssa-structalias.c 30 Sep 2004 22:52:36 -0000
@@ -183,6 +183,11 @@ static varinfo_t var_readonly;
static tree readonly_tree;
static unsigned int readonly_id;
+/* Variable that represents integers. */
+static varinfo_t var_integer;
+static tree integer_tree;
+static unsigned int integer_id;
+
/* Return a new variable info structure consisting for a variable
named NAME, ending at id END, and using constraint graph node
NODE. */
@@ -445,6 +450,7 @@ process_constraint (constraint_t t)
gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
+
/* ANYTHING == ANYTHING is pointless. */
if (lhs.var == anything_id && lhs.var == anything_id)
return;
@@ -608,7 +614,7 @@ get_constraint_for_component_ref (tree t
if (!integer_zerop (t))
{
varlookup = get_constraint_exp_from_ssa_var (t);
- if (varlookup.var <= readonly_id)
+ if (varlookup.var <= integer_id)
result.type = DEREF;
result.var = varlookup.var;
@@ -688,9 +694,9 @@ get_constraint_for (tree t)
{
struct constraint_expr temp;
- if (is_gimple_min_invariant (t) && integer_zerop (t))
+ if (is_gimple_min_invariant (t) && TREE_CODE (t) == INTEGER_CST)
{
- temp.var = nothing_id;
+ temp.var = integer_id;
temp.type = SCALAR;
temp.offset = 0;
return temp;
@@ -1351,10 +1357,10 @@ static bool int_add_graph_edge (constrai
unsigned int, unsigned int);
static bool add_graph_edge (constraint_graph_t, struct constraint_edge);
static bitmap get_graph_weights (constraint_graph_t, struct constraint_edge);
-static void
-/* Merge graph nodes w and n into node n. */
+/* Merge graph nodes w and n into node n. */
+static void
merge_graph_nodes (constraint_graph_t graph, unsigned int n, unsigned int w)
{
VEC(constraint_edge_t) *succvec = graph->succs[w];
@@ -1628,7 +1634,9 @@ process_unification_queue (constraint_gr
unsigned int n = get_varinfo (tounify)->node;
bool domore = false;
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Unifying %d to %d\n", tounify, n);
+ fprintf (dump_file, "Unifying %s to %s\n",
+ get_varinfo (tounify)->name,
+ get_varinfo (n)->name);
if (update_changed)
stats.unified_vars_dynamic++;
else
@@ -1657,13 +1665,16 @@ process_unification_queue (constraint_gr
tounify = VARRAY_UINT (si->unification_queue, i);
if (get_varinfo (tounify)->node != n)
domore = true;
- }
+ }
if (domore)
{
struct constraint_edge edge;
- if (bitmap_a_or_b (tmp, tmp, get_varinfo (n)->solution))
+ /* If the solution changes because of the merging, we need to mark
+ the variable as changed. */
+ if (bitmap_a_or_b (get_varinfo (n)->solution,
+ tmp,
+ get_varinfo (n)->solution))
{
- bitmap_copy (get_varinfo (n)->solution, tmp);
if (update_changed && !TEST_BIT (changed, n))
{
SET_BIT (changed, n);
@@ -2183,9 +2194,18 @@ create_alias_vars (void)
rhs.type = ADDRESSOF;
rhs.var = readonly_id;
rhs.offset = 0;
- var_anything->address_taken = true;
+ var_readonly->address_taken = true;
VEC_safe_push (constraint_t, constraints,
new_constraint (lhs, rhs));
+
+ /* Create the INTEGER variable, used to represent that a variable points
+ to an INTEGER. */
+ integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
+ var_integer = new_var_info (integer_tree, "INTEGER", 4, 3);
+ insert_id_for_tree (integer_tree, 3);
+ var_integer->is_artificial_var = 1;
+ integer_id = 3;
+ VEC_safe_push (varinfo_t, varmap, var_integer);
create_variable_infos ();
/* Now walk all statements and derive aliases. */
@@ -2318,7 +2338,7 @@ alias_get_name (tree t)
{
char *result = alloca (128);
char *newname;
- sprintf (result, "%s_%d", get_name (SSA_NAME_VAR (t)),
+ sprintf (result, "%s_%d", alias_get_name (SSA_NAME_VAR (t)),
SSA_NAME_VERSION (t));
newname = ggc_alloc (strlen (result) + 1);
strcpy (newname, result);