X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FLoopUnswitch.cpp;h=955622e0256c2274efb090c3a29dc113b950680a;hb=2a6a6457094e05e5f5ab34f90dbd25c13d61f8b5;hp=5486d5d298fce0dc90657318bfe9f3f68e31a583;hpb=f476e8e7ce7b6aa0bec26aeb9e926148f7f9d02a;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp index 5486d5d298f..955622e0256 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" @@ -55,11 +54,11 @@ STATISTIC(NumSelects , "Number of selects unswitched"); STATISTIC(NumTrivial , "Number of unswitches that are trivial"); STATISTIC(NumSimplify, "Number of simplifications of unswitched code"); -namespace { - cl::opt - Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), - cl::init(10), cl::Hidden); +static cl::opt +Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), + cl::init(10), cl::Hidden); +namespace { class VISIBILITY_HIDDEN LoopUnswitch : public LoopPass { LoopInfo *LI; // Loop information LPPassManager *LPM; @@ -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) : @@ -104,10 +115,15 @@ namespace { 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(const SmallVector &ExitBlocks, + /// 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); @@ -128,9 +144,9 @@ namespace { std::vector &Worklist, Loop *l); void RemoveLoopFromHierarchy(Loop *L); }; - char LoopUnswitch::ID = 0; - RegisterPass X("loop-unswitch", "Unswitch loops"); } +char LoopUnswitch::ID = 0; +static RegisterPass X("loop-unswitch", "Unswitch loops"); LoopPass *llvm::createLoopUnswitchPass(bool Os) { return new LoopUnswitch(Os); @@ -158,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 { @@ -440,11 +459,11 @@ static inline void RemapInstruction(Instruction *I, // OrigPreheader is loop pre-header before this pass started // updating CFG. NewPrehader is loops new pre-header. However, after CFG // manipulation, loop L may not exist. So rely on input parameter NewPreheader. -void CloneDomInfo(BasicBlock *NewBB, BasicBlock *Orig, - BasicBlock *NewPreheader, BasicBlock *OrigPreheader, - BasicBlock *OrigHeader, - DominatorTree *DT, DominanceFrontier *DF, - DenseMap &VM) { +static void CloneDomInfo(BasicBlock *NewBB, BasicBlock *Orig, + BasicBlock *NewPreheader, BasicBlock *OrigPreheader, + BasicBlock *OrigHeader, + DominatorTree *DT, DominanceFrontier *DF, + DenseMap &VM) { // If NewBB alreay has found its place in domiantor tree then no need to do // anything. @@ -523,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) @@ -549,8 +568,7 @@ void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, std::swap(TrueDest, FalseDest); // Insert the new branch. - new BranchInst(TrueDest, FalseDest, BranchVal, InsertPt); - + BranchInst::Create(TrueDest, FalseDest, BranchVal, InsertPt); } @@ -588,6 +606,27 @@ void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, // insert the new conditional branch. EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, OrigPH->getTerminator()); + if (DT) { + DT->changeImmediateDominator(NewExit, OrigPH); + DT->changeImmediateDominator(NewPH, OrigPH); + } + + if (DF) { + // NewExit is now part of NewPH and Loop Header's dominance + // frontier. + DominanceFrontier::iterator DFI = DF->find(NewPH); + if (DFI != DF->end()) + DF->addToFrontier(DFI, NewExit); + DFI = DF->find(L->getHeader()); + DF->addToFrontier(DFI, NewExit); + + // ExitBlock does not have successors then NewExit is part of + // its dominance frontier. + if (succ_begin(ExitBlock) == succ_end(ExitBlock)) { + DFI = DF->find(ExitBlock); + DF->addToFrontier(DFI, NewExit); + } + } LPM->deleteSimpleAnalysisValue(OrigPH->getTerminator(), L); OrigPH->getTerminator()->eraseFromParent(); @@ -601,11 +640,36 @@ void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, ++NumTrivial; } -/// 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(const SmallVector &ExitBlocks, +/// 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; + + DF->removeFromFrontier(DFI, B); + LoopDF.insert(B); + } + + DF->addToFrontier(DFI, NewDFMember); +} + +/// 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) { + for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { BasicBlock *ExitBlock = ExitBlocks[i]; std::vector Preds(pred_begin(ExitBlock), pred_end(ExitBlock)); @@ -622,38 +686,55 @@ void LoopUnswitch::SplitExitEdges(const SmallVector &ExitBlocks EndBlock = ExitBlock; } + OrigLoopExitMap[StartBlock] = EndBlock; + std::set InsertedPHIs; PHINode* OldLCSSA = 0; for (BasicBlock::iterator I = EndBlock->begin(); (OldLCSSA = dyn_cast(I)); ++I) { Value* OldValue = OldLCSSA->getIncomingValueForBlock(MiddleBlock); - PHINode* NewLCSSA = new PHINode(OldLCSSA->getType(), - OldLCSSA->getName() + ".us-lcssa", - MiddleBlock->getTerminator()); + PHINode* NewLCSSA = PHINode::Create(OldLCSSA->getType(), + OldLCSSA->getName() + ".us-lcssa", + MiddleBlock->getTerminator()); NewLCSSA->addIncoming(OldValue, StartBlock); OldLCSSA->setIncomingValue(OldLCSSA->getBasicBlockIndex(MiddleBlock), NewLCSSA); InsertedPHIs.insert(NewLCSSA); } - BasicBlock::iterator InsertPt = EndBlock->begin(); - while (dyn_cast(InsertPt)) ++InsertPt; + BasicBlock::iterator InsertPt = EndBlock->getFirstNonPHI(); for (BasicBlock::iterator I = MiddleBlock->begin(); (OldLCSSA = dyn_cast(I)) && InsertedPHIs.count(OldLCSSA) == 0; ++I) { - PHINode *NewLCSSA = new PHINode(OldLCSSA->getType(), - OldLCSSA->getName() + ".us-lcssa", - InsertPt); + PHINode *NewLCSSA = PHINode::Create(OldLCSSA->getType(), + OldLCSSA->getName() + ".us-lcssa", + InsertPt); 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. +/// 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(); @@ -683,7 +764,7 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, // 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(ExitBlocks, MiddleBlocks); + SplitExitEdges(L, ExitBlocks, MiddleBlocks); // The exit blocks may have been changed due to edge splitting, recompute. ExitBlocks.clear(); @@ -692,9 +773,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. @@ -734,14 +812,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!"); @@ -778,6 +856,9 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, // 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]; @@ -785,29 +866,59 @@ 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; /* NULL */) { - 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; /* NULL */) { - 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 @@ -1061,10 +1172,10 @@ void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, BasicBlock* Split = SplitBlock(Old, SI, this); Instruction* OldTerm = Old->getTerminator(); - new BranchInst(Split, SI->getSuccessor(i), - ConstantInt::getTrue(), OldTerm); + BranchInst::Create(Split, SI->getSuccessor(i), + ConstantInt::getTrue(), OldTerm); - LPM->deleteSimpleAnalysisValue(Old->getTerminator(), L); + LPM->deleteSimpleAnalysisValue(Old->getTerminator(), L); Old->getTerminator()->eraseFromParent(); PHINode *PN; @@ -1201,7 +1312,7 @@ void LoopUnswitch::SimplifyCode(std::vector &Worklist, Loop *L) { BasicBlock *DeadSucc = BI->getSuccessor(CB->getZExtValue()); BasicBlock *LiveSucc = BI->getSuccessor(!CB->getZExtValue()); DeadSucc->removePredecessor(BI->getParent(), true); - Worklist.push_back(new BranchInst(LiveSucc, BI)); + Worklist.push_back(BranchInst::Create(LiveSucc, BI)); LPM->deleteSimpleAnalysisValue(BI, L); BI->eraseFromParent(); RemoveFromWorklist(BI, Worklist);