James Molloy via llvm-dev
2015-Nov-05 15:44 UTC
[llvm-dev] [PATCH] D14227: Add a new attribute: norecurse
[Adding llvm-dev and re-stating the situation for llvm-dev's benefit] *RFC: A new attribute, "norecurse".* In some cases, it is possible to demote global variables to local variables. This is possible when the global is only used in one function, and that function is known not to recurse (because if the function recurses, a local variable cannot be equivalent to a global as the global would hold state over the recursive call). GlobalOpt has this ability already, however it is currently (a) weak and (b) broken. GlobalOpt has a special case for the function "main". It assumes that any function called "main" with external linkage is by definition non-recursive. It does this because in C++, main is defined by the standard not to recurse. However, this is not the case in C, so GlobalOpt will happily break C code. GlobalOpt also currently won't even attempt to discover functions that don't recurse - it only checks "main". What I'd like to do is improve GlobalOpt to be more aggressive with demoting globals to locals, and to do that I need to teach it which functions are known to be non-recursive. At the same time I'd really like to fix the "main" kludge. There are three options I see: 1. Just use an analysis pass to infer non-recursiveness as a property. This can be a simple SCC pass which is queried by GlobalOpt. 2. Add an attribute, "norecurse". This would be inferred just like above by FunctionAttrs in the general case, but it also allows frontends to add the attribute if they have specific knowledge - for example "main" in C++ mode. 3. (1), but use metadata to add the non-recursiveness information in the frontend, to solve the "main" problem. What I'm suggesting here is (2). I have no real problem implementing (3) instead, and I think it's something that's worthwhile discussing. Adding new metadata is very cheap and easy and doesn't seem to have many downsides as an option. Hopefully I've described the problem and potential solutions well enough - what are peoples' thoughts? I quite like the attribute solution best, but I'd be happy with anything that moves us forward. Cheers, James On Wed, 4 Nov 2015 at 17:46 Philip Reames via llvm-commits < llvm-commits at lists.llvm.org> wrote:> This should probably be raised on llvm-dev for boarder visibility. > > Side question: What optimizations or codegen opportunities does this > enable? i.e. what's the actual use case? > > > On 11/02/2015 05:03 AM, James Molloy via llvm-commits wrote: > > jmolloy created this revision. > jmolloy added reviewers: manmanren, dexonsmith, joker.eph. > jmolloy added a subscriber: llvm-commits. > jmolloy set the repository for this revision to rL LLVM. > > This attribute allows the compiler to assume that the function never recurses into itself, either directly or indirectly (transitively). This can be used among other things to demote global variables to locals. > > The norecurse attribute indicates that the function does not call itself either directly or indirectly down any possible call path. > > Repository: > rL LLVM > http://reviews.llvm.org/D14227 > > Files: > docs/LangRef.rst > include/llvm/Bitcode/LLVMBitCodes.h > include/llvm/IR/Attributes.h > include/llvm/IR/Function.h > lib/AsmParser/LLLexer.cpp > lib/AsmParser/LLParser.cpp > lib/AsmParser/LLToken.h > lib/Bitcode/Reader/BitcodeReader.cpp > lib/Bitcode/Writer/BitcodeWriter.cpp > lib/IR/Attributes.cpp > lib/IR/Verifier.cpp > test/Bindings/llvm-c/invalid-bitcode.test > test/Bitcode/attributes.ll > test/Bitcode/compatibility.ll > test/Bitcode/invalid.ll > test/LTO/X86/invalid.ll > > > > > _______________________________________________ > llvm-commits mailing listllvm-commits at lists.llvm.orghttp://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits > > > _______________________________________________ > llvm-commits mailing list > llvm-commits at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20151105/28561cd5/attachment.html>
Hal Finkel via llvm-dev
2015-Nov-05 15:54 UTC
[llvm-dev] [PATCH] D14227: Add a new attribute: norecurse
----- Original Message -----> From: "James Molloy via llvm-dev" <llvm-dev at lists.llvm.org> > To: "Philip Reames" <listmail at philipreames.com>, > reviews+D14227+public+6a20206dc9791b02 at reviews.llvm.org, "James > Molloy" <james.molloy at arm.com>, "manman ren" <manman.ren at gmail.com>, > dexonsmith at apple.com, "mehdi amini" <mehdi.amini at apple.com>, "LLVM > Dev" <llvm-dev at lists.llvm.org> > Cc: "LLVM Commits" <llvm-commits at lists.llvm.org> > Sent: Thursday, November 5, 2015 9:44:45 AM > Subject: Re: [llvm-dev] [PATCH] D14227: Add a new attribute: > norecurse> [Adding llvm-dev and re-stating the situation for llvm-dev's benefit]> RFC: A new attribute, "norecurse".> In some cases, it is possible to demote global variables to local > variables. This is possible when the global is only used in one > function, and that function is known not to recurse (because if the > function recurses, a local variable cannot be equivalent to a global > as the global would hold state over the recursive call).> GlobalOpt has this ability already, however it is currently (a) weak > and (b) broken.> GlobalOpt has a special case for the function "main". It assumes that > any function called "main" with external linkage is by definition > non-recursive. It does this because in C++, main is defined by the > standard not to recurse. However, this is not the case in C, so > GlobalOpt will happily break C code.> GlobalOpt also currently won't even attempt to discover functions > that don't recurse - it only checks "main".> What I'd like to do is improve GlobalOpt to be more aggressive with > demoting globals to locals, and to do that I need to teach it which > functions are known to be non-recursive. At the same time I'd really > like to fix the "main" kludge.> There are three options I see: > 1. Just use an analysis pass to infer non-recursiveness as a > property. This can be a simple SCC pass which is queried by > GlobalOpt. > 2. Add an attribute, "norecurse". This would be inferred just like > above by FunctionAttrs in the general case, but it also allows > frontends to add the attribute if they have specific knowledge - for > example "main" in C++ mode. > 3. (1), but use metadata to add the non-recursiveness information in > the frontend, to solve the "main" problem.> What I'm suggesting here is (2).+1 This is a very generic property, and I'm happy with the conciseness provided by an attribute. -Hal> I have no real problem implementing (3) instead, and I think it's > something that's worthwhile discussing. Adding new metadata is very > cheap and easy and doesn't seem to have many downsides as an option.> Hopefully I've described the problem and potential solutions well > enough - what are peoples' thoughts? I quite like the attribute > solution best, but I'd be happy with anything that moves us forward.> Cheers,> James> On Wed, 4 Nov 2015 at 17:46 Philip Reames via llvm-commits < > llvm-commits at lists.llvm.org > wrote:> > This should probably be raised on llvm-dev for boarder visibility. >> > Side question: What optimizations or codegen opportunities does > > this > > enable? i.e. what's the actual use case? >> > On 11/02/2015 05:03 AM, James Molloy via llvm-commits wrote: >> > > jmolloy created this revision. > > > > > > jmolloy added reviewers: manmanren, dexonsmith, joker.eph. > > > > > > jmolloy added a subscriber: llvm-commits. > > > > > > jmolloy set the repository for this revision to rL LLVM. > > >> > > This attribute allows the compiler to assume that the function > > > never > > > recurses into itself, either directly or indirectly > > > (transitively). > > > This can be used among other things to demote global variables to > > > locals. > > >> > > The norecurse attribute indicates that the function does not call > > > itself either directly or indirectly down any possible call path. > > >> > > Repository: > > > > > > rL LLVM http://reviews.llvm.org/D14227 Files: > > > > > > docs/LangRef.rst > > > > > > include/llvm/Bitcode/LLVMBitCodes.h > > > > > > include/llvm/IR/Attributes.h > > > > > > include/llvm/IR/Function.h > > > > > > lib/AsmParser/LLLexer.cpp > > > > > > lib/AsmParser/LLParser.cpp > > > > > > lib/AsmParser/LLToken.h > > > > > > lib/Bitcode/Reader/BitcodeReader.cpp > > > > > > lib/Bitcode/Writer/BitcodeWriter.cpp > > > > > > lib/IR/Attributes.cpp > > > > > > lib/IR/Verifier.cpp > > > > > > test/Bindings/llvm-c/invalid-bitcode.test > > > > > > test/Bitcode/attributes.ll > > > > > > test/Bitcode/compatibility.ll > > > > > > test/Bitcode/invalid.ll > > > > > > test/LTO/X86/invalid.ll > > >> > > _______________________________________________ > > > > > > llvm-commits mailing list llvm-commits at lists.llvm.org > > > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits > > > > > _______________________________________________ > > > llvm-commits mailing list > > > llvm-commits at lists.llvm.org > > > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits >> _______________________________________________ > 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 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20151105/d39f9c31/attachment.html>
Aaron Ballman via llvm-dev
2015-Nov-05 16:03 UTC
[llvm-dev] [PATCH] D14227: Add a new attribute: norecurse
On Thu, Nov 5, 2015 at 10:44 AM, James Molloy via llvm-dev <llvm-dev at lists.llvm.org> wrote:> [Adding llvm-dev and re-stating the situation for llvm-dev's benefit] > > RFC: A new attribute, "norecurse". > > In some cases, it is possible to demote global variables to local variables. > This is possible when the global is only used in one function, and that > function is known not to recurse (because if the function recurses, a local > variable cannot be equivalent to a global as the global would hold state > over the recursive call). > > GlobalOpt has this ability already, however it is currently (a) weak and (b) > broken. > > GlobalOpt has a special case for the function "main". It assumes that any > function called "main" with external linkage is by definition non-recursive. > It does this because in C++, main is defined by the standard not to recurse. > However, this is not the case in C, so GlobalOpt will happily break C code. > > GlobalOpt also currently won't even attempt to discover functions that don't > recurse - it only checks "main". > > What I'd like to do is improve GlobalOpt to be more aggressive with demoting > globals to locals, and to do that I need to teach it which functions are > known to be non-recursive. At the same time I'd really like to fix the > "main" kludge. > > There are three options I see: > 1. Just use an analysis pass to infer non-recursiveness as a property. > This can be a simple SCC pass which is queried by GlobalOpt. > 2. Add an attribute, "norecurse". This would be inferred just like above > by FunctionAttrs in the general case, but it also allows frontends to add > the attribute if they have specific knowledge - for example "main" in C++ > mode. > 3. (1), but use metadata to add the non-recursiveness information in the > frontend, to solve the "main" problem. > > What I'm suggesting here is (2). I have no real problem implementing (3) > instead, and I think it's something that's worthwhile discussing. Adding new > metadata is very cheap and easy and doesn't seem to have many downsides as > an option. > > Hopefully I've described the problem and potential solutions well enough - > what are peoples' thoughts? I quite like the attribute solution best, but > I'd be happy with anything that moves us forward.I think (2) is a good solution, but am wondering whether you intend to expose that attribute to users, or whether it's one that can only be created implicitly by the compiler? ~Aaron> > Cheers, > > James > > On Wed, 4 Nov 2015 at 17:46 Philip Reames via llvm-commits > <llvm-commits at lists.llvm.org> wrote: >> >> This should probably be raised on llvm-dev for boarder visibility. >> >> Side question: What optimizations or codegen opportunities does this >> enable? i.e. what's the actual use case? >> >> >> On 11/02/2015 05:03 AM, James Molloy via llvm-commits wrote: >> >> jmolloy created this revision. >> jmolloy added reviewers: manmanren, dexonsmith, joker.eph. >> jmolloy added a subscriber: llvm-commits. >> jmolloy set the repository for this revision to rL LLVM. >> >> This attribute allows the compiler to assume that the function never >> recurses into itself, either directly or indirectly (transitively). This can >> be used among other things to demote global variables to locals. >> >> The norecurse attribute indicates that the function does not call itself >> either directly or indirectly down any possible call path. >> >> Repository: >> rL LLVM >> >> http://reviews.llvm.org/D14227 >> >> Files: >> docs/LangRef.rst >> include/llvm/Bitcode/LLVMBitCodes.h >> include/llvm/IR/Attributes.h >> include/llvm/IR/Function.h >> lib/AsmParser/LLLexer.cpp >> lib/AsmParser/LLParser.cpp >> lib/AsmParser/LLToken.h >> lib/Bitcode/Reader/BitcodeReader.cpp >> lib/Bitcode/Writer/BitcodeWriter.cpp >> lib/IR/Attributes.cpp >> lib/IR/Verifier.cpp >> test/Bindings/llvm-c/invalid-bitcode.test >> test/Bitcode/attributes.ll >> test/Bitcode/compatibility.ll >> test/Bitcode/invalid.ll >> test/LTO/X86/invalid.ll >> >> >> >> _______________________________________________ >> llvm-commits mailing list >> llvm-commits at lists.llvm.org >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits >> >> >> _______________________________________________ >> llvm-commits mailing list >> llvm-commits at lists.llvm.org >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >
James Molloy via llvm-dev
2015-Nov-05 16:06 UTC
[llvm-dev] [PATCH] D14227: Add a new attribute: norecurse
Hi Aaron, I think it must necessarily be exposed to users - clang must add it in certain circumstances for example. I don't think this is particularly different to many other attributes such as nocapture/nounwind, that are exposed to users and can be set by users in exceptional circumstances but are primarily inferred by the midend. James On Thu, 5 Nov 2015 at 16:03 Aaron Ballman <aaron at aaronballman.com> wrote:> On Thu, Nov 5, 2015 at 10:44 AM, James Molloy via llvm-dev > <llvm-dev at lists.llvm.org> wrote: > > [Adding llvm-dev and re-stating the situation for llvm-dev's benefit] > > > > RFC: A new attribute, "norecurse". > > > > In some cases, it is possible to demote global variables to local > variables. > > This is possible when the global is only used in one function, and that > > function is known not to recurse (because if the function recurses, a > local > > variable cannot be equivalent to a global as the global would hold state > > over the recursive call). > > > > GlobalOpt has this ability already, however it is currently (a) weak and > (b) > > broken. > > > > GlobalOpt has a special case for the function "main". It assumes that any > > function called "main" with external linkage is by definition > non-recursive. > > It does this because in C++, main is defined by the standard not to > recurse. > > However, this is not the case in C, so GlobalOpt will happily break C > code. > > > > GlobalOpt also currently won't even attempt to discover functions that > don't > > recurse - it only checks "main". > > > > What I'd like to do is improve GlobalOpt to be more aggressive with > demoting > > globals to locals, and to do that I need to teach it which functions are > > known to be non-recursive. At the same time I'd really like to fix the > > "main" kludge. > > > > There are three options I see: > > 1. Just use an analysis pass to infer non-recursiveness as a property. > > This can be a simple SCC pass which is queried by GlobalOpt. > > 2. Add an attribute, "norecurse". This would be inferred just like > above > > by FunctionAttrs in the general case, but it also allows frontends to add > > the attribute if they have specific knowledge - for example "main" in C++ > > mode. > > 3. (1), but use metadata to add the non-recursiveness information in > the > > frontend, to solve the "main" problem. > > > > What I'm suggesting here is (2). I have no real problem implementing (3) > > instead, and I think it's something that's worthwhile discussing. Adding > new > > metadata is very cheap and easy and doesn't seem to have many downsides > as > > an option. > > > > Hopefully I've described the problem and potential solutions well enough > - > > what are peoples' thoughts? I quite like the attribute solution best, but > > I'd be happy with anything that moves us forward. > > I think (2) is a good solution, but am wondering whether you intend to > expose that attribute to users, or whether it's one that can only be > created implicitly by the compiler? > > ~Aaron > > > > > Cheers, > > > > James > > > > On Wed, 4 Nov 2015 at 17:46 Philip Reames via llvm-commits > > <llvm-commits at lists.llvm.org> wrote: > >> > >> This should probably be raised on llvm-dev for boarder visibility. > >> > >> Side question: What optimizations or codegen opportunities does this > >> enable? i.e. what's the actual use case? > >> > >> > >> On 11/02/2015 05:03 AM, James Molloy via llvm-commits wrote: > >> > >> jmolloy created this revision. > >> jmolloy added reviewers: manmanren, dexonsmith, joker.eph. > >> jmolloy added a subscriber: llvm-commits. > >> jmolloy set the repository for this revision to rL LLVM. > >> > >> This attribute allows the compiler to assume that the function never > >> recurses into itself, either directly or indirectly (transitively). > This can > >> be used among other things to demote global variables to locals. > >> > >> The norecurse attribute indicates that the function does not call itself > >> either directly or indirectly down any possible call path. > >> > >> Repository: > >> rL LLVM > >> > >> http://reviews.llvm.org/D14227 > >> > >> Files: > >> docs/LangRef.rst > >> include/llvm/Bitcode/LLVMBitCodes.h > >> include/llvm/IR/Attributes.h > >> include/llvm/IR/Function.h > >> lib/AsmParser/LLLexer.cpp > >> lib/AsmParser/LLParser.cpp > >> lib/AsmParser/LLToken.h > >> lib/Bitcode/Reader/BitcodeReader.cpp > >> lib/Bitcode/Writer/BitcodeWriter.cpp > >> lib/IR/Attributes.cpp > >> lib/IR/Verifier.cpp > >> test/Bindings/llvm-c/invalid-bitcode.test > >> test/Bitcode/attributes.ll > >> test/Bitcode/compatibility.ll > >> test/Bitcode/invalid.ll > >> test/LTO/X86/invalid.ll > >> > >> > >> > >> _______________________________________________ > >> llvm-commits mailing list > >> llvm-commits at lists.llvm.org > >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits > >> > >> > >> _______________________________________________ > >> llvm-commits mailing list > >> llvm-commits at lists.llvm.org > >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits > > > > > > _______________________________________________ > > 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/20151105/6a555265/attachment.html>
Duncan P. N. Exon Smith via llvm-dev
2015-Nov-05 17:45 UTC
[llvm-dev] [PATCH] D14227: Add a new attribute: norecurse
> On 2015-Nov-05, at 07:54, Hal Finkel <hfinkel at anl.gov> wrote: > > > From: "James Molloy via llvm-dev" <llvm-dev at lists.llvm.org> > To: "Philip Reames" <listmail at philipreames.com>, reviews+D14227+public+6a20206dc9791b02 at reviews.llvm.org, "James Molloy" <james.molloy at arm.com>, "manman ren" <manman.ren at gmail.com>, dexonsmith at apple.com, "mehdi amini" <mehdi.amini at apple.com>, "LLVM Dev" <llvm-dev at lists.llvm.org> > Cc: "LLVM Commits" <llvm-commits at lists.llvm.org> > Sent: Thursday, November 5, 2015 9:44:45 AM > Subject: Re: [llvm-dev] [PATCH] D14227: Add a new attribute: norecurse > > [Adding llvm-dev and re-stating the situation for llvm-dev's benefit] > > RFC: A new attribute, "norecurse". > > In some cases, it is possible to demote global variables to local variables. This is possible when the global is only used in one function, and that function is known not to recurse (because if the function recurses, a local variable cannot be equivalent to a global as the global would hold state over the recursive call). > > GlobalOpt has this ability already, however it is currently (a) weak and (b) broken. > > GlobalOpt has a special case for the function "main". It assumes that any function called "main" with external linkage is by definition non-recursive. It does this because in C++, main is defined by the standard not to recurse. However, this is not the case in C, so GlobalOpt will happily break C code. > > GlobalOpt also currently won't even attempt to discover functions that don't recurse - it only checks "main". > > What I'd like to do is improve GlobalOpt to be more aggressive with demoting globals to locals, and to do that I need to teach it which functions are known to be non-recursive. At the same time I'd really like to fix the "main" kludge. > > There are three options I see: > 1. Just use an analysis pass to infer non-recursiveness as a property. This can be a simple SCC pass which is queried by GlobalOpt. > 2. Add an attribute, "norecurse". This would be inferred just like above by FunctionAttrs in the general case, but it also allows frontends to add the attribute if they have specific knowledge - for example "main" in C++ mode. > 3. (1), but use metadata to add the non-recursiveness information in the frontend, to solve the "main" problem. > > What I'm suggesting here is (2). > > +1 > > This is a very generic property, and I'm happy with the conciseness provided by an attribute.+1 I think (2), an IR-level attribute, makes the most sense.