//===- llvm/Analysis/Dominators.h - Dominator Info Calculation --*- C++ -*-===//
-//
+//
// 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 defines the following classes:
// 2. DominatorSet: Calculates the [reverse] dominator set for a function
// 3. DominatorTree: Represent the ImmediateDominator as an explicit tree
// structure.
-// 4. DominanceFrontier: Calculate and hold the dominance frontier for a
+// 4. ETForest: Efficient data structure for dominance comparisons and
+// nearest-common-ancestor queries.
+// 5. DominanceFrontier: Calculate and hold the dominance frontier for a
// function.
//
// These data structures are listed in increasing order of complexity. It
-// takes longer to calculate the dominator frontier, for example, than the
+// takes longer to calculate the dominator frontier, for example, than the
// ImmediateDominator mapping.
-//
+//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_DOMINATORS_H
#define LLVM_ANALYSIS_DOMINATORS_H
+#include "llvm/Analysis/ET-Forest.h"
#include "llvm/Pass.h"
#include <set>
///
class ImmediateDominatorsBase : public DominatorBase {
protected:
+ struct InfoRec {
+ unsigned Semi;
+ unsigned Size;
+ BasicBlock *Label, *Parent, *Child, *Ancestor;
+
+ std::vector<BasicBlock*> Bucket;
+
+ InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){}
+ };
+
std::map<BasicBlock*, BasicBlock*> IDoms;
+
+ // Vertex - Map the DFS number to the BasicBlock*
+ std::vector<BasicBlock*> Vertex;
+
+ // Info - Collection of information used during the computation of idoms.
+ std::map<BasicBlock*, InfoRec> Info;
public:
ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {}
inline BasicBlock *operator[](BasicBlock *BB) const {
return get(BB);
}
+
+ /// dominates - Return true if A dominates B.
+ ///
+ bool dominates(BasicBlock *A, BasicBlock *B) const;
+ /// properlyDominates - Return true if A dominates B and A != B.
+ ///
+ bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
+ return A != B || properlyDominates(A, B);
+ }
+
/// get() - Synonym for operator[].
///
inline BasicBlock *get(BasicBlock *BB) const {
/// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase
/// that is used to compute a normal immediate dominator set.
///
-struct ImmediateDominators : public ImmediateDominatorsBase {
+class ImmediateDominators : public ImmediateDominatorsBase {
+public:
ImmediateDominators() : ImmediateDominatorsBase(false) {}
BasicBlock *getRoot() const {
}
private:
- struct InfoRec {
- unsigned Semi;
- unsigned Size;
- BasicBlock *Label, *Parent, *Child, *Ancestor;
-
- std::vector<BasicBlock*> Bucket;
-
- InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){}
- };
-
- // Vertex - Map the DFS number to the BasicBlock*
- std::vector<BasicBlock*> Vertex;
-
- // Info - Collection of information used during the computation of idoms.
- std::map<BasicBlock*, InfoRec> Info;
-
unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
void Compress(BasicBlock *V, InfoRec &VInfo);
BasicBlock *Eval(BasicBlock *v);
/// is unreachable in this function, the set will be empty. This cannot happen
/// for reachable code, because every block dominates at least itself.
///
-struct DominatorSetBase : public DominatorBase {
+class DominatorSetBase : public DominatorBase {
+public:
typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
// Map of dom sets
typedef std::map<BasicBlock*, DomSetType> DomSetMapType;
/// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
/// compute a normal dominator set.
///
-struct DominatorSet : public DominatorSetBase {
+class DominatorSet : public DominatorSetBase {
+public:
DominatorSet() : DominatorSetBase(false) {}
virtual bool runOnFunction(Function &F);
}
// stub - dummy function, just ignore it
- static void stub();
+ static int stub;
};
//===----------------------------------------------------------------------===//
/// DominatorTree - Calculate the immediate dominator tree for a function.
///
-struct DominatorTreeBase : public DominatorBase {
+class DominatorTreeBase : public DominatorBase {
+public:
class Node;
protected:
std::map<BasicBlock*, Node*> Nodes;
Node *RootNode;
public:
class Node {
- friend struct DominatorTree;
+ friend class DominatorTree;
friend struct PostDominatorTree;
- friend struct DominatorTreeBase;
+ friend class DominatorTreeBase;
BasicBlock *TheBB;
Node *IDom;
std::vector<Node*> Children;
inline Node *getIDom() const { return IDom; }
inline const std::vector<Node*> &getChildren() const { return Children; }
- /// dominates - Returns true iff this dominates N. Note that this is not a
- /// constant time operation!
+ /// properlyDominates - Returns true iff this dominates N and this != N.
+ /// Note that this is not a constant time operation!
///
- inline bool dominates(const Node *N) const {
+ bool properlyDominates(const Node *N) const {
const Node *IDom;
+ if (this == 0 || N == 0) return false;
while ((IDom = N->getIDom()) != 0 && IDom != this)
- N = IDom; // Walk up the tree
+ N = IDom; // Walk up the tree
return IDom != 0;
}
+ /// dominates - Returns true iff this dominates N. Note that this is not a
+ /// constant time operation!
+ ///
+ inline bool dominates(const Node *N) const {
+ if (N == this) return true; // A node trivially dominates itself.
+ return properlyDominates(N);
+ }
+
private:
inline Node(BasicBlock *BB, Node *iDom) : TheBB(BB), IDom(iDom) {}
inline Node *addChild(Node *C) { Children.push_back(C); return C; }
N->setIDom(NewIDom);
}
+ /// removeNode - Removes a node from the dominator tree. Block must not
+ /// dominate any other blocks. Invalidates any node pointing to removed
+ /// block.
+ void removeNode(BasicBlock *BB) {
+ assert(getNode(BB) && "Removing node that isn't in dominator tree.");
+ Nodes.erase(BB);
+ }
+
/// print - Convert to human readable form
///
virtual void print(std::ostream &OS, const Module* = 0) const;
};
-
//===-------------------------------------
/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
/// compute a normal dominator tree.
///
-struct DominatorTree : public DominatorTreeBase {
+class DominatorTree : public DominatorTreeBase {
+public:
DominatorTree() : DominatorTreeBase(false) {}
-
+
BasicBlock *getRoot() const {
assert(Roots.size() == 1 && "Should always have entry node!");
return Roots[0];
}
-
+
virtual bool runOnFunction(Function &F) {
reset(); // Reset from the last time we were run...
ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
calculate(ID);
return false;
}
-
+
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<ImmediateDominators>();
template <> struct GraphTraits<DominatorTree::Node*> {
typedef DominatorTree::Node NodeType;
typedef NodeType::iterator ChildIteratorType;
-
+
static NodeType *getEntryNode(NodeType *N) {
return N;
}
}
};
+
+//===-------------------------------------
+/// ET-Forest Class - Class used to construct forwards and backwards
+/// ET-Forests
+///
+class ETForestBase : public DominatorBase {
+public:
+ ETForestBase(bool isPostDom) : DominatorBase(isPostDom), Nodes(),
+ DFSInfoValid(false), SlowQueries(0) {}
+
+ virtual void releaseMemory() { reset(); }
+
+ typedef std::map<BasicBlock*, ETNode*> ETMapType;
+
+ void updateDFSNumbers();
+
+ /// dominates - Return true if A dominates B.
+ ///
+ inline bool dominates(BasicBlock *A, BasicBlock *B) {
+ if (A == B)
+ return true;
+
+ ETNode *NodeA = getNode(A);
+ ETNode *NodeB = getNode(B);
+
+ if (DFSInfoValid)
+ return NodeB->DominatedBy(NodeA);
+ else {
+ // If we end up with too many slow queries, just update the
+ // DFS numbers on the theory that we are going to keep querying.
+ SlowQueries++;
+ if (SlowQueries > 32) {
+ updateDFSNumbers();
+ return NodeB->DominatedBy(NodeA);
+ }
+ return NodeB->DominatedBySlow(NodeA);
+ }
+ }
+
+ /// properlyDominates - Return true if A dominates B and A != B.
+ ///
+ bool properlyDominates(BasicBlock *A, BasicBlock *B) {
+ return dominates(A, B) && A != B;
+ }
+
+ /// Return the nearest common dominator of A and B.
+ BasicBlock *nearestCommonDominator(BasicBlock *A, BasicBlock *B) const {
+ ETNode *NodeA = getNode(A);
+ ETNode *NodeB = getNode(B);
+
+ ETNode *Common = NodeA->NCA(NodeB);
+ if (!Common)
+ return NULL;
+ return Common->getData<BasicBlock>();
+ }
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ AU.addRequired<ImmediateDominators>();
+ }
+ //===--------------------------------------------------------------------===//
+ // API to update Forest information based on modifications
+ // to the CFG...
+
+ /// addNewBlock - Add a new block to the CFG, with the specified immediate
+ /// dominator.
+ ///
+ void addNewBlock(BasicBlock *BB, BasicBlock *IDom);
+
+ /// setImmediateDominator - Update the immediate dominator information to
+ /// change the current immediate dominator for the specified block
+ /// to another block. This method requires that BB for NewIDom
+ /// already have an ETNode, otherwise just use addNewBlock.
+ ///
+ void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom);
+ /// print - Convert to human readable form
+ ///
+ virtual void print(std::ostream &OS, const Module* = 0) const;
+protected:
+ /// getNode - return the (Post)DominatorTree node for the specified basic
+ /// block. This is the same as using operator[] on this class.
+ ///
+ inline ETNode *getNode(BasicBlock *BB) const {
+ ETMapType::const_iterator i = Nodes.find(BB);
+ return (i != Nodes.end()) ? i->second : 0;
+ }
+
+ inline ETNode *operator[](BasicBlock *BB) const {
+ return getNode(BB);
+ }
+
+ void reset();
+ ETMapType Nodes;
+ bool DFSInfoValid;
+ unsigned int SlowQueries;
+
+};
+
+//==-------------------------------------
+/// ETForest Class - Concrete subclass of ETForestBase that is used to
+/// compute a forwards ET-Forest.
+
+class ETForest : public ETForestBase {
+public:
+ ETForest() : ETForestBase(false) {}
+
+ BasicBlock *getRoot() const {
+ assert(Roots.size() == 1 && "Should always have entry node!");
+ return Roots[0];
+ }
+
+ virtual bool runOnFunction(Function &F) {
+ reset(); // Reset from the last time we were run...
+ ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
+ Roots = ID.getRoots();
+ calculate(ID);
+ return false;
+ }
+
+ void calculate(const ImmediateDominators &ID);
+ ETNode *getNodeForBlock(BasicBlock *BB);
+};
+
//===----------------------------------------------------------------------===//
-/// DominanceFrontier - Calculate the dominance frontiers for a function.
+/// DominanceFrontierBase - Common base class for computing forward and inverse
+/// dominance frontiers for a function.
///
-struct DominanceFrontierBase : public DominatorBase {
+class DominanceFrontierBase : public DominatorBase {
+public:
typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
protected:
//===-------------------------------------
-/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
-/// compute a normal dominator tree.
+/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
+/// used to compute a forward dominator frontiers.
///
-struct DominanceFrontier : public DominanceFrontierBase {
+class DominanceFrontier : public DominanceFrontierBase {
+public:
DominanceFrontier() : DominanceFrontierBase(false) {}
BasicBlock *getRoot() const {
const DominatorTree::Node *Node);
};
-// Make sure that any clients of this file link in Dominators.cpp
-static IncludeFile
-DOMINATORS_INCLUDE_FILE((void*)&DominatorSet::stub);
+
} // End llvm namespace
+// Make sure that any clients of this file link in Dominators.cpp
+FORCE_DEFINING_FILE_TO_BE_LINKED(DominatorSet)
+
#endif