Analysis/Analyses/Dominators.h

0001 //- Dominators.h - Implementation of dominators tree for Clang CFG -*- 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 file implements the dominators tree functionality for Clang CFGs.
0010 //
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
0014 #define LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
0015
0016 #include "clang/Analysis/AnalysisDeclContext.h"
0017 #include "clang/Analysis/CFG.h"
0018 #include "llvm/ADT/DepthFirstIterator.h"
0019 #include "llvm/ADT/GraphTraits.h"
0020 #include "llvm/ADT/iterator.h"
0021 #include "llvm/Support/GenericIteratedDominanceFrontier.h"
0022 #include "llvm/Support/GenericDomTree.h"
0023 #include "llvm/Support/GenericDomTreeConstruction.h"
0024 #include "llvm/Support/raw_ostream.h"
0025
0026 // FIXME: There is no good reason for the domtree to require a print method
0027 // which accepts an LLVM Module, so remove this (and the method's argument that
0028 // needs it) when that is fixed.
0029
0030 namespace llvm {
0031
0032 class Module;
0033
0034 } // namespace llvm
0035
0036 namespace clang {
0037
0038 using DomTreeNode = llvm::DomTreeNodeBase<CFGBlock>;
0039
0040 /// Dominator tree builder for Clang's CFG based on llvm::DominatorTreeBase.
0041 template <bool IsPostDom>
0042 class CFGDominatorTreeImpl : public ManagedAnalysis {
0043   virtual void anchor();
0044
0045 public:
0046   using DominatorTreeBase = llvm::DominatorTreeBase<CFGBlock, IsPostDom>;
0047
0048   CFGDominatorTreeImpl() = default;
0049
0050   CFGDominatorTreeImpl(CFG *cfg) {
0051     buildDominatorTree(cfg);
0052   }
0053
0054   ~CFGDominatorTreeImpl() override = default;
0055
0056   DominatorTreeBase &getBase() { return DT; }
0057
0058   CFG *getCFG() { return cfg; }
0059
0060   /// \returns the root CFGBlock of the dominators tree.
0061   CFGBlock *getRoot() const {
0062     return DT.getRoot();
0063   }
0064
0065   /// \returns the root DomTreeNode, which is the wrapper for CFGBlock.
0066   DomTreeNode *getRootNode() {
0067     return DT.getRootNode();
0068   }
0069
0070   /// Compares two dominator trees.
0071   /// \returns false if the other dominator tree matches this dominator tree,
0072   /// false otherwise.
0073   bool compare(CFGDominatorTreeImpl &Other) const {
0074     DomTreeNode *R = getRootNode();
0075     DomTreeNode *OtherR = Other.getRootNode();
0076
0077     if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
0078       return true;
0079
0080     if (DT.compare(Other.getBase()))
0081       return true;
0082
0083     return false;
0084   }
0085
0086   /// Builds the dominator tree for a given CFG.
0087   void buildDominatorTree(CFG *cfg) {
0088     assert(cfg);
0089     this->cfg = cfg;
0090     DT.recalculate(*cfg);
0091   }
0092
0093   /// Dumps immediate dominators for each block.
0094   void dump() {
0095     llvm::errs() << "Immediate " << (IsPostDom ? "post " : "")
0096                  << "dominance tree (Node#,IDom#):\n";
0097     for (CFG::const_iterator I = cfg->begin(),
0098         E = cfg->end(); I != E; ++I) {
0099
0100       assert(*I &&
0101              "LLVM's Dominator tree builder uses nullpointers to signify the "
0102              "virtual root!");
0103
0104       DomTreeNode *IDom = DT.getNode(*I)->getIDom();
0105       if (IDom && IDom->getBlock())
0106         llvm::errs() << "(" << (*I)->getBlockID()
0107                      << ","
0108                      << IDom->getBlock()->getBlockID()
0109                      << ")\n";
0110       else {
0111         bool IsEntryBlock = *I == &(*I)->getParent()->getEntry();
0112         bool IsExitBlock = *I == &(*I)->getParent()->getExit();
0113
0114         bool IsDomTreeRoot = !IDom && !IsPostDom && IsEntryBlock;
0115         bool IsPostDomTreeRoot =
0116             IDom && !IDom->getBlock() && IsPostDom && IsExitBlock;
0117
0118         assert((IsDomTreeRoot || IsPostDomTreeRoot) &&
0119                "If the immediate dominator node is nullptr, the CFG block "
0120                "should be the exit point (since it's the root of the dominator "
0121                "tree), or if the CFG block it refers to is a nullpointer, it "
0122                "must be the entry block (since it's the root of the post "
0123                "dominator tree)");
0124
0125         (void)IsDomTreeRoot;
0126         (void)IsPostDomTreeRoot;
0127
0128         llvm::errs() << "(" << (*I)->getBlockID()
0129                      << "," << (*I)->getBlockID() << ")\n";
0130       }
0131     }
0132   }
0133
0134   /// Tests whether \p A dominates \p B.
0135   /// Note a block always dominates itself.
0136   bool dominates(const CFGBlock *A, const CFGBlock *B) const {
0137     return DT.dominates(A, B);
0138   }
0139
0140   /// Tests whether \p A properly dominates \p B.
0141   /// \returns false if \p A is the same block as \p B, otherwise whether A
0142   /// dominates B.
0143   bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const {
0144     return DT.properlyDominates(A, B);
0145   }
0146
0147   /// \returns the nearest common dominator CFG block for CFG block \p A and \p
0148   /// B. If there is no such block then return NULL.
0149   CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) {
0150     return DT.findNearestCommonDominator(A, B);
0151   }
0152
0153   const CFGBlock *findNearestCommonDominator(const CFGBlock *A,
0154                                              const CFGBlock *B) {
0155     return DT.findNearestCommonDominator(A, B);
0156   }
0157
0158   /// Update the dominator tree information when a node's immediate dominator
0159   /// changes.
0160   void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
0161     DT.changeImmediateDominator(N, NewIDom);
0162   }
0163
0164   /// Tests whether \p A is reachable from the entry block.
0165   bool isReachableFromEntry(const CFGBlock *A) {
0166     return DT.isReachableFromEntry(A);
0167   }
0168
0169   /// Releases the memory held by the dominator tree.
0170   virtual void releaseMemory() { DT.reset(); }
0171
0172   /// Converts the dominator tree to human readable form.
0173   virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
0174     DT.print(OS);
0175   }
0176
0177 private:
0178   CFG *cfg;
0179   DominatorTreeBase DT;
0180 };
0181
0182 using CFGDomTree = CFGDominatorTreeImpl</*IsPostDom*/ false>;
0183 using CFGPostDomTree = CFGDominatorTreeImpl</*IsPostDom*/ true>;
0184
0185 template<> void CFGDominatorTreeImpl<true>::anchor();
0186 template<> void CFGDominatorTreeImpl<false>::anchor();
0187
0188 } // end of namespace clang
0189
0190 namespace llvm {
0191 namespace IDFCalculatorDetail {
0192
0193 /// Specialize ChildrenGetterTy to skip nullpointer successors.
0194 template <bool IsPostDom>
0195 struct ChildrenGetterTy<clang::CFGBlock, IsPostDom> {
0196   using NodeRef = typename GraphTraits<clang::CFGBlock *>::NodeRef;
0197   using ChildrenTy = SmallVector<NodeRef, 8>;
0198
0199   ChildrenTy get(const NodeRef &N) {
0200     using OrderedNodeTy =
0201         typename IDFCalculatorBase<clang::CFGBlock, IsPostDom>::OrderedNodeTy;
0202
0203     auto Children = children<OrderedNodeTy>(N);
0204     ChildrenTy Ret{Children.begin(), Children.end()};
0205     llvm::erase(Ret, nullptr);
0206     return Ret;
0207   }
0208 };
0209
0210 } // end of namespace IDFCalculatorDetail
0211 } // end of namespace llvm
0212
0213 namespace clang {
0214
0215 class ControlDependencyCalculator : public ManagedAnalysis {
0216   using IDFCalculator = llvm::IDFCalculatorBase<CFGBlock, /*IsPostDom=*/true>;
0217   using CFGBlockVector = llvm::SmallVector<CFGBlock *, 4>;
0218   using CFGBlockSet = llvm::SmallPtrSet<CFGBlock *, 4>;
0219
0220   CFGPostDomTree PostDomTree;
0221   IDFCalculator IDFCalc;
0222
0223   llvm::DenseMap<CFGBlock *, CFGBlockVector> ControlDepenencyMap;
0224
0225 public:
0226   ControlDependencyCalculator(CFG *cfg)
0227     : PostDomTree(cfg), IDFCalc(PostDomTree.getBase()) {}
0228
0229   const CFGPostDomTree &getCFGPostDomTree() const { return PostDomTree; }
0230
0231   // Lazily retrieves the set of control dependencies to \p A.
0232   const CFGBlockVector &getControlDependencies(CFGBlock *A) {
0233     auto It = ControlDepenencyMap.find(A);
0234     if (It == ControlDepenencyMap.end()) {
0235       CFGBlockSet DefiningBlock = {A};
0236       IDFCalc.setDefiningBlocks(DefiningBlock);
0237
0238       CFGBlockVector ControlDependencies;
0239       IDFCalc.calculate(ControlDependencies);
0240
0241       It = ControlDepenencyMap.insert({A, ControlDependencies}).first;
0242     }
0243
0244     assert(It != ControlDepenencyMap.end());
0245     return It->second;
0246   }
0247
0248   /// Whether \p A is control dependent on \p B.
0249   bool isControlDependent(CFGBlock *A, CFGBlock *B) {
0250     return llvm::is_contained(getControlDependencies(A), B);
0251   }
0252
0253   // Dumps immediate control dependencies for each block.
0254   LLVM_DUMP_METHOD void dump() {
0255     CFG *cfg = PostDomTree.getCFG();
0256     llvm::errs() << "Control dependencies (Node#,Dependency#):\n";
0257     for (CFGBlock *BB : *cfg) {
0258
0259       assert(BB &&
0260              "LLVM's Dominator tree builder uses nullpointers to signify the "
0261              "virtual root!");
0262
0263       for (CFGBlock *isControlDependency : getControlDependencies(BB))
0264         llvm::errs() << "(" << BB->getBlockID()
0265                      << ","
0266                      << isControlDependency->getBlockID()
0267                      << ")\n";
0268     }
0269   }
0270 };
0271
0272 } // namespace clang
0273
0274 namespace llvm {
0275
0276 //===-------------------------------------
0277 /// DominatorTree GraphTraits specialization so the DominatorTree can be
0278 /// iterable by generic graph iterators.
0279 ///
0280 template <> struct GraphTraits<clang::DomTreeNode *> {
0281   using NodeRef = ::clang::DomTreeNode *;
0282   using ChildIteratorType = ::clang::DomTreeNode::const_iterator;
0283
0284   static NodeRef getEntryNode(NodeRef N) { return N; }
0285   static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
0286   static ChildIteratorType child_end(NodeRef N) { return N->end(); }
0287
0288   using nodes_iterator =
0289       llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;
0290
0291   static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
0292     return nodes_iterator(df_begin(getEntryNode(N)));
0293   }
0294
0295   static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
0296     return nodes_iterator(df_end(getEntryNode(N)));
0297   }
0298 };
0299
0300 template <> struct GraphTraits<clang::CFGDomTree *>
0301     : public GraphTraits<clang::DomTreeNode *> {
0302   static NodeRef getEntryNode(clang::CFGDomTree *DT) {
0303     return DT->getRootNode();
0304   }
0305
0306   static nodes_iterator nodes_begin(clang::CFGDomTree *N) {
0307     return nodes_iterator(df_begin(getEntryNode(N)));
0308   }
0309
0310   static nodes_iterator nodes_end(clang::CFGDomTree *N) {
0311     return nodes_iterator(df_end(getEntryNode(N)));
0312   }
0313 };
0314
0315 } // namespace llvm
0316
0317 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H