include/llvm/Analysis/Dominators.h

   1 //===- llvm/Analysis/Dominators.h - Dominator Info Calculation ---*- C++ -*--=//
   2 //
   3 // This file defines the following classes:
   4 //  1. DominatorSet: Calculates the [reverse] dominator set for a function
   5 //  2. ImmediateDominators: Calculates and holds a mapping between BasicBlocks
   6 //     and their immediate dominator.
   7 //  3. DominatorTree: Represent the ImmediateDominator as an explicit tree
   8 //     structure.
   9 //  4. DominanceFrontier: Calculate and hold the dominance frontier for a
  10 //     function.
  11 //
  12 //  These data structures are listed in increasing order of complexity.  It
  13 //  takes longer to calculate the dominator frontier, for example, than the
  14 //  ImmediateDominator mapping.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #ifndef LLVM_ANALYSIS_DOMINATORS_H
  19 #define LLVM_ANALYSIS_DOMINATORS_H
  20
  21 #include "llvm/Pass.h"
  22 #include <set>
  23 class Instruction;
  24
  25 //===----------------------------------------------------------------------===//
  26 //
  27 // DominatorBase - Base class that other, more interesting dominator analyses
  28 // inherit from.
  29 //
  30 class DominatorBase : public FunctionPass {
  31 protected:
  32   BasicBlock *Root;
  33   const bool IsPostDominators;
  34
  35   inline DominatorBase(bool isPostDom) : Root(0), IsPostDominators(isPostDom) {}
  36 public:
  37   inline BasicBlock *getRoot() const { return Root; }
  38
  39   // Returns true if analysis based of postdoms
  40   bool isPostDominator() const { return IsPostDominators; }
  41 };
  42
  43 //===----------------------------------------------------------------------===//
  44 //
  45 // DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
  46 // function, that represents the blocks that dominate the block.
  47 //
  48 class DominatorSetBase : public DominatorBase {
  49 public:
  50   typedef std::set<BasicBlock*> DomSetType;    // Dom set for a bb
  51   // Map of dom sets
  52   typedef std::map<BasicBlock*, DomSetType> DomSetMapType;
  53 protected:
  54   DomSetMapType Doms;
  55 public:
  56   DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
  57
  58   virtual void releaseMemory() { Doms.clear(); }
  59
  60   // Accessor interface:
  61   typedef DomSetMapType::const_iterator const_iterator;
  62   typedef DomSetMapType::iterator iterator;
  63   inline const_iterator begin() const { return Doms.begin(); }
  64   inline       iterator begin()       { return Doms.begin(); }
  65   inline const_iterator end()   const { return Doms.end(); }
  66   inline       iterator end()         { return Doms.end(); }
  67   inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
  68   inline       iterator find(BasicBlock* B)       { return Doms.find(B); }
  69
  70   // getDominators - Return the set of basic blocks that dominate the specified
  71   // block.
  72   //
  73   inline const DomSetType &getDominators(BasicBlock *BB) const {
  74     const_iterator I = find(BB);
  75     assert(I != end() && "BB not in function!");
  76     return I->second;
  77   }
  78
  79   // dominates - Return true if A dominates B.
  80   //
  81   inline bool dominates(BasicBlock *A, BasicBlock *B) const {
  82     return getDominators(B).count(A) != 0;
  83   }
  84
  85   // print - Convert to human readable form
  86   virtual void print(std::ostream &OS) const;
  87
  88   // dominates - Return true if A dominates B.  This performs the special checks
  89   // neccesary if A and B are in the same basic block.
  90   //
  91   bool dominates(Instruction *A, Instruction *B) const;
  92 };
  93
  94
  95 //===-------------------------------------
  96 // DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
  97 // compute a normal dominator set.
  98 //
  99 struct DominatorSet : public DominatorSetBase {
 100   DominatorSet() : DominatorSetBase(false) {}
 101
 102   virtual bool runOnFunction(Function &F);
 103
 104   // getAnalysisUsage - This simply provides a dominator set
 105   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 106     AU.setPreservesAll();
 107   }
 108 private:
 109   void calculateDominatorsFromBlock(BasicBlock *BB);
 110 };
 111
 112
 113 //===----------------------------------------------------------------------===//
 114 //
 115 // ImmediateDominators - Calculate the immediate dominator for each node in a
 116 // function.
 117 //
 118 class ImmediateDominatorsBase : public DominatorBase {
 119 protected:
 120   std::map<BasicBlock*, BasicBlock*> IDoms;
 121   void calcIDoms(const DominatorSetBase &DS);
 122 public:
 123   ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {}
 124
 125   virtual void releaseMemory() { IDoms.clear(); }
 126
 127   // Accessor interface:
 128   typedef std::map<BasicBlock*, BasicBlock*> IDomMapType;
 129   typedef IDomMapType::const_iterator const_iterator;
 130   inline const_iterator begin() const { return IDoms.begin(); }
 131   inline const_iterator end()   const { return IDoms.end(); }
 132   inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);}
 133
 134   // operator[] - Return the idom for the specified basic block.  The start
 135   // node returns null, because it does not have an immediate dominator.
 136   //
 137   inline BasicBlock *operator[](BasicBlock *BB) const {
 138     std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
 139     return I != IDoms.end() ? I->second : 0;
 140   }
 141
 142   // print - Convert to human readable form
 143   virtual void print(std::ostream &OS) const;
 144 };
 145
 146 //===-------------------------------------
 147 // ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase that
 148 // is used to compute a normal immediate dominator set.
 149 //
 150 struct ImmediateDominators : public ImmediateDominatorsBase {
 151   ImmediateDominators() : ImmediateDominatorsBase(false) {}
 152
 153   virtual bool runOnFunction(Function &F) {
 154     IDoms.clear();     // Reset from the last time we were run...
 155     DominatorSet &DS = getAnalysis<DominatorSet>();
 156     Root = DS.getRoot();
 157     calcIDoms(DS);
 158     return false;
 159   }
 160
 161   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 162     AU.setPreservesAll();
 163     AU.addRequired<DominatorSet>();
 164   }
 165 };
 166
 167
 168 //===----------------------------------------------------------------------===//
 169 //
 170 // DominatorTree - Calculate the immediate dominator tree for a function.
 171 //
 172 class DominatorTreeBase : public DominatorBase {
 173 protected:
 174   class Node2;
 175 public:
 176   typedef Node2 Node;
 177 protected:
 178   std::map<BasicBlock*, Node*> Nodes;
 179   void reset();
 180   typedef std::map<BasicBlock*, Node*> NodeMapType;
 181 public:
 182   class Node2 : public std::vector<Node*> {
 183     friend class DominatorTree;
 184     friend class PostDominatorTree;
 185     BasicBlock *TheNode;
 186     Node2 *IDom;
 187   public:
 188     inline BasicBlock *getNode() const { return TheNode; }
 189     inline Node2 *getIDom() const { return IDom; }
 190     inline const std::vector<Node*> &getChildren() const { return *this; }
 191
 192     // dominates - Returns true iff this dominates N.  Note that this is not a
 193     // constant time operation!
 194     inline bool dominates(const Node2 *N) const {
 195       const Node2 *IDom;
 196       while ((IDom = N->getIDom()) != 0 && IDom != this)
 197         N = IDom;   // Walk up the tree
 198       return IDom != 0;
 199     }
 200
 201   private:
 202     inline Node2(BasicBlock *node, Node *iDom)
 203       : TheNode(node), IDom(iDom) {}
 204     inline Node2 *addChild(Node *C) { push_back(C); return C; }
 205   };
 206
 207 public:
 208   DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
 209   ~DominatorTreeBase() { reset(); }
 210
 211   virtual void releaseMemory() { reset(); }
 212
 213   inline Node *operator[](BasicBlock *BB) const {
 214     NodeMapType::const_iterator i = Nodes.find(BB);
 215     return (i != Nodes.end()) ? i->second : 0;
 216   }
 217
 218   // print - Convert to human readable form
 219   virtual void print(std::ostream &OS) const;
 220 };
 221
 222
 223 //===-------------------------------------
 224 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 225 // compute a normal dominator tree.
 226 //
 227 struct DominatorTree : public DominatorTreeBase {
 228   DominatorTree() : DominatorTreeBase(false) {}
 229
 230   virtual bool runOnFunction(Function &F) {
 231     reset();     // Reset from the last time we were run...
 232     DominatorSet &DS = getAnalysis<DominatorSet>();
 233     Root = DS.getRoot();
 234     calculate(DS);
 235     return false;
 236   }
 237
 238   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 239     AU.setPreservesAll();
 240     AU.addRequired<DominatorSet>();
 241   }
 242 private:
 243   void calculate(const DominatorSet &DS);
 244 };
 245
 246
 247 //===----------------------------------------------------------------------===//
 248 //
 249 // DominanceFrontier - Calculate the dominance frontiers for a function.
 250 //
 251 class DominanceFrontierBase : public DominatorBase {
 252 public:
 253   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
 254   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
 255 protected:
 256   DomSetMapType Frontiers;
 257 public:
 258   DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
 259
 260   virtual void releaseMemory() { Frontiers.clear(); }
 261
 262   // Accessor interface:
 263   typedef DomSetMapType::const_iterator const_iterator;
 264   inline const_iterator begin() const { return Frontiers.begin(); }
 265   inline const_iterator end()   const { return Frontiers.end(); }
 266   inline const_iterator find(BasicBlock* B) const { return Frontiers.find(B); }
 267
 268   // print - Convert to human readable form
 269   virtual void print(std::ostream &OS) const;
 270 };
 271
 272
 273 //===-------------------------------------
 274 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 275 // compute a normal dominator tree.
 276 //
 277 struct DominanceFrontier : public DominanceFrontierBase {
 278   DominanceFrontier() : DominanceFrontierBase(false) {}
 279
 280   virtual bool runOnFunction(Function &) {
 281     Frontiers.clear();
 282     DominatorTree &DT = getAnalysis<DominatorTree>();
 283     Root = DT.getRoot();
 284     calculate(DT, DT[Root]);
 285     return false;
 286   }
 287
 288   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 289     AU.setPreservesAll();
 290     AU.addRequired<DominatorTree>();
 291   }
 292 private:
 293   const DomSetType &calculate(const DominatorTree &DT,
 294                               const DominatorTree::Node *Node);
 295 };
 296
 297 #endif