llvm dev - Dec 2015 - RFC: New function attribute HasInaccessibleState

----- Original Message -----
> From: "Mehdi Amini" <mehdi.amini at apple.com>
> To: "Joseph Tremoulet" <jotrem at microsoft.com>
> Cc: "Hal Finkel" <hfinkel at anl.gov>, "llvm-dev"
<llvm-dev at lists.llvm.org>
> Sent: Friday, December 11, 2015 1:28:05 PM
> Subject: Re: [llvm-dev] RFC: New function attribute HasInaccessibleState
> 
> 
> > On Dec 11, 2015, at 11:16 AM, Joseph Tremoulet
> > <jotrem at microsoft.com> wrote:
> > 
> > <<<
> > I may misunderstand, but it seems to me that this solves only query
> > for aliasing with a pointer known to be pointing only to globals
> > defined in the current compilation unit.
> > For any pointer which "may point somewhere else”, you won’t be
able
> > to resolve the non-aliasing with the “internal state” for
> > malloc/free, right?
> > 
> > To take the original example in this thread:
> > 
> > int *x = malloc(4);
> > *x = 2;
> > int *y = malloc(4);
> > *y = 4;
> > 
> > A pointer analysis can solve this case, but I’m not sure it scale
> > inter procedurally and will have a limited impact outside of LTO
> > anyway.
> >>>> 
> > 
> > I think you're understanding correctly, but I don't understand
what
> > you're saying will go badly with the malloc example.  Quoting the
> > start of the thread:
> > 
> > <<<
> > The intention behind introducing this attribute is to relax the
> > conditions in GlobalsAA as below:
> > (this code is in GlobalsAAResult::AnalyzeCallGraph)
> >       if (F->isDeclaration()) {
> >         // Try to get mod/ref behaviour from function attributes.
> > -        if (F->doesNotAccessMemory()) {
> > +        if (F->doesNotAccessMemory() ||
> > F->onlyAccessesArgMemory()) {
> >           // Can't do better than that!
> >         } else if (F->onlyReadsMemory()) {
> >           FunctionEffect |= Ref;
> >           if (!F->isIntrinsic())
> >             // This function might call back into the module and
> >             read a global -
> >             // consider every global as possibly being read by this
> >             function.
> >             FR.MayReadAnyGlobal = true;
> >         } else {
> >           FunctionEffect |= ModRef;
> >           // Can't say anything useful unless it's an
intrinsic -
> >           they don't
> >           // read or write global variables of the kind considered
> >           here.
> >           KnowNothing = !F->isIntrinsic();
> >         }
> >         continue;
> >       }
> > This relaxation allows functions that (transitively) call library
> > functions (such as printf/malloc) to still maintain and propagate
> > GlobalsAA info. In general, this adds more precision to the
> > description of these functions.
> > Concerns regarding impact on other optimizations (I'm repeating a
> > few examples that Hal mentioned earlier).
> > 
> > 1.
> >> A readnone function is one whose output is a function only of its
> >> inputs, and if you have this:
> >> 
> >> int *x = malloc(4);
> >> *x = 2;
> >> int *y = malloc(4);
> >> *y = 4;
> >> you certainly don't want EarlyCSE to replace the second call
to
> >> malloc with the result of the first (which it will happily do if
> >> you mark malloc as readnone).
> >>>> 
> > 
> > It sounded like improving GlobalsAA (and thus disambiguation
> > against globals) was the explicit goal, and that the concern with
> > the malloc case was that you don't want EarlyCSE to start
> > combining those two calls; I may be misunderstanding the code, but
> > I wouldn't expect EarlyCSE to start combining those calls just
> > because they have a new meaningful-only-to-GlobalsAA
> > "almost-readnone" attribute.
> 
> Sure, my point is not that your solution would enable CSE where we
> don’t want, but rather that it is not as powerful as what the
> attribute “HasInaccessibleState” would model, which I saw as "this
> function might access globals, but none of these globals can alias
> with any memory location accessible from the IR being optimized”.
This is also, essentially, what I had in mind. I think it is sufficiently well
defined in this form.

 -Hal
> For instance:
> 
> void foo(int *x) {
>   int *y = malloc(4);
>   *x = 2;
> }
> 
> If you don’t know anything about x, can you execute the write to *x
> before the call to malloc?
> This is something that the HasInaccessibleState would allow, but I
> don’t believe would be possible with your categorization.
> 
> I’m don’t know how much it matters in practice, but I’d rather be
> sure we’re on the same track about the various tradeoff.
> 
> —
> Mehdi
> 
> 
> 
> > 
> > 
> > To the larger point of whether there are other similar cases that
> > extending GlobalsAA wouldn't allow us to optimize -- yes,
> > certainly.  I'm just saying that I think that the notion of
> > "external state" is much easier to define in the context of
a
> > particular analysis than the IR as a whole, and that I'd expect
> > that coordinating the notion across analyses would require methods
> > on the analysis API explicitly for that coordination.
> > 
> > 
> > 
> > —
> > Mehdi
> > 
> 
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

Yeah, I'd agree (rewording slightly) that "state which is only modified
by external code" is well-defined (and likely to be in the
"other" bucket of any individual analysis).  I do, as other have, find
it odd to redefine readonly and argmemonly in terms of this and require its
propagation up the call graph, as opposed to introducing new "writes only
external" and "writes only arg and external" attributes.

Thanks
-Joseph

-----Original Message-----
From: Hal Finkel [mailto:hfinkel at anl.gov] 
Sent: Friday, December 11, 2015 4:00 PM
To: Mehdi Amini <mehdi.amini at apple.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>; Joseph Tremoulet <jotrem at
microsoft.com>
Subject: Re: [llvm-dev] RFC: New function attribute HasInaccessibleState

----- Original Message -----
> From: "Mehdi Amini" <mehdi.amini at apple.com>
> To: "Joseph Tremoulet" <jotrem at microsoft.com>
> Cc: "Hal Finkel" <hfinkel at anl.gov>, "llvm-dev"
> <llvm-dev at lists.llvm.org>
> Sent: Friday, December 11, 2015 1:28:05 PM
> Subject: Re: [llvm-dev] RFC: New function attribute 
> HasInaccessibleState
> 
> 
> > On Dec 11, 2015, at 11:16 AM, Joseph Tremoulet 
> > <jotrem at microsoft.com> wrote:
> > 
> > <<<
> > I may misunderstand, but it seems to me that this solves only query 
> > for aliasing with a pointer known to be pointing only to globals 
> > defined in the current compilation unit.
> > For any pointer which "may point somewhere else”, you won’t be
able
> > to resolve the non-aliasing with the “internal state” for 
> > malloc/free, right?
> > 
> > To take the original example in this thread:
> > 
> > int *x = malloc(4);
> > *x = 2;
> > int *y = malloc(4);
> > *y = 4;
> > 
> > A pointer analysis can solve this case, but I’m not sure it scale 
> > inter procedurally and will have a limited impact outside of LTO 
> > anyway.
> >>>> 
> > 
> > I think you're understanding correctly, but I don't understand
what
> > you're saying will go badly with the malloc example.  Quoting the 
> > start of the thread:
> > 
> > <<<
> > The intention behind introducing this attribute is to relax the 
> > conditions in GlobalsAA as below:
> > (this code is in GlobalsAAResult::AnalyzeCallGraph)
> >       if (F->isDeclaration()) {
> >         // Try to get mod/ref behaviour from function attributes.
> > -        if (F->doesNotAccessMemory()) {
> > +        if (F->doesNotAccessMemory() ||
> > F->onlyAccessesArgMemory()) {
> >           // Can't do better than that!
> >         } else if (F->onlyReadsMemory()) {
> >           FunctionEffect |= Ref;
> >           if (!F->isIntrinsic())
> >             // This function might call back into the module and
> >             read a global -
> >             // consider every global as possibly being read by this
> >             function.
> >             FR.MayReadAnyGlobal = true;
> >         } else {
> >           FunctionEffect |= ModRef;
> >           // Can't say anything useful unless it's an
intrinsic -
> >           they don't
> >           // read or write global variables of the kind considered
> >           here.
> >           KnowNothing = !F->isIntrinsic();
> >         }
> >         continue;
> >       }
> > This relaxation allows functions that (transitively) call library 
> > functions (such as printf/malloc) to still maintain and propagate 
> > GlobalsAA info. In general, this adds more precision to the 
> > description of these functions.
> > Concerns regarding impact on other optimizations (I'm repeating a 
> > few examples that Hal mentioned earlier).
> > 
> > 1.
> >> A readnone function is one whose output is a function only of its 
> >> inputs, and if you have this:
> >> 
> >> int *x = malloc(4);
> >> *x = 2;
> >> int *y = malloc(4);
> >> *y = 4;
> >> you certainly don't want EarlyCSE to replace the second call
to
> >> malloc with the result of the first (which it will happily do if 
> >> you mark malloc as readnone).
> >>>> 
> > 
> > It sounded like improving GlobalsAA (and thus disambiguation against 
> > globals) was the explicit goal, and that the concern with the malloc 
> > case was that you don't want EarlyCSE to start combining those two
> > calls; I may be misunderstanding the code, but I wouldn't expect 
> > EarlyCSE to start combining those calls just because they have a new 
> > meaningful-only-to-GlobalsAA "almost-readnone" attribute.
> 
> Sure, my point is not that your solution would enable CSE where we 
> don’t want, but rather that it is not as powerful as what the 
> attribute “HasInaccessibleState” would model, which I saw as "this 
> function might access globals, but none of these globals can alias 
> with any memory location accessible from the IR being optimized”.
This is also, essentially, what I had in mind. I think it is sufficiently well
defined in this form.

 -Hal
> For instance:
> 
> void foo(int *x) {
>   int *y = malloc(4);
>   *x = 2;
> }
> 
> If you don’t know anything about x, can you execute the write to *x 
> before the call to malloc?
> This is something that the HasInaccessibleState would allow, but I 
> don’t believe would be possible with your categorization.
> 
> I’m don’t know how much it matters in practice, but I’d rather be sure 
> we’re on the same track about the various tradeoff.
> 
> —
> Mehdi
> 
> 
> 
> > 
> > 
> > To the larger point of whether there are other similar cases that 
> > extending GlobalsAA wouldn't allow us to optimize -- yes,
certainly.
> > I'm just saying that I think that the notion of "external
state" is
> > much easier to define in the context of a particular analysis than 
> > the IR as a whole, and that I'd expect that coordinating the
notion
> > across analyses would require methods on the analysis API explicitly 
> > for that coordination.
> > 
> > 
> > 
> > —
> > Mehdi
> > 
> 
> 
--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

----- Original Message -----
> From: "Joseph Tremoulet" <jotrem at microsoft.com>
> To: "Hal Finkel" <hfinkel at anl.gov>, "Mehdi
Amini" <mehdi.amini at apple.com>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Friday, December 11, 2015 3:35:38 PM
> Subject: RE: [llvm-dev] RFC: New function attribute HasInaccessibleState
> 
> Yeah, I'd agree (rewording slightly) that "state which is only
> modified by external code" is well-defined (and likely to be in the
> "other" bucket of any individual analysis).  I do, as other have,
> find it odd to redefine readonly and argmemonly in terms of this and
> require its propagation up the call graph, as opposed to introducing
> new "writes only external" and "writes only arg and
external"
> attributes.
As I stated in some other e-mail, I'm against adding this as a
"subtractive" attribute. We need to add these as new attributes, not
as an attribute that makes readonly a little less read only. I believe we're
in agreement on this point.

 -Hal
> 
> Thanks
> -Joseph
> 
> -----Original Message-----
> From: Hal Finkel [mailto:hfinkel at anl.gov]
> Sent: Friday, December 11, 2015 4:00 PM
> To: Mehdi Amini <mehdi.amini at apple.com>
> Cc: llvm-dev <llvm-dev at lists.llvm.org>; Joseph Tremoulet
> <jotrem at microsoft.com>
> Subject: Re: [llvm-dev] RFC: New function attribute
> HasInaccessibleState
> 
> ----- Original Message -----
> > From: "Mehdi Amini" <mehdi.amini at apple.com>
> > To: "Joseph Tremoulet" <jotrem at microsoft.com>
> > Cc: "Hal Finkel" <hfinkel at anl.gov>,
"llvm-dev"
> > <llvm-dev at lists.llvm.org>
> > Sent: Friday, December 11, 2015 1:28:05 PM
> > Subject: Re: [llvm-dev] RFC: New function attribute
> > HasInaccessibleState
> > 
> > 
> > > On Dec 11, 2015, at 11:16 AM, Joseph Tremoulet
> > > <jotrem at microsoft.com> wrote:
> > > 
> > > <<<
> > > I may misunderstand, but it seems to me that this solves only
> > > query
> > > for aliasing with a pointer known to be pointing only to globals
> > > defined in the current compilation unit.
> > > For any pointer which "may point somewhere else”, you won’t
be
> > > able
> > > to resolve the non-aliasing with the “internal state” for
> > > malloc/free, right?
> > > 
> > > To take the original example in this thread:
> > > 
> > > int *x = malloc(4);
> > > *x = 2;
> > > int *y = malloc(4);
> > > *y = 4;
> > > 
> > > A pointer analysis can solve this case, but I’m not sure it scale
> > > inter procedurally and will have a limited impact outside of LTO
> > > anyway.
> > >>>> 
> > > 
> > > I think you're understanding correctly, but I don't
understand
> > > what
> > > you're saying will go badly with the malloc example.  Quoting
the
> > > start of the thread:
> > > 
> > > <<<
> > > The intention behind introducing this attribute is to relax the
> > > conditions in GlobalsAA as below:
> > > (this code is in GlobalsAAResult::AnalyzeCallGraph)
> > >       if (F->isDeclaration()) {
> > >         // Try to get mod/ref behaviour from function attributes.
> > > -        if (F->doesNotAccessMemory()) {
> > > +        if (F->doesNotAccessMemory() ||
> > > F->onlyAccessesArgMemory()) {
> > >           // Can't do better than that!
> > >         } else if (F->onlyReadsMemory()) {
> > >           FunctionEffect |= Ref;
> > >           if (!F->isIntrinsic())
> > >             // This function might call back into the module and
> > >             read a global -
> > >             // consider every global as possibly being read by
> > >             this
> > >             function.
> > >             FR.MayReadAnyGlobal = true;
> > >         } else {
> > >           FunctionEffect |= ModRef;
> > >           // Can't say anything useful unless it's an
intrinsic -
> > >           they don't
> > >           // read or write global variables of the kind
> > >           considered
> > >           here.
> > >           KnowNothing = !F->isIntrinsic();
> > >         }
> > >         continue;
> > >       }
> > > This relaxation allows functions that (transitively) call library
> > > functions (such as printf/malloc) to still maintain and propagate
> > > GlobalsAA info. In general, this adds more precision to the
> > > description of these functions.
> > > Concerns regarding impact on other optimizations (I'm
repeating a
> > > few examples that Hal mentioned earlier).
> > > 
> > > 1.
> > >> A readnone function is one whose output is a function only of
> > >> its
> > >> inputs, and if you have this:
> > >> 
> > >> int *x = malloc(4);
> > >> *x = 2;
> > >> int *y = malloc(4);
> > >> *y = 4;
> > >> you certainly don't want EarlyCSE to replace the second
call to
> > >> malloc with the result of the first (which it will happily do
if
> > >> you mark malloc as readnone).
> > >>>> 
> > > 
> > > It sounded like improving GlobalsAA (and thus disambiguation
> > > against
> > > globals) was the explicit goal, and that the concern with the
> > > malloc
> > > case was that you don't want EarlyCSE to start combining
those
> > > two
> > > calls; I may be misunderstanding the code, but I wouldn't
expect
> > > EarlyCSE to start combining those calls just because they have a
> > > new
> > > meaningful-only-to-GlobalsAA "almost-readnone"
attribute.
> > 
> > Sure, my point is not that your solution would enable CSE where we
> > don’t want, but rather that it is not as powerful as what the
> > attribute “HasInaccessibleState” would model, which I saw as
"this
> > function might access globals, but none of these globals can alias
> > with any memory location accessible from the IR being optimized”.
> 
> This is also, essentially, what I had in mind. I think it is
> sufficiently well defined in this form.
> 
>  -Hal
> 
> > For instance:
> > 
> > void foo(int *x) {
> >   int *y = malloc(4);
> >   *x = 2;
> > }
> > 
> > If you don’t know anything about x, can you execute the write to *x
> > before the call to malloc?
> > This is something that the HasInaccessibleState would allow, but I
> > don’t believe would be possible with your categorization.
> > 
> > I’m don’t know how much it matters in practice, but I’d rather be
> > sure
> > we’re on the same track about the various tradeoff.
> > 
> > —
> > Mehdi
> > 
> > 
> > 
> > > 
> > > 
> > > To the larger point of whether there are other similar cases that
> > > extending GlobalsAA wouldn't allow us to optimize -- yes,
> > > certainly.
> > > I'm just saying that I think that the notion of
"external state"
> > > is
> > > much easier to define in the context of a particular analysis
> > > than
> > > the IR as a whole, and that I'd expect that coordinating the
> > > notion
> > > across analyses would require methods on the analysis API
> > > explicitly
> > > for that coordination.
> > > 
> > > 
> > > 
> > > —
> > > Mehdi
> > > 
> > 
> > 
> 
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory