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