X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FLoopSimplify.cpp;h=246263026bb495268eb5787bd0aa946bdf5f9333;hb=2bc2a08b1bf6b5dcbfa515acc85999d6f884ec1a;hp=1ef3c32ae58f5c447ab0d57505c5b1be9f76f366;hpb=689fac02268929b756086753b4656d6dabc5cf2d;p=oota-llvm.git diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp index 1ef3c32ae58..246263026bb 100644 --- a/lib/Transforms/Utils/LoopSimplify.cpp +++ b/lib/Transforms/Utils/LoopSimplify.cpp @@ -37,7 +37,7 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "loopsimplify" +#define DEBUG_TYPE "loop-simplify" #include "llvm/Transforms/Scalar.h" #include "llvm/Constants.h" #include "llvm/Instructions.h" @@ -47,6 +47,7 @@ #include "llvm/Type.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" @@ -65,24 +66,27 @@ 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.addRequiredTransitive(); - AU.addRequiredTransitive(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); AU.addPreserved(); - AU.addPreserved(); - AU.addPreserved(); + AU.addPreserved(); AU.addPreserved(); AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. @@ -104,11 +108,15 @@ namespace { } char LoopSimplify::ID = 0; -static RegisterPass -X("loopsimplify", "Canonicalize natural loops", true); +INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify", + "Canonicalize natural loops", true, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTree) +INITIALIZE_PASS_DEPENDENCY(LoopInfo) +INITIALIZE_PASS_END(LoopSimplify, "loop-simplify", + "Canonicalize natural loops", true, false) // Publically exposed interface to pass... -const PassInfo *const llvm::LoopSimplifyID = &X; +char &llvm::LoopSimplifyID = LoopSimplify::ID; Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } /// runOnLoop - Run down all loops in the CFG (recursively, but we could do @@ -120,6 +128,7 @@ bool LoopSimplify::runOnLoop(Loop *l, LPPassManager &LPM) { LI = &getAnalysis(); AA = getAnalysisIfAvailable(); DT = &getAnalysis(); + SE = getAnalysisIfAvailable(); Changed |= ProcessLoop(L, LPM); @@ -141,18 +150,20 @@ ReprocessLoop: BB != E; ++BB) { if (*BB == L->getHeader()) continue; - SmallPtrSet BadPreds; - for (pred_iterator PI = pred_begin(*BB), PE = pred_end(*BB); PI != PE; ++PI) - if (!L->contains(*PI)) - BadPreds.insert(*PI); + SmallPtrSet BadPreds; + for (pred_iterator PI = pred_begin(*BB), + PE = pred_end(*BB); PI != PE; ++PI) { + BasicBlock *P = *PI; + if (!L->contains(P)) + BadPreds.insert(P); + } // Delete each unique out-of-loop (and thus dead) predecessor. - for (SmallPtrSet::iterator I = BadPreds.begin(), + 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) @@ -177,9 +188,8 @@ 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)))); @@ -192,7 +202,7 @@ ReprocessLoop: if (!Preheader) { Preheader = InsertPreheaderForLoop(L); if (Preheader) { - NumInserted++; + ++NumInserted; Changed = true; } } @@ -215,7 +225,7 @@ ReprocessLoop: // allowed. if (!L->contains(*PI)) { if (RewriteLoopExitBlock(L, ExitBlock)) { - NumInserted++; + ++NumInserted; Changed = true; } break; @@ -244,7 +254,7 @@ ReprocessLoop: // loop header. LoopLatch = InsertUniqueBackedgeBlock(L, Preheader); if (LoopLatch) { - NumInserted++; + ++NumInserted; Changed = true; } } @@ -255,8 +265,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, DT)) { if (AA) AA->deleteValue(PN); + if (SE) SE->forgetValue(PN); PN->replaceAllUsesWith(V); PN->eraseFromParent(); } @@ -310,29 +321,22 @@ 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. - - DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block "; - WriteAsOperand(dbgs(), ExitingBlock, false); - dbgs() << "\n"); + // update the dominator tree and delete it. + DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block " + << ExitingBlock->getName() << "\n"); 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); @@ -353,25 +357,26 @@ BasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) { // Compute the set of predecessors of the loop that are not in the loop. SmallVector OutsideBlocks; for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); - PI != PE; ++PI) - if (!L->contains(*PI)) { // Coming in from outside the loop? + PI != PE; ++PI) { + BasicBlock *P = *PI; + if (!L->contains(P)) { // Coming in from outside the loop? // If the loop is branched to from an indirect branch, we won't // be able to fully transform the loop, because it prohibits // edge splitting. - if (isa((*PI)->getTerminator())) return 0; + if (isa(P->getTerminator())) return 0; // Keep track of it. - OutsideBlocks.push_back(*PI); + OutsideBlocks.push_back(P); } + } // Split out the loop pre-header. BasicBlock *NewBB = SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(), ".preheader", this); - DEBUG(dbgs() << "LoopSimplify: Creating pre-header "; - WriteAsOperand(dbgs(), NewBB, false); - dbgs() << "\n"); + DEBUG(dbgs() << "LoopSimplify: Creating pre-header " << NewBB->getName() + << "\n"); // Make sure that NewBB is put someplace intelligent, which doesn't mess up // code layout too horribly. @@ -385,23 +390,23 @@ BasicBlock *LoopSimplify::InsertPreheaderForLoop(Loop *L) { /// outside of the loop. BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { SmallVector LoopBlocks; - for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) - if (L->contains(*I)) { + for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) { + BasicBlock *P = *I; + if (L->contains(P)) { // Don't do this if the loop is exited via an indirect branch. - if (isa((*I)->getTerminator())) return 0; + if (isa(P->getTerminator())) return 0; - LoopBlocks.push_back(*I); + LoopBlocks.push_back(P); } + } 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"); - + DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block " + << NewBB->getName() << "\n"); return NewBB; } @@ -427,11 +432,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, DT)) { // This is a degenerate PHI already, don't modify it! PN->replaceAllUsesWith(V); if (AA) AA->deleteValue(PN); @@ -505,7 +510,7 @@ void LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB, /// created. /// Loop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM) { - PHINode *PN = FindPHIToPartitionLoops(L, DT, AA); + 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 @@ -524,6 +529,12 @@ Loop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM) { 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(), @@ -559,10 +570,11 @@ Loop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM) { // Determine which blocks should stay in L and which should be moved out to // the Outer loop now. std::set BlocksInL; - for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) - if (DT->dominates(Header, *PI)) - AddBlockAndPredsToSet(*PI, Header, BlocksInL); - + for (pred_iterator PI=pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) { + BasicBlock *P = *PI; + if (DT->dominates(Header, P)) + AddBlockAndPredsToSet(P, Header, BlocksInL); + } // Scan all of the loop children of L, moving them to OuterLoop if they are // not part of the inner loop. @@ -610,17 +622,23 @@ LoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) { // 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) - if (*I != Preheader) BackedgeBlocks.push_back(*I); + 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); + } // Create and insert the new backedge block... BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(), 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; @@ -696,8 +714,6 @@ LoopSimplify::InsertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader) { // Update dominator information DT->splitBlock(BEBlock); - if (DominanceFrontier *DF = getAnalysisIfAvailable()) - DF->splitBlock(BEBlock); return BEBlock; }