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