#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
#include "llvm/Instructions.h"
#include "llvm/Support/Streams.h"
#include <algorithm>
static RegisterPass<DominatorTree>
E("domtree", "Dominator Tree Construction", true);
-unsigned DominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo,
- unsigned N) {
+// NewBB is split and now it has one successor. Update dominator tree to
+// reflect this change.
+void DominatorTree::splitBlock(BasicBlock *NewBB) {
+ assert(NewBB->getTerminator()->getNumSuccessors() == 1
+ && "NewBB should have a single successor!");
+ BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0);
+
+ std::vector<BasicBlock*> PredBlocks;
+ for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB);
+ PI != PE; ++PI)
+ PredBlocks.push_back(*PI);
+
+ assert(!PredBlocks.empty() && "No predblocks??");
+
+ // The newly inserted basic block will dominate existing basic blocks iff the
+ // PredBlocks dominate all of the non-pred blocks. If all predblocks dominate
+ // the non-pred blocks, then they all must be the same block!
+ //
+ bool NewBBDominatesNewBBSucc = true;
+ {
+ BasicBlock *OnePred = PredBlocks[0];
+ unsigned i = 1, e = PredBlocks.size();
+ for (i = 1; !isReachableFromEntry(OnePred); ++i) {
+ assert(i != e && "Didn't find reachable pred?");
+ OnePred = PredBlocks[i];
+ }
+
+ for (; i != e; ++i)
+ if (PredBlocks[i] != OnePred && isReachableFromEntry(OnePred)) {
+ NewBBDominatesNewBBSucc = false;
+ break;
+ }
+
+ if (NewBBDominatesNewBBSucc)
+ for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc);
+ PI != E; ++PI)
+ if (*PI != NewBB && !dominates(NewBBSucc, *PI)) {
+ NewBBDominatesNewBBSucc = false;
+ break;
+ }
+ }
+
+ // The other scenario where the new block can dominate its successors are when
+ // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc
+ // already.
+ if (!NewBBDominatesNewBBSucc) {
+ NewBBDominatesNewBBSucc = true;
+ for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc);
+ PI != E; ++PI)
+ if (*PI != NewBB && !dominates(NewBBSucc, *PI)) {
+ NewBBDominatesNewBBSucc = false;
+ break;
+ }
+ }
+
+ // Find NewBB's immediate dominator and create new dominator tree node for
+ // NewBB.
+ BasicBlock *NewBBIDom = 0;
+ unsigned i = 0;
+ for (i = 0; i < PredBlocks.size(); ++i)
+ if (isReachableFromEntry(PredBlocks[i])) {
+ NewBBIDom = PredBlocks[i];
+ break;
+ }
+ assert(i != PredBlocks.size() && "No reachable preds?");
+ for (i = i + 1; i < PredBlocks.size(); ++i) {
+ if (isReachableFromEntry(PredBlocks[i]))
+ NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
+ }
+ assert(NewBBIDom && "No immediate dominator found??");
+
+ // Create the new dominator tree node... and set the idom of NewBB.
+ DomTreeNode *NewBBNode = addNewBlock(NewBB, NewBBIDom);
+
+ // If NewBB strictly dominates other blocks, then it is now the immediate
+ // dominator of NewBBSucc. Update the dominator tree as appropriate.
+ if (NewBBDominatesNewBBSucc) {
+ DomTreeNode *NewBBSuccNode = getNode(NewBBSucc);
+ changeImmediateDominator(NewBBSuccNode, NewBBNode);
+ }
+}
+
+unsigned DominatorTree::DFSPass(BasicBlock *V, unsigned N) {
// This is more understandable as a recursive algorithm, but we can't use the
// recursive algorithm due to stack depth issues. Keep it here for
// documentation purposes.
#if 0
+ InfoRec &VInfo = Info[Roots[i]];
VInfo.Semi = ++N;
VInfo.Label = V;
InfoRec &SuccVInfo = Info[*SI];
if (SuccVInfo.Semi == 0) {
SuccVInfo.Parent = V;
- N = DFSPass(*SI, SuccVInfo, N);
+ N = DFSPass(*SI, N);
}
}
#else
void DominatorTree::Compress(BasicBlock *VIn) {
std::vector<BasicBlock *> Work;
- std::set<BasicBlock *> Visited;
- InfoRec &VInInfo = Info[VIn];
- BasicBlock *VInAncestor = VInInfo.Ancestor;
+ SmallPtrSet<BasicBlock *, 32> Visited;
+ BasicBlock *VInAncestor = Info[VIn].Ancestor;
InfoRec &VInVAInfo = Info[VInAncestor];
if (VInVAInfo.Ancestor != 0)
InfoRec &VAInfo = Info[VAncestor];
// Process Ancestor first
- if (Visited.count(VAncestor) == 0 && VAInfo.Ancestor != 0) {
+ if (Visited.insert(VAncestor) &&
+ VAInfo.Ancestor != 0) {
Work.push_back(VAncestor);
- Visited.insert(VAncestor);
continue;
}
Work.pop_back();
- // Update VINfo based on Ancestor info
+ // Update VInfo based on Ancestor info
if (VAInfo.Ancestor == 0)
continue;
BasicBlock *VAncestorLabel = VAInfo.Label;
#endif
}
-void DominatorTree::calculate(Function& F) {
+void DominatorTree::calculate(Function &F) {
BasicBlock* Root = Roots[0];
-
- DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0); // Add a node for the root...
+
+ // Add a node for the root...
+ DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0);
Vertex.push_back(0);
// Step #1: Number blocks in depth-first order and initialize variables used
// in later stages of the algorithm.
- unsigned N = 0;
- for (unsigned i = 0, e = Roots.size(); i != e; ++i)
- N = DFSPass(Roots[i], Info[Roots[i]], 0);
+ unsigned N = DFSPass(Root, 0);
for (unsigned i = N; i >= 2; --i) {
BasicBlock *W = Vertex[i];
// Loop over all of the reachable blocks in the function...
for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
if (BasicBlock *ImmDom = getIDom(I)) { // Reachable block.
- DomTreeNode *&BBNode = DomTreeNodes[I];
- if (!BBNode) { // Haven't calculated this node yet?
- // Get or calculate the node for the immediate dominator
- DomTreeNode *IDomNode = getNodeForBlock(ImmDom);
-
- // Add a new tree node for this BasicBlock, and link it as a child of
- // IDomNode
- BBNode = IDomNode->addChild(new DomTreeNode(I, IDomNode));
- }
+ DomTreeNode *BBNode = DomTreeNodes[I];
+ if (BBNode) continue; // Haven't calculated this node yet?
+
+ // Get or calculate the node for the immediate dominator
+ DomTreeNode *IDomNode = getNodeForBlock(ImmDom);
+
+ // Add a new tree node for this BasicBlock, and link it as a child of
+ // IDomNode
+ DomTreeNode *C = new DomTreeNode(I, IDomNode);
+ DomTreeNodes[I] = IDomNode->addChild(C);
}
// Free temporary memory used to construct idom's
Info.clear();
IDoms.clear();
std::vector<BasicBlock*>().swap(Vertex);
+
+ updateDFSNumbers();
+}
+
+void DominatorTreeBase::updateDFSNumbers() {
+ unsigned DFSNum = 0;
+
+ SmallVector<std::pair<DomTreeNode*, DomTreeNode::iterator>, 32> WorkStack;
+
+ for (unsigned i = 0, e = Roots.size(); i != e; ++i) {
+ DomTreeNode *ThisRoot = getNode(Roots[i]);
+ WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));
+ ThisRoot->DFSNumIn = DFSNum++;
+
+ while (!WorkStack.empty()) {
+ DomTreeNode *Node = WorkStack.back().first;
+ DomTreeNode::iterator ChildIt = WorkStack.back().second;
+
+ // If we visited all of the children of this node, "recurse" back up the
+ // stack setting the DFOutNum.
+ if (ChildIt == Node->end()) {
+ Node->DFSNumOut = DFSNum++;
+ WorkStack.pop_back();
+ } else {
+ // Otherwise, recursively visit this child.
+ DomTreeNode *Child = *ChildIt;
+ ++WorkStack.back().second;
+
+ WorkStack.push_back(std::make_pair(Child, Child->begin()));
+ Child->DFSNumIn = DFSNum++;
+ }
+ }
+ }
+
+ SlowQueries = 0;
+ DFSInfoValid = true;
+}
+
+/// isReachableFromEntry - Return true if A is dominated by the entry
+/// block of the function containing it.
+const bool DominatorTreeBase::isReachableFromEntry(BasicBlock* A) {
+ assert (!isPostDominator()
+ && "This is not implemented for post dominators");
+ return dominates(&A->getParent()->getEntryBlock(), A);
+}
+
+// dominates - Return true if A dominates B. THis performs the
+// special checks necessary if A and B are in the same basic block.
+bool DominatorTreeBase::dominates(Instruction *A, Instruction *B) {
+ BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
+ if (BBA != BBB) return dominates(BBA, BBB);
+
+ // It is not possible to determine dominance between two PHI nodes
+ // based on their ordering.
+ if (isa<PHINode>(A) && isa<PHINode>(B))
+ return false;
+
+ // Loop through the basic block until we find A or B.
+ BasicBlock::iterator I = BBA->begin();
+ for (; &*I != A && &*I != B; ++I) /*empty*/;
+
+ if(!IsPostDominators) {
+ // A dominates B if it is found first in the basic block.
+ return &*I == A;
+ } else {
+ // A post-dominates B if B is found first in the basic block.
+ return &*I == B;
+ }
}
// DominatorTreeBase::reset - Free all of the tree node memory.
//
void DominatorTreeBase::reset() {
- for (DomTreeNodeMapType::iterator I = DomTreeNodes.begin(), E = DomTreeNodes.end(); I != E; ++I)
+ for (DomTreeNodeMapType::iterator I = DomTreeNodes.begin(),
+ E = DomTreeNodes.end(); I != E; ++I)
delete I->second;
DomTreeNodes.clear();
IDoms.clear();
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 B dominates A then B is nearest common dominator.
+ if (dominates(B, A))
+ return B;
+
+ // If A dominates B then A is nearest common dominator.
+ if (dominates(A, B))
+ return A;
+
+ DomTreeNode *NodeA = getNode(A);
+ DomTreeNode *NodeB = getNode(B);
+
+ // Collect NodeA dominators set.
+ SmallPtrSet<DomTreeNode*, 16> NodeADoms;
+ NodeADoms.insert(NodeA);
+ DomTreeNode *IDomA = NodeA->getIDom();
+ while (IDomA) {
+ NodeADoms.insert(IDomA);
+ IDomA = IDomA->getIDom();
+ }
+
+ // 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) {
}
DomTreeNode *DominatorTree::getNodeForBlock(BasicBlock *BB) {
- DomTreeNode *&BBNode = DomTreeNodes[BB];
- if (BBNode) return BBNode;
+ if (DomTreeNode *BBNode = DomTreeNodes[BB])
+ return BBNode;
// Haven't calculated this node yet? Get or calculate the node for the
// immediate dominator.
// Add a new tree node for this BasicBlock, and link it as a child of
// IDomNode
- return BBNode = IDomNode->addChild(new DomTreeNode(BB, IDomNode));
+ DomTreeNode *C = new DomTreeNode(BB, IDomNode);
+ return DomTreeNodes[BB] = IDomNode->addChild(C);
}
-static std::ostream &operator<<(std::ostream &o,
- const DomTreeNode *Node) {
+static std::ostream &operator<<(std::ostream &o, const DomTreeNode *Node) {
if (Node->getBlock())
WriteAsOperand(o, Node->getBlock(), false);
else
o << " <<exit node>>";
+
+ o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}";
+
return o << "\n";
}
PrintDomTree(*I, o, Lev+1);
}
+/// eraseNode - Removes a node from the domiantor tree. Block must not
+/// domiante any other blocks. Removes node from its immediate dominator's
+/// children list. Deletes dominator node associated with basic block BB.
+void DominatorTreeBase::eraseNode(BasicBlock *BB) {
+ DomTreeNode *Node = getNode(BB);
+ assert (Node && "Removing node that isn't in dominator tree.");
+ assert (Node->getChildren().empty() && "Node is not a leaf node.");
+
+ // Remove node from immediate dominator's children list.
+ DomTreeNode *IDom = Node->getIDom();
+ if (IDom) {
+ std::vector<DomTreeNode*>::iterator I =
+ std::find(IDom->Children.begin(), IDom->Children.end(), Node);
+ assert(I != IDom->Children.end() &&
+ "Not in immediate dominator children set!");
+ // I am no longer your child...
+ IDom->Children.erase(I);
+ }
+
+ DomTreeNodes.erase(BB);
+ delete Node;
+}
+
void DominatorTreeBase::print(std::ostream &o, const Module* ) const {
- o << "=============================--------------------------------\n"
- << "Inorder Dominator Tree:\n";
+ o << "=============================--------------------------------\n";
+ o << "Inorder Dominator Tree: ";
+ if (DFSInfoValid)
+ o << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
+ o << "\n";
+
PrintDomTree(getRootNode(), o, 1);
}
void DominatorTreeBase::dump() {
- print (llvm::cerr);
+ print(llvm::cerr);
}
bool DominatorTree::runOnFunction(Function &F) {
static RegisterPass<DominanceFrontier>
G("domfrontier", "Dominance Frontier Construction", true);
+// NewBB is split and now it has one successor. Update dominace frontier to
+// reflect this change.
+void DominanceFrontier::splitBlock(BasicBlock *NewBB) {
+ assert(NewBB->getTerminator()->getNumSuccessors() == 1
+ && "NewBB should have a single successor!");
+ BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0);
+
+ std::vector<BasicBlock*> PredBlocks;
+ for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB);
+ PI != PE; ++PI)
+ PredBlocks.push_back(*PI);
+
+ if (PredBlocks.empty())
+ // If NewBB does not have any predecessors then it is a entry block.
+ // In this case, NewBB and its successor NewBBSucc dominates all
+ // other blocks.
+ return;
+
+ // NewBBSucc inherits original NewBB frontier.
+ DominanceFrontier::iterator NewBBI = find(NewBB);
+ if (NewBBI != end()) {
+ DominanceFrontier::DomSetType NewBBSet = NewBBI->second;
+ DominanceFrontier::DomSetType NewBBSuccSet;
+ NewBBSuccSet.insert(NewBBSet.begin(), NewBBSet.end());
+ addBasicBlock(NewBBSucc, NewBBSuccSet);
+ }
+
+ // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the
+ // DF(PredBlocks[0]) without the stuff that the new block does not dominate
+ // a predecessor of.
+ DominatorTree &DT = getAnalysis<DominatorTree>();
+ if (DT.dominates(NewBB, NewBBSucc)) {
+ DominanceFrontier::iterator DFI = find(PredBlocks[0]);
+ if (DFI != end()) {
+ DominanceFrontier::DomSetType Set = DFI->second;
+ // Filter out stuff in Set that we do not dominate a predecessor of.
+ for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
+ E = Set.end(); SetI != E;) {
+ bool DominatesPred = false;
+ for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI);
+ PI != E; ++PI)
+ if (DT.dominates(NewBB, *PI))
+ DominatesPred = true;
+ if (!DominatesPred)
+ Set.erase(SetI++);
+ else
+ ++SetI;
+ }
+
+ if (NewBBI != end()) {
+ DominanceFrontier::DomSetType NewBBSet = NewBBI->second;
+ NewBBSet.insert(Set.begin(), Set.end());
+ } else
+ addBasicBlock(NewBB, Set);
+ }
+
+ } else {
+ // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate
+ // NewBBSucc, but it does dominate itself (and there is an edge (NewBB ->
+ // NewBBSucc)). NewBBSucc is the single successor of NewBB.
+ DominanceFrontier::DomSetType NewDFSet;
+ NewDFSet.insert(NewBBSucc);
+ addBasicBlock(NewBB, NewDFSet);
+ }
+
+ // Now we must loop over all of the dominance frontiers in the function,
+ // replacing occurrences of NewBBSucc with NewBB in some cases. All
+ // blocks that dominate a block in PredBlocks and contained NewBBSucc in
+ // their dominance frontier must be updated to contain NewBB instead.
+ //
+ for (Function::iterator FI = NewBB->getParent()->begin(),
+ FE = NewBB->getParent()->end(); FI != FE; ++FI) {
+ DominanceFrontier::iterator DFI = find(FI);
+ if (DFI == end()) continue; // unreachable block.
+
+ // Only consider nodes that have NewBBSucc in their dominator frontier.
+ if (!DFI->second.count(NewBBSucc)) continue;
+
+ // Verify whether this block dominates a block in predblocks. If not, do
+ // not update it.
+ bool BlockDominatesAny = false;
+ for (std::vector<BasicBlock*>::const_iterator BI = PredBlocks.begin(),
+ BE = PredBlocks.end(); BI != BE; ++BI) {
+ if (DT.dominates(FI, *BI)) {
+ BlockDominatesAny = true;
+ break;
+ }
+ }
+
+ if (!BlockDominatesAny)
+ continue;
+
+ // If NewBBSucc should not stay in our dominator frontier, remove it.
+ // We remove it unless there is a predecessor of NewBBSucc that we
+ // dominate, but we don't strictly dominate NewBBSucc.
+ bool ShouldRemove = true;
+ if ((BasicBlock*)FI == NewBBSucc || !DT.dominates(FI, NewBBSucc)) {
+ // Okay, we know that PredDom does not strictly dominate NewBBSucc.
+ // Check to see if it dominates any predecessors of NewBBSucc.
+ for (pred_iterator PI = pred_begin(NewBBSucc),
+ E = pred_end(NewBBSucc); PI != E; ++PI)
+ if (DT.dominates(FI, *PI)) {
+ ShouldRemove = false;
+ break;
+ }
+ }
+
+ if (ShouldRemove)
+ removeFromFrontier(DFI, NewBBSucc);
+ addToFrontier(DFI, NewBB);
+ }
+}
+
namespace {
class DFCalculateWorkObject {
public:
DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
DomSetType &parentSet = Frontiers[parentBB];
for (; CDFI != CDFE; ++CDFI) {
- if (!parentNode->properlyDominates(DT[*CDFI]))
+ if (!DT.properlyDominates(parentNode, DT[*CDFI]))
parentSet.insert(*CDFI);
}
workList.pop_back();
void DominanceFrontierBase::dump() {
print (llvm::cerr);
}
-
-
-//===----------------------------------------------------------------------===//
-// ETOccurrence Implementation
-//===----------------------------------------------------------------------===//
-
-void ETOccurrence::Splay() {
- ETOccurrence *father;
- ETOccurrence *grandfather;
- int occdepth;
- int fatherdepth;
-
- while (Parent) {
- occdepth = Depth;
-
- father = Parent;
- fatherdepth = Parent->Depth;
- grandfather = father->Parent;
-
- // If we have no grandparent, a single zig or zag will do.
- if (!grandfather) {
- setDepthAdd(fatherdepth);
- MinOccurrence = father->MinOccurrence;
- Min = father->Min;
-
- // See what we have to rotate
- if (father->Left == this) {
- // Zig
- father->setLeft(Right);
- setRight(father);
- if (father->Left)
- father->Left->setDepthAdd(occdepth);
- } else {
- // Zag
- father->setRight(Left);
- setLeft(father);
- if (father->Right)
- father->Right->setDepthAdd(occdepth);
- }
- father->setDepth(-occdepth);
- Parent = NULL;
-
- father->recomputeMin();
- return;
- }
-
- // If we have a grandfather, we need to do some
- // combination of zig and zag.
- int grandfatherdepth = grandfather->Depth;
-
- setDepthAdd(fatherdepth + grandfatherdepth);
- MinOccurrence = grandfather->MinOccurrence;
- Min = grandfather->Min;
-
- ETOccurrence *greatgrandfather = grandfather->Parent;
-
- if (grandfather->Left == father) {
- if (father->Left == this) {
- // Zig zig
- grandfather->setLeft(father->Right);
- father->setLeft(Right);
- setRight(father);
- father->setRight(grandfather);
-
- father->setDepth(-occdepth);
-
- if (father->Left)
- father->Left->setDepthAdd(occdepth);
-
- grandfather->setDepth(-fatherdepth);
- if (grandfather->Left)
- grandfather->Left->setDepthAdd(fatherdepth);
- } else {
- // Zag zig
- grandfather->setLeft(Right);
- father->setRight(Left);
- setLeft(father);
- setRight(grandfather);
-
- father->setDepth(-occdepth);
- if (father->Right)
- father->Right->setDepthAdd(occdepth);
- grandfather->setDepth(-occdepth - fatherdepth);
- if (grandfather->Left)
- grandfather->Left->setDepthAdd(occdepth + fatherdepth);
- }
- } else {
- if (father->Left == this) {
- // Zig zag
- grandfather->setRight(Left);
- father->setLeft(Right);
- setLeft(grandfather);
- setRight(father);
-
- father->setDepth(-occdepth);
- if (father->Left)
- father->Left->setDepthAdd(occdepth);
- grandfather->setDepth(-occdepth - fatherdepth);
- if (grandfather->Right)
- grandfather->Right->setDepthAdd(occdepth + fatherdepth);
- } else { // Zag Zag
- grandfather->setRight(father->Left);
- father->setRight(Left);
- setLeft(father);
- father->setLeft(grandfather);
-
- father->setDepth(-occdepth);
- if (father->Right)
- father->Right->setDepthAdd(occdepth);
- grandfather->setDepth(-fatherdepth);
- if (grandfather->Right)
- grandfather->Right->setDepthAdd(fatherdepth);
- }
- }
-
- // Might need one more rotate depending on greatgrandfather.
- setParent(greatgrandfather);
- if (greatgrandfather) {
- if (greatgrandfather->Left == grandfather)
- greatgrandfather->Left = this;
- else
- greatgrandfather->Right = this;
-
- }
- grandfather->recomputeMin();
- father->recomputeMin();
- }
-}
-
-//===----------------------------------------------------------------------===//
-// ETNode implementation
-//===----------------------------------------------------------------------===//
-
-void ETNode::Split() {
- ETOccurrence *right, *left;
- ETOccurrence *rightmost = RightmostOcc;
- ETOccurrence *parent;
-
- // Update the occurrence tree first.
- RightmostOcc->Splay();
-
- // Find the leftmost occurrence in the rightmost subtree, then splay
- // around it.
- for (right = rightmost->Right; right->Left; right = right->Left);
-
- right->Splay();
-
- // Start splitting
- right->Left->Parent = NULL;
- parent = ParentOcc;
- parent->Splay();
- ParentOcc = NULL;
-
- left = parent->Left;
- parent->Right->Parent = NULL;
-
- right->setLeft(left);
-
- right->recomputeMin();
-
- rightmost->Splay();
- rightmost->Depth = 0;
- rightmost->Min = 0;
-
- delete parent;
-
- // Now update *our* tree
-
- if (Father->Son == this)
- Father->Son = Right;
-
- if (Father->Son == this)
- Father->Son = NULL;
- else {
- Left->Right = Right;
- Right->Left = Left;
- }
- Left = Right = NULL;
- Father = NULL;
-}
-
-void ETNode::setFather(ETNode *NewFather) {
- ETOccurrence *rightmost;
- ETOccurrence *leftpart;
- ETOccurrence *NewFatherOcc;
- ETOccurrence *temp;
-
- // First update the path in the splay tree
- NewFatherOcc = new ETOccurrence(NewFather);
-
- rightmost = NewFather->RightmostOcc;
- rightmost->Splay();
-
- leftpart = rightmost->Left;
-
- temp = RightmostOcc;
- temp->Splay();
-
- NewFatherOcc->setLeft(leftpart);
- NewFatherOcc->setRight(temp);
-
- temp->Depth++;
- temp->Min++;
- NewFatherOcc->recomputeMin();
-
- rightmost->setLeft(NewFatherOcc);
-
- if (NewFatherOcc->Min + rightmost->Depth < rightmost->Min) {
- rightmost->Min = NewFatherOcc->Min + rightmost->Depth;
- rightmost->MinOccurrence = NewFatherOcc->MinOccurrence;
- }
-
- delete ParentOcc;
- ParentOcc = NewFatherOcc;
-
- // Update *our* tree
- ETNode *left;
- ETNode *right;
-
- Father = NewFather;
- right = Father->Son;
-
- if (right)
- left = right->Left;
- else
- left = right = this;
-
- left->Right = this;
- right->Left = this;
- Left = left;
- Right = right;
-
- Father->Son = this;
-}
-
-bool ETNode::Below(ETNode *other) {
- ETOccurrence *up = other->RightmostOcc;
- ETOccurrence *down = RightmostOcc;
-
- if (this == other)
- return true;
-
- up->Splay();
-
- ETOccurrence *left, *right;
- left = up->Left;
- right = up->Right;
-
- if (!left)
- return false;
-
- left->Parent = NULL;
-
- if (right)
- right->Parent = NULL;
-
- down->Splay();
-
- if (left == down || left->Parent != NULL) {
- if (right)
- right->Parent = up;
- up->setLeft(down);
- } else {
- left->Parent = up;
-
- // If the two occurrences are in different trees, put things
- // back the way they were.
- if (right && right->Parent != NULL)
- up->setRight(down);
- else
- up->setRight(right);
- return false;
- }
-
- if (down->Depth <= 0)
- return false;
-
- return !down->Right || down->Right->Min + down->Depth >= 0;
-}
-
-ETNode *ETNode::NCA(ETNode *other) {
- ETOccurrence *occ1 = RightmostOcc;
- ETOccurrence *occ2 = other->RightmostOcc;
-
- ETOccurrence *left, *right, *ret;
- ETOccurrence *occmin;
- int mindepth;
-
- if (this == other)
- return this;
-
- occ1->Splay();
- left = occ1->Left;
- right = occ1->Right;
-
- if (left)
- left->Parent = NULL;
-
- if (right)
- right->Parent = NULL;
- occ2->Splay();
-
- if (left == occ2 || (left && left->Parent != NULL)) {
- ret = occ2->Right;
-
- occ1->setLeft(occ2);
- if (right)
- right->Parent = occ1;
- } else {
- ret = occ2->Left;
-
- occ1->setRight(occ2);
- if (left)
- left->Parent = occ1;
- }
-
- if (occ2->Depth > 0) {
- occmin = occ1;
- mindepth = occ1->Depth;
- } else {
- occmin = occ2;
- mindepth = occ2->Depth + occ1->Depth;
- }
-
- if (ret && ret->Min + occ1->Depth + occ2->Depth < mindepth)
- return ret->MinOccurrence->OccFor;
- else
- return occmin->OccFor;
-}
-
-void ETNode::assignDFSNumber(int num) {
- std::vector<ETNode *> workStack;
- std::set<ETNode *> visitedNodes;
-
- workStack.push_back(this);
- visitedNodes.insert(this);
- this->DFSNumIn = num++;
-
- while (!workStack.empty()) {
- ETNode *Node = workStack.back();
-
- // If this is leaf node then set DFSNumOut and pop the stack
- if (!Node->Son) {
- Node->DFSNumOut = num++;
- workStack.pop_back();
- continue;
- }
-
- ETNode *son = Node->Son;
-
- // Visit Node->Son first
- if (visitedNodes.count(son) == 0) {
- son->DFSNumIn = num++;
- workStack.push_back(son);
- visitedNodes.insert(son);
- continue;
- }
-
- bool visitChild = false;
- // Visit remaining children
- for (ETNode *s = son->Right; s != son && !visitChild; s = s->Right) {
- if (visitedNodes.count(s) == 0) {
- visitChild = true;
- s->DFSNumIn = num++;
- workStack.push_back(s);
- visitedNodes.insert(s);
- }
- }
-
- if (!visitChild) {
- // If we reach here means all children are visited
- Node->DFSNumOut = num++;
- workStack.pop_back();
- }
- }
-}
-
-//===----------------------------------------------------------------------===//
-// ETForest implementation
-//===----------------------------------------------------------------------===//
-
-char ETForest::ID = 0;
-static RegisterPass<ETForest>
-D("etforest", "ET Forest Construction", true);
-
-void ETForestBase::reset() {
- for (ETMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
- delete I->second;
- Nodes.clear();
-}
-
-void ETForestBase::updateDFSNumbers()
-{
- int dfsnum = 0;
- // Iterate over all nodes in depth first order.
- for (unsigned i = 0, e = Roots.size(); i != e; ++i)
- for (df_iterator<BasicBlock*> I = df_begin(Roots[i]),
- E = df_end(Roots[i]); I != E; ++I) {
- BasicBlock *BB = *I;
- ETNode *ETN = getNode(BB);
- if (ETN && !ETN->hasFather())
- ETN->assignDFSNumber(dfsnum);
- }
- SlowQueries = 0;
- DFSInfoValid = true;
-}
-
-// dominates - Return true if A dominates B. THis performs the
-// special checks necessary if A and B are in the same basic block.
-bool ETForestBase::dominates(Instruction *A, Instruction *B) {
- BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
- if (BBA != BBB) return dominates(BBA, BBB);
-
- // It is not possible to determine dominance between two PHI nodes
- // based on their ordering.
- if (isa<PHINode>(A) && isa<PHINode>(B))
- return false;
-
- // Loop through the basic block until we find A or B.
- BasicBlock::iterator I = BBA->begin();
- for (; &*I != A && &*I != B; ++I) /*empty*/;
-
- if(!IsPostDominators) {
- // A dominates B if it is found first in the basic block.
- return &*I == A;
- } else {
- // A post-dominates B if B is found first in the basic block.
- return &*I == B;
- }
-}
-
-/// isReachableFromEntry - Return true if A is dominated by the entry
-/// block of the function containing it.
-const bool ETForestBase::isReachableFromEntry(BasicBlock* A) {
- return dominates(&A->getParent()->getEntryBlock(), A);
-}
-
-// FIXME : There is no need to make getNodeForBlock public. Fix
-// predicate simplifier.
-ETNode *ETForest::getNodeForBlock(BasicBlock *BB) {
- ETNode *&BBNode = Nodes[BB];
- if (BBNode) return BBNode;
-
- // Haven't calculated this node yet? Get or calculate the node for the
- // immediate dominator.
- DomTreeNode *node= getAnalysis<DominatorTree>().getNode(BB);
-
- // If we are unreachable, we may not have an immediate dominator.
- if (!node || !node->getIDom())
- return BBNode = new ETNode(BB);
- else {
- ETNode *IDomNode = getNodeForBlock(node->getIDom()->getBlock());
-
- // Add a new tree node for this BasicBlock, and link it as a child of
- // IDomNode
- BBNode = new ETNode(BB);
- BBNode->setFather(IDomNode);
- return BBNode;
- }
-}
-
-void ETForest::calculate(const DominatorTree &DT) {
- assert(Roots.size() == 1 && "ETForest should have 1 root block!");
- BasicBlock *Root = Roots[0];
- Nodes[Root] = new ETNode(Root); // Add a node for the root
-
- Function *F = Root->getParent();
- // Loop over all of the reachable blocks in the function...
- for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
- DomTreeNode* node = DT.getNode(I);
- if (node && node->getIDom()) { // Reachable block.
- BasicBlock* ImmDom = node->getIDom()->getBlock();
- ETNode *&BBNode = Nodes[I];
- if (!BBNode) { // Haven't calculated this node yet?
- // Get or calculate the node for the immediate dominator
- ETNode *IDomNode = getNodeForBlock(ImmDom);
-
- // Add a new ETNode for this BasicBlock, and set it's parent
- // to it's immediate dominator.
- BBNode = new ETNode(I);
- BBNode->setFather(IDomNode);
- }
- }
- }
-
- // Make sure we've got nodes around for every block
- for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
- ETNode *&BBNode = Nodes[I];
- if (!BBNode)
- BBNode = new ETNode(I);
- }
-
- updateDFSNumbers ();
-}
-
-//===----------------------------------------------------------------------===//
-// ETForestBase Implementation
-//===----------------------------------------------------------------------===//
-
-void ETForestBase::addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
- ETNode *&BBNode = Nodes[BB];
- assert(!BBNode && "BasicBlock already in ET-Forest");
-
- BBNode = new ETNode(BB);
- BBNode->setFather(getNode(IDom));
- DFSInfoValid = false;
-}
-
-void ETForestBase::setImmediateDominator(BasicBlock *BB, BasicBlock *newIDom) {
- assert(getNode(BB) && "BasicBlock not in ET-Forest");
- assert(getNode(newIDom) && "IDom not in ET-Forest");
-
- ETNode *Node = getNode(BB);
- if (Node->hasFather()) {
- if (Node->getFather()->getData<BasicBlock>() == newIDom)
- return;
- Node->Split();
- }
- Node->setFather(getNode(newIDom));
- DFSInfoValid= false;
-}
-
-void ETForestBase::print(std::ostream &o, const Module *) const {
- o << "=============================--------------------------------\n";
- o << "ET Forest:\n";
- o << "DFS Info ";
- if (DFSInfoValid)
- o << "is";
- else
- o << "is not";
- o << " up to date\n";
-
- Function *F = getRoots()[0]->getParent();
- for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
- o << " DFS Numbers For Basic Block:";
- WriteAsOperand(o, I, false);
- o << " are:";
- if (ETNode *EN = getNode(I)) {
- o << "In: " << EN->getDFSNumIn();
- o << " Out: " << EN->getDFSNumOut() << "\n";
- } else {
- o << "No associated ETNode";
- }
- o << "\n";
- }
- o << "\n";
-}
-
-void ETForestBase::dump() {
- print (llvm::cerr);
-}
projects / oota-llvm.git / blobdiff