-//===- 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
#ifndef LLVM_DOMINATORS_H
#define LLVM_DOMINATORS_H
+#include "llvm/Pass.h"
#include <set>
-#include <map>
-#include <vector>
-class Method;
-class BasicBlock;
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; }
};
//===----------------------------------------------------------------------===//
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.
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);
};
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:
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);
+ }
+ }
};
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*> {
};
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);
+ }
+ }
};
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
#define LLVM_INTERVAL_PARTITION_H
#include "llvm/Analysis/Interval.h"
-#include <map>
-
-class Method;
+#include "llvm/Pass.h"
namespace cfg {
// BasicBlock is a (possibly nonexistent) loop with a "tail" of non looping
// nodes following it.
//
-class IntervalPartition : public std::vector<Interval*> {
+class IntervalPartition : public MethodPass, public std::vector<Interval*> {
typedef std::map<BasicBlock*, Interval*> IntervalMapTy;
IntervalMapTy IntervalMap;
Interval *RootInterval;
public:
- // IntervalPartition ctor - Build the partition for the specified method
- IntervalPartition(Method *M);
+ static AnalysisID ID; // We are an analysis, we must have an ID
+
+ IntervalPartition(AnalysisID AID) : RootInterval(0) { assert(AID == ID); }
+
+ // run - Calculate the interval partition for this method
+ virtual bool runOnMethod(Method *M);
// IntervalPartition ctor - Build a reduced interval partition from an
// existing interval graph. This takes an additional boolean parameter to
IntervalPartition(IntervalPartition &I, bool);
// Destructor - Free memory
- ~IntervalPartition();
+ ~IntervalPartition() { destroy(); }
// getRootInterval() - Return the root interval that contains the starting
// block of the method.
return I != IntervalMap.end() ? I->second : 0;
}
+ // getAnalysisUsageInfo - Implement the Pass API
+ virtual void getAnalysisUsageInfo(AnalysisSet &Required,
+ AnalysisSet &Destroyed,
+ AnalysisSet &Provided) {
+ Provided.push_back(ID);
+ }
+
private:
+ // destroy - Reset state back to before method was analyzed
+ void destroy();
+
// addIntervalToPartition - Add an interval to the internal list of intervals,
// and then add mappings from all of the basic blocks in the interval to the
// interval itself (in the IntervalMap).
projects / oota-llvm.git / commitdiff