llvm-project

1
//===- RegionInfo.cpp - SESE region detection analysis --------------------===//
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
// Detects single entry single exit regions in the control flow graph.
9
//===----------------------------------------------------------------------===//
10

11
#include "llvm/Analysis/RegionInfo.h"
12
#include "llvm/ADT/Statistic.h"
13
#include "llvm/Analysis/DominanceFrontier.h"
14
#include "llvm/InitializePasses.h"
15
#ifndef NDEBUG
16
#include "llvm/Analysis/RegionPrinter.h"
17
#endif
18
#include "llvm/Analysis/RegionInfoImpl.h"
19
#include "llvm/Config/llvm-config.h"
20
#include "llvm/IR/Function.h"
21
#include "llvm/Support/CommandLine.h"
22
#include "llvm/Support/Compiler.h"
23

24
using namespace llvm;
25

26
#define DEBUG_TYPE "region"
27

28
namespace llvm {
29

30
template class RegionBase<RegionTraits<Function>>;
31
template class RegionNodeBase<RegionTraits<Function>>;
32
template class RegionInfoBase<RegionTraits<Function>>;
33

34
} // end namespace llvm
35

36
STATISTIC(numRegions,       "The # of regions");
37
STATISTIC(numSimpleRegions, "The # of simple regions");
38

39
// Always verify if expensive checking is enabled.
40

41
static cl::opt<bool,true>
42
VerifyRegionInfoX(
43
  "verify-region-info",
44
  cl::location(RegionInfoBase<RegionTraits<Function>>::VerifyRegionInfo),
45
  cl::desc("Verify region info (time consuming)"));
46

47
static cl::opt<Region::PrintStyle, true> printStyleX("print-region-style",
48
  cl::location(RegionInfo::printStyle),
49
  cl::Hidden,
50
  cl::desc("style of printing regions"),
51
  cl::values(
52
    clEnumValN(Region::PrintNone, "none",  "print no details"),
53
    clEnumValN(Region::PrintBB, "bb",
54
               "print regions in detail with block_iterator"),
55
    clEnumValN(Region::PrintRN, "rn",
56
               "print regions in detail with element_iterator")));
57

58
//===----------------------------------------------------------------------===//
59
// Region implementation
60
//
61

62
Region::Region(BasicBlock *Entry, BasicBlock *Exit,
63
               RegionInfo* RI,
64
               DominatorTree *DT, Region *Parent) :
65
  RegionBase<RegionTraits<Function>>(Entry, Exit, RI, DT, Parent) {
66

67
}
68

69
Region::~Region() = default;
70

71
//===----------------------------------------------------------------------===//
72
// RegionInfo implementation
73
//
74

75
RegionInfo::RegionInfo() = default;
76

77
RegionInfo::~RegionInfo() = default;
78

79
bool RegionInfo::invalidate(Function &F, const PreservedAnalyses &PA,
80
                            FunctionAnalysisManager::Invalidator &) {
81
  // Check whether the analysis, all analyses on functions, or the function's
82
  // CFG has been preserved.
83
  auto PAC = PA.getChecker<RegionInfoAnalysis>();
84
  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
85
           PAC.preservedSet<CFGAnalyses>());
86
}
87

88
void RegionInfo::updateStatistics(Region *R) {
89
  ++numRegions;
90

91
  // TODO: Slow. Should only be enabled if -stats is used.
92
  if (R->isSimple())
93
    ++numSimpleRegions;
94
}
95

96
void RegionInfo::recalculate(Function &F, DominatorTree *DT_,
97
                             PostDominatorTree *PDT_, DominanceFrontier *DF_) {
98
  DT = DT_;
99
  PDT = PDT_;
100
  DF = DF_;
101

102
  TopLevelRegion = new Region(&F.getEntryBlock(), nullptr,
103
                              this, DT, nullptr);
104
  updateStatistics(TopLevelRegion);
105
  calculate(F);
106
}
107

108
#ifndef NDEBUG
109
void RegionInfo::view() { viewRegion(this); }
110

111
void RegionInfo::viewOnly() { viewRegionOnly(this); }
112
#endif
113

114
//===----------------------------------------------------------------------===//
115
// RegionInfoPass implementation
116
//
117

118
RegionInfoPass::RegionInfoPass() : FunctionPass(ID) {
119
  initializeRegionInfoPassPass(*PassRegistry::getPassRegistry());
120
}
121

122
RegionInfoPass::~RegionInfoPass() = default;
123

124
bool RegionInfoPass::runOnFunction(Function &F) {
125
  releaseMemory();
126

127
  auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
128
  auto PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
129
  auto DF = &getAnalysis<DominanceFrontierWrapperPass>().getDominanceFrontier();
130

131
  RI.recalculate(F, DT, PDT, DF);
132
  return false;
133
}
134

135
void RegionInfoPass::releaseMemory() {
136
  RI.releaseMemory();
137
}
138

139
void RegionInfoPass::verifyAnalysis() const {
140
    RI.verifyAnalysis();
141
}
142

143
void RegionInfoPass::getAnalysisUsage(AnalysisUsage &AU) const {
144
  AU.setPreservesAll();
145
  AU.addRequiredTransitive<DominatorTreeWrapperPass>();
146
  AU.addRequired<PostDominatorTreeWrapperPass>();
147
  AU.addRequired<DominanceFrontierWrapperPass>();
148
}
149

150
void RegionInfoPass::print(raw_ostream &OS, const Module *) const {
151
  RI.print(OS);
152
}
153

154
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
155
LLVM_DUMP_METHOD void RegionInfoPass::dump() const {
156
  RI.dump();
157
}
158
#endif
159

160
char RegionInfoPass::ID = 0;
161

162
INITIALIZE_PASS_BEGIN(RegionInfoPass, "regions",
163
                "Detect single entry single exit regions", true, true)
164
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
165
INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
166
INITIALIZE_PASS_DEPENDENCY(DominanceFrontierWrapperPass)
167
INITIALIZE_PASS_END(RegionInfoPass, "regions",
168
                "Detect single entry single exit regions", true, true)
169

170
// Create methods available outside of this file, to use them
171
// "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
172
// the link time optimization.
173

174
namespace llvm {
175

176
  FunctionPass *createRegionInfoPass() {
177
    return new RegionInfoPass();
178
  }
179

180
} // end namespace llvm
181

182
//===----------------------------------------------------------------------===//
183
// RegionInfoAnalysis implementation
184
//
185

186
AnalysisKey RegionInfoAnalysis::Key;
187

188
RegionInfo RegionInfoAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
189
  RegionInfo RI;
190
  auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
191
  auto *PDT = &AM.getResult<PostDominatorTreeAnalysis>(F);
192
  auto *DF = &AM.getResult<DominanceFrontierAnalysis>(F);
193

194
  RI.recalculate(F, DT, PDT, DF);
195
  return RI;
196
}
197

198
RegionInfoPrinterPass::RegionInfoPrinterPass(raw_ostream &OS)
199
  : OS(OS) {}
200

201
PreservedAnalyses RegionInfoPrinterPass::run(Function &F,
202
                                             FunctionAnalysisManager &AM) {
203
  OS << "Region Tree for function: " << F.getName() << "\n";
204
  AM.getResult<RegionInfoAnalysis>(F).print(OS);
205

206
  return PreservedAnalyses::all();
207
}
208

209
PreservedAnalyses RegionInfoVerifierPass::run(Function &F,
210
                                              FunctionAnalysisManager &AM) {
211
  AM.getResult<RegionInfoAnalysis>(F).verifyAnalysis();
212

213
  return PreservedAnalyses::all();
214
}
215