Author: dpatel
Date: Fri Aug 17 16:59:16 2007
New Revision: 41144
URL: http://llvm.org/viewvc/llvm-project?rev=41144&view=rev
Log:
When one branch of condition is eliminated then head of the other
branch is not necessary immediate dominators of merge blcok in all cases.
Modified:
llvm/trunk/include/llvm/Analysis/Dominators.h
llvm/trunk/lib/Transforms/Scalar/LoopIndexSplit.cpp
llvm/trunk/lib/Transforms/Utils/LCSSA.cpp
Modified: llvm/trunk/include/llvm/Analysis/Dominators.h
URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/Analysis/Dominators.h?rev=41144&r1=41143&r2=41144&view=diff
==============================================================================
--- llvm/trunk/include/llvm/Analysis/Dominators.h (original)
+++ llvm/trunk/include/llvm/Analysis/Dominators.h Fri Aug 17 16:59:16 2007
@@ -438,6 +438,26 @@
/// frontier to reflect this change.
void splitBlock(BasicBlock *BB);
+ /// BasicBlock BB's new dominator is NewBB. Update BB's dominance frontier
+ /// to reflect this change.
+ void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB,
+ DominatorTree *DT) {
+ // NewBB is now dominating BB. Which means BB's dominance
+ // frontier is now part of NewBB's dominance frontier. However, BB
+ // itself is not member of NewBB's dominance frontier.
+ DominanceFrontier::iterator NewDFI = find(NewBB);
+ DominanceFrontier::iterator DFI = find(BB);
+ DominanceFrontier::DomSetType BBSet = DFI->second;
+ for (DominanceFrontier::DomSetType::iterator BBSetI = BBSet.begin(),
+ BBSetE = BBSet.end(); BBSetI != BBSetE; ++BBSetI) {
+ BasicBlock *DFMember = *BBSetI;
+ // Insert only if NewBB dominates DFMember.
+ if (!DT->dominates(NewBB, DFMember))
+ NewDFI->second.insert(DFMember);
+ }
+ NewDFI->second.erase(BB);
+ }
+
private:
const DomSetType &calculate(const DominatorTree &DT,
const DomTreeNode *Node);
Modified: llvm/trunk/lib/Transforms/Scalar/LoopIndexSplit.cpp
URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Transforms/Scalar/LoopIndexSplit.cpp?rev=41144&r1=41143&r2=41144&view=diff
==============================================================================
--- llvm/trunk/lib/Transforms/Scalar/LoopIndexSplit.cpp (original)
+++ llvm/trunk/lib/Transforms/Scalar/LoopIndexSplit.cpp Fri Aug 17 16:59:16 2007
@@ -603,6 +603,7 @@
BasicBlock *LiveBB) {
// First update DeadBB's dominance frontier.
+ SmallVector<BasicBlock *, 8> FrontierBBs;
DominanceFrontier::iterator DeadBBDF = DF->find(DeadBB);
if (DeadBBDF != DF->end()) {
SmallVector<BasicBlock *, 8> PredBlocks;
@@ -611,7 +612,8 @@
for (DominanceFrontier::DomSetType::iterator DeadBBSetI =
DeadBBSet.begin(),
DeadBBSetE = DeadBBSet.end(); DeadBBSetI != DeadBBSetE;
++DeadBBSetI) {
BasicBlock *FrontierBB = *DeadBBSetI;
-
+ FrontierBBs.push_back(FrontierBB);
+
// Rremove any PHI incoming edge from blocks dominated by DeadBB.
PredBlocks.clear();
for(pred_iterator PI = pred_begin(FrontierBB), PE = pred_end(FrontierBB);
@@ -620,7 +622,8 @@
if (P == DeadBB || DT->dominates(DeadBB, P))
PredBlocks.push_back(P);
}
-
+
+ BasicBlock *NewDominator = NULL;
for(BasicBlock::iterator FBI = FrontierBB->begin(), FBE =
FrontierBB->end();
FBI != FBE; ++FBI) {
if (PHINode *PN = dyn_cast<PHINode>(FBI)) {
@@ -629,27 +632,14 @@
BasicBlock *P = *PI;
PN->removeIncomingValue(P);
}
+ // If we have not identified new dominator then see if we can
identify
+ // one based on remaining incoming PHINode values.
+ if (NewDominator == NULL && PN->getNumIncomingValues() == 1)
+ NewDominator = PN->getIncomingBlock(0);
}
else
break;
- }
-
- DT->changeImmediateDominator(FrontierBB, LiveBB);
-
- // LiveBB is now dominating FrontierBB. Which means FrontierBB's
dominance
- // frontier is member of LiveBB's dominance frontier. However, FrontierBB
- // itself is not member of LiveBB's dominance frontier.
- DominanceFrontier::iterator LiveDF = DF->find(LiveBB);
- DominanceFrontier::iterator FrontierDF = DF->find(FrontierBB);
- DominanceFrontier::DomSetType FrontierBBSet = FrontierDF->second;
- for (DominanceFrontier::DomSetType::iterator FrontierBBSetI =
FrontierBBSet.begin(),
- FrontierBBSetE = FrontierBBSet.end(); FrontierBBSetI !=
FrontierBBSetE; ++FrontierBBSetI) {
- BasicBlock *DFMember = *FrontierBBSetI;
- // Insert only if LiveBB dominates DFMember.
- if (!DT->dominates(LiveBB, DFMember))
- LiveDF->second.insert(DFMember);
- }
- LiveDF->second.erase(FrontierBB);
+ }
}
}
@@ -660,7 +650,7 @@
E = df_end(DN); DI != E; ++DI) {
BasicBlock *BB = DI->getBlock();
WorkList.push_back(BB);
- BB->getTerminator()->eraseFromParent();
+ BB->replaceAllUsesWith(UndefValue::get(Type::LabelTy));
}
while (!WorkList.empty()) {
@@ -677,6 +667,31 @@
LI->removeBlock(BB);
BB->eraseFromParent();
}
+
+ // Update Frontier BBs' dominator info.
+ while (!FrontierBBs.empty()) {
+ BasicBlock *FBB = FrontierBBs.back(); FrontierBBs.pop_back();
+ BasicBlock *NewDominator = FBB->getSinglePredecessor();
+ if (!NewDominator) {
+ pred_iterator PI = pred_begin(FBB), PE = pred_end(FBB);
+ NewDominator = *PI;
+ ++PI;
+ if (NewDominator != LiveBB) {
+ for(; PI != PE; ++PI) {
+ BasicBlock *P = *PI;
+ if (P == LiveBB) {
+ NewDominator = LiveBB;
+ break;
+ }
+ NewDominator = DT->findNearestCommonDominator(NewDominator, P);
+ }
+ }
+ }
+ assert (NewDominator && "Unable to fix dominator info.");
+ DT->changeImmediateDominator(FBB, NewDominator);
+ DF->changeImmediateDominator(FBB, NewDominator, DT);
+ }
+
}
bool LoopIndexSplit::splitLoop(SplitInfo &SD) {
@@ -696,6 +711,12 @@
|| Latch == SplitTerminator->getSuccessor(1)))
return false;
+
+ BasicBlock *Succ0 = SplitTerminator->getSuccessor(0);
+ BasicBlock *Succ1 = SplitTerminator->getSuccessor(1);
+ if (DT->dominates(Succ0, Latch) || DT->dominates(Succ1, Latch))
+ return false;
+
// True loop is original loop. False loop is cloned loop.
bool SignedPredicate = ExitCondition->isSignedPredicate();
Modified: llvm/trunk/lib/Transforms/Utils/LCSSA.cpp
URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Transforms/Utils/LCSSA.cpp?rev=41144&r1=41143&r2=41144&view=diff
==============================================================================
--- llvm/trunk/lib/Transforms/Utils/LCSSA.cpp (original)
+++ llvm/trunk/lib/Transforms/Utils/LCSSA.cpp Fri Aug 17 16:59:16 2007
@@ -107,7 +107,8 @@
LI = &LPM.getAnalysis<LoopInfo>();
DT = &getAnalysis<DominatorTree>();
-
+ DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>();
+
// Speed up queries by creating a sorted list of blocks
LoopBlocks.clear();
LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
