//- 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/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>;

/// Concrete subclass of DominatorTreeBase for Clang
/// This class implements the dominators tree functionality given a Clang CFG.
///
class DominatorTree : public ManagedAnalysis {
  virtual void anchor();

public:
  llvm::DomTreeBase<CFGBlock> *DT;

  DominatorTree() {
    DT = new llvm::DomTreeBase<CFGBlock>();
  }

  ~DominatorTree() override { delete DT; }

  llvm::DomTreeBase<CFGBlock>& getBase() { return *DT; }

  /// This method returns the root CFGBlock of the dominators tree.
  CFGBlock *getRoot() const {
    return DT->getRoot();
  }

  /// This method returns the root DomTreeNode, which is the wrapper
  /// for CFGBlock.
  DomTreeNode *getRootNode() const {
    return DT->getRootNode();
  }

  /// This method compares two dominator trees.
  /// The method returns false if the other dominator tree matches this
  /// dominator tree, otherwise returns true.
  bool compare(DominatorTree &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;
  }

  /// This method builds the dominator tree for a given CFG
  /// The CFG information is passed via AnalysisDeclContext
  void buildDominatorTree(AnalysisDeclContext &AC) {
    cfg = AC.getCFG();
    DT->recalculate(*cfg);
  }

  /// This method dumps immediate dominators for each block,
  /// mainly used for debug purposes.
  void dump() {
    llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n";
    for (CFG::const_iterator I = cfg->begin(),
        E = cfg->end(); I != E; ++I) {
      if(DT->getNode(*I)->getIDom())
        llvm::errs() << "(" << (*I)->getBlockID()
                     << ","
                     << DT->getNode(*I)->getIDom()->getBlock()->getBlockID()
                     << ")\n";
      else llvm::errs() << "(" << (*I)->getBlockID()
                        << "," << (*I)->getBlockID() << ")\n";
    }
  }

  /// This method tests if one CFGBlock dominates the other.
  /// The method return true if A dominates B, false otherwise.
  /// Note a block always dominates itself.
  bool dominates(const CFGBlock *A, const CFGBlock *B) const {
    return DT->dominates(A, B);
  }

  /// This method tests if one CFGBlock properly dominates the other.
  /// The method return true if A properly dominates B, false otherwise.
  bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const {
    return DT->properlyDominates(A, B);
  }

  /// This method finds the nearest common dominator CFG block
  /// for CFG block A and 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);
  }

  /// This method is used to update the dominator
  /// tree information when a node's immediate dominator changes.
  void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) {
    DT->changeImmediateDominator(N, NewIDom);
  }

  /// This method tests if the given CFGBlock can be reachable from root.
  /// Returns true if reachable, false otherwise.
  bool isReachableFromEntry(const CFGBlock *A) {
    return DT->isReachableFromEntry(A);
  }

  /// This method releases the memory held by the dominator tree.
  virtual void releaseMemory() {
    DT->releaseMemory();
  }

  /// This method 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;
};

} // namespace clang

//===-------------------------------------
/// DominatorTree GraphTraits specialization so the DominatorTree can be
/// iterable by generic graph iterators.
///
namespace llvm {

template <> struct GraphTraits< ::clang::DomTreeNode* > {
  using NodeRef = ::clang::DomTreeNode *;
  using ChildIteratorType = ::clang::DomTreeNode::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::DominatorTree* >
    : public GraphTraits< ::clang::DomTreeNode* > {
  static NodeRef getEntryNode(::clang::DominatorTree *DT) {
    return DT->getRootNode();
  }

  static nodes_iterator nodes_begin(::clang::DominatorTree *N) {
    return nodes_iterator(df_begin(getEntryNode(N)));
  }

  static nodes_iterator nodes_end(::clang::DominatorTree *N) {
    return nodes_iterator(df_end(getEntryNode(N)));
  }
};

} // namespace llvm

#endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H