Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//- Dominators.h - Implementation of dominators tree for Clang CFG -*- C++ -*-//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// This file implements the dominators tree functionality for Clang CFGs.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H

#define LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H

#include "clang/Analysis/AnalysisDeclContext.h"

#include "clang/Analysis/CFG.h"

#include "llvm/ADT/DepthFirstIterator.h"

#include "llvm/ADT/GraphTraits.h"

#include "llvm/ADT/iterator.h"

#include "llvm/Support/GenericIteratedDominanceFrontier.h"

#include "llvm/Support/GenericDomTree.h"

#include "llvm/Support/GenericDomTreeConstruction.h"

#include "llvm/Support/raw_ostream.h"

// FIXME: There is no good reason for the domtree to require a print method

// which accepts an LLVM Module, so remove this (and the method's argument that

// needs it) when that is fixed.

namespace llvm {

class Module;

} // namespace llvm

namespace clang {

using DomTreeNode = llvm::DomTreeNodeBase<CFGBlock>;

/// Dominator tree builder for Clang's CFG based on llvm::DominatorTreeBase.

template <bool IsPostDom>

class CFGDominatorTreeImpl : public ManagedAnalysis {

  virtual void anchor();

public:

  using DominatorTreeBase = llvm::DominatorTreeBase<CFGBlock, IsPostDom>;

  CFGDominatorTreeImpl() = default;

  CFGDominatorTreeImpl(CFG *cfg) {

    buildDominatorTree(cfg);

  }

  ~CFGDominatorTreeImpl() override = default;

  DominatorTreeBase &getBase() { return DT; }

  CFG *getCFG() { return cfg; }

  /// \returns the root CFGBlock of the dominators tree.

  CFGBlock *getRoot() const {

    return DT.getRoot();

  }

  /// \returns the root DomTreeNode, which is the wrapper for CFGBlock.

  DomTreeNode *getRootNode() {

    return DT.getRootNode();

  }

  /// Compares two dominator trees.

  /// \returns false if the other dominator tree matches this dominator tree,

  /// false otherwise.

  bool compare(CFGDominatorTreeImpl &Other) const {

    DomTreeNode *R = getRootNode();

    DomTreeNode *OtherR = Other.getRootNode();

    if (!R || !OtherR || R->getBlock() != OtherR->getBlock())

      return true;

    if (DT.compare(Other.getBase()))

      return true;

    return false;

  }

  /// Builds the dominator tree for a given CFG.

  void buildDominatorTree(CFG *cfg) {

    assert(cfg);

    this->cfg = cfg;

    DT.recalculate(*cfg);

  }

  /// Dumps immediate dominators for each block.

  void dump() {

    llvm::errs() << "Immediate " << (IsPostDom ? "post " : "")

                 << "dominance tree (Node#,IDom#):\n";

    for (CFG::const_iterator I = cfg->begin(),

        E = cfg->end(); I != E; ++I) {

      assert(*I &&

             "LLVM's Dominator tree builder uses nullpointers to signify the "

             "virtual root!");

      DomTreeNode *IDom = DT.getNode(*I)->getIDom();

      if (IDom && IDom->getBlock())

        llvm::errs() << "(" << (*I)->getBlockID()

                     << ","

                     << IDom->getBlock()->getBlockID()

                     << ")\n";

      else {

        bool IsEntryBlock = *I == &(*I)->getParent()->getEntry();

        bool IsExitBlock = *I == &(*I)->getParent()->getExit();

        bool IsDomTreeRoot = !IDom && !IsPostDom && IsEntryBlock;

        bool IsPostDomTreeRoot =

            IDom && !IDom->getBlock() && IsPostDom && IsExitBlock;

        assert((IsDomTreeRoot || IsPostDomTreeRoot) &&

               "If the immediate dominator node is nullptr, the CFG block "

               "should be the exit point (since it's the root of the dominator "

               "tree), or if the CFG block it refers to is a nullpointer, it "

               "must be the entry block (since it's the root of the post "

               "dominator tree)");

        (void)IsDomTreeRoot;

        (void)IsPostDomTreeRoot;

        llvm::errs() << "(" << (*I)->getBlockID()

                     << "," << (*I)->getBlockID() << ")\n";

      }

    }

  }

  /// Tests whether \p A dominates \p B.

  /// Note a block always dominates itself.

  bool dominates(const CFGBlock *A, const CFGBlock *B) const {

    return DT.dominates(A, B);

  }

  /// Tests whether \p A properly dominates \p B.

  /// \returns false if \p A is the same block as \p B, otherwise whether A

  /// dominates B.

  bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const {

    return DT.properlyDominates(A, B);

  }

  /// \returns the nearest common dominator CFG block for CFG block \p A and \p

  /// B. If there is no such block then return NULL.

  CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) {

    return DT.findNearestCommonDominator(A, B);

  }

  const CFGBlock *findNearestCommonDominator(const CFGBlock *A,

                                             const CFGBlock *B) {

    return DT.findNearestCommonDominator(A, B);

  }

  /// Update the dominator tree information when a node's immediate dominator

  /// changes.

  void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {

    DT.changeImmediateDominator(N, NewIDom);

  }

  /// Tests whether \p A is reachable from the entry block.

