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?
Andrew
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?I think what you actually want is the ADCE pass (opt -adce). The reason we turned ADCE off by default is that it kept deleting infinite loops, and the LoopDeletion pass was written as a safe replacement. Nick
On 11/24/2010 03:36 PM, Nick Lewycky wrote:> 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? > > I think what you actually want is the ADCE pass (opt -adce). The > reason we turned ADCE off by default is that it kept deleting infinite > loops, and the LoopDeletion pass was written as a safe replacement. > > NickThis looks sort of like what I'm looking for. The only problem is that ADCE is treating all terminator instructions as live: // Collect the set of "root" instructions that are known live. for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) if (isa<TerminatorInst>(I.getInstructionIterator()) || isa<DbgInfoIntrinsic>(I.getInstructionIterator()) || I->mayHaveSideEffects()) { alive.insert(I.getInstructionIterator()); worklist.push_back(I.getInstructionIterator()); } Is this correct? I would have thought that branch instructions should not be initially live. FYI, removing the ScalarEvolution conditional in the LoopDeletion code (and copying the algorithm to my own loop deletion pass) seems to correctly handle the elimination of infinite loops. However I'd still like to find a way to do this with standard passes if possible. Andrew
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
On Nov 24, 2010, at 12:36 PM, Nick Lewycky wrote:> 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? > > I think what you actually want is the ADCE pass (opt -adce). The reason > we turned ADCE off by default is that it kept deleting infinite loops, > and the LoopDeletion pass was written as a safe replacement.This is incorrect. ADCE does not remove infinite loops either, as doing so would be semantics-changing transformation. --Owen
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