//===- PostDominators.cpp - Post-Dominator Calculation --------------------===//
-//
+//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
+//
//===----------------------------------------------------------------------===//
//
// This file implements the post-dominator construction algorithms.
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/PostDominators.h"
-#include "llvm/iTerminators.h"
+#include "llvm/Instructions.h"
#include "llvm/Support/CFG.h"
-#include "Support/DepthFirstIterator.h"
-#include "Support/SetOperations.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/SetOperations.h"
+using namespace llvm;
//===----------------------------------------------------------------------===//
// PostDominatorSet Implementation
for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
Doms[I]; // Initialize to empty
- if (isa<ReturnInst>(I->getTerminator()) ||
- isa<UnwindInst>(I->getTerminator()))
+ if (succ_begin(I) == succ_end(I))
Roots.push_back(I);
}
//
while (Doms[*SI].size() == 0) ++SI;
WorkingSet = Doms[*SI];
-
+
for (++SI; SI != SE; ++SI) { // Intersect all of the successor sets
DomSetType &SuccSet = Doms[*SI];
if (SuccSet.size())
if (Roots.size() > 1)
WorkingSet.insert(0);
}
-
+
WorkingSet.insert(BB); // A block always dominates itself
DomSetType &BBSet = Doms[BB];
if (BBSet != WorkingSet) {
static RegisterAnalysis<ImmediatePostDominators>
D("postidom", "Immediate Post-Dominators Construction", true);
+
+// calcIDoms - Calculate the immediate dominator mapping, given a set of
+// dominators for every basic block.
+void ImmediatePostDominators::calcIDoms(const DominatorSetBase &DS) {
+ // Loop over all of the nodes that have dominators... figuring out the IDOM
+ // for each node...
+ //
+ for (DominatorSet::const_iterator DI = DS.begin(), DEnd = DS.end();
+ DI != DEnd; ++DI) {
+ BasicBlock *BB = DI->first;
+ const DominatorSet::DomSetType &Dominators = DI->second;
+ unsigned DomSetSize = Dominators.size();
+ if (DomSetSize == 1) continue; // Root node... IDom = null
+
+ // Loop over all dominators of this node. This corresponds to looping over
+ // nodes in the dominator chain, looking for a node whose dominator set is
+ // equal to the current nodes, except that the current node does not exist
+ // in it. This means that it is one level higher in the dom chain than the
+ // current node, and it is our idom!
+ //
+ DominatorSet::DomSetType::const_iterator I = Dominators.begin();
+ DominatorSet::DomSetType::const_iterator End = Dominators.end();
+ for (; I != End; ++I) { // Iterate over dominators...
+ // All of our dominators should form a chain, where the number of elements
+ // in the dominator set indicates what level the node is at in the chain.
+ // We want the node immediately above us, so it will have an identical
+ // dominator set, except that BB will not dominate it... therefore it's
+ // dominator set size will be one less than BB's...
+ //
+ if (DS.getDominators(*I).size() == DomSetSize - 1) {
+ IDoms[BB] = *I;
+ break;
+ }
+ }
+ }
+}
+
//===----------------------------------------------------------------------===//
// PostDominatorTree Implementation
//===----------------------------------------------------------------------===//
// be a predecessor in the depth first order that we are iterating through
// the function.
//
- DominatorSet::DomSetType::const_iterator I = Dominators.begin();
- DominatorSet::DomSetType::const_iterator End = Dominators.end();
- for (; I != End; ++I) { // Iterate over dominators...
+ for (DominatorSet::DomSetType::const_iterator I = Dominators.begin(),
+ E = Dominators.end(); I != E; ++I) { // Iterate over dominators.
// All of our dominators should form a chain, where the number
// of elements in the dominator set indicates what level the
// node is at in the chain. We want the node immediately
// dominator set size will be one less than BB's...
//
if (DS.getDominators(*I).size() == DomSetSize - 1) {
- // We know that the immediate dominator should already have a node,
+ // We know that the immediate dominator should already have a node,
// because we are traversing the CFG in depth first order!
//
Node *IDomNode = Nodes[*I];
assert(IDomNode && "No node for IDOM?");
-
+
// Add a new tree node for this BasicBlock, and link it as a child of
// IDomNode
Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
}
}
}
+//===----------------------------------------------------------------------===//
+// PostETForest Implementation
+//===----------------------------------------------------------------------===//
+
+static RegisterAnalysis<PostETForest>
+G("postetforest", "Post-ET-Forest Construction", true);
+
+ETNode *PostETForest::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.
+ BasicBlock *IDom = getAnalysis<ImmediatePostDominators>()[BB];
+
+ // If we are unreachable, we may not have an immediate dominator.
+ if (!IDom)
+ return BBNode = new ETNode(BB);
+ else {
+ ETNode *IDomNode = getNodeForBlock(IDom);
+
+ // 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 PostETForest::calculate(const ImmediatePostDominators &ID) {
+ for (unsigned i = 0, e = Roots.size(); i != e; ++i)
+ Nodes[Roots[i]] = new ETNode(Roots[i]); // Add a node for the root
+
+ // Iterate over all nodes in inverse depth first order.
+ for (unsigned i = 0, e = Roots.size(); i != e; ++i)
+ for (idf_iterator<BasicBlock*> I = idf_begin(Roots[i]),
+ E = idf_end(Roots[i]); I != E; ++I) {
+ BasicBlock *BB = *I;
+ ETNode *&BBNode = Nodes[BB];
+ if (!BBNode) {
+ ETNode *IDomNode = NULL;
+
+ if (ID.get(BB))
+ IDomNode = getNodeForBlock(ID.get(BB));
+
+ // Add a new ETNode for this BasicBlock, and set it's parent
+ // to it's immediate dominator.
+ BBNode = new ETNode(BB);
+ if (IDomNode)
+ BBNode->setFather(IDomNode);
+ }
+ }
+
+ int dfsnum = 0;
+ // Iterate over all nodes in depth first order...
+ for (unsigned i = 0, e = Roots.size(); i != e; ++i)
+ for (idf_iterator<BasicBlock*> I = idf_begin(Roots[i]),
+ E = idf_end(Roots[i]); I != E; ++I) {
+ if (!getNodeForBlock(*I)->hasFather())
+ getNodeForBlock(*I)->assignDFSNumber(dfsnum);
+ }
+ DFSInfoValid = true;
+}
//===----------------------------------------------------------------------===//
// PostDominanceFrontier Implementation
H("postdomfrontier", "Post-Dominance Frontier Construction", true);
const DominanceFrontier::DomSetType &
-PostDominanceFrontier::calculate(const PostDominatorTree &DT,
+PostDominanceFrontier::calculate(const PostDominatorTree &DT,
const DominatorTree::Node *Node) {
// Loop over CFG successors to calculate DFlocal[Node]
BasicBlock *BB = Node->getBlock();
DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
for (; CDFI != CDFE; ++CDFI) {
- if (!Node->dominates(DT[*CDFI]))
- S.insert(*CDFI);
+ if (!Node->properlyDominates(DT[*CDFI]))
+ S.insert(*CDFI);
}
}
// stub - a dummy function to make linking work ok.
void PostDominanceFrontier::stub() {
}
+
projects / oota-llvm.git / blobdiff