  bool isReachableFromEntry(const CFGBlock *A) {

    return DT.isReachableFromEntry(A);

  }

  /// Releases the memory held by the dominator tree.

  virtual void releaseMemory() { DT.reset(); }

  /// Converts the dominator tree to human readable form.

  virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {

    DT.print(OS);

  }

private:

  CFG *cfg;

  DominatorTreeBase DT;

};

using CFGDomTree = CFGDominatorTreeImpl</*IsPostDom*/ false>;

using CFGPostDomTree = CFGDominatorTreeImpl</*IsPostDom*/ true>;

template<> void CFGDominatorTreeImpl<true>::anchor();

template<> void CFGDominatorTreeImpl<false>::anchor();

} // end of namespace clang

namespace llvm {

namespace IDFCalculatorDetail {

/// Specialize ChildrenGetterTy to skip nullpointer successors.

template <bool IsPostDom>

struct ChildrenGetterTy<clang::CFGBlock, IsPostDom> {

  using NodeRef = typename GraphTraits<clang::CFGBlock *>::NodeRef;

  using ChildrenTy = SmallVector<NodeRef, 8>;

  ChildrenTy get(const NodeRef &N) {

    using OrderedNodeTy =

        typename IDFCalculatorBase<clang::CFGBlock, IsPostDom>::OrderedNodeTy;

    auto Children = children<OrderedNodeTy>(N);

    ChildrenTy Ret{Children.begin(), Children.end()};

    llvm::erase_value(Ret, nullptr);

    return Ret;

  }

};

} // end of namespace IDFCalculatorDetail

} // end of namespace llvm

namespace clang {

class ControlDependencyCalculator : public ManagedAnalysis {

  using IDFCalculator = llvm::IDFCalculatorBase<CFGBlock, /*IsPostDom=*/true>;

  using CFGBlockVector = llvm::SmallVector<CFGBlock *, 4>;

  using CFGBlockSet = llvm::SmallPtrSet<CFGBlock *, 4>;

  CFGPostDomTree PostDomTree;

  IDFCalculator IDFCalc;

  llvm::DenseMap<CFGBlock *, CFGBlockVector> ControlDepenencyMap;

public:

  ControlDependencyCalculator(CFG *cfg)

    : PostDomTree(cfg), IDFCalc(PostDomTree.getBase()) {}

  const CFGPostDomTree &getCFGPostDomTree() const { return PostDomTree; }

  // Lazily retrieves the set of control dependencies to \p A.

  const CFGBlockVector &getControlDependencies(CFGBlock *A) {

    auto It = ControlDepenencyMap.find(A);

    if (It == ControlDepenencyMap.end()) {

      CFGBlockSet DefiningBlock = {A};

      IDFCalc.setDefiningBlocks(DefiningBlock);

      CFGBlockVector ControlDependencies;

      IDFCalc.calculate(ControlDependencies);

      It = ControlDepenencyMap.insert({A, ControlDependencies}).first;

    }

    assert(It != ControlDepenencyMap.end());

    return It->second;

  }

  /// Whether \p A is control dependent on \p B.

  bool isControlDependent(CFGBlock *A, CFGBlock *B) {

    return llvm::is_contained(getControlDependencies(A), B);

  }

  // Dumps immediate control dependencies for each block.

  LLVM_DUMP_METHOD void dump() {

    CFG *cfg = PostDomTree.getCFG();

    llvm::errs() << "Control dependencies (Node#,Dependency#):\n";

    for (CFGBlock *BB : *cfg) {

      assert(BB &&

             "LLVM's Dominator tree builder uses nullpointers to signify the "

             "virtual root!");

      for (CFGBlock *isControlDependency : getControlDependencies(BB))

        llvm::errs() << "(" << BB->getBlockID()

                     << ","

                     << isControlDependency->getBlockID()

                     << ")\n";

    }

  }

};

} // namespace clang

namespace llvm {

//===-------------------------------------

/// DominatorTree GraphTraits specialization so the DominatorTree can be

/// iterable by generic graph iterators.

///

template <> struct GraphTraits<clang::DomTreeNode *> {

  using NodeRef = ::clang::DomTreeNode *;

  using ChildIteratorType = ::clang::DomTreeNode::const_iterator;

  static NodeRef getEntryNode(NodeRef N) { return N; }

  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }

  static ChildIteratorType child_end(NodeRef N) { return N->end(); }

  using nodes_iterator =

      llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;

  static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {

    return nodes_iterator(df_begin(getEntryNode(N)));

  }

  static nodes_iterator nodes_end(::clang::DomTreeNode *N) {

    return nodes_iterator(df_end(getEntryNode(N)));

  }

};

template <> struct GraphTraits<clang::CFGDomTree *>

    : public GraphTraits<clang::DomTreeNode *> {

  static NodeRef getEntryNode(clang::CFGDomTree *DT) {

    return DT->getRootNode();

  }

  static nodes_iterator nodes_begin(clang::CFGDomTree *N) {

    return nodes_iterator(df_begin(getEntryNode(N)));

  }

  static nodes_iterator nodes_end(clang::CFGDomTree *N) {

    return nodes_iterator(df_end(getEntryNode(N)));

  }

};

} // namespace llvm

#endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H