Home | History | Annotate | Download | only in Analysis
      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/Analysis/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<DominatorTree>();
    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<DominatorTree>();
    182   }
    183 
    184   const DomSetType &calculate(const DominatorTree &DT,
    185                               const DomTreeNode *Node);
    186 };
    187 
    188 } // End llvm namespace
    189 
    190 #endif
    191