[llvm-dev] RFC: New function attribute HasInaccessibleState
Sanjoy Das via llvm-dev
llvm-dev at lists.llvm.org
Sun Dec 13 22:04:17 PST 2015
Vaivaswatha Nagaraj wrote:
> >You'll have to mark free as argmemonly + read-write, since the
> The intention is to say that free can modify the memory pointed to in its argument. Doesn't ArgMemOnly cover that
> already?
Yes, but I thought you were suggesting against marking free as argmemonly, since you said "Mark malloc/free as
(HasInaccessibleState, ReadNone)"?
A question that will help me assess if I've understood what you have in mind: why do you need to mark printf() as
argmemonly?
-- Sanjoy
>
> - Vaivaswatha
>
> On Mon, Dec 14, 2015 at 10:59 AM, Sanjoy Das <sanjoy at playingwithpointers.com <mailto:sanjoy at playingwithpointers.com>> wrote:
>
> Vaivaswatha Nagaraj via llvm-dev wrote:
> > >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).
>
> You'll have to mark free as argmemonly + read-write, since the
> following transform needs to be illegal:
>
> val = *ptr
> free(ptr)
>
> =>
>
> free(ptr)
> val = *ptr
>
> In fact, I think you can mark @free as argmemonly *today* without any
> problems. There is a theoretical issue on whether a "write" can make
> a location no longer dereferenceable, but that's not new.
>
> > 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. 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.
>
> A third approach is to extend the noalias metadata [1] (I mentioned
> this earlier in the thread, but did not do a good job on
> expanding on it). Currently noalias metadata can be used to specify
> that a certain call or invoke does not read / modify memory locations
> belonging to certain *specific* alias domains. We could generalize
> this mechanism and specify a new kind of alias domain called (say)
> !ir-mem. Calls to @malloc and @printf could be marked with "!noalias
> !ir-mem" [2], and we could specify (as an axiom) that no loads and
> stores visible at the IR level alias with the !ir-mem domain. The
> advantage of this approach is that we won't have to introduce any
> fundamentally new first class concepts to LLVM IR (though it would
> still be a fair amount of work).
>
> [1]: http://llvm.org/docs/LangRef.html#noalias-and-alias-scope-metadata
> [2]: We'll also have to introduce an "NoAliasIRMem" attribute, that
> can be used denote that all calls to the marked function are !noalias
> !ir-mem.
>
> -- Sanjoy
>
>
> >
> > Thanks,
> >
> >
> > - Vaivaswatha
> >
> > On Sat, Dec 12, 2015 at 3:21 AM, Hal Finkel via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> <mailto:llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>> wrote:
> >
> > ----- Original Message -----
> > > From: "Joseph Tremoulet" <jotrem at microsoft.com <mailto:jotrem at microsoft.com> <mailto:jotrem at microsoft.com
> <mailto:jotrem at microsoft.com>>>
> > > To: "Hal Finkel" <hfinkel at anl.gov <mailto:hfinkel at anl.gov> <mailto:hfinkel at anl.gov <mailto:hfinkel at anl.gov>>>,
> "Mehdi Amini" <mehdi.amini at apple.com <mailto:mehdi.amini at apple.com>
> > <mailto:mehdi.amini at apple.com <mailto:mehdi.amini at apple.com>>>
> > > Cc: "llvm-dev" <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> <mailto:llvm-dev at lists.llvm.org
> <mailto: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 <mailto:hfinkel at anl.gov> <mailto:hfinkel at anl.gov <mailto:hfinkel at anl.gov>>]
> > > Sent: Friday, December 11, 2015 4:00 PM
> > > To: Mehdi Amini <mehdi.amini at apple.com <mailto:mehdi.amini at apple.com> <mailto:mehdi.amini at apple.com
> <mailto:mehdi.amini at apple.com>>>
> > > Cc: llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> <mailto:llvm-dev at lists.llvm.org
> <mailto:llvm-dev at lists.llvm.org>>>; Joseph Tremoulet
> > > <jotrem at microsoft.com <mailto:jotrem at microsoft.com> <mailto:jotrem at microsoft.com <mailto:jotrem at microsoft.com>>>
> > > Subject: Re: [llvm-dev] RFC: New function attribute
> > > HasInaccessibleState
> > >
> > > ----- Original Message -----
> > > > From: "Mehdi Amini" <mehdi.amini at apple.com <mailto:mehdi.amini at apple.com> <mailto:mehdi.amini at apple.com
> <mailto:mehdi.amini at apple.com>>>
> > > > To: "Joseph Tremoulet" <jotrem at microsoft.com <mailto:jotrem at microsoft.com> <mailto:jotrem at microsoft.com
> <mailto:jotrem at microsoft.com>>>
> > > > Cc: "Hal Finkel" <hfinkel at anl.gov <mailto:hfinkel at anl.gov> <mailto:hfinkel at anl.gov <mailto:hfinkel at anl.gov>>>,
> "llvm-dev"
> > > > <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> <mailto:llvm-dev at lists.llvm.org
> <mailto: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 <mailto:jotrem at microsoft.com> <mailto:jotrem at microsoft.com
> <mailto: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 <mailto:llvm-dev at lists.llvm.org> <mailto:llvm-dev at lists.llvm.org
> <mailto:llvm-dev at lists.llvm.org>>
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
More information about the llvm-dev
mailing list