[llvm-dev] RFC: New function attribute HasInaccessibleState

[Hal Finkel via llvm-dev]

----- 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