This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Share some INDIRECT_REF nodes [patch]
- From: Diego Novillo <dnovillo at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 3 Feb 2003 22:19:12 -0500
- Subject: [tree-ssa] Share some INDIRECT_REF nodes [patch]
- Organization: Red Hat Canada
The dataflow routines treat INDIRECT_REF nodes of the form
INDIRECT_REF <VAR_DECL> as regular variables. This causes some
grief when we want to add annotation to these variables, because
INDIRECT_REF nodes are not shared.
At first we had changed var_ann() for an INDIRECT_REF node to
access the annotation object for its base pointer. This is a bit
slow because of the additional indirection that it needs to do.
Besides the extra indirection in var_ann(), the fact that
INDIRECT_REF nodes aren't shared also meant that optimizers can't
rely on pointer equality to test if two variables are the same.
More overhead.
The patch also changes get_base_symbol from a recursive into an
iterative function.
Bootstrapped and tested on x86.
Diego.
* tree-dfa.c (find_vars_r): Share INDIRECT_REF nodes whose operand
is a VAR_DECL.
(add_referenced_var): Add additional argument 'sym'. Update all users.
Don't call get_base_symbol.
(add_indirect_ref_var): Rename argument 'var' to 'ptr'.
(htab_hash_var): Remove. Update all users to use htab_hash_pointer.
(htab_var_eq): Remove. Update all users to use htab_eq_pointer.
* tree-flow-inline.h (var_ann): Don't retrieve the annotation of
the base pointer for INDIRECT_REF variables.
(is_aliased): Remove. Update all users.
(is_dereferenced): Remove. Update all users.
(same_var_p): Remove. Update all users to use pointer equality.
* tree-simple.c (get_base_symbol): Convert tail recursion into
iteration.
* tree-ssa.c (rewrite_out_of_ssa): Add FIXME note about overlapping
live ranges for different versions of the same variable.
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.70
diff -d -u -p -r1.1.4.70 tree-dfa.c
--- tree-dfa.c 3 Feb 2003 23:56:24 -0000 1.1.4.70
+++ tree-dfa.c 4 Feb 2003 00:22:38 -0000
@@ -104,7 +104,7 @@ static void add_stmt_operand PARAMS ((t
voperands_t));
static void add_immediate_use PARAMS ((tree, tree));
static tree find_vars_r PARAMS ((tree *, int *, void *));
-static void add_referenced_var PARAMS ((tree, void *));
+static void add_referenced_var PARAMS ((tree, tree, void *));
static void add_indirect_ref_var PARAMS ((tree, void *));
static void compute_immediate_uses_for PARAMS ((tree, int));
static void add_may_alias PARAMS ((tree, tree));
@@ -514,7 +514,8 @@ add_stmt_operand (var_p, stmt, is_def, f
voperands_t prev_vops;
{
bool is_scalar;
- tree var;
+ tree var, deref;
+ varray_type aliases;
var = *var_p;
STRIP_NOPS (var);
@@ -530,7 +531,8 @@ add_stmt_operand (var_p, stmt, is_def, f
if (var == NULL_TREE || !SSA_VAR_P (var))
return;
- if (!is_aliased (var))
+ aliases = may_aliases (var);
+ if (aliases == NULL)
{
/* The variable is not aliased. If it's a scalar, process it as a
real operand. Otherwise, add it to the virtual operands. Note
@@ -562,7 +564,6 @@ add_stmt_operand (var_p, stmt, is_def, f
{
/* The variable is aliased. Add its aliases to the virtual operands. */
size_t i;
- varray_type aliases = may_aliases (var);
if (is_def)
{
@@ -579,12 +580,12 @@ add_stmt_operand (var_p, stmt, is_def, f
/* A definition of a pointer variable 'p' clobbers its associated
indirect variable '*p', because now 'p' is pointing to a different
memory location. */
+ deref = indirect_ref (var);
if (is_def
&& SSA_DECL_P (var)
&& POINTER_TYPE_P (TREE_TYPE (var))
- && is_dereferenced (var))
+ && deref != NULL_TREE)
{
- tree deref = indirect_ref (var);
add_stmt_operand (&deref, stmt, true, true, prev_vops);
/* If the relocation of 'p' is due to an expression that may
@@ -687,7 +688,7 @@ add_vdef (var, stmt, prev_vops)
for (i = 0; i < VARRAY_ACTIVE_SIZE (prev_vops->vdef_ops); i++)
{
tree d = VARRAY_TREE (prev_vops->vdef_ops, i);
- if (same_var_p (var, SSA_NAME_VAR (VDEF_RESULT (d))))
+ if (var == SSA_NAME_VAR (VDEF_RESULT (d)))
{
vdef = d;
break;
@@ -716,7 +717,7 @@ add_vdef (var, stmt, prev_vops)
/* Don't allow duplicate entries. */
for (i = 0; i < VARRAY_ACTIVE_SIZE (ann->vops->vdef_ops); i++)
- if (same_var_p (var, VDEF_RESULT (VARRAY_TREE (ann->vops->vdef_ops, i))))
+ if (var == VDEF_RESULT (VARRAY_TREE (ann->vops->vdef_ops, i)))
return;
VARRAY_PUSH_TREE (ann->vops->vdef_ops, vdef);
@@ -743,7 +744,7 @@ add_vuse (var, stmt, prev_vops)
for (i = 0; i < VARRAY_ACTIVE_SIZE (prev_vops->vuse_ops); i++)
{
tree u = VARRAY_TREE (prev_vops->vuse_ops, i);
- if (same_var_p (var, SSA_NAME_VAR (u)))
+ if (var == SSA_NAME_VAR (u))
{
vuse = u;
break;
@@ -774,7 +775,7 @@ add_vuse (var, stmt, prev_vops)
/* Don't allow duplicate entries. */
for (i = 0; i < VARRAY_ACTIVE_SIZE (ann->vops->vuse_ops); i++)
- if (same_var_p (var, VARRAY_TREE (ann->vops->vuse_ops, i)))
+ if (var == VARRAY_TREE (ann->vops->vuse_ops, i))
return;
VARRAY_PUSH_TREE (ann->vops->vuse_ops, var);
@@ -1079,6 +1080,8 @@ dump_variable (file, var)
FILE *file;
tree var;
{
+ varray_type aliases;
+
if (var == NULL_TREE)
{
fprintf (file, "<nil>");
@@ -1087,9 +1090,9 @@ dump_variable (file, var)
print_generic_expr (file, var, 0);
- if (is_aliased (var))
+ aliases = may_aliases (var);
+ if (aliases)
{
- varray_type aliases = may_aliases (var);
size_t i, num_aliases = VARRAY_ACTIVE_SIZE (aliases);
fprintf (file, ", may aliases: ");
for (i = 0; i < num_aliases; i++)
@@ -1435,13 +1438,15 @@ compute_may_aliases ()
VARRAY_WIDE_INT_INIT (addressable_vars_alias_set, 20, "addressable_vars_alias_set");
/* Hash table of all the objects the SSA builder needs to be aware of. */
- vars_found = htab_create (50, htab_hash_var, htab_var_eq, NULL);
+ vars_found = htab_create (50, htab_hash_pointer, htab_eq_pointer, NULL);
/* Hash table of all the unique INDIRECT_REFs found. */
- indirect_refs_found = htab_create (50, htab_hash_var, htab_var_eq, NULL);
+ indirect_refs_found = htab_create (50, htab_hash_pointer, htab_eq_pointer,
+ NULL);
/* Hash table of all the unique addressable variables found. */
- addressable_vars_found = htab_create (50, htab_hash_var, htab_var_eq, NULL);
+ addressable_vars_found = htab_create (50, htab_hash_pointer, htab_eq_pointer,
+ NULL);
walk_state[0] = vars_found;
walk_state[1] = indirect_refs_found;
@@ -1786,7 +1791,7 @@ add_may_alias (var, alias)
/* Avoid adding duplicates. */
for (i = 0; i < VARRAY_ACTIVE_SIZE (ann->may_aliases); i++)
- if (same_var_p (alias, VARRAY_TREE (ann->may_aliases, i)))
+ if (alias == VARRAY_TREE (ann->may_aliases, i))
return;
VARRAY_PUSH_TREE (ann->may_aliases, alias);
@@ -1987,10 +1992,31 @@ find_vars_r (tp, walk_subtrees, data)
{
if (SSA_VAR_P (*tp))
{
- add_referenced_var (*tp, data);
+ tree sym, var, deref;
+
+ var = *tp;
+ sym = get_base_symbol (var);
+
+ /* If VAR is an INDIRECT_REF node for a VAR_DECL pointer, rewrite *TP
+ with the first INDIRECT_REF we found (if any). We need to share
+ INDIRECT_REF nodes because we treat them as regular variables and
+ several passes rely on pointer equality for testing if two variables
+ are the same. */
+ if (TREE_CODE (var) == INDIRECT_REF && DECL_P (TREE_OPERAND (var, 0)))
+ {
+ deref = indirect_ref (sym);
+ if (deref)
+ *tp = deref;
+ else
+ set_indirect_ref (sym, var);
+ }
+
+ add_referenced_var (var, sym, data);
+
return NULL_TREE;
}
+
/* Function calls. Consider them a reference for an artificial variable
called GLOBAL_VAR. This variable is a pointer that will alias every
global variable and locals that have had their address taken. The
@@ -2028,46 +2054,28 @@ find_vars_r (tp, walk_subtrees, data)
}
-/* Add VAR to the list of dereferenced variables. Also add it to the sets
- ADDRESSABLE_VARS or INDIRECT_REFS needed for alias analysis. DATA is an
- array with three hash tables used to avoid adding the same variable more
- than once to its corresponding set. Note that this function assumes
- that VAR is a valid SSA variable. */
+/* Add VAR to the list of dereferenced variables. SYM is the base symbol
+ when VAR is anything but a _DECL node. Otherwise, SYM and VAR are the
+ same tree.
+
+ Also add VAR to the sets ADDRESSABLE_VARS or INDIRECT_REFS needed for
+ alias analysis. DATA is an array with three hash tables used to avoid
+ adding the same variable more than once to its corresponding set. Note
+ that this function assumes that VAR is a valid SSA variable. */
static void
-add_referenced_var (var, data)
+add_referenced_var (var, sym, data)
tree var;
+ tree sym;
void *data;
{
void **slot;
- tree sym;
- tree ind;
htab_t vars_found = ((htab_t *) data)[0];
htab_t indirect_refs_found = ((htab_t *) data)[1];
htab_t addressable_vars_found = ((htab_t *) data)[2];
- /* Get the underlying symbol. We will need it shortly. */
- if (TREE_CODE (var) == INDIRECT_REF)
- {
- sym = get_base_symbol (TREE_OPERAND (var, 0));
- ind = var;
-
- if (!is_dereferenced (sym))
- set_indirect_ref (sym, ind);
- else
- ind = indirect_ref (sym);
- }
- else
- {
- sym = get_base_symbol (var);
- ind = NULL_TREE;
- }
-
- /* Make VAR either the canonical INDIRECT_REF or the real symbol. */
- var = (ind ? ind : var);
-
/* First handle an INDIRECT_REF. */
- if (ind)
+ if (TREE_CODE (var) == INDIRECT_REF)
{
slot = htab_find_slot (indirect_refs_found, (void *) var, INSERT);
if (*slot == NULL)
@@ -2115,49 +2123,18 @@ add_referenced_var (var, data)
pointer decl. */
static void
-add_indirect_ref_var (var, data)
- tree var;
+add_indirect_ref_var (ptr, data)
+ tree ptr;
void *data;
{
- tree deref = indirect_ref (var);
-
+ tree deref = indirect_ref (ptr);
if (deref == NULL_TREE)
{
- deref = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (var)), var);
- set_indirect_ref (var, deref);
+ deref = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (ptr)), ptr);
+ set_indirect_ref (ptr, deref);
}
- add_referenced_var (deref, data);
-}
-
-
-/* Return a hash value for a variable. If the variable is an INDIRECT_REF
- node, return the hash value for its pointer. */
-
-hashval_t
-htab_hash_var (p)
- const void *p;
-{
- tree v = (tree) p;
- if (TREE_CODE (v) == INDIRECT_REF)
- v = TREE_OPERAND (v, 0);
- return htab_hash_pointer (v);
-}
-
-
-/* Check if variables V1 and V2 are the same.
- Two variables are the same if both V1 and V2 are pointers to the same
- variable, or if they are both indirect refs to the same variable. */
-
-int
-htab_var_eq (v1, v2)
- const void *v1;
- const void *v2;
-{
- return (v1 == v2
- || (TREE_CODE ((tree) v1) == INDIRECT_REF
- && TREE_CODE ((tree) v2) == INDIRECT_REF
- && TREE_OPERAND ((tree) v1, 0) == TREE_OPERAND ((tree) v2, 0)));
+ add_referenced_var (deref, ptr, data);
}
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow-inline.h,v
retrieving revision 1.1.2.22
diff -d -u -p -r1.1.2.22 tree-flow-inline.h
--- tree-flow-inline.h 3 Feb 2003 01:26:53 -0000 1.1.2.22
+++ tree-flow-inline.h 4 Feb 2003 00:22:38 -0000
@@ -33,19 +33,11 @@ var_ann (t)
if (!SSA_VAR_P (t))
abort ();
#endif
- /* SSA_NAME nodes share the same annotations as the VAR_DECL node that
- they wrap. */
+ /* SSA_NAME nodes share the same annotations as the VAR_DECL/INDIRECT_REF
+ node that they wrap. */
if (TREE_CODE (t) == SSA_NAME)
t = SSA_NAME_VAR (t);
- /* INDIRECT_REF nodes share the annotation from the canonical
- dereference for their base pointer (see find_vars_r). */
- if (TREE_CODE (t) == INDIRECT_REF)
- {
- t = get_base_symbol (t);
- t = ((var_ann_t) t->common.ann)->indirect_ref;
- }
-
return (t->common.ann && t->common.ann->common.type == VAR_ANN)
? (var_ann_t) t->common.ann
: NULL;
@@ -84,13 +76,6 @@ may_aliases (var)
}
static inline bool
-is_aliased (var)
- tree var;
-{
- return may_aliases (var) != NULL;
-}
-
-static inline bool
may_alias_global_mem_p (var)
tree var;
{
@@ -117,13 +102,6 @@ indirect_ref (var)
return ann ? ann->indirect_ref : NULL_TREE;
}
-static inline bool
-is_dereferenced (var)
- tree var;
-{
- return indirect_ref (var) != NULL_TREE;
-}
-
static inline int
get_lineno (expr)
tree expr;
@@ -333,14 +311,6 @@ is_exec_stmt (t)
tree t;
{
return (t && t != empty_stmt_node && t != error_mark_node);
-}
-
-static inline bool
-same_var_p (v1, v2)
- tree v1;
- tree v2;
-{
- return htab_var_eq ((const void *)v1, (const void *)v2);
}
#endif /* _TREE_FLOW_INLINE_H */
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.49
diff -d -u -p -r1.1.4.49 tree-flow.h
--- tree-flow.h 3 Feb 2003 23:56:25 -0000 1.1.4.49
+++ tree-flow.h 4 Feb 2003 00:22:38 -0000
@@ -172,9 +172,7 @@ static inline void unmodify_stmt PARAMS
static inline bool stmt_modified_p PARAMS ((tree));
static inline tree create_indirect_ref PARAMS ((tree));
static inline varray_type may_aliases PARAMS ((tree));
-static inline bool is_aliased PARAMS ((tree));
static inline bool may_alias_global_mem_p PARAMS ((tree));
-static inline bool is_dereferenced PARAMS ((tree));
static inline void set_indirect_ref PARAMS ((tree, tree));
static inline tree indirect_ref PARAMS ((tree));
static inline int get_lineno PARAMS ((tree));
@@ -339,9 +337,6 @@ extern void compute_reached_uses PARAMS
extern void compute_immediate_uses PARAMS ((int));
extern void compute_reaching_defs PARAMS ((int));
extern tree copy_stmt PARAMS ((tree));
-extern hashval_t htab_hash_var PARAMS ((const void *));
-extern int htab_var_eq PARAMS ((const void *, const void *));
-static inline bool same_var_p PARAMS ((tree, tree));
extern void dump_alias_info PARAMS ((FILE *));
extern void debug_alias_info PARAMS ((void));
extern tree get_virtual_var PARAMS ((tree));
Index: tree-simple.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-simple.c,v
retrieving revision 1.1.4.27
diff -d -u -p -r1.1.4.27 tree-simple.c
--- tree-simple.c 3 Feb 2003 01:26:53 -0000 1.1.4.27
+++ tree-simple.c 4 Feb 2003 00:22:38 -0000
@@ -937,30 +937,34 @@ tree
get_base_symbol (t)
tree t;
{
- STRIP_NOPS (t);
-
- switch (TREE_CODE (t))
+ do
{
- case VAR_DECL:
- case FUNCTION_DECL:
- case PARM_DECL:
- case FIELD_DECL:
- case LABEL_DECL:
- return t;
+ STRIP_NOPS (t);
- case SSA_NAME:
- return get_base_symbol (SSA_NAME_VAR (t));
+ if (DECL_P (t))
+ return t;
- case ARRAY_REF:
- case COMPONENT_REF:
- case INDIRECT_REF:
- case REALPART_EXPR:
- case IMAGPART_EXPR:
- return get_base_symbol (TREE_OPERAND (t, 0));
+ switch (TREE_CODE (t))
+ {
+ case SSA_NAME:
+ t = SSA_NAME_VAR (t);
+ break;
- default:
- return NULL_TREE;
+ case ARRAY_REF:
+ case COMPONENT_REF:
+ case INDIRECT_REF:
+ case REALPART_EXPR:
+ case IMAGPART_EXPR:
+ t = TREE_OPERAND (t, 0);
+ break;
+
+ default:
+ return NULL_TREE;
+ }
}
+ while (t);
+
+ return t;
}
void
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.43
diff -d -u -p -r1.1.2.43 tree-ssa-ccp.c
--- tree-ssa-ccp.c 3 Feb 2003 01:26:53 -0000 1.1.2.43
+++ tree-ssa-ccp.c 4 Feb 2003 00:22:38 -0000
@@ -1074,7 +1074,7 @@ static hashval_t
value_map_hash (p)
const void *p;
{
- return htab_hash_var ((const void *)((const struct value_map_d *)p)->var);
+ return htab_hash_pointer ((const void *)((const struct value_map_d *)p)->var);
}
static int
@@ -1082,6 +1082,6 @@ value_map_eq (p1, p2)
const void *p1;
const void *p2;
{
- return same_var_p (((const struct value_map_d *)p1)->var,
- ((const struct value_map_d *)p2)->var);
+ return ((const struct value_map_d *)p1)->var
+ == ((const struct value_map_d *)p2)->var;
}
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.46
diff -d -u -p -r1.1.4.46 tree-ssa.c
--- tree-ssa.c 3 Feb 2003 23:56:25 -0000 1.1.4.46
+++ tree-ssa.c 4 Feb 2003 00:22:38 -0000
@@ -495,7 +495,12 @@ rewrite_block (bb)
}
-/* Take function FNDECL out of SSA form. */
+/* Take function FNDECL out of SSA form.
+
+ FIXME: Need to support overlapping live ranges for different versions of
+ the same variable. At the moment, we will silently generate
+ wrong code if an optimizer pass moves code so that two versions
+ of the same variable have overlapping live ranges. */
void
rewrite_out_of_ssa (fndecl)
@@ -993,7 +998,7 @@ static hashval_t
def_blocks_hash (p)
const void *p;
{
- return htab_hash_var ((const void *)((const struct def_blocks_d *)p)->var);
+ return htab_hash_pointer ((const void *)((const struct def_blocks_d *)p)->var);
}
static int
@@ -1001,8 +1006,8 @@ def_blocks_eq (p1, p2)
const void *p1;
const void *p2;
{
- return same_var_p (((const struct def_blocks_d *)p1)->var,
- ((const struct def_blocks_d *)p2)->var);
+ return ((const struct def_blocks_d *)p1)->var
+ == ((const struct def_blocks_d *)p2)->var;
}
@@ -1012,7 +1017,7 @@ static hashval_t
currdef_hash (p)
const void *p;
{
- return htab_hash_var ((const void *)((const struct currdef_d *)p)->var);
+ return htab_hash_pointer ((const void *)((const struct currdef_d *)p)->var);
}
static int
@@ -1020,8 +1025,8 @@ currdef_eq (p1, p2)
const void *p1;
const void *p2;
{
- return same_var_p (((const struct currdef_d *)p1)->var,
- ((const struct currdef_d *)p2)->var);
+ return ((const struct currdef_d *)p1)->var
+ == ((const struct currdef_d *)p2)->var;
}