X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FLoopSimplify.cpp;h=1ad4d768d11e8bfe615c91fe0f6db1919734decb;hb=7f2eff792a2e18758a25956abdac2440ee18dd7f;hp=1571fe8f0b36ed70af9871939dcd9f6b276eea7b;hpb=1f74590e9d1b9cf0f1f81a156efea73f76546e05;p=oota-llvm.git diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp index 1571fe8f0b3..1ad4d768d11 100644 --- a/lib/Transforms/Utils/LoopSimplify.cpp +++ b/lib/Transforms/Utils/LoopSimplify.cpp @@ -37,26 +37,29 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "loopsimplify" +#define DEBUG_TYPE "loop-simplify" #include "llvm/Transforms/Scalar.h" -#include "llvm/Constants.h" -#include "llvm/Instructions.h" -#include "llvm/IntrinsicInst.h" -#include "llvm/Function.h" -#include "llvm/LLVMContext.h" -#include "llvm/Type.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/SetOperations.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/DependenceAnalysis.h" +#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolution.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.h" -#include "llvm/Transforms/Utils/Local.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Type.h" #include "llvm/Support/CFG.h" #include "llvm/Support/Debug.h" -#include "llvm/ADT/SetOperations.h" -#include "llvm/ADT/SetVector.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Utils/LoopUtils.h" using namespace llvm; STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted"); @@ -65,29 +68,31 @@ STATISTIC(NumNested , "Number of nested loops split out"); namespace { struct LoopSimplify : public LoopPass { static char ID; // Pass identification, replacement for typeid - LoopSimplify() : LoopPass(&ID) {} + LoopSimplify() : LoopPass(ID) { + initializeLoopSimplifyPass(*PassRegistry::getPassRegistry()); + } // AA - If we have an alias analysis object to update, this is it, otherwise // this is null. AliasAnalysis *AA; LoopInfo *LI; DominatorTree *DT; + ScalarEvolution *SE; Loop *L; virtual bool runOnLoop(Loop *L, LPPassManager &LPM); virtual void getAnalysisUsage(AnalysisUsage &AU) const { // We need loop information to identify the loops... - AU.addRequired(); - AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); AU.addRequired(); AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); + AU.addPreserved(); AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. - AU.addPreserved(); - AU.addPreservedID(LCSSAID); } /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees. @@ -96,21 +101,26 @@ namespace { private: bool ProcessLoop(Loop *L, LPPassManager &LPM); BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); - BasicBlock *InsertPreheaderForLoop(Loop *L); - Loop *SeparateNestedLoop(Loop *L, LPPassManager &LPM); + Loop *SeparateNestedLoop(Loop *L, LPPassManager &LPM, + BasicBlock *Preheader); BasicBlock *InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader); - void PlaceSplitBlockCarefully(BasicBlock *NewBB, - SmallVectorImpl &SplitPreds, - Loop *L); }; } -char LoopSimplify::ID = 0; -static RegisterPass -X("loopsimplify", "Canonicalize natural loops", true); +static void PlaceSplitBlockCarefully(BasicBlock *NewBB, + SmallVectorImpl &SplitPreds, + Loop *L); -// Publically exposed interface to pass... -const PassInfo *const llvm::LoopSimplifyID = &X; +char LoopSimplify::ID = 0; +INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify", + "Canonicalize natural loops", true, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LoopInfo) +INITIALIZE_PASS_END(LoopSimplify, "loop-simplify", + "Canonicalize natural loops", true, false) + +// Publicly exposed interface to pass... +char &llvm::LoopSimplifyID = LoopSimplify::ID; Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } /// runOnLoop - Run down all loops in the CFG (recursively, but we could do @@ -121,7 +131,8 @@ bool LoopSimplify::runOnLoop(Loop *l, LPPassManager &LPM) { bool Changed = false; LI = &getAnalysis(); AA = getAnalysisIfAvailable(); - DT = &getAnalysis(); + DT = &getAnalysis().getDomTree(); + SE = getAnalysisIfAvailable(); Changed |= ProcessLoop(L, LPM); @@ -155,9 +166,8 @@ ReprocessLoop: for (SmallPtrSet::iterator I = BadPreds.begin(), E = BadPreds.end(); I != E; ++I) { - DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor "; - WriteAsOperand(dbgs(), *I, false); - dbgs() << "\n"); + DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor " + << (*I)->getName() << "\n"); // Inform each successor of each dead pred. for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI) @@ -182,12 +192,16 @@ ReprocessLoop: if (BI->isConditional()) { if (UndefValue *Cond = dyn_cast(BI->getCondition())) { - DEBUG(dbgs() << "LoopSimplify: Resolving \"br i1 undef\" to exit in "; - WriteAsOperand(dbgs(), *I, false); - dbgs() << "\n"); + DEBUG(dbgs() << "LoopSimplify: Resolving \"br i1 undef\" to exit in " + << (*I)->getName() << "\n"); BI->setCondition(ConstantInt::get(Cond->getType(), !L->contains(BI->getSuccessor(0)))); + + // This may make the loop analyzable, force SCEV recomputation. + if (SE) + SE->forgetLoop(L); + Changed = true; } } @@ -195,7 +209,7 @@ ReprocessLoop: // Does the loop already have a preheader? If so, don't insert one. BasicBlock *Preheader = L->getLoopPreheader(); if (!Preheader) { - Preheader = InsertPreheaderForLoop(L); + Preheader = InsertPreheaderForLoop(L, this); if (Preheader) { ++NumInserted; Changed = true; @@ -208,7 +222,7 @@ ReprocessLoop: // predecessors from outside of the loop, split the edge now. SmallVector ExitBlocks; L->getExitBlocks(ExitBlocks); - + SmallSetVector ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); for (SmallSetVector::iterator I = ExitBlockSet.begin(), @@ -235,7 +249,7 @@ ReprocessLoop: // this for loops with a giant number of backedges, just factor them into a // common backedge instead. if (L->getNumBackEdges() < 8) { - if (SeparateNestedLoop(L, LPM)) { + if (SeparateNestedLoop(L, LPM, Preheader)) { ++NumNested; // This is a big restructuring change, reprocess the whole loop. Changed = true; @@ -260,8 +274,9 @@ ReprocessLoop: PHINode *PN; for (BasicBlock::iterator I = L->getHeader()->begin(); (PN = dyn_cast(I++)); ) - if (Value *V = PN->hasConstantValue(DT)) { + if (Value *V = SimplifyInstruction(PN, 0, 0, DT)) { if (AA) AA->deleteValue(PN); + if (SE) SE->forgetValue(PN); PN->replaceAllUsesWith(V); PN->eraseFromParent(); } @@ -294,6 +309,7 @@ ReprocessLoop: // Attempt to hoist out all instructions except for the // comparison and the branch. bool AllInvariant = true; + bool AnyInvariant = false; for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) { Instruction *Inst = I++; // Skip debug info intrinsics. @@ -301,12 +317,19 @@ ReprocessLoop: continue; if (Inst == CI) continue; - if (!L->makeLoopInvariant(Inst, Changed, - Preheader ? Preheader->getTerminator() : 0)) { + if (!L->makeLoopInvariant(Inst, AnyInvariant, + Preheader ? Preheader->getTerminator() : 0)) { AllInvariant = false; break; } } + if (AnyInvariant) { + Changed = true; + // The loop disposition of all SCEV expressions that depend on any + // hoisted values have also changed. + if (SE) + SE->forgetLoopDispositions(L); + } if (!AllInvariant) continue; // The block has now been cleared of all instructions except for @@ -315,29 +338,29 @@ ReprocessLoop: if (!FoldBranchToCommonDest(BI)) continue; // Success. The block is now dead, so remove it from the loop, - // update the dominator tree and dominance frontier, and delete it. + // update the dominator tree and delete it. + DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block " + << ExitingBlock->getName() << "\n"); - DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block "; - WriteAsOperand(dbgs(), ExitingBlock, false); - dbgs() << "\n"); + // Notify ScalarEvolution before deleting this block. Currently assume the + // parent loop doesn't change (spliting edges doesn't count). If blocks, + // CFG edges, or other values in the parent loop change, then we need call + // to forgetLoop() for the parent instead. + if (SE) + SE->forgetLoop(L); assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock)); Changed = true; LI->removeBlock(ExitingBlock); - DominanceFrontier *DF = getAnalysisIfAvailable(); DomTreeNode *Node = DT->getNode(ExitingBlock); const std::vector *> &Children = Node->getChildren(); while (!Children.empty()) { DomTreeNode *Child = Children.front(); DT->changeImmediateDominator(Child, Node->getIDom()); - if (DF) DF->changeImmediateDominator(Child->getBlock(), - Node->getIDom()->getBlock(), - DT); } DT->eraseNode(ExitingBlock); - if (DF) DF->removeBlock(ExitingBlock); BI->getSuccessor(0)->removePredecessor(ExitingBlock); BI->getSuccessor(1)->removePredecessor(ExitingBlock); @@ -352,7 +375,7 @@ ReprocessLoop: /// preheader, this method is called to insert one. This method has two phases: /// preheader insertion and analysis updating. /// -BasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) { +BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, Pass *PP) { BasicBlock *Header = L->getHeader(); // Compute the set of predecessors of the loop that are not in the loop. @@ -372,19 +395,27 @@ BasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) { } // Split out the loop pre-header. - BasicBlock *NewBB = - SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(), - ".preheader", this); + BasicBlock *PreheaderBB; + if (!Header->isLandingPad()) { + PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", + PP); + } else { + SmallVector NewBBs; + SplitLandingPadPredecessors(Header, OutsideBlocks, ".preheader", + ".split-lp", PP, NewBBs); + PreheaderBB = NewBBs[0]; + } - DEBUG(dbgs() << "LoopSimplify: Creating pre-header "; - WriteAsOperand(dbgs(), NewBB, false); - dbgs() << "\n"); + PreheaderBB->getTerminator()->setDebugLoc( + Header->getFirstNonPHI()->getDebugLoc()); + DEBUG(dbgs() << "LoopSimplify: Creating pre-header " + << PreheaderBB->getName() << "\n"); // Make sure that NewBB is put someplace intelligent, which doesn't mess up // code layout too horribly. - PlaceSplitBlockCarefully(NewBB, OutsideBlocks, L); + PlaceSplitBlockCarefully(PreheaderBB, OutsideBlocks, L); - return NewBB; + return PreheaderBB; } /// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit @@ -403,15 +434,22 @@ BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { } assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); - BasicBlock *NewBB = SplitBlockPredecessors(Exit, &LoopBlocks[0], - LoopBlocks.size(), ".loopexit", - this); - - DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "; - WriteAsOperand(dbgs(), NewBB, false); - dbgs() << "\n"); + BasicBlock *NewExitBB = 0; + + if (Exit->isLandingPad()) { + SmallVector NewBBs; + SplitLandingPadPredecessors(Exit, ArrayRef(&LoopBlocks[0], + LoopBlocks.size()), + ".loopexit", ".nonloopexit", + this, NewBBs); + NewExitBB = NewBBs[0]; + } else { + NewExitBB = SplitBlockPredecessors(Exit, LoopBlocks, ".loopexit", this); + } - return NewBB; + DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block " + << NewExitBB->getName() << "\n"); + return NewExitBB; } /// AddBlockAndPredsToSet - Add the specified block, and all of its @@ -436,11 +474,11 @@ static void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock, /// FindPHIToPartitionLoops - The first part of loop-nestification is to find a /// PHI node that tells us how to partition the loops. static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT, - AliasAnalysis *AA) { + AliasAnalysis *AA, LoopInfo *LI) { for (BasicBlock::iterator I = L->getHeader()->begin(); isa(I); ) { PHINode *PN = cast(I); ++I; - if (Value *V = PN->hasConstantValue(DT)) { + if (Value *V = SimplifyInstruction(PN, 0, 0, DT)) { // This is a degenerate PHI already, don't modify it! PN->replaceAllUsesWith(V); if (AA) AA->deleteValue(PN); @@ -461,32 +499,32 @@ static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT, // PlaceSplitBlockCarefully - If the block isn't already, move the new block to // right after some 'outside block' block. This prevents the preheader from // being placed inside the loop body, e.g. when the loop hasn't been rotated. -void LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB, - SmallVectorImpl &SplitPreds, - Loop *L) { +void PlaceSplitBlockCarefully(BasicBlock *NewBB, + SmallVectorImpl &SplitPreds, + Loop *L) { // Check to see if NewBB is already well placed. Function::iterator BBI = NewBB; --BBI; for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { if (&*BBI == SplitPreds[i]) return; } - + // If it isn't already after an outside block, move it after one. This is // always good as it makes the uncond branch from the outside block into a // fall-through. - + // Figure out *which* outside block to put this after. Prefer an outside // block that neighbors a BB actually in the loop. BasicBlock *FoundBB = 0; for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { Function::iterator BBI = SplitPreds[i]; - if (++BBI != NewBB->getParent()->end() && + if (++BBI != NewBB->getParent()->end() && L->contains(BBI)) { FoundBB = SplitPreds[i]; break; } } - + // If our heuristic for a *good* bb to place this after doesn't find // anything, just pick something. It's likely better than leaving it within // the loop. @@ -513,35 +551,48 @@ void LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB, /// If we are able to separate out a loop, return the new outer loop that was /// created. /// -Loop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM) { - PHINode *PN = FindPHIToPartitionLoops(L, DT, AA); +Loop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM, + BasicBlock *Preheader) { + // Don't try to separate loops without a preheader. + if (!Preheader) + return 0; + + // The header is not a landing pad; preheader insertion should ensure this. + assert(!L->getHeader()->isLandingPad() && + "Can't insert backedge to landing pad"); + + PHINode *PN = FindPHIToPartitionLoops(L, DT, AA, LI); if (PN == 0) return 0; // No known way to partition. // Pull out all predecessors that have varying values in the loop. This // handles the case when a PHI node has multiple instances of itself as // arguments. SmallVector OuterLoopPreds; - for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { if (PN->getIncomingValue(i) != PN || !L->contains(PN->getIncomingBlock(i))) { // We can't split indirectbr edges. if (isa(PN->getIncomingBlock(i)->getTerminator())) return 0; - OuterLoopPreds.push_back(PN->getIncomingBlock(i)); } - + } DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n"); + // If ScalarEvolution is around and knows anything about values in + // this loop, tell it to forget them, because we're about to + // substantially change it. + if (SE) + SE->forgetLoop(L); + BasicBlock *Header = L->getHeader(); - BasicBlock *NewBB = SplitBlockPredecessors(Header, &OuterLoopPreds[0], - OuterLoopPreds.size(), - ".outer", this); + BasicBlock *NewBB = + SplitBlockPredecessors(Header, OuterLoopPreds, ".outer", this); // Make sure that NewBB is put someplace intelligent, which doesn't mess up // code layout too horribly. PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L); - + // Create the new outer loop. Loop *NewOuter = new Loop(); @@ -618,10 +669,18 @@ LoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) { if (!Preheader) return 0; + // The header is not a landing pad; preheader insertion should ensure this. + assert(!Header->isLandingPad() && "Can't insert backedge to landing pad"); + // Figure out which basic blocks contain back-edges to the loop header. std::vector BackedgeBlocks; for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I){ BasicBlock *P = *I; + + // Indirectbr edges cannot be split, so we must fail if we find one. + if (isa(P->getTerminator())) + return 0; + if (P != Preheader) BackedgeBlocks.push_back(P); } @@ -630,9 +689,8 @@ LoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) { Header->getName()+".backedge", F); BranchInst *BETerminator = BranchInst::Create(Header, BEBlock); - DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block "; - WriteAsOperand(dbgs(), BEBlock, false); - dbgs() << "\n"); + DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block " + << BEBlock->getName() << "\n"); // Move the new backedge block to right after the last backedge block. Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; @@ -642,9 +700,8 @@ LoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) { // the backedge block which correspond to any PHI nodes in the header block. for (BasicBlock::iterator I = Header->begin(); isa(I); ++I) { PHINode *PN = cast(I); - PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName()+".be", - BETerminator); - NewPN->reserveOperandSpace(BackedgeBlocks.size()); + PHINode *NewPN = PHINode::Create(PN->getType(), BackedgeBlocks.size(), + PN->getName()+".be", BETerminator); if (AA) AA->copyValue(PN, NewPN); // Loop over the PHI node, moving all entries except the one for the @@ -708,8 +765,6 @@ LoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) { // Update dominator information DT->splitBlock(BEBlock); - if (DominanceFrontier *DF = getAnalysisIfAvailable()) - DF->splitBlock(BEBlock); return BEBlock; } @@ -731,6 +786,7 @@ void LoopSimplify::verifyAnalysis() const { } assert(HasIndBrPred && "LoopSimplify has no excuse for missing loop header info!"); + (void)HasIndBrPred; } // Indirectbr can interfere with exit block canonicalization. @@ -738,12 +794,15 @@ void LoopSimplify::verifyAnalysis() const { bool HasIndBrExiting = false; SmallVector ExitingBlocks; L->getExitingBlocks(ExitingBlocks); - for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) + for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { if (isa((ExitingBlocks[i])->getTerminator())) { HasIndBrExiting = true; break; } + } + assert(HasIndBrExiting && "LoopSimplify has no excuse for missing exit block info!"); + (void)HasIndBrExiting; } }