On 11/24/2010 06:55 PM, Owen Anderson wrote:> On Nov 23, 2010, at 9:22 AM, Andrew Clinton wrote: > > >> Most of my programs contain loops that the LoopDeletion pass is unable >> to remove. It appears that the following code in LoopDeletion.cpp:152 >> is the culprit: >> >> ScalarEvolution& SE = getAnalysis<ScalarEvolution>(); >> const SCEV *S = SE.getMaxBackedgeTakenCount(L); >> if (isa<SCEVCouldNotCompute>(S)) >> return Changed; >> >> So, LoopDeletion thinks my loops might be infinite so it does not delete >> them - even if they do not write to any of the function return values. >> Is there a way to flag a loop as non-infinite? Or will I need to create >> my own modified loop deletion pass that can eliminate potentially >> infinite loops. Is it correct just to remove the above code to allow >> deletion of infinite loops? >> > No. Removing an infinite loop changes the semantics of the source program. > > The question you should be asking is: why can't ScalarEvolution determine that your loops are finite? > > --Owen >That's a good question. I think the reason that ScalarEvolution doesn't know the loop is finite is that the loop conditional depends on values that are only known at runtime, since I'm using external unbound functions as input to the loop's conditional branch. So given that eliminating infinite loops is incorrect, I guess my question now would be what is the best way to let LLVM know that my loop is finite. In this case, I think I have more information than LLVM - the functions that evaluate at runtime to determine the loop iteration count will eventually cause the loop to terminate, but I don't see any way to indicate to the optimizer that this is the case. Andrew
On 11/25/2010 12:59 PM, Andrew Clinton wrote:> On 11/24/2010 06:55 PM, Owen Anderson wrote: >> On Nov 23, 2010, at 9:22 AM, Andrew Clinton wrote: >> >> >>> Most of my programs contain loops that the LoopDeletion pass is unable >>> to remove. It appears that the following code in LoopDeletion.cpp:152 >>> is the culprit: >>> >>> ScalarEvolution& SE = getAnalysis<ScalarEvolution>(); >>> const SCEV *S = SE.getMaxBackedgeTakenCount(L); >>> if (isa<SCEVCouldNotCompute>(S)) >>> return Changed; >>> >>> So, LoopDeletion thinks my loops might be infinite so it does not delete >>> them - even if they do not write to any of the function return values. >>> Is there a way to flag a loop as non-infinite? Or will I need to create >>> my own modified loop deletion pass that can eliminate potentially >>> infinite loops. Is it correct just to remove the above code to allow >>> deletion of infinite loops? >>> >> No. Removing an infinite loop changes the semantics of the source program. >> >> The question you should be asking is: why can't ScalarEvolution determine that your loops are finite? >> >> --Owen >> > That's a good question. I think the reason that ScalarEvolution doesn't > know the loop is finite is that the loop conditional depends on values > that are only known at runtime, since I'm using external unbound > functions as input to the loop's conditional branch. > > So given that eliminating infinite loops is incorrect, I guess my > question now would be what is the best way to let LLVM know that my loop > is finite. In this case, I think I have more information than LLVM - > the functions that evaluate at runtime to determine the loop iteration > count will eventually cause the loop to terminate, but I don't see any > way to indicate to the optimizer that this is the case. > > AndrewI'm thinking a good way to support this feature would be to add a new function attribute "AlwaysReturn" that would indicate that a function does not contain any infinite loops, so that the LoopDeletion pass and others could treat it accordingly. What do you think? What's the best way for me to submit changes back to the LLVM repository? Andrew
Andrew Clinton wrote:> On 11/25/2010 12:59 PM, Andrew Clinton wrote: >> On 11/24/2010 06:55 PM, Owen Anderson wrote: >>> On Nov 23, 2010, at 9:22 AM, Andrew Clinton wrote: >>> >>> >>>> Most of my programs contain loops that the LoopDeletion pass is unable >>>> to remove. It appears that the following code in LoopDeletion.cpp:152 >>>> is the culprit: >>>> >>>> ScalarEvolution& SE = getAnalysis<ScalarEvolution>(); >>>> const SCEV *S = SE.getMaxBackedgeTakenCount(L); >>>> if (isa<SCEVCouldNotCompute>(S)) >>>> return Changed; >>>> >>>> So, LoopDeletion thinks my loops might be infinite so it does not delete >>>> them - even if they do not write to any of the function return values. >>>> Is there a way to flag a loop as non-infinite? Or will I need to create >>>> my own modified loop deletion pass that can eliminate potentially >>>> infinite loops. Is it correct just to remove the above code to allow >>>> deletion of infinite loops? >>>> >>> No. Removing an infinite loop changes the semantics of the source program. >>> >>> The question you should be asking is: why can't ScalarEvolution determine that your loops are finite? >>> >>> --Owen >>> >> That's a good question. I think the reason that ScalarEvolution doesn't >> know the loop is finite is that the loop conditional depends on values >> that are only known at runtime, since I'm using external unbound >> functions as input to the loop's conditional branch. >> >> So given that eliminating infinite loops is incorrect, I guess my >> question now would be what is the best way to let LLVM know that my loop >> is finite. In this case, I think I have more information than LLVM - >> the functions that evaluate at runtime to determine the loop iteration >> count will eventually cause the loop to terminate, but I don't see any >> way to indicate to the optimizer that this is the case. >> >> Andrew > > I'm thinking a good way to support this feature would be to add a new > function attribute "AlwaysReturn" that would indicate that a function > does not contain any infinite loops, so that the LoopDeletion pass and > others could treat it accordingly. What do you think?I called it "halting": http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html but it turns out that making it efficient at compile time and make the optimizers make use of it is very tricky. In short, we want to be able to automatically deduce that a function is halting (as well as permitting labelling by the frontend which is easy) and that deduction requires a FunctionPass but the user of the information is a CallGraphSCCPass and you can't have CGSCC passes depending on function passes. So, it's blocked on changes to the pass manager to make this possible.> What's the best way for me to submit changes back to the LLVM repository?Email patches to llvm-commits. But first, please read http://llvm.org/docs/DeveloperPolicy.html . Nick
On Fri, Nov 26, 2010 at 11:14 PM, Andrew Clinton <andrew at sidefx.com> wrote:> I'm thinking a good way to support this feature would be to add a new > function attribute "AlwaysReturn" that would indicate that a function > does not contain any infinite loops, so that the LoopDeletion pass and > others could treat it accordingly. What do you think?That's probably the best way to really fix this, yes. I'd go for a different name though, since 'AlwaysReturn' implies the function doesn't throw any exceptions, which is a separate issue already addressed by 'nounwind'. You'll also want some way to set the attribute. Ideally, some pass would automatically set it on appropriate functions. For some of the other attributes -functionattrs does this. It'd probably be a decent place to set the attribute for simple non-looping functions, but getting the best results probably requires something like ScalarEvolution analysis so I'm not sure if this would be appropriate there. Eventually llvm-gcc/dragonegg/clang should also have support for an explicit attribute to set this, but first it should work :).> What's the best way for me to submit changes back to the LLVM repository?Assuming the question means you don't have commit access, just send one or more patches to llvm-commits at cs.uiuc.edu.