blob: 08ebf0d85723670c1a4a6a05c39d9f141c87632a [file] [log] [blame]
Tobias Grosser336734a2010-07-22 07:46:31 +00001//===- RegionInfo.cpp - SESE region detection analysis --------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9// Detects single entry single exit regions in the control flow graph.
10//===----------------------------------------------------------------------===//
11
12#include "llvm/Analysis/RegionInfo.h"
Matt Arsenault1b8d8372014-07-19 18:29:29 +000013#include "llvm/Analysis/RegionInfoImpl.h"
Tobias Grosser336734a2010-07-22 07:46:31 +000014#include "llvm/ADT/PostOrderIterator.h"
15#include "llvm/ADT/Statistic.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000016#include "llvm/Analysis/LoopInfo.h"
17#include "llvm/Analysis/RegionIterator.h"
Tobias Grosser336734a2010-07-22 07:46:31 +000018#include "llvm/Support/CommandLine.h"
Tobias Grosser336734a2010-07-22 07:46:31 +000019#include "llvm/Support/Debug.h"
Chandler Carruth8a8cd2b2014-01-07 11:48:04 +000020#include "llvm/Support/ErrorHandling.h"
Tobias Grosser336734a2010-07-22 07:46:31 +000021#include <algorithm>
David Blaikieec649ac2014-04-15 18:32:43 +000022#include <iterator>
Bill Wendling570d3022013-08-21 21:14:19 +000023#include <set>
Tobias Grosser336734a2010-07-22 07:46:31 +000024
25using namespace llvm;
26
Chandler Carruthf1221bd2014-04-22 02:48:03 +000027#define DEBUG_TYPE "region"
28
Matt Arsenault1b8d8372014-07-19 18:29:29 +000029namespace llvm {
30template class RegionBase<RegionTraits<Function>>;
31template class RegionNodeBase<RegionTraits<Function>>;
32template class RegionInfoBase<RegionTraits<Function>>;
33}
Tobias Grosser336734a2010-07-22 07:46:31 +000034
35STATISTIC(numRegions, "The # of regions");
36STATISTIC(numSimpleRegions, "The # of simple regions");
37
Matt Arsenault1b8d8372014-07-19 18:29:29 +000038// Always verify if expensive checking is enabled.
39
40static cl::opt<bool,true>
41VerifyRegionInfoX(
42 "verify-region-info",
43 cl::location(RegionInfoBase<RegionTraits<Function>>::VerifyRegionInfo),
44 cl::desc("Verify region info (time consuming)"));
45
46
47static cl::opt<Region::PrintStyle, true> printStyleX("print-region-style",
48 cl::location(RegionInfo::printStyle),
Tobias Grosser8b304ff2011-04-04 07:19:18 +000049 cl::Hidden,
Tobias Grosser336734a2010-07-22 07:46:31 +000050 cl::desc("style of printing regions"),
51 cl::values(
Tobias Grosser8b304ff2011-04-04 07:19:18 +000052 clEnumValN(Region::PrintNone, "none", "print no details"),
53 clEnumValN(Region::PrintBB, "bb",
Hongbin Zheng14c05c42012-08-27 13:49:24 +000054 "print regions in detail with block_iterator"),
Tobias Grosser8b304ff2011-04-04 07:19:18 +000055 clEnumValN(Region::PrintRN, "rn",
56 "print regions in detail with element_iterator"),
Tobias Grosser336734a2010-07-22 07:46:31 +000057 clEnumValEnd));
Matt Arsenault1b8d8372014-07-19 18:29:29 +000058
59
Tobias Grosser336734a2010-07-22 07:46:31 +000060//===----------------------------------------------------------------------===//
Matt Arsenault1b8d8372014-07-19 18:29:29 +000061// Region implementation
62//
Tobias Grosser336734a2010-07-22 07:46:31 +000063
Matt Arsenault1b8d8372014-07-19 18:29:29 +000064Region::Region(BasicBlock *Entry, BasicBlock *Exit,
65 RegionInfo* RI,
66 DominatorTree *DT, Region *Parent) :
67 RegionBase<RegionTraits<Function>>(Entry, Exit, RI, DT, Parent) {
Daniel Dunbar18e39ce2010-07-28 20:28:50 +000068
Tobias Grosser336734a2010-07-22 07:46:31 +000069}
70
Matt Arsenault1b8d8372014-07-19 18:29:29 +000071Region::~Region() { }
Tobias Grosser336734a2010-07-22 07:46:31 +000072
73//===----------------------------------------------------------------------===//
74// RegionInfo implementation
75//
76
Matt Arsenault1b8d8372014-07-19 18:29:29 +000077RegionInfo::RegionInfo() :
78 RegionInfoBase<RegionTraits<Function>>() {
79
Tobias Grosser336734a2010-07-22 07:46:31 +000080}
81
Matt Arsenault1b8d8372014-07-19 18:29:29 +000082RegionInfo::~RegionInfo() {
Tobias Grosser336734a2010-07-22 07:46:31 +000083
Tobias Grosser336734a2010-07-22 07:46:31 +000084}
85
86void RegionInfo::updateStatistics(Region *R) {
87 ++numRegions;
88
89 // TODO: Slow. Should only be enabled if -stats is used.
Matt Arsenault1b8d8372014-07-19 18:29:29 +000090 if (R->isSimple())
91 ++numSimpleRegions;
Tobias Grosser336734a2010-07-22 07:46:31 +000092}
93
NAKAMURA Takumi8eb82fc2014-07-20 03:57:51 +000094void RegionInfo::recalculate(Function &F, DominatorTree *DT_,
95 PostDominatorTree *PDT_, DominanceFrontier *DF_) {
Matt Arsenault1b8d8372014-07-19 18:29:29 +000096 DT = DT_;
97 PDT = PDT_;
98 DF = DF_;
Tobias Grosser336734a2010-07-22 07:46:31 +000099
Matt Arsenault1b8d8372014-07-19 18:29:29 +0000100 TopLevelRegion = new Region(&F.getEntryBlock(), nullptr,
101 this, DT, nullptr);
Tobias Grosser336734a2010-07-22 07:46:31 +0000102 updateStatistics(TopLevelRegion);
Matt Arsenault1b8d8372014-07-19 18:29:29 +0000103 calculate(F);
104}
Tobias Grosser336734a2010-07-22 07:46:31 +0000105
Matt Arsenault1b8d8372014-07-19 18:29:29 +0000106//===----------------------------------------------------------------------===//
107// RegionInfoPass implementation
108//
Tobias Grosser336734a2010-07-22 07:46:31 +0000109
Matt Arsenault1b8d8372014-07-19 18:29:29 +0000110RegionInfoPass::RegionInfoPass() : FunctionPass(ID) {
111 initializeRegionInfoPassPass(*PassRegistry::getPassRegistry());
112}
113
114RegionInfoPass::~RegionInfoPass() {
115
116}
117
118bool RegionInfoPass::runOnFunction(Function &F) {
119 releaseMemory();
120
121 auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
122 auto PDT = &getAnalysis<PostDominatorTree>();
123 auto DF = &getAnalysis<DominanceFrontier>();
124
125 RI.recalculate(F, DT, PDT, DF);
Tobias Grosser336734a2010-07-22 07:46:31 +0000126 return false;
127}
128
Matt Arsenault1b8d8372014-07-19 18:29:29 +0000129void RegionInfoPass::releaseMemory() {
130 RI.releaseMemory();
131}
132
133void RegionInfoPass::verifyAnalysis() const {
134 RI.verifyAnalysis();
135}
136
137void RegionInfoPass::getAnalysisUsage(AnalysisUsage &AU) const {
Tobias Grosser336734a2010-07-22 07:46:31 +0000138 AU.setPreservesAll();
Chandler Carruth73523022014-01-13 13:07:17 +0000139 AU.addRequiredTransitive<DominatorTreeWrapperPass>();
Tobias Grosser336734a2010-07-22 07:46:31 +0000140 AU.addRequired<PostDominatorTree>();
141 AU.addRequired<DominanceFrontier>();
142}
143
Matt Arsenault1b8d8372014-07-19 18:29:29 +0000144void RegionInfoPass::print(raw_ostream &OS, const Module *) const {
145 RI.print(OS);
Tobias Grosser336734a2010-07-22 07:46:31 +0000146}
147
NAKAMURA Takumi118b0c72014-07-20 00:00:42 +0000148#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
Matt Arsenault1b8d8372014-07-19 18:29:29 +0000149void RegionInfoPass::dump() const {
150 RI.dump();
Tobias Grosser336734a2010-07-22 07:46:31 +0000151}
NAKAMURA Takumi118b0c72014-07-20 00:00:42 +0000152#endif
Tobias Grosser336734a2010-07-22 07:46:31 +0000153
Matt Arsenault1b8d8372014-07-19 18:29:29 +0000154char RegionInfoPass::ID = 0;
Tobias Grosser336734a2010-07-22 07:46:31 +0000155
Matt Arsenault1b8d8372014-07-19 18:29:29 +0000156INITIALIZE_PASS_BEGIN(RegionInfoPass, "regions",
Owen Anderson8ac477f2010-10-12 19:48:12 +0000157 "Detect single entry single exit regions", true, true)
Chandler Carruth73523022014-01-13 13:07:17 +0000158INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
Owen Anderson8ac477f2010-10-12 19:48:12 +0000159INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
160INITIALIZE_PASS_DEPENDENCY(DominanceFrontier)
Matt Arsenault1b8d8372014-07-19 18:29:29 +0000161INITIALIZE_PASS_END(RegionInfoPass, "regions",
Owen Andersondf7a4f22010-10-07 22:25:06 +0000162 "Detect single entry single exit regions", true, true)
Tobias Grosser336734a2010-07-22 07:46:31 +0000163
164// Create methods available outside of this file, to use them
165// "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
166// the link time optimization.
167
168namespace llvm {
169 FunctionPass *createRegionInfoPass() {
Matt Arsenault1b8d8372014-07-19 18:29:29 +0000170 return new RegionInfoPass();
Tobias Grosser336734a2010-07-22 07:46:31 +0000171 }
172}
173