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

["Daniel Berlin" <dberlin at dberlin dot org>]

On Mon, Jun 9, 2008 at 7:21 AM, Richard Guenther <rguenther@suse.de> wrote:
> On Fri, 6 Jun 2008, Daniel Berlin wrote:
>
>> On Fri, Jun 6, 2008 at 10:14 AM, Richard Guenther <rguenther@suse.de> wrote:
>> > On Fri, 6 Jun 2008, Richard Guenther wrote:
>> >
>> >> On Thu, 5 Jun 2008, Daniel Berlin wrote:
>> >>
>> >> > On Thu, Jun 5, 2008 at 9:07 AM, Richard Guenther <rguenther@suse.de> wrote:
>> >> > > On Fri, 30 May 2008, Daniel Berlin wrote:
>> >> > >
>> >> > >> Something like the attached should fix the points-to results (I may
>> >> > >> have missed some is_special_var cases to remove, etc)
>> >> > >
>> >> > > I played a little with the patch and tried to simplify and extend it
>> >> > > somewhat (I'm still trying to improve the accuracy of call clobbers,
>> >> > > because thats the only thing the alias-oracle really has to punt on
>> >> > > while walking the statements).
>> >> > >
>> >> > > First I didn't like re-using ANYTHING for aggregating the reachable
>> >> > > escaped memory, so I created a new var ESCAPED for that (and simply
>> >> > > make it not a special_var, so the solver part of the patch seems
>> >> > > unneeded).  In interpreting the PTA results, ESCAPED needs to
>> >> > > be treated the same as anything in this state.  Note in particular
>> >> > > that for fixing the aggregate escape bugs I created proper
>> >> > > constraints for escape sites.
>> >> > >
>> >> > > The thing we can improve with call-clobbers is to track NONLOCAL
>> >> > > again, noting that at calls the reachable memory can point to
>> >> > > NONLOCAL and ESCAPED.  Likewise call results point to NONLOCAL
>> >> > > and ESCAPED and obviously incoming function arguments point to NONLOCAL.
>> >> > > But for that to really work I need to track escapes to global vars
>> >> > > and read from global vars properly - in the end ESCAPED would then
>> >> > > (apart from global vars) include the full call-clobber solution, no
>> >> > > need for a separate transitive closure there.
>> >> > >
>> >> > > This still won't handle pure/const functions in an optimal manner
>> >> > > because we would have to track call-used memory for those.  Both
>> >> > > are not escape sites but const functions may return pointers to
>> >> > > global memory and its function arguments.  pure functions may return
>> >> > > pointers to any reachable memory by its function arguments in addition.
>> >> > > Proper VUSEs need to be added for them.  [with the patch below
>> >> > > gcc.dg/tree-ssa/pr24287.c fails to optimize because of this]
>> >> > >
>> >> > > I verified that with the re-invention of NONLOCAL and ESCAPED we
>> >> > > don't get PR30052 back, but I still have to do some compile-time
>> >> > > analyses.  With making can_have_pointers more precise we can possibly
>> >> > > avoid creating some constraints and increase the precision as well.
>> >> > >
>> >> > > Bootstrapped / tested on x86_64-unknown-linux-gnu.
>> >> > >
>> >> > > While the patch is getting somewhat big I'm going to try to track
>> >> > > call-used memory separately and clean up the memory-tag clobbering
>> >> > > code.  Still, does this look like a reasonable change?
>> >> > >
>> >> >
>> >> > It looks reasonable to me. If you have ESCAPE compute transitive
>> >> > closure from points-to, you are going to want to make a fake set until
>> >> > the end.
>> >> >
>> >> > Otherwise, you will have this:
>> >> >
>> >> > ESCAPED = <6000 variables>
>> >> > foo (which escapes) = ESCAPED
>> >> > bar (which escapes) = ESCAPED
>> >> > etc
>> >> > Offline var substitution will not always collapse these, and you will
>> >> > end up allocating 6000 bit bitmaps for a lot of variables and then
>> >> > propagating them around.
>> >> >
>> >> > This is easily taken care of with a fake variable though, like
>> >> > ESCAPED_SET, which you fill in at *_what_p_points_to time with the
>> >> > result of ESCAPED.
>> >>
>> >> Yes, I'm seeing for example
>> >>
>> >> ESCAPED = *ESCAPED
>> >> ESCAPED = &ESCAPED
>> >> derefaddrtmp.30 = &ESCAPED
>> >> *ESCAPED = derefaddrtmp.30
>> >> derefaddrtmp.31 = &NONLOCAL
>> >> *ESCAPED = derefaddrtmp.31
>> >> a = &i
>> >> b = &i
>> >> ESCAPED = &a
>> >> ESCAPED = &b
>> >> D.1567_1 = a
>> >> D.1570_4 = b
>> >>
>> >> ->
>> >>
>> >> ESCAPED = { ESCAPED NONLOCAL a i b }
>> >> NONLOCAL = { }
>> >> a = same as D.1567_1
>> >> i = { ESCAPED NONLOCAL }
>> >> b = same as D.1570_4
>> >> D.1567_1 = { ESCAPED NONLOCAL i }
>> >> D.1570_4 = { ESCAPED NONLOCAL i }
>> >>
>> >> where for example the i = { ESCAPED NONLOCAL } is not needed (i is not
>> >> a pointer) and D.1567_1 and D.1570_4 could have been unified.
>> >>
>> >> but I don't understand what you are suggesting ;)
>> >>
>> >> are you suggesting not to add ESCAPED to the points-to solution until
>> >> after the solver finished and get the information from the ESCAPED
>> >> set itself at *_what_p_points_to time?  That is, omit
>> >>
>> >> derefaddrtmp.30 = &ESCAPED
>> >> *ESCAPED = derefaddrtmp.30
>> >> derefaddrtmp.31 = &NONLOCAL
>> >> *ESCAPED = derefaddrtmp.31
>> >>
>> >> from the static constraints so we end up with
>> >>
>> >> ESCAPED = { ESCAPED a i b }
>> >> NONLOCAL = { }
>> >> a = same as D.1567_1
>> >> i = { }
>> >> b = same as D.1570_4
>> >> D.1567_1 = { i }
>> >> D.1570_4 = { i }
>> >>
>> >> ?
>> >>
>> >> btw - can ESCAPED ever be unioned with some other variable?  (it's
>> >> only an is_artificial_var, not is_special_var)
>> >
>> > Btw - this doesn't work correctly.  Suppose you have
>> >
>> > p = &i
>> > ESCAPED = &p
>> > x_4 = p
>> > x_1 = x_4
>> > x_1 = &NULL
>> >
>> > then you end up with
>> >
>> > ESCAPED = { p i }
>> > p = { ESCAPED NONLOCAL i }
>> > p = same as x_4
>> > i = { }
>> > x_4 = { ESCAPED NONLOCAL i }
>> > x_1 = { NULL i }
>> >
>>
>> ???
>> From your constraints, x_1 = x_4, so if x_4 contains { ESCAPED
>> NONLOCAL }, so should x_1 at the end of solving.
>> My guess is that  it is one of the special casings in the solver that
>> is making this not work (or you didn't actually try the above :P)
>
> Yes, I did ;)  x_1 is the result of a PHI node (I just wanted to avoid
> x_1 is being unified with p, in which case it obviously works).

Let me go see why the solver gets this wrong.

>
> But the above is without the
>
>  *ESCAPED = &ESCAPED

*ESC

>> No, i'm suggesting that you have  both "ESCAPED" and
>> "ESCAPED_PLACEHOLDER". ESCAPED should be computed as it is now.
>> Things you are trying to set *from* ESCAPED (IE a = ESCAPED) should be
>> set to ESCAPED_PLACEHOLDER instead.
>>
>> At the end, anything pointing to ESCAPED_PLACEHOLDER gets ESCAPED's
>> points-to vars added to it's set.
>
> Computing ESCAPED requires a transitive closure, thus
>
>  ESCAPED = *ESCAPED
>  ESCAPED = p
>  ...
>
> and the clobbering (that is, the set that needs its points-to set
> adjusted by ESCAPED) as well, thus
>
>  ESCAPED_PLACEHOLDER = *ESCAPED_PLACEHOLDER
>  *p = &ESCAPED_PLACEHOLDER
>
> but that means I gain nothing from using ESCAPED_PLACEHOLDER?

No, because you've just shown that only ESCAPED will have a large set,
not ESCAPE_PLACEHOLDER, thus what you gain is the ability to not have
the large ESCAPE set propagated around when there are double
dereferences of things pointing to ESCAPED


IE foo = ESCAPED
a = *foo
b = *a

Now b will include everything in ESCAPED, and anything that includes b
will also include all those variables.
When ESCAPED is large, this ends up quite bad.
since ESCAPED_PLACEHOLDER never grows, it isn't a big deal there.
Certainly, for regular old uses, it's not going to make any difference.
This is more or less doing manual "location equivalence optimization".