This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Improve handling of call-clobbered variables [patch]
- From: Diego Novillo <dnovillo at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 21 Mar 2003 08:34:46 -0500
- Subject: [tree-ssa] Improve handling of call-clobbered variables [patch]
- Organization: Red Hat Canada
Up until now, call-clobbered variables were handled by creating a
fake variable (global_var) that was made to alias all call
clobbered variables.
While this approach worked, it was too pessimistic for two
reasons:
(a) Call clobbered variables would never be renamed into SSA form
because they were aliased to GLOBAL_VAR.
(b) When using type-based aliasing (the default), the presence of
GLOBAL_VAR would often cause it to be the alias tag for
*every* aliased variable in the function.
This patch implements a new approach that also makes use of
GLOBAL_VAR, but in a different way. GLOBAL_VAR is treated like a
regular variable but it cannot alias any other variable.
Whenever a call to a clobbering function is made or a
call-clobbered variable is assigned a new value, the compiler
inserts a virtual definition for GLOBAL_VAR at the site.
When renaming statement operands, if the operand is
call-clobbered, we check if the current definition for the
operand is killed by a more recent definition of GLOBAL_VAR
coming from a function call. If so, we create a new name for the
operand and set its originating statement to a unique expression
(GLOBAL_CLOBBER_EXPR) that is there only to mean that the operand
comes from out of this function and has an unknown value.
This uncovered a few bugs in the constant propagator and alias
analysis pass. These bugs were masked by having GLOBAL_VAR alias
just about everything else.
Daniel, I disabled the uses of GLOBAL_VAR in the points-to alias
analysis pass. I believe that all that code can be removed, but
I'll let you decide how to handle it.
The patch is compile-time neutral and provides a few more
opportunities for optimization.
Bootstrapped and tested x86 and x86-64. Will commit after
the (slow) bootstrap cycle finishes on ppc.
Diego.
* Makefile.in (gtype-desc.o): Add dependency on $(TREE_FLOW_H).
* tree-alias-common.c (get_alias_var_decl): Disable references to
global_var everywhere.
* tree-dfa.c (create_global_var): New function.
(num_referenced_vars, num_aliased_objects): Change type to size_t.
Update all users.
(aliased_objects, aliased_objects_base, aliased_objects_alias_set):
Add GTY markers.
(num_call_clobbered_vars, call_clobbered_vars): New local
variables.
(global_clobber_expr): New variable representing the defining
statement for clobbered variables.
(get_expr_operands): When processing CALL_EXPR nodes, mark the
statement if it makes a call to a clobbering function.
If the call is to a clobbering function add a VDEF<*p> for every
pointer argument 'p'.
(add_stmt_operand): If the statement is an assignment to a call
clobbered variable, add a VDEF for GLOBAL_VAR.
(compute_immediate_uses_for): Ignore def-use edges to
GLOBAL_CLOBBER_EXPR.
(create_stmt_ann): Abort if trying to annotate GLOBAL_CLOBBER_EXPR.
(dump_variable): Show if a variable is call clobbered.
(dump_dfa_stats): Show information about call clobbered variables.
(compute_may_aliases): Minor formatting changes.
(compute_alias_sets): Don't treat GLOBAL_VAR as a special case.
(may_alias_p): Likewise.
Check for structure aliasing when either PTR or VAR are a
structure. Don't do it only when both are structures.
(dump_alias_info): Show all aliases of each variable.
(find_vars_r): When processing a CALL_EXPR node, set
walk_state->is_store if the function may clobber and create a VDEF
for GLOBAL_VAR.
(add_indirect_ref_var): Change 'void *' argument to 'struct
walk_state *'. Update all users.
(add_referenced_var): Likewise.
If a potentially aliased variabe is not declared 'const', add it to
the list of call clobbered variables.
* tree-flow.h (struct var_ann_d): Add field 'is_call_clobbered'.
Change type of field 'uid' to size_t. Update all users.
(stmt_ann_d): Add field 'makes_clobbering_call'.
(next_tree_ref_id): Remove unused variable.
(global_clobber_expr): Declare.
(call_clobbered_vars): Declare.
(num_call_clobbered_vars): Declare.
(call_clobbered_var): New inline function.
* tree-ssa-ccp.c (visit_phi_node): If the LHS of a PHI node is
volatile, mark the PHI node VARYING without checking its arguments.
(visit_assignment): Likewise.
(set_value): Remove. Update all users.
(likely_value): If the statement makes aliased loads or has
volatile operands, consider it VARYING.
(get_value): Variables whose definition originates at
GLOBAL_CLOBBER_EXPR are considered VARYING.
(get_default_value): If a variable is volatile, consider it
VARYING.
* tree-ssa-dce.c (mark_tree_necessary): Ignore GLOBAL_CLOBBER_EXPR.
* tree-ssa.c (get_reaching_def): Rename from currdef_for. Remove
second argument. Update all users. Callers that use to call
currdef_for with the second argument set to false now call
get_value_for.
If the variable doesn't have a reaching definition, create a
default one.
If the variable is call clobbered and its reaching definition is
killed by a more recent definition to GLOBAL_VAR, return the
definition for GLOBAL_VAR.
(rewrite_block): When adding arguments to a PHI node, if the
argument is GLOBAL_VAR and it comes from a call clobbering
function, mark the PHI node as clobbering as well.
(rewrite_operand): Add argument 'block_defs_p'. Update all users.
Don't update the base pointer of an INDIRECT_REF node if it's
reached by GLOBAL_VAR.
If the reaching definition for the operand is killed by a more
recent definition for GLOBAL_VAR, create a new name for the operand
originating at GLOBAL_CLOBBER_EXPR.
(init_tree_ssa): Initialize global_var, global_clobber_expr,
num_call_clobbered_vars and call_clobbered_vars.
Remove code to create global_var.
(delete_tree_ssa): Reset global_clobber_expr,
num_call_clobbered_vars and call_clobbered_vars.
(var_is_live): If 'var' is clobbered, check if there is another
more recent definition of GLOBAL_VAR that may reach it.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.79
diff -d -u -p -r1.903.2.79 Makefile.in
--- Makefile.in 10 Mar 2003 20:26:25 -0000 1.903.2.79
+++ Makefile.in 20 Mar 2003 18:32:36 -0000
@@ -1396,7 +1396,7 @@ version.o: version.c version.h
gtype-desc.o: gtype-desc.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) varray.h \
$(HASHTAB_H) $(TREE_H) $(RTL_H) function.h insn-config.h $(EXPR_H) $(OPTABS_H) \
libfuncs.h debug.h $(GGC_H) bitmap.h $(BASIC_BLOCK_H) hard-reg-set.h \
- ssa.h cselib.h insn-addr.h
+ ssa.h cselib.h insn-addr.h $(TREE_FLOW_H)
ggc-common.o: ggc-common.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(GGC_H) \
$(HASHTAB_H) toplev.h $(PARAMS_H)
Index: tree-alias-common.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-alias-common.c,v
retrieving revision 1.1.2.20
diff -d -u -p -r1.1.2.20 tree-alias-common.c
--- tree-alias-common.c 26 Feb 2003 16:26:03 -0000 1.1.2.20
+++ tree-alias-common.c 20 Mar 2003 18:32:37 -0000
@@ -162,9 +162,11 @@ get_alias_var_decl (decl)
newvar = create_fun_alias_var (decl, 0);
else
{
+#if 0
if (decl_function_context (decl) == NULL && decl != global_var)
return get_alias_var (global_var);
else
+#endif
newvar = create_alias_var (decl);
}
@@ -292,7 +294,12 @@ intra_function_call (args)
{
size_t l = VARRAY_ACTIVE_SIZE (args);
size_t i;
+#if 0
alias_typevar av = get_alias_var (global_var);
+#else
+ alias_typevar av = NULL;
+#endif
+
/* We assume that an actual parameter can point to any global. */
for (i = 0; i < l; i++)
@@ -727,6 +734,7 @@ create_fun_alias_var (decl, force)
either we are interprocedural, or we can do ip on all
statics + this function has been defined + it's not an
external function. */
+#if 0
if (POINTER_TYPE_P (TREE_TYPE (arg))
&& !current_alias_ops->ip
/* FIXME: Need to let analyzer decide in partial case. */
@@ -735,6 +743,7 @@ create_fun_alias_var (decl, force)
|| TREE_PUBLIC (decl)))
current_alias_ops->addr_assign (current_alias_ops, tvar,
get_alias_var (global_var));
+#endif
}
}
else if (TYPE_ARG_TYPES (TREE_TYPE (decl)) != NULL)
@@ -753,6 +762,7 @@ create_fun_alias_var (decl, force)
either we are interprocedural, or we can do ip on all
statics + this function has been defined + it's not an
external function. */
+#if 0
if (POINTER_TYPE_P (TREE_TYPE (fakedecl))
&& !current_alias_ops->ip
/* FIXME: need to let analyzer decide in partial case. */
@@ -761,6 +771,7 @@ create_fun_alias_var (decl, force)
|| TREE_PUBLIC (decl)))
current_alias_ops->addr_assign (current_alias_ops, tvar,
get_alias_var (global_var));
+#endif
}
}
/* Functions declared like void f() are *not* equivalent to void
@@ -1040,46 +1051,62 @@ ptr_may_alias_var (ptr, var)
if (DECL_P (ptr))
{
ptrtv = DECL_PTA_TYPEVAR (ptr);
+#if 0
if (DECL_CONTEXT (ptr) == NULL)
ptrtv = DECL_PTA_TYPEVAR (global_var);
if (!ptrtv && !current_alias_ops->ip && ptr != global_var)
abort ();
else if (!ptrtv)
+#endif
+ if (!ptrtv)
return false;
}
else
{
+#if 0
if (DECL_CONTEXT (ptr) == NULL)
entry.key = global_var;
else
+#endif
entry.key = ptr;
result = htab_find (alias_annot, &entry);
+#if 0
if (!result && !current_alias_ops->ip && ptr != global_var)
abort ();
else if (!result)
+#endif
+ if (!result)
return false;
ptrtv = result->value;
}
if (DECL_P (var))
{
vartv = DECL_PTA_TYPEVAR (var);
+#if 0
if (DECL_CONTEXT (var) == NULL)
vartv = DECL_PTA_TYPEVAR (global_var);
if (!vartv && !current_alias_ops->ip && var != global_var)
abort ();
else if (!vartv)
+#endif
+ if (!vartv)
return false;
}
else
{
+#if 0
if (DECL_CONTEXT (var) == NULL)
entry.key = global_var;
else
+#endif
entry.key = var;
result = htab_find (alias_annot, &entry);
+#if 0
if (!result && !current_alias_ops->ip && var != global_var)
abort ();
else if (!result)
+#endif
+ if (!result)
return false;
vartv = result->value;
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.88
diff -d -u -p -r1.1.4.88 tree-dfa.c
--- tree-dfa.c 11 Mar 2003 16:34:53 -0000 1.1.4.88
+++ tree-dfa.c 20 Mar 2003 18:32:37 -0000
@@ -81,6 +81,14 @@ struct alias_set_d
static varray_type alias_sets;
+/* State information for find_vars_r. */
+struct walk_state
+{
+ htab_t vars_found;
+ htab_t aliased_objects_found;
+ int is_store;
+};
+
/* Flags to describe operand properties in get_stmt_operands and helpers. */
static const int opf_none = 0;
@@ -120,25 +128,27 @@ 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, tree, void *));
-static void add_indirect_ref_var PARAMS ((tree, void *));
+static void add_referenced_var PARAMS ((tree, tree,
+ struct walk_state *));
+static void add_indirect_ref_var PARAMS ((tree, struct walk_state *));
static void compute_immediate_uses_for PARAMS ((tree, int));
static void add_may_alias PARAMS ((tree, tree, tree, tree));
static bool call_may_clobber PARAMS ((tree));
static void find_vla_decls PARAMS ((tree));
static tree find_vla_decls_r PARAMS ((tree *, int *, void *));
+static void create_global_var PARAMS ((void));
/* Global declarations. */
/* The total number of referenced variables in the function. */
-unsigned long num_referenced_vars;
+size_t num_referenced_vars;
/* Array of all variables referenced in the function. */
varray_type referenced_vars;
/* The total number of unique aliased objects in the function. */
-static unsigned long num_aliased_objects;
+static size_t num_aliased_objects;
/* Arrays for all the potentially aliased memory objects in the
function.
@@ -150,23 +160,33 @@ static unsigned long num_aliased_objects
* Addressable variable which is used or assigned
* global scoped variable which is used or assigned
* ASM_OUTPUTs, ASM_CLOBBERS and ASM_INPUTs
- * CALL_EXPRs which load and store GLOBAL_VAR
ALIASED_OBJECTS contains the object
ALIASED_OBJECTS_BASE contains the base symbol for those objects
ALIASED_OBJECTS_ALIAS_SET contains the alias set for those objects. */
+static GTY(()) varray_type aliased_objects;
+static GTY(()) varray_type aliased_objects_base;
+static GTY(()) varray_type aliased_objects_alias_set;
-static varray_type aliased_objects;
-static varray_type aliased_objects_base;
-static varray_type aliased_objects_alias_set;
+/* The total number of unique call clobbered variables in the function. */
+size_t num_call_clobbered_vars;
+
+/* Arrays for all the call clobbered variables in the function. */
+varray_type call_clobbered_vars;
/* Artificial variable used to model the effects of function calls on every
variable that they may use and define. Calls to non-const and non-pure
- functions are assumed to use and clobber this variable.
-
- Aliased loads and stores will be considered aliased with this variable. */
+ functions are assumed to clobber this variable. Similarly, assignments
+ to call-clobbered variables will make a clobbering definition to
+ GLOBAL_VAR. */
tree global_var;
+/* Artificial expression serving as the definition statement for all the
+ clobbered variables in the function. When an operand is reached by a
+ clobbering function call, a new SSA version is created with its
+ originating definition set to GLOBAL_CLOBBER_EXPR. */
+tree global_clobber_expr;
+
/* Get the operands of statement STMT. Note that repeated calls to
get_stmt_operands for the same statement will do nothing until the
statement is marked modified by a call to modify_stmt(). */
@@ -375,29 +395,35 @@ get_expr_operands (stmt, expr_p, flags,
}
/* Function calls. Add every argument to USES. If the callee is
- neither pure nor const, create a use and clobbering definition of
- *GLOBAL_VAR (See find_vars_r). */
+ neither pure nor const, create a VDEF reference for GLOBAL_VAR
+ (See find_vars_r). */
if (code == CALL_EXPR)
{
+ int flags;
tree op;
bool may_clobber = call_may_clobber (expr);
/* Find uses in the called function. */
get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_none, prev_vops);
+ /* If the called function is neither pure nor const, we create a
+ clobbering definition of GLOBAL_VAR and mark the statement so that
+ the SSA renaming pass considers this statement a definition site
+ for every call clobbered variable in the program (i.e., the
+ variables mentioned in CALL_CLOBBERED_VARS). */
if (may_clobber)
{
- /* If the called function is neither pure nor const, we create a
- clobbering definition of *GLOBAL_VAR. */
- tree v = indirect_ref (global_var);
- add_stmt_operand (&v, stmt, opf_is_def|opf_force_vop, prev_vops);
+ stmt_ann (stmt)->makes_clobbering_call = may_clobber;
+ add_stmt_operand (&global_var, stmt, opf_is_def|opf_force_vop,
+ prev_vops);
}
- /* Add all the arguments to the function. If the function will not
- clobber any local variable, check if it may dereference a local
- pointer. If so, add a VUSE for the dereferenced pointer. This is
- to address the following problem: Suppose that function 'foo' is
- constant but receives a pointer to a local variable:
+ /* Add all the arguments to the function. For every pointer argument
+ to the function, add a VUSE for its dereferenced pointer (if the
+ function is pure or const) or a VDEF for its dereferenced pointer
+ (if the function may clobber). This is to address the following
+ problem: Suppose that function 'foo' receives a pointer to a local
+ variable:
int foo (int *x)
{
@@ -416,23 +442,28 @@ get_expr_operands (stmt, expr_p, flags,
to kill the assignment to 'i' because it's never used in bar().
To address this problem, we add a VUSE<*p> at the call site of
foo(). */
+ flags = opf_force_vop | opf_ignore_bp;
+ if (may_clobber)
+ flags |= opf_is_def;
+
for (op = TREE_OPERAND (expr, 1); op; op = TREE_CHAIN (op))
{
tree arg = TREE_VALUE (op);
add_stmt_operand (&TREE_VALUE (op), stmt, opf_none, prev_vops);
- /* If the function may not clobber locals, add a VUSE<*p> for
- every pointer p passed in the argument list (see note above). */
- if (!may_clobber
- && SSA_DECL_P (arg)
+ /* Add a VUSE<*p> or VDEF<*p> for every pointer p passed in the
+ argument list (see note above). */
+ if (SSA_DECL_P (arg)
&& POINTER_TYPE_P (TREE_TYPE (arg)))
{
tree deref = indirect_ref (arg);
- /* We have already added a real USE for the pointer. We
- don't need to add a VUSE for it as well. */
- add_stmt_operand (&deref, stmt, opf_force_vop|opf_ignore_bp,
- prev_vops);
+
+ /* By default, adding a reference to an INDIRECT_REF
+ variable, adds a VUSE of the base pointer. Since we have
+ already added a real USE for the pointer, we don't need to
+ add a VUSE for it as well. */
+ add_stmt_operand (&deref, stmt, flags, prev_vops);
}
}
@@ -658,6 +689,15 @@ add_stmt_operand (var_p, stmt, flags, pr
add_stmt_operand (&TREE_OPERAND (var, 0), stmt, opf_force_vop,
prev_vops);
}
+
+ /* If VAR is call clobbered and it is being modified, add a VDEF to
+ GLOBAL_VAR. This way, there will be a def-use link between this
+ modification and the next function call. Otherwise, if there are no
+ other uses of VAR in the code, the assignment will appear dead. */
+ if ((flags & opf_is_def)
+ && global_var
+ && var_ann (var)->is_call_clobbered)
+ add_vdef (global_var, stmt, prev_vops);
}
@@ -949,7 +989,8 @@ compute_immediate_uses_for (stmt, flags)
for (i = 0; i < PHI_NUM_ARGS (stmt); i++)
{
tree imm_rdef_stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF (stmt, i));
- if (imm_rdef_stmt != empty_stmt_node)
+ if (imm_rdef_stmt != empty_stmt_node
+ && imm_rdef_stmt != global_clobber_expr)
add_immediate_use (imm_rdef_stmt, stmt);
}
return;
@@ -965,7 +1006,8 @@ compute_immediate_uses_for (stmt, flags)
{
tree *use_p = VARRAY_GENERIC_PTR (ops, i);
tree imm_rdef_stmt = SSA_NAME_DEF_STMT (*use_p);
- if (imm_rdef_stmt != empty_stmt_node)
+ if (imm_rdef_stmt != empty_stmt_node
+ && imm_rdef_stmt != global_clobber_expr)
add_immediate_use (imm_rdef_stmt, stmt);
}
}
@@ -977,7 +1019,8 @@ compute_immediate_uses_for (stmt, flags)
{
tree vuse = VARRAY_TREE (ops, i);
tree imm_rdef_stmt = SSA_NAME_DEF_STMT (vuse);
- if (imm_rdef_stmt != empty_stmt_node)
+ if (imm_rdef_stmt != empty_stmt_node
+ && imm_rdef_stmt != global_clobber_expr)
add_immediate_use (imm_rdef_stmt, stmt);
}
}
@@ -1068,6 +1111,7 @@ create_stmt_ann (t)
#if defined ENABLE_CHECKING
if (t == empty_stmt_node
+ || t == global_clobber_expr
|| t == NULL_TREE
|| TREE_CODE_CLASS (TREE_CODE (t)) == 'c'
|| TREE_CODE_CLASS (TREE_CODE (t)) == 't')
@@ -1122,10 +1166,10 @@ void
dump_referenced_vars (file)
FILE *file;
{
- unsigned long i;
+ size_t i;
- fprintf (file, "\nReferenced variables in %s: %lu\n\n",
- get_name (current_function_decl), num_referenced_vars);
+ fprintf (file, "\nReferenced variables in %s: %u\n\n",
+ get_name (current_function_decl), (unsigned) num_referenced_vars);
for (i = 0; i < num_referenced_vars; i++)
{
@@ -1185,6 +1229,9 @@ dump_variable (file, var)
if (may_point_to_global_mem_p (var))
fprintf (file, ", may point to global memory");
+ if (var_ann (var)->is_call_clobbered)
+ fprintf (file, ", call clobbered");
+
fprintf (file, "\n");
}
@@ -1302,7 +1349,12 @@ dump_dfa_stats (file)
size = num_aliased_objects * sizeof (tree);
total += size;
- fprintf (file, fmt_str_1, "Aliased objects", num_aliased_objects,
+ fprintf (file, fmt_str_1, "Aliased variables", num_aliased_objects,
+ SCALE (size), LABEL (size));
+
+ size = num_call_clobbered_vars * sizeof (tree);
+ total += size;
+ fprintf (file, fmt_str_1, "Call-clobbered variables", num_call_clobbered_vars,
SCALE (size), LABEL (size));
size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
@@ -1485,14 +1537,6 @@ clobber_vars_r (tp, walk_subtrees, data)
/*---------------------------------------------------------------------------
Aliasing
---------------------------------------------------------------------------*/
-
-struct walk_state
-{
- htab_t vars_found;
- htab_t aliased_objects_found;
- int is_store;
-};
-
/* Compute may-alias information for every variable referenced in the
program. Note that in the absence of points-to analysis
(-ftree-points-to), this may compute a much bigger set than necessary. */
@@ -1513,7 +1557,6 @@ compute_may_aliases ()
should expose VLAs in the code. */
find_vla_decls (DECL_INITIAL (current_function_decl));
-
num_aliased_objects = 0;
VARRAY_TREE_INIT (aliased_objects, 20, "aliased_objects");
VARRAY_TREE_INIT (aliased_objects_base, 20, "aliased_objects_base");
@@ -1524,7 +1567,7 @@ compute_may_aliases ()
/* Hash table of all the unique aliased objects found. */
aliased_objects_found = htab_create (50, htab_hash_pointer, htab_eq_pointer,
- NULL);
+ NULL);
walk_state.vars_found = vars_found;
walk_state.aliased_objects_found = aliased_objects_found;
@@ -1555,9 +1598,9 @@ compute_may_aliases ()
}
num_aliased_objects = 0;
- aliased_objects = 0;
- aliased_objects_base = 0;
- aliased_objects_alias_set = 0;
+ aliased_objects = NULL;
+ aliased_objects_base = NULL;
+ aliased_objects_alias_set = NULL;
timevar_pop (TV_TREE_MAY_ALIAS);
}
@@ -1585,40 +1628,19 @@ static void
compute_alias_sets ()
{
size_t i;
- tree var, sym, deref_gv;
+ tree var, sym;
VARRAY_GENERIC_PTR_INIT (alias_sets, 20, "alias_sets");
/* For each object that is stored in the program, compute its alias set
and register it in ALIAS_SETS. If P's alias set does not conflict
with any entry in ALIAS_SETS, or if it conflicts with more than one
- entry, create a new entry for P.
-
- We need to treat GLOBAL_VAR separately. Since GLOBAL_VAR aliases
- variables that might have been otherwise unaliased, we register it
- first so that we make sure that if GLOBAL_VAR is needed for this
- function, it is always an alias tag. Otherwise we will miss the
- following case: Suppose that *P and Q are two variables that don't
- alias each other:
-
- foo (*P)
- {
- *P = ...;
- bar (&Q);
- }
-
- If *P is added to ALIAS_SETS first, then we will build an alias set
- tagged with *P which contains *P and GLOBAL_VAR. However, since Q
- does not conflict with *P, it will never be added to the set. */
- deref_gv = indirect_ref (global_var);
- if (deref_gv)
- register_alias_set (deref_gv, global_var);
-
+ entry, create a new entry for P. */
for (i = 0; i < num_aliased_objects; i++)
{
var = VARRAY_TREE (aliased_objects, i);
sym = VARRAY_TREE (aliased_objects_base, i);
- if (var_ann (var)->is_stored && var != deref_gv)
+ if (var_ann (var)->is_stored)
register_alias_set (var, sym);
}
@@ -1651,7 +1673,7 @@ compute_alias_sets ()
}
-/* Try to add DEREF as a new new alias tag in ALIAS_SETS. If a conflicting
+/* Try to add DEREF as a new alias tag in ALIAS_SETS. If a conflicting
tag is already present, then instead of adding a new entry, DEREF is
marked as an alias of the existing entry. DEREF_SYM is the base symbol
of DEREF. */
@@ -1841,9 +1863,9 @@ may_alias_p (v1, v1_base, v1_alias_set,
if (v1 == v2)
return true;
- /* One of the two variables needs to be an INDIRECT_REF or GLOBAL_VAR,
- otherwise they can't possibly alias each other. */
- if (TREE_CODE (v1) == INDIRECT_REF || v1 == global_var)
+ /* One of the two variables needs to be an INDIRECT_REF, otherwise they
+ can't possibly alias each other. */
+ if (TREE_CODE (v1) == INDIRECT_REF)
{
ptr = v1;
ptr_sym = v1_base;
@@ -1852,7 +1874,7 @@ may_alias_p (v1, v1_base, v1_alias_set,
var_sym = v2_base;
var_alias_set = v2_alias_set;
}
- else if (TREE_CODE (v2) == INDIRECT_REF || v2 == global_var)
+ else if (TREE_CODE (v2) == INDIRECT_REF)
{
ptr = v2;
ptr_sym = v2_base;
@@ -1864,38 +1886,10 @@ may_alias_p (v1, v1_base, v1_alias_set,
else
return false;
- /* GLOBAL_VAR aliases every global variable, pointer dereference and
- locals that have had their address taken, unless points-to analysis is
- done. This is because points-to is supposed to handle this case, and
- thus, can give a more accurate answer. */
- if (ptr_sym == global_var
- && (TREE_ADDRESSABLE (var_sym)
- || TREE_CODE (var) == INDIRECT_REF
- || decl_function_context (var_sym) == NULL))
- {
- if (flag_tree_points_to == PTA_NONE)
- return true;
- else
- {
- /* Right now, it's just not worth the time/space to make
- points-to handle the global variables seperately (in
- intraprocedural mode, anyway). */
- if (decl_function_context (var_sym) == NULL)
- return true;
-
- /* For GLOBAL_VAR, we want to see if the variable aliases
- GLOBAL_VAR, not if GLOBAL_VAR aliases the variable (since
- the points-to sets are possibly directional, and
- GLOBAL_VAR never gets assigned to, only assigned from). */
- if (ptr_may_alias_var (var_sym, ptr_sym))
- return true;
- }
- }
-
/* If the alias sets don't conflict then PTR cannot alias VAR. */
if (!alias_sets_conflict_p (ptr_alias_set, var_alias_set))
{
- /* Handle aliases to structure fields. If both VAR and PTR are
+ /* Handle aliases to structure fields. If either VAR or PTR are
aggregate types, they may not have conflicting types, but one of
the structures could contain a pointer to the other one.
@@ -1913,12 +1907,28 @@ may_alias_p (v1, v1_base, v1_alias_set,
or 'struct Q' aliases 'struct P *'. Notice, that since GIMPLE
does not have more than one-level pointers, we don't need to
recurse into the structures. */
- if (TREE_CODE (var) == INDIRECT_REF
- && AGGREGATE_TYPE_P (TREE_TYPE (ptr))
- && AGGREGATE_TYPE_P (TREE_TYPE (var))
- && (alias_sets_conflict_p (ptr_alias_set, get_alias_set (var_sym))
- || alias_sets_conflict_p (var_alias_set, get_alias_set (ptr_sym))))
- return true;
+ if (AGGREGATE_TYPE_P (TREE_TYPE (ptr))
+ || AGGREGATE_TYPE_P (TREE_TYPE (var)))
+ {
+ tree ptr_to_var;
+
+ /* If VAR is not an INDIRECT_REF, we use the canonical pointer-to
+ VAR's type. */
+ if (TREE_CODE (var) == INDIRECT_REF)
+ ptr_to_var = var_sym;
+ else
+ {
+ ptr_to_var = TYPE_POINTER_TO (TREE_TYPE (var));
+ /* If no pointer-to VAR exists, then PTR can't possibly alias
+ VAR. */
+ if (ptr_to_var == NULL_TREE)
+ return false;
+ }
+
+ return
+ alias_sets_conflict_p (ptr_alias_set, get_alias_set (ptr_to_var))
+ || alias_sets_conflict_p (var_alias_set, get_alias_set (ptr_sym));
+ }
else
return false;
}
@@ -1980,7 +1990,7 @@ void
dump_alias_info (file)
FILE *file;
{
- unsigned long i, j;
+ size_t i, j, k;
if (alias_sets == NULL)
return;
@@ -1994,7 +2004,7 @@ dump_alias_info (file)
as = (struct alias_set_d *) VARRAY_GENERIC_PTR (alias_sets, i);
- fprintf (file, "Alias set #%ld:\n", i);
+ fprintf (file, "Alias set #%u:\n", (unsigned) i);
fprintf (file, " Tag: ");
dump_variable (file, as->tag);
fprintf (file, " Aliases objects: { ");
@@ -2003,11 +2013,12 @@ dump_alias_info (file)
{
tree var = VARRAY_TREE (aliased_objects, j);
varray_type aliases = may_aliases (var);
- if (aliases && VARRAY_TREE (aliases, 0) == as->tag)
- {
- print_generic_expr (file, var, 0);
- fprintf (file, " ");
- }
+ for (k = 0; aliases && k < VARRAY_ACTIVE_SIZE (aliases); k++)
+ if (VARRAY_TREE (aliases, k) == as->tag)
+ {
+ print_generic_expr (file, var, 0);
+ fprintf (file, " ");
+ }
}
fprintf (file, "}\n\n");
}
@@ -2200,47 +2211,43 @@ find_vars_r (tp, walk_subtrees, data)
set_indirect_ref (sym, var);
}
- add_referenced_var (var, sym, data);
+ add_referenced_var (var, sym, walk_state);
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
- exception to this rule are functions marked pure, const or if they are
- known to not return.
-
- Stores to *GLOBAL_VAR will reach uses of every call clobbered variable
- in the function. Uses of *GLOBAL_VAR will be reached by definitions
- of call clobbered variables.
-
- This is used to model the effects that the called function may have on
- local and global variables that might be visible to it. */
+ /* A function call that receives pointer arguments may dereference them.
+ For every pointer 'p' add '*p' to the list of referenced variables.
+ See the handler for CALL_EXPR nodes in get_expr_operands for details. */
if (TREE_CODE (*tp) == CALL_EXPR)
{
- if (call_may_clobber (*tp))
+ tree op;
+ bool may_clobber = call_may_clobber (*tp);
+
+ if (may_clobber)
+ walk_state->is_store = 1;
+
+ for (op = TREE_OPERAND (*tp, 1); op; op = TREE_CHAIN (op))
{
- walk_state->is_store = 1;
- add_indirect_ref_var (global_var, data);
+ tree arg = TREE_VALUE (op);
+ if (SSA_DECL_P (arg)
+ && POINTER_TYPE_P (TREE_TYPE (arg)))
+ add_indirect_ref_var (arg, walk_state);
}
- else
- {
- tree op;
- walk_state->is_store = 0;
- /* If the function does not clobber locals, it still may
- dereference them. Scan its operands to see if it receives any
- pointers. For every pointer 'p' add '*p' to the list of
- referenced variables. */
- for (op = TREE_OPERAND (*tp, 1); op; op = TREE_CHAIN (op))
- {
- tree arg = TREE_VALUE (op);
- if (SSA_DECL_P (arg) && POINTER_TYPE_P (TREE_TYPE (arg)))
- add_indirect_ref_var (arg, data);
- }
+ /* If the function may clobber globals and addressable locals, add a
+ VDEF reference to GLOBAL_VAR. This definition will be reached by
+ other VDEFs to GLOBAL_VAR made by statements that modify
+ call-clobbered variables. This will prevent passes like DCE to
+ consider those assignments dead. */
+ if (may_clobber)
+ {
+ if (global_var == NULL_TREE)
+ create_global_var ();
+ add_referenced_var (global_var, global_var, walk_state);
}
+
walk_state->is_store = saved_is_store;
}
@@ -2253,29 +2260,35 @@ find_vars_r (tp, walk_subtrees, data)
same tree.
Also add VAR to the ALIASED_OBJECTS set of varrays that are needed for
- alias analysis. DATA is an array with two hash tables used to avoid
- adding the same variable more than once to its corresponding set as
- well as a bit indicating if we're processing a load or store. Note
- that this function assumes that VAR is a valid SSA variable. */
+ alias analysis.
+
+ WALK_STATE is an array with two hash tables used to avoid adding the
+ same variable more than once to its corresponding set as well as a bit
+ indicating if we're processing a load or store. Note that this function
+ assumes that VAR is a valid SSA variable. */
static void
-add_referenced_var (var, sym, data)
+add_referenced_var (var, sym, walk_state)
tree var;
tree sym;
- void *data;
+ struct walk_state *walk_state;
{
void **slot;
- struct walk_state *walk_state = (struct walk_state *)data;
htab_t vars_found = walk_state->vars_found;
htab_t aliased_objects_found = walk_state->aliased_objects_found;
int is_store = walk_state->is_store;
- /* First handle aliasing information. */
+ /* First handle aliasing information. INDIRECT_REF, global and
+ addressable local variables are all potentially aliased and call
+ clobbered. */
if (TREE_CODE (var) == INDIRECT_REF
|| TREE_ADDRESSABLE (sym)
|| decl_function_context (sym) == NULL)
{
- var_ann_t ann;
+ var_ann_t ann = var_ann (var);
+ if (! ann)
+ ann = create_var_ann (var);
+
slot = htab_find_slot (aliased_objects_found, (void *) var, INSERT);
if (*slot == NULL)
{
@@ -2285,12 +2298,18 @@ add_referenced_var (var, sym, data)
VARRAY_PUSH_TREE (aliased_objects_base, sym);
VARRAY_PUSH_INT (aliased_objects_alias_set, get_alias_set (var));
num_aliased_objects++;
+
+ /* If the variable is not read-only, it may also be clobbered by
+ function calls. */
+ if (!TREE_READONLY (var))
+ {
+ VARRAY_PUSH_TREE (call_clobbered_vars, var);
+ num_call_clobbered_vars++;
+ ann->is_call_clobbered = 1;
+ }
}
/* Note if this object was loaded or stored. */
- ann = var_ann (var);
- if (! ann)
- ann = create_var_ann (var);
if (is_store)
ann->is_stored = 1;
else
@@ -2335,14 +2354,14 @@ add_referenced_var (var, sym, data)
/* Add a reference to the INDIRECT_REF node of variable VAR. If VAR has
- not been dereferenced yet, create a new INDIRECT_REF node for it. DATA
- is as in add_referenced_var. Note that VAR is assumed to be a valid
- pointer decl. */
+ not been dereferenced yet, create a new INDIRECT_REF node for it.
+ WALK_STATE is as in add_referenced_var. Note that VAR is assumed to be
+ a valid pointer decl. */
static void
-add_indirect_ref_var (ptr, data)
+add_indirect_ref_var (ptr, walk_state)
tree ptr;
- void *data;
+ struct walk_state *walk_state;
{
tree deref = indirect_ref (ptr);
if (deref == NULL_TREE)
@@ -2351,7 +2370,7 @@ add_indirect_ref_var (ptr, data)
set_indirect_ref (ptr, deref);
}
- add_referenced_var (deref, ptr, data);
+ add_referenced_var (deref, ptr, walk_state);
}
@@ -2457,4 +2476,30 @@ find_vla_decls_r (tp, walk_subtrees, dat
set_vla_decl (*tp);
return NULL_TREE;
+}
+
+
+/* Create GLOBAL_VAR, an artificial global variable to act as a
+ representative of all the variables that may be clobbered by function
+ calls. Also create GLOBAL_CLOBBER_EXPR, an artificial expression that
+ is used as the originating definition of all clobbered SSA variables in
+ the program. */
+
+static void
+create_global_var ()
+{
+ global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"),
+ ptr_type_node);
+ DECL_ARTIFICIAL (global_var) = 1;
+ TREE_READONLY (global_var) = 0;
+ DECL_EXTERNAL (global_var) = 0;
+ TREE_STATIC (global_var) = 1;
+ TREE_USED (global_var) = 1;
+ DECL_CONTEXT (global_var) = current_function_decl;
+ TREE_THIS_VOLATILE (global_var) = 1;
+ TREE_ADDRESSABLE (global_var) = 0;
+
+ /* Create GLOBAL_CLOBBER_EXPR (.GLOBAL_VAR = NULL). */
+ global_clobber_expr = build (MODIFY_EXPR, ptr_type_node, global_var,
+ null_pointer_node);
}
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.63
diff -d -u -p -r1.1.4.63 tree-flow.h
--- tree-flow.h 18 Mar 2003 14:52:25 -0000 1.1.4.63
+++ tree-flow.h 20 Mar 2003 18:32:37 -0000
@@ -68,16 +68,19 @@ struct var_ann_d GTY(())
Note this only applies to objects which are subject to
alias analysis. */
- unsigned int is_stored: 1;
+ unsigned is_stored : 1;
/* Nonzero if this variable was loaded/read in this function.
Note this only applies to objects which are subject to
alias analysis. */
- unsigned int is_loaded: 1;
+ unsigned is_loaded : 1;
+
+ /* Nonzero if the variable may be modified by function calls. */
+ unsigned is_call_clobbered : 1;
/* Unused bits. */
- unsigned int unused: 27;
+ unsigned unused : 26;
/* An INDIRECT_REF expression representing all the dereferences of this
pointer. Used to store aliasing information for pointer dereferences
@@ -88,7 +91,7 @@ struct var_ann_d GTY(())
varray_type may_aliases;
/* Unique ID of this variable. */
- int uid;
+ size_t uid;
};
@@ -106,10 +109,10 @@ typedef struct operands_d *operands_t;
struct voperands_d GTY(())
{
- /* List of V_DEF references in this statement. */
+ /* List of VDEF references in this statement. */
varray_type vdef_ops;
- /* List of V_USE references in this statement. */
+ /* List of VUSE references in this statement. */
varray_type GTY ((skip (""))) vuse_ops;
};
@@ -175,6 +178,10 @@ struct stmt_ann_d GTY(())
/* Nonzero if the statement makes references to volatile storage. */
unsigned has_volatile_ops : 1;
+ /* Nonzero if the statement makes a function call that may clobber global
+ and local addressable variables. */
+ unsigned makes_clobbering_call : 1;
+
/* Basic block that contains this statement. */
basic_block GTY ((skip (""))) bb;
@@ -325,14 +332,15 @@ extern int tree_warn_uninitialized;
/* Array of all variables referenced in the function. */
extern GTY(()) varray_type referenced_vars;
-/* Next unique reference ID to be assigned by create_ref(). */
-extern unsigned long next_tree_ref_id;
-
/* Artificial variable used to model the effects of function calls. */
extern GTY(()) tree global_var;
+/* Artificial expression serving as the definition statement for every call
+ clobbered variable in the function. */
+extern GTY(()) tree global_clobber_expr;
+
/* Accessors for the referenced_vars array. */
-extern unsigned long num_referenced_vars;
+extern size_t num_referenced_vars;
static inline tree referenced_var PARAMS ((size_t));
static inline tree
@@ -340,6 +348,20 @@ referenced_var (i)
size_t i;
{
return VARRAY_TREE (referenced_vars, i);
+}
+
+/* Array of all variables that are call clobbered in the function. */
+extern GTY(()) varray_type call_clobbered_vars;
+
+/* The total number of unique call clobbered variables in the function. */
+extern size_t num_call_clobbered_vars;
+
+static inline tree call_clobbered_var PARAMS ((size_t));
+static inline tree
+call_clobbered_var (i)
+ size_t i;
+{
+ return VARRAY_TREE (call_clobbered_vars, i);
}
/* Macros for showing usage statistics. */
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.63
diff -d -u -p -r1.1.2.63 tree-ssa-ccp.c
--- tree-ssa-ccp.c 6 Mar 2003 20:52:54 -0000 1.1.2.63
+++ tree-ssa-ccp.c 20 Mar 2003 18:32:38 -0000
@@ -121,7 +121,6 @@ static latticevalue likely_value PARAMS
static void fold_stmt PARAMS ((tree));
static tree get_rhs PARAMS ((tree));
static void set_rhs PARAMS ((tree, tree));
-static void set_value PARAMS ((tree, latticevalue, tree));
static value *get_value PARAMS ((tree));
static value get_default_value PARAMS ((tree));
static hashval_t value_map_hash PARAMS ((const void *));
@@ -344,7 +343,10 @@ visit_phi_node (phi)
phi_val.lattice_val = UNDEFINED;
phi_val.const_val = NULL_TREE;
- if (!TREE_THIS_VOLATILE (SSA_NAME_VAR (PHI_RESULT (phi))))
+ /* If the variable is volatile, consider it VARYING. */
+ if (TREE_THIS_VOLATILE (SSA_NAME_VAR (PHI_RESULT (phi))))
+ phi_val.lattice_val = VARYING;
+ else
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
/* Compute the meet operator over all the PHI arguments. */
@@ -362,27 +364,15 @@ visit_phi_node (phi)
if (e->flags & EDGE_EXECUTABLE)
{
tree rdef = PHI_ARG_DEF (phi, i);
+ value *rdef_val = get_value (rdef);
+ phi_val = cp_lattice_meet (phi_val, *rdef_val);
- if (!TREE_THIS_VOLATILE (SSA_NAME_VAR (rdef)))
- {
- value *rdef_val = get_value (rdef);
- phi_val = cp_lattice_meet (phi_val, *rdef_val);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\t");
- print_generic_expr (dump_file, rdef, 0);
- dump_lattice_value (dump_file, "\tValue: ", *rdef_val);
- fprintf (dump_file, "\n");
- }
- }
- else
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- /* If the variable is volatile, we cannot assume anything
- about this PHI's node value. In that case, set its
- value to VARYING. */
- phi_val.lattice_val = VARYING;
- phi_val.const_val = NULL_TREE;
+ fprintf (dump_file, "\t");
+ print_generic_expr (dump_file, rdef, 0);
+ dump_lattice_value (dump_file, "\tValue: ", *rdef_val);
+ fprintf (dump_file, "\n");
}
if (phi_val.lattice_val == VARYING)
@@ -502,7 +492,7 @@ visit_stmt (stmt)
/* Mark all VDEF operands VARYING. */
ops = vdef_ops (stmt);
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
- set_value (VDEF_RESULT (VARRAY_TREE (ops, i)), VARYING, NULL_TREE);
+ def_to_varying (VDEF_RESULT (VARRAY_TREE (ops, i)));
}
@@ -514,19 +504,26 @@ visit_assignment (stmt)
tree stmt;
{
value val;
+ tree lhs, rhs;
#if defined ENABLE_CHECKING
if (!def_op (stmt))
abort ();
#endif
- if (TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
- && TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
+ lhs = TREE_OPERAND (stmt, 0);
+ rhs = TREE_OPERAND (stmt, 1);
+
+ if (TREE_THIS_VOLATILE (SSA_NAME_VAR (lhs)))
{
- /* For a simple copy operation, we copy the lattice
- values. */
- value *nval = get_value (TREE_OPERAND (stmt, 1));
-
+ /* Volatile variables are always VARYING. */
+ val.lattice_val = VARYING;
+ val.const_val = NULL_TREE;
+ }
+ else if (TREE_CODE (rhs) == SSA_NAME)
+ {
+ /* For a simple copy operation, we copy the lattice values. */
+ value *nval = get_value (rhs);
val.lattice_val = nval->lattice_val;
val.const_val = nval->const_val;
}
@@ -1024,7 +1021,6 @@ def_to_undefined (var)
value->lattice_val = UNDEFINED;
value->const_val = NULL_TREE;
}
-
}
@@ -1045,7 +1041,6 @@ def_to_varying (var)
value->lattice_val = VARYING;
value->const_val = NULL_TREE;
}
-
}
@@ -1150,9 +1145,16 @@ likely_value (stmt)
varray_type uses;
size_t i;
int found_constant = 0;
+ stmt_ann_t ann;
get_stmt_operands (stmt);
+ /* If the statement makes aliased loads or has volatile operands, it
+ won't fold to a constant value. */
+ ann = stmt_ann (stmt);
+ if (ann->makes_aliased_loads || ann->has_volatile_ops)
+ return VARYING;
+
uses = use_ops (stmt);
for (i = 0; uses && i < VARRAY_ACTIVE_SIZE (uses); i++)
{
@@ -1166,7 +1168,7 @@ likely_value (stmt)
found_constant = 1;
}
- return (found_constant || (!uses && !vuse_ops (stmt)) ? CONSTANT : VARYING);
+ return ((found_constant || !uses) ? CONSTANT : VARYING);
}
@@ -1277,7 +1279,10 @@ get_value (var)
2- Function arguments are considered VARYING.
- 3- Any other value is considered UNDEFINED. This is useful when
+ 3- SSA names created by a function call (i.e., call clobbered
+ variables) are considered VARYING.
+
+ 4- Any other value is considered UNDEFINED. This is useful when
considering PHI nodes. PHI arguments that are undefined do not
change the constant value of the PHI node, which allows for more
constants to be propagated. */
@@ -1287,66 +1292,54 @@ get_default_value (var)
tree var;
{
value val;
+ tree sym;
- if (!DECL_P (var))
- var = get_base_symbol (var);
+ sym = (!DECL_P (var)) ? get_base_symbol (var) : var;
val.lattice_val = UNDEFINED;
val.const_val = NULL_TREE;
- if (TREE_CODE (var) == PARM_DECL)
+ if (TREE_CODE (sym) == PARM_DECL || TREE_THIS_VOLATILE (sym))
{
- /* Function arguments are considered VARYING. */
+ /* Function arguments and volatile variables are considered VARYING. */
val.lattice_val = VARYING;
}
- else if (decl_function_context (var) == NULL_TREE || TREE_STATIC (var))
+ else if (decl_function_context (sym) == NULL_TREE || TREE_STATIC (sym))
{
- /* Globals and static variables are considered VARYING. */
+ /* Globals and static variables are considered VARYING, unless they
+ are declared 'const'. */
val.lattice_val = VARYING;
- /* Except if they are declared 'const'. */
- if (TREE_READONLY (var)
- && DECL_INITIAL (var)
- && really_constant_p (DECL_INITIAL (var)))
+ if (TREE_READONLY (sym)
+ && DECL_INITIAL (sym)
+ && really_constant_p (DECL_INITIAL (sym)))
{
val.lattice_val = CONSTANT;
- val.const_val = DECL_INITIAL (var);
+ val.const_val = DECL_INITIAL (sym);
}
}
-
- return val;
-}
-
-
-/* Set the value for variable VAR to <LATTICE_VAL, CONST_VAL>. */
-
-static void
-set_value (var, lattice_val, const_val)
- tree var;
- latticevalue lattice_val;
- tree const_val;
-{
- void **slot;
- struct value_map_d *vm_p, vm;
-
-#if defined ENABLE_CHECKING
- if (TREE_CODE (var) != SSA_NAME)
- abort ();
-#endif
-
- vm.var = var;
- slot = htab_find_slot (const_values, (void *) &vm, INSERT);
- if (*slot == NULL)
+ else if (SSA_NAME_DEF_STMT (var) == global_clobber_expr)
{
- vm_p = xmalloc (sizeof (*vm_p));
- vm_p->var = var;
- *slot = (void *) vm_p;
+ /* If VAR is call clobbered and defined by a clobbering function
+ call, consider it VARYING.
+
+ NOTE: With this we are modifying the usual behaviour of the
+ propagator. We typically register new values as we find them in
+ visit_assignment. We could have used the same model for function
+ calls (i.e., when we visit a function call, register a new
+ definition for all call clobbered variables).
+
+ However, function calls don't introduce VDEFs for all the
+ variables they clobber because that proved to be a significant
+ compile-time problem (CCP went from a couple of seconds to 45
+ seconds while compiling expr.c). There were too many of these
+ VDEFs that essentially state nothing more than "this variable
+ changed in unexpected ways". We get the same information by just
+ noting that they originate at a CALL_EXPR. */
+ val.lattice_val = VARYING;
}
- else
- vm_p = (struct value_map_d *) *slot;
- vm_p->val.lattice_val = lattice_val;
- vm_p->val.const_val = const_val;
+ return val;
}
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dce.c,v
retrieving revision 1.1.2.30
diff -d -u -p -r1.1.2.30 tree-ssa-dce.c
--- tree-ssa-dce.c 10 Mar 2003 17:38:31 -0000 1.1.2.30
+++ tree-ssa-dce.c 20 Mar 2003 18:32:38 -0000
@@ -117,6 +117,7 @@ mark_tree_necessary (t)
if (t == NULL
|| t == empty_stmt_node
|| t == error_mark_node
+ || t == global_clobber_expr
|| necessary_p (t))
return 0;
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.57
diff -d -u -p -r1.1.4.57 tree-ssa.c
--- tree-ssa.c 11 Mar 2003 16:34:53 -0000 1.1.4.57
+++ tree-ssa.c 20 Mar 2003 18:32:38 -0000
@@ -143,13 +143,13 @@ static void rewrite_block PARAMS ((basi
static void rewrite_stmt PARAMS ((block_stmt_iterator,
varray_type *,
varray_type *));
-static inline void rewrite_operand PARAMS ((tree *));
+static void rewrite_operand PARAMS ((tree *, varray_type *));
static void register_new_def PARAMS ((tree, tree, varray_type *));
static void update_indirect_ref_vuses PARAMS ((tree, tree, varray_type));
static void update_pointer_vuses PARAMS ((tree, tree, varray_type));
static void insert_phi_nodes_for PARAMS ((tree, bitmap *));
static tree remove_annotations_r PARAMS ((tree *, int *, void *));
-static tree currdef_for PARAMS ((tree, int));
+static tree get_reaching_def PARAMS ((tree));
static tree get_value_for PARAMS ((tree, htab_t));
static void set_value_for PARAMS ((tree, tree, htab_t));
static hashval_t def_blocks_hash PARAMS ((const void *));
@@ -424,7 +424,7 @@ mark_def_sites (idom, globals)
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
{
tree *use = VARRAY_GENERIC_PTR (ops, i);
- int uid = var_ann (*use)->uid;
+ size_t uid = var_ann (*use)->uid;
if (! TEST_BIT (kills, uid))
{
@@ -438,7 +438,7 @@ mark_def_sites (idom, globals)
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
{
tree use = VARRAY_TREE (ops, i);
- int uid = var_ann (use)->uid;
+ size_t uid = var_ann (use)->uid;
if (! TEST_BIT (kills, uid))
{
@@ -457,7 +457,7 @@ mark_def_sites (idom, globals)
{
tree vdef = VARRAY_TREE (ops, i);
tree vdef_op = VDEF_OP (vdef);
- int uid = var_ann (vdef_op)->uid;
+ size_t uid = var_ann (vdef_op)->uid;
set_def_block (VDEF_RESULT (vdef), bb);
if (!TEST_BIT (kills, uid))
@@ -465,7 +465,6 @@ mark_def_sites (idom, globals)
SET_BIT (globals, uid);
set_livein_block (vdef_op, bb);
}
-
}
/* Now process the definition made by this statement. */
@@ -475,7 +474,6 @@ mark_def_sites (idom, globals)
set_def_block (*dest, bb);
SET_BIT (kills, var_ann (*dest)->uid);
}
-
}
}
@@ -663,10 +661,27 @@ rewrite_block (bb)
for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
{
+ stmt_ann_t ann = NULL;
+
/* FIXME. [UNSSA] After fixing the SSA->normal pass, allow
constants and copies to be propagated into PHI arguments. */
- tree currdef = currdef_for (SSA_NAME_VAR (PHI_RESULT (phi)), true);
+ tree currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
add_phi_arg (phi, currdef, e);
+
+ /* If CURRDEF for the argument is GLOBAL_VAR and it comes from a
+ call to a clobbering function, propagate the attribute
+ into the PHI node. This is used by rewrite_operand to
+ determine if the use of a call clobbered variable should be
+ reached by GLOBAL_VAR. */
+ if (SSA_NAME_VAR (currdef) == global_var
+ && ((ann = stmt_ann (SSA_NAME_DEF_STMT (currdef))) != NULL)
+ && ann->makes_clobbering_call)
+ {
+ ann = stmt_ann (phi);
+ if (ann == NULL)
+ ann = create_stmt_ann (phi);
+ ann->makes_clobbering_call = 1;
+ }
}
}
@@ -1102,7 +1117,7 @@ rewrite_stmt (si, block_defs_p, block_av
{
tree val;
tree *op_p = (tree *) VARRAY_GENERIC_PTR (uses, i);
- rewrite_operand (op_p);
+ rewrite_operand (op_p, block_defs_p);
/* If the operand has a known constant value or it is known to be a
copy of some other variable, use the value or copy stored in
@@ -1166,7 +1181,7 @@ rewrite_stmt (si, block_defs_p, block_av
/* Rewrite virtual uses in the statement. */
for (i = 0; vuses && i < VARRAY_ACTIVE_SIZE (vuses); i++)
- rewrite_operand (&(VARRAY_TREE (vuses, i)));
+ rewrite_operand (&(VARRAY_TREE (vuses, i)), block_defs_p);
/* If the statement has been modified with constant replacements,
fold its RHS before checking for redundant computations. */
@@ -1262,7 +1277,7 @@ rewrite_stmt (si, block_defs_p, block_av
for (i = 0; vdefs && i < VARRAY_ACTIVE_SIZE (vdefs); i++)
{
tree vdef = VARRAY_TREE (vdefs, i);
- rewrite_operand (&(VDEF_OP (vdef)));
+ rewrite_operand (&(VDEF_OP (vdef)), block_defs_p);
VDEF_RESULT (vdef) = make_ssa_name (VDEF_RESULT (vdef), stmt);
register_new_def (SSA_NAME_VAR (VDEF_RESULT (vdef)),
VDEF_RESULT (vdef), block_defs_p);
@@ -1271,11 +1286,12 @@ rewrite_stmt (si, block_defs_p, block_av
/* Replace the operand pointed by OP_P with its immediate reaching
- definition. */
+ definition. BLOCK_DEFS_P is as in rewrite_stmt. */
-static inline void
-rewrite_operand (op_p)
+static void
+rewrite_operand (op_p, block_defs_p)
tree *op_p;
+ varray_type *block_defs_p;
{
tree op, currdef;
@@ -1302,13 +1318,45 @@ rewrite_operand (op_p)
op = *op_p;
if (TREE_CODE (op) == INDIRECT_REF)
{
- tree base = currdef_for (TREE_OPERAND (op, 0), false);
- if (base && SSA_NAME_VAR (base) != TREE_OPERAND (op, 0))
+ tree base = get_value_for (TREE_OPERAND (op, 0), currdefs);
+ if (base
+ && SSA_NAME_VAR (base) != global_var
+ && SSA_NAME_VAR (base) != TREE_OPERAND (op, 0))
op = indirect_ref (base);
}
- currdef = currdef_for (op, true);
- *op_p = currdef;
+ currdef = get_reaching_def (op);
+
+ /* If the operand is reached by a definition of GLOBAL_VAR coming from a
+ call to a clobbering function, it means that the operand may have been
+ modified by the call. In this case, we create a new name for the
+ operand and set its originating definition to GLOBAL_CLOBBER_EXPR,
+ which indicates that nothing is known about the definition.
+
+ 1 X_3 = ...
+
+ # GLOBAL_VAR_5 = VDEF <GLOBAL_VAR_4>
+ 2 foo()
+ 3 = X_6
+
+ In the code fragment above, the use of X at line 3 is reached by the
+ call to foo(). So, we create the new version X_6 and rewrite line 3
+ to use X_6. */
+ if (SSA_NAME_VAR (currdef) != op)
+ {
+ tree new_op_name;
+
+ /* Create a new SSA name for OP, register it and rename the operand
+ with its new name. */
+ new_op_name = make_ssa_name (op, global_clobber_expr);
+ register_new_def (op, new_op_name, block_defs_p);
+ *op_p = new_op_name;
+ }
+ else
+ {
+ /* Rewrite the operand with its reaching definition. */
+ *op_p = currdef;
+ }
}
@@ -1321,7 +1369,7 @@ register_new_def (var, def, block_defs_p
tree def;
varray_type *block_defs_p;
{
- tree currdef = currdef_for (var, false);
+ tree currdef = get_value_for (var, currdefs);
/* If the current reaching definition is NULL or a constant, push the
variable itself so that rewrite_blocks knows what variable is
@@ -1412,20 +1460,11 @@ init_tree_ssa ()
next_ssa_version = 1;
num_referenced_vars = 0;
VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
+ num_call_clobbered_vars = 0;
+ VARRAY_TREE_INIT (call_clobbered_vars, 20, "call_clobbered_vars");
memset ((void *) &ssa_stats, 0, sizeof (ssa_stats));
-
- /* Declare an artificial global variable to act as a representative of
- all the variables that may be clobbered by function calls. */
- global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"),
- ptr_type_node);
- DECL_ARTIFICIAL (global_var) = 1;
- TREE_READONLY (global_var) = 0;
- DECL_EXTERNAL (global_var) = 0;
- TREE_STATIC (global_var) = 0;
- TREE_USED (global_var) = 1;
- DECL_CONTEXT (global_var) = NULL_TREE;
- TREE_THIS_VOLATILE (global_var) = 1;
- TREE_ADDRESSABLE (global_var) = 1;
+ global_var = NULL_TREE;
+ global_clobber_expr = NULL_TREE;
/* Allocate memory for the DEF_BLOCKS hash table. */
def_blocks = htab_create (num_referenced_vars, def_blocks_hash,
@@ -1449,7 +1488,7 @@ static void
delete_tree_ssa (fndecl)
tree fndecl;
{
- unsigned long int i;
+ size_t i;
/* Remove annotations from every tree in the function. */
walk_tree (&DECL_SAVED_TREE (fndecl), remove_annotations_r, NULL, NULL);
@@ -1461,6 +1500,9 @@ delete_tree_ssa (fndecl)
num_referenced_vars = 0;
referenced_vars = NULL;
global_var = NULL_TREE;
+ global_clobber_expr = NULL_TREE;
+ num_call_clobbered_vars = 0;
+ call_clobbered_vars = NULL;
}
@@ -1500,23 +1542,129 @@ remove_annotations_r (tp, walk_subtrees,
return NULL_TREE;
}
-/* Return the current definition for variable V. If none is found and
- CREATE_DEFAULT is nonzero, create a new SSA name to act as the zeroth
- definition for V. */
+/* 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
-currdef_for (v, create_default)
- tree v;
- int create_default;
+get_reaching_def (var)
+ tree var;
{
- tree def = get_value_for (v, currdefs);
- if (def == NULL_TREE && create_default)
+ tree default_def, currdef_var;
+
+ /* Lookup the current reaching definition for VAR. */
+ default_def = NULL_TREE;
+ currdef_var = get_value_for (var, currdefs);
+
+ /* If there is no reaching definition for VAR, create and register a
+ default definition for it. */
+ if (currdef_var == NULL_TREE)
{
- def = make_ssa_name (v, empty_stmt_node);
- set_value_for (v, def, currdefs);
+ default_def = make_ssa_name (var, empty_stmt_node);
+ set_value_for (var, default_def, currdefs);
}
- return def;
+ /* If VAR is is call clobbered, we need to determine whether its current
+ reaching definition is killed by a more recent definition of
+ GLOBAL_VAR. For instance, consider this partially renamed fragment:
+
+ 1 X_3 = ...
+ # GLOBAL_VAR_4 = VDEF <GLOBAL_VAR_2>
+ 2 foo ()
+ 3 = X
+
+ Suppose that variable X is call-clobbered. When renaming X at line 3,
+ we need to realize that X_3 is killed by the call to foo() at line 2.
+ That is, the use of X at line 3 should be reached by the call to
+ foo().
+
+ Note that GLOBAL_VAR is modified by statements that make calls to
+ clobbering functions and by assignments to call-clobbered variables.
+ Here, we are only interested in definitions of GLOBAL_VAR coming from
+ function calls.
+
+ To determine if a definition of GLOBAL_VAR may kill the reaching
+ definition for VAR, we take advantage of these properties of the SSA
+ renaming process:
+
+ 1- Since we are doing a depth-first walk over the dominator tree of
+ the flowgraph, the current reaching definition for GLOBAL_VAR and
+ VAR are guaranteed to reach this point.
+
+ 2- To determine whether the current definition for GLOBAL_VAR kills
+ the current definition for OP, we only need to look at their SSA
+ version numbers. Whichever definition has the higher number is the
+ one that kills the other (simply because of the order in which we do
+ the renaming). This is why it's important to use a global SSA
+ version number for all the variables in the program.
+
+ 3- The test done in #2 is NOT valid if both definitions are PHI nodes
+ in the same basic block. Conceptually, PHI nodes are all executed
+ in parallel, so it is wrong to base the decision on the SSA
+ versions. If this happens, we use the PHI node for VAR because if
+ any of the operands of the PHI is clobbered by a call, it will
+ already have been renamed to GLOBAL_VAR. For instance,
+
+ if (...)
+ {
+ X_2 = ...
+ # GLOBAL_VAR_3 = VDEF <GLOBAL_VAR_1>
+ foo ();
+ }
+ else
+ {
+ X_3 = ...;
+ }
+ X_4 = PHI <GLOBAL_VAR_3, X_3>
+ GLOBAL_VAR_5 = PHI <GLOBAL_VAR_3, GLOBAL_VAR_1>
+
+ Notice how the first argument of X_4's PHI node is GLOBAL_VAR_3
+ because on the THEN clause of this conditional, there is a call
+ to a clobbering function after the assignment to X_2. However, the
+ second operand to X_4's PHI node is X_3 because there are no
+ clobbering calls on the ELSE clause. */
+ if (global_var && var_ann (var)->is_call_clobbered)
+ {
+ tree currdef_gv = get_value_for (global_var, currdefs);
+
+ /* GLOBAL_VAR cannot affect VAR if (1) it hasn't been defined yet, or
+ (2) if its reaching definition comes from empty_stmt_node (i.e.,
+ if it's just a default definition), or (3) if its defining
+ statement is not a call to a clobbering function. */
+ if (currdef_gv
+ && SSA_NAME_DEF_STMT (currdef_gv) != empty_stmt_node
+ && stmt_ann (SSA_NAME_DEF_STMT (currdef_gv))->makes_clobbering_call)
+ {
+ /* If VAR didn't have a reaching definition, return the current
+ definition for GLOBAL_VAR. */
+ if (currdef_var == NULL_TREE)
+ return currdef_gv;
+
+ /* If GLOBAL_VAR has a more recent definition than VAR, then
+ return it unless both definitions are PHI nodes in the same
+ basic block (see the example above). */
+ if (SSA_NAME_VERSION (currdef_gv) > SSA_NAME_VERSION (currdef_var))
+ {
+ tree gv_def_stmt = SSA_NAME_DEF_STMT (currdef_gv);
+ tree var_def_stmt = SSA_NAME_DEF_STMT (currdef_var);
+
+ /* If both definitions come from PHI nodes in the same basic
+ block, return VAR's reaching definition. */
+ if (TREE_CODE (gv_def_stmt) == PHI_NODE
+ && TREE_CODE (var_def_stmt) == PHI_NODE
+ && bb_for_stmt (gv_def_stmt) == bb_for_stmt (var_def_stmt))
+ return currdef_var;
+ else
+ return currdef_gv;
+ }
+ }
+ }
+
+ /* Otherwise, return the current reaching definition for VAR, or the
+ default definition, if we had to create one. */
+ return (currdef_var) ? currdef_var : default_def;
}
@@ -1786,12 +1934,31 @@ var_is_live (var, bb)
struct def_blocks_d *def_map;
tree real_var = SSA_NAME_VAR (var);
- if (currdef_for (real_var, false) != var)
+ if (get_value_for (real_var, currdefs) != var)
{
ssa_stats.blocked_by_life_crossing++;
return false;
}
+ /* If VAR is call clobbered, check that there isn't another definition
+ for GLOBAL_VAR between the block that defines VAR and BB. */
+ def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
+ if (def_bb == NULL)
+ def_bb = ENTRY_BLOCK_PTR;
+
+ if (global_var && var_ann (var)->is_call_clobbered)
+ {
+ tree currdef_gv = get_value_for (global_var, currdefs);
+ if (currdef_gv
+ && SSA_NAME_DEF_STMT (currdef_gv) != empty_stmt_node
+ && stmt_ann (SSA_NAME_DEF_STMT (currdef_gv))->makes_clobbering_call)
+ {
+ basic_block x = bb_for_stmt (SSA_NAME_DEF_STMT (currdef_gv));
+ if (def_bb->index <= x->index && x->index <= bb->index)
+ return false;
+ }
+ }
+
/* This is gross, but since it's temporary, close your eyes. It's needed
to avoid miscompiling java/jcf-write.c:generate_classfile, where the
fully pruned SSA form is not inserting PHI nodes in the main loop of
@@ -1802,12 +1969,11 @@ var_is_live (var, bb)
VAR is defined again, then two versions of VAR are live at the same
time. */
def_map = get_def_blocks_for (real_var);
- def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
if (def_bb && bitmap_first_set_bit (def_map->def_blocks) >= 0)
{
int i;
EXECUTE_IF_SET_IN_BITMAP (def_map->def_blocks, def_bb->index + 1, i,
- return ((i < bb->index) ? false : true));
+ return ((i <= bb->index) ? false : true));
}
return true;