bool redoLoop;
public:
static char ID; // Pass ID, replacement for typeid
- LoopUnswitch(bool Os = false) :
+ explicit LoopUnswitch(bool Os = false) :
LoopPass((intptr_t)&ID), OptimizeForSize(Os), redoLoop(false) {}
bool runOnLoop(Loop *L, LPPassManager &LPM);
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;
}
}
-// 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
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.
redoLoop = true;
// 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);
redoLoop = true;
/// 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;
}