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 {
/// 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;
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.
+///
+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>();
+ Roots = ID.getRoots();
+ calculate(ID);
+ return false;
+ }
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ AU.addRequired<ImmediateDominators>();
+ }
+private:
+ void calculate(const ImmediateDominators &ID);
+ Node *getNodeForBlock(BasicBlock *BB);
+};
+
+//===-------------------------------------
+/// DominatorTree GraphTraits specialization so the DominatorTree can be
+/// iterable by generic graph iterators.
+///
+template <> struct GraphTraits<DominatorTree::Node*> {
+ typedef DominatorTree::Node NodeType;
+ typedef NodeType::iterator ChildIteratorType;
+
+ static NodeType *getEntryNode(NodeType *N) {
+ return N;
+ }
+ static inline ChildIteratorType child_begin(NodeType* N) {
+ return N->begin();
+ }
+ static inline ChildIteratorType child_end(NodeType* N) {
+ return N->end();
+ }
+};
+
+template <> struct GraphTraits<DominatorTree*>
+ : public GraphTraits<DominatorTree::Node*> {
+ static NodeType *getEntryNode(DominatorTree *DT) {
+ return DT->getRootNode();
+ }
+};
+
//===-------------------------------------
/// ET-Forest Class - Class used to construct forwards and backwards
/// ET-Forests
///
-struct ETForestBase : public DominatorBase {
+class ETForestBase : public DominatorBase {
+public:
ETForestBase(bool isPostDom) : DominatorBase(isPostDom), Nodes(),
DFSInfoValid(false), SlowQueries(0) {}
/// ETForest Class - Concrete subclass of ETForestBase that is used to
/// compute a forwards ET-Forest.
-struct ETForest : public ETForestBase {
+class ETForest : public ETForestBase {
+public:
ETForest() : ETForestBase(false) {}
BasicBlock *getRoot() const {
ETNode *getNodeForBlock(BasicBlock *BB);
};
-//===-------------------------------------
-/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
-/// compute a normal dominator tree.
-///
-struct DominatorTree : public DominatorTreeBase {
- 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>();
- Roots = ID.getRoots();
- calculate(ID);
- return false;
- }
-
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.setPreservesAll();
- AU.addRequired<ImmediateDominators>();
- }
-private:
- void calculate(const ImmediateDominators &ID);
- Node *getNodeForBlock(BasicBlock *BB);
-};
-
-//===-------------------------------------
-/// DominatorTree GraphTraits specialization so the DominatorTree can be
-/// iterable by generic graph iterators.
-///
-template <> struct GraphTraits<DominatorTree::Node*> {
- typedef DominatorTree::Node NodeType;
- typedef NodeType::iterator ChildIteratorType;
-
- static NodeType *getEntryNode(NodeType *N) {
- return N;
- }
- static inline ChildIteratorType child_begin(NodeType* N) {
- return N->begin();
- }
- static inline ChildIteratorType child_end(NodeType* N) {
- return N->end();
- }
-};
-
-template <> struct GraphTraits<DominatorTree*>
- : public GraphTraits<DominatorTree::Node*> {
- static NodeType *getEntryNode(DominatorTree *DT) {
- return DT->getRootNode();
- }
-};
-
//===----------------------------------------------------------------------===//
-/// 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 {
};
-// 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
projects / oota-llvm.git / blobdiff