<div dir="ltr">Thanks everyone for your inputs. I have a patch up for review here <a href="http://reviews.llvm.org/D15499">http://reviews.llvm.org/D15499</a><br></div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature"><div dir="ltr">  - Vaivaswatha<br></div></div></div>
<br><div class="gmail_quote">On Mon, Dec 14, 2015 at 1:50 PM, James Molloy <span dir="ltr"><<a href="mailto:james@jamesmolloy.co.uk" target="_blank">james@jamesmolloy.co.uk</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi,<div><br></div><div>If these are the options, I'm also in favour of approach B. Approach A redefines ReadNone, which I don't think is acceptable.</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>James</div></font></span></div><div class="HOEnZb"><div class="h5"><br><div class="gmail_quote"><div dir="ltr">On Mon, 14 Dec 2015 at 08:15 Vaivaswatha Nagaraj via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>>I am in favor of approach B (although perhaps with different names).<br></div></div><div dir="ltr">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.<br>
</div><div class="gmail_extra"></div><div class="gmail_extra"><br clear="all"><div><div><div dir="ltr">  - Vaivaswatha<br></div></div></div></div><div class="gmail_extra">
<br><div class="gmail_quote">On Mon, Dec 14, 2015 at 1:36 PM, Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">----- Original Message -----<br>
<br>
> From: "Vaivaswatha Nagaraj" <<a href="mailto:vn@compilertree.com" target="_blank">vn@compilertree.com</a>><br>
> To: "Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>><br>
> Cc: "Joseph Tremoulet" <<a href="mailto:jotrem@microsoft.com" target="_blank">jotrem@microsoft.com</a>>, "llvm-dev"<br>
> <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
> Sent: Sunday, December 13, 2015 9:50:25 PM<br>
<span>> Subject: Re: [llvm-dev] RFC: New function attribute<br>
> HasInaccessibleState<br>
<br>
</span><div><div>> >I'm against adding this as a "subtractive" attribute. We need to add<br>
> >these as new attributes, not as an attribute that makes readonly a<br>
> >little less read only. I believe we're in agreement on this point.<br>
> Just to make sure I understood right, below are the things that need<br>
> to be done:<br>
<br>
> (Approach A)<br>
<br>
> 1. We define a new a attribute "HasInaccessibleState" to denote "this<br>
> function might access globals, but none of these globals can alias<br>
> with any memory location accessible from the IR being optimized".<br>
> 2. Mark malloc/free as (HasInaccessibleState, ReadNone) and printf as<br>
> (HasInaccessibleState, ArgMemOnly) ... (similarly other libc<br>
> functions).<br>
> 3. Any function whose definition is not available needs to be marked<br>
> with "HasInaccessibleState" (conservatively).<br>
> 4. Propagate the flag "HasInaccessibleState" upwards in the call<br>
> graph. (Do this in FunctionAttrs.cpp?).<br>
> 5. Since ReadNone and ArgMemOnly has now been redfined, all<br>
> optimizations that rely on these flags for safety now also need to<br>
> check the new "HasInaccessibleState" flag and make sure it isn't<br>
> present.<br>
> 6. GlobalsAA will be modified according to the diff in the first mail<br>
> in this email thread.<br>
<br>
> The alternative approach that was discussed would involve the<br>
> following changes:<br>
<br>
> (Approach B)<br>
> 1. Define new attributes AlmostReadNone and AlmostArgMemOnly, (with<br>
> the "Almost" part denoting that the function may accesses globals<br>
> that are not part of the IR).<br>
> 2. malloc/free would have AlmostReadNone set and printf would have<br>
> AlmostArgMemOnly set ... (and similarly other libc calls).<br>
> 3. In the diff I originally posted for GlobalsAA, the code would<br>
> check for AlmostReadNone or AlmostArgMemOnly too (along with<br>
> ReadNone or ArgMemOnly).<br>
<br>
> Approach B seems simpler to me, but I understand the concern about<br>
> having a "subtractive" attribute which is new to the framework.<br>
<br>
</div></div>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).<br>
<br>
Thanks again,<br>
Hal<br>
<div><div><br>
> If<br>
> there is a consensus on which of these two approaches is the way to<br>
> go, I can submit a quick prototype patch for further<br>
> review/discussion.<br>
<br>
> Thanks,<br>
<br>
> - Vaivaswatha<br>
<br>
> On Sat, Dec 12, 2015 at 3:21 AM, Hal Finkel via llvm-dev <<br>
> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a> > wrote:<br>
<br>
> > ----- Original Message -----<br>
><br>
<br>
> > > From: "Joseph Tremoulet" < <a href="mailto:jotrem@microsoft.com" target="_blank">jotrem@microsoft.com</a> ><br>
><br>
> > > To: "Hal Finkel" < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> >, "Mehdi Amini" <<br>
> > > <a href="mailto:mehdi.amini@apple.com" target="_blank">mehdi.amini@apple.com</a> ><br>
><br>
> > > Cc: "llvm-dev" < <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a> ><br>
><br>
> > > Sent: Friday, December 11, 2015 3:35:38 PM<br>
><br>
> > > Subject: RE: [llvm-dev] RFC: New function attribute<br>
> > > HasInaccessibleState<br>
><br>
> > ><br>
><br>
> > > Yeah, I'd agree (rewording slightly) that "state which is only<br>
><br>
> > > modified by external code" is well-defined (and likely to be in<br>
> > > the<br>
><br>
> > > "other" bucket of any individual analysis). I do, as other have,<br>
><br>
> > > find it odd to redefine readonly and argmemonly in terms of this<br>
> > > and<br>
><br>
> > > require its propagation up the call graph, as opposed to<br>
> > > introducing<br>
><br>
> > > new "writes only external" and "writes only arg and external"<br>
><br>
> > > attributes.<br>
><br>
<br>
> > As I stated in some other e-mail, I'm against adding this as a<br>
> > "subtractive" attribute. We need to add these as new attributes,<br>
> > not<br>
> > as an attribute that makes readonly a little less read only. I<br>
> > believe we're in agreement on this point.<br>
><br>
<br>
> > -Hal<br>
><br>
<br>
> > ><br>
><br>
> > > Thanks<br>
><br>
> > > -Joseph<br>
><br>
> > ><br>
><br>
> > > -----Original Message-----<br>
><br>
> > > From: Hal Finkel [mailto: <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> ]<br>
><br>
> > > Sent: Friday, December 11, 2015 4:00 PM<br>
><br>
> > > To: Mehdi Amini < <a href="mailto:mehdi.amini@apple.com" target="_blank">mehdi.amini@apple.com</a> ><br>
><br>
> > > Cc: llvm-dev < <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a> >; Joseph Tremoulet<br>
><br>
> > > < <a href="mailto:jotrem@microsoft.com" target="_blank">jotrem@microsoft.com</a> ><br>
><br>
> > > Subject: Re: [llvm-dev] RFC: New function attribute<br>
><br>
> > > HasInaccessibleState<br>
><br>
> > ><br>
><br>
> > > ----- Original Message -----<br>
><br>
> > > > From: "Mehdi Amini" < <a href="mailto:mehdi.amini@apple.com" target="_blank">mehdi.amini@apple.com</a> ><br>
><br>
> > > > To: "Joseph Tremoulet" < <a href="mailto:jotrem@microsoft.com" target="_blank">jotrem@microsoft.com</a> ><br>
><br>
> > > > Cc: "Hal Finkel" < <a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a> >, "llvm-dev"<br>
><br>
> > > > < <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a> ><br>
><br>
> > > > Sent: Friday, December 11, 2015 1:28:05 PM<br>
><br>
> > > > Subject: Re: [llvm-dev] RFC: New function attribute<br>
><br>
> > > > HasInaccessibleState<br>
><br>
> > > ><br>
><br>
> > > ><br>
><br>
> > > > > On Dec 11, 2015, at 11:16 AM, Joseph Tremoulet<br>
><br>
> > > > > < <a href="mailto:jotrem@microsoft.com" target="_blank">jotrem@microsoft.com</a> > wrote:<br>
><br>
> > > > ><br>
><br>
> > > > > <<<<br>
><br>
> > > > > I may misunderstand, but it seems to me that this solves only<br>
><br>
> > > > > query<br>
><br>
> > > > > for aliasing with a pointer known to be pointing only to<br>
> > > > > globals<br>
><br>
> > > > > defined in the current compilation unit.<br>
><br>
> > > > > For any pointer which "may point somewhere else”, you won’t<br>
> > > > > be<br>
><br>
> > > > > able<br>
><br>
> > > > > to resolve the non-aliasing with the “internal state” for<br>
><br>
> > > > > malloc/free, right?<br>
><br>
> > > > ><br>
><br>
> > > > > To take the original example in this thread:<br>
><br>
> > > > ><br>
><br>
> > > > > int *x = malloc(4);<br>
><br>
> > > > > *x = 2;<br>
><br>
> > > > > int *y = malloc(4);<br>
><br>
> > > > > *y = 4;<br>
><br>
> > > > ><br>
><br>
> > > > > A pointer analysis can solve this case, but I’m not sure it<br>
> > > > > scale<br>
><br>
> > > > > inter procedurally and will have a limited impact outside of<br>
> > > > > LTO<br>
><br>
> > > > > anyway.<br>
><br>
> > > > >>>><br>
><br>
> > > > ><br>
><br>
> > > > > I think you're understanding correctly, but I don't<br>
> > > > > understand<br>
><br>
> > > > > what<br>
><br>
> > > > > you're saying will go badly with the malloc example. Quoting<br>
> > > > > the<br>
><br>
> > > > > start of the thread:<br>
><br>
> > > > ><br>
><br>
> > > > > <<<<br>
><br>
> > > > > The intention behind introducing this attribute is to relax<br>
> > > > > the<br>
><br>
> > > > > conditions in GlobalsAA as below:<br>
><br>
> > > > > (this code is in GlobalsAAResult::AnalyzeCallGraph)<br>
><br>
> > > > > if (F->isDeclaration()) {<br>
><br>
> > > > > // Try to get mod/ref behaviour from function attributes.<br>
><br>
> > > > > - if (F->doesNotAccessMemory()) {<br>
><br>
> > > > > + if (F->doesNotAccessMemory() ||<br>
><br>
> > > > > F->onlyAccessesArgMemory()) {<br>
><br>
> > > > > // Can't do better than that!<br>
><br>
> > > > > } else if (F->onlyReadsMemory()) {<br>
><br>
> > > > > FunctionEffect |= Ref;<br>
><br>
> > > > > if (!F->isIntrinsic())<br>
><br>
> > > > > // This function might call back into the module and<br>
><br>
> > > > > read a global -<br>
><br>
> > > > > // consider every global as possibly being read by<br>
><br>
> > > > > this<br>
><br>
> > > > > function.<br>
><br>
> > > > > FR.MayReadAnyGlobal = true;<br>
><br>
> > > > > } else {<br>
><br>
> > > > > FunctionEffect |= ModRef;<br>
><br>
> > > > > // Can't say anything useful unless it's an intrinsic -<br>
><br>
> > > > > they don't<br>
><br>
> > > > > // read or write global variables of the kind<br>
><br>
> > > > > considered<br>
><br>
> > > > > here.<br>
><br>
> > > > > KnowNothing = !F->isIntrinsic();<br>
><br>
> > > > > }<br>
><br>
> > > > > continue;<br>
><br>
> > > > > }<br>
><br>
> > > > > This relaxation allows functions that (transitively) call<br>
> > > > > library<br>
><br>
> > > > > functions (such as printf/malloc) to still maintain and<br>
> > > > > propagate<br>
><br>
> > > > > GlobalsAA info. In general, this adds more precision to the<br>
><br>
> > > > > description of these functions.<br>
><br>
> > > > > Concerns regarding impact on other optimizations (I'm<br>
> > > > > repeating<br>
> > > > > a<br>
><br>
> > > > > few examples that Hal mentioned earlier).<br>
><br>
> > > > ><br>
><br>
> > > > > 1.<br>
><br>
> > > > >> A readnone function is one whose output is a function only<br>
> > > > >> of<br>
><br>
> > > > >> its<br>
><br>
> > > > >> inputs, and if you have this:<br>
><br>
> > > > >><br>
><br>
> > > > >> int *x = malloc(4);<br>
><br>
> > > > >> *x = 2;<br>
><br>
> > > > >> int *y = malloc(4);<br>
><br>
> > > > >> *y = 4;<br>
><br>
> > > > >> you certainly don't want EarlyCSE to replace the second call<br>
> > > > >> to<br>
><br>
> > > > >> malloc with the result of the first (which it will happily<br>
> > > > >> do<br>
> > > > >> if<br>
><br>
> > > > >> you mark malloc as readnone).<br>
><br>
> > > > >>>><br>
><br>
> > > > ><br>
><br>
> > > > > It sounded like improving GlobalsAA (and thus disambiguation<br>
><br>
> > > > > against<br>
><br>
> > > > > globals) was the explicit goal, and that the concern with the<br>
><br>
> > > > > malloc<br>
><br>
> > > > > case was that you don't want EarlyCSE to start combining<br>
> > > > > those<br>
><br>
> > > > > two<br>
><br>
> > > > > calls; I may be misunderstanding the code, but I wouldn't<br>
> > > > > expect<br>
><br>
> > > > > EarlyCSE to start combining those calls just because they<br>
> > > > > have<br>
> > > > > a<br>
><br>
> > > > > new<br>
><br>
> > > > > meaningful-only-to-GlobalsAA "almost-readnone" attribute.<br>
><br>
> > > ><br>
><br>
> > > > Sure, my point is not that your solution would enable CSE where<br>
> > > > we<br>
><br>
> > > > don’t want, but rather that it is not as powerful as what the<br>
><br>
> > > > attribute “HasInaccessibleState” would model, which I saw as<br>
> > > > "this<br>
><br>
> > > > function might access globals, but none of these globals can<br>
> > > > alias<br>
><br>
> > > > with any memory location accessible from the IR being<br>
> > > > optimized”.<br>
><br>
> > ><br>
><br>
> > > This is also, essentially, what I had in mind. I think it is<br>
><br>
> > > sufficiently well defined in this form.<br>
><br>
> > ><br>
><br>
> > > -Hal<br>
><br>
> > ><br>
><br>
> > > > For instance:<br>
><br>
> > > ><br>
><br>
> > > > void foo(int *x) {<br>
><br>
> > > > int *y = malloc(4);<br>
><br>
> > > > *x = 2;<br>
><br>
> > > > }<br>
><br>
> > > ><br>
><br>
> > > > If you don’t know anything about x, can you execute the write<br>
> > > > to<br>
> > > > *x<br>
><br>
> > > > before the call to malloc?<br>
><br>
> > > > This is something that the HasInaccessibleState would allow,<br>
> > > > but<br>
> > > > I<br>
><br>
> > > > don’t believe would be possible with your categorization.<br>
><br>
> > > ><br>
><br>
> > > > I’m don’t know how much it matters in practice, but I’d rather<br>
> > > > be<br>
><br>
> > > > sure<br>
><br>
> > > > we’re on the same track about the various tradeoff.<br>
><br>
> > > ><br>
><br>
> > > > —<br>
><br>
> > > > Mehdi<br>
><br>
> > > ><br>
><br>
> > > ><br>
><br>
> > > ><br>
><br>
> > > > ><br>
><br>
> > > > ><br>
><br>
> > > > > To the larger point of whether there are other similar cases<br>
> > > > > that<br>
><br>
> > > > > extending GlobalsAA wouldn't allow us to optimize -- yes,<br>
><br>
> > > > > certainly.<br>
><br>
> > > > > I'm just saying that I think that the notion of "external<br>
> > > > > state"<br>
><br>
> > > > > is<br>
><br>
> > > > > much easier to define in the context of a particular analysis<br>
><br>
> > > > > than<br>
><br>
> > > > > the IR as a whole, and that I'd expect that coordinating the<br>
><br>
> > > > > notion<br>
><br>
> > > > > across analyses would require methods on the analysis API<br>
><br>
> > > > > explicitly<br>
><br>
> > > > > for that coordination.<br>
><br>
> > > > ><br>
><br>
> > > > ><br>
><br>
> > > > ><br>
><br>
> > > > > —<br>
><br>
> > > > > Mehdi<br>
><br>
> > > > ><br>
><br>
> > > ><br>
><br>
> > > ><br>
><br>
> > ><br>
><br>
> > > --<br>
><br>
> > > Hal Finkel<br>
><br>
> > > Assistant Computational Scientist<br>
><br>
> > > Leadership Computing Facility<br>
><br>
> > > Argonne National Laboratory<br>
><br>
> > ><br>
><br>
<br>
> > --<br>
><br>
> > Hal Finkel<br>
><br>
> > Assistant Computational Scientist<br>
><br>
> > Leadership Computing Facility<br>
><br>
> > Argonne National Laboratory<br>
><br>
> > _______________________________________________<br>
><br>
> > LLVM Developers mailing list<br>
><br>
> > <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
><br>
> > <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
><br>
<br>
</div></div>--<br>
<div><div><br>
--<br>
Hal Finkel<br>
Assistant Computational Scientist<br>
Leadership Computing Facility<br>
Argonne National Laboratory<br>
</div></div></blockquote></div><br></div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>
</div></div></blockquote></div><br></div>