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