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 24, 2010, at 1:23 PM, Andrew Clinton wrote:> > 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.There is no way to do this with the standard pass set, because removing an infinite loop is an invalid transformation. John Regehr wrote a pretty good exposé about why it's illegal here: http://blog.regehr.org/archives/140 --Owen
On Nov 24, 2010, at 3:58 PM, Owen Anderson wrote:> > On Nov 24, 2010, at 1:23 PM, Andrew Clinton wrote: >> >> 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. > > There is no way to do this with the standard pass set, because removing an infinite loop is > an invalid transformation. John Regehr wrote a pretty good exposé about why it's illegal > here: http://blog.regehr.org/archives/140FWIW, this is currently a discussion in the C++ and C committees, and my understanding is that this has changed (or is changing soon) in the C'1x draft. Assuming it happens, it will make it valid to assume that loops always terminate unless they are written with a condition that is an integer constant expression that folds to 1. In addition to being able to delete noop loops that traverse over pointer-based data structures, this will also solve the: for (unsigned i = 0; i <= N; ++i) class of problems. I'm obviously strongly in favor of this, and I also think we should apply it to all C languages. I don't see any reason for people to write infinite loops with non-trivial conditions. -Chris