aboutsummaryrefslogtreecommitdiff
path: root/include/llvm/Analysis/Dominators.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/Analysis/Dominators.h')
-rw-r--r--include/llvm/Analysis/Dominators.h174
1 files changed, 131 insertions, 43 deletions
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index c018eafe2c..6de4e5b9bf 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -1,4 +1,4 @@
-//===- llvm/Analysis/DominatorSet.h - Dominator Set Calculation --*- C++ -*--=//
+//===- llvm/Analysis/Dominators.h - Dominator Info Calculation ---*- C++ -*--=//
//
// This file defines the following classes:
// 1. DominatorSet: Calculates the [reverse] dominator set for a method
@@ -18,11 +18,8 @@
#ifndef LLVM_DOMINATORS_H
#define LLVM_DOMINATORS_H
+#include "llvm/Pass.h"
#include <set>
-#include <map>
-#include <vector>
-class Method;
-class BasicBlock;
namespace cfg {
@@ -31,13 +28,18 @@ namespace cfg {
// DominatorBase - Base class that other, more interesting dominator analyses
// inherit from.
//
-class DominatorBase {
+class DominatorBase : public MethodPass {
protected:
- const BasicBlock *Root;
- inline DominatorBase(const BasicBlock *root = 0) : Root(root) {}
+ BasicBlock *Root;
+ const bool IsPostDominators;
+
+ inline DominatorBase(bool isPostDom) : Root(0), IsPostDominators(isPostDom) {}
public:
inline const BasicBlock *getRoot() const { return Root; }
- bool isPostDominator() const; // Returns true if analysis based of postdoms
+ inline BasicBlock *getRoot() { return Root; }
+
+ // Returns true if analysis based of postdoms
+ bool isPostDominator() const { return IsPostDominators; }
};
//===----------------------------------------------------------------------===//
@@ -53,21 +55,28 @@ public:
private:
DomSetMapType Doms;
- void calcForwardDominatorSet(const Method *M);
+ void calcForwardDominatorSet(Method *M);
+ void calcPostDominatorSet(Method *M);
public:
// DominatorSet ctor - Build either the dominator set or the post-dominator
- // set for a method... Building the postdominator set may require the analysis
- // routine to modify the method so that there is only a single return in the
- // method.
+ // set for a method...
//
- DominatorSet(const Method *M);
- DominatorSet( Method *M, bool PostDomSet);
+ static AnalysisID ID; // Build dominator set
+ static AnalysisID PostDomID; // Build postdominator set
+
+ DominatorSet(AnalysisID id) : DominatorBase(id == PostDomID) {}
+
+ virtual bool runOnMethod(Method *M);
// Accessor interface:
typedef DomSetMapType::const_iterator const_iterator;
+ typedef DomSetMapType::iterator iterator;
inline const_iterator begin() const { return Doms.begin(); }
+ inline iterator begin() { return Doms.begin(); }
inline const_iterator end() const { return Doms.end(); }
+ inline iterator end() { return Doms.end(); }
inline const_iterator find(const BasicBlock* B) const { return Doms.find(B); }
+ inline iterator find( BasicBlock* B) { return Doms.find(B); }
// getDominators - Return the set of basic blocks that dominate the specified
// block.
@@ -83,6 +92,13 @@ public:
inline bool dominates(const BasicBlock *A, const BasicBlock *B) const {
return getDominators(B).count(A) != 0;
}
+
+ // getAnalysisUsageInfo - This obviously provides a dominator set, but it also
+ // uses the UnifyMethodExitNode pass if building post-dominators
+ //
+ virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
+ Pass::AnalysisSet &Destroyed,
+ Pass::AnalysisSet &Provided);
};
@@ -96,12 +112,25 @@ class ImmediateDominators : public DominatorBase {
void calcIDoms(const DominatorSet &DS);
public:
- // ImmediateDominators ctor - Calculate the idom mapping, for a method, or
- // from a dominator set calculated for something else...
+ // ImmediateDominators ctor - Calculate the idom or post-idom mapping,
+ // for a method...
//
- inline ImmediateDominators(const DominatorSet &DS)
- : DominatorBase(DS.getRoot()) {
- calcIDoms(DS); // Can be used to make rev-idoms
+ static AnalysisID ID; // Build immediate dominators
+ static AnalysisID PostDomID; // Build immediate postdominators
+
+ ImmediateDominators(AnalysisID id) : DominatorBase(id == PostDomID) {}
+
+ virtual bool runOnMethod(Method *M) {
+ IDoms.clear(); // Reset from the last time we were run...
+ DominatorSet *DS;
+ if (isPostDominator())
+ DS = &getAnalysis<DominatorSet>(DominatorSet::PostDomID);
+ else
+ DS = &getAnalysis<DominatorSet>();
+
+ Root = DS->getRoot();
+ calcIDoms(*DS); // Can be used to make rev-idoms
+ return false;
}
// Accessor interface:
@@ -119,6 +148,21 @@ public:
IDoms.find(BB);
return I != IDoms.end() ? I->second : 0;
}
+
+ // getAnalysisUsageInfo - This obviously provides a dominator tree, but it
+ // can only do so with the input of dominator sets
+ //
+ virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
+ Pass::AnalysisSet &Destroyed,
+ Pass::AnalysisSet &Provided) {
+ if (isPostDominator()) {
+ Requires.push_back(DominatorSet::PostDomID);
+ Provided.push_back(PostDomID);
+ } else {
+ Requires.push_back(DominatorSet::ID);
+ Provided.push_back(ID);
+ }
+ }
};
@@ -133,6 +177,7 @@ public:
private:
std::map<const BasicBlock*, Node*> Nodes;
void calculate(const DominatorSet &DS);
+ void reset();
typedef std::map<const BasicBlock*, Node*> NodeMapType;
public:
class Node2 : public std::vector<Node*> {
@@ -160,19 +205,45 @@ public:
};
public:
- // DominatorTree ctors - Compute a dominator tree, given various amounts of
+ // DominatorTree ctor - Compute a dominator tree, given various amounts of
// previous knowledge...
- inline DominatorTree(const DominatorSet &DS) : DominatorBase(DS.getRoot()) {
- calculate(DS);
- }
+ static AnalysisID ID; // Build dominator tree
+ static AnalysisID PostDomID; // Build postdominator tree
- DominatorTree(const ImmediateDominators &IDoms);
- ~DominatorTree();
+ DominatorTree(AnalysisID id) : DominatorBase(id == PostDomID) {}
+ ~DominatorTree() { reset(); }
+
+ virtual bool runOnMethod(Method *M) {
+ reset();
+ DominatorSet *DS;
+ if (isPostDominator())
+ DS = &getAnalysis<DominatorSet>(DominatorSet::PostDomID);
+ else
+ DS = &getAnalysis<DominatorSet>();
+ Root = DS->getRoot();
+ calculate(*DS); // Can be used to make rev-idoms
+ return false;
+ }
inline const Node *operator[](const BasicBlock *BB) const {
NodeMapType::const_iterator i = Nodes.find(BB);
return (i != Nodes.end()) ? i->second : 0;
}
+
+ // getAnalysisUsageInfo - This obviously provides a dominator tree, but it
+ // uses dominator sets
+ //
+ virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
+ Pass::AnalysisSet &Destroyed,
+ Pass::AnalysisSet &Provided) {
+ if (isPostDominator()) {
+ Requires.push_back(DominatorSet::PostDomID);
+ Provided.push_back(PostDomID);
+ } else {
+ Requires.push_back(DominatorSet::ID);
+ Provided.push_back(ID);
+ }
+ }
};
@@ -191,33 +262,50 @@ private:
const DomSetType &calcPostDomFrontier(const DominatorTree &DT,
const DominatorTree::Node *Node);
public:
- DominanceFrontier(const DominatorSet &DS) : DominatorBase(DS.getRoot()) {
- const DominatorTree DT(DS);
- if (isPostDominator())
- calcPostDomFrontier(DT, DT[Root]);
- else
- calcDomFrontier(DT, DT[Root]);
- }
- DominanceFrontier(const ImmediateDominators &ID)
- : DominatorBase(ID.getRoot()) {
- const DominatorTree DT(ID);
+
+ // DominatorFrontier ctor - Compute dominator frontiers for a method
+ //
+ static AnalysisID ID; // Build dominator frontier
+ static AnalysisID PostDomID; // Build postdominator frontier
+
+ DominanceFrontier(AnalysisID id) : DominatorBase(id == PostDomID) {}
+
+ virtual bool runOnMethod(Method *M) {
+ Frontiers.clear();
+ DominatorTree *DT;
if (isPostDominator())
- calcPostDomFrontier(DT, DT[Root]);
+ DT = &getAnalysis<DominatorTree>(DominatorTree::PostDomID);
else
- calcDomFrontier(DT, DT[Root]);
- }
- DominanceFrontier(const DominatorTree &DT) : DominatorBase(DT.getRoot()) {
+ DT = &getAnalysis<DominatorTree>();
+ Root = DT->getRoot();
+
if (isPostDominator())
- calcPostDomFrontier(DT, DT[Root]);
+ calcPostDomFrontier(*DT, (*DT)[Root]);
else
- calcDomFrontier(DT, DT[Root]);
+ calcDomFrontier(*DT, (*DT)[Root]);
+ return false;
}
// Accessor interface:
typedef DomSetMapType::const_iterator const_iterator;
inline const_iterator begin() const { return Frontiers.begin(); }
inline const_iterator end() const { return Frontiers.end(); }
- inline const_iterator find(const BasicBlock* B) const { return Frontiers.find(B);}
+ inline const_iterator find(const BasicBlock* B) const { return Frontiers.find(B); }
+
+ // getAnalysisUsageInfo - This obviously provides a dominator tree, but it
+ // uses dominator sets
+ //
+ virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
+ Pass::AnalysisSet &Destroyed,
+ Pass::AnalysisSet &Provided) {
+ if (isPostDominator()) {
+ Requires.push_back(DominatorTree::PostDomID);
+ Provided.push_back(PostDomID);
+ } else {
+ Requires.push_back(DominatorTree::ID);
+ Provided.push_back(ID);
+ }
+ }
};
} // End namespace cfg
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-24 08:21:21 +0000