include/llvm/Analysis/DominanceFrontierImpl.h

   1 //===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This is the generic implementation of the DominanceFrontier class, which
  10 // calculate and holds the dominance frontier for a function for.
  11 //
  12 // This should be considered deprecated, don't add any more uses of this data
  13 // structure.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #ifndef LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
  18 #define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
  19
  20 #include "llvm/ADT/GraphTraits.h"
  21 #include "llvm/ADT/SmallPtrSet.h"
  22 #include "llvm/Analysis/DominanceFrontier.h"
  23 #include "llvm/Config/llvm-config.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