This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Speedup alias analysis [patch]
- From: Diego Novillo <dnovillo at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 23 Jun 2003 17:35:14 -0400
- Subject: [tree-ssa] Speedup alias analysis [patch]
- Organization: Red Hat Canada
This patch re-implements alias analysis to prevent the huge
compile time and memory consumption problems we were experiencing
in heavily aliased code.
The main idea behind the changes is to reduce the amount of
virtual operands emitted by reducing the size of the may-alias
sets. Also, I wanted to avoid creating virtual operands when
referencing regular variables. Previously, if a variable 'a' was
found to be aliased to pointer 'p', we would create virtual
operands even in statements that referenced 'a' directly.
- We no longer create a different memory tag for every pointer in
the program. Instead, when we find a new pointer P in the
program, we check whether P may be pointing to some other
pointer Q that we had found before. If so, we make P and Q
share the same memory tag. Since alias analysis will consider
the two pointers alias of each other, for all intents and
purposes in the optimizers their memory tags should be the
same.
- While finding variable references, we build two arrays. One
with all the pointers that have unique memory tags (POINTERS)
and another one with addressable locals and globals
(ADDRESSABLE_VARS).
- The alias analyzer will create may-alias sets for all the
memory tags collected in the POINTERS array. This means that
regular variables will not have may-alias sets anymore (unless
the grouping heuristic is triggered, see below). This is an
advantage for the optimizers because statements that reference
aliased variables directly may still be optimized. While
statements that reference these variables via the aliased
pointer will have virtual operands, as usual.
For instance, consider the following function:
foo (int i)
{
int *p, a, b;
if (i > 10)
p = &a;
else
p = &b;
*p = 3;
a = b + 2;
return *p;
}
After aliasing analysis has finished, the memory tag for pointer 'p'
will have two aliases, namely variables 'a' and 'b'. Every time pointer
'p' is dereferenced, we want to mark the operation as a potential
reference to 'a' and 'b'. This is marked with virtual operands.
Resulting in the following renamed program:
foo (int i)
{
int *p, a, b;
if (i_2 > 10)
p_4 = &a;
else
p_6 = &b;
# p_1 = PHI <p_4(1), p_6(2)>;
# a_7 = VDEF <a_3>;
# b_8 = VDEF <b_5>;
*p_1 = 3;
a_9 = b_8 + 2;
# VUSE <a_9>;
# VUSE <b_8>;
return *p_1;
}
This method allows the compiler to optimize aliased variables
when they're use directly and prevent optimizations when they
are being accessed via aliased pointers.
In certain cases, the list of may aliases for a pointer may
grow too large. This may cause an explosion in the number of
virtual operands inserted in the code. Resulting in increased
memory consumption and compilation time.
When the set of may aliases for a pointer grows beyond 5
elements (this is currently an arbitrary limit, I need to
experiment a bit more), instead of adding new variables to the
may-alias set, the new variables are made to share the same
alias set as the original pointer. For instance, suppose that
pointer 'p' may point to variables 'a', 'b', 'c', 'd', 'e', 'f'
and 'g'. After alias analysis, the alias sets will be as
follows:
may-alias(p) = { a, b, c, d, e }
may-alias(f) = { a, b, c, d, e }
may-alias(g) = { a, b, c, d, e }
Notice that this grouping causes variables 'f' and 'g' to be
aliased to variables they can't possibly alias to.
- Finally, the fact that we can now have SSA names in both
virtual and real operands, means that if two different names
can't coalesce in the SSA->normal pass, we may end up with an
uninitialized variable (gcc.c-torture/execute/980701-1.c).
# VUSE <ptr_5>
ptr.1_7 = &ptr;
# ptr_8 = VDEF <ptr_5>;
*ptr.1_7 = 0b;
ptr.3_11 = (long int)ptr_5;
Since ptr_8 and ptr_5 are in different partitions. The
SSA->normal pass converts that VDEF into a real copy operation.
Andrew, I'd like your opinion on this part because it certainly
goes against the current scheme of not mixing real and virtual
operands. It's very easy to disable if we find major problems
with it. But otherwise we would miss a few optimization
opportunities.
Bootstrapped and tested on x86, amd64, ia64 and ppc. Will commit
after all the tests finish running.
Diego.
* tree-alias-common.c (ptr_may_alias_var): Don't handle memory
tags.
* tree-dfa.c (struct alias_set_d): Remove. Update all users.
(alias_sets): Remove. Update all users.
(struct walk_state): Remove field aliased_objects_found.
(struct alias_map_d): New.
(addressable_vars): New local variable.
(pointers): New local variable.
(add_stmt_operand): Do not force aliased variables to be in virtual
operands.
(register_alias_set): Remove. Update all users.
(find_alias_for): Remove. Update all users.
(get_memory_tag_for): New local function.
(num_referenced_vars): Remove.
(num_aliased_objects): Remove. Update all users.
(aliased_objects): Remove. Update all users.
(aliased_objects_alias_set): Remove. Update all users.
(num_call_clobbered_vars): Remove. Update all users.
(dump_variable): Move code to dump aliases ...
(dump_may_aliases_for): ... here.
(debug_may_aliases_for): New function.
(compute_may_aliases): Initialize 'addressable_vars' and 'pointers'
arrays.
(compute_alias_sets): Re-implement matching pointers with
addressable variables. Limit the size of may-alias sets.
(may_alias_p): Re-implement to compare pointers against variables,
instead of memory tags.
(dump_alias_info): Re-implement to display pointers and addresable
variables arrays.
(add_referenced_var): Collect addressable variables and pointers.
Share memory tags among pointers that may alias each other.
* tree-flow.h (num_referenced_vars): Change to macro.
(referenced_var): Likewise.
(num_call_clobbered_vars): Likewise.
(call_clobbered_var): Likewise.
(dump_may_aliases_for): Declare.
(debug_may_aliases_for): Declare.
* tree-ssa.c (rewrite_vdefs): New local function.
(rewrite_out_of_ssa): Call it.
Index: tree-alias-common.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-alias-common.c,v
retrieving revision 1.1.2.30
diff -d -c -p -r1.1.2.30 tree-alias-common.c
*** tree-alias-common.c 18 Jun 2003 00:40:19 -0000 1.1.2.30
--- tree-alias-common.c 23 Jun 2003 16:47:37 -0000
*************** ptr_may_alias_var (ptr, var)
*** 1059,1074 ****
{
struct alias_annot_entry entry, *result;
alias_typevar ptrtv, vartv;
- var_ann_t tempann;
tree ptrcontext;
tree varcontext;
- tempann = get_var_ann (var);
- if (tempann && tempann->is_mem_tag && tempann->mem_tag)
- var = tempann->mem_tag;
- tempann = get_var_ann (ptr);
- if (tempann && tempann->is_mem_tag && tempann->mem_tag)
- ptr = tempann->mem_tag;
#if !FIELD_BASED
#else
if (TREE_CODE (ptr) == COMPONENT_REF)
--- 1059,1067 ----
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.121
diff -d -c -p -r1.1.4.121 tree-dfa.c
*** tree-dfa.c 13 Jun 2003 23:58:39 -0000 1.1.4.121
--- tree-dfa.c 23 Jun 2003 16:47:37 -0000
*************** struct clobber_data_d
*** 68,95 ****
voperands_t prev_vops;
};
! /* Alias sets. Each entry in the array ALIAS_SETS represents a unique tag
! that represents a group of variables with conflicting alias types. */
! struct alias_set_d
{
! /* Variable or memory tag representing all the variables in this set. */
! tree tag;
!
! /* Alias set of the memory pointed-to by TAG. */
! HOST_WIDE_INT tag_set;
!
! /* Number of elements in this set. */
! size_t num_elements;
};
! static varray_type alias_sets;
/* State information for find_vars_r. */
struct walk_state
{
! /* Hash tables used to avoid adding the same variable more than once. */
htab_t vars_found;
- htab_t aliased_objects_found;
/* Nonzero if the variables found under the current tree are written to. */
int is_store;
--- 68,94 ----
voperands_t prev_vops;
};
! /* Tuple to map a variable to its alias set. Used to cache the results of
! calls to get_alias_set(). */
! struct alias_map_d
{
! tree var;
! HOST_WIDE_INT set;
};
!
! /* ADDRESSABLE_VARS contains all the global variables and locals that have
! had their address taken. POINTERS contains all the pointers that have been
! referenced in the program. Alias analysis will determine, for every two
! elements from each array whether they may alias each other or not. */
! static GTY(()) varray_type addressable_vars;
! static GTY(()) varray_type pointers;
/* State information for find_vars_r. */
struct walk_state
{
! /* Hash table used to avoid adding the same variable more than once. */
htab_t vars_found;
/* Nonzero if the variables found under the current tree are written to. */
int is_store;
*************** static void collect_dfa_stats (struct df
*** 123,130 ****
static tree collect_dfa_stats_r (tree *, int *, void *);
static tree clobber_vars_r (tree *, int *, void *);
static void compute_alias_sets (void);
- static void register_alias_set (tree);
- static void find_alias_for (tree, HOST_WIDE_INT);
static bool may_alias_p (tree, HOST_WIDE_INT, tree, HOST_WIDE_INT);
static bool may_access_global_mem_p (tree);
static void set_def (tree *, tree);
--- 122,127 ----
*************** static void add_stmt_operand (tree *, tr
*** 134,139 ****
--- 131,137 ----
static void add_immediate_use (tree, tree);
static tree find_vars_r (tree *, int *, void *);
static void add_referenced_var (tree, struct walk_state *);
+ static tree get_memory_tag_for (tree);
static void compute_immediate_uses_for (tree, int);
static void add_may_alias (tree, tree);
static bool call_may_clobber (tree);
*************** static tree find_hidden_use_vars_r (tree
*** 143,177 ****
/* Global declarations. */
- /* The total number of referenced variables in the function. */
- 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 size_t num_aliased_objects;
-
- /* Arrays for all the potentially aliased memory objects in the
- function.
-
- A potentially aliased memory object can come from the following
- sources:
-
- * Memory tags associated with dereferenced pointers
- * 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_ALIAS_SET contains the alias set for those objects. */
- static GTY(()) varray_type aliased_objects;
- static GTY(()) 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;
--- 141,149 ----
*************** add_stmt_operand (tree *var_p, tree stmt
*** 591,599 ****
(execute/20020107-1.c). Do we really need to be this
drastic? Or should each optimization take care when
dealing with ASM_EXPRs? */
- if (v_ann->is_alias_tag)
- flags |= opf_force_vop;
-
if (flags & opf_is_def)
{
if (is_scalar
--- 563,568 ----
*************** void
*** 1147,1153 ****
dump_variable (FILE *file, tree var)
{
var_ann_t ann;
- varray_type aliases;
if (var == NULL_TREE)
{
--- 1116,1121 ----
*************** dump_variable (FILE *file, tree var)
*** 1165,1183 ****
print_generic_expr (file, ann->mem_tag, 0);
}
- aliases = ann->may_aliases;
- if (aliases)
- {
- size_t i, num_aliases = VARRAY_ACTIVE_SIZE (aliases);
- fprintf (file, ", may aliases: { ");
- for (i = 0; i < num_aliases; i++)
- {
- print_generic_expr (file, VARRAY_TREE (aliases, i), 0);
- fprintf (file, " ");
- }
- fprintf (file, "}");
- }
-
if (ann->is_alias_tag)
fprintf (file, ", is an alias tag");
--- 1133,1138 ----
*************** dump_variable (FILE *file, tree var)
*** 1199,1204 ****
--- 1154,1165 ----
if (ann->is_stored)
fprintf (file, ", is stored");
+ if (ann->may_aliases)
+ {
+ fprintf (file, ", may aliases: ");
+ dump_may_aliases_for (file, var);
+ }
+
fprintf (file, "\n");
}
*************** debug_variable (tree var)
*** 1212,1217 ****
--- 1173,1211 ----
}
+ /* Dump to FILE the list of variables that may be aliasing VAR. */
+
+ void
+ dump_may_aliases_for (FILE *file, tree var)
+ {
+ varray_type aliases = var_ann (var)->may_aliases;
+
+ if (aliases)
+ {
+ size_t i, num_aliases = VARRAY_ACTIVE_SIZE (aliases);
+
+ fprintf (file, "{ ");
+ for (i = 0; i < num_aliases; i++)
+ {
+ print_generic_expr (file, VARRAY_TREE (aliases, i), 0);
+ fprintf (file, " ");
+ }
+ fprintf (file, "}");
+ }
+
+ fprintf (file, "\n");
+ }
+
+
+ /* Dump to stderr the list of variables that may be aliasing VAR. */
+
+ void
+ debug_may_aliases_for (tree var)
+ {
+ dump_may_aliases_for (stderr, var);
+ }
+
+
/* Dump def-use edges on FILE. */
void
*************** dump_dfa_stats (FILE *file)
*** 1312,1322 ****
fprintf (file, fmt_str_1, "Referenced variables", num_referenced_vars,
SCALE (size), LABEL (size));
- size = num_aliased_objects * sizeof (tree);
- total += size;
- 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,
--- 1306,1311 ----
*************** void
*** 1505,1511 ****
compute_may_aliases (tree fndecl)
{
static htab_t vars_found;
- static htab_t aliased_objects_found;
basic_block bb;
block_stmt_iterator si;
struct walk_state walk_state;
--- 1494,1499 ----
*************** compute_may_aliases (tree fndecl)
*** 1527,1544 ****
block = BLOCK_CHAIN (block);
}
! num_aliased_objects = 0;
! VARRAY_TREE_INIT (aliased_objects, 20, "aliased_objects");
! VARRAY_WIDE_INT_INIT (aliased_objects_alias_set, 20,
! "aliased_objects_alias_set");
/* Hash table of all the objects the SSA builder needs to be aware of. */
vars_found = htab_create (50, htab_hash_pointer, htab_eq_pointer, NULL);
- /* Hash table of all the unique aliased objects found. */
- aliased_objects_found = htab_create (50, htab_hash_pointer, htab_eq_pointer,
- NULL);
-
if (flag_tree_points_to != PTA_NONE)
{
timevar_push (TV_TREE_PTA);
--- 1515,1526 ----
block = BLOCK_CHAIN (block);
}
! VARRAY_GENERIC_PTR_INIT (addressable_vars, 20, "addressable_vars");
! VARRAY_GENERIC_PTR_INIT (pointers, 20, "pointers");
/* Hash table of all the objects the SSA builder needs to be aware of. */
vars_found = htab_create (50, htab_hash_pointer, htab_eq_pointer, NULL);
if (flag_tree_points_to != PTA_NONE)
{
timevar_push (TV_TREE_PTA);
*************** compute_may_aliases (tree fndecl)
*** 1547,1553 ****
}
walk_state.vars_found = vars_found;
- walk_state.aliased_objects_found = aliased_objects_found;
walk_state.is_store = 0;
walk_state.is_indirect_ref = 0;
--- 1529,1534 ----
*************** compute_may_aliases (tree fndecl)
*** 1557,1564 ****
walk_tree (bsi_stmt_ptr (si), find_vars_r, &walk_state, NULL);
htab_delete (vars_found);
- htab_delete (aliased_objects_found);
-
compute_alias_sets ();
--- 1538,1543 ----
*************** compute_may_aliases (tree fndecl)
*** 1569,1855 ****
timevar_pop (TV_TREE_PTA);
}
! num_aliased_objects = 0;
! aliased_objects = NULL;
! aliased_objects_alias_set = NULL;
timevar_pop (TV_TREE_MAY_ALIAS);
}
! /* Compute type-based alias sets. This can be used in conjunction with
! points-to analysis.
!
! First we compute alias sets for objects which are stored into. Stores
! create the only may alias relationships we care about. If there are
! no aliased stores, then there's really nothing to do.
!
! Once we have alias sets for the aliased stores, we can check for
! conflicts with all the aliased objects in the function.
!
! Each entry I in ALIAS_SETS represents a set of all the variables that
! are aliased by ALIAS_SETS[I]. The ALIAS_SETS array tends to have few
! entries, and each entry will likely alias many program variables.
!
! This will negatively impact optimizations because variable uses will be
! reached by many definitions that can't really reach them. See the
! documentation in tree-ssa.c. */
!
! static void
! compute_alias_sets (void)
! {
! size_t i;
! 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. */
! for (i = 0; i < num_aliased_objects; i++)
! {
! tree var = VARRAY_TREE (aliased_objects, i);
! if (var_ann (var)->is_stored)
! register_alias_set (var);
! }
! /* Now for every potentially aliased object, see if the object's alias
! set conflicts with any of the alias sets for objects which were
! stored. */
! for (i = 0; i < num_aliased_objects; i++)
! {
! tree var = VARRAY_TREE (aliased_objects, i);
! find_alias_for (var, VARRAY_WIDE_INT (aliased_objects_alias_set, i));
! }
! /* If the function has calls to clobbering functions, make GLOBAL_VAR
! an alias for all call-clobbered variables. */
! if (global_var)
! for (i = 0; i < num_call_clobbered_vars; i++)
! {
! tree var = call_clobbered_var (i);
! add_may_alias (var, global_var);
! }
! /* Debugging dumps. */
! if (tree_ssa_dump_file && tree_ssa_dump_flags & TDF_ALIAS)
! {
! dump_alias_info (tree_ssa_dump_file);
! dump_referenced_vars (tree_ssa_dump_file);
! }
! /* Deallocate memory used by ALIAS_SETS. */
! for (i = 0; i < VARRAY_ACTIVE_SIZE (alias_sets); i++)
! {
! struct alias_set_d *as;
! as = (struct alias_set_d *) VARRAY_GENERIC_PTR (alias_sets, i);
! free (as);
! }
! alias_sets = NULL;
! }
! /* Potentially add VAR as a new alias tag in ALIAS_SETS. VAR is assumed to
! be an addressable local, a global or the memory tag of a dereferenced
! pointer. Furthermore, this function assumes that VAR is stored at least
! once (for aliasing, we are only interested in stores, if two variables
! alias each other but are never stored, the fact that they alias is
! irrelevant for the optimizer).
! Addressable and global variables are distinguished from memory tags by
! checking the IS_MEM_TAG annotation. If VAR has IS_MEM_TAG set, then VAR
! is a memory tag representing dereferences of the pointer in
! var_ann(VAR)->mem_tag.
! Note that aliasing can only occur between regular variables and memory
! tags representing pointer dereferences. Therefore, when deciding if two
! objects may alias each other, we only need to compare regular variables
! against memory tags.
!
! To decide whether VAR should start a new alias set, VAR is compared
! against all the existing entries in ALIAS_SETS. If VAR does not
! conflict with any entry, then a new entry is added for it.
! The following are the rules used to determine if a new entry should be
! added for VAR:
! 1- If VAR is a regular variable, an entry in ALIAS_SETS will be added
! only if VAR's alias set is not already represented, or if all the
! entries that have the same alias set as VAR are also regular
! variables (because two regular variables cannot possibly alias each
! other).
! 2- If VAR is a memory tag, an entry in ALIAS_SETS will be added only if
! VAR's alias set is not already represented. */
static void
! register_alias_set (tree var)
{
size_t i;
- struct alias_set_d *curr;
- HOST_WIDE_INT var_set;
- bool found;
- var_ann_t ann;
-
- var_set = get_alias_set (var);
- ann = var_ann (var);
! /* Search the ALIAS_SETS list for entries which match VAR_SET. FIXME:
! ALIAS_SETS will usually be small (<< 10 entries). If it becomes a
! performance problem, try with a splay tree. */
! found = false;
! for (i = 0; i < VARRAY_ACTIVE_SIZE (alias_sets); i++)
{
! var_ann_t tag_ann;
! curr = (struct alias_set_d *) VARRAY_GENERIC_PTR (alias_sets, i);
! tag_ann = var_ann (curr->tag);
! /* See if we have any entries with the same alias set. */
! if (curr->tag_set == var_set)
! {
! /* If VAR is a regular variable and the current entry is another
! regular variable, keep looking (rule #1 above). */
! if (!tag_ann->is_mem_tag && !ann->is_mem_tag)
continue;
!
! /* Otherwise, we have found a matching entry. Since the current
! tag and/or VAR are a memory tag, we don't need to keep
! looking (rules #1 and #2 above). */
! found = true;
! break;
}
}
! /* If we did not find an entry in ALIAS_SETS with a matching
! alias set, create a new entry. */
! if (!found)
! {
! curr = xmalloc (sizeof (*curr));
! curr->tag = var;
! curr->tag_set = var_set;
! curr->num_elements = 0;
! VARRAY_PUSH_GENERIC_PTR (alias_sets, (void *) curr);
! }
! }
!
!
! /* Set an alias between VAR and any entry in ALIAS_SETS that has a
! conflicting alias set with VAR. */
!
! static void
! find_alias_for (tree var, HOST_WIDE_INT var_set)
! {
! size_t i;
! for (i = 0; i < VARRAY_ACTIVE_SIZE (alias_sets); i++)
{
! struct alias_set_d *as;
!
! as = (struct alias_set_d *) VARRAY_GENERIC_PTR (alias_sets, i);
!
! /* If AS->TAG aliases VAR, add it to the set of may-aliases for VAR. */
! if (may_alias_p (as->tag, as->tag_set, var, var_set))
! {
! /* Add AS->TAG to the list of aliases for VAR. */
! add_may_alias (var, as->tag);
! as->num_elements++;
! }
}
}
! /* Return TRUE if variables V1 and V2 may alias. V1_ALIAS_SET is the alias
! set for V1. V2_ALIAS_SET is the alias set for V2. */
static bool
! may_alias_p (tree v1, HOST_WIDE_INT v1_alias_set,
! tree v2, HOST_WIDE_INT v2_alias_set)
{
! tree var;
! HOST_WIDE_INT var_alias_set;
! tree tag;
! HOST_WIDE_INT tag_alias_set;
! var_ann_t v_ann, t_ann, v1_ann, v2_ann;
! tree tag_ptr;
!
! /* A variable cannot alias itself. */
! if (v1 == v2)
! return false;
! v1_ann = var_ann (v1);
! v2_ann = var_ann (v2);
! /* One of the two variables must be a memory tag. Otherwise V1 and V2
! cannot alias each other. */
! if (v1_ann->is_mem_tag)
! {
! var = v2;
! var_alias_set = v2_alias_set;
! v_ann = v2_ann;
! tag = v1;
! tag_alias_set = v1_alias_set;
! t_ann = v1_ann;
! }
! else if (v2_ann->is_mem_tag)
! {
! var = v1;
! var_alias_set = v1_alias_set;
! v_ann = v1_ann;
! tag = v2;
! tag_alias_set = v2_alias_set;
! t_ann = v2_ann;
! }
! else
return false;
! tag_ptr = t_ann->mem_tag;
! /* If the alias sets don't conflict then TAG cannot alias VAR. */
! if (!alias_sets_conflict_p (tag_alias_set, var_alias_set))
{
! /* Handle aliases to structure fields. If either VAR or TAG are
aggregate types, they may not have conflicting types, but one of
the structures could contain a pointer to the other one.
For instance, given
! TAG -> struct P *p;
VAR -> struct Q *q;
It may happen that '*p' and '*q' can't alias because 'struct P'
and 'struct Q' have non-conflicting alias sets. However, it could
! happen that one of the fields in 'struct P' is a 'struct Q *' and
vice-versa.
Therefore, we also need to check if 'struct P' aliases 'struct Q *'
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 (AGGREGATE_TYPE_P (TREE_TYPE (tag))
|| AGGREGATE_TYPE_P (TREE_TYPE (var)))
{
tree ptr_to_var = TYPE_POINTER_TO (TREE_TYPE (var));
! /* If no pointer-to VAR exists, then TAG can't alias VAR. */
if (ptr_to_var == NULL_TREE)
return false;
! /* Otherwise, return true if TAG aliases a pointer to VAR or VAR
! aliases TAG's pointer. */
! return
! alias_sets_conflict_p (tag_alias_set, get_alias_set (ptr_to_var))
! || alias_sets_conflict_p (var_alias_set, get_alias_set (tag_ptr));
}
else
return false;
}
! /* If -ftree-points-to is given, check if TAG may point to VAR. */
! if (flag_tree_points_to)
! if (!ptr_may_alias_var (tag_ptr, var))
! return false;
return true;
}
--- 1548,1774 ----
timevar_pop (TV_TREE_PTA);
}
! /* Deallocate memory used by aliasing data structures. */
! addressable_vars = NULL;
! pointers = NULL;
timevar_pop (TV_TREE_MAY_ALIAS);
}
! /* Compute alias sets. Aliasing information is computed in two stages:
! 1- Artificial variables called "memory tags" are created for each
! pointer used in the program. Each memory tag (MT) represents the
! memory location pointed by its associated pointer. Since pointers
! may point to each other, two or more pointers that may point to each
! other will be assigned the same memory tag. These unique memory tags
! are computed by get_memory_tag_for and their associated pointers are
! added to the POINTERS array.
! 2- All the addressable variables in ADDRESABLE_VARS are compared against
! the pointers collected in step 1. If a pointer P may point to
! variable V, then V is added to the list of may-aliases for P.
! For instance, consider the following function:
! foo (int i)
! {
! int *p, a, b;
!
! if (i > 10)
! p = &a;
! else
! p = &b;
!
! *p = 3;
! a = b + 2;
! return *p;
! }
! After aliasing analysis has finished, the memory tag for pointer 'p'
! will have two aliases, namely variables 'a' and 'b'. Every time pointer
! 'p' is dereferenced, we want to mark the operation as a potential
! reference to 'a' and 'b'. This is marked with virtual operands.
! Resulting in the following renamed program:
! foo (int i)
! {
! int *p, a, b;
! if (i_2 > 10)
! p_4 = &a;
! else
! p_6 = &b;
! # p_1 = PHI <p_4(1), p_6(2)>;
+ # a_7 = VDEF <a_3>;
+ # b_8 = VDEF <b_5>;
+ *p_1 = 3;
+ a_9 = b_8 + 2;
! # VUSE <a_9>;
! # VUSE <b_8>;
! return *p_1;
! }
! This method allows the compiler to optimize aliased variables when
! they're use directly and prevent optimizations when they are being
! accessed via aliased pointers.
! In certain cases, the list of may aliases for a pointer may grow too
! large. This may cause an explosion in the number of virtual operands
! inserted in the code. Resulting in increased memory consumption and
! compilation time.
! When the set of may aliases for a pointer grows beyond 5 elements
! (FIXME, this is currently an arbitrary limit), instead of adding new
! variables to the may-alias set, the new variables are made to share the
! same alias set as the original pointer. For instance, suppose that
! pointer 'p' may point to variables 'a', 'b', 'c', 'd', 'e', 'f' and 'g'.
! After alias analysis, the alias sets will be as follows:
! may-alias(p) = { a, b, c, d, e }
! may-alias(f) = { a, b, c, d, e }
! may-alias(g) = { a, b, c, d, e }
! Notice that this grouping causes variables 'f' and 'g' to be aliased to
! variables they can't possibly alias to. */
static void
! compute_alias_sets (void)
{
size_t i;
! /* For every pointer P, determine which addressable variables may alias
! with P. */
! for (i = 0; i < VARRAY_ACTIVE_SIZE (pointers); i++)
{
! size_t j;
! struct alias_map_d *ptr = VARRAY_GENERIC_PTR (pointers, i);
! tree mem = var_ann (ptr->var)->mem_tag;
! var_ann_t mem_ann = var_ann (mem);
! for (j = 0; j < VARRAY_ACTIVE_SIZE (addressable_vars); j++)
! {
! struct alias_map_d *var = VARRAY_GENERIC_PTR (addressable_vars, j);
! var_ann_t v_ann = var_ann (var->var);
! /* Skip memory tags and variables that have never been written to. */
! if (!mem_ann->is_stored && !v_ann->is_stored)
continue;
!
! if (may_alias_p (ptr->var, ptr->set, var->var, var->set))
! {
! /* If MEM has less than 5 aliases in its alias set, add
! VAR->VAR to the list of aliases for MEM. Otherwise,
! set the may-alias set for VAR->VAR to be the same alias
! set as MEM. This is to avoid the problem of having
! large may-alias sets. Large may-alias sets translate into
! lots of virtual operands which can slow down the SSA pass
! tremendously. */
! if (mem_ann->may_aliases
! && VARRAY_ACTIVE_SIZE (mem_ann->may_aliases) >= 5)
! v_ann->may_aliases = mem_ann->may_aliases;
! else
! add_may_alias (mem, var->var);
! }
}
}
! /* If the function has calls to clobbering functions, make GLOBAL_VAR
! an alias for all call-clobbered variables. */
! if (global_var)
! for (i = 0; i < num_call_clobbered_vars; i++)
! {
! tree var = call_clobbered_var (i);
! add_may_alias (var, global_var);
! }
! /* Debugging dumps. */
! if (tree_ssa_dump_file && tree_ssa_dump_flags & TDF_ALIAS)
{
! dump_alias_info (tree_ssa_dump_file);
! dump_referenced_vars (tree_ssa_dump_file);
}
}
! /* Return TRUE if pointer PTR may point to variable VAR.
!
! MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR
! This is needed because when checking for type conflicts we are
! interested in the alias set of the memory location pointed-to by
! PTR. The alias set of PTR itself is irrelevant.
!
! VAR_ALIAS_SET is the alias set for VAR. */
static bool
! may_alias_p (tree ptr, HOST_WIDE_INT mem_alias_set,
! tree var, HOST_WIDE_INT var_alias_set)
{
! tree mem;
! var_ann_t v_ann, m_ann;
! mem = var_ann (ptr)->mem_tag;
! /* By convention, a variable cannot alias itself. */
! if (mem == var)
return false;
! v_ann = var_ann (var);
! m_ann = var_ann (mem);
! #if defined ENABLE_CHECKING
! if (!m_ann->is_mem_tag)
! abort ();
! #endif
!
! /* If the alias sets don't conflict then MEM cannot alias VAR. */
! if (!alias_sets_conflict_p (mem_alias_set, var_alias_set))
{
! /* Handle aliases to structure fields. If either VAR or MEM are
aggregate types, they may not have conflicting types, but one of
the structures could contain a pointer to the other one.
For instance, given
! MEM -> struct P *p;
VAR -> struct Q *q;
It may happen that '*p' and '*q' can't alias because 'struct P'
and 'struct Q' have non-conflicting alias sets. However, it could
! happen that one of the fields in 'struct P' is a 'struct Q *' or
vice-versa.
Therefore, we also need to check if 'struct P' aliases 'struct Q *'
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 (AGGREGATE_TYPE_P (TREE_TYPE (mem))
|| AGGREGATE_TYPE_P (TREE_TYPE (var)))
{
tree ptr_to_var = TYPE_POINTER_TO (TREE_TYPE (var));
! /* If no pointer-to VAR exists, then MEM can't alias VAR. */
if (ptr_to_var == NULL_TREE)
return false;
! /* If MEM doesn't alias a pointer to VAR and VAR doesn't alias
! PTR, then PTR can't alias VAR. */
! if (!alias_sets_conflict_p (mem_alias_set, get_alias_set (ptr_to_var))
! && !alias_sets_conflict_p (var_alias_set, get_alias_set (ptr)))
! return false;
}
else
return false;
}
! /* If -ftree-points-to is given, check if PTR may point to VAR. */
! if (flag_tree_points_to != PTA_NONE
! && !ptr_may_alias_var (ptr, var))
! return false;
!
return true;
}
*************** add_may_alias (tree var, tree alias)
*** 1895,1934 ****
void
dump_alias_info (FILE *file)
{
! size_t i, j, k;
const char *funcname
= (*lang_hooks.decl_printable_name) (current_function_decl, 2);
! if (alias_sets == NULL)
return;
! fprintf (file, "\nAlias information for %s: %ld sets\n\n",
! funcname, (long) VARRAY_ACTIVE_SIZE (alias_sets));
! for (i = 0; i < VARRAY_ACTIVE_SIZE (alias_sets); i++)
{
! struct alias_set_d *as;
!
! as = (struct alias_set_d *) VARRAY_GENERIC_PTR (alias_sets, i);
!
! fprintf (file, "Alias set #%u:\n", (unsigned) i);
! fprintf (file, " Tag: ");
! dump_variable (file, as->tag);
! fprintf (file, " Aliases objects: { ");
! for (j = 0; j < num_aliased_objects; j++)
{
! tree var = VARRAY_TREE (aliased_objects, j);
! varray_type aliases = may_aliases (var);
! 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");
}
}
--- 1814,1860 ----
void
dump_alias_info (FILE *file)
{
! size_t i;
const char *funcname
= (*lang_hooks.decl_printable_name) (current_function_decl, 2);
! if (addressable_vars == NULL)
return;
! fprintf (file, "\nAlias information for %s\n\n", funcname);
! fprintf (file, "%u addressable variables\n",
! (unsigned) VARRAY_ACTIVE_SIZE (addressable_vars));
! fprintf (file, "%u memory tags\n\n",
! (unsigned) VARRAY_ACTIVE_SIZE (pointers));
! for (i = 0; i < VARRAY_ACTIVE_SIZE (pointers); i++)
{
! struct alias_map_d *map = VARRAY_GENERIC_PTR (pointers, i);
! tree mem = var_ann (map->var)->mem_tag;
! varray_type aliases = may_aliases (mem);
! if (aliases)
! {
! fprintf (file, "Memory tag ");
! print_generic_expr (file, mem, 0);
! fprintf (file, " aliases ");
! dump_may_aliases_for (file, mem);
! }
! }
! for (i = 0; i < VARRAY_ACTIVE_SIZE (addressable_vars); i++)
! {
! struct alias_map_d *map = VARRAY_GENERIC_PTR (addressable_vars, i);
! varray_type aliases = may_aliases (map->var);
! if (aliases)
{
! fprintf (file, "Addressable var ");
! print_generic_expr (file, map->var, 0);
! fprintf (file, " aliases ");
! dump_may_aliases_for (file, map->var);
}
}
+
+ fprintf (file, "\n");
}
*************** find_vars_r (tree *tp, int *walk_subtree
*** 2149,2158 ****
/* Add VAR to the list of dereferenced variables. If VAR is a candidate
! for aliasing, add it to the ALIASED_OBJECTS set of varrays that are
! needed for 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 flags
indicating if we're processing a load or store. Note that this function
assumes that VAR is a valid SSA variable. */
--- 2075,2085 ----
/* Add VAR to the list of dereferenced variables. If VAR is a candidate
! for aliasing, add it to the ADDRESSABLE_VAR array. If VAR is a memory
! tag, add it to the POINTERS array. These two arrays are used for
! alias analysis (See compute_alias_sets).
! WALK_STATE is an array with a hash table used to avoid adding the
same variable more than once to its corresponding set as well as flags
indicating if we're processing a load or store. Note that this function
assumes that VAR is a valid SSA variable. */
*************** add_referenced_var (tree var, struct wal
*** 2162,2247 ****
{
void **slot;
htab_t vars_found = walk_state->vars_found;
! htab_t aliased_objects_found = walk_state->aliased_objects_found;
! var_ann_t ann = get_var_ann (var);
!
! /* Remember if the variable has been written to. This is important for
! alias analysis. If a variable is never modified, it is not
! interesting as an entry in ALIAS_SETS (see compute_may_aliases). */
! if (walk_state->is_store)
! ann->is_stored = 1;
!
! /* Handle aliasing information. Memory tags, global and addressable
! local variables are all potentially aliased and call clobbered. */
! if (ann->is_mem_tag
! || TREE_ADDRESSABLE (var)
! || decl_function_context (var) == NULL)
! {
! slot = htab_find_slot (aliased_objects_found, (void *) var, INSERT);
! if (*slot == NULL)
! {
! *slot = (void *) var;
! VARRAY_PUSH_TREE (aliased_objects, var);
! VARRAY_PUSH_WIDE_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;
! }
! }
! }
slot = htab_find_slot (vars_found, (void *) var, INSERT);
if (*slot == NULL)
{
/* This is the first time we find this variable, add it to the
! REFERENCED_VARS array, also annotate it with its unique id. */
*slot = (void *) var;
VARRAY_PUSH_TREE (referenced_vars, var);
- ann->uid = num_referenced_vars++;
/* Arguments or global variable pointers may point to memory outside
the current function. */
if (POINTER_TYPE_P (TREE_TYPE (var))
&& (TREE_CODE (var) == PARM_DECL
|| decl_function_context (var) == NULL_TREE))
! ann->may_point_to_global_mem = 1;
/* By default, assume that the variable has no real references. If
the variable is used as a real operand to a statement (i.e.,
add_use and set_def), this field will be set to 1. */
! ann->has_real_refs = 0;
}
! /* If VAR is a pointer referenced in an INDIRECT_REF node, create a
! memory tag to represent the location pointed-to by VAR. */
if (walk_state->is_indirect_ref)
{
- tree tag;
- var_ann_t tag_ann;
-
/* If pointer VAR still doesn't have a memory tag associated with it,
! create it now. */
! tag = ann->mem_tag;
if (tag == NULL_TREE)
! {
! tag = create_tmp_alias_var (TREE_TYPE (TREE_TYPE (var)), "MT");
! tag_ann = get_var_ann (tag);
! tag_ann->mem_tag = var;
! tag_ann->is_mem_tag = 1;
! if (ann->may_point_to_global_mem)
! tag_ann->may_alias_global_mem = 1;
! ann->mem_tag = tag;
! }
walk_state->is_indirect_ref = 0;
add_referenced_var (tag, walk_state);
}
}
--- 2089,2235 ----
{
void **slot;
htab_t vars_found = walk_state->vars_found;
! var_ann_t v_ann;
! v_ann = get_var_ann (var);
slot = htab_find_slot (vars_found, (void *) var, INSERT);
if (*slot == NULL)
{
+ bool is_addressable;
+
/* This is the first time we find this variable, add it to the
! REFERENCED_VARS array and annotate it with attributes that are
! intrinsic to the variable. */
*slot = (void *) var;
+ v_ann->uid = num_referenced_vars;
VARRAY_PUSH_TREE (referenced_vars, var);
/* Arguments or global variable pointers may point to memory outside
the current function. */
if (POINTER_TYPE_P (TREE_TYPE (var))
&& (TREE_CODE (var) == PARM_DECL
|| decl_function_context (var) == NULL_TREE))
! v_ann->may_point_to_global_mem = 1;
/* By default, assume that the variable has no real references. If
the variable is used as a real operand to a statement (i.e.,
add_use and set_def), this field will be set to 1. */
! v_ann->has_real_refs = 0;
!
! is_addressable = TREE_ADDRESSABLE (var)
! || decl_function_context (var) == NULL;
!
! /* Global variables and addressable locals may be aliased. Create an
! entry in ADDRESSABLE_VARS for VAR. */
! if (is_addressable)
! {
! /* Create a new alias set entry for VAR. */
! struct alias_map_d *alias_map;
! alias_map = ggc_alloc (sizeof (*alias_map));
! alias_map->var = var;
! alias_map->set = get_alias_set (var);
! VARRAY_PUSH_GENERIC_PTR (addressable_vars, (void *) alias_map);
! }
!
! /* If the variable is a writeable memory tag, a global or an
! addressable local, it may be clobbered by function calls. */
! if (!TREE_READONLY (var)
! && (is_addressable || v_ann->is_mem_tag))
! {
! add_call_clobbered_var (var);
! v_ann->is_call_clobbered = 1;
! }
}
! /* Now, set attributes that depend on WALK_STATE. */
!
! /* Remember if the variable has been written to. This is important for
! alias analysis. If a variable and its aliases are never modified, it
! is not interesting for the optimizers because there are no aliased
! stores to keep track of. */
! if (walk_state->is_store)
! v_ann->is_stored = 1;
!
! /* If VAR is a pointer referenced in an INDIRECT_REF node, create (or
! re-use) a memory tag to represent the location pointed-to by VAR. */
if (walk_state->is_indirect_ref)
{
/* If pointer VAR still doesn't have a memory tag associated with it,
! create it now or re-use an existing one. A memory tag for some
! other pointer P will be reused if P and VAR may point to each
! other. */
! tree tag = v_ann->mem_tag;
if (tag == NULL_TREE)
! tag = get_memory_tag_for (var);
!
! /* Associate the tag with pointer VAR. */
! v_ann->mem_tag = tag;
+ /* Add the memory tag to the list of referenced variables. Note that
+ this needs to be done every time because there are attributes for
+ the memory tag that depend on WALK_STATE (e.g., whether this
+ variable is being stored-to). */
walk_state->is_indirect_ref = 0;
add_referenced_var (tag, walk_state);
+
+ /* If pointer VAR may point to global mem, then TAG may alias
+ global memory. */
+ if (v_ann->may_point_to_global_mem)
+ var_ann (tag)->may_alias_global_mem = 1;
}
+ }
+
+
+ /* Return the memory tag associated to pointer P. */
+
+ static tree
+ get_memory_tag_for (tree ptr)
+ {
+ size_t i;
+ tree tag;
+ tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
+ HOST_WIDE_INT tag_set = get_alias_set (tag_type);
+
+ /* See if PTR may alias any of the existing pointers. Note that we can't
+ use may_alias_p here because we have not created a memory tag for PTR
+ yet. */
+ for (i = 0, tag = NULL_TREE; i < VARRAY_ACTIVE_SIZE (pointers); i++)
+ {
+ struct alias_map_d *curr = VARRAY_GENERIC_PTR (pointers, i);
+ if (alias_sets_conflict_p (curr->set, tag_set)
+ && (flag_tree_points_to == PTA_NONE
+ || ptr_may_alias_var (ptr, curr->var)))
+ {
+ tag = var_ann (curr->var)->mem_tag;
+ break;
+ }
+ }
+
+ /* If VAR cannot alias with any of the existing memory tags, create a new
+ tag for PTR and add it to the POINTERS array. */
+ if (tag == NULL_TREE)
+ {
+ struct alias_map_d *alias_map;
+ var_ann_t tag_ann;
+
+ /* Create a new MT.* artificial variable representing the memory
+ location pointed-to by PTR. */
+ tag = create_tmp_alias_var (tag_type, "MT");
+ tag_ann = get_var_ann (tag);
+ tag_ann->is_mem_tag = 1;
+ tag_ann->mem_tag = NULL_TREE;
+
+ /* Add PTR to the POINTERS array. Note that we are not interested in
+ PTR's alias set. Instead, we cache the alias set for the memory that
+ PTR points to. */
+ alias_map = ggc_alloc (sizeof (*alias_map));
+ alias_map->var = ptr;
+ alias_map->set = tag_set;
+ VARRAY_PUSH_GENERIC_PTR (pointers, (void *) alias_map);
+ }
+
+ return tag;
}
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.85
diff -d -c -p -r1.1.4.85 tree-flow.h
*** tree-flow.h 17 Jun 2003 02:18:06 -0000 1.1.4.85
--- tree-flow.h 23 Jun 2003 16:47:37 -0000
*************** extern int tree_warn_uninitialized;
*** 359,391 ****
/* Array of all variables referenced in the function. */
extern GTY(()) varray_type referenced_vars;
/* Artificial variable used to model the effects of function calls. */
extern GTY(()) tree global_var;
- /* Accessors for the referenced_vars array. */
- extern size_t num_referenced_vars;
-
- static inline tree referenced_var PARAMS ((size_t));
- static inline tree
- 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. */
#define SCALE(x) ((unsigned long) ((x) < 1024*10 \
--- 359,377 ----
/* Array of all variables referenced in the function. */
extern GTY(()) varray_type referenced_vars;
+ #define num_referenced_vars VARRAY_ACTIVE_SIZE (referenced_vars)
+ #define referenced_var(i) VARRAY_TREE (referenced_vars, i)
+
/* Artificial variable used to model the effects of function calls. */
extern GTY(()) tree global_var;
/* Array of all variables that are call clobbered in the function. */
extern GTY(()) varray_type call_clobbered_vars;
! #define num_call_clobbered_vars VARRAY_ACTIVE_SIZE (call_clobbered_vars)
! #define add_call_clobbered_var(v) VARRAY_PUSH_TREE (call_clobbered_vars, v)
! #define call_clobbered_var(i) VARRAY_TREE (call_clobbered_vars, i)
/* Macros for showing usage statistics. */
#define SCALE(x) ((unsigned long) ((x) < 1024*10 \
*************** extern void debug_referenced_vars (void)
*** 444,449 ****
--- 430,437 ----
extern void dump_referenced_vars (FILE *);
extern void dump_variable (FILE *, tree);
extern void debug_variable (tree);
+ extern void dump_may_aliases_for (FILE *, tree);
+ extern void debug_may_aliases_for (tree);
extern void dump_immediate_uses (FILE *);
extern void debug_immediate_uses (void);
extern void dump_immediate_uses_for (FILE *, tree);
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.94
diff -d -c -p -r1.1.4.94 tree-ssa.c
*** tree-ssa.c 16 Jun 2003 18:54:00 -0000 1.1.4.94
--- tree-ssa.c 23 Jun 2003 16:47:37 -0000
*************** static inline void set_if_valid (var_map
*** 205,210 ****
--- 205,211 ----
static inline void add_conflicts_if_valid (root_var_p, conflict_graph,
var_map, sbitmap, tree);
static void replace_variable (var_map, tree *);
+ static void rewrite_vdefs (block_stmt_iterator *, varray_type, var_map);
/* Main entry point to the SSA builder. FNDECL is the gimplified function
to convert.
*************** rewrite_out_of_ssa (tree fndecl)
*** 1626,1631 ****
--- 1627,1636 ----
get_stmt_operands (stmt);
+ ops = vdef_ops (stmt);
+ if (ops)
+ rewrite_vdefs (&si, ops, map);
+
if (TREE_CODE (stmt) == MODIFY_EXPR
&& (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME))
is_copy = 1;
*************** rewrite_out_of_ssa (tree fndecl)
*** 1645,1651 ****
*def_p = var_to_partition_to_var (map, *def_p);
replace_variable (map, def_p);
! if (is_copy && num_ops == 1 && use_p && def_p && (*def_p == *use_p))
remove = 1;
}
--- 1650,1660 ----
*def_p = var_to_partition_to_var (map, *def_p);
replace_variable (map, def_p);
! if (is_copy
! && num_ops == 1
! && use_p
! && def_p
! && (*def_p == *use_p))
remove = 1;
}
*************** rewrite_out_of_ssa (tree fndecl)
*** 1667,1673 ****
remove_phi_node (phi, NULL_TREE, bb);
}
}
-
}
delete_elim_graph (g);
--- 1676,1681 ----
*************** rewrite_out_of_ssa (tree fndecl)
*** 1697,1702 ****
--- 1705,1748 ----
}
+ /* Rewrite virtual definitions in VDEFS from the statement pointed by
+ iterator SI_P, potentially converting them into real copy operations. A
+ virtual definition is converted into a copy operation when the LHS of
+ the VDEF has been used as a real operand in some statement.
+
+ This happens when variables are aliased and are referenced directly or
+ via their aliased pointers. Converting the VDEF into a real copy
+ operation is necessary for correctly coalescing the different names when
+ two or more are live simultaneously. */
+
+ static void
+ rewrite_vdefs (block_stmt_iterator *si_p, varray_type vdefs, var_map map)
+ {
+ size_t i;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (vdefs); i++)
+ {
+ tree lhs, rhs, vdef = VARRAY_TREE (vdefs, i);
+
+ if (!var_ann (SSA_NAME_VAR (VDEF_RESULT (vdef)))->has_real_refs)
+ continue;
+
+ lhs = var_to_partition_to_var (map, VDEF_RESULT (vdef));
+ rhs = var_to_partition_to_var (map, VDEF_OP (vdef));
+
+ if (lhs
+ && rhs
+ && TREE_CODE (lhs) != SSA_NAME
+ && TREE_CODE (rhs) != SSA_NAME
+ && lhs != rhs)
+ {
+ tree t = build (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
+ bsi_insert_before (si_p, t, BSI_SAME_STMT);
+ }
+ }
+ }
+
+
/* Remove edge E and remove the corresponding arguments from the PHI nodes
in E's destination block. Return a TREE_LIST node with all the removed
PHI arguments. */
*************** static void
*** 2297,2305 ****
init_tree_ssa (void)
{
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));
global_var = NULL_TREE;
--- 2343,2349 ----
*************** delete_tree_ssa (tree fndecl)
*** 2334,2343 ****
for (i = 0; i < num_referenced_vars; i++)
referenced_var (i)->common.ann = NULL;
- num_referenced_vars = 0;
referenced_vars = NULL;
global_var = NULL_TREE;
- num_call_clobbered_vars = 0;
call_clobbered_vars = NULL;
}
--- 2378,2385 ----