This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH]: Teach aliasers to use ipa type escape analysis results
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: Kenneth Zadeck <zadeck at naturalbridge dot com>, GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Wed, 08 Jun 2005 13:58:49 -0400
- Subject: [PATCH]: Teach aliasers to use ipa type escape analysis results
Patch 5/7
This patch adds code to the RTL and tree aliasers to be able to use the
results of type escape analysis.
Bootstrapped and regtested on i686-pc-linux-gnu and powerpc-linux-gnu.
Okay for mainline?
2005-06-06 Kenneth Zadeck <zadeck@naturalbridge.com>
Danny Berlin <dberlin@dberlin.org>
* alias.c (nonoverlapping_component_refs_p): Added calls to support
type based aliasing.
* tree-ssa-alias.c (may_alias_p, compute_flow_insensitive_aliasing):
Ditto.
* tree-ssa-alias.c (dump_alias_stats): Added stats for type based
aliasing.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1496
diff -u -p -r1.1496 Makefile.in
--- Makefile.in 4 Jun 2005 17:07:50 -0000 1.1496
+++ Makefile.in 6 Jun 2005 21:39:26 -0000
@@ -1835,7 +1840,7 @@ tree-ssa-alias.o : tree-ssa-alias.c $(TR
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) tree-inline.h $(FLAGS_H) \
function.h $(TIMEVAR_H) convert.h $(TM_H) coretypes.h langhooks.h \
$(TREE_DUMP_H) tree-pass.h $(PARAMS_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) \
- hard-reg-set.h $(TREE_GIMPLE_H) vec.h
+ hard-reg-set.h $(TREE_GIMPLE_H) vec.h $(IPA_TYPE_ESCAPE_H)
tree-optimize.o : tree-optimize.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h $(DIAGNOSTIC_H) \
$(FLAGS_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) toplev.h \
@@ -2269,7 +2293,7 @@ alias.o : alias.c $(CONFIG_H) $(SYSTEM_H
$(FLAGS_H) hard-reg-set.h $(BASIC_BLOCK_H) $(REGS_H) toplev.h output.h \
$(ALIAS_H) $(EMIT_RTL_H) $(GGC_H) function.h cselib.h $(TREE_H) $(TM_P_H) \
langhooks.h $(TARGET_H) gt-alias.h $(TIMEVAR_H) $(CGRAPH_H) \
- $(SPLAY_TREE_H) $(VARRAY_H)
+ $(SPLAY_TREE_H) $(VARRAY_H) $(IPA_TYPE_ESCAPE_H)
regmove.o : regmove.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) insn-config.h \
$(RECOG_H) output.h $(REGS_H) hard-reg-set.h $(FLAGS_H) function.h \
$(EXPR_H) $(BASIC_BLOCK_H) toplev.h $(TM_P_H) except.h reload.h
Index: alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/alias.c,v
retrieving revision 1.250
diff -u -p -r1.250 alias.c
--- alias.c 21 Apr 2005 15:47:04 -0000 1.250
+++ alias.c 6 Jun 2005 21:39:27 -0000
@@ -44,6 +44,55 @@ Software Foundation, 59 Temple Place - S
#include "target.h"
#include "cgraph.h"
#include "varray.h"
+#include "ipa-type-escape.h"
+
+/* The aliasing API provided here solves related but different problems:
+
+ Say there exists (in c)
+
+ struct X {
+ struct Y y1;
+ struct Z z2;
+ } x1, *px1, *px2;
+
+ struct Y y2, *py;
+ struct Z z2, *pz;
+
+
+ py = &px1.y1;
+ px2 = &x1;
+
+ Consider the four questions:
+
+ Can a store to x1 interfere with px2->y2?
+ Can a store to x1 interfere with px2->z2?
+ (*px2).z2
+ Can a store to x1 change the value pointed to by with py?
+ Can a store to x1 change the value pointed to by with pz?
+
+ The answer to these questions can be yes, yes, yes, and no.
+
+ The first two questions can be answered with a simple examination
+ of the type system. If structure X contains a field of type Y then
+ a store thru a pointer to an X can overwrite any field that is
+ contained (recursively) in an X (unless we know that px1 != px2).
+
+ The last two of the questions can be solved in the same way as the
+ first two questions but this is too conservative. The observation
+ is that if the address of a field is not explicitly taken and the
+ type is completely local to the compilation unit, then it is
+ impossible that a pointer to an instance of the field type overlaps
+ with an enclosing structure.
+
+ Historically in GCC, these two problems were combined and a single
+ data structure was used to represent the solution to these
+ problems. We now have two similar but different data structures,
+ The data structure to solve the last two question is similar to the
+ first, but does not contain have the fields in it whose address are
+ never taken. For types that do escape the compilation unit, the
+ data structures will have identical information.
+
+*/
/* The alias sets assigned to MEMs assist the back-end in determining
which MEMs can alias which other MEMs. In general, two MEMs in
@@ -1889,6 +1932,7 @@ aliases_everything_p (rtx mem)
return 0;
}
+/*#define AGRESSIVE_ALIASING 1*/
/* Return true if we can determine that the fields referenced cannot
overlap for any pair of objects. */
@@ -1923,9 +1967,12 @@ nonoverlapping_component_refs_p (tree x,
x = TREE_OPERAND (x, 0);
}
while (x && TREE_CODE (x) == COMPONENT_REF);
-
/* Never found a common type. */
+#ifdef AGRESSIVE_ALIASING
+ return true;
+#else
return false;
+#endif /* AGRESSIVE_ALIASING */
found:
/* If we're left with accessing different fields of a structure,
@@ -2005,22 +2052,36 @@ nonoverlapping_memrefs_p (rtx x, rtx y)
/* Unless both have exprs, we can't tell anything. */
if (exprx == 0 || expry == 0)
return 0;
-
+
/* If both are field references, we may be able to determine something. */
if (TREE_CODE (exprx) == COMPONENT_REF
&& TREE_CODE (expry) == COMPONENT_REF
&& nonoverlapping_component_refs_p (exprx, expry))
return 1;
+
/* If the field reference test failed, look at the DECLs involved. */
moffsetx = MEM_OFFSET (x);
if (TREE_CODE (exprx) == COMPONENT_REF)
{
- tree t = decl_for_component_ref (exprx);
- if (! t)
- return 0;
- moffsetx = adjust_offset_for_component_ref (exprx, moffsetx);
- exprx = t;
+#ifdef AGRESSIVE_ALIASING
+ if (TREE_CODE (expry) == VAR_DECL
+ && POINTER_TYPE_P (TREE_TYPE (expry)))
+ {
+ tree field = TREE_OPERAND (exprx, 1);
+ tree fieldcontext = DECL_FIELD_CONTEXT (field);
+ if (ipa_type_escape_field_does_not_clobber_p (fieldcontext,
+ TREE_TYPE (field)))
+ return 1;
+ }
+#endif /* AGRESSIVE_ALIASING */
+ {
+ tree t = decl_for_component_ref (exprx);
+ if (! t)
+ return 0;
+ moffsetx = adjust_offset_for_component_ref (exprx, moffsetx);
+ exprx = t;
+ }
}
else if (INDIRECT_REF_P (exprx))
{
@@ -2033,11 +2094,24 @@ nonoverlapping_memrefs_p (rtx x, rtx y)
moffsety = MEM_OFFSET (y);
if (TREE_CODE (expry) == COMPONENT_REF)
{
- tree t = decl_for_component_ref (expry);
- if (! t)
- return 0;
- moffsety = adjust_offset_for_component_ref (expry, moffsety);
- expry = t;
+#ifdef AGRESSIVE_ALIASING
+ if (TREE_CODE (exprx) == VAR_DECL
+ && POINTER_TYPE_P (TREE_TYPE (exprx)))
+ {
+ tree field = TREE_OPERAND (expry, 1);
+ tree fieldcontext = DECL_FIELD_CONTEXT (field);
+ if (ipa_type_escape_field_does_not_clobber_p (fieldcontext,
+ TREE_TYPE (field)))
+ return 1;
+ }
+#endif /* AGRESSIVE_ALIASING */
+ {
+ tree t = decl_for_component_ref (expry);
+ if (! t)
+ return 0;
+ moffsety = adjust_offset_for_component_ref (expry, moffsety);
+ expry = t;
+ }
}
else if (INDIRECT_REF_P (expry))
{
Index: tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-alias.c,v
retrieving revision 2.93
diff -u -p -r2.93 tree-ssa-alias.c
--- tree-ssa-alias.c 29 May 2005 13:14:42 -0000 2.93
+++ tree-ssa-alias.c 6 Jun 2005 21:39:35 -0000
@@ -42,6 +42,7 @@ Boston, MA 02111-1307, USA. */
#include "tree-pass.h"
#include "convert.h"
#include "params.h"
+#include "ipa-type-escape.h"
#include "vec.h"
/* 'true' after aliases have been computed (see compute_may_aliases). */
@@ -130,6 +131,8 @@ struct alias_stats_d
unsigned int simple_resolved;
unsigned int tbaa_queries;
unsigned int tbaa_resolved;
+ unsigned int structnoaddress_queries;
+ unsigned int structnoaddress_resolved;
};
@@ -139,7 +142,7 @@ static struct alias_stats_d alias_stats;
/* Local functions. */
static void compute_flow_insensitive_aliasing (struct alias_info *);
static void dump_alias_stats (FILE *);
-static bool may_alias_p (tree, HOST_WIDE_INT, tree, HOST_WIDE_INT);
+static bool may_alias_p (tree, HOST_WIDE_INT, tree, HOST_WIDE_INT, bool);
static tree create_memory_tag (tree type, bool is_type_tag);
static tree get_tmt_for (tree, struct alias_info *);
static tree get_nmt_for (tree);
@@ -396,6 +399,7 @@ count_ptr_derefs (tree *tp, int *walk_su
struct count_ptr_d *count_p = (struct count_ptr_d *) data;
if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr)
+/* || (TREE_CODE (*tp) == MEM_REF && MEM_REF_SYMBOL (*tp) == count_p->ptr)) */
count_p->count++;
return NULL_TREE;
@@ -483,7 +487,6 @@ count_uses_and_derefs (tree ptr, tree st
gcc_assert (*num_uses_p >= *num_derefs_p);
}
-
/* Initialize the data structures used for alias analysis. */
static struct alias_info *
@@ -981,8 +984,8 @@ compute_flow_insensitive_aliasing (struc
|| bitmap_bit_p (ai->written_vars, v_ann->uid);
if (!tag_stored_p && !var_stored_p)
continue;
-
- if (may_alias_p (p_map->var, p_map->set, var, v_map->set))
+
+ if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false))
{
subvar_t svars;
size_t num_tag_refs, num_var_refs;
@@ -1063,7 +1066,7 @@ compute_flow_insensitive_aliasing (struc
sbitmap may_aliases2 = p_map2->may_aliases;
/* If the pointers may not point to each other, do nothing. */
- if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set))
+ if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true))
continue;
/* The two pointers may alias each other. If they already have
@@ -1669,7 +1672,8 @@ maybe_create_global_var (struct alias_in
static bool
may_alias_p (tree ptr, HOST_WIDE_INT mem_alias_set,
- tree var, HOST_WIDE_INT var_alias_set)
+ tree var, HOST_WIDE_INT var_alias_set,
+ bool alias_set_only)
{
tree mem;
var_ann_t m_ann;
@@ -1736,6 +1740,65 @@ may_alias_p (tree ptr, HOST_WIDE_INT mem
alias_stats.tbaa_resolved++;
return false;
}
+
+ /* If var is a record or union type, ptr cannot point into var
+ unless there is some operation explicit address operation in the
+ program that can reference a field of the ptr's dereferenced
+ type. This also assumes that the types of both var and ptr are
+ contained within the compilation unit, and that there is no fancy
+ addressing arithmetic associated with any of the types
+ involved. */
+
+ if ((mem_alias_set != 0) && (var_alias_set != 0))
+ {
+ tree ptr_type = TREE_TYPE (ptr);
+ tree var_type = TREE_TYPE (var);
+
+ /* The star count is -1 if the type at the end of the pointer_to
+ chain is not a record or union type. */
+ if ((!alias_set_only) &&
+ ipa_type_escape_star_count_of_interesting_type (var_type) >= 0)
+ {
+ int ptr_star_count = 0;
+
+ /* Ipa_type_escape_star_count_of_interesting_type is a little to
+ restrictive for the pointer type, need to allow pointers to
+ primitive types as long as those types cannot be pointers
+ to everything. */
+ while (POINTER_TYPE_P (ptr_type))
+ /* Strip the *'s off. */
+ {
+ ptr_type = TREE_TYPE (ptr_type);
+ ptr_star_count++;
+ }
+
+ /* There does not appear to be a better test to see if the
+ pointer type was one of the pointer to everything
+ types. */
+
+ if (ptr_star_count > 0)
+ {
+ alias_stats.structnoaddress_queries++;
+ if (ipa_type_escape_field_does_not_clobber_p (var_type,
+ TREE_TYPE (ptr)))
+ {
+ alias_stats.structnoaddress_resolved++;
+ alias_stats.alias_noalias++;
+ return false;
+ }
+ }
+ else if (ptr_star_count == 0)
+ {
+ /* If ptr_type was not really a pointer to type, it cannot
+ alias. */
+ alias_stats.structnoaddress_queries++;
+ alias_stats.structnoaddress_resolved++;
+ alias_stats.alias_noalias++;
+ return false;
+ }
+ }
+ }
+
alias_stats.alias_mayalias++;
return true;
}
@@ -2397,6 +2471,10 @@ dump_alias_stats (FILE *file)
alias_stats.tbaa_queries);
fprintf (file, "Total TBAA resolved:\t%u\n",
alias_stats.tbaa_resolved);
+ fprintf (file, "Total non-addressable structure type queries:\t%u\n",
+ alias_stats.structnoaddress_queries);
+ fprintf (file, "Total non-addressable structure type resolved:\t%u\n",
+ alias_stats.structnoaddress_resolved);
}