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