James Molloy via llvm-dev
2015-Dec-14 08:20 UTC
[llvm-dev] RFC: New function attribute HasInaccessibleState
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/20151214/8558016b/attachment.html>
Vaivaswatha Nagaraj via llvm-dev
2015-Dec-14 16:35 UTC
[llvm-dev] RFC: New function attribute HasInaccessibleState
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/20151214/7af064b6/attachment.html>
Vaivaswatha Nagaraj via llvm-dev
2015-Dec-15 05:49 UTC
[llvm-dev] RFC: New function attribute HasInaccessibleState
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>