Joseph Tremoulet via llvm-dev
2015-Dec-09 15:32 UTC
[llvm-dev] RFC: New function attribute HasInaccessibleState
Sigh... let me try that last part again: Maybe GlobalsAA and/or a GlobalsAA-centric attribution pass could partition writes as: 1. Stores to local allocas 2. Stores through pointer parameters 3. Stores to globals defined in this compilation unit 4. Other Attributing functions with attributes: readonly: only writes of type 1 argmemonly: only writes of type 1/2 almost-readonly: only writes of type 1/4 almost-argmemonly: only writes of type 1/2/4 and when visiting a call instruction to determine what sort of writes it entails: - calls to almost-readonly functions and almost-argmemonly functions imply a write of type 4 - calls to argmemonly functions and almost-argmemonly functions may imply a write of any type depending what we know about their arguments This would allow deducing aliasing relationships: A. (global defined in this compilation unit) vs (call to almost-readonly function) => no-alias B. (global defined in this compilation unit) vs (call to almost-argmemonly function), if we know (via escape analysis or whatever) that the address of the global isn't passed as an argument to the call => no-alias But "almost-readonly" and "almost-argmemonly" would differ from readonly and argmemonly in that C. (call to almost-readonly function) vs (call to almost-readonly function) => may-alias D. (call to almost-readonly function) vs (call to almost-argmemonly function) => may-alias E. (call to almost-argmemonly function) vs (call to almost-argmemonly function), even if we know their arguments have disjoint points-to sets => may-alias and then I think we could soundly annotate externally-defined printf as almost-argmemonly, malloc as almost-readonly, etc, and gain the desired optimizations by way of alias rules A and B And, of course, that's pretty much what was already proposed, since we could do this by having a special pseudo-global representing #4, so now I think my key points are: - we'd want to assume a write to the pseudo-global for any operation we couldn't prove only made writes of type 1/2/3 - "I only write the pseudo-global" is a useful annotation (== "almost-readonly") - "I only write the pseudo-global and my pointer parameters" is also useful (== "almost-argmemonly") - I'd expect that generalizing this to have a common notion of "external pseudo thingamajig" across analyses would require adjusting the APIs so they can communicate in a fine-grained way what is or isn't in their external thingamajig, and also whether may-aliases they report involve interference via their external thingamajig or not. Thanks -Joseph -----Original Message----- From: Joseph Tremoulet Sent: Tuesday, December 8, 2015 1:12 PM To: Joseph Tremoulet <jotrem at microsoft.com>; Hal Finkel <hfinkel at anl.gov>; Mehdi Amini <mehdi.amini at apple.com> Cc: llvm-dev <llvm-dev at lists.llvm.org> Subject: RE: [llvm-dev] RFC: New function attribute HasInaccessibleState [sorry for the re-send; fixed a couple critical typos inline] We used a similar thing in the phx compiler. We called it "ExternalMemoryTag". It was a name for "all the program state that doesn't have another name", and in phx (unlike LLVM) it was easy to define what "has another name" meant since we kept an explicit universe of names in our alias metadata. The inferences were flipped the other way, though; being able to access "external memory" was the default assumption, and what the compiler had to prove/propagate was that some functions (whose definitions could be inspected) did NOT touch "external memory". Trying to translate that idea to LLVM, I'm having trouble getting around the lack of an explicit universe of named storage locations. Different alias analyses of course have their own ways of partitioning program storage, and "external memory" (in the sense I'm used to it) is the intersection of each analysis' notion of "other storage I'm not modeling precisely". So e.g. in phx we'd start with a heap-insensitive analysis that would leave the entire heap in "external memory", but then running a heap-sensitive analysis would "chip away" at it, carving out a name for each allocation site and redefining "external memory" to exclude those. The difficulty translating this to LLVM is that when you have different analyses all summarizing the same function definition, each one could tell you "I have specific names for all the things this function touches" or not, but there's no useful way to combine those results, since what you want to know is whether all accessed storage is covered by the union of all the specific names. You'd need something along the lines of an API on each alias analysis that would look at an individual instruction and tell you whether it has specific names for all the storage accessed by that instruction; then the function could be summarized as "this doesn't touch anything we don't have a specific name for" if every instruction had at least one analysis claim to have a name for it. Then when querying for aliasing between two calls, the set of returns could be expanded so that each analysis could report "may alias because they both might touch something I have a specific name for" as one possible answer, and "may alias because neither touches anything I have a specific name for (but both might touch something else)" as another possible answer -- then the calls don't alias if the function was summarized as "this doesn't touch anything we don't have a specific name for" and all the analyses report "may alias because neither touches anything I have a specific name for". The other way would of course be to make one analysis powerful enough to catch the cases we're concerned with. Would it be workable to have GlobalsAA look through the stores (and other mutating operations) in a function to see if they're: 1. a store to a local alloca 2. a store to a global defined in this compilation unit 3. a store through a pointer parameter 4. a call to a function that it has inferred is "ReadOnly-like" (or that is actually readonly) 5. a call to a function that it has inferred is "ArgMemOnly-like" (or that is actually argmemonly) 6. other so that: - if it gets through a function and all modifications are of type 1 or 4, it could summarize that function as "ReadOnly-like"; it could report two calls to "ReadOnly-like" functions as not aliasing in their writes, and report calls to "ReadOnly-like" functions as not modifying any global in the current compilation unit (i.e. any global it can be asked about) - if it gets through a function and all modifications are of type 1, 3, 4, or 5, it could summarize that function as "ArgMemOnly-like"; it could report a global (in the current compilation unit) as not modified by an "ArgMemOnly-like" so long as it knows the global's address isn't passed as an argument to that function (which I hope is what its notion of "escaped" can tell it) ? Then IIUC we could have it recognize some libcalls and treat printf as ArgMemOnly-like (so long as printf's definition is not in the current compilation unit), treat free as ReadOnly-like (so long as likewise), etc. I'm probably mixing up details around how lib calls are analyzed and how GlobalsAA propagates information, but I think they key points I'm making are that we may be looking for attributes that would only mean anything to GlobalsAA, and that what they would mean to GlobalsAA may be the same things that "ReadOnly" and "ArgMemOnly" already mean to it. Thanks -Joseph -----Original Message----- From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Hal Finkel via llvm-dev Sent: Friday, December 4, 2015 7:33 PM To: Mehdi Amini <mehdi.amini at apple.com> Cc: LLVM Dev <llvm-dev at lists.llvm.org> Subject: Re: [llvm-dev] RFC: New function attribute HasInaccessibleState ----- Original Message -----> From: "Mehdi Amini" <mehdi.amini at apple.com> > To: "Hal Finkel" <hfinkel at anl.gov> > Cc: "Vaivaswatha Nagaraj" <vn at compilertree.com>, "LLVM Dev" > <llvm-dev at lists.llvm.org> > Sent: Friday, December 4, 2015 12:47:00 PM > Subject: Re: [llvm-dev] RFC: New function attribute > HasInaccessibleState > > > > On Dec 4, 2015, at 10:33 AM, Hal Finkel via llvm-dev > > <llvm-dev at lists.llvm.org> wrote: > > > > ----- Original Message ----- > >> From: "Vaivaswatha Nagaraj" <vn at compilertree.com> > >> To: "James Molloy" <james at jamesmolloy.co.uk>, "Hal Finkel" > >> <hfinkel at anl.gov> > >> Cc: "LLVM Dev" <llvm-dev at lists.llvm.org> > >> Sent: Friday, December 4, 2015 12:28:03 PM > >> Subject: Re: [llvm-dev] RFC: New function attribute > >> HasInaccessibleState > >> > >> that would be an escaping global, and as far as I know is handled > >> separately in GlobalsAA (AnalyzeUsesOfPointer checks if a global is > >> used as operand to a function) > >> > > > > More generally, I think this attribute is supposed to mean, "this > > function might access globals, but none of these globals are things > > you can name in the IR being optimized." You might, of course, pass > > in aliasing memory as a parameter, but that's a separate matter. > > I’m not what "things you can name in the IR” mean exactly, would this > be equivalent to "none of these globals can alias with any memory > location accessible from the IR being optimized”? > > To come back to what I phrased earlier, this effectively split the > state in two distinct parts, is this enough in all cases? Would there > be some need/benefit to model more partitions?I agree this is a good question. I don't have any use cases right now where modeling multiple external states would be useful. There might be a relationship to our long-standing problem of modeling errno, but that does not quite fit into this model, because errno is sometimes implemented as a global. -Hal> > Thanks, > > — > Mehdi > > > > >> > >> On December 4, 2015 11:47:20 PM GMT+05:30, James Molloy > >> <james at jamesmolloy.co.uk> wrote: > >> > >> It is if one of the operands is or can alias a global ? > >> > >> > >> On Fri, 4 Dec 2015 at 18:16, Vaivaswatha Nagaraj < > >> vn at compilertree.com > wrote: > >> > >> > >> > >> writing into operands is not the same as writing to globals right? > >> I > >> added printf in the same category since we were discussing writing > >> to globals. > >> > >> > >> > >> On December 4, 2015 11:34:10 PM GMT+05:30, James Molloy < > >> james at jamesmolloy.co.uk > wrote: > >> > >> > >> Hi, > >> > >> > >> I just want to reiterate: printf and friends do *not* fall into > >> this category as they can write to their operands (unless you parse > >> and check the format string for %n). > >> > >> > >> James > >> > >> > >> On Fri, 4 Dec 2015 at 17:53 Vaivaswatha Nagaraj via llvm-dev < > >> llvm-dev at lists.llvm.org > wrote: > >> > >> > >> > >> > >> > >>> Most of the time you don't have the entire call graph information. > >>> Imagine that you are developing a module that is a part of a > >>> larger project. > >> > >> > >> I now understand the concern. It looks to me that we will need to > >> set the flag by default to all functions whose definitions aren't > >> available (external), and then propagate from there on. I don't see > >> any optimizations being inhibited by such a setting, so it should > >> be okay. > >> > >> > >> > >>> I think we need to go back and look at the underlying use case (as > >>> I understand it): GlobalAA should be able to figure out that calls > >>> to malloc/free don't touch global variables visible to the > >>> optimizer. > >>> How do we address this problem? > >> > >> > >> Yes, this is the primary concern. Most libc functions (including > >> printf, malloc, free) fall into the same category. > >> > >> > >> > >> > >> > >> > >> > >> > >> > >> > >> - Vaivaswatha > >> > >> > >> > >> On Fri, Dec 4, 2015 at 11:12 PM, Hal Finkel < hfinkel at anl.gov > > >> wrote: > >> > >> > >> ----- Original Message ----- > >>> From: "Vaivaswatha Nagaraj via llvm-dev" < llvm-dev at lists.llvm.org > >>>> > >>> To: "Krzysztof Parzyszek" < kparzysz at codeaurora.org > > >>> Cc: "LLVM Dev" < llvm-dev at lists.llvm.org > > >>> Sent: Friday, December 4, 2015 11:21:03 AM > >>> Subject: Re: [llvm-dev] RFC: New function attribute > >>> HasInaccessibleState > >> > >>>>> In the case of user-defined allocation functions, the > >>>>> definitions for those functions are available > >> > >>>> Are they? probably not unless you're in an LTO build. > >> > >>> Yes, I'm assuming an LTO build. > >> > >> The concerns around LTO here, while legitimate, apply only to a > >> very-specific kind of LTO: An LTO which includes the definitions of > >> the libc. This is actually quite tricky to support, semantically, > >> and already breaks our malloc aliasing assumptions. There are many > >> legitimate uses of LLVM, both for statically-compiled code and for > >> JIT'd code, that depend on a visibility boundary between certain > >> core runtime services and the user code being compiled to provide > >> for effective optimization. > >> > >> So, yes, this will break LTO when you include libc itself in the > >> optimization process. We already don't support this (we'd need, at > >> least, to adjust our malloc noalias assumptions, if not many other > >> things). I don't think this is a major concern. > >> > >> I think we need to go back and look at the underlying use case (as > >> I understand it): GlobalAA should be able to figure out that calls > >> to malloc/free don't touch global variables visible to the > >> optimizer. > >> How do we address this problem? > >> > >> Thanks again, > >> Hal > >> > >> ... > >> > >>> _______________________________________________ > >>> LLVM Developers mailing list > >>> llvm-dev at lists.llvm.org > >>> https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fli > >>> sts.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev&data=01%7c0 > >>> 1%7cjotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72 > >>> f988bf86f141af91ab2d7cd011db47%7c1&sdata=n61OMLL2IjHgbhxfk14QNboJi > >>> MdHphjpB5DlXBIqKso%3d > >> > >> -- > >> > >> > >> > >> -- > >> Hal Finkel > >> Assistant Computational Scientist > >> Leadership Computing Facility > >> Argonne National Laboratory > >> > >> _______________________________________________ > >> LLVM Developers mailing list > >> llvm-dev at lists.llvm.org > >> https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flis > >> ts.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev&data=01%7c01% > >> 7cjotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72f98 > >> 8bf86f141af91ab2d7cd011db47%7c1&sdata=n61OMLL2IjHgbhxfk14QNboJiMdHp > >> hjpB5DlXBIqKso%3d > >> > >> > >> -- > >> Sent from my Android device with K-9 Mail. Please excuse my > >> brevity. > >> -- > >> Sent from my Android device with K-9 Mail. Please excuse my > >> brevity. > > > > -- > > Hal Finkel > > Assistant Computational Scientist > > Leadership Computing Facility > > Argonne National Laboratory > > _______________________________________________ > > LLVM Developers mailing list > > llvm-dev at lists.llvm.org > > https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flist > > s.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev&data=01%7c01%7c > > jotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72f988bf > > 86f141af91ab2d7cd011db47%7c1&sdata=n61OMLL2IjHgbhxfk14QNboJiMdHphjpB > > 5DlXBIqKso%3d > >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory _______________________________________________ LLVM Developers mailing list llvm-dev at lists.llvm.org https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flists.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev%0a&data=01%7c01%7cjotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=Gh14ReFy%2bwjHGJqP%2bV22kWRNOvd6S2WFJX3Cka%2bwRaw%3d _______________________________________________ LLVM Developers mailing list llvm-dev at lists.llvm.org https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flists.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev%0a&data=01%7c01%7cjotrem%40microsoft.com%7c1ac7b4dd642a408033a408d2fff891eb%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=YsWMlFxWi2ZmJp%2fb%2fcxScUqLW7nOy43IyDC4Zfsut9U%3d
Philip Reames via llvm-dev
2015-Dec-10 23:54 UTC
[llvm-dev] RFC: New function attribute HasInaccessibleState
On 12/09/2015 07:32 AM, Joseph Tremoulet via llvm-dev wrote:> Sigh... let me try that last part again: > > Maybe GlobalsAA and/or a GlobalsAA-centric attribution pass could partition writes as: > 1. Stores to local allocas > 2. Stores through pointer parameters > 3. Stores to globals defined in this compilation unit > 4. Other > > Attributing functions with attributes: > readonly: only writes of type 1 > argmemonly: only writes of type 1/2 > almost-readonly: only writes of type 1/4 > almost-argmemonly: only writes of type 1/2/4Aside from bikesheding, I like the notions your describing here. Bikesheed wise, adding "internalonly" (analogous to argmemonly) and "externalonly" combined with our existing attributes appears to give all the combinations you mention.> > and when visiting a call instruction to determine what sort of writes it entails: > - calls to almost-readonly functions and almost-argmemonly functions imply a write of type 4 > - calls to argmemonly functions and almost-argmemonly functions may imply a write of any type depending what we know about their arguments > > This would allow deducing aliasing relationships: > A. (global defined in this compilation unit) vs (call to almost-readonly function) => no-alias > B. (global defined in this compilation unit) vs (call to almost-argmemonly function), if we know (via escape analysis or whatever) that the address of the global isn't passed as an argument to the call => no-alias > > But "almost-readonly" and "almost-argmemonly" would differ from readonly and argmemonly in that > C. (call to almost-readonly function) vs (call to almost-readonly function) => may-alias > D. (call to almost-readonly function) vs (call to almost-argmemonly function) => may-alias > E. (call to almost-argmemonly function) vs (call to almost-argmemonly function), even if we know their arguments have disjoint points-to sets => may-alias > > and then I think we could soundly annotate externally-defined printf as almost-argmemonly, malloc as almost-readonly, etc, and gain the desired optimizations by way of alias rules A and BI will admit I got lost in this bit. I think I got your key point above, but I might have missed something in this bit.> > And, of course, that's pretty much what was already proposed, since we could do this by having a special pseudo-global representing #4, so now I think my key points are: > - we'd want to assume a write to the pseudo-global for any operation we couldn't prove only made writes of type 1/2/3 > - "I only write the pseudo-global" is a useful annotation (== "almost-readonly") > - "I only write the pseudo-global and my pointer parameters" is also useful (== "almost-argmemonly") > - I'd expect that generalizing this to have a common notion of "external pseudo thingamajig" across analyses would require adjusting the APIs so they can communicate in a fine-grained way what is or isn't in their external thingamajig, and also whether may-aliases they report involve interference via their external thingamajig or not. > > Thanks > -Joseph > > > -----Original Message----- > From: Joseph Tremoulet > Sent: Tuesday, December 8, 2015 1:12 PM > To: Joseph Tremoulet <jotrem at microsoft.com>; Hal Finkel <hfinkel at anl.gov>; Mehdi Amini <mehdi.amini at apple.com> > Cc: llvm-dev <llvm-dev at lists.llvm.org> > Subject: RE: [llvm-dev] RFC: New function attribute HasInaccessibleState > > [sorry for the re-send; fixed a couple critical typos inline] > > We used a similar thing in the phx compiler. We called it "ExternalMemoryTag". It was a name for "all the program state that doesn't have another name", and in phx (unlike LLVM) it was easy to define what "has another name" meant since we kept an explicit universe of names in our alias metadata. The inferences were flipped the other way, though; being able to access "external memory" was the default assumption, and what the compiler had to prove/propagate was that some functions (whose definitions could be inspected) did NOT touch "external memory". > > Trying to translate that idea to LLVM, I'm having trouble getting around the lack of an explicit universe of named storage locations. Different alias analyses of course have their own ways of partitioning program storage, and "external memory" (in the sense I'm used to it) is the intersection of each analysis' notion of "other storage I'm not modeling precisely". So e.g. in phx we'd start with a heap-insensitive analysis that would leave the entire heap in "external memory", but then running a heap-sensitive analysis would "chip away" at it, carving out a name for each allocation site and redefining "external memory" to exclude those. The difficulty translating this to LLVM is that when you have different analyses all summarizing the same function definition, each one could tell you "I have specific names for all the things this function touches" or not, but there's no useful way to combine those results, since what you want to know is whether all accessed storage is covered by the union of all the specific names. You'd need something along the lines of an API on each alias analysis that would look at an individual instruction and tell you whether it has specific names for all the storage accessed by that instruction; then the function could be summarized as "this doesn't touch anything we don't have a specific name for" if every instruction had at least one analysis claim to have a name for it. Then when querying for aliasing between two calls, the set of returns could be expanded so that each analysis could report "may alias because they both might touch something I have a specific name for" as one possible answer, and "may alias because neither touches anything I have a specific name for (but both might touch something else)" as another possible answer -- then the calls don't alias if the function was summarized as "this doesn't touch anything we don't have a specific name for" and all the analyses report "may alias because neither touches anything I have a specific name for". > > The other way would of course be to make one analysis powerful enough to catch the cases we're concerned with. Would it be workable to have GlobalsAA look through the stores (and other mutating operations) in a function to see if they're: > > 1. a store to a local alloca > 2. a store to a global defined in this compilation unit 3. a store through a pointer parameter 4. a call to a function that it has inferred is "ReadOnly-like" (or that is actually readonly) 5. a call to a function that it has inferred is "ArgMemOnly-like" (or that is actually argmemonly) 6. other > > so that: > - if it gets through a function and all modifications are of type 1 or 4, it could summarize that function as "ReadOnly-like"; it could report two calls to "ReadOnly-like" functions as not aliasing in their writes, and report calls to "ReadOnly-like" functions as not modifying any global in the current compilation unit (i.e. any global it can be asked about) > - if it gets through a function and all modifications are of type 1, 3, 4, or 5, it could summarize that function as "ArgMemOnly-like"; it could report a global (in the current compilation unit) as not modified by an "ArgMemOnly-like" so long as it knows the global's address isn't passed as an argument to that function (which I hope is what its notion of "escaped" can tell it) ? > > Then IIUC we could have it recognize some libcalls and treat printf as ArgMemOnly-like (so long as printf's definition is not in the current compilation unit), treat free as ReadOnly-like (so long as likewise), etc. > > I'm probably mixing up details around how lib calls are analyzed and how GlobalsAA propagates information, but I think they key points I'm making are that we may be looking for attributes that would only mean anything to GlobalsAA, and that what they would mean to GlobalsAA may be the same things that "ReadOnly" and "ArgMemOnly" already mean to it. > > Thanks > -Joseph > > -----Original Message----- > From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Hal Finkel via llvm-dev > Sent: Friday, December 4, 2015 7:33 PM > To: Mehdi Amini <mehdi.amini at apple.com> > Cc: LLVM Dev <llvm-dev at lists.llvm.org> > Subject: Re: [llvm-dev] RFC: New function attribute HasInaccessibleState > > ----- Original Message ----- >> From: "Mehdi Amini" <mehdi.amini at apple.com> >> To: "Hal Finkel" <hfinkel at anl.gov> >> Cc: "Vaivaswatha Nagaraj" <vn at compilertree.com>, "LLVM Dev" >> <llvm-dev at lists.llvm.org> >> Sent: Friday, December 4, 2015 12:47:00 PM >> Subject: Re: [llvm-dev] RFC: New function attribute >> HasInaccessibleState >> >> >>> On Dec 4, 2015, at 10:33 AM, Hal Finkel via llvm-dev >>> <llvm-dev at lists.llvm.org> wrote: >>> >>> ----- Original Message ----- >>>> From: "Vaivaswatha Nagaraj" <vn at compilertree.com> >>>> To: "James Molloy" <james at jamesmolloy.co.uk>, "Hal Finkel" >>>> <hfinkel at anl.gov> >>>> Cc: "LLVM Dev" <llvm-dev at lists.llvm.org> >>>> Sent: Friday, December 4, 2015 12:28:03 PM >>>> Subject: Re: [llvm-dev] RFC: New function attribute >>>> HasInaccessibleState >>>> >>>> that would be an escaping global, and as far as I know is handled >>>> separately in GlobalsAA (AnalyzeUsesOfPointer checks if a global is >>>> used as operand to a function) >>>> >>> More generally, I think this attribute is supposed to mean, "this >>> function might access globals, but none of these globals are things >>> you can name in the IR being optimized." You might, of course, pass >>> in aliasing memory as a parameter, but that's a separate matter. >> I’m not what "things you can name in the IR” mean exactly, would this >> be equivalent to "none of these globals can alias with any memory >> location accessible from the IR being optimized”? >> >> To come back to what I phrased earlier, this effectively split the >> state in two distinct parts, is this enough in all cases? Would there >> be some need/benefit to model more partitions? > I agree this is a good question. I don't have any use cases right now where modeling multiple external states would be useful. > > There might be a relationship to our long-standing problem of modeling errno, but that does not quite fit into this model, because errno is sometimes implemented as a global. > > -Hal > >> Thanks, >> >> — >> Mehdi >> >>>> On December 4, 2015 11:47:20 PM GMT+05:30, James Molloy >>>> <james at jamesmolloy.co.uk> wrote: >>>> >>>> It is if one of the operands is or can alias a global ? >>>> >>>> >>>> On Fri, 4 Dec 2015 at 18:16, Vaivaswatha Nagaraj < >>>> vn at compilertree.com > wrote: >>>> >>>> >>>> >>>> writing into operands is not the same as writing to globals right? >>>> I >>>> added printf in the same category since we were discussing writing >>>> to globals. >>>> >>>> >>>> >>>> On December 4, 2015 11:34:10 PM GMT+05:30, James Molloy < >>>> james at jamesmolloy.co.uk > wrote: >>>> >>>> >>>> Hi, >>>> >>>> >>>> I just want to reiterate: printf and friends do *not* fall into >>>> this category as they can write to their operands (unless you parse >>>> and check the format string for %n). >>>> >>>> >>>> James >>>> >>>> >>>> On Fri, 4 Dec 2015 at 17:53 Vaivaswatha Nagaraj via llvm-dev < >>>> llvm-dev at lists.llvm.org > wrote: >>>> >>>> >>>> >>>> >>>> >>>>> Most of the time you don't have the entire call graph information. >>>>> Imagine that you are developing a module that is a part of a >>>>> larger project. >>>> >>>> I now understand the concern. It looks to me that we will need to >>>> set the flag by default to all functions whose definitions aren't >>>> available (external), and then propagate from there on. I don't see >>>> any optimizations being inhibited by such a setting, so it should >>>> be okay. >>>> >>>> >>>> >>>>> I think we need to go back and look at the underlying use case (as >>>>> I understand it): GlobalAA should be able to figure out that calls >>>>> to malloc/free don't touch global variables visible to the >>>>> optimizer. >>>>> How do we address this problem? >>>> >>>> Yes, this is the primary concern. Most libc functions (including >>>> printf, malloc, free) fall into the same category. >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> - Vaivaswatha >>>> >>>> >>>> >>>> On Fri, Dec 4, 2015 at 11:12 PM, Hal Finkel < hfinkel at anl.gov > >>>> wrote: >>>> >>>> >>>> ----- Original Message ----- >>>>> From: "Vaivaswatha Nagaraj via llvm-dev" < llvm-dev at lists.llvm.org >>>>> To: "Krzysztof Parzyszek" < kparzysz at codeaurora.org > >>>>> Cc: "LLVM Dev" < llvm-dev at lists.llvm.org > >>>>> Sent: Friday, December 4, 2015 11:21:03 AM >>>>> Subject: Re: [llvm-dev] RFC: New function attribute >>>>> HasInaccessibleState >>>>>>> In the case of user-defined allocation functions, the >>>>>>> definitions for those functions are available >>>>>> Are they? probably not unless you're in an LTO build. >>>>> Yes, I'm assuming an LTO build. >>>> The concerns around LTO here, while legitimate, apply only to a >>>> very-specific kind of LTO: An LTO which includes the definitions of >>>> the libc. This is actually quite tricky to support, semantically, >>>> and already breaks our malloc aliasing assumptions. There are many >>>> legitimate uses of LLVM, both for statically-compiled code and for >>>> JIT'd code, that depend on a visibility boundary between certain >>>> core runtime services and the user code being compiled to provide >>>> for effective optimization. >>>> >>>> So, yes, this will break LTO when you include libc itself in the >>>> optimization process. We already don't support this (we'd need, at >>>> least, to adjust our malloc noalias assumptions, if not many other >>>> things). I don't think this is a major concern. >>>> >>>> I think we need to go back and look at the underlying use case (as >>>> I understand it): GlobalAA should be able to figure out that calls >>>> to malloc/free don't touch global variables visible to the >>>> optimizer. >>>> How do we address this problem? >>>> >>>> Thanks again, >>>> Hal >>>> >>>> ... >>>> >>>>> _______________________________________________ >>>>> LLVM Developers mailing list >>>>> llvm-dev at lists.llvm.org >>>>> https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fli >>>>> sts.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev&data=01%7c0 >>>>> 1%7cjotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72 >>>>> f988bf86f141af91ab2d7cd011db47%7c1&sdata=n61OMLL2IjHgbhxfk14QNboJi >>>>> MdHphjpB5DlXBIqKso%3d >>>> -- >>>> >>>> >>>> >>>> -- >>>> Hal Finkel >>>> Assistant Computational Scientist >>>> Leadership Computing Facility >>>> Argonne National Laboratory >>>> >>>> _______________________________________________ >>>> LLVM Developers mailing list >>>> llvm-dev at lists.llvm.org >>>> https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flis >>>> ts.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev&data=01%7c01% >>>> 7cjotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72f98 >>>> 8bf86f141af91ab2d7cd011db47%7c1&sdata=n61OMLL2IjHgbhxfk14QNboJiMdHp >>>> hjpB5DlXBIqKso%3d >>>> >>>> >>>> -- >>>> Sent from my Android device with K-9 Mail. Please excuse my >>>> brevity. >>>> -- >>>> Sent from my Android device with K-9 Mail. Please excuse my >>>> brevity. >>> -- >>> Hal Finkel >>> Assistant Computational Scientist >>> Leadership Computing Facility >>> Argonne National Laboratory >>> _______________________________________________ >>> LLVM Developers mailing list >>> llvm-dev at lists.llvm.org >>> https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flist >>> s.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev&data=01%7c01%7c >>> jotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72f988bf >>> 86f141af91ab2d7cd011db47%7c1&sdata=n61OMLL2IjHgbhxfk14QNboJiMdHphjpB >>> 5DlXBIqKso%3d >> > -- > Hal Finkel > Assistant Computational Scientist > Leadership Computing Facility > Argonne National Laboratory > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flists.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev%0a&data=01%7c01%7cjotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=Gh14ReFy%2bwjHGJqP%2bV22kWRNOvd6S2WFJX3Cka%2bwRaw%3d > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flists.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev%0a&data=01%7c01%7cjotrem%40microsoft.com%7c1ac7b4dd642a408033a408d2fff891eb%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=YsWMlFxWi2ZmJp%2fb%2fcxScUqLW7nOy43IyDC4Zfsut9U%3d > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Sanjoy Das via llvm-dev
2015-Dec-11 01:49 UTC
[llvm-dev] RFC: New function attribute HasInaccessibleState
Joseph Tremoulet via llvm-dev wrote:> Sigh... let me try that last part again: > > Maybe GlobalsAA and/or a GlobalsAA-centric attribution pass could partition writes as: > 1. Stores to local allocas > 2. Stores through pointer parameters > 3. Stores to globals defined in this compilation unit > 4. Other > > Attributing functions with attributes: > readonly: only writes of type 1 > argmemonly: only writes of type 1/2 > almost-readonly: only writes of type 1/4 > almost-argmemonly: only writes of type 1/2/4 > > and when visiting a call instruction to determine what sort of writes it entails: > - calls to almost-readonly functions and almost-argmemonly functions imply a write of type 4Do you mean "readonly and almost-readonly"? -- Sanjoy> - calls to argmemonly functions and almost-argmemonly functions may imply a write of any type depending what we know about their arguments > > This would allow deducing aliasing relationships: > A. (global defined in this compilation unit) vs (call to almost-readonly function) => no-alias > B. (global defined in this compilation unit) vs (call to almost-argmemonly function), if we know (via escape analysis or whatever) that the address of the global isn't passed as an argument to the call => no-alias > > But "almost-readonly" and "almost-argmemonly" would differ from readonly and argmemonly in that > C. (call to almost-readonly function) vs (call to almost-readonly function) => may-alias > D. (call to almost-readonly function) vs (call to almost-argmemonly function) => may-alias > E. (call to almost-argmemonly function) vs (call to almost-argmemonly function), even if we know their arguments have disjoint points-to sets => may-alias > > and then I think we could soundly annotate externally-defined printf as almost-argmemonly, malloc as almost-readonly, etc, and gain the desired optimizations by way of alias rules A and B > > And, of course, that's pretty much what was already proposed, since we could do this by having a special pseudo-global representing #4, so now I think my key points are: > - we'd want to assume a write to the pseudo-global for any operation we couldn't prove only made writes of type 1/2/3 > - "I only write the pseudo-global" is a useful annotation (== "almost-readonly") > - "I only write the pseudo-global and my pointer parameters" is also useful (== "almost-argmemonly") > - I'd expect that generalizing this to have a common notion of "external pseudo thingamajig" across analyses would require adjusting the APIs so they can communicate in a fine-grained way what is or isn't in their external thingamajig, and also whether may-aliases they report involve interference via their external thingamajig or not. > > Thanks > -Joseph > > > -----Original Message----- > From: Joseph Tremoulet > Sent: Tuesday, December 8, 2015 1:12 PM > To: Joseph Tremoulet<jotrem at microsoft.com>; Hal Finkel<hfinkel at anl.gov>; Mehdi Amini<mehdi.amini at apple.com> > Cc: llvm-dev<llvm-dev at lists.llvm.org> > Subject: RE: [llvm-dev] RFC: New function attribute HasInaccessibleState > > [sorry for the re-send; fixed a couple critical typos inline] > > We used a similar thing in the phx compiler. We called it "ExternalMemoryTag". It was a name for "all the program state that doesn't have another name", and in phx (unlike LLVM) it was easy to define what "has another name" meant since we kept an explicit universe of names in our alias metadata. The inferences were flipped the other way, though; being able to access "external memory" was the default assumption, and what the compiler had to prove/propagate was that some functions (whose definitions could be inspected) did NOT touch "external memory". > > Trying to translate that idea to LLVM, I'm having trouble getting around the lack of an explicit universe of named storage locations. Different alias analyses of course have their own ways of partitioning program storage, and "external memory" (in the sense I'm used to it) is the intersection of each analysis' notion of "other storage I'm not modeling precisely". So e.g. in phx we'd start with a heap-insensitive analysis that would leave the entire heap in "external memory", but then running a heap-sensitive analysis would "chip away" at it, carving out a name for each allocation site and redefining "external memory" to exclude those. The difficulty translating this to LLVM is that when you have different analyses all summarizing the same function definition, each one could tell you "I have specific names for all the things this function touches" or not, but there's no useful way to combine those results, since what you want to know is whether all accessed storage is covered by the union of all the specific names. You'd need something along the lines of an API on each alias analysis that would look at an individual instruction and tell you whether it has specific names for all the storage accessed by that instruction; then the function could be summarized as "this doesn't touch anything we don't have a specific name for" if every instruction had at least one analysis claim to have a name for it. Then when querying for aliasing between two calls, the set of returns could be expanded so that each analysis could report "may alias because they both might touch something I have a specific name for" as one possible answer, and "may alias because neither touches anything I have a specific name for (but both might touch something else)" as another possible answer -- then the calls don't alias if the function was summarized as "this doesn't touch anything we don't have a specific name for" and all the analyses report "may alias because neither touc hes anything I have a specific name for".> > The other way would of course be to make one analysis powerful enough to catch the cases we're concerned with. Would it be workable to have GlobalsAA look through the stores (and other mutating operations) in a function to see if they're: > > 1. a store to a local alloca > 2. a store to a global defined in this compilation unit 3. a store through a pointer parameter 4. a call to a function that it has inferred is "ReadOnly-like" (or that is actually readonly) 5. a call to a function that it has inferred is "ArgMemOnly-like" (or that is actually argmemonly) 6. other > > so that: > - if it gets through a function and all modifications are of type 1 or 4, it could summarize that function as "ReadOnly-like"; it could report two calls to "ReadOnly-like" functions as not aliasing in their writes, and report calls to "ReadOnly-like" functions as not modifying any global in the current compilation unit (i.e. any global it can be asked about) > - if it gets through a function and all modifications are of type 1, 3, 4, or 5, it could summarize that function as "ArgMemOnly-like"; it could report a global (in the current compilation unit) as not modified by an "ArgMemOnly-like" so long as it knows the global's address isn't passed as an argument to that function (which I hope is what its notion of "escaped" can tell it) ? > > Then IIUC we could have it recognize some libcalls and treat printf as ArgMemOnly-like (so long as printf's definition is not in the current compilation unit), treat free as ReadOnly-like (so long as likewise), etc. > > I'm probably mixing up details around how lib calls are analyzed and how GlobalsAA propagates information, but I think they key points I'm making are that we may be looking for attributes that would only mean anything to GlobalsAA, and that what they would mean to GlobalsAA may be the same things that "ReadOnly" and "ArgMemOnly" already mean to it. > > Thanks > -Joseph > > -----Original Message----- > From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Hal Finkel via llvm-dev > Sent: Friday, December 4, 2015 7:33 PM > To: Mehdi Amini<mehdi.amini at apple.com> > Cc: LLVM Dev<llvm-dev at lists.llvm.org> > Subject: Re: [llvm-dev] RFC: New function attribute HasInaccessibleState > > ----- Original Message ----- >> From: "Mehdi Amini"<mehdi.amini at apple.com> >> To: "Hal Finkel"<hfinkel at anl.gov> >> Cc: "Vaivaswatha Nagaraj"<vn at compilertree.com>, "LLVM Dev" >> <llvm-dev at lists.llvm.org> >> Sent: Friday, December 4, 2015 12:47:00 PM >> Subject: Re: [llvm-dev] RFC: New function attribute >> HasInaccessibleState >> >> >>> On Dec 4, 2015, at 10:33 AM, Hal Finkel via llvm-dev >>> <llvm-dev at lists.llvm.org> wrote: >>> >>> ----- Original Message ----- >>>> From: "Vaivaswatha Nagaraj"<vn at compilertree.com> >>>> To: "James Molloy"<james at jamesmolloy.co.uk>, "Hal Finkel" >>>> <hfinkel at anl.gov> >>>> Cc: "LLVM Dev"<llvm-dev at lists.llvm.org> >>>> Sent: Friday, December 4, 2015 12:28:03 PM >>>> Subject: Re: [llvm-dev] RFC: New function attribute >>>> HasInaccessibleState >>>> >>>> that would be an escaping global, and as far as I know is handled >>>> separately in GlobalsAA (AnalyzeUsesOfPointer checks if a global is >>>> used as operand to a function) >>>> >>> More generally, I think this attribute is supposed to mean, "this >>> function might access globals, but none of these globals are things >>> you can name in the IR being optimized." You might, of course, pass >>> in aliasing memory as a parameter, but that's a separate matter. >> I’m not what "things you can name in the IR” mean exactly, would this >> be equivalent to "none of these globals can alias with any memory >> location accessible from the IR being optimized”? >> >> To come back to what I phrased earlier, this effectively split the >> state in two distinct parts, is this enough in all cases? Would there >> be some need/benefit to model more partitions? > > I agree this is a good question. I don't have any use cases right now where modeling multiple external states would be useful. > > There might be a relationship to our long-standing problem of modeling errno, but that does not quite fit into this model, because errno is sometimes implemented as a global. > > -Hal > >> Thanks, >> >> — >> Mehdi >> >>>> On December 4, 2015 11:47:20 PM GMT+05:30, James Molloy >>>> <james at jamesmolloy.co.uk> wrote: >>>> >>>> It is if one of the operands is or can alias a global ? >>>> >>>> >>>> On Fri, 4 Dec 2015 at 18:16, Vaivaswatha Nagaraj< >>>> vn at compilertree.com> wrote: >>>> >>>> >>>> >>>> writing into operands is not the same as writing to globals right? >>>> I >>>> added printf in the same category since we were discussing writing >>>> to globals. >>>> >>>> >>>> >>>> On December 4, 2015 11:34:10 PM GMT+05:30, James Molloy< >>>> james at jamesmolloy.co.uk> wrote: >>>> >>>> >>>> Hi, >>>> >>>> >>>> I just want to reiterate: printf and friends do *not* fall into >>>> this category as they can write to their operands (unless you parse >>>> and check the format string for %n). >>>> >>>> >>>> James >>>> >>>> >>>> On Fri, 4 Dec 2015 at 17:53 Vaivaswatha Nagaraj via llvm-dev< >>>> llvm-dev at lists.llvm.org> wrote: >>>> >>>> >>>> >>>> >>>> >>>>> Most of the time you don't have the entire call graph information. >>>>> Imagine that you are developing a module that is a part of a >>>>> larger project. >>>> >>>> I now understand the concern. It looks to me that we will need to >>>> set the flag by default to all functions whose definitions aren't >>>> available (external), and then propagate from there on. I don't see >>>> any optimizations being inhibited by such a setting, so it should >>>> be okay. >>>> >>>> >>>> >>>>> I think we need to go back and look at the underlying use case (as >>>>> I understand it): GlobalAA should be able to figure out that calls >>>>> to malloc/free don't touch global variables visible to the >>>>> optimizer. >>>>> How do we address this problem? >>>> >>>> Yes, this is the primary concern. Most libc functions (including >>>> printf, malloc, free) fall into the same category. >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> - Vaivaswatha >>>> >>>> >>>> >>>> On Fri, Dec 4, 2015 at 11:12 PM, Hal Finkel< hfinkel at anl.gov> >>>> wrote: >>>> >>>> >>>> ----- Original Message ----- >>>>> From: "Vaivaswatha Nagaraj via llvm-dev"< llvm-dev at lists.llvm.org >>>>> To: "Krzysztof Parzyszek"< kparzysz at codeaurora.org> >>>>> Cc: "LLVM Dev"< llvm-dev at lists.llvm.org> >>>>> Sent: Friday, December 4, 2015 11:21:03 AM >>>>> Subject: Re: [llvm-dev] RFC: New function attribute >>>>> HasInaccessibleState >>>>>>> In the case of user-defined allocation functions, the >>>>>>> definitions for those functions are available >>>>>> Are they? probably not unless you're in an LTO build. >>>>> Yes, I'm assuming an LTO build. >>>> The concerns around LTO here, while legitimate, apply only to a >>>> very-specific kind of LTO: An LTO which includes the definitions of >>>> the libc. This is actually quite tricky to support, semantically, >>>> and already breaks our malloc aliasing assumptions. There are many >>>> legitimate uses of LLVM, both for statically-compiled code and for >>>> JIT'd code, that depend on a visibility boundary between certain >>>> core runtime services and the user code being compiled to provide >>>> for effective optimization. >>>> >>>> So, yes, this will break LTO when you include libc itself in the >>>> optimization process. We already don't support this (we'd need, at >>>> least, to adjust our malloc noalias assumptions, if not many other >>>> things). I don't think this is a major concern. >>>> >>>> I think we need to go back and look at the underlying use case (as >>>> I understand it): GlobalAA should be able to figure out that calls >>>> to malloc/free don't touch global variables visible to the >>>> optimizer. >>>> How do we address this problem? >>>> >>>> Thanks again, >>>> Hal >>>> >>>> ... >>>> >>>>> _______________________________________________ >>>>> LLVM Developers mailing list >>>>> llvm-dev at lists.llvm.org >>>>> https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fli >>>>> sts.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev&data=01%7c0 >>>>> 1%7cjotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72 >>>>> f988bf86f141af91ab2d7cd011db47%7c1&sdata=n61OMLL2IjHgbhxfk14QNboJi >>>>> MdHphjpB5DlXBIqKso%3d >>>> -- >>>> >>>> >>>> >>>> -- >>>> Hal Finkel >>>> Assistant Computational Scientist >>>> Leadership Computing Facility >>>> Argonne National Laboratory >>>> >>>> _______________________________________________ >>>> LLVM Developers mailing list >>>> llvm-dev at lists.llvm.org >>>> https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flis >>>> ts.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev&data=01%7c01% >>>> 7cjotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72f98 >>>> 8bf86f141af91ab2d7cd011db47%7c1&sdata=n61OMLL2IjHgbhxfk14QNboJiMdHp >>>> hjpB5DlXBIqKso%3d >>>> >>>> >>>> -- >>>> Sent from my Android device with K-9 Mail. Please excuse my >>>> brevity. >>>> -- >>>> Sent from my Android device with K-9 Mail. Please excuse my >>>> brevity. >>> -- >>> Hal Finkel >>> Assistant Computational Scientist >>> Leadership Computing Facility >>> Argonne National Laboratory >>> _______________________________________________ >>> LLVM Developers mailing list >>> llvm-dev at lists.llvm.org >>> https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flist >>> s.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev&data=01%7c01%7c >>> jotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72f988bf >>> 86f141af91ab2d7cd011db47%7c1&sdata=n61OMLL2IjHgbhxfk14QNboJiMdHphjpB >>> 5DlXBIqKso%3d >> > > -- > Hal Finkel > Assistant Computational Scientist > Leadership Computing Facility > Argonne National Laboratory > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flists.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev%0a&data=01%7c01%7cjotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=Gh14ReFy%2bwjHGJqP%2bV22kWRNOvd6S2WFJX3Cka%2bwRaw%3d > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flists.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev%0a&data=01%7c01%7cjotrem%40microsoft.com%7c1ac7b4dd642a408033a408d2fff891eb%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=YsWMlFxWi2ZmJp%2fb%2fcxScUqLW7nOy43IyDC4Zfsut9U%3d > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Mehdi Amini via llvm-dev
2015-Dec-11 02:09 UTC
[llvm-dev] RFC: New function attribute HasInaccessibleState
> On Dec 9, 2015, at 7:32 AM, Joseph Tremoulet <jotrem at microsoft.com> wrote: > > Sigh... let me try that last part again: > > Maybe GlobalsAA and/or a GlobalsAA-centric attribution pass could partition writes as: > 1. Stores to local allocas > 2. Stores through pointer parameters > 3. Stores to globals defined in this compilation unit > 4. Other > > Attributing functions with attributes: > readonly: only writes of type 1 > argmemonly: only writes of type 1/2 > almost-readonly: only writes of type 1/4 > almost-argmemonly: only writes of type 1/2/4 > > and when visiting a call instruction to determine what sort of writes it entails: > - calls to almost-readonly functions and almost-argmemonly functions imply a write of type 4 > - calls to argmemonly functions and almost-argmemonly functions may imply a write of any type depending what we know about their arguments > > This would allow deducing aliasing relationships: > A. (global defined in this compilation unit) vs (call to almost-readonly function) => no-alias > B. (global defined in this compilation unit) vs (call to almost-argmemonly function), if we know (via escape analysis or whatever) that the address of the global isn't passed as an argument to the call => no-alias > > But "almost-readonly" and "almost-argmemonly" would differ from readonly and argmemonly in that > C. (call to almost-readonly function) vs (call to almost-readonly function) => may-alias > D. (call to almost-readonly function) vs (call to almost-argmemonly function) => may-alias > E. (call to almost-argmemonly function) vs (call to almost-argmemonly function), even if we know their arguments have disjoint points-to sets => may-alias > > and then I think we could soundly annotate externally-defined printf as almost-argmemonly, malloc as almost-readonly, etc, and gain the desired optimizations by way of alias rules A and B > > And, of course, that's pretty much what was already proposed, since we could do this by having a special pseudo-global representing #4, so now I think my key points are: > - we'd want to assume a write to the pseudo-global for any operation we couldn't prove only made writes of type 1/2/3 > - "I only write the pseudo-global" is a useful annotation (== "almost-readonly") > - "I only write the pseudo-global and my pointer parameters" is also useful (== "almost-argmemonly") > - I'd expect that generalizing this to have a common notion of "external pseudo thingamajig" across analyses would require adjusting the APIs so they can communicate in a fine-grained way what is or isn't in their external thingamajig, and also whether may-aliases they report involve interference via their external thingamajig or not.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. — Mehdi> > Thanks > -Joseph > > > -----Original Message----- > From: Joseph Tremoulet > Sent: Tuesday, December 8, 2015 1:12 PM > To: Joseph Tremoulet <jotrem at microsoft.com>; Hal Finkel <hfinkel at anl.gov>; Mehdi Amini <mehdi.amini at apple.com> > Cc: llvm-dev <llvm-dev at lists.llvm.org> > Subject: RE: [llvm-dev] RFC: New function attribute HasInaccessibleState > > [sorry for the re-send; fixed a couple critical typos inline] > > We used a similar thing in the phx compiler. We called it "ExternalMemoryTag". It was a name for "all the program state that doesn't have another name", and in phx (unlike LLVM) it was easy to define what "has another name" meant since we kept an explicit universe of names in our alias metadata. The inferences were flipped the other way, though; being able to access "external memory" was the default assumption, and what the compiler had to prove/propagate was that some functions (whose definitions could be inspected) did NOT touch "external memory". > > Trying to translate that idea to LLVM, I'm having trouble getting around the lack of an explicit universe of named storage locations. Different alias analyses of course have their own ways of partitioning program storage, and "external memory" (in the sense I'm used to it) is the intersection of each analysis' notion of "other storage I'm not modeling precisely". So e.g. in phx we'd start with a heap-insensitive analysis that would leave the entire heap in "external memory", but then running a heap-sensitive analysis would "chip away" at it, carving out a name for each allocation site and redefining "external memory" to exclude those. The difficulty translating this to LLVM is that when you have different analyses all summarizing the same function definition, each one could tell you "I have specific names for all the things this function touches" or not, but there's no useful way to combine those results, since what you want to know is whether all accessed storage is covered by the union of all the specific names. You'd need something along the lines of an API on each alias analysis that would look at an individual instruction and tell you whether it has specific names for all the storage accessed by that instruction; then the function could be summarized as "this doesn't touch anything we don't have a specific name for" if every instruction had at least one analysis claim to have a name for it. Then when querying for aliasing between two calls, the set of returns could be expanded so that each analysis could report "may alias because they both might touch something I have a specific name for" as one possible answer, and "may alias because neither touches anything I have a specific name for (but both might touch something else)" as another possible answer -- then the calls don't alias if the function was summarized as "this doesn't touch anything we don't have a specific name for" and all the analyses report "may alias because neither touches anything I have a specific name for". > > The other way would of course be to make one analysis powerful enough to catch the cases we're concerned with. Would it be workable to have GlobalsAA look through the stores (and other mutating operations) in a function to see if they're: > > 1. a store to a local alloca > 2. a store to a global defined in this compilation unit 3. a store through a pointer parameter 4. a call to a function that it has inferred is "ReadOnly-like" (or that is actually readonly) 5. a call to a function that it has inferred is "ArgMemOnly-like" (or that is actually argmemonly) 6. other > > so that: > - if it gets through a function and all modifications are of type 1 or 4, it could summarize that function as "ReadOnly-like"; it could report two calls to "ReadOnly-like" functions as not aliasing in their writes, and report calls to "ReadOnly-like" functions as not modifying any global in the current compilation unit (i.e. any global it can be asked about) > - if it gets through a function and all modifications are of type 1, 3, 4, or 5, it could summarize that function as "ArgMemOnly-like"; it could report a global (in the current compilation unit) as not modified by an "ArgMemOnly-like" so long as it knows the global's address isn't passed as an argument to that function (which I hope is what its notion of "escaped" can tell it) ? > > Then IIUC we could have it recognize some libcalls and treat printf as ArgMemOnly-like (so long as printf's definition is not in the current compilation unit), treat free as ReadOnly-like (so long as likewise), etc. > > I'm probably mixing up details around how lib calls are analyzed and how GlobalsAA propagates information, but I think they key points I'm making are that we may be looking for attributes that would only mean anything to GlobalsAA, and that what they would mean to GlobalsAA may be the same things that "ReadOnly" and "ArgMemOnly" already mean to it. > > Thanks > -Joseph > > -----Original Message----- > From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Hal Finkel via llvm-dev > Sent: Friday, December 4, 2015 7:33 PM > To: Mehdi Amini <mehdi.amini at apple.com> > Cc: LLVM Dev <llvm-dev at lists.llvm.org> > Subject: Re: [llvm-dev] RFC: New function attribute HasInaccessibleState > > ----- Original Message ----- >> From: "Mehdi Amini" <mehdi.amini at apple.com> >> To: "Hal Finkel" <hfinkel at anl.gov> >> Cc: "Vaivaswatha Nagaraj" <vn at compilertree.com>, "LLVM Dev" >> <llvm-dev at lists.llvm.org> >> Sent: Friday, December 4, 2015 12:47:00 PM >> Subject: Re: [llvm-dev] RFC: New function attribute >> HasInaccessibleState >> >> >>> On Dec 4, 2015, at 10:33 AM, Hal Finkel via llvm-dev >>> <llvm-dev at lists.llvm.org> wrote: >>> >>> ----- Original Message ----- >>>> From: "Vaivaswatha Nagaraj" <vn at compilertree.com> >>>> To: "James Molloy" <james at jamesmolloy.co.uk>, "Hal Finkel" >>>> <hfinkel at anl.gov> >>>> Cc: "LLVM Dev" <llvm-dev at lists.llvm.org> >>>> Sent: Friday, December 4, 2015 12:28:03 PM >>>> Subject: Re: [llvm-dev] RFC: New function attribute >>>> HasInaccessibleState >>>> >>>> that would be an escaping global, and as far as I know is handled >>>> separately in GlobalsAA (AnalyzeUsesOfPointer checks if a global is >>>> used as operand to a function) >>>> >>> >>> More generally, I think this attribute is supposed to mean, "this >>> function might access globals, but none of these globals are things >>> you can name in the IR being optimized." You might, of course, pass >>> in aliasing memory as a parameter, but that's a separate matter. >> >> I’m not what "things you can name in the IR” mean exactly, would this >> be equivalent to "none of these globals can alias with any memory >> location accessible from the IR being optimized”? >> >> To come back to what I phrased earlier, this effectively split the >> state in two distinct parts, is this enough in all cases? Would there >> be some need/benefit to model more partitions? > > I agree this is a good question. I don't have any use cases right now where modeling multiple external states would be useful. > > There might be a relationship to our long-standing problem of modeling errno, but that does not quite fit into this model, because errno is sometimes implemented as a global. > > -Hal > >> >> Thanks, >> >> — >> Mehdi >> >>> >>>> >>>> On December 4, 2015 11:47:20 PM GMT+05:30, James Molloy >>>> <james at jamesmolloy.co.uk> wrote: >>>> >>>> It is if one of the operands is or can alias a global ? >>>> >>>> >>>> On Fri, 4 Dec 2015 at 18:16, Vaivaswatha Nagaraj < >>>> vn at compilertree.com > wrote: >>>> >>>> >>>> >>>> writing into operands is not the same as writing to globals right? >>>> I >>>> added printf in the same category since we were discussing writing >>>> to globals. >>>> >>>> >>>> >>>> On December 4, 2015 11:34:10 PM GMT+05:30, James Molloy < >>>> james at jamesmolloy.co.uk > wrote: >>>> >>>> >>>> Hi, >>>> >>>> >>>> I just want to reiterate: printf and friends do *not* fall into >>>> this category as they can write to their operands (unless you parse >>>> and check the format string for %n). >>>> >>>> >>>> James >>>> >>>> >>>> On Fri, 4 Dec 2015 at 17:53 Vaivaswatha Nagaraj via llvm-dev < >>>> llvm-dev at lists.llvm.org > wrote: >>>> >>>> >>>> >>>> >>>> >>>>> Most of the time you don't have the entire call graph information. >>>>> Imagine that you are developing a module that is a part of a >>>>> larger project. >>>> >>>> >>>> I now understand the concern. It looks to me that we will need to >>>> set the flag by default to all functions whose definitions aren't >>>> available (external), and then propagate from there on. I don't see >>>> any optimizations being inhibited by such a setting, so it should >>>> be okay. >>>> >>>> >>>> >>>>> I think we need to go back and look at the underlying use case (as >>>>> I understand it): GlobalAA should be able to figure out that calls >>>>> to malloc/free don't touch global variables visible to the >>>>> optimizer. >>>>> How do we address this problem? >>>> >>>> >>>> Yes, this is the primary concern. Most libc functions (including >>>> printf, malloc, free) fall into the same category. >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> - Vaivaswatha >>>> >>>> >>>> >>>> On Fri, Dec 4, 2015 at 11:12 PM, Hal Finkel < hfinkel at anl.gov > >>>> wrote: >>>> >>>> >>>> ----- Original Message ----- >>>>> From: "Vaivaswatha Nagaraj via llvm-dev" < llvm-dev at lists.llvm.org >>>>>> >>>>> To: "Krzysztof Parzyszek" < kparzysz at codeaurora.org > >>>>> Cc: "LLVM Dev" < llvm-dev at lists.llvm.org > >>>>> Sent: Friday, December 4, 2015 11:21:03 AM >>>>> Subject: Re: [llvm-dev] RFC: New function attribute >>>>> HasInaccessibleState >>>> >>>>>>> In the case of user-defined allocation functions, the >>>>>>> definitions for those functions are available >>>> >>>>>> Are they? probably not unless you're in an LTO build. >>>> >>>>> Yes, I'm assuming an LTO build. >>>> >>>> The concerns around LTO here, while legitimate, apply only to a >>>> very-specific kind of LTO: An LTO which includes the definitions of >>>> the libc. This is actually quite tricky to support, semantically, >>>> and already breaks our malloc aliasing assumptions. There are many >>>> legitimate uses of LLVM, both for statically-compiled code and for >>>> JIT'd code, that depend on a visibility boundary between certain >>>> core runtime services and the user code being compiled to provide >>>> for effective optimization. >>>> >>>> So, yes, this will break LTO when you include libc itself in the >>>> optimization process. We already don't support this (we'd need, at >>>> least, to adjust our malloc noalias assumptions, if not many other >>>> things). I don't think this is a major concern. >>>> >>>> I think we need to go back and look at the underlying use case (as >>>> I understand it): GlobalAA should be able to figure out that calls >>>> to malloc/free don't touch global variables visible to the >>>> optimizer. >>>> How do we address this problem? >>>> >>>> Thanks again, >>>> Hal >>>> >>>> ... >>>> >>>>> _______________________________________________ >>>>> LLVM Developers mailing list >>>>> llvm-dev at lists.llvm.org >>>>> https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fli >>>>> sts.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev&data=01%7c0 >>>>> 1%7cjotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72 >>>>> f988bf86f141af91ab2d7cd011db47%7c1&sdata=n61OMLL2IjHgbhxfk14QNboJi >>>>> MdHphjpB5DlXBIqKso%3d >>>> >>>> -- >>>> >>>> >>>> >>>> -- >>>> Hal Finkel >>>> Assistant Computational Scientist >>>> Leadership Computing Facility >>>> Argonne National Laboratory >>>> >>>> _______________________________________________ >>>> LLVM Developers mailing list >>>> llvm-dev at lists.llvm.org >>>> https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flis >>>> ts.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev&data=01%7c01% >>>> 7cjotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72f98 >>>> 8bf86f141af91ab2d7cd011db47%7c1&sdata=n61OMLL2IjHgbhxfk14QNboJiMdHp >>>> hjpB5DlXBIqKso%3d >>>> >>>> >>>> -- >>>> Sent from my Android device with K-9 Mail. Please excuse my >>>> brevity. >>>> -- >>>> Sent from my Android device with K-9 Mail. Please excuse my >>>> brevity. >>> >>> -- >>> Hal Finkel >>> Assistant Computational Scientist >>> Leadership Computing Facility >>> Argonne National Laboratory >>> _______________________________________________ >>> LLVM Developers mailing list >>> llvm-dev at lists.llvm.org >>> https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flist >>> s.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev&data=01%7c01%7c >>> jotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72f988bf >>> 86f141af91ab2d7cd011db47%7c1&sdata=n61OMLL2IjHgbhxfk14QNboJiMdHphjpB >>> 5DlXBIqKso%3d >> >> > > -- > Hal Finkel > Assistant Computational Scientist > Leadership Computing Facility > Argonne National Laboratory > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flists.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev%0a&data=01%7c01%7cjotrem%40microsoft.com%7c606569a7772347cd741408d2fd0babf8%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=Gh14ReFy%2bwjHGJqP%2bV22kWRNOvd6S2WFJX3Cka%2bwRaw%3d > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flists.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev%0a&data=01%7c01%7cjotrem%40microsoft.com%7c1ac7b4dd642a408033a408d2fff891eb%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=YsWMlFxWi2ZmJp%2fb%2fcxScUqLW7nOy43IyDC4Zfsut9U%3d
Joseph Tremoulet via llvm-dev
2015-Dec-11 19:16 UTC
[llvm-dev] RFC: New function attribute HasInaccessibleState
<<< 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. 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
Joseph Tremoulet via llvm-dev
2015-Dec-11 19:21 UTC
[llvm-dev] RFC: New function attribute HasInaccessibleState
<< Joseph Tremoulet via llvm-dev wrote:> Sigh... let me try that last part again: > > Maybe GlobalsAA and/or a GlobalsAA-centric attribution pass could partition writes as: > 1. Stores to local allocas > 2. Stores through pointer parameters > 3. Stores to globals defined in this compilation unit > 4. Other > > Attributing functions with attributes: > readonly: only writes of type 1 > argmemonly: only writes of type 1/2 > almost-readonly: only writes of type 1/4 > almost-argmemonly: only writes of type 1/2/4 > > and when visiting a call instruction to determine what sort of writes it entails: > - calls to almost-readonly functions and almost-argmemonly > functions imply a write of type 4Do you mean "readonly and almost-readonly"?>>No -- the thing that makes them "almost-" is that they can read and write state that is neither (1) local nor (3) one of the globals that GlobalsAA can precisely reason about nor (2) state that is an easily summarizable function of the parameters and which therefore allows reasoning at each callsite.