//
// 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.
//
//===----------------------------------------------------------------------===//
//
#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"
STATISTIC(NumTrivial , "Number of unswitches that are trivial");
STATISTIC(NumSimplify, "Number of simplifications of unswitched code");
-namespace {
- cl::opt<unsigned>
- Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"),
- cl::init(10), cl::Hidden);
+static cl::opt<unsigned>
+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;
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<BasicBlock *, 8> LoopDF;
+
+ /// OrigLoopExitMap - This is used to map loop exiting block with
+ /// corresponding loop exit block, before updating CFG.
+ DenseMap<BasicBlock *, BasicBlock *> OrigLoopExitMap;
public:
static char ID; // Pass ID, replacement for typeid
explicit LoopUnswitch(bool Os = false) :
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<BasicBlock *, 8> &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<BasicBlock *, 8> &ExitBlocks,
SmallVector<BasicBlock *, 8> &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);
std::vector<Instruction*> &Worklist, Loop *l);
void RemoveLoopFromHierarchy(Loop *L);
};
- char LoopUnswitch::ID = 0;
- RegisterPass<LoopUnswitch> X("loop-unswitch", "Unswitch loops");
}
+char LoopUnswitch::ID = 0;
+static RegisterPass<LoopUnswitch> X("loop-unswitch", "Unswitch loops");
LoopPass *llvm::createLoopUnswitchPass(bool Os) {
return new LoopUnswitch(Os);
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<LoopInfo>();
LPM = &LPM_Ref;
+ DF = getAnalysisToUpdate<DominanceFrontier>();
+ DT = getAnalysisToUpdate<DominatorTree>();
+
bool Changed = false;
do {
// 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<const Value*, Value*> &VM) {
+static void CloneDomInfo(BasicBlock *NewBB, BasicBlock *Orig,
+ BasicBlock *NewPreheader, BasicBlock *OrigPreheader,
+ BasicBlock *OrigHeader,
+ DominatorTree *DT, DominanceFrontier *DF,
+ DenseMap<const Value*, Value*> &VM) {
// If NewBB alreay has found its place in domiantor tree then no need to do
// anything.
for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
I != E; ++I)
if (LI->getLoopFor(*I) == L)
- New->addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), *LI);
+ New->addBasicBlockToLoop(cast<BasicBlock>(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)
std::swap(TrueDest, FalseDest);
// Insert the new branch.
- new BranchInst(TrueDest, FalseDest, BranchVal, InsertPt);
-
+ BranchInst::Create(TrueDest, FalseDest, BranchVal, InsertPt);
}
// 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();
++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<BasicBlock *, 8> &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<BasicBlock *, 8> &ExitBlocks,
SmallVector<BasicBlock *, 8> &MiddleBlocks) {
+
for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
BasicBlock *ExitBlock = ExitBlocks[i];
std::vector<BasicBlock*> Preds(pred_begin(ExitBlock), pred_end(ExitBlock));
EndBlock = ExitBlock;
}
+ OrigLoopExitMap[StartBlock] = EndBlock;
+
std::set<PHINode*> InsertedPHIs;
PHINode* OldLCSSA = 0;
for (BasicBlock::iterator I = EndBlock->begin();
(OldLCSSA = dyn_cast<PHINode>(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<PHINode>(InsertPt)) ++InsertPt;
+ BasicBlock::iterator InsertPt = EndBlock->getFirstNonPHI();
for (BasicBlock::iterator I = MiddleBlock->begin();
(OldLCSSA = dyn_cast<PHINode>(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();
// Split all of the edges from inside the loop to their exit blocks. Update
// the appropriate Phi nodes as we do so.
SmallVector<BasicBlock *,8> MiddleBlocks;
- SplitExitEdges(ExitBlocks, MiddleBlocks);
+ SplitExitEdges(L, ExitBlocks, MiddleBlocks);
// The exit blocks may have been changed due to edge splitting, recompute.
ExitBlocks.clear();
// Add exit blocks to the loop blocks.
LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end());
- DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>();
- DominatorTree *DT = getAnalysisToUpdate<DominatorTree>();
-
// 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.
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<BasicBlock>(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!");
// Update dominator info
if (DF && DT) {
+ SmallVector<BasicBlock *,4> 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];
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<BasicBlock *, 4>::iterator
+ LExitI = ExitingBlocks.begin(),
+ LExitE = ExitingBlocks.end(); LExitI != LExitE; ++LExitI) {
+ BasicBlock *E = *LExitI;
+
+ if (!DT->dominates(LBB,E))
+ continue;
+
+ DenseMap<BasicBlock *, BasicBlock *>::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<BasicBlock>(ValueMap[B]));
+ else
DF->removeFromFrontier(NBBI, B);
}
}
+
}
// MiddleBlocks are dominated by original pre header. SplitEdge updated
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;
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);
projects / oota-llvm.git / blobdiff