[llvm-dev] RFC: New function attribute HasInaccessibleState

Mon Dec 14 21:49:34 PST 2015

Proposal for naming the attributes:

AlmostReadNone -> InaccessibleMemOnly
AlmostArgMemOnly -> ArgMemORInaccessibleMemOnly

Any other suggestions are welcome.

Thanks,

  - Vaivaswatha

On Mon, Dec 14, 2015 at 10:05 PM, Vaivaswatha Nagaraj <vn at compilertree.com>
wrote:

> Thanks everyone for your inputs. I have a patch up for review here
> http://reviews.llvm.org/D15499
>
>   - Vaivaswatha
>
> On Mon, Dec 14, 2015 at 1:50 PM, James Molloy <james at jamesmolloy.co.uk>
> wrote:
>
>> Hi,
>>
>> If these are the options, I'm also in favour of approach B. Approach A
>> redefines ReadNone, which I don't think is acceptable.
>>
>> James
>>
>> On Mon, 14 Dec 2015 at 08:15 Vaivaswatha Nagaraj via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>>> >I am in favor of approach B (although perhaps with different names).
>>> Just to clarify, this does not requires any propagation of attributes
>>> along the call graph. If the name is all that needs closure, I think I can
>>> submit a patch for review (with the current name) and we can conclude on a
>>> name later. The idea is to implement the three items I mentioned as
>>> Approach B. Please let me know.
>>>
>>>   - Vaivaswatha
>>>
>>> On Mon, Dec 14, 2015 at 1:36 PM, Hal Finkel <hfinkel at anl.gov> wrote:
>>>
>>>> ----- Original Message -----
>>>>
>>>> > From: "Vaivaswatha Nagaraj" <vn at compilertree.com>
>>>> > To: "Hal Finkel" <hfinkel at anl.gov>
>>>> > Cc: "Joseph Tremoulet" <jotrem at microsoft.com>, "llvm-dev"
>>>> > <llvm-dev at lists.llvm.org>
>>>> > Sent: Sunday, December 13, 2015 9:50:25 PM
>>>> > Subject: Re: [llvm-dev] RFC: New function attribute
>>>> > HasInaccessibleState
>>>>
>>>> > >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.
>>>> > Just to make sure I understood right, below are the things that need
>>>> > to be done:
>>>>
>>>> > (Approach A)
>>>>
>>>> > 1. We define a new a attribute "HasInaccessibleState" to denote "this
>>>> > function might access globals, but none of these globals can alias
>>>> > with any memory location accessible from the IR being optimized".
>>>> > 2. Mark malloc/free as (HasInaccessibleState, ReadNone) and printf as
>>>> > (HasInaccessibleState, ArgMemOnly) ... (similarly other libc
>>>> > functions).
>>>> > 3. Any function whose definition is not available needs to be marked
>>>> > with "HasInaccessibleState" (conservatively).
>>>> > 4. Propagate the flag "HasInaccessibleState" upwards in the call
>>>> > graph. (Do this in FunctionAttrs.cpp?).
>>>> > 5. Since ReadNone and ArgMemOnly has now been redfined, all
>>>> > optimizations that rely on these flags for safety now also need to
>>>> > check the new "HasInaccessibleState" flag and make sure it isn't
>>>> > present.
>>>> > 6. GlobalsAA will be modified according to the diff in the first mail
>>>> > in this email thread.
>>>>
>>>> > The alternative approach that was discussed would involve the
>>>> > following changes:
>>>>
>>>> > (Approach B)
>>>> > 1. Define new attributes AlmostReadNone and AlmostArgMemOnly, (with
>>>> > the "Almost" part denoting that the function may accesses globals
>>>> > that are not part of the IR).
>>>> > 2. malloc/free would have AlmostReadNone set and printf would have
>>>> > AlmostArgMemOnly set ... (and similarly other libc calls).
>>>> > 3. In the diff I originally posted for GlobalsAA, the code would
>>>> > check for AlmostReadNone or AlmostArgMemOnly too (along with
>>>> > ReadNone or ArgMemOnly).
>>>>
>>>> > Approach B seems simpler to me, but I understand the concern about
>>>> > having a "subtractive" attribute which is new to the framework.
>>>>
>>>> No, you have my concern reversed. Approach A is the "subtractive" one,
>>>> because (HasInaccessibleState, ReadNone) "subtracts" from the meaning of
>>>> ReadNone. This I am against. I am in favor of approach B (although perhaps
>>>> with different names).
>>>>
>>>> Thanks again,
>>>> Hal
>>>>
>>>> > If
>>>> > there is a consensus on which of these two approaches is the way to
>>>> > go, I can submit a quick prototype patch for further
>>>> > review/discussion.
>>>>
>>>> > Thanks,
>>>>
>>>> > - Vaivaswatha
>>>>
>>>> > On Sat, Dec 12, 2015 at 3:21 AM, Hal Finkel via llvm-dev <
>>>> > llvm-dev at lists.llvm.org > wrote:
>>>>
>>>> > > ----- 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
>>>> >
>>>> > > _______________________________________________
>>>> >
>>>> > > LLVM Developers mailing list
>>>> >
>>>> > > llvm-dev at lists.llvm.org
>>>> >
>>>> > > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>> >
>>>>
>>>> --
>>>>
>>>> --
>>>> Hal Finkel
>>>> Assistant Computational Scientist
>>>> Leadership Computing Facility
>>>> Argonne National Laboratory
>>>>
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20151215/ef36fcaf/attachment-0001.html>