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 is the generic implementation of the DominanceFrontier class, which
     11 // calculate and holds the dominance frontier for a function for.
     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_DOMINANCEFRONTIERIMPL_H
     19 #define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
     20 
     21 #include "llvm/ADT/GraphTraits.h"
     22 #include "llvm/ADT/SmallPtrSet.h"
     23 #include "llvm/Analysis/DominanceFrontier.h"
     24 #include "llvm/Support/Debug.h"
     25 #include "llvm/Support/GenericDomTree.h"
     26 #include "llvm/Support/raw_ostream.h"
     27 #include <cassert>
     28 #include <set>
     29 #include <utility>
     30 #include <vector>
     31 
     32 namespace llvm {
     33 
     34 template <class BlockT>
     35 class DFCalculateWorkObject {
     36 public:
     37   using DomTreeNodeT = DomTreeNodeBase<BlockT>;
     38 
     39   DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N,
     40                         const DomTreeNodeT *PN)
     41       : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
     42 
     43   BlockT *currentBB;
     44   BlockT *parentBB;
     45   const DomTreeNodeT *Node;
     46   const DomTreeNodeT *parentNode;
     47 };
     48 
     49 template <class BlockT, bool IsPostDom>
     50 void DominanceFrontierBase<BlockT, IsPostDom>::removeBlock(BlockT *BB) {
     51   assert(find(BB) != end() && "Block is not in DominanceFrontier!");
     52   for (iterator I = begin(), E = end(); I != E; ++I)
     53     I->second.erase(BB);
     54   Frontiers.erase(BB);
     55 }
     56 
     57 template <class BlockT, bool IsPostDom>
     58 void DominanceFrontierBase<BlockT, IsPostDom>::addToFrontier(iterator I,
     59                                                              BlockT *Node) {
     60   assert(I != end() && "BB is not in DominanceFrontier!");
     61   assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
     62   I->second.erase(Node);
     63 }
     64 
     65 template <class BlockT, bool IsPostDom>
     66 void DominanceFrontierBase<BlockT, IsPostDom>::removeFromFrontier(
     67     iterator I, BlockT *Node) {
     68   assert(I != end() && "BB is not in DominanceFrontier!");
     69   assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
     70   I->second.erase(Node);
     71 }
     72 
     73 template <class BlockT, bool IsPostDom>
     74 bool DominanceFrontierBase<BlockT, IsPostDom>::compareDomSet(
     75     DomSetType &DS1, const DomSetType &DS2) const {
     76   std::set<BlockT *> tmpSet;
     77   for (BlockT *BB : DS2)
     78     tmpSet.insert(BB);
     79 
     80   for (typename DomSetType::const_iterator I = DS1.begin(), E = DS1.end();
     81        I != E;) {
     82     BlockT *Node = *I++;
     83 
     84     if (tmpSet.erase(Node) == 0)
     85       // Node is in DS1 but tnot in DS2.
     86       return true;
     87   }
     88 
     89   if (!tmpSet.empty()) {
     90     // There are nodes that are in DS2 but not in DS1.
     91     return true;
     92   }
     93 
     94   // DS1 and DS2 matches.
     95   return false;
     96 }
     97 
     98 template <class BlockT, bool IsPostDom>
     99 bool DominanceFrontierBase<BlockT, IsPostDom>::compare(
    100     DominanceFrontierBase<BlockT, IsPostDom> &Other) const {
    101   DomSetMapType tmpFrontiers;
    102   for (typename DomSetMapType::const_iterator I = Other.begin(),
    103                                               E = Other.end();
    104        I != E; ++I)
    105     tmpFrontiers.insert(std::make_pair(I->first, I->second));
    106 
    107   for (typename DomSetMapType::iterator I = tmpFrontiers.begin(),
    108                                         E = tmpFrontiers.end();
    109        I != E;) {
    110     BlockT *Node = I->first;
    111     const_iterator DFI = find(Node);
    112     if (DFI == end())
    113       return true;
    114 
    115     if (compareDomSet(I->second, DFI->second))
    116       return true;
    117 
    118     ++I;
    119     tmpFrontiers.erase(Node);
    120   }
    121 
    122   if (!tmpFrontiers.empty())
    123     return true;
    124 
    125   return false;
    126 }
    127 
    128 template <class BlockT, bool IsPostDom>
    129 void DominanceFrontierBase<BlockT, IsPostDom>::print(raw_ostream &OS) const {
    130   for (const_iterator I = begin(), E = end(); I != E; ++I) {
    131     OS << "  DomFrontier for BB ";
    132     if (I->first)
    133       I->first->printAsOperand(OS, false);
    134     else
    135       OS << " <<exit node>>";
    136     OS << " is:\t";
    137 
    138     const std::set<BlockT *> &BBs = I->second;
    139 
    140     for (const BlockT *BB : BBs) {
    141       OS << ' ';
    142       if (BB)
    143         BB->printAsOperand(OS, false);
    144       else
    145         OS << "<<exit node>>";
    146     }
    147     OS << '\n';
    148   }
    149 }
    150 
    151 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    152 template <class BlockT, bool IsPostDom>
    153 void DominanceFrontierBase<BlockT, IsPostDom>::dump() const {
    154   print(dbgs());
    155 }
    156 #endif
    157 
    158 template <class BlockT>
    159 const typename ForwardDominanceFrontierBase<BlockT>::DomSetType &
    160 ForwardDominanceFrontierBase<BlockT>::calculate(const DomTreeT &DT,
    161                                                 const DomTreeNodeT *Node) {
    162   BlockT *BB = Node->getBlock();
    163   DomSetType *Result = nullptr;
    164 
    165   std::vector<DFCalculateWorkObject<BlockT>> workList;
    166   SmallPtrSet<BlockT *, 32> visited;
    167 
    168   workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr));
    169   do {
    170     DFCalculateWorkObject<BlockT> *currentW = &workList.back();
    171     assert(currentW && "Missing work object.");
    172 
    173     BlockT *currentBB = currentW->currentBB;
    174     BlockT *parentBB = currentW->parentBB;
    175     const DomTreeNodeT *currentNode = currentW->Node;
    176     const DomTreeNodeT *parentNode = currentW->parentNode;
    177     assert(currentBB && "Invalid work object. Missing current Basic Block");
    178     assert(currentNode && "Invalid work object. Missing current Node");
    179     DomSetType &S = this->Frontiers[currentBB];
    180 
    181     // Visit each block only once.
    182     if (visited.insert(currentBB).second) {
    183       // Loop over CFG successors to calculate DFlocal[currentNode]
    184       for (const auto Succ : children<BlockT *>(currentBB)) {
    185         // Does Node immediately dominate this successor?
    186         if (DT[Succ]->getIDom() != currentNode)
    187           S.insert(Succ);
    188       }
    189     }
    190 
    191     // At this point, S is DFlocal.  Now we union in DFup's of our children...
    192     // Loop through and visit the nodes that Node immediately dominates (Node's
    193     // children in the IDomTree)
    194     bool visitChild = false;
    195     for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(),
    196                                                NE = currentNode->end();
    197          NI != NE; ++NI) {
    198       DomTreeNodeT *IDominee = *NI;
    199       BlockT *childBB = IDominee->getBlock();
    200       if (visited.count(childBB) == 0) {
    201         workList.push_back(DFCalculateWorkObject<BlockT>(
    202             childBB, currentBB, IDominee, currentNode));
    203         visitChild = true;
    204       }
    205     }
    206 
    207     // If all children are visited or there is any child then pop this block
    208     // from the workList.
    209     if (!visitChild) {
    210       if (!parentBB) {
    211         Result = &S;
    212         break;
    213       }
    214 
    215       typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
    216       DomSetType &parentSet = this->Frontiers[parentBB];
    217       for (; CDFI != CDFE; ++CDFI) {
    218         if (!DT.properlyDominates(parentNode, DT[*CDFI]))
    219           parentSet.insert(*CDFI);
    220       }
    221       workList.pop_back();
    222     }
    223 
    224   } while (!workList.empty());
    225 
    226   return *Result;
    227 }
    228 
    229 } // end namespace llvm
    230 
    231 #endif // LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
    232