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/Support/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   return GD->template getChildren<IsPostDom>(N);
77 }
78 
79 } // end of namespace IDFCalculatorDetail
80 
81 } // end of namespace llvm
82 
83 #endif
84