include/llvm/Analysis/DominanceFrontier.h

   1 //===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the DominanceFrontier class, which calculate and holds the
  11 // dominance frontier for a function.
  12 //
  13 // This should be considered deprecated, don't add any more uses of this data
  14 // structure.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H
  19 #define LLVM_ANALYSIS_DOMINANCEFRONTIER_H
  20
  21 #include "llvm/IR/Dominators.h"
  22 #include <map>
  23 #include <set>
  24
  25 namespace llvm {
  26
  27 //===----------------------------------------------------------------------===//
  28 /// DominanceFrontierBase - Common base class for computing forward and inverse
  29 /// dominance frontiers for a function.
  30 ///
  31 class DominanceFrontierBase : public FunctionPass {
  32 public:
  33   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
  34   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
  35 protected:
  36   DomSetMapType Frontiers;
  37   std::vector<BasicBlock*> Roots;
  38   const bool IsPostDominators;
  39
  40 public:
  41   DominanceFrontierBase(char &ID, bool isPostDom)
  42     : FunctionPass(ID), IsPostDominators(isPostDom) {}
  43
  44   /// getRoots - Return the root blocks of the current CFG.  This may include
  45   /// multiple blocks if we are computing post dominators.  For forward
  46   /// dominators, this will always be a single block (the entry node).
  47   ///
  48   inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
  49
  50   /// isPostDominator - Returns true if analysis based of postdoms
  51   ///
  52   bool isPostDominator() const { return IsPostDominators; }
  53
  54   virtual void releaseMemory() { Frontiers.clear(); }
  55
  56   // Accessor interface:
  57   typedef DomSetMapType::iterator iterator;
  58   typedef DomSetMapType::const_iterator const_iterator;
  59   iterator       begin()       { return Frontiers.begin(); }
  60   const_iterator begin() const { return Frontiers.begin(); }
  61   iterator       end()         { return Frontiers.end(); }
  62   const_iterator end()   const { return Frontiers.end(); }
  63   iterator       find(BasicBlock *B)       { return Frontiers.find(B); }
  64   const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
  65
  66   iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
  67     assert(find(BB) == end() && "Block already in DominanceFrontier!");
  68     return Frontiers.insert(std::make_pair(BB, frontier)).first;
  69   }
  70
  71   /// removeBlock - Remove basic block BB's frontier.
  72   void removeBlock(BasicBlock *BB) {
  73     assert(find(BB) != end() && "Block is not in DominanceFrontier!");
  74     for (iterator I = begin(), E = end(); I != E; ++I)
  75       I->second.erase(BB);
  76     Frontiers.erase(BB);
  77   }
  78
  79   void addToFrontier(iterator I, BasicBlock *Node) {
  80     assert(I != end() && "BB is not in DominanceFrontier!");
  81     I->second.insert(Node);
  82   }
  83
  84   void removeFromFrontier(iterator I, BasicBlock *Node) {
  85     assert(I != end() && "BB is not in DominanceFrontier!");
  86     assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
  87     I->second.erase(Node);
  88   }
  89
  90   /// compareDomSet - Return false if two domsets match. Otherwise
  91   /// return true;
  92   bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const {
  93     std::set<BasicBlock *> tmpSet;
  94     for (DomSetType::const_iterator I = DS2.begin(),
  95            E = DS2.end(); I != E; ++I)
  96       tmpSet.insert(*I);
  97
  98     for (DomSetType::const_iterator I = DS1.begin(),
  99            E = DS1.end(); I != E; ) {
 100       BasicBlock *Node = *I++;
 101
 102       if (tmpSet.erase(Node) == 0)
 103         // Node is in DS1 but not in DS2.
 104         return true;
 105     }
 106
 107     if (!tmpSet.empty())
 108       // There are nodes that are in DS2 but not in DS1.
 109       return true;
 110
 111     // DS1 and DS2 matches.
 112     return false;
 113   }
 114
 115   /// compare - Return true if the other dominance frontier base matches
 116   /// this dominance frontier base. Otherwise return false.
 117   bool compare(DominanceFrontierBase &Other) const {
 118     DomSetMapType tmpFrontiers;
 119     for (DomSetMapType::const_iterator I = Other.begin(),
 120            E = Other.end(); I != E; ++I)
 121       tmpFrontiers.insert(std::make_pair(I->first, I->second));
 122
 123     for (DomSetMapType::iterator I = tmpFrontiers.begin(),
 124            E = tmpFrontiers.end(); I != E; ) {
 125       BasicBlock *Node = I->first;
 126       const_iterator DFI = find(Node);
 127       if (DFI == end())
 128         return true;
 129
 130       if (compareDomSet(I->second, DFI->second))
 131         return true;
 132
 133       ++I;
 134       tmpFrontiers.erase(Node);
 135     }
 136
 137     if (!tmpFrontiers.empty())
 138       return true;
 139
 140     return false;
 141   }
 142
 143   /// print - Convert to human readable form
 144   ///
 145   virtual void print(raw_ostream &OS, const Module* = 0) const;
 146
 147   /// dump - Dump the dominance frontier to dbgs().
 148   void dump() const;
 149 };
 150
 151
 152 //===-------------------------------------
 153 /// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
 154 /// used to compute a forward dominator frontiers.
 155 ///
 156 class DominanceFrontier : public DominanceFrontierBase {
 157   virtual void anchor();
 158 public:
 159   static char ID; // Pass ID, replacement for typeid
 160   DominanceFrontier() :
 161     DominanceFrontierBase(ID, false) {
 162       initializeDominanceFrontierPass(*PassRegistry::getPassRegistry());
 163     }
 164
 165   BasicBlock *getRoot() const {
 166     assert(Roots.size() == 1 && "Should always have entry node!");
 167     return Roots[0];
 168   }
 169
 170   virtual bool runOnFunction(Function &) {
 171     Frontiers.clear();
 172     DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 173     Roots = DT.getRoots();
 174     assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
 175     calculate(DT, DT[Roots[0]]);
 176     return false;
 177   }
 178
 179   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 180     AU.setPreservesAll();
 181     AU.addRequired<DominatorTreeWrapperPass>();
 182   }
 183
 184   const DomSetType &calculate(const DominatorTree &DT,
 185                               const DomTreeNode *Node);
 186 };
 187
 188 } // End llvm namespace
 189
 190 #endif