llvm/Analysis/DominanceFrontierImpl.h

0001 //===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This is the generic implementation of the DominanceFrontier class, which
0010 // calculate and holds the dominance frontier for a function for.
0011 //
0012 // This should be considered deprecated, don't add any more uses of this data
0013 // structure.
0014 //
0015 //===----------------------------------------------------------------------===//
0016
0017 #ifndef LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
0018 #define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
0019
0020 #include "llvm/ADT/SmallPtrSet.h"
0021 #include "llvm/Analysis/DominanceFrontier.h"
0022 #include "llvm/Config/llvm-config.h"
0023 #include "llvm/Support/Debug.h"
0024 #include "llvm/Support/GenericDomTree.h"
0025 #include "llvm/Support/raw_ostream.h"
0026 #include <cassert>
0027 #include <set>
0028 #include <utility>
0029 #include <vector>
0030
0031 namespace llvm {
0032
0033 template <class BlockT>
0034 class DFCalculateWorkObject {
0035 public:
0036   using DomTreeNodeT = DomTreeNodeBase<BlockT>;
0037
0038   DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N,
0039                         const DomTreeNodeT *PN)
0040       : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
0041
0042   BlockT *currentBB;
0043   BlockT *parentBB;
0044   const DomTreeNodeT *Node;
0045   const DomTreeNodeT *parentNode;
0046 };
0047
0048 template <class BlockT, bool IsPostDom>
0049 void DominanceFrontierBase<BlockT, IsPostDom>::print(raw_ostream &OS) const {
0050   for (const_iterator I = begin(), E = end(); I != E; ++I) {
0051     OS << "  DomFrontier for BB ";
0052     if (I->first)
0053       I->first->printAsOperand(OS, false);
0054     else
0055       OS << " <<exit node>>";
0056     OS << " is:\t";
0057
0058     const SetVector<BlockT *> &BBs = I->second;
0059
0060     for (const BlockT *BB : BBs) {
0061       OS << ' ';
0062       if (BB)
0063         BB->printAsOperand(OS, false);
0064       else
0065         OS << "<<exit node>>";
0066     }
0067     OS << '\n';
0068   }
0069 }
0070
0071 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
0072 template <class BlockT, bool IsPostDom>
0073 void DominanceFrontierBase<BlockT, IsPostDom>::dump() const {
0074   print(dbgs());
0075 }
0076 #endif
0077
0078 template <class BlockT>
0079 const typename ForwardDominanceFrontierBase<BlockT>::DomSetType &
0080 ForwardDominanceFrontierBase<BlockT>::calculate(const DomTreeT &DT,
0081                                                 const DomTreeNodeT *Node) {
0082   BlockT *BB = Node->getBlock();
0083   DomSetType *Result = nullptr;
0084
0085   std::vector<DFCalculateWorkObject<BlockT>> workList;
0086   SmallPtrSet<BlockT *, 32> visited;
0087
0088   workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr));
0089   do {
0090     DFCalculateWorkObject<BlockT> *currentW = &workList.back();
0091     assert(currentW && "Missing work object.");
0092
0093     BlockT *currentBB = currentW->currentBB;
0094     BlockT *parentBB = currentW->parentBB;
0095     const DomTreeNodeT *currentNode = currentW->Node;
0096     const DomTreeNodeT *parentNode = currentW->parentNode;
0097     assert(currentBB && "Invalid work object. Missing current Basic Block");
0098     assert(currentNode && "Invalid work object. Missing current Node");
0099     DomSetType &S = this->Frontiers[currentBB];
0100
0101     // Visit each block only once.
0102     if (visited.insert(currentBB).second) {
0103       // Loop over CFG successors to calculate DFlocal[currentNode]
0104       for (const auto Succ : children<BlockT *>(currentBB)) {
0105         // Does Node immediately dominate this successor?
0106         if (DT[Succ]->getIDom() != currentNode)
0107           S.insert(Succ);
0108       }
0109     }
0110
0111     // At this point, S is DFlocal.  Now we union in DFup's of our children...
0112     // Loop through and visit the nodes that Node immediately dominates (Node's
0113     // children in the IDomTree)
0114     bool visitChild = false;
0115     for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(),
0116                                                NE = currentNode->end();
0117          NI != NE; ++NI) {
0118       DomTreeNodeT *IDominee = *NI;
0119       BlockT *childBB = IDominee->getBlock();
0120       if (visited.count(childBB) == 0) {
0121         workList.push_back(DFCalculateWorkObject<BlockT>(
0122             childBB, currentBB, IDominee, currentNode));
0123         visitChild = true;
0124       }
0125     }
0126
0127     // If all children are visited or there is any child then pop this block
0128     // from the workList.
0129     if (!visitChild) {
0130       if (!parentBB) {
0131         Result = &S;
0132         break;
0133       }
0134
0135       typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
0136       DomSetType &parentSet = this->Frontiers[parentBB];
0137       for (; CDFI != CDFE; ++CDFI) {
0138         if (!DT.properlyDominates(parentNode, DT[*CDFI]))
0139           parentSet.insert(*CDFI);
0140       }
0141       workList.pop_back();
0142     }
0143
0144   } while (!workList.empty());
0145
0146   return *Result;
0147 }
0148
0149 } // end namespace llvm
0150
0151 #endif // LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H