include/llvm/Analysis/IteratedDominanceFrontier.h

   1 //===- IteratedDominanceFrontier.h - Calculate IDF --------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef LLVM_ANALYSIS_IDF_H
  10 #define LLVM_ANALYSIS_IDF_H
  11
  12 #include "llvm/IR/CFGDiff.h"
  13 #include "llvm/Support/GenericIteratedDominanceFrontier.h"
  14
  15 namespace llvm {
  16
  17 class BasicBlock;
  18
  19 namespace IDFCalculatorDetail {
  20
  21 /// Specialization for BasicBlock for the optional use of GraphDiff.
  22 template <bool IsPostDom> struct ChildrenGetterTy<BasicBlock, IsPostDom> {
  23   using NodeRef = BasicBlock *;
  24   using ChildrenTy = SmallVector<BasicBlock *, 8>;
  25
  26   ChildrenGetterTy() = default;
  27   ChildrenGetterTy(const GraphDiff<BasicBlock *, IsPostDom> *GD) : GD(GD) {
  28     assert(GD);
  29   }
  30
  31   ChildrenTy get(const NodeRef &N);
  32
  33   const GraphDiff<BasicBlock *, IsPostDom> *GD = nullptr;
  34 };
  35
  36 } // end of namespace IDFCalculatorDetail
  37
  38 template <bool IsPostDom>
  39 class IDFCalculator final : public IDFCalculatorBase<BasicBlock, IsPostDom> {
  40 public:
  41   using IDFCalculatorBase =
  42       typename llvm::IDFCalculatorBase<BasicBlock, IsPostDom>;
  43   using ChildrenGetterTy = typename IDFCalculatorBase::ChildrenGetterTy;
  44
  45   IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT)
  46       : IDFCalculatorBase(DT) {}
  47
  48   IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT,
  49                 const GraphDiff<BasicBlock *, IsPostDom> *GD)
  50       : IDFCalculatorBase(DT, ChildrenGetterTy(GD)) {
  51     assert(GD);
  52   }
  53 };
  54
  55 using ForwardIDFCalculator = IDFCalculator<false>;
  56 using ReverseIDFCalculator = IDFCalculator<true>;
  57
  58 //===----------------------------------------------------------------------===//
  59 // Implementation.
  60 //===----------------------------------------------------------------------===//
  61
  62 namespace IDFCalculatorDetail {
  63
  64 template <bool IsPostDom>
  65 typename ChildrenGetterTy<BasicBlock, IsPostDom>::ChildrenTy
  66 ChildrenGetterTy<BasicBlock, IsPostDom>::get(const NodeRef &N) {
  67
  68   using OrderedNodeTy =
  69       typename IDFCalculatorBase<BasicBlock, IsPostDom>::OrderedNodeTy;
  70
  71   if (!GD) {
  72     auto Children = children<OrderedNodeTy>(N);
  73     return {Children.begin(), Children.end()};
  74   }
  75
  76   using SnapShotBBPairTy =
  77       std::pair<const GraphDiff<BasicBlock *, IsPostDom> *, OrderedNodeTy>;
  78
  79   ChildrenTy Ret;
  80   for (const auto &SnapShotBBPair : children<SnapShotBBPairTy>({GD, N}))
  81     Ret.emplace_back(SnapShotBBPair.second);
  82   return Ret;
  83 }
  84
  85 } // end of namespace IDFCalculatorDetail
  86
  87 } // end of namespace llvm
  88
  89 #endif