This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Track pure function call uses separately
On Fri, 27 Jun 2008, Richard Guenther wrote:
On Thu, 26 Jun 2008, Daniel Berlin wrote:
On Thu, Jun 26, 2008 at 12:34 PM, Richard Guenther <rguenther@suse.de>
wrote:
This adds the ability (on top of
http://gcc.gnu.org/ml/gcc-patches/2008-06/msg01432.html - PING for that)
I thought I okayed that one on IRC.
I will do so explicitly in a moment.
We have one "little" problem. If we re-enable field-sensitive PTA
then the transitive closure we use for computing the ESCAPED set
is no longer equivalent to the reachability, which we really need
to compute. Consider
struct Foo {
int *p;
int *q;
};
void __attribute__((noinline))
bar (int **x)
{
struct Foo *f = (struct Foo *)x;
*(f->q) = 0;
}
int foo(void)
{
struct Foo f;
int i = 1, j = 2;
f.p = &i;
f.q = &j;
bar(&f.p);
return j;
}
extern void abort (void);
int main()
{
if (foo () != 0)
abort ();
}
where in foo we end up with
ESCAPED = *ESCAPED
derefaddrtmp.30 = &ESCAPED
*ESCAPED = derefaddrtmp.30
derefaddrtmp.31 = &NONLOCAL
*ESCAPED = derefaddrtmp.31
f = &i
f.q = &j
ESCAPED = &f
and the solution
ESCAPED = { ESCAPED NONLOCAL f i }
f = { ESCAPED NONLOCAL i }
f.q = { j }
while f.q and j should also be escaped and f.q pointing to
ESCAPED NONLOCAL as well.
So what we would need here is a special deref constraint that
dereferences all subvars and use that for the ESCAPED = *ESCAPED
constraint. Where can this be implemented? I guess the solver
itself doesn't know about subvariables, but at constraint generation
time we cannot fix this either. Computing the reachability after
PTA does also not work because then the PTA results would be wrong
again.
Ideas? It looks like we would need to add constraints on-the-fly
during solving - is this possible at all? (can you hint me at
where I would need to add those?)
Ok, I have it "working" with something like the following.
Basically we need to treat 'reachability vars' specially, for
ESCAPED this is constraints of the form
ESCAPED = x
(in the solution propagation propagate using set_union_all_fields)
ESCAPED = &x
initially add all fields of x to ESCAPED. Probably better done by
collapsing x - the solution of x will get all of ESCAPED through
the *ESCAPED = ESCAPED constraint anyway, so no point in processing
the fields of x separately. (Ideally we would collapse during
solving, but that doesn't look easily doable(?))
ESCAPED = *ESCAPED
I hacked do_sd_constraint to handle this special case - we need
to add all fields the solution in ESCAPED can reach.
So, it gets somewhat ugly, and of course I am not sure that
variable unification will not get in our way ... (when exactly
are two variables unified?)
Thanks,
Richard.
Index: trunk/gcc/tree-ssa-structalias.c
===================================================================
--- trunk.orig/gcc/tree-ssa-structalias.c 2008-06-27 14:32:22.000000000 +0200
+++ trunk/gcc/tree-ssa-structalias.c 2008-06-27 14:24:27.000000000 +0200
@@ -262,6 +262,7 @@ struct variable_info
typedef struct variable_info *varinfo_t;
static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
+static varinfo_t lookup_vi_for_tree (tree);
/* Pool of variable info structures. */
static alloc_pool variable_info_pool;
@@ -1114,7 +1115,18 @@ build_succ_graph (void)
/* x = &y */
gcc_assert (find (get_varinfo_fc (rhs.var)->id)
== get_varinfo_fc (rhs.var)->id);
- bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
+ if (lhs.var == escaped_id)
+ {
+ /* We might want to simply collapse the rhs variable at this
+ point.
+ ??? This would need to happen at the point we generate
+ the constraint. */
+ varinfo_t vi = lookup_vi_for_tree (get_varinfo_fc (rhs.var)->decl);
+ for (; vi != NULL; vi = vi->next)
+ bitmap_set_bit (get_varinfo (lhsvar)->solution, vi->id);
+ }
+ else
+ bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
}
else if (lhsvar > anything_id
&& lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
@@ -1400,13 +1412,45 @@ do_sd_constraint (constraint_graph_t gra
unsigned int j;
bitmap_iterator bi;
- if (bitmap_bit_p (delta, anything_id))
- {
- flag = !bitmap_bit_p (sol, anything_id);
- if (flag)
- bitmap_set_bit (sol, anything_id);
- goto done;
- }
+ if (bitmap_bit_p (delta, anything_id))
+ {
+ flag = !bitmap_bit_p (sol, anything_id);
+ if (flag)
+ bitmap_set_bit (sol, anything_id);
+ goto done;
+ }
+
+ /* For x = *ESCAPED we interpret the deref as dereferencing all fields
+ of the ESCAPED solution variables.
+ ??? The question is if this works reliably if subvars are
+ collapsed. We might not see the original variable in delta and thus
+ not reach other fields. */
+ if (c->rhs.var == escaped_id)
+ {
+ EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
+ {
+ varinfo_t v = lookup_vi_for_tree (get_varinfo (j)->decl);
+
+ /* Only process one field as representative. */
+ if (v != get_varinfo (j)
+ && bitmap_bit_p (delta, v->id))
+ continue;
+
+ for (; v != NULL; v = v->next)
+ {
+ unsigned int t = find (v->id);
+
+ /* Adding edges from the special vars is pointless.
+ They don't have sets that can change. */
+ if (get_varinfo (t)->is_special_var)
+ flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
+ else if (add_graph_edge (graph, lhs, t))
+ flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
+ }
+ }
+ goto done;
+ }
+
/* For each variable j in delta (Sol(y)), add
an edge in the graph from j to x, and union Sol(j) into Sol(x). */
EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
@@ -1564,6 +1608,30 @@ do_complex_constraint (constraint_graph_
}
}
+static bool
+set_union_all_fields (bitmap tmp, bitmap pts)
+{
+ bitmap_iterator bi;
+ unsigned i;
+ bool flag = false;
+
+ /* For each variable in pts add all its decls variables to tmp. */
+ EXECUTE_IF_SET_IN_BITMAP (pts, 0, i, bi)
+ {
+ varinfo_t vi = lookup_vi_for_tree (get_varinfo (i)->decl);
+ if (vi != get_varinfo (i)
+ && bitmap_bit_p (pts, vi->id))
+ continue;
+ for (; vi != NULL; vi = vi->next)
+ {
+ flag |= bitmap_bit_p (tmp, vi->id);
+ bitmap_set_bit (tmp, vi->id);
+ }
+ }
+
+ return flag;
+}
+
/* Initialize and return a new SCC info structure. */
static struct scc_info *
@@ -2378,7 +2446,12 @@ solve_graph (constraint_graph_t graph)
if (to == i)
continue;
- flag = set_union_with_increment (tmp, pts, 0);
+ /* If this is a copy to the reachability set
+ ESCAPED, process it specially. */
+ if (to == escaped_id)
+ flag = set_union_all_fields (tmp, pts);
+ else
+ flag = set_union_with_increment (tmp, pts, 0);
if (flag)
{