diff options
| -rw-r--r-- | include/llvm/Analysis/CallGraph.h | 22 | ||||
| -rw-r--r-- | include/llvm/Analysis/Dominators.h | 174 | ||||
| -rw-r--r-- | include/llvm/Analysis/FindUnsafePointerTypes.h | 17 | ||||
| -rw-r--r-- | include/llvm/Analysis/FindUsedTypes.h | 20 | ||||
| -rw-r--r-- | include/llvm/Analysis/IntervalPartition.h | 26 | ||||
| -rw-r--r-- | include/llvm/Analysis/LoopInfo.h | 19 |
6 files changed, 206 insertions, 72 deletions
diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h index f5b020269c..6fea49bb6f 100644 --- a/include/llvm/Analysis/CallGraph.h +++ b/include/llvm/Analysis/CallGraph.h @@ -17,8 +17,7 @@ #define LLVM_ANALYSIS_CALLGRAPH_H #include "Support/GraphTraits.h" -#include <map> -#include <vector> +#include "llvm/Pass.h" class Method; class Module; @@ -62,7 +61,7 @@ private: // Stuff to construct the node, used by CallGraph }; -class CallGraph { +class CallGraph : public Pass { Module *Mod; // The module this call graph represents typedef std::map<const Method *, CallGraphNode *> MethodMapTy; @@ -70,8 +69,10 @@ class CallGraph { CallGraphNode *Root; public: - CallGraph(Module *TheModule); - ~CallGraph(); + static AnalysisID ID; // We are an analysis, we must have an ID + + CallGraph(AnalysisID AID) : Root(0) { assert(AID == ID); } + ~CallGraph() { destroy(); } typedef MethodMapTy::iterator iterator; typedef MethodMapTy::const_iterator const_iterator; @@ -111,7 +112,18 @@ public: return removeMethodFromModule((*this)[Meth]); } + // run - Compute the call graph for the specified module. + virtual bool run(Module *TheModule); + + // getAnalysisUsageInfo - This obviously provides a call graph + virtual void getAnalysisUsageInfo(AnalysisSet &Required, + AnalysisSet &Destroyed, + AnalysisSet &Provided) { + Provided.push_back(ID); + } + private: // Implementation of CallGraph construction + void destroy(); // getNodeFor - Return the node for the specified method or create one if it // does not already exist. 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 diff --git a/include/llvm/Analysis/FindUnsafePointerTypes.h b/include/llvm/Analysis/FindUnsafePointerTypes.h index 4b2251d905..cd34676727 100644 --- a/include/llvm/Analysis/FindUnsafePointerTypes.h +++ b/include/llvm/Analysis/FindUnsafePointerTypes.h @@ -22,26 +22,35 @@ class PointerType; -struct FindUnsafePointerTypes : public MethodPass { +struct FindUnsafePointerTypes : public Pass { // UnsafeTypes - Set of types that are not safe to transform. std::set<PointerType*> UnsafeTypes; public: + static AnalysisID ID; // We are an analysis, we must have an ID + + FindUnsafePointerTypes(AnalysisID id) { assert(ID == id); } // Accessor for underlying type set... inline const std::set<PointerType*> &getUnsafeTypes() const { return UnsafeTypes; } - // runOnMethod - Inspect the operations that the specified method does on + // run - Inspect the operations that the specified module does on // values of various types. If they are deemed to be 'unsafe' note that the // type is not safe to transform. // - virtual bool runOnMethod(Method *M); + virtual bool run(Module *M); // printResults - Loop over the results of the analysis, printing out unsafe // types. // - void printResults(const Module *Mod, std::ostream &o); + void printResults(const Module *Mod, std::ostream &o) const; + + // getAnalysisUsageInfo - This function needs FindUsedTypes to do its job... + // + virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Required, + Pass::AnalysisSet &Destroyed, + Pass::AnalysisSet &Provided); }; #endif diff --git a/include/llvm/Analysis/FindUsedTypes.h b/include/llvm/Analysis/FindUsedTypes.h index 1005042ab9..bbaf8dff6b 100644 --- a/include/llvm/Analysis/FindUsedTypes.h +++ b/include/llvm/Analysis/FindUsedTypes.h @@ -10,17 +10,20 @@ #include "llvm/Pass.h" #include <set> class SymbolTable; +class Type; -class FindUsedTypes : public MethodPass { +class FindUsedTypes : public Pass { std::set<const Type *> UsedTypes; bool IncludeSymbolTables; public: - // FindUsedTypes ctor - This pass can optionally include types that are // referenced only in symbol tables, but the default is not to. // - FindUsedTypes(bool IST = false) : IncludeSymbolTables(IST) {} + static AnalysisID ID; + static AnalysisID IncludeSymbolTableID; + + FindUsedTypes(AnalysisID id) : IncludeSymbolTables(id != ID) {} // getTypes - After the pass has been run, return the set containing all of // the types used in the module. @@ -45,14 +48,15 @@ private: void IncorporateSymbolTable(const SymbolTable *ST); public: - // doInitialization - This loops over global constants defined in the - // module, converting them to their new type. + // run - This incorporates all types used by the specified module // - bool doInitialization(Module *M); + bool run(Module *M); - // runOnMethod - This incorporates all types used by the specified method + // getAnalysisUsageInfo - This function needs FindUsedTypes to do its job... // - bool runOnMethod(Method *M); + virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Required, + Pass::AnalysisSet &Destroyed, + Pass::AnalysisSet &Provided); }; #endif diff --git a/include/llvm/Analysis/IntervalPartition.h b/include/llvm/Analysis/IntervalPartition.h index f05408b022..16b3c9c457 100644 --- a/include/llvm/Analysis/IntervalPartition.h +++ b/include/llvm/Analysis/IntervalPartition.h @@ -17,9 +17,7 @@ #define LLVM_INTERVAL_PARTITION_H #include "llvm/Analysis/Interval.h" -#include <map> - -class Method; +#include "llvm/Pass.h" namespace cfg { @@ -31,7 +29,7 @@ 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; @@ -39,8 +37,12 @@ class IntervalPartition : public std::vector<Interval*> { 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 @@ -49,7 +51,7 @@ public: IntervalPartition(IntervalPartition &I, bool); // Destructor - Free memory - ~IntervalPartition(); + ~IntervalPartition() { destroy(); } // getRootInterval() - Return the root interval that contains the starting // block of the method. @@ -67,7 +69,17 @@ public: 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). diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index 10fcfe9f30..f36550e504 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -10,10 +10,8 @@ #ifndef LLVM_ANALYSIS_LOOP_INFO_H #define LLVM_ANALYSIS_LOOP_INFO_H -#include <vector> -#include <map> +#include "llvm/Pass.h" #include <set> -class BasicBlock; namespace cfg { class DominatorSet; @@ -62,13 +60,15 @@ private: // LoopInfo - This class builds and contains all of the top level loop // structures in the specified method. // -class LoopInfo { +class LoopInfo : public MethodPass { // BBMap - Mapping of basic blocks to the inner most loop they occur in std::map<const BasicBlock *, Loop*> BBMap; std::vector<Loop*> TopLevelLoops; public: + static AnalysisID ID; // cfg::LoopInfo Analysis ID + // LoopInfo ctor - Calculate the natural loop information for a CFG - LoopInfo(const DominatorSet &DS); + LoopInfo(AnalysisID id) { assert(id == ID); } const std::vector<Loop*> &getTopLevelLoops() const { return TopLevelLoops; } @@ -100,7 +100,16 @@ public: bool isLoopExit(const BasicBlock *BB) const; #endif + // runOnMethod - Pass framework implementation + virtual bool runOnMethod(Method *M); + + // getAnalysisUsageInfo - Provide loop info, require dominator set + // + virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires, + Pass::AnalysisSet &Destroyed, + Pass::AnalysisSet &Provided); private: + void Calculate(const DominatorSet &DS); Loop *ConsiderForLoop(const BasicBlock *BB, const DominatorSet &DS); }; |