[llvm-dev] RFC: New function attribute HasInaccessibleState

[Hal Finkel via llvm-dev]

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