SmallPtrSet<Value *,8> UnswitchedVals;
bool OptimizeForSize;
+ bool redoLoop;
public:
static char ID; // Pass ID, replacement for typeid
- LoopUnswitch(bool Os = false) :
- LoopPass((intptr_t)&ID), OptimizeForSize(Os) {}
+ explicit LoopUnswitch(bool Os = false) :
+ LoopPass((intptr_t)&ID), OptimizeForSize(Os), redoLoop(false) {}
bool runOnLoop(Loop *L, LPPassManager &LPM);
+ bool processLoop(Loop *L);
/// This transformation requires natural loop information & requires that
/// loop preheaders be inserted into the CFG...
AU.addRequired<LoopInfo>();
AU.addPreserved<LoopInfo>();
AU.addRequiredID(LCSSAID);
+ AU.addPreservedID(LCSSAID);
+ AU.addPreserved<DominatorTree>();
+ AU.addPreserved<DominanceFrontier>();
}
private:
+
/// RemoveLoopFromWorklist - If the specified loop is on the loop worklist,
/// remove it.
void RemoveLoopFromWorklist(Loop *L) {
BasicBlock *FalseDest,
Instruction *InsertPt);
- void SimplifyCode(std::vector<Instruction*> &Worklist);
+ void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L);
void RemoveBlockIfDead(BasicBlock *BB,
- std::vector<Instruction*> &Worklist);
+ std::vector<Instruction*> &Worklist, Loop *l);
void RemoveLoopFromHierarchy(Loop *L);
};
char LoopUnswitch::ID = 0;
}
bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
- assert(L->isLCSSAForm());
LI = &getAnalysis<LoopInfo>();
LPM = &LPM_Ref;
bool Changed = false;
-
+
+ do {
+ redoLoop = false;
+ Changed |= processLoop(L);
+ } while(redoLoop);
+
+ return Changed;
+}
+
+/// processLoop - Do actual work and unswitch loop if possible and profitable.
+bool LoopUnswitch::processLoop(Loop *L) {
+ assert(L->isLCSSAForm());
+ bool Changed = false;
+
// Loop over all of the basic blocks in the loop. If we find an interior
// block that is branching on a loop-invariant condition, we can unswitch this
// loop.
}
}
-// CloneDomInfo - NewBB is cloned from Orig basic block. Now clone Dominator Info.
+// CloneDomInfo - NewBB is cloned from Orig basic block. Now clone Dominator
+// Info.
//
// If Orig block's immediate dominator is mapped in VM then use corresponding
// immediate dominator from the map. Otherwise Orig block's dominator is also
// NewBB's dominator.
//
-// OrigPreheader is loop pre-header before this patch started
+// 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 in input parameter NewPreheader.
+// manipulation, loop L may not exist. So rely on input parameter NewPreheader.
void CloneDomInfo(BasicBlock *NewBB, BasicBlock *Orig,
BasicBlock *NewPreheader, BasicBlock *OrigPreheader,
BasicBlock *OrigHeader,
else
OrigIDom = OrigIDomNode->getBlock();
- // Initially use Orig's immediate dominator as NewBB's immediate dominator.
- BasicBlock *NewIDom = OrigIDom;
- DenseMap<const Value*, Value*>::iterator I = VM.find(OrigIDom);
- if (I != VM.end()) {
- // if (!DT->getNode(OrigIDom))
- // CloneDomInfo(NewIDom, OrigIDom, NewPreheader, OrigPreheader,
- // OrigHeader, DT, DF, VM);
-
- NewIDom = cast<BasicBlock>(I->second);
-
- // If NewIDom does not have corresponding dominatore tree node then
- // get one.
- if (!DT->getNode(NewIDom))
+ // Initially use Orig's immediate dominator as NewBB's immediate dominator.
+ BasicBlock *NewIDom = OrigIDom;
+ DenseMap<const Value*, Value*>::iterator I = VM.find(OrigIDom);
+ if (I != VM.end()) {
+ NewIDom = cast<BasicBlock>(I->second);
+
+ // If NewIDom does not have corresponding dominatore tree node then
+ // get one.
+ if (!DT->getNode(NewIDom))
CloneDomInfo(NewIDom, OrigIDom, NewPreheader, OrigPreheader,
OrigHeader, DT, DF, VM);
}
- // if (NewBB == NewIDom) {
- // DT->addNewBlock(NewBB, OrigIDom);
- // DT->changeImmediateDominator(NewBB, NewIDom);
- //} else
- DT->addNewBlock(NewBB, NewIDom);
-
+
+ DT->addNewBlock(NewBB, NewIDom);
+
+ // Copy cloned dominance frontiner set
DominanceFrontier::DomSetType NewDFSet;
if (DF) {
DominanceFrontier::iterator DFI = DF->find(Orig);
for (DominanceFrontier::DomSetType::iterator I = S.begin(), E = S.end();
I != E; ++I) {
BasicBlock *BB = *I;
- DenseMap<const Value*, Value*>::iterator I = VM.find(BB);
- if (I != VM.end())
- NewDFSet.insert(cast<BasicBlock>(I->second));
+ DenseMap<const Value*, Value*>::iterator IDM = VM.find(BB);
+ if (IDM != VM.end())
+ NewDFSet.insert(cast<BasicBlock>(IDM->second));
else
NewDFSet.insert(BB);
}
std::swap(TrueDest, FalseDest);
// Insert the new branch.
- BranchInst *BRI = new BranchInst(TrueDest, FalseDest, BranchVal, InsertPt);
-
- // Update dominator info.
- // BranchVal is a new preheader so it dominates true and false destination
- // loop headers.
- if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) {
- DT->changeImmediateDominator(TrueDest, BRI->getParent());
- DT->changeImmediateDominator(FalseDest, BRI->getParent());
- }
- // No need to update DominanceFrontier. BRI->getParent() dominated TrueDest
- // and FalseDest anyway. Now it immediately dominates them.
+ new BranchInst(TrueDest, FalseDest, BranchVal, InsertPt);
+
}
EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH,
OrigPH->getTerminator());
OrigPH->getTerminator()->eraseFromParent();
+ LPM->deleteSimpleAnalysisValue(OrigPH->getTerminator(), L);
// We need to reprocess this loop, it could be unswitched again.
- LPM->redoLoop(L);
+ redoLoop = true;
// Now that we know that the loop is never entered when this condition is a
// particular value, rewrite the loop with this info. We know that this will
// 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;
for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
BasicBlock *ExitBlock = ExitBlocks[i];
std::vector<BasicBlock*> Preds(pred_begin(ExitBlock), pred_end(ExitBlock));
for (unsigned j = 0, e = Preds.size(); j != e; ++j) {
BasicBlock* MiddleBlock = SplitEdge(Preds[j], ExitBlock, this);
+ MiddleBlocks.push_back(MiddleBlock);
BasicBlock* StartBlock = Preds[j];
BasicBlock* EndBlock;
if (MiddleBlock->getSinglePredecessor() == ExitBlock) {
// 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.
BasicBlock *New = CloneBasicBlock(LoopBlocks[i], ValueMap, ".us", F);
NewBlocks.push_back(New);
ValueMap[LoopBlocks[i]] = New; // Keep the BB mapping.
+ LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], New, L);
}
- // Update dominator info
- DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>();
- if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>())
- for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) {
- BasicBlock *LBB = LoopBlocks[i];
- BasicBlock *NBB = NewBlocks[i];
- CloneDomInfo(NBB, LBB, NewPreheader, OrigPreheader,
- OrigHeader, DT, DF, ValueMap);
+ // OutSiders are basic block that are dominated by original header and
+ // at the same time they are not part of loop.
+ SmallPtrSet<BasicBlock *, 8> OutSiders;
+ if (DT) {
+ DomTreeNode *OrigHeaderNode = DT->getNode(OrigHeader);
+ for(std::vector<DomTreeNode*>::iterator DI = OrigHeaderNode->begin(),
+ DE = OrigHeaderNode->end(); DI != DE; ++DI) {
+ BasicBlock *B = (*DI)->getBlock();
+
+ DenseMap<const Value*, Value*>::iterator VI = ValueMap.find(B);
+ if (VI == ValueMap.end())
+ OutSiders.insert(B);
}
-
+ }
+
// Splice the newly inserted blocks into the function right before the
// original preheader.
F->getBasicBlockList().splice(LoopBlocks[0], F->getBasicBlockList(),
// 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);
+
+ // Update dominator info
+ if (DF && DT) {
+
+ // Clone dominator info for all cloned basic block.
+ for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) {
+ BasicBlock *LBB = LoopBlocks[i];
+ BasicBlock *NBB = NewBlocks[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);
+ }
+ }
+
+ // Remove any OutSiders from LBB and NBB's dominance frontier.
+ 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))
+ DF->removeFromFrontier(NBBI, B);
+ }
+ }
+ }
+
+ // MiddleBlocks are dominated by original pre header. SplitEdge updated
+ // MiddleBlocks' dominance frontier appropriately.
+ for (unsigned i = 0, e = MiddleBlocks.size(); i != e; ++i) {
+ BasicBlock *MBB = MiddleBlocks[i];
+ if (!MBB->getSinglePredecessor())
+ DT->changeImmediateDominator(MBB, OrigPreheader);
+ }
+
+ // All Outsiders are now dominated by original pre header.
+ for (SmallPtrSet<BasicBlock *, 8>::iterator OI = OutSiders.begin(),
+ OE = OutSiders.end(); OI != OE; ++OI) {
+ BasicBlock *OB = *OI;
+ DT->changeImmediateDominator(OB, OrigPreheader);
+ }
+
+ // New loop headers are dominated by original preheader
+ DT->changeImmediateDominator(NewBlocks[0], OrigPreheader);
+ DT->changeImmediateDominator(LoopBlocks[0], OrigPreheader);
+ }
+
LoopProcessWorklist.push_back(NewLoop);
- LPM->redoLoop(L);
+ redoLoop = true;
// Now we rewrite the original code to know that the condition is true and the
// new code to know that the condition is false.
/// ReplaceUsesOfWith - When we find that I really equals V, remove I from the
/// program, replacing all uses with V and update the worklist.
static void ReplaceUsesOfWith(Instruction *I, Value *V,
- std::vector<Instruction*> &Worklist) {
+ std::vector<Instruction*> &Worklist,
+ Loop *L, LPPassManager *LPM) {
DOUT << "Replace with '" << *V << "': " << *I;
// Add uses to the worklist, which may be dead now.
Worklist.push_back(cast<Instruction>(*UI));
I->replaceAllUsesWith(V);
I->eraseFromParent();
+ LPM->deleteSimpleAnalysisValue(I, L);
RemoveFromWorklist(I, Worklist);
++NumSimplify;
}
/// information, and remove any dead successors it has.
///
void LoopUnswitch::RemoveBlockIfDead(BasicBlock *BB,
- std::vector<Instruction*> &Worklist) {
+ std::vector<Instruction*> &Worklist,
+ Loop *L) {
if (pred_begin(BB) != pred_end(BB)) {
// This block isn't dead, since an edge to BB was just removed, see if there
// are any easy simplifications we can do now.
while (isa<PHINode>(BB->begin()))
ReplaceUsesOfWith(BB->begin(),
cast<PHINode>(BB->begin())->getIncomingValue(0),
- Worklist);
+ Worklist, L, LPM);
// If this is the header of a loop and the only pred is the latch, we now
// have an unreachable loop.
// the header dead, which will make the latch dead (because the header
// dominates the latch).
Pred->getTerminator()->eraseFromParent();
+ LPM->deleteSimpleAnalysisValue(Pred->getTerminator(), L);
new UnreachableInst(Pred);
// The loop is now broken, remove it from LI.
RemoveLoopFromHierarchy(L);
// Reprocess the header, which now IS dead.
- RemoveBlockIfDead(BB, Worklist);
+ RemoveBlockIfDead(BB, Worklist, L);
return;
}
// Remove the basic block, including all of the instructions contained in it.
BB->eraseFromParent();
-
+ LPM->deleteSimpleAnalysisValue(BB, L);
// 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.
}
for (unsigned i = 0, e = Succs.size(); i != e; ++i)
- RemoveBlockIfDead(Succs[i], Worklist);
+ RemoveBlockIfDead(Succs[i], Worklist, L);
}
/// RemoveLoopFromHierarchy - We have discovered that the specified loop has
}
}
- SimplifyCode(Worklist);
+ SimplifyCode(Worklist, L);
}
/// SimplifyCode - Okay, now that we have simplified some instructions in the
/// FIXME: When the loop optimizer is more mature, separate this out to a new
/// pass.
///
-void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist) {
+void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) {
while (!Worklist.empty()) {
Instruction *I = Worklist.back();
Worklist.pop_back();
// Simple constant folding.
if (Constant *C = ConstantFoldInstruction(I)) {
- ReplaceUsesOfWith(I, C, Worklist);
+ ReplaceUsesOfWith(I, C, Worklist, L, LPM);
continue;
}
if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
Worklist.push_back(Use);
I->eraseFromParent();
+ LPM->deleteSimpleAnalysisValue(I, L);
RemoveFromWorklist(I, Worklist);
++NumSimplify;
continue;
switch (I->getOpcode()) {
case Instruction::Select:
if (ConstantInt *CB = dyn_cast<ConstantInt>(I->getOperand(0))) {
- ReplaceUsesOfWith(I, I->getOperand(!CB->getZExtValue()+1), Worklist);
+ ReplaceUsesOfWith(I, I->getOperand(!CB->getZExtValue()+1), Worklist, L,
+ LPM);
continue;
}
break;
if (ConstantInt *CB = dyn_cast<ConstantInt>(I->getOperand(1)))
if (CB->getType() == Type::Int1Ty) {
if (CB->isOne()) // X & 1 -> X
- ReplaceUsesOfWith(I, I->getOperand(0), Worklist);
+ ReplaceUsesOfWith(I, I->getOperand(0), Worklist, L, LPM);
else // X & 0 -> 0
- ReplaceUsesOfWith(I, I->getOperand(1), Worklist);
+ ReplaceUsesOfWith(I, I->getOperand(1), Worklist, L, LPM);
continue;
}
break;
if (ConstantInt *CB = dyn_cast<ConstantInt>(I->getOperand(1)))
if (CB->getType() == Type::Int1Ty) {
if (CB->isOne()) // X | 1 -> 1
- ReplaceUsesOfWith(I, I->getOperand(1), Worklist);
+ ReplaceUsesOfWith(I, I->getOperand(1), Worklist, L, LPM);
else // X | 0 -> X
- ReplaceUsesOfWith(I, I->getOperand(0), Worklist);
+ ReplaceUsesOfWith(I, I->getOperand(0), Worklist, L, LPM);
continue;
}
break;
// Resolve any single entry PHI nodes in Succ.
while (PHINode *PN = dyn_cast<PHINode>(Succ->begin()))
- ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist);
+ ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist, L, LPM);
// 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);
RemoveFromWorklist(BI, Worklist);
// If Succ has any successors with PHI nodes, update them to have
// Remove Succ from the loop tree.
LI->removeBlock(Succ);
Succ->eraseFromParent();
+ LPM->deleteSimpleAnalysisValue(Succ, L);
++NumSimplify;
} else if (ConstantInt *CB = dyn_cast<ConstantInt>(BI->getCondition())){
// Conditional branch. Turn it into an unconditional branch, then
DeadSucc->removePredecessor(BI->getParent(), true);
Worklist.push_back(new BranchInst(LiveSucc, BI));
BI->eraseFromParent();
+ LPM->deleteSimpleAnalysisValue(BI, L);
RemoveFromWorklist(BI, Worklist);
++NumSimplify;
- RemoveBlockIfDead(DeadSucc, Worklist);
+ RemoveBlockIfDead(DeadSucc, Worklist, L);
}
break;
}