//===- Dominance.h - Dominator analysis for regions -------------*- 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
//
//===----------------------------------------------------------------------===//
//
// The DominanceInfo and PostDominanceInfo class provide routines for performimg
// simple dominance checks, and expose dominator trees for advanced clients.
// These classes provide fully region-aware functionality, lazily constructing
// dominator information for any multi-block regions that need it.
//
// For more information about the theory behind dominance in graphs algorithms,
// see: https://en.wikipedia.org/wiki/Dominator_(graph_theory)
//
//===----------------------------------------------------------------------===//

#ifndef MLIR_IR_DOMINANCE_H
#define MLIR_IR_DOMINANCE_H

#include "mlir/IR/RegionGraphTraits.h"
#include "llvm/Support/GenericDomTree.h"

extern template class llvm::DominatorTreeBase<mlir::Block, false>;
extern template class llvm::DominatorTreeBase<mlir::Block, true>;

namespace mlir {
using DominanceInfoNode = llvm::DomTreeNodeBase<Block>;
class Operation;

namespace detail {
template <bool IsPostDom>
class DominanceInfoBase {
  using DomTree = llvm::DominatorTreeBase<Block, IsPostDom>;

public:
  DominanceInfoBase(Operation *op = nullptr) {}
  DominanceInfoBase(DominanceInfoBase &&) = default;
  DominanceInfoBase &operator=(DominanceInfoBase &&) = default;
  ~DominanceInfoBase();

  DominanceInfoBase(const DominanceInfoBase &) = delete;
  DominanceInfoBase &operator=(const DominanceInfoBase &) = delete;

  /// Invalidate dominance info. This can be used by clients that make major
  /// changes to the CFG and don't have a good way to update it.
  void invalidate() { dominanceInfos.clear(); }
  void invalidate(Region *region) { dominanceInfos.erase(region); }

  /// Finds the nearest common dominator block for the two given blocks a
  /// and b. If no common dominator can be found, this function will return
  /// nullptr.
  Block *findNearestCommonDominator(Block *a, Block *b) const;

  /// Get the root dominance node of the given region. Note that this operation
  /// is only defined for multi-block regions!
  DominanceInfoNode *getRootNode(Region *region) {
    auto domInfo = getDominanceInfo(region, /*needsDomTree*/ true).getPointer();
    assert(domInfo && "Region isn't multiblock");
    return domInfo->getRootNode();
  }

  /// Return the dominance node from the Region containing block A. This only
  /// works for multi-block regions.
  DominanceInfoNode *getNode(Block *a) {
    return getDomTree(a->getParent()).getNode(a);
  }

  /// Return true if the specified block is reachable from the entry
  /// block of its region.
  bool isReachableFromEntry(Block *a) const;

  /// Return true if operations in the specified block are known to obey SSA
  /// dominance requirements. False if the block is a graph region or unknown.
  bool hasSSADominance(Block *block) const {
    return hasSSADominance(block->getParent());
  }
  /// Return true if operations in the specified block are known to obey SSA
  /// dominance requirements. False if the block is a graph region or unknown.
  bool hasSSADominance(Region *region) const {
    return getDominanceInfo(region, /*needsDomTree=*/false).getInt();
  }

  DomTree &getDomTree(Region *region) const {
    assert(!region->hasOneBlock() &&
           "Can't get DomTree for single block regions");
    return *getDominanceInfo(region, /*needsDomTree=*/true).getPointer();
  }

protected:
  using super = DominanceInfoBase<IsPostDom>;

  /// Return the dom tree and "hasSSADominance" bit for the given region. The
  /// DomTree will be null for single-block regions. This lazily constructs the
  /// DomTree on demand when needsDomTree=true.
  llvm::PointerIntPair<DomTree *, 1, bool>
  getDominanceInfo(Region *region, bool needsDomTree) const;

  /// Return true if the specified block A properly dominates block B.
  bool properlyDominates(Block *a, Block *b) const;

  /// A mapping of regions to their base dominator tree and a cached
  /// "hasSSADominance" bit. This map does not contain dominator trees for
  /// single block CFG regions, but we do want to cache the "hasSSADominance"
  /// bit for them. We may also not have computed the DomTree yet. In either
  /// case, the DomTree is just null.
  ///
  mutable DenseMap<Region *, llvm::PointerIntPair<DomTree *, 1, bool>>
      dominanceInfos;
};
} // end namespace detail

/// A class for computing basic dominance information. Note that this
/// class is aware of different types of regions and returns a
/// region-kind specific concept of dominance. See RegionKindInterface.
class DominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/false> {
public:
  using super::super;

  /// Return true if operation A properly dominates operation B, i.e. if A and B
  /// are in the same block and A properly dominates B within the block, or if
  /// the block that contains A properly dominates the block that contains B. In
  /// an SSACFG region, Operation A dominates Operation B in the same block if A
  /// preceeds B. In a Graph region, all operations in a block dominate all
  /// other operations in the same block.
  ///
  /// The `enclosingOpOk` flag says whether we should return true if the B op
  /// is enclosed by a region on A.
  bool properlyDominates(Operation *a, Operation *b,
                         bool enclosingOpOk = true) const {
    return properlyDominatesImpl(a, b, enclosingOpOk);
  }

  /// Return true if operation A dominates operation B, i.e. if A and B are the
  /// same operation or A properly dominates B.
  bool dominates(Operation *a, Operation *b) const {
    return a == b || properlyDominates(a, b);
  }

  /// Return true if the `a` value properly dominates operation `b`, i.e if the
  /// operation that defines `a` properlyDominates `b` and the operation that
  /// defines `a` does not contain `b`.
  bool properlyDominates(Value a, Operation *b) const;

  /// Return true if the `a` value dominates operation `b`.
  bool dominates(Value a, Operation *b) const {
    return (Operation *)a.getDefiningOp() == b || properlyDominates(a, b);
  }

  /// Return true if the specified block A dominates block B, i.e. if block A
  /// and block B are the same block or block A properly dominates block B.
  bool dominates(Block *a, Block *b) const {
    return a == b || properlyDominates(a, b);
  }

  /// Return true if the specified block A properly dominates block B, i.e.: if
  /// block A contains block B, or if the region which contains block A also
  /// contains block B or some parent of block B and block A dominates that
  /// block in that kind of region. In an SSACFG region, block A dominates
  /// block B if all control flow paths from the entry block to block B flow
  /// through block A. In a Graph region, all blocks dominate all other blocks.
  bool properlyDominates(Block *a, Block *b) const {
    return super::properlyDominates(a, b);
  }

private:
  // Return true if operation A properly dominates operation B.  The
  /// 'enclosingOpOk' flag says whether we should return true if the b op is
  /// enclosed by a region on 'A'.
  bool properlyDominatesImpl(Operation *a, Operation *b,
                             bool enclosingOpOk) const;
};

/// A class for computing basic postdominance information.
class PostDominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/true> {
public:
  using super::super;

  /// Return true if operation A properly postdominates operation B.
  bool properlyPostDominates(Operation *a, Operation *b);

  /// Return true if operation A postdominates operation B.
  bool postDominates(Operation *a, Operation *b) {
    return a == b || properlyPostDominates(a, b);
  }

  /// Return true if the specified block A properly postdominates block B.
  bool properlyPostDominates(Block *a, Block *b) {
    return super::properlyDominates(a, b);
  }

  /// Return true if the specified block A postdominates block B.
  bool postDominates(Block *a, Block *b) {
    return a == b || properlyPostDominates(a, b);
  }
};

} //  end namespace mlir

namespace llvm {

/// DominatorTree GraphTraits specialization so the DominatorTree can be
/// iterated by generic graph iterators.
template <>
struct GraphTraits<mlir::DominanceInfoNode *> {
  using ChildIteratorType = mlir::DominanceInfoNode::const_iterator;
  using NodeRef = mlir::DominanceInfoNode *;

  static NodeRef getEntryNode(NodeRef N) { return N; }
  static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
  static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
};

template <>
struct GraphTraits<const mlir::DominanceInfoNode *> {
  using ChildIteratorType = mlir::DominanceInfoNode::const_iterator;
  using NodeRef = const mlir::DominanceInfoNode *;

  static NodeRef getEntryNode(NodeRef N) { return N; }
  static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
  static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
};

} // end namespace llvm
#endif