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_DOMINATORS_H
  19 #define LLVM_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   static AnalysisID ID;            // Build dominator set
 101
 102   DominatorSet() : DominatorSetBase(false) {}
 103
 104   virtual bool runOnFunction(Function &F);
 105
 106   // getAnalysisUsage - This simply provides a dominator set
 107   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 108     AU.setPreservesAll();
 109     AU.addProvided(ID);
 110   }
 111 };
 112
 113
 114 //===-------------------------------------
 115 // DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
 116 // compute the post-dominator set.
 117 //
 118 struct PostDominatorSet : public DominatorSetBase {
 119   static AnalysisID ID;            // Build post-dominator set
 120
 121   PostDominatorSet() : DominatorSetBase(true) {}
 122
 123   virtual bool runOnFunction(Function &F);
 124
 125   // getAnalysisUsage - This obviously provides a dominator set, but it also
 126   // uses the UnifyFunctionExitNode pass if building post-dominators
 127   //
 128   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 129 };
 130
 131
 132
 133
 134
 135 //===----------------------------------------------------------------------===//
 136 //
 137 // ImmediateDominators - Calculate the immediate dominator for each node in a
 138 // function.
 139 //
 140 class ImmediateDominatorsBase : public DominatorBase {
 141 protected:
 142   std::map<BasicBlock*, BasicBlock*> IDoms;
 143   void calcIDoms(const DominatorSetBase &DS);
 144 public:
 145   ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {}
 146
 147   virtual void releaseMemory() { IDoms.clear(); }
 148
 149   // Accessor interface:
 150   typedef std::map<BasicBlock*, BasicBlock*> IDomMapType;
 151   typedef IDomMapType::const_iterator const_iterator;
 152   inline const_iterator begin() const { return IDoms.begin(); }
 153   inline const_iterator end()   const { return IDoms.end(); }
 154   inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);}
 155
 156   // operator[] - Return the idom for the specified basic block.  The start
 157   // node returns null, because it does not have an immediate dominator.
 158   //
 159   inline BasicBlock *operator[](BasicBlock *BB) const {
 160     std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
 161     return I != IDoms.end() ? I->second : 0;
 162   }
 163
 164   // print - Convert to human readable form
 165   virtual void print(std::ostream &OS) const;
 166 };
 167
 168 //===-------------------------------------
 169 // ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase that
 170 // is used to compute a normal immediate dominator set.
 171 //
 172 struct ImmediateDominators : public ImmediateDominatorsBase {
 173   static AnalysisID ID;         // Build immediate dominators
 174
 175   ImmediateDominators() : ImmediateDominatorsBase(false) {}
 176
 177   virtual bool runOnFunction(Function &F) {
 178     IDoms.clear();     // Reset from the last time we were run...
 179     DominatorSet &DS = getAnalysis<DominatorSet>();
 180     Root = DS.getRoot();
 181     calcIDoms(DS);
 182     return false;
 183   }
 184
 185   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 186     AU.setPreservesAll();
 187     AU.addProvided(ID);
 188     AU.addRequired(DominatorSet::ID);
 189   }
 190 };
 191
 192
 193 //===-------------------------------------
 194 // ImmediatePostDominators Class - Concrete subclass of ImmediateDominatorsBase
 195 // that is used to compute the immediate post-dominators.
 196 //
 197 struct ImmediatePostDominators : public ImmediateDominatorsBase {
 198   static AnalysisID ID;         // Build immediate postdominators
 199
 200   ImmediatePostDominators() : ImmediateDominatorsBase(true) {}
 201
 202   virtual bool runOnFunction(Function &F) {
 203     IDoms.clear();     // Reset from the last time we were run...
 204     PostDominatorSet &DS = getAnalysis<PostDominatorSet>();
 205     Root = DS.getRoot();
 206     calcIDoms(DS);
 207     return false;
 208   }
 209
 210   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 211     AU.setPreservesAll();
 212     AU.addRequired(PostDominatorSet::ID);
 213     AU.addProvided(ID);
 214   }
 215 };
 216
 217
 218
 219 //===----------------------------------------------------------------------===//
 220 //
 221 // DominatorTree - Calculate the immediate dominator tree for a function.
 222 //
 223 class DominatorTreeBase : public DominatorBase {
 224 protected:
 225   class Node2;
 226 public:
 227   typedef Node2 Node;
 228 protected:
 229   std::map<BasicBlock*, Node*> Nodes;
 230   void reset();
 231   typedef std::map<BasicBlock*, Node*> NodeMapType;
 232 public:
 233   class Node2 : public std::vector<Node*> {
 234     friend class DominatorTree;
 235     friend class PostDominatorTree;
 236     BasicBlock *TheNode;
 237     Node2 *IDom;
 238   public:
 239     inline BasicBlock *getNode() const { return TheNode; }
 240     inline Node2 *getIDom() const { return IDom; }
 241     inline const std::vector<Node*> &getChildren() const { return *this; }
 242
 243     // dominates - Returns true iff this dominates N.  Note that this is not a
 244     // constant time operation!
 245     inline bool dominates(const Node2 *N) const {
 246       const Node2 *IDom;
 247       while ((IDom = N->getIDom()) != 0 && IDom != this)
 248         N = IDom;   // Walk up the tree
 249       return IDom != 0;
 250     }
 251
 252   private:
 253     inline Node2(BasicBlock *node, Node *iDom)
 254       : TheNode(node), IDom(iDom) {}
 255     inline Node2 *addChild(Node *C) { push_back(C); return C; }
 256   };
 257
 258 public:
 259   DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
 260   ~DominatorTreeBase() { reset(); }
 261
 262   virtual void releaseMemory() { reset(); }
 263
 264   inline Node *operator[](BasicBlock *BB) const {
 265     NodeMapType::const_iterator i = Nodes.find(BB);
 266     return (i != Nodes.end()) ? i->second : 0;
 267   }
 268
 269   // print - Convert to human readable form
 270   virtual void print(std::ostream &OS) const;
 271 };
 272
 273
 274 //===-------------------------------------
 275 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 276 // compute a normal dominator tree.
 277 //
 278 struct DominatorTree : public DominatorTreeBase {
 279   static AnalysisID ID;         // Build dominator tree
 280
 281   DominatorTree() : DominatorTreeBase(false) {}
 282
 283   virtual bool runOnFunction(Function &F) {
 284     reset();     // Reset from the last time we were run...
 285     DominatorSet &DS = getAnalysis<DominatorSet>();
 286     Root = DS.getRoot();
 287     calculate(DS);
 288     return false;
 289   }
 290
 291   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 292     AU.setPreservesAll();
 293     AU.addProvided(ID);
 294     AU.addRequired(DominatorSet::ID);
 295   }
 296 private:
 297   void calculate(const DominatorSet &DS);
 298 };
 299
 300
 301 //===-------------------------------------
 302 // PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
 303 // compute the a post-dominator tree.
 304 //
 305 struct PostDominatorTree : public DominatorTreeBase {
 306   static AnalysisID ID;         // Build immediate postdominators
 307
 308   PostDominatorTree() : DominatorTreeBase(true) {}
 309
 310   virtual bool runOnFunction(Function &F) {
 311     reset();     // Reset from the last time we were run...
 312     PostDominatorSet &DS = getAnalysis<PostDominatorSet>();
 313     Root = DS.getRoot();
 314     calculate(DS);
 315     return false;
 316   }
 317
 318   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 319     AU.setPreservesAll();
 320     AU.addRequired(PostDominatorSet::ID);
 321     AU.addProvided(ID);
 322   }
 323 private:
 324   void calculate(const PostDominatorSet &DS);
 325 };
 326
 327
 328 //===----------------------------------------------------------------------===//
 329 //
 330 // DominanceFrontier - Calculate the dominance frontiers for a function.
 331 //
 332 class DominanceFrontierBase : public DominatorBase {
 333 public:
 334   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
 335   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
 336 protected:
 337   DomSetMapType Frontiers;
 338 public:
 339   DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
 340
 341   virtual void releaseMemory() { Frontiers.clear(); }
 342
 343   // Accessor interface:
 344   typedef DomSetMapType::const_iterator const_iterator;
 345   inline const_iterator begin() const { return Frontiers.begin(); }
 346   inline const_iterator end()   const { return Frontiers.end(); }
 347   inline const_iterator find(BasicBlock* B) const { return Frontiers.find(B); }
 348
 349   // print - Convert to human readable form
 350   virtual void print(std::ostream &OS) const;
 351 };
 352
 353
 354 //===-------------------------------------
 355 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 356 // compute a normal dominator tree.
 357 //
 358 struct DominanceFrontier : public DominanceFrontierBase {
 359   static AnalysisID ID;         // Build dominance frontier
 360
 361   DominanceFrontier() : DominanceFrontierBase(false) {}
 362
 363   virtual bool runOnFunction(Function &) {
 364     Frontiers.clear();
 365     DominatorTree &DT = getAnalysis<DominatorTree>();
 366     Root = DT.getRoot();
 367     calculate(DT, DT[Root]);
 368     return false;
 369   }
 370
 371   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 372     AU.setPreservesAll();
 373     AU.addProvided(ID);
 374     AU.addRequired(DominatorTree::ID);
 375   }
 376 private:
 377   const DomSetType &calculate(const DominatorTree &DT,
 378                               const DominatorTree::Node *Node);
 379 };
 380
 381
 382 //===-------------------------------------
 383
 384 // PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is
 385 // used to compute the a post-dominance frontier.
 386 //
 387 struct PostDominanceFrontier : public DominanceFrontierBase {
 388   static AnalysisID ID;         // Build post dominance frontier
 389
 390   PostDominanceFrontier() : DominanceFrontierBase(true) {}
 391
 392   virtual bool runOnFunction(Function &) {
 393     Frontiers.clear();
 394     PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
 395     Root = DT.getRoot();
 396     calculate(DT, DT[Root]);
 397     return false;
 398   }
 399
 400   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 401     AU.setPreservesAll();
 402     AU.addRequired(PostDominatorTree::ID);
 403     AU.addProvided(ID);
 404   }
 405 private:
 406   const DomSetType &calculate(const PostDominatorTree &DT,
 407                               const DominatorTree::Node *Node);
 408 };
 409
 410 #endif