[ tree-ssa ] speeding up tree alias analysis
law@redhat.com
law@redhat.com
Thu Jan 30 18:52:00 GMT 2003
This is the first batch of my pending changes to speed up the tree alias
analysis code. This message is long, but if you take the time to read
and understand you'll see how we managed to do billions of unnecessary
calls and waste tons of time in the process.
As I've outlined before, we're making 4 orders of magnitude more calls
to get_base_symbol and get_alias_set (and its descendants) than are
necessary and those calls account for nearly 50% of the time spent
building may alias information for 20001226-1.c. 2.5 billion calls
when 100k should be sufficient.
Let's look at a simplified version of the main loop for computing may aliases:
foreach INDIRECT_REF X
{
if (may_access_global_mem (X))
set_may_alias_global_mem (X)
foreach INDIRECT_REF Y
{
if (may_alias (X, Y))
{
find_alias_tag (X, Y);
add new alias (X, Y);
if (may_access_global_mem (Y))
{
set_may_alias_global_mem (Y);
set_may_alias_global_mem (AT);
}
}
}
foreach ADDRESSABLE Y
{
if (may_alias (X, Y))
{
find_alias_tag (X, Y);
add new alias (X, Y);
if (may_access_global_mem (Y))
{
set_may_alias_global_mem (Y);
set_may_alias_global_mem (AT);
}
}
}
}
Each call to may_alias has to call get_base_symbol for X and Y and
get_alias_set for X and Y.
It should be pretty obvious that the base symbol and alias set for X
is invariant for the inner loop. So conceptually you could rewrite
those as
foreach INDIRECT_REF X
{
X_BASE = get_base_symbol (X);
X_ALIAS_SET = get_alias_set (X);
if (may_access_global_mem (X))
set_may_alias_global_mem (X)
foreach INDIRECT_REF Y
{
if (may_alias (X, X_BASE, X_ALIAS_SET, Y))
{
find_alias_tag (X, Y);
add new alias (X, Y);
if (may_access_global_mem (Y))
{
set_may_alias_global_mem (Y);
set_may_alias_global_mem (AT);
}
}
}
foreach ADDRESSABLE Y
{
if (may_alias (X, X_BASE, X_ALIAS_SET, Y))
{
find_alias_tag (X, Y);
add new alias (X, Y);
if (may_access_global_mem (Y))
{
set_may_alias_global_mem (Y);
set_may_alias_global_mem (AT);
}
}
}
}
[ And may_alias is updated to not call get_base_symbol or get_alias_set
for X. ]
That gets rid of a bunch of useless work. However, it should also be
clear that the information for Y is redundantly computed each for
each iteration of the outer loop, which is still extremely wasteful.
So when we build the arrays of indirect refs and addressable vars, we
go ahead and compute the base symbol and alias set information at
that time. Thus the loops look something like this:
Compute and store base and alias set information when locating the
indirect references and addressable objects.
foreach INDIRECT_REF X
{
if (may_access_global_mem (X))
set_may_alias_global_mem (X)
foreach INDIRECT_REF Y
{
if (may_alias (X, X_BASE, X_ALIAS_SET, Y, Y_BASE, Y_ALIAS_SET))
{
find_alias_tag (X, Y);
add new alias (X, Y);
if (may_access_global_mem (Y))
{
set_may_alias_global_mem (Y);
set_may_alias_global_mem (AT);
}
}
}
foreach ADDRESSABLE Y
{
if (may_alias (X, X_BASE, X_ALIAS_SET, Y, Y_BASE, Y_ALIAS_SET))
{
find_alias_tag (X, Y);
add new alias (X, Y);
if (may_access_global_mem (Y))
{
set_may_alias_global_mem (Y);
set_may_alias_global_mem (AT);
}
}
}
}
[ And may_alias is updated to never call get_base_symbol or get_alias_set. ]
We've effectively hoisted the invariant calls to get_base_symbol and
get_alias_set occurring within may_alias out of all the loops.
But wait, there's more. If you look at how find_alias_tag works you'll
find this little gem:
for (i = 0; i < num_alias_tags; i++)
if (may_alias_p (alias_tags[i], X) || may_alias_p (alias_tags[i], Y))
Yup, there's two more calls into may_alias_p which would have to
compute the base symbol and alias sets for X & Y inside a loop that
we have to execute anytime we find an alias between X & Y. [Note these
calls are effectively 3 levels deep in the overall loop nesting structure. ]
Clearly this is more useless work. So we propagate the pre-computed
base symbol and alias information for X & Y into find_alias_tag.
But we're still computing the base symbol and alias tag for each
member in the alias_tags array. And while that array is probably
relatively small, recall that we're at our 3rd level of loop nesting
so the effects are multiplied significantly. So rather than recompute
this invariant information for the alias tags over and over and over,
we compute it once and store it with the memory tags.
But wait, there's more (and you thought we were done... HA!).
If you look at may_access_global_mem the first thing it does is call
get_base_symbol on its argument. We do this inside the first and second
loop nesting levels. ARGGGH, more useless work. Luckily we've already
got the necessary information handy, so it's easy to propagate it down
into may_access_global_mem and avoid another ton of useless work.
I know this was long. But go back and re-read and look at how often
we repeated non-trivial computations -- worse yet we did so within an
algorithm that is inherently O(N^2).
These changes get the tree-ssa may alias code down from 755 seconds
to 459 (estimated) for a profiled compiler. For a non-profiled compiler
we go from 258 seconds down to 157 seconds (actual, not estimated).
There's further work to do, which should get us down in the range of
260 profiled and 130 non-profiled (similar stuff -- we're still doing
a lot of unnecessary get_base_symbol calls in this code).
Bootstrapped, regression tested.
* tree-dfa.c (struct alias_tags): New. Collector for key information
regarding alias tags.
(indirect_refs_base, indirect_refs_alias_set): New varrays.
(addressable_vars_base, addressable_vars_alias_set): Likewise.
(compute_may_aliases): Initialize and finalize the new varrays.
Update allocation of alias tags information.
(find_may_aliases_for): Extract base symbols and alias set
information for V1 and V2 from the virtual arrays and store
them into local variables. Pass them as necessary to
may_alias_p, may_access_global_mem, find_alias_tag. Add base
symbol and alias set when creating a new alias tag.
(find_vars_r): Fill in new varrays as needed.
(may_alias_p): Add new arguments for base and alias set of the
two origianl incoming arguments. No longer call get_base_symbol
or get_alias_set.
(find_alias_tag, may_access_global_mem): Similarly.
(add_stmt_operand): Update to pass additional argument to
may_access_global_mem.
(dump_alias_info): Update to deal with new alias tag structure.
* tree-flow.h (may_alias_p): Update prototype with new arguments.
* tree-ssa-pre.c (process_left_occs_and_kills): Update to pass
new arguments to may_alias_p.
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.66
diff -c -3 -p -r1.1.4.66 tree-dfa.c
*** tree-dfa.c 30 Jan 2003 17:53:33 -0000 1.1.4.66
--- tree-dfa.c 30 Jan 2003 18:39:05 -0000
*************** Boston, MA 02111-1307, USA. */
*** 45,52 ****
/* Build and maintain data flow information for trees. */
! /* Local declarations. */
! static tree *alias_tags;
static unsigned long num_alias_tags;
/* Counters used to display DFA and SSA statistics. */
--- 45,61 ----
/* Build and maintain data flow information for trees. */
! /* To avoid useless and repeated lookups, we cache the base symbol
! and the alias set for the alias tag within the alias tag structure
! itself. */
! struct alias_tags
! {
! tree alias_tags;
! tree base_symbol;
! HOST_WIDE_INT alias_set;
! };
!
! static struct alias_tags *alias_tags;
static unsigned long num_alias_tags;
/* Counters used to display DFA and SSA statistics. */
*************** static void collect_dfa_stats PARAMS ((
*** 84,91 ****
static tree collect_dfa_stats_r PARAMS ((tree *, int *, void *));
static tree clobber_vars_r PARAMS ((tree *, int *, void *));
static void find_may_aliases_for PARAMS ((int));
! static tree find_alias_tag PARAMS ((tree, tree));
! static bool may_access_global_mem PARAMS ((tree));
static void set_def PARAMS ((tree *, tree));
static void add_use PARAMS ((tree *, tree));
static void add_vdef PARAMS ((tree, tree, voperands_t));
--- 93,101 ----
static tree collect_dfa_stats_r PARAMS ((tree *, int *, void *));
static tree clobber_vars_r PARAMS ((tree *, int *, void *));
static void find_may_aliases_for PARAMS ((int));
! static tree find_alias_tag
! PARAMS ((tree, tree, HOST_WIDE_INT, tree, tree, HOST_WIDE_INT));
! static bool may_access_global_mem PARAMS ((tree, tree));
static void set_def PARAMS ((tree *, tree));
static void add_use PARAMS ((tree *, tree));
static void add_vdef PARAMS ((tree, tree, voperands_t));
*************** varray_type referenced_vars;
*** 109,122 ****
/* The total number of unique INDIRECT_REFs in the function. */
static unsigned long num_indirect_refs;
! /* Array of all the unique INDIRECT_REFs in the function. */
static varray_type indirect_refs;
/* The total number of unique addressable vars in the function. */
static unsigned long num_addressable_vars;
! /* Array of all the unique addressable vars in the function. */
static varray_type addressable_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
--- 119,146 ----
/* The total number of unique INDIRECT_REFs in the function. */
static unsigned long num_indirect_refs;
! /* Arrays for all the unique INDIRECT_REFs in the function.
!
! INDIRECT_REFS contains the canonical INDIRECT_REFs
! INDIRECT_REFS_BASE contains the base symbol for those refs
! INDIRECT_REFS_ALIAS_SET contains the alias set for this INDIRECT_REF. */
!
static varray_type indirect_refs;
+ static varray_type indirect_refs_base;
+ static varray_type indirect_refs_alias_set;
/* The total number of unique addressable vars in the function. */
static unsigned long num_addressable_vars;
! /* Arrays for all the unique addressable vars in the function.
!
! ADDRESSABLE_VARS contains the canonical addressable variable
! ADDRESSABLE_VARS_BASE contains the base symbol for those variables
! ADDRESSABLE_VARS_ALIAS_SET contains the alias set for this addressable
! variable. */
static varray_type addressable_vars;
+ static varray_type addressable_vars_base;
+ static varray_type addressable_vars_alias_set;
/* 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
*************** add_stmt_operand (var_p, stmt, is_def, f
*** 535,541 ****
point to global memory, then mark '*p' as an alias for
global memory. */
if (TREE_CODE (stmt) == MODIFY_EXPR
! && may_access_global_mem (TREE_OPERAND (stmt, 1)))
set_may_alias_global_mem (deref);
}
}
--- 559,566 ----
point to global memory, then mark '*p' as an alias for
global memory. */
if (TREE_CODE (stmt) == MODIFY_EXPR
! && may_access_global_mem (TREE_OPERAND (stmt, 1),
! get_base_symbol (TREE_OPERAND (stmt, 1))))
set_may_alias_global_mem (deref);
}
}
*************** compute_may_aliases ()
*** 1357,1365 ****
--- 1382,1394 ----
num_indirect_refs = 0;
VARRAY_TREE_INIT (indirect_refs, 20, "indirect_refs");
+ VARRAY_TREE_INIT (indirect_refs_base, 20, "indirect_refs_base");
+ VARRAY_WIDE_INT_INIT (indirect_refs_alias_set, 20,
"indirect_refs_alias_set");
num_addressable_vars = 0;
VARRAY_TREE_INIT (addressable_vars, 20, "addressable_vars");
+ VARRAY_TREE_INIT (addressable_vars_base, 20, "addressable_vars_base");
+ VARRAY_WIDE_INT_INIT (addressable_vars_alias_set, 20,
"addressable_vars_alias_set");
/* Hash table of all the objects the SSA builder needs to be aware of. */
vars_found = htab_create (50, htab_hash_var, htab_var_eq, NULL);
*************** compute_may_aliases ()
*** 1391,1403 ****
if (flag_tree_points_to == PTA_NONE)
{
num_alias_tags = 0;
! alias_tags = (tree *) xmalloc ((num_indirect_refs +
num_addressable_vars)
! * sizeof (tree));
! memset ((void *) alias_tags, 0,
! ((num_indirect_refs + num_addressable_vars) * sizeof (tree)));
}
!
for (i = 0; i < num_indirect_refs; i++)
find_may_aliases_for (i);
--- 1420,1433 ----
if (flag_tree_points_to == PTA_NONE)
{
+ size_t count = num_indirect_refs + num_addressable_vars;
+ size_t size = count * sizeof (struct alias_tags);
+
num_alias_tags = 0;
! alias_tags = (struct alias_tags *) xmalloc (size);
! memset ((void *) alias_tags, 0, size);
}
!
for (i = 0; i < num_indirect_refs; i++)
find_may_aliases_for (i);
*************** compute_may_aliases ()
*** 1413,1430 ****
num_indirect_refs = 0;
indirect_refs = 0;
num_addressable_vars = 0;
addressable_vars = 0;
timevar_pop (TV_TREE_MAY_ALIAS);
}
! /* Return TRUE if variables V1 and V2 may alias. */
bool
! may_alias_p (v1, v2)
tree v1;
tree v2;
{
tree ptr, var, ptr_sym, var_sym;
HOST_WIDE_INT ptr_alias_set, var_alias_set;
--- 1443,1473 ----
num_indirect_refs = 0;
indirect_refs = 0;
+ indirect_refs_base = 0;
+ indirect_refs_alias_set = 0;
num_addressable_vars = 0;
addressable_vars = 0;
+ addressable_vars_base = 0;
+ addressable_vars_alias_set = 0;
timevar_pop (TV_TREE_MAY_ALIAS);
}
! /* Return TRUE if variables V1 and V2 may alias.
!
! V1_BASE is the base symbol for V1
! V1_ALIAS_SET is the alias set for V1
! V2_BASE is the base symbol for V2
! V2_ALIAS_SET is the base symbol for V2. */
bool
! may_alias_p (v1, v1_base, v1_alias_set, v2, v2_base, v2_alias_set)
tree v1;
+ tree v1_base;
+ HOST_WIDE_INT v1_alias_set;
tree v2;
+ tree v2_base;
+ HOST_WIDE_INT v2_alias_set;
{
tree ptr, var, ptr_sym, var_sym;
HOST_WIDE_INT ptr_alias_set, var_alias_set;
*************** may_alias_p (v1, v2)
*** 1437,1455 ****
if (TREE_CODE (v1) == INDIRECT_REF || v1 == global_var)
{
ptr = v1;
var = v2;
}
else if (TREE_CODE (v2) == INDIRECT_REF || v2 == global_var)
{
ptr = v2;
var = v1;
}
else
return false;
- ptr_sym = get_base_symbol (ptr);
- var_sym = get_base_symbol (var);
-
/* 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
--- 1480,1503 ----
if (TREE_CODE (v1) == INDIRECT_REF || v1 == global_var)
{
ptr = v1;
+ ptr_sym = v1_base;
+ ptr_alias_set = v1_alias_set;
var = v2;
+ var_sym = v2_base;
+ var_alias_set = v2_alias_set;
}
else if (TREE_CODE (v2) == INDIRECT_REF || v2 == global_var)
{
ptr = v2;
+ ptr_sym = v2_base;
+ ptr_alias_set = v2_alias_set;
var = v1;
+ var_sym = v1_base;
+ var_alias_set = 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
*************** may_alias_p (v1, v2)
*** 1482,1491 ****
if (DECL_P (var) && !TREE_ADDRESSABLE (var))
return false;
! /* Compute type-based alias information. If the alias sets don't
! conflict then PTR cannot alias VAR. */
! ptr_alias_set = get_alias_set (ptr);
! var_alias_set = get_alias_set (var);
if (!alias_sets_conflict_p (ptr_alias_set, var_alias_set))
return false;
--- 1530,1536 ----
if (DECL_P (var) && !TREE_ADDRESSABLE (var))
return false;
! /* If the alias sets don't conflict then PTR cannot alias VAR. */
if (!alias_sets_conflict_p (ptr_alias_set, var_alias_set))
return false;
*************** may_alias_p (v1, v2)
*** 1497,1503 ****
return true;
}
-
/* Find variables that may be aliased by the variable (V1) at
index VAR_INDEX in the alias_vars varray.
--- 1542,1547 ----
*************** find_may_aliases_for (indirect_ref_index
*** 1519,1531 ****
{
unsigned long i;
tree v1 = VARRAY_TREE (indirect_refs, indirect_ref_index);
#if defined ENABLE_CHECKING
if (TREE_CODE (v1) != INDIRECT_REF)
abort ();
#endif
! if (may_access_global_mem (v1))
set_may_alias_global_mem (v1);
/* Note that our aliasing properties are symmetric, so we can
--- 1563,1578 ----
{
unsigned long i;
tree v1 = VARRAY_TREE (indirect_refs, indirect_ref_index);
+ tree v1_base = VARRAY_TREE (indirect_refs_base, indirect_ref_index);
+ HOST_WIDE_INT v1_alias_set
+ = VARRAY_INT (indirect_refs_alias_set, indirect_ref_index);
#if defined ENABLE_CHECKING
if (TREE_CODE (v1) != INDIRECT_REF)
abort ();
#endif
! if (may_access_global_mem (v1, v1_base))
set_may_alias_global_mem (v1);
/* Note that our aliasing properties are symmetric, so we can
*************** find_may_aliases_for (indirect_ref_index
*** 1534,1544 ****
for (i = indirect_ref_index; i < num_indirect_refs; i++)
{
tree v2 = VARRAY_TREE (indirect_refs, i);
if (v1 == v2)
continue;
! if (may_alias_p (v1, v2))
{
tree at;
--- 1581,1593 ----
for (i = indirect_ref_index; i < num_indirect_refs; i++)
{
tree v2 = VARRAY_TREE (indirect_refs, i);
+ tree v2_base = VARRAY_TREE (indirect_refs_base, i);
+ HOST_WIDE_INT v2_alias_set = VARRAY_INT (indirect_refs_alias_set, i);
if (v1 == v2)
continue;
! if (may_alias_p (v1, v1_base, v1_alias_set, v2, v2_base, v2_alias_set))
{
tree at;
*************** find_may_aliases_for (indirect_ref_index
*** 1548,1556 ****
all the aliases into a single representative alias that
represents a group of variables with similar aliasing
characteristics. */
! at = find_alias_tag (v1, v2);
if (at == NULL_TREE)
! at = alias_tags [num_alias_tags++] = v1;
add_may_alias (v2, at);
}
else
--- 1597,1612 ----
all the aliases into a single representative alias that
represents a group of variables with similar aliasing
characteristics. */
! at = find_alias_tag (v1, v1_base, v1_alias_set,
! v2, v2_base, v2_alias_set);
if (at == NULL_TREE)
! {
! at = v1;
! alias_tags [num_alias_tags].alias_tags = v1;
! alias_tags [num_alias_tags].base_symbol = v1_base;
! alias_tags [num_alias_tags].alias_set = v1_alias_set;
! num_alias_tags++;
! }
add_may_alias (v2, at);
}
else
*************** find_may_aliases_for (indirect_ref_index
*** 1565,1571 ****
/* If V2 may access global memory, mark both AT and V1 as aliases
for global memory. */
! if (may_access_global_mem (v2))
{
set_may_alias_global_mem (at);
set_may_alias_global_mem (v1);
--- 1621,1627 ----
/* If V2 may access global memory, mark both AT and V1 as aliases
for global memory. */
! if (may_access_global_mem (v2, v2_base))
{
set_may_alias_global_mem (at);
set_may_alias_global_mem (v1);
*************** find_may_aliases_for (indirect_ref_index
*** 1576,1586 ****
for (i = 0; i < num_addressable_vars; i++)
{
tree v2 = VARRAY_TREE (addressable_vars, i);
if (v1 == v2)
continue;
! if (may_alias_p (v1, v2))
{
tree at;
--- 1632,1644 ----
for (i = 0; i < num_addressable_vars; i++)
{
tree v2 = VARRAY_TREE (addressable_vars, i);
+ tree v2_base = VARRAY_TREE (addressable_vars_base, i);
+ HOST_WIDE_INT v2_alias_set = VARRAY_INT (addressable_vars_alias_set,
i);
if (v1 == v2)
continue;
! if (may_alias_p (v1, v1_base, v1_alias_set, v2, v2_base, v2_alias_set))
{
tree at;
*************** find_may_aliases_for (indirect_ref_index
*** 1590,1598 ****
all the aliases into a single representative alias that
represents a group of variables with similar aliasing
characteristics. */
! at = find_alias_tag (v1, v2);
if (at == NULL_TREE)
! at = alias_tags [num_alias_tags++] = v1;
add_may_alias (v2, at);
}
else
--- 1648,1663 ----
all the aliases into a single representative alias that
represents a group of variables with similar aliasing
characteristics. */
! at = find_alias_tag (v1, v1_base, v1_alias_set,
! v2, v2_base, v2_alias_set);
if (at == NULL_TREE)
! {
! at = v1;
! alias_tags [num_alias_tags].alias_tags = v1;
! alias_tags [num_alias_tags].base_symbol = v1_base;
! alias_tags [num_alias_tags].alias_set = v1_alias_set;
! num_alias_tags++;
! }
add_may_alias (v2, at);
}
else
*************** find_may_aliases_for (indirect_ref_index
*** 1607,1613 ****
/* If V2 may access global memory, mark both AT and V1 as aliases
for global memory. */
! if (may_access_global_mem (v2))
{
set_may_alias_global_mem (at);
set_may_alias_global_mem (v1);
--- 1672,1678 ----
/* If V2 may access global memory, mark both AT and V1 as aliases
for global memory. */
! if (may_access_global_mem (v2, v2_base))
{
set_may_alias_global_mem (at);
set_may_alias_global_mem (v1);
*************** add_may_alias (var, alias)
*** 1643,1662 ****
/* Traverse the ALIAS_TAGS array looking for an alias tag that may alias
! variable V1 or V2. If no entry is found for either V1 or V2, return
! NULL_TREE to tell the caller that it should create a new entry in the
! ALIAS_TAG array. */
static tree
! find_alias_tag (v1, v2)
tree v1;
tree v2;
{
unsigned long i;
for (i = 0; i < num_alias_tags; i++)
! if (may_alias_p (alias_tags[i], v1) || may_alias_p (alias_tags[i], v2))
! return alias_tags[i];
return NULL_TREE;
}
--- 1708,1743 ----
/* Traverse the ALIAS_TAGS array looking for an alias tag that may alias
! variable V1 or V2. The caller also provides the base symbol and
! alias set V1 and V2 in V1_BASE, V2_BASE, V1_ALIAS_SET and V2_ALIAS_SET.
!
!
! If no entry is found for either V1 or V2, return NULL_TREE to tell the
! caller that it should create a new entry in the ALIAS_TAG array. */
static tree
! find_alias_tag (v1, v1_base, v1_alias_set, v2, v2_base, v2_alias_set)
tree v1;
+ tree v1_base;
+ HOST_WIDE_INT v1_alias_set;
tree v2;
+ tree v2_base;
+ HOST_WIDE_INT v2_alias_set;
{
unsigned long i;
for (i = 0; i < num_alias_tags; i++)
! {
! if (may_alias_p (alias_tags[i].alias_tags,
! alias_tags[i].base_symbol,
! alias_tags[i].alias_set,
! v1, v1_base, v1_alias_set)
! || may_alias_p (alias_tags[i].alias_tags,
! alias_tags[i].base_symbol,
! alias_tags[i].alias_set,
! v2, v2_base, v2_alias_set))
! return alias_tags[i].alias_tags;
! }
return NULL_TREE;
}
*************** dump_alias_info (file)
*** 1677,1690 ****
{
fprintf (file, "Alias set #%ld:\n", i);
fprintf (file, " Tag: ");
! dump_variable (file, alias_tags[i]);
fprintf (file, " Aliases: { ");
for (j = 0; j < num_addressable_vars; j++)
{
tree var = VARRAY_TREE (addressable_vars, j);
varray_type aliases = may_aliases (var);
! if (aliases && VARRAY_TREE (aliases, 0) == alias_tags[i])
{
print_generic_expr (file, var, 0);
fprintf (file, " ");
--- 1758,1771 ----
{
fprintf (file, "Alias set #%ld:\n", i);
fprintf (file, " Tag: ");
! dump_variable (file, alias_tags[i].alias_tags);
fprintf (file, " Aliases: { ");
for (j = 0; j < num_addressable_vars; j++)
{
tree var = VARRAY_TREE (addressable_vars, j);
varray_type aliases = may_aliases (var);
! if (aliases && VARRAY_TREE (aliases, 0) == alias_tags[i].alias_tags)
{
print_generic_expr (file, var, 0);
fprintf (file, " ");
*************** dump_alias_info (file)
*** 1695,1701 ****
{
tree var = VARRAY_TREE (indirect_refs, j);
varray_type aliases = may_aliases (var);
! if (aliases && VARRAY_TREE (aliases, 0) == alias_tags[i])
{
print_generic_expr (file, var, 0);
fprintf (file, " ");
--- 1776,1782 ----
{
tree var = VARRAY_TREE (indirect_refs, j);
varray_type aliases = may_aliases (var);
! if (aliases && VARRAY_TREE (aliases, 0) == alias_tags[i].alias_tags)
{
print_generic_expr (file, var, 0);
fprintf (file, " ");
*************** debug_alias_info ()
*** 1722,1741 ****
/* Return TRUE if expression EXPR may return a pointer to global memory. */
static bool
! may_access_global_mem (expr)
tree expr;
{
char class;
- tree sym;
if (expr == NULL_TREE)
return false;
/* Function arguments and global variables may reference global memory. */
! if ((sym = get_base_symbol (expr)) != NULL_TREE)
{
! if (TREE_CODE (sym) == PARM_DECL
! || decl_function_context (sym) == NULL_TREE)
return true;
}
--- 1803,1822 ----
/* Return TRUE if expression EXPR may return a pointer to global memory. */
static bool
! may_access_global_mem (expr, expr_base)
tree expr;
+ tree expr_base;
{
char class;
if (expr == NULL_TREE)
return false;
/* Function arguments and global variables may reference global memory. */
! if (expr_base != NULL_TREE)
{
! if (TREE_CODE (expr_base) == PARM_DECL
! || decl_function_context (expr_base) == NULL_TREE)
return true;
}
*************** may_access_global_mem (expr)
*** 1755,1761 ****
unsigned char i;
for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (expr)); i++)
! if (may_access_global_mem (TREE_OPERAND (expr, i)))
return true;
}
--- 1836,1843 ----
unsigned char i;
for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (expr)); i++)
! if (may_access_global_mem (TREE_OPERAND (expr, i),
! get_base_symbol (TREE_OPERAND (expr, i))))
return true;
}
*************** find_vars_r (tp, walk_subtrees, data)
*** 1860,1866 ****
/* Get the underlying symbol. We will need it shortly. */
if (TREE_CODE (var) == INDIRECT_REF)
{
! sym = get_base_symbol (var);
ind = var;
if (!is_dereferenced (sym))
--- 1942,1948 ----
/* Get the underlying symbol. We will need it shortly. */
if (TREE_CODE (var) == INDIRECT_REF)
{
! sym = get_base_symbol (TREE_OPERAND (var, 0));
ind = var;
if (!is_dereferenced (sym))
*************** find_vars_r (tp, walk_subtrees, data)
*** 1870,1881 ****
}
else
{
ind = NULL_TREE;
- sym = var;
}
/* Make VAR either the canonical INDIRECT_REF or the real symbol. */
! var = (ind ? ind : sym);
/* First handle an INDIRECT_REF. */
if (ind)
--- 1952,1963 ----
}
else
{
+ sym = get_base_symbol (var);
ind = NULL_TREE;
}
/* Make VAR either the canonical INDIRECT_REF or the real symbol. */
! var = (ind ? ind : var);
/* First handle an INDIRECT_REF. */
if (ind)
*************** find_vars_r (tp, walk_subtrees, data)
*** 1885,1890 ****
--- 1967,1974 ----
{
*slot = (void *)var;
VARRAY_PUSH_TREE (indirect_refs, var);
+ VARRAY_PUSH_TREE (indirect_refs_base, sym);
+ VARRAY_PUSH_INT (indirect_refs_alias_set, get_alias_set (var));
num_indirect_refs++;
}
*************** find_vars_r (tp, walk_subtrees, data)
*** 1898,1903 ****
--- 1982,1990 ----
{
*slot = (void *)var;
VARRAY_PUSH_TREE (addressable_vars, var);
+ VARRAY_PUSH_TREE (addressable_vars_base, sym);
+ VARRAY_PUSH_INT (addressable_vars_alias_set,
+ get_alias_set (var));
num_addressable_vars++;
}
}
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.46
diff -c -3 -p -r1.1.4.46 tree-flow.h
*** tree-flow.h 30 Jan 2003 17:53:33 -0000 1.1.4.46
--- tree-flow.h 30 Jan 2003 18:39:07 -0000
*************** extern void debug_immediate_uses_for PAR
*** 331,337 ****
extern void remove_decl PARAMS ((tree));
extern tree *find_decl_location PARAMS ((tree, tree));
extern void compute_may_aliases PARAMS ((void));
! extern bool may_alias_p PARAMS ((tree, tree));
extern void compute_reached_uses PARAMS ((int));
extern void compute_immediate_uses PARAMS ((int));
extern void compute_reaching_defs PARAMS ((int));
--- 331,338 ----
extern void remove_decl PARAMS ((tree));
extern tree *find_decl_location PARAMS ((tree, tree));
extern void compute_may_aliases PARAMS ((void));
! extern bool may_alias_p PARAMS ((tree, tree, HOST_WIDE_INT,
! tree, tree, HOST_WIDE_INT));
extern void compute_reached_uses PARAMS ((int));
extern void compute_immediate_uses PARAMS ((int));
extern void compute_reaching_defs PARAMS ((int));
Index: tree-ssa-pre.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-pre.c,v
retrieving revision 1.1.4.46
diff -c -3 -p -r1.1.4.46 tree-ssa-pre.c
*** tree-ssa-pre.c 16 Jan 2003 16:03:59 -0000 1.1.4.46
--- tree-ssa-pre.c 30 Jan 2003 18:39:10 -0000
*************** process_left_occs_and_kills (bexprs, slo
*** 2806,2811 ****
--- 2806,2814 ----
}
if (DECL_P (TREE_OPERAND (expr, 0)))
{
+ tree op0_base = get_base_symbol (TREE_OPERAND (expr, 0));
+ HOST_WIDE_INT op0_alias_set = get_alias_set (TREE_OPERAND (expr, 0));
+
for (k = 0; k < VARRAY_ACTIVE_SIZE (bexprs); k++)
{
tree op;
*************** process_left_occs_and_kills (bexprs, slo
*** 2819,2825 ****
? indirect_var (get_base_symbol (ei->expr)) : NULL;
/* : component_ref (ei->expr, get_component_ref_index (ei->expr)); */
! if (may_alias_p (op, TREE_OPERAND (expr, 0))
|| op == TREE_OPERAND (expr, 0))
{
add_left_occ (ei, ref->common.stmt_p);
--- 2822,2833 ----
? indirect_var (get_base_symbol (ei->expr)) : NULL;
/* : component_ref (ei->expr, get_component_ref_index (ei->expr)); */
! if (may_alias_p (op,
! get_base_symbol (op),
! get_alias_set (op),
! TREE_OPERAND (expr, 0),
! op0_base,
! op0_alias_set)
|| op == TREE_OPERAND (expr, 0))
{
add_left_occ (ei, ref->common.stmt_p);
*************** process_left_occs_and_kills (bexprs, slo
*** 2827,2833 ****
}
else if (DECL_P (ei->expr))
{
! if (may_alias_p (ei->expr, TREE_OPERAND (expr, 0))
|| ei->expr == TREE_OPERAND (expr, 0))
{
add_left_occ (ei, ref->common.stmt_p);
--- 2835,2846 ----
}
else if (DECL_P (ei->expr))
{
! if (may_alias_p (ei->expr,
! get_base_symbol (ei->expr),
! get_alias_set (ei->expr),
! TREE_OPERAND (expr, 0),
! op0_base,
! op0_alias_set)
|| ei->expr == TREE_OPERAND (expr, 0))
{
add_left_occ (ei, ref->common.stmt_p);
*************** process_left_occs_and_kills (bexprs, slo
*** 2851,2857 ****
? indirect_var (get_base_symbol (ei->expr)) : NULL;
/*: component_ref (ei->expr, get_component_ref_index (ei->expr));*/
op2 = indirect_var (get_base_symbol (TREE_OPERAND (expr, 0)));
! if (may_alias_p (op1, op2) || op1 == op2)
{
add_left_occ (ei, ref->common.stmt_p);
}
--- 2864,2876 ----
? indirect_var (get_base_symbol (ei->expr)) : NULL;
/*: component_ref (ei->expr, get_component_ref_index (ei->expr));*/
op2 = indirect_var (get_base_symbol (TREE_OPERAND (expr, 0)));
! if (may_alias_p (op1,
! get_base_symbol (op1),
! get_alias_set (op1),
! op2,
! get_base_symbol (op2),
! get_alias_set (op2))
! || op1 == op2)
{
add_left_occ (ei, ref->common.stmt_p);
}
*************** process_left_occs_and_kills (bexprs, slo
*** 2859,2865 ****
else if (DECL_P (ei->expr))
{
tree op2 = indirect_var (get_base_symbol (TREE_OPERAND (expr, 0)));
! if (may_alias_p (ei->expr, op2))
{
add_left_occ (ei, ref->common.stmt_p);
}
--- 2878,2889 ----
else if (DECL_P (ei->expr))
{
tree op2 = indirect_var (get_base_symbol (TREE_OPERAND (expr, 0)));
! if (may_alias_p (ei->expr,
! get_base_symbol (ei->expr),
! get_alias_set (ei->expr),
! op2,
! get_base_symbol (op2),
! get_alias_set (op2))
{
add_left_occ (ei, ref->common.stmt_p);
}
*************** process_left_occs_and_kills (bexprs, slo
*** 2883,2889 ****
/* : component_ref (ei->expr, get_component_ref_index (ei->expr));*/
op2 = TREE_OPERAND (expr, 0);
/* op2 = component_ref (op2, get_component_ref_index (op2));*/
! if (may_alias_p (op1, op2) || op1 == op2)
{
add_left_occ (ei, ref->common.stmt_p);
}
--- 2907,2919 ----
/* : component_ref (ei->expr, get_component_ref_index (ei->expr));*/
op2 = TREE_OPERAND (expr, 0);
/* op2 = component_ref (op2, get_component_ref_index (op2));*/
! if (may_alias_p (op1,
! get_base_symbol (op1),
! get_alias_set (op1),
! op2,
! get_base_symbol (op2),
! get_alias_set (op2))
! || op1 == op2)
{
add_left_occ (ei, ref->common.stmt_p);
}
*************** process_left_occs_and_kills (bexprs, slo
*** 2892,2898 ****
{
tree op2 = TREE_OPERAND (expr, 0);
/* op2 = component_ref (op2, get_component_ref_index (op2));*/
! if (may_alias_p (ei->expr, op2))
{
add_left_occ (ei, ref->common.stmt_p);
}
--- 2922,2933 ----
{
tree op2 = TREE_OPERAND (expr, 0);
/* op2 = component_ref (op2, get_component_ref_index (op2));*/
! if (may_alias_p (ei->expr,
! get_base_symbol (ei->expr),
! get_alias_set (ei->expr),
! op2,
! get_base_symbol (op2),
! get_alias_set (op2))
{
add_left_occ (ei, ref->common.stmt_p);
}
More information about the Gcc-patches
mailing list