Re: [PATCH] Fix call-clobbering (PRs 36373 and 36387)

[Richard Guenther <rguenther at suse dot de>]

On Fri, 30 May 2008, Daniel Berlin wrote:

> On Fri, May 30, 2008 at 6:12 PM, Richard Guenther <rguenther@suse.de> wrote:
> >
> > Second, we miss to compute the reachability set of the
> > escaped pointers and only clobber the directly pointed-to
> > memory.
> 
> This is because points-to is not computing the reachability of the
> anything variable properly.

No.  points-to is not supposed to compute reachability.  points-to
is supposed to compute points-to, no?  Thus, for

  int i;
  int *p = &i;
  int **q = &p;

the points to set of p is { i } and the points to set of q is { p }.
The points to set of q is _not_ { p i } as far as I understand.  But
the reachability set is!

anything is only special as in interpreting the points to sets for
{ i anything } you just need to take anything as a placeholder for
anything.

IMHO points-to in this regard is working correctly.

The case in question is that for

  int i;
  int *p = &i;
  int **q = &p;
  foo (q);

points-to computes the points-to set of p to be { i } (ok, it doesn't
because of the "fix" in handle_rhs_call, but you get the idea).

And it cannot really do better unless you add constraints for call-sites
that make all _reachable_ memory point to anything.  But as points-to
is not about reachability we can just ignore that here and fix-up
the points-to set after computing the reachability set of the escapes
by doing

  for_all_pointers
    if pointer in escape-set
      add anything to points-to set of pointer

(or rather, if we implement it, add escape-set | nonlocal to the
points-to sets)

> Trying to work around this by doing 3 other transitive closures is not
> going to buy you anything.

I'm going to remove two of those.

> We should just fix points-to, which will fix all of these problems.

I don't think points-to is broken.  If you look in Andersens thesis
you either have to know the bodies of called functions or properly
'punt'.  We are not properly punting.

> > A followup patch needs to deal with the wrong final points-to sets
> > (see comment #2 of PR36387) by fixing them by using the
> > call-clobber solution.  A followup also may need to deal with the
> > memory tag clobbering code - but I have to think about how to
> > correctly deal with that.
> >
> 
> You are really going about this wrong.  Trying to post-fix up results
> that are wrong through computing the properties it should have been
> computing in the first place is not the way to go here.
> You will end up writing a lot of code to try to fix up the broken results.

I don't think so ;)

> As you point out in comment #2, p should point to j, or at the very
> least, ANYTHING.

Yes.  But I'm distinguishing between the solution of the constraints
and the final points-to set with varinfos substituted with decls
(and TBAA pruned).  The constraint solution is useful for computing
call-clobbering, the final points-to set not (this is already fixed
with my earlier patch).

> There are two ways to do this, the really easy way (which i'm not
> positive will work but should), the easy way (which may use a bit of
> memory), or the hard way (which is harder to get right but lower
> memory usage).
> 
> The really easy way is to add *q = q at the escape site for q.
> 
> IE the following constraints:
> ANYTHING = &ANYTHING
> READONLY = &ANYTHING
> INTEGER = &ANYTHING
> p = &i
> q = &p
> q = &ANYTHING
> *q = q
> p.0_2 = p
> 
> This will end up causing p to point to anything, as it should after the call.

Interesting idea.  But there is no q = &ANYTHING constraint (IMHO there
shouldn't be).  For the example above (let's assume handle_rhs_call
wouldn't exist)

  int i;
  int *p = &i;
  int **q = &p;
  foo (q);

we have

  p = &i
  q = &p

(w/o handle_rhs_call as it is implemented now).  So we add

  q = &ANYTHING
  *q = q

for the escape of q.  This will make p point to anything.  Good.  Now

  int i;
  int *p = &i;
  int **q = &p;
  int ***w = &q;
  foo (w);

if we add

  w = &ANYTHING
  *w = w

this will make q point to anything, but p still points to i.  Oops.

> The easy way is to
> 1. Let edges be added to anything (IE remove the special casing from the solver)
> 2. Add *ANYTHING = &ANYTHING to the constraint list (*ANYTHING = tmp,
> tmp = &ANYTHING)
> 3. At each escape site, add the escaped variables to ANYTHING.
> 4. Add the ANYTHING set to each variable pointing to ANYTHING at the end.
> 
> This should generate the following constraints for your testcase:
> 
> ANYTHING = &ANYTHING
> *ANYTHING = tmp
> tmp = &ANYTHING
> READONLY = &ANYTHING
> INTEGER = &ANYTHING
> p = &i
> q = &p
> ANYTHING = &q
> q = &ANYTHING
> p.0_2 = p
> 
> This will come up with
> 
> ANYTHING = {ANYTHING, q, p, i}
> q = {q, p, i, ANYTHING}
> p = { i, ANYTHING }
> 
> 
> The harder way is to separate ANYTHING and ESCAPED so you don't have
> to propagate the ANYTHING set around until the very end.
> 
> IE Like the easy way, except you have:
> ANYTHING = &ANYTHING
> *ANYTHING = tmp
> tmp = &ANYTHING
> READONLY = &ANYTHING
> INTEGER = &ANYTHING
> ESCAPED = *ESCAPED
> p = &i
> q = &p
> ESCAPED = &q
> q = &ANYTHING
> p.0_2 = p
> 
> Then add ESCAPED to all things with ANYTHING at the very end
> > Anyway, bootstrapped and tested on x86_64-unknown-linux-gnu, ok
> > for trunk?
> 
> No.
> We very much need to solve this problem by making points-to do a
> correct transitive closure and correctly give the result of "p points
> to anything" for your testcase.
> Trying to work around points-to not transitive closing the set of
> ANYTHING variables is a hack.

I didn't look at the solver part at all (I assume you got that right),
but only at the constraints we generate and at the various papers
(of which most circumvent the call problem by not mentioning them or
doing IPA-PTA only ...).  It seems to me the solver part never
transitively closes anything but copies - that is, it doesn't try
to promise to compute reachability.

Richard.