X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FLoopUnswitch.cpp;h=8d39a4dece31e4374d8727bb897376e6ca3a0441;hp=130db9fe4199e76529d9a9882fd1afd68bb7d19d;hb=4ee451de366474b9c228b4e5fa573795a715216d;hpb=684b22df79c51114a12289e10a4063d5f02259a9 diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp index 130db9fe419..8d39a4dece3 100644 --- a/lib/Transforms/Scalar/LoopUnswitch.cpp +++ b/lib/Transforms/Scalar/LoopUnswitch.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -41,7 +41,6 @@ #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/PostOrderIterator.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" @@ -71,6 +70,18 @@ namespace { bool OptimizeForSize; bool redoLoop; + + DominanceFrontier *DF; + DominatorTree *DT; + + /// LoopDF - Loop's dominance frontier. This set is a collection of + /// loop exiting blocks' DF member blocks. However this does set does not + /// includes basic blocks that are inside loop. + SmallPtrSet LoopDF; + + /// OrigLoopExitMap - This is used to map loop exiting block with + /// corresponding loop exit block, before updating CFG. + DenseMap OrigLoopExitMap; public: static char ID; // Pass ID, replacement for typeid explicit LoopUnswitch(bool Os = false) : @@ -103,6 +114,16 @@ namespace { if (I != LoopProcessWorklist.end()) LoopProcessWorklist.erase(I); } + + /// Split all of the edges from inside the loop to their exit blocks. Update + /// the appropriate Phi nodes as we do so. + void SplitExitEdges(Loop *L, const SmallVector &ExitBlocks, + SmallVector &MiddleBlocks); + + /// If BB's dominance frontier has a member that is not part of loop L then + /// remove it. Add NewDFMember in BB's dominance frontier. + void ReplaceLoopExternalDFMember(Loop *L, BasicBlock *BB, + BasicBlock *NewDFMember); bool UnswitchIfProfitable(Value *LoopCond, Constant *Val,Loop *L); unsigned getLoopUnswitchCost(Loop *L, Value *LIC); @@ -153,13 +174,16 @@ static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) { if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed)) return RHS; } - - return 0; + + return 0; } bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) { LI = &getAnalysis(); LPM = &LPM_Ref; + DF = getAnalysisToUpdate(); + DT = getAnalysisToUpdate(); + bool Changed = false; do { @@ -518,7 +542,7 @@ static Loop *CloneLoop(Loop *L, Loop *PL, DenseMap &VM, for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E; ++I) if (LI->getLoopFor(*I) == L) - New->addBasicBlockToLoop(cast(VM[*I]), *LI); + New->addBasicBlockToLoop(cast(VM[*I]), LI->getBase()); // Add all of the subloops to the new loop. for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) @@ -583,8 +607,8 @@ void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, // insert the new conditional branch. EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, OrigPH->getTerminator()); - OrigPH->getTerminator()->eraseFromParent(); LPM->deleteSimpleAnalysisValue(OrigPH->getTerminator(), L); + OrigPH->getTerminator()->eraseFromParent(); // We need to reprocess this loop, it could be unswitched again. redoLoop = true; @@ -596,38 +620,36 @@ void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, ++NumTrivial; } -/// VersionLoop - We determined that the loop is profitable to unswitch when LIC -/// equal Val. Split it into loop versions and test the condition outside of -/// either loop. Return the loops created as Out1/Out2. -void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, - Loop *L) { - Function *F = L->getHeader()->getParent(); - DOUT << "loop-unswitch: Unswitching loop %" - << L->getHeader()->getName() << " [" << L->getBlocks().size() - << " blocks] in Function " << F->getName() - << " when '" << *Val << "' == " << *LIC << "\n"; - - // LoopBlocks contains all of the basic blocks of the loop, including the - // preheader of the loop, the body of the loop, and the exit blocks of the - // loop, in that order. - std::vector LoopBlocks; +/// ReplaceLoopExternalDFMember - +/// If BB's dominance frontier has a member that is not part of loop L then +/// remove it. Add NewDFMember in BB's dominance frontier. +void LoopUnswitch::ReplaceLoopExternalDFMember(Loop *L, BasicBlock *BB, + BasicBlock *NewDFMember) { + + DominanceFrontier::iterator DFI = DF->find(BB); + if (DFI == DF->end()) + return; + + DominanceFrontier::DomSetType &DFSet = DFI->second; + for (DominanceFrontier::DomSetType::iterator DI = DFSet.begin(), + DE = DFSet.end(); DI != DE;) { + BasicBlock *B = *DI++; + if (L->contains(B)) + continue; - // First step, split the preheader and exit blocks, and add these blocks to - // the LoopBlocks list. - BasicBlock *OrigHeader = L->getHeader(); - BasicBlock *OrigPreheader = L->getLoopPreheader(); - BasicBlock *NewPreheader = SplitEdge(OrigPreheader, L->getHeader(), this); - LoopBlocks.push_back(NewPreheader); + DF->removeFromFrontier(DFI, B); + LoopDF.insert(B); + } - // We want the loop to come after the preheader, but before the exit blocks. - LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); + DF->addToFrontier(DFI, NewDFMember); +} - std::vector ExitBlocks; - L->getUniqueExitBlocks(ExitBlocks); +/// SplitExitEdges - +/// Split all of the edges from inside the loop to their exit blocks. Update +/// the appropriate Phi nodes as we do so. +void LoopUnswitch::SplitExitEdges(Loop *L, const SmallVector &ExitBlocks, + SmallVector &MiddleBlocks) { - // Split all of the edges from inside the loop to their exit blocks. Update - // the appropriate Phi nodes as we do so. - SmallVector MiddleBlocks; for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { BasicBlock *ExitBlock = ExitBlocks[i]; std::vector Preds(pred_begin(ExitBlock), pred_end(ExitBlock)); @@ -644,6 +666,8 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, EndBlock = ExitBlock; } + OrigLoopExitMap[StartBlock] = EndBlock; + std::set InsertedPHIs; PHINode* OldLCSSA = 0; for (BasicBlock::iterator I = EndBlock->begin(); @@ -669,9 +693,60 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, OldLCSSA->replaceAllUsesWith(NewLCSSA); NewLCSSA->addIncoming(OldLCSSA, MiddleBlock); } + + if (DF && DT) { + // StartBlock -- > MiddleBlock -- > EndBlock + // StartBlock is loop exiting block. EndBlock will become merge point + // of two loop exits after loop unswitch. + + // If StartBlock's DF member includes a block that is not loop member + // then replace that DF member with EndBlock. + + // If MiddleBlock's DF member includes a block that is not loop member + // tnen replace that DF member with EndBlock. + + ReplaceLoopExternalDFMember(L, StartBlock, EndBlock); + ReplaceLoopExternalDFMember(L, MiddleBlock, EndBlock); + } } } - + +} + +/// UnswitchNontrivialCondition - We determined that the loop is profitable +/// to unswitch when LIC equal Val. Split it into loop versions and test the +/// condition outside of either loop. Return the loops created as Out1/Out2. +void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, + Loop *L) { + Function *F = L->getHeader()->getParent(); + DOUT << "loop-unswitch: Unswitching loop %" + << L->getHeader()->getName() << " [" << L->getBlocks().size() + << " blocks] in Function " << F->getName() + << " when '" << *Val << "' == " << *LIC << "\n"; + + // LoopBlocks contains all of the basic blocks of the loop, including the + // preheader of the loop, the body of the loop, and the exit blocks of the + // loop, in that order. + std::vector LoopBlocks; + + // First step, split the preheader and exit blocks, and add these blocks to + // the LoopBlocks list. + BasicBlock *OrigHeader = L->getHeader(); + BasicBlock *OrigPreheader = L->getLoopPreheader(); + BasicBlock *NewPreheader = SplitEdge(OrigPreheader, L->getHeader(), this); + LoopBlocks.push_back(NewPreheader); + + // We want the loop to come after the preheader, but before the exit blocks. + LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); + + SmallVector ExitBlocks; + L->getUniqueExitBlocks(ExitBlocks); + + // Split all of the edges from inside the loop to their exit blocks. Update + // the appropriate Phi nodes as we do so. + SmallVector MiddleBlocks; + SplitExitEdges(L, ExitBlocks, MiddleBlocks); + // The exit blocks may have been changed due to edge splitting, recompute. ExitBlocks.clear(); L->getUniqueExitBlocks(ExitBlocks); @@ -679,9 +754,6 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, // Add exit blocks to the loop blocks. LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end()); - DominanceFrontier *DF = getAnalysisToUpdate(); - DominatorTree *DT = getAnalysisToUpdate(); - // Next step, clone all of the basic blocks that make up the loop (including // the loop preheader and exit blocks), keeping track of the mapping between // the instructions and blocks. @@ -721,14 +793,14 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, if (ParentLoop) { // Make sure to add the cloned preheader and exit blocks to the parent loop // as well. - ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI); + ParentLoop->addBasicBlockToLoop(NewBlocks[0], LI->getBase()); } for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { BasicBlock *NewExit = cast(ValueMap[ExitBlocks[i]]); // The new exit block should be in the same loop as the old one. if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i])) - ExitBBLoop->addBasicBlockToLoop(NewExit, *LI); + ExitBBLoop->addBasicBlockToLoop(NewExit, LI->getBase()); assert(NewExit->getTerminator()->getNumSuccessors() == 1 && "Exit block should have been split to have one successor!"); @@ -759,12 +831,15 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, // Emit the new branch that selects between the two versions of this loop. EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR); - OldBR->eraseFromParent(); LPM->deleteSimpleAnalysisValue(OldBR, L); + OldBR->eraseFromParent(); // Update dominator info if (DF && DT) { + SmallVector ExitingBlocks; + L->getExitingBlocks(ExitingBlocks); + // Clone dominator info for all cloned basic block. for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) { BasicBlock *LBB = LoopBlocks[i]; @@ -772,29 +847,57 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, CloneDomInfo(NBB, LBB, NewPreheader, OrigPreheader, OrigHeader, DT, DF, ValueMap); - // Remove any OutSiders from LBB and NBB's dominance frontier. - DominanceFrontier::iterator LBBI = DF->find(LBB); - if (LBBI != DF->end()) { - DominanceFrontier::DomSetType &LBSet = LBBI->second; - for (DominanceFrontier::DomSetType::iterator LI = LBSet.begin(), - LE = LBSet.end(); LI != LE; ++LI) { - BasicBlock *B = *LI; - if (OutSiders.count(B)) - DF->removeFromFrontier(LBBI, B); - } - } + // If LBB's dominance frontier includes DFMember + // such that DFMember is also a member of LoopDF then + // - Remove DFMember from LBB's dominance frontier + // - Copy loop exiting blocks', that are dominated by BB, dominance frontier + // member in BB's dominance frontier - // Remove any OutSiders from LBB and NBB's dominance frontier. + DominanceFrontier::iterator LBBI = DF->find(LBB); DominanceFrontier::iterator NBBI = DF->find(NBB); - if (NBBI != DF->end()) { - DominanceFrontier::DomSetType NBSet = NBBI->second; - for (DominanceFrontier::DomSetType::iterator NI = NBSet.begin(), - NE = NBSet.end(); NI != NE; ++NI) { - BasicBlock *B = *NI; - if (OutSiders.count(B)) + if (LBBI == DF->end()) + continue; + + DominanceFrontier::DomSetType &LBSet = LBBI->second; + for (DominanceFrontier::DomSetType::iterator LI = LBSet.begin(), + LE = LBSet.end(); LI != LE; /* NULL */) { + BasicBlock *B = *LI++; + if (B == LBB && B == L->getHeader()) + continue; + bool removeB = false; + if (!LoopDF.count(B)) + continue; + + // If LBB dominates loop exits then insert loop exit block's DF + // into B's DF. + for(SmallVector::iterator LExitI = ExitingBlocks.begin(), + LExitE = ExitingBlocks.end(); LExitI != LExitE; ++LExitI) { + BasicBlock *E = *LExitI; + + if (!DT->dominates(LBB,E)) + continue; + + DenseMap::iterator DFBI = + OrigLoopExitMap.find(E); + if (DFBI == OrigLoopExitMap.end()) + continue; + + BasicBlock *DFB = DFBI->second; + DF->addToFrontier(LBBI, DFB); + DF->addToFrontier(NBBI, DFB); + removeB = true; + } + + // If B's replacement is inserted in DF then now is the time to remove B. + if (removeB) { + DF->removeFromFrontier(LBBI, B); + if (L->contains(B)) + DF->removeFromFrontier(NBBI, cast(ValueMap[B])); + else DF->removeFromFrontier(NBBI, B); } } + } // MiddleBlocks are dominated by original pre header. SplitEdge updated @@ -859,10 +962,10 @@ static void ReplaceUsesOfWith(Instruction *I, Value *V, for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI) Worklist.push_back(cast(*UI)); - I->replaceAllUsesWith(V); - I->eraseFromParent(); LPM->deleteSimpleAnalysisValue(I, L); RemoveFromWorklist(I, Worklist); + I->replaceAllUsesWith(V); + I->eraseFromParent(); ++NumSimplify; } @@ -889,8 +992,8 @@ void LoopUnswitch::RemoveBlockIfDead(BasicBlock *BB, // Remove the branch from the latch to the header block, this makes // the header dead, which will make the latch dead (because the header // dominates the latch). - Pred->getTerminator()->eraseFromParent(); LPM->deleteSimpleAnalysisValue(Pred->getTerminator(), L); + Pred->getTerminator()->eraseFromParent(); new UnreachableInst(Pred); // The loop is now broken, remove it from LI. @@ -947,8 +1050,8 @@ void LoopUnswitch::RemoveBlockIfDead(BasicBlock *BB, Succs.erase(std::unique(Succs.begin(), Succs.end()), Succs.end()); // Remove the basic block, including all of the instructions contained in it. - BB->eraseFromParent(); LPM->deleteSimpleAnalysisValue(BB, L); + BB->eraseFromParent(); // Remove successor blocks here that are not dead, so that we know we only // have dead blocks in this list. Nondead blocks have a way of becoming dead, // then getting removed before we revisit them, which is badness. @@ -1050,10 +1153,10 @@ void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, Instruction* OldTerm = Old->getTerminator(); new BranchInst(Split, SI->getSuccessor(i), ConstantInt::getTrue(), OldTerm); - + + LPM->deleteSimpleAnalysisValue(Old->getTerminator(), L); Old->getTerminator()->eraseFromParent(); - PHINode *PN; for (BasicBlock::iterator II = SI->getSuccessor(i)->begin(); (PN = dyn_cast(II)); ++II) { @@ -1103,9 +1206,9 @@ void LoopUnswitch::SimplifyCode(std::vector &Worklist, Loop *L) { for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) if (Instruction *Use = dyn_cast(I->getOperand(i))) Worklist.push_back(Use); - I->eraseFromParent(); LPM->deleteSimpleAnalysisValue(I, L); RemoveFromWorklist(I, Worklist); + I->eraseFromParent(); ++NumSimplify; continue; } @@ -1166,8 +1269,8 @@ void LoopUnswitch::SimplifyCode(std::vector &Worklist, Loop *L) { // Move all of the successor contents from Succ to Pred. Pred->getInstList().splice(BI, Succ->getInstList(), Succ->begin(), Succ->end()); - BI->eraseFromParent(); LPM->deleteSimpleAnalysisValue(BI, L); + BI->eraseFromParent(); RemoveFromWorklist(BI, Worklist); // If Succ has any successors with PHI nodes, update them to have @@ -1176,8 +1279,8 @@ void LoopUnswitch::SimplifyCode(std::vector &Worklist, Loop *L) { // Remove Succ from the loop tree. LI->removeBlock(Succ); - Succ->eraseFromParent(); LPM->deleteSimpleAnalysisValue(Succ, L); + Succ->eraseFromParent(); ++NumSimplify; } else if (ConstantInt *CB = dyn_cast(BI->getCondition())){ // Conditional branch. Turn it into an unconditional branch, then @@ -1189,8 +1292,8 @@ void LoopUnswitch::SimplifyCode(std::vector &Worklist, Loop *L) { BasicBlock *LiveSucc = BI->getSuccessor(!CB->getZExtValue()); DeadSucc->removePredecessor(BI->getParent(), true); Worklist.push_back(new BranchInst(LiveSucc, BI)); - BI->eraseFromParent(); LPM->deleteSimpleAnalysisValue(BI, L); + BI->eraseFromParent(); RemoveFromWorklist(BI, Worklist); ++NumSimplify;