Vaivaswatha Nagaraj via llvm-dev
2015-Dec-04 09:51 UTC
[llvm-dev] RFC: New function attribute HasInaccessibleState
>but is there or is there not accessible, visible state,Wouldn't ReadNone and/or ReadOnly cover that? If ReadNone is set, it means it doesn't access any of the visible (accessible) states. - Vaivaswatha On Fri, Dec 4, 2015 at 3:17 PM, James Molloy <james at jamesmolloy.co.uk> wrote:> Hi, > > I don't think the attribute as is is strong enough to do what you wish. > "HasInaccessibleState" is in fact a no-op because it implies nothing about > the *accessible* state. OK, there's inaccessible state but is there or is > there not accessible, visible state, is the question that optimizers need > to ask. > > So I'd rephrase it to something like "HasNoAccessibleState" ? > > James > > On Fri, 4 Dec 2015 at 07:58 Vaivaswatha Nagaraj via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > >> >is this "internal state” supposed to be private to the function? >> It could be private or not. Hence the name "inaccessible", to mean that >> the program under compilation has no access to the state. So while printf >> and malloc (for example) could share state in libc, the program under >> compilation cannot access this state. >> >> >> >how this flag would prevent the last “optimization” you’re illustrating >> Assuming you are referring to the quoted examples, currently these >> optimizations are not happening anyway (from what I understand). The issue >> is that, after malloc/free are tagged with "ReadNone", such transforms may >> happen. Hence to prevent that, the additional flag denoting that these >> functions maintain an internal state. >> >> >> - Vaivaswatha >> >> On Fri, Dec 4, 2015 at 12:20 PM, Mehdi Amini <mehdi.amini at apple.com> >> wrote: >> >>> Hi, >>> >>> On Dec 3, 2015, at 10:33 PM, Vaivaswatha Nagaraj via llvm-dev < >>> llvm-dev at lists.llvm.org> wrote: >>> >>> Hi, >>> >>> This email is in continuation to the mail thread >>> http://lists.llvm.org/pipermail/llvm-dev/2015-December/092996.html, to >>> propose a new function attribute that can convey that a function maintains >>> state, but this state is inaccessible to the rest of the program under >>> compilation. >>> >>> Such a flag could be added to most libc/system calls such as >>> printf/malloc/free. (libc and system calls do access/modify internal >>> variables such as errno). >>> >>> Example attributes (in addition to what are already set): >>> malloc/free: HasInaccessibleState, ReadNone >>> printf: HasInaccessibleState, ArgMemOnly >>> realloc: HasInaccessibleState, ReadOnly (not sure). >>> >>> 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). >>> >>> For malloc, even though ReadNone is set now (as proposed above), >>> EarlyCSE should be taught to respect the HasInaccessibleState and not >>> combine functions that maintain internal states. Similarly other >>> optimizations (such as DCE) must be taught to respect the flag. >>> >>> 2. >>> >void foo(char * restrict s1, char * restrict s2) { >>> > printf(s1); >>> > printf(s2); >>> >} >>> >>> >If printf is argmemonly, then we could interchange the two printf calls. >>> >>> In this example too, printf maintains an internal state, preventing the >>> calls from being internchanged. Also, it is now correct to add >>> ArgMemOnly to printf as it does not access any other program memory. >>> >>> 3. >>> >For malloc this is still a problem, in the following sense, if we have: >>> > >>> > p1 = malloc(really_big); >>> > ... >>> > free(p1); >>> > >>> > p2 = malloc(really_big); >>> > ... >>> > free(p2); >>> >allowing a transformation into: >>> > p1 = malloc(really_big); >>> > p2 = malloc(really_big); >>> > ... >>> > free(p1); free(p2); >>> >could be problematic. >>> >>> Both free and malloc would be marked with having an internal state. This >>> should prevent this kind of an optimization. Note that having the >>> ReadNone attribute should not cause problems anymore. >>> >>> >>> Something is not clear to me: is this "internal state” supposed to be >>> private to the function? >>> How does it deal with malloc/free which can be seen as sharing a state? >>> Especially it is not clear to me how this flag would prevent the last >>> “optimization” you’re illustrating. >>> >>> — >>> Mehdi >>> >>> >>> >>> >> _______________________________________________ >> 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/20151204/99d56634/attachment.html>
James Molloy via llvm-dev
2015-Dec-04 10:00 UTC
[llvm-dev] RFC: New function attribute HasInaccessibleState
No, that'd be redefining the semantics of ReadNone. ReadNone allows elision of a call if its result is unused, which would break some "hasinaccessiblestate" functions (although not malloc). On Fri, 4 Dec 2015 at 09:51 Vaivaswatha Nagaraj <vn at compilertree.com> wrote:> >but is there or is there not accessible, visible state, > Wouldn't ReadNone and/or ReadOnly cover that? If ReadNone is set, it means > it doesn't access any of the visible (accessible) states. > > - Vaivaswatha > > On Fri, Dec 4, 2015 at 3:17 PM, James Molloy <james at jamesmolloy.co.uk> > wrote: > >> Hi, >> >> I don't think the attribute as is is strong enough to do what you wish. >> "HasInaccessibleState" is in fact a no-op because it implies nothing about >> the *accessible* state. OK, there's inaccessible state but is there or is >> there not accessible, visible state, is the question that optimizers need >> to ask. >> >> So I'd rephrase it to something like "HasNoAccessibleState" ? >> >> James >> >> On Fri, 4 Dec 2015 at 07:58 Vaivaswatha Nagaraj via llvm-dev < >> llvm-dev at lists.llvm.org> wrote: >> >>> >is this "internal state” supposed to be private to the function? >>> It could be private or not. Hence the name "inaccessible", to mean that >>> the program under compilation has no access to the state. So while printf >>> and malloc (for example) could share state in libc, the program under >>> compilation cannot access this state. >>> >>> >>> >how this flag would prevent the last “optimization” you’re illustrating >>> Assuming you are referring to the quoted examples, currently these >>> optimizations are not happening anyway (from what I understand). The issue >>> is that, after malloc/free are tagged with "ReadNone", such transforms may >>> happen. Hence to prevent that, the additional flag denoting that these >>> functions maintain an internal state. >>> >>> >>> - Vaivaswatha >>> >>> On Fri, Dec 4, 2015 at 12:20 PM, Mehdi Amini <mehdi.amini at apple.com> >>> wrote: >>> >>>> Hi, >>>> >>>> On Dec 3, 2015, at 10:33 PM, Vaivaswatha Nagaraj via llvm-dev < >>>> llvm-dev at lists.llvm.org> wrote: >>>> >>>> Hi, >>>> >>>> This email is in continuation to the mail thread >>>> http://lists.llvm.org/pipermail/llvm-dev/2015-December/092996.html, to >>>> propose a new function attribute that can convey that a function maintains >>>> state, but this state is inaccessible to the rest of the program under >>>> compilation. >>>> >>>> Such a flag could be added to most libc/system calls such as >>>> printf/malloc/free. (libc and system calls do access/modify internal >>>> variables such as errno). >>>> >>>> Example attributes (in addition to what are already set): >>>> malloc/free: HasInaccessibleState, ReadNone >>>> printf: HasInaccessibleState, ArgMemOnly >>>> realloc: HasInaccessibleState, ReadOnly (not sure). >>>> >>>> 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). >>>> >>>> For malloc, even though ReadNone is set now (as proposed above), >>>> EarlyCSE should be taught to respect the HasInaccessibleState and not >>>> combine functions that maintain internal states. Similarly other >>>> optimizations (such as DCE) must be taught to respect the flag. >>>> >>>> 2. >>>> >void foo(char * restrict s1, char * restrict s2) { >>>> > printf(s1); >>>> > printf(s2); >>>> >} >>>> >>>> >If printf is argmemonly, then we could interchange the two printf >>>> calls. >>>> >>>> In this example too, printf maintains an internal state, preventing the >>>> calls from being internchanged. Also, it is now correct to add >>>> ArgMemOnly to printf as it does not access any other program memory. >>>> >>>> 3. >>>> >For malloc this is still a problem, in the following sense, if we have: >>>> > >>>> > p1 = malloc(really_big); >>>> > ... >>>> > free(p1); >>>> > >>>> > p2 = malloc(really_big); >>>> > ... >>>> > free(p2); >>>> >allowing a transformation into: >>>> > p1 = malloc(really_big); >>>> > p2 = malloc(really_big); >>>> > ... >>>> > free(p1); free(p2); >>>> >could be problematic. >>>> >>>> Both free and malloc would be marked with having an internal state. >>>> This should prevent this kind of an optimization. Note that having the >>>> ReadNone attribute should not cause problems anymore. >>>> >>>> >>>> Something is not clear to me: is this "internal state” supposed to be >>>> private to the function? >>>> How does it deal with malloc/free which can be seen as sharing a state? >>>> Especially it is not clear to me how this flag would prevent the last >>>> “optimization” you’re illustrating. >>>> >>>> — >>>> Mehdi >>>> >>>> >>>> >>>> >>> _______________________________________________ >>> 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/20151204/14ec9cc1/attachment.html>
Hal Finkel via llvm-dev
2015-Dec-04 15:04 UTC
[llvm-dev] RFC: New function attribute HasInaccessibleState
----- Original Message -----> From: "James Molloy via llvm-dev" <llvm-dev at lists.llvm.org> > To: "Vaivaswatha Nagaraj" <vn at compilertree.com> > Cc: "LLVM Dev" <llvm-dev at lists.llvm.org> > Sent: Friday, December 4, 2015 4:00:24 AM > Subject: Re: [llvm-dev] RFC: New function attribute HasInaccessibleState > > No, that'd be redefining the semantics of ReadNone. ReadNone allows > elision of a call if its result is unused, which would break some > "hasinaccessiblestate" functions (although not malloc). >To make a (perhaps incorrect) general statement: We currently only have 'additive' attributes, but no 'subtractive' ones (builtin/nobuiltin aside, as those are exactly paired). Having an attribute that subtracts from the strength of ReadNone would be a new concept in the design of our IR, and a change that I'd be hesitant to make. At the cost of some redundancy, I think a new attribute is needed. -Hal> > On Fri, 4 Dec 2015 at 09:51 Vaivaswatha Nagaraj < vn at compilertree.com > > wrote: > > >but is there or is there not accessible, visible state, > > Wouldn't ReadNone and/or ReadOnly cover that? If ReadNone is set, it > means it doesn't access any of the visible (accessible) states. > > > > > > > - Vaivaswatha > > > > On Fri, Dec 4, 2015 at 3:17 PM, James Molloy < > james at jamesmolloy.co.uk > wrote: > > > > Hi, > > > I don't think the attribute as is is strong enough to do what you > wish. "HasInaccessibleState" is in fact a no-op because it implies > nothing about the *accessible* state. OK, there's inaccessible state > but is there or is there not accessible, visible state, is the > question that optimizers need to ask. > > > So I'd rephrase it to something like "HasNoAccessibleState" ? > > > James > > > > > On Fri, 4 Dec 2015 at 07:58 Vaivaswatha Nagaraj via llvm-dev < > llvm-dev at lists.llvm.org > wrote: > > > > > > > > >is this "internal state” supposed to be private to the function? > > > It could be private or not. Hence the name "inaccessible", to mean > that the program under compilation has no access to the state. So > while printf and malloc (for example) could share state in libc, the > program under compilation cannot access this state. > > > > >how this flag would prevent the last “optimization” you’re > >illustrating > > > Assuming you are referring to the quoted examples, currently these > optimizations are not happening anyway (from what I understand). The > issue is that, after malloc/free are tagged with "ReadNone", such > transforms may happen. Hence to prevent that, the additional flag > denoting that these functions maintain an internal state. > > > > > > > > > - Vaivaswatha > > > > On Fri, Dec 4, 2015 at 12:20 PM, Mehdi Amini < mehdi.amini at apple.com > > wrote: > > > > Hi, > > > > > > > > > On Dec 3, 2015, at 10:33 PM, Vaivaswatha Nagaraj via llvm-dev < > llvm-dev at lists.llvm.org > wrote: > > > > > Hi, > > This email is in continuation to the mail thread > http://lists.llvm.org/pipermail/llvm-dev/2015-December/092996.html , > to propose a new function attribute that can convey that a function > maintains state, but this state is inaccessible to the rest of the > program under compilation. > > Such a flag could be added to most libc/system calls such as > printf/malloc/free. (libc and system calls do access/modify internal > variables such as errno). > > > > > Example attributes (in addition to what are already set): > > malloc/free: HasInaccessibleState, ReadNone > > printf: HasInaccessibleState, ArgMemOnly > > realloc: HasInaccessibleState, ReadOnly (not sure). > > > 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). > > > For malloc, even though ReadNone is set now (as proposed above), > EarlyCSE should be taught to respect the HasInaccessibleState and > not combine functions that maintain internal states. Similarly other > optimizations (such as DCE) must be taught to respect the flag. > > 2. > >void foo(char * restrict s1, char * restrict s2) { > > printf(s1); > > printf(s2); > >} > > >If printf is argmemonly, then we could interchange the two printf > >calls. > > > In this example too, printf maintains an internal state, preventing > the calls from being internchanged . Also, it is now correct to add > ArgMemOnly to printf as it does not access any other program memory. > > 3. > >For malloc this is still a problem, in the following sense, if we > >have: > > > > p1 = malloc(really_big); > > ... > > free(p1); > > > > p2 = malloc(really_big); > > ... > > free(p2); > >allowing a transformation into: > > p1 = malloc(really_big); > > p2 = malloc(really_big); > > ... > > free(p1); free(p2); > >could be problematic. > > > Both free and malloc would be marked with having an internal state. > This should prevent this kind of an optimization . Note that having > the ReadNone attribute should not cause problems anymore. > > > > > Something is not clear to me: is this "internal state” supposed to be > private to the function? > How does it deal with malloc/free which can be seen as sharing a > state? Especially it is not clear to me how this flag would prevent > the last “optimization” you’re illustrating. > > > — > Mehdi > > > > > > > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory