diff options
author | Devang Patel <dpatel@apple.com> | 2007-06-11 23:31:22 +0000 |
---|---|---|
committer | Devang Patel <dpatel@apple.com> | 2007-06-11 23:31:22 +0000 |
commit | fe7d4e50b8a34e660a8713da79613041987c19d6 (patch) | |
tree | 209458250cd746aac738b8eb7cd58eba46fce3d3 /lib | |
parent | 976e2da081519d3438da6bf8e5ae7b25cc3433e4 (diff) | |
download | llvm-fe7d4e50b8a34e660a8713da79613041987c19d6.tar.gz llvm-fe7d4e50b8a34e660a8713da79613041987c19d6.tar.bz2 llvm-fe7d4e50b8a34e660a8713da79613041987c19d6.tar.xz |
Add and use DominatorTreeBase::findNearestCommonDominator().
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37545 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Transforms/Utils/LoopSimplify.cpp | 2 | ||||
-rw-r--r-- | lib/VMCore/Dominators.cpp | 45 |
2 files changed, 46 insertions, 1 deletions
diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp index 98ec288e18..7e1281213b 100644 --- a/lib/Transforms/Utils/LoopSimplify.cpp +++ b/lib/Transforms/Utils/LoopSimplify.cpp @@ -768,7 +768,7 @@ void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, assert(i != PredBlocks.size() && "No reachable preds?"); for (i = i + 1; i < PredBlocks.size(); ++i) { if (DT.isReachableFromEntry(PredBlocks[i])) - NewBBIDom = DT.nearestCommonDominator(NewBBIDom, PredBlocks[i]); + NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]); } assert(NewBBIDom && "No immediate dominator found??"); diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 32c435b2c6..8b2c1a45e2 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -23,6 +23,7 @@ #include "llvm/Instructions.h" #include "llvm/Support/Streams.h" #include <algorithm> +#include <set> using namespace llvm; namespace llvm { @@ -369,6 +370,50 @@ void DominatorTreeBase::reset() { RootNode = 0; } +/// findNearestCommonDominator - Find nearest common dominator basic block +/// for basic block A and B. If there is no such block then return NULL. +BasicBlock *DominatorTreeBase::findNearestCommonDominator(BasicBlock *A, BasicBlock *B) { + + assert (!isPostDominator() && "This is not implemented for post dominators"); + assert (A->getParent() == B->getParent() && "Two blocks are not in same function"); + + // If either A or B is a entry block then it is nearest common dominator. + BasicBlock &Entry = A->getParent()->getEntryBlock(); + if (A == &Entry || B == &Entry) + return &Entry; + + // If A and B are same then A is nearest common dominator. + DomTreeNode *NodeA = getNode(A); + if (A != 0 && A == B) + return A; + + DomTreeNode *NodeB = getNode(B); + + // Collect NodeA dominators set. + std::set<DomTreeNode *> NodeADoms; + NodeADoms.insert(NodeA); + DomTreeNode *IDomA = NodeA->getIDom(); + while(IDomA) { + NodeADoms.insert(IDomA); + IDomA = IDomA->getIDom(); + } + + // If B dominates A then B is nearest common dominator. + if (NodeADoms.count(NodeB) != 0) + return B; + + // Walk NodeB immediate dominators chain and find common dominator node. + DomTreeNode *IDomB = NodeB->getIDom(); + while(IDomB) { + if (NodeADoms.count(IDomB) != 0) + return IDomB->getBlock(); + + IDomB = IDomB->getIDom(); + } + + return NULL; +} + void DomTreeNode::setIDom(DomTreeNode *NewIDom) { assert(IDom && "No immediate dominator?"); if (IDom != NewIDom) { |