Coverage Report

Created: 2017-04-29 12:21

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/Analysis/ScopDetection.cpp
Line
Count
Source (jump to first uncovered line)
1
//===----- ScopDetection.cpp  - Detect Scops --------------------*- C++ -*-===//
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
//
10
// Detect the maximal Scops of a function.
11
//
12
// A static control part (Scop) is a subgraph of the control flow graph (CFG)
13
// that only has statically known control flow and can therefore be described
14
// within the polyhedral model.
15
//
16
// Every Scop fullfills these restrictions:
17
//
18
// * It is a single entry single exit region
19
//
20
// * Only affine linear bounds in the loops
21
//
22
// Every natural loop in a Scop must have a number of loop iterations that can
23
// be described as an affine linear function in surrounding loop iterators or
24
// parameters. (A parameter is a scalar that does not change its value during
25
// execution of the Scop).
26
//
27
// * Only comparisons of affine linear expressions in conditions
28
//
29
// * All loops and conditions perfectly nested
30
//
31
// The control flow needs to be structured such that it could be written using
32
// just 'for' and 'if' statements, without the need for any 'goto', 'break' or
33
// 'continue'.
34
//
35
// * Side effect free functions call
36
//
37
// Function calls and intrinsics that do not have side effects (readnone)
38
// or memory intrinsics (memset, memcpy, memmove) are allowed.
39
//
40
// The Scop detection finds the largest Scops by checking if the largest
41
// region is a Scop. If this is not the case, its canonical subregions are
42
// checked until a region is a Scop. It is now tried to extend this Scop by
43
// creating a larger non canonical region.
44
//
45
//===----------------------------------------------------------------------===//
46
47
#include "polly/ScopDetection.h"
48
#include "polly/CodeGen/CodeGeneration.h"
49
#include "polly/LinkAllPasses.h"
50
#include "polly/Options.h"
51
#include "polly/ScopDetectionDiagnostic.h"
52
#include "polly/Support/SCEVValidator.h"
53
#include "polly/Support/ScopLocation.h"
54
#include "llvm/ADT/Statistic.h"
55
#include "llvm/Analysis/AliasAnalysis.h"
56
#include "llvm/Analysis/Loads.h"
57
#include "llvm/Analysis/LoopInfo.h"
58
#include "llvm/Analysis/RegionIterator.h"
59
#include "llvm/Analysis/ScalarEvolution.h"
60
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
61
#include "llvm/IR/DebugInfo.h"
62
#include "llvm/IR/DiagnosticInfo.h"
63
#include "llvm/IR/DiagnosticPrinter.h"
64
#include "llvm/IR/IntrinsicInst.h"
65
#include "llvm/IR/LLVMContext.h"
66
#include "llvm/Support/Debug.h"
67
#include <set>
68
#include <stack>
69
70
using namespace llvm;
71
using namespace polly;
72
73
#define DEBUG_TYPE "polly-detect"
74
75
// This option is set to a very high value, as analyzing such loops increases
76
// compile time on several cases. For experiments that enable this option,
77
// a value of around 40 has been working to avoid run-time regressions with
78
// Polly while still exposing interesting optimization opportunities.
79
static cl::opt<int> ProfitabilityMinPerLoopInstructions(
80
    "polly-detect-profitability-min-per-loop-insts",
81
    cl::desc("The minimal number of per-loop instructions before a single loop "
82
             "region is considered profitable"),
83
    cl::Hidden, cl::ValueRequired, cl::init(100000000), cl::cat(PollyCategory));
84
85
bool polly::PollyProcessUnprofitable;
86
static cl::opt<bool, true> XPollyProcessUnprofitable(
87
    "polly-process-unprofitable",
88
    cl::desc(
89
        "Process scops that are unlikely to benefit from Polly optimizations."),
90
    cl::location(PollyProcessUnprofitable), cl::init(false), cl::ZeroOrMore,
91
    cl::cat(PollyCategory));
92
93
static cl::opt<std::string> OnlyFunction(
94
    "polly-only-func",
95
    cl::desc("Only run on functions that contain a certain string"),
96
    cl::value_desc("string"), cl::ValueRequired, cl::init(""),
97
    cl::cat(PollyCategory));
98
99
static cl::opt<std::string> OnlyRegion(
100
    "polly-only-region",
101
    cl::desc("Only run on certain regions (The provided identifier must "
102
             "appear in the name of the region's entry block"),
103
    cl::value_desc("identifier"), cl::ValueRequired, cl::init(""),
104
    cl::cat(PollyCategory));
105
106
static cl::opt<bool>
107
    IgnoreAliasing("polly-ignore-aliasing",
108
                   cl::desc("Ignore possible aliasing of the array bases"),
109
                   cl::Hidden, cl::init(false), cl::ZeroOrMore,
110
                   cl::cat(PollyCategory));
111
112
bool polly::PollyAllowUnsignedOperations;
113
static cl::opt<bool, true> XPollyAllowUnsignedOperations(
114
    "polly-allow-unsigned-operations",
115
    cl::desc("Allow unsigned operations such as comparisons or zero-extends."),
116
    cl::location(PollyAllowUnsignedOperations), cl::Hidden, cl::ZeroOrMore,
117
    cl::init(true), cl::cat(PollyCategory));
118
119
bool polly::PollyUseRuntimeAliasChecks;
120
static cl::opt<bool, true> XPollyUseRuntimeAliasChecks(
121
    "polly-use-runtime-alias-checks",
122
    cl::desc("Use runtime alias checks to resolve possible aliasing."),
123
    cl::location(PollyUseRuntimeAliasChecks), cl::Hidden, cl::ZeroOrMore,
124
    cl::init(true), cl::cat(PollyCategory));
125
126
static cl::opt<bool>
127
    ReportLevel("polly-report",
128
                cl::desc("Print information about the activities of Polly"),
129
                cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
130
131
static cl::opt<bool> AllowDifferentTypes(
132
    "polly-allow-differing-element-types",
133
    cl::desc("Allow different element types for array accesses"), cl::Hidden,
134
    cl::init(true), cl::ZeroOrMore, cl::cat(PollyCategory));
135
136
static cl::opt<bool>
137
    AllowNonAffine("polly-allow-nonaffine",
138
                   cl::desc("Allow non affine access functions in arrays"),
139
                   cl::Hidden, cl::init(false), cl::ZeroOrMore,
140
                   cl::cat(PollyCategory));
141
142
static cl::opt<bool>
143
    AllowModrefCall("polly-allow-modref-calls",
144
                    cl::desc("Allow functions with known modref behavior"),
145
                    cl::Hidden, cl::init(false), cl::ZeroOrMore,
146
                    cl::cat(PollyCategory));
147
148
static cl::opt<bool> AllowNonAffineSubRegions(
149
    "polly-allow-nonaffine-branches",
150
    cl::desc("Allow non affine conditions for branches"), cl::Hidden,
151
    cl::init(true), cl::ZeroOrMore, cl::cat(PollyCategory));
152
153
static cl::opt<bool>
154
    AllowNonAffineSubLoops("polly-allow-nonaffine-loops",
155
                           cl::desc("Allow non affine conditions for loops"),
156
                           cl::Hidden, cl::init(false), cl::ZeroOrMore,
157
                           cl::cat(PollyCategory));
158
159
static cl::opt<bool, true>
160
    TrackFailures("polly-detect-track-failures",
161
                  cl::desc("Track failure strings in detecting scop regions"),
162
                  cl::location(PollyTrackFailures), cl::Hidden, cl::ZeroOrMore,
163
                  cl::init(true), cl::cat(PollyCategory));
164
165
static cl::opt<bool> KeepGoing("polly-detect-keep-going",
166
                               cl::desc("Do not fail on the first error."),
167
                               cl::Hidden, cl::ZeroOrMore, cl::init(false),
168
                               cl::cat(PollyCategory));
169
170
static cl::opt<bool, true>
171
    PollyDelinearizeX("polly-delinearize",
172
                      cl::desc("Delinearize array access functions"),
173
                      cl::location(PollyDelinearize), cl::Hidden,
174
                      cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory));
175
176
static cl::opt<bool>
177
    VerifyScops("polly-detect-verify",
178
                cl::desc("Verify the detected SCoPs after each transformation"),
179
                cl::Hidden, cl::init(false), cl::ZeroOrMore,
180
                cl::cat(PollyCategory));
181
182
bool polly::PollyInvariantLoadHoisting;
183
static cl::opt<bool, true> XPollyInvariantLoadHoisting(
184
    "polly-invariant-load-hoisting", cl::desc("Hoist invariant loads."),
185
    cl::location(PollyInvariantLoadHoisting), cl::Hidden, cl::ZeroOrMore,
186
    cl::init(false), cl::cat(PollyCategory));
187
188
/// The minimal trip count under which loops are considered unprofitable.
189
static const unsigned MIN_LOOP_TRIP_COUNT = 8;
190
191
bool polly::PollyTrackFailures = false;
192
bool polly::PollyDelinearize = false;
193
StringRef polly::PollySkipFnAttr = "polly.skip.fn";
194
195
//===----------------------------------------------------------------------===//
196
// Statistics.
197
198
STATISTIC(NumScopRegions, "Number of scops");
199
STATISTIC(NumLoopsInScop, "Number of loops in scops");
200
STATISTIC(NumScopsDepthOne, "Number of scops with maximal loop depth 1");
201
STATISTIC(NumScopsDepthTwo, "Number of scops with maximal loop depth 2");
202
STATISTIC(NumScopsDepthThree, "Number of scops with maximal loop depth 3");
203
STATISTIC(NumScopsDepthFour, "Number of scops with maximal loop depth 4");
204
STATISTIC(NumScopsDepthFive, "Number of scops with maximal loop depth 5");
205
STATISTIC(NumScopsDepthLarger,
206
          "Number of scops with maximal loop depth 6 and larger");
207
STATISTIC(NumProfScopRegions, "Number of scops (profitable scops only)");
208
STATISTIC(NumLoopsInProfScop,
209
          "Number of loops in scops (profitable scops only)");
210
STATISTIC(NumLoopsOverall, "Number of total loops");
211
STATISTIC(NumProfScopsDepthOne,
212
          "Number of scops with maximal loop depth 1 (profitable scops only)");
213
STATISTIC(NumProfScopsDepthTwo,
214
          "Number of scops with maximal loop depth 2 (profitable scops only)");
215
STATISTIC(NumProfScopsDepthThree,
216
          "Number of scops with maximal loop depth 3 (profitable scops only)");
217
STATISTIC(NumProfScopsDepthFour,
218
          "Number of scops with maximal loop depth 4 (profitable scops only)");
219
STATISTIC(NumProfScopsDepthFive,
220
          "Number of scops with maximal loop depth 5 (profitable scops only)");
221
STATISTIC(NumProfScopsDepthLarger,
222
          "Number of scops with maximal loop depth 6 and larger "
223
          "(profitable scops only)");
224
STATISTIC(MaxNumLoopsInScop, "Maximal number of loops in scops");
225
STATISTIC(MaxNumLoopsInProfScop,
226
          "Maximal number of loops in scops (profitable scops only)");
227
228
class DiagnosticScopFound : public DiagnosticInfo {
229
private:
230
  static int PluginDiagnosticKind;
231
232
  Function &F;
233
  std::string FileName;
234
  unsigned EntryLine, ExitLine;
235
236
public:
237
  DiagnosticScopFound(Function &F, std::string FileName, unsigned EntryLine,
238
                      unsigned ExitLine)
239
      : DiagnosticInfo(PluginDiagnosticKind, DS_Note), F(F), FileName(FileName),
240
2
        EntryLine(EntryLine), ExitLine(ExitLine) {}
241
242
  virtual void print(DiagnosticPrinter &DP) const;
243
244
0
  static bool classof(const DiagnosticInfo *DI) {
245
0
    return DI->getKind() == PluginDiagnosticKind;
246
0
  }
247
};
248
249
int DiagnosticScopFound::PluginDiagnosticKind =
250
    getNextAvailablePluginDiagnosticKind();
251
252
2
void DiagnosticScopFound::print(DiagnosticPrinter &DP) const {
253
2
  DP << "Polly detected an optimizable loop region (scop) in function '" << F
254
2
     << "'\n";
255
2
256
2
  if (
FileName.empty()2
)
{0
257
0
    DP << "Scop location is unknown. Compile with debug info "
258
0
          "(-g) to get more precise information. ";
259
0
    return;
260
0
  }
261
2
262
2
  DP << FileName << ":" << EntryLine << ": Start of scop\n";
263
2
  DP << FileName << ":" << ExitLine << ": End of scop";
264
2
}
265
266
//===----------------------------------------------------------------------===//
267
// ScopDetection.
268
269
1.02k
ScopDetection::ScopDetection() : FunctionPass(ID) {
270
1.02k
  // Disable runtime alias checks if we ignore aliasing all together.
271
1.02k
  if (IgnoreAliasing)
272
18
    PollyUseRuntimeAliasChecks = false;
273
1.02k
}
274
275
template <class RR, typename... Args>
276
inline bool ScopDetection::invalid(DetectionContext &Context, bool Assert,
277
587
                                   Args &&... Arguments) const {
278
587
279
587
  if (
!Context.Verifying587
)
{587
280
587
    RejectLog &Log = Context.Log;
281
587
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
587
283
587
    if (PollyTrackFailures)
284
587
      Log.report(RejectReason);
285
587
286
587
    DEBUG(dbgs() << RejectReason->getMessage());
287
587
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
587
292
587
  return false;
293
587
}
Unexecuted instantiation: bool polly::ScopDetection::invalid<polly::ReportNonAffBranch, llvm::BasicBlock*, llvm::SCEV const*&, llvm::SCEV const*&, llvm::SwitchInst*&>(polly::ScopDetection::DetectionContext&, bool, llvm::BasicBlock*&&, llvm::SCEV const*&&&, llvm::SCEV const*&&&, llvm::SwitchInst*&&&) const
Unexecuted instantiation: bool polly::ScopDetection::invalid<polly::ReportInvalidCond, llvm::BranchInst*&, llvm::BasicBlock*>(polly::ScopDetection::DetectionContext&, bool, llvm::BranchInst*&&&, llvm::BasicBlock*&&) const
bool polly::ScopDetection::invalid<polly::ReportUndefOperand, llvm::BasicBlock*, llvm::ICmpInst*&>(polly::ScopDetection::DetectionContext&, bool, llvm::BasicBlock*&&, llvm::ICmpInst*&&&) const
Line
Count
Source
277
5
                                   Args &&... Arguments) const {
278
5
279
5
  if (
!Context.Verifying5
)
{5
280
5
    RejectLog &Log = Context.Log;
281
5
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
5
283
5
    if (PollyTrackFailures)
284
5
      Log.report(RejectReason);
285
5
286
5
    DEBUG(dbgs() << RejectReason->getMessage());
287
5
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
5
292
5
  return false;
293
5
}
bool polly::ScopDetection::invalid<polly::ReportNonAffBranch, llvm::BasicBlock*, llvm::SCEV const*&, llvm::SCEV const*&, llvm::ICmpInst*&>(polly::ScopDetection::DetectionContext&, bool, llvm::BasicBlock*&&, llvm::SCEV const*&&&, llvm::SCEV const*&&&, llvm::ICmpInst*&&&) const
Line
Count
Source
277
5
                                   Args &&... Arguments) const {
278
5
279
5
  if (
!Context.Verifying5
)
{5
280
5
    RejectLog &Log = Context.Log;
281
5
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
5
283
5
    if (PollyTrackFailures)
284
5
      Log.report(RejectReason);
285
5
286
5
    DEBUG(dbgs() << RejectReason->getMessage());
287
5
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
5
292
5
  return false;
293
5
}
Unexecuted instantiation: bool polly::ScopDetection::invalid<polly::ReportInvalidTerminator, llvm::BasicBlock*>(polly::ScopDetection::DetectionContext&, bool, llvm::BasicBlock*&&) const
bool polly::ScopDetection::invalid<polly::ReportUndefCond, llvm::TerminatorInst*&, llvm::BasicBlock*>(polly::ScopDetection::DetectionContext&, bool, llvm::TerminatorInst*&&&, llvm::BasicBlock*&&) const
Line
Count
Source
277
154
                                   Args &&... Arguments) const {
278
154
279
154
  if (
!Context.Verifying154
)
{154
280
154
    RejectLog &Log = Context.Log;
281
154
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
154
283
154
    if (PollyTrackFailures)
284
154
      Log.report(RejectReason);
285
154
286
154
    DEBUG(dbgs() << RejectReason->getMessage());
287
154
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
154
292
154
  return false;
293
154
}
bool polly::ScopDetection::invalid<polly::ReportNonAffineAccess, llvm::SCEV const*&, llvm::Instruction const*&, llvm::Value*&>(polly::ScopDetection::DetectionContext&, bool, llvm::SCEV const*&&&, llvm::Instruction const*&&&, llvm::Value*&&&) const
Line
Count
Source
277
28
                                   Args &&... Arguments) const {
278
28
279
28
  if (
!Context.Verifying28
)
{28
280
28
    RejectLog &Log = Context.Log;
281
28
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
28
283
28
    if (PollyTrackFailures)
284
28
      Log.report(RejectReason);
285
28
286
28
    DEBUG(dbgs() << RejectReason->getMessage());
287
28
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
28
292
28
  return false;
293
28
}
bool polly::ScopDetection::invalid<polly::ReportNonAffineAccess, llvm::SCEV const* const&, llvm::Instruction const*&, llvm::Value*&>(polly::ScopDetection::DetectionContext&, bool, llvm::SCEV const* const&&&, llvm::Instruction const*&&&, llvm::Value*&&&) const
Line
Count
Source
277
6
                                   Args &&... Arguments) const {
278
6
279
6
  if (
!Context.Verifying6
)
{6
280
6
    RejectLog &Log = Context.Log;
281
6
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
6
283
6
    if (PollyTrackFailures)
284
6
      Log.report(RejectReason);
285
6
286
6
    DEBUG(dbgs() << RejectReason->getMessage());
287
6
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
6
292
6
  return false;
293
6
}
Unexecuted instantiation: bool polly::ScopDetection::invalid<polly::ReportNoBasePtr, llvm::Instruction*&>(polly::ScopDetection::DetectionContext&, bool, llvm::Instruction*&&&) const
bool polly::ScopDetection::invalid<polly::ReportUndefBasePtr, llvm::Instruction*&>(polly::ScopDetection::DetectionContext&, bool, llvm::Instruction*&&&) const
Line
Count
Source
277
5
                                   Args &&... Arguments) const {
278
5
279
5
  if (
!Context.Verifying5
)
{5
280
5
    RejectLog &Log = Context.Log;
281
5
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
5
283
5
    if (PollyTrackFailures)
284
5
      Log.report(RejectReason);
285
5
286
5
    DEBUG(dbgs() << RejectReason->getMessage());
287
5
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
5
292
5
  return false;
293
5
}
bool polly::ScopDetection::invalid<polly::ReportIntToPtr, llvm::IntToPtrInst*&>(polly::ScopDetection::DetectionContext&, bool, llvm::IntToPtrInst*&&&) const
Line
Count
Source
277
1
                                   Args &&... Arguments) const {
278
1
279
1
  if (
!Context.Verifying1
)
{1
280
1
    RejectLog &Log = Context.Log;
281
1
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
1
283
1
    if (PollyTrackFailures)
284
1
      Log.report(RejectReason);
285
1
286
1
    DEBUG(dbgs() << RejectReason->getMessage());
287
1
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
1
292
1
  return false;
293
1
}
bool polly::ScopDetection::invalid<polly::ReportVariantBasePtr, llvm::Value*&, llvm::Instruction*&>(polly::ScopDetection::DetectionContext&, bool, llvm::Value*&&&, llvm::Instruction*&&&) const
Line
Count
Source
277
10
                                   Args &&... Arguments) const {
278
10
279
10
  if (
!Context.Verifying10
)
{10
280
10
    RejectLog &Log = Context.Log;
281
10
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
10
283
10
    if (PollyTrackFailures)
284
10
      Log.report(RejectReason);
285
10
286
10
    DEBUG(dbgs() << RejectReason->getMessage());
287
10
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
10
292
10
  return false;
293
10
}
Unexecuted instantiation: bool polly::ScopDetection::invalid<polly::ReportDifferentArrayElementSize, llvm::Instruction*&, llvm::Value*&>(polly::ScopDetection::DetectionContext&, bool, llvm::Instruction*&&&, llvm::Value*&&&) const
bool polly::ScopDetection::invalid<polly::ReportNonAffineAccess, llvm::SCEV const*&, llvm::Instruction*&, llvm::Value*&>(polly::ScopDetection::DetectionContext&, bool, llvm::SCEV const*&&&, llvm::Instruction*&&&, llvm::Value*&&&) const
Line
Count
Source
277
22
                                   Args &&... Arguments) const {
278
22
279
22
  if (
!Context.Verifying22
)
{22
280
22
    RejectLog &Log = Context.Log;
281
22
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
22
283
22
    if (PollyTrackFailures)
284
22
      Log.report(RejectReason);
285
22
286
22
    DEBUG(dbgs() << RejectReason->getMessage());
287
22
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
22
292
22
  return false;
293
22
}
bool polly::ScopDetection::invalid<polly::ReportAlias, llvm::Instruction*&, llvm::AliasSet&>(polly::ScopDetection::DetectionContext&, bool, llvm::Instruction*&&&, llvm::AliasSet&&&) const
Line
Count
Source
277
3
                                   Args &&... Arguments) const {
278
3
279
3
  if (
!Context.Verifying3
)
{3
280
3
    RejectLog &Log = Context.Log;
281
3
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
3
283
3
    if (PollyTrackFailures)
284
3
      Log.report(RejectReason);
285
3
286
3
    DEBUG(dbgs() << RejectReason->getMessage());
287
3
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
3
292
3
  return false;
293
3
}
bool polly::ScopDetection::invalid<polly::ReportFuncCall, llvm::Instruction*>(polly::ScopDetection::DetectionContext&, bool, llvm::Instruction*&&) const
Line
Count
Source
277
12
                                   Args &&... Arguments) const {
278
12
279
12
  if (
!Context.Verifying12
)
{12
280
12
    RejectLog &Log = Context.Log;
281
12
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
12
283
12
    if (PollyTrackFailures)
284
12
      Log.report(RejectReason);
285
12
286
12
    DEBUG(dbgs() << RejectReason->getMessage());
287
12
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
12
292
12
  return false;
293
12
}
Unexecuted instantiation: bool polly::ScopDetection::invalid<polly::ReportAlloca, llvm::Instruction*>(polly::ScopDetection::DetectionContext&, bool, llvm::Instruction*&&) const
Unexecuted instantiation: bool polly::ScopDetection::invalid<polly::ReportNonSimpleMemoryAccess, llvm::Instruction*>(polly::ScopDetection::DetectionContext&, bool, llvm::Instruction*&&) const
bool polly::ScopDetection::invalid<polly::ReportUnknownInst, llvm::Instruction*>(polly::ScopDetection::DetectionContext&, bool, llvm::Instruction*&&) const
Line
Count
Source
277
51
                                   Args &&... Arguments) const {
278
51
279
51
  if (
!Context.Verifying51
)
{51
280
51
    RejectLog &Log = Context.Log;
281
51
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
51
283
51
    if (PollyTrackFailures)
284
51
      Log.report(RejectReason);
285
51
286
51
    DEBUG(dbgs() << RejectReason->getMessage());
287
51
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
51
292
51
  return false;
293
51
}
bool polly::ScopDetection::invalid<polly::ReportLoopHasNoExit, llvm::Loop*&>(polly::ScopDetection::DetectionContext&, bool, llvm::Loop*&&&) const
Line
Count
Source
277
16
                                   Args &&... Arguments) const {
278
16
279
16
  if (
!Context.Verifying16
)
{16
280
16
    RejectLog &Log = Context.Log;
281
16
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
16
283
16
    if (PollyTrackFailures)
284
16
      Log.report(RejectReason);
285
16
286
16
    DEBUG(dbgs() << RejectReason->getMessage());
287
16
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
16
292
16
  return false;
293
16
}
bool polly::ScopDetection::invalid<polly::ReportLoopBound, llvm::Loop*&, llvm::SCEV const*&>(polly::ScopDetection::DetectionContext&, bool, llvm::Loop*&&&, llvm::SCEV const*&&&) const
Line
Count
Source
277
143
                                   Args &&... Arguments) const {
278
143
279
143
  if (
!Context.Verifying143
)
{143
280
143
    RejectLog &Log = Context.Log;
281
143
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
143
283
143
    if (PollyTrackFailures)
284
143
      Log.report(RejectReason);
285
143
286
143
    DEBUG(dbgs() << RejectReason->getMessage());
287
143
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
143
292
143
  return false;
293
143
}
bool polly::ScopDetection::invalid<polly::ReportUnprofitable, llvm::Region*>(polly::ScopDetection::DetectionContext&, bool, llvm::Region*&&) const
Line
Count
Source
277
14
                                   Args &&... Arguments) const {
278
14
279
14
  if (
!Context.Verifying14
)
{14
280
14
    RejectLog &Log = Context.Log;
281
14
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
14
283
14
    if (PollyTrackFailures)
284
14
      Log.report(RejectReason);
285
14
286
14
    DEBUG(dbgs() << RejectReason->getMessage());
287
14
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
14
292
14
  return false;
293
14
}
bool polly::ScopDetection::invalid<polly::ReportUnreachableInExit, llvm::BasicBlock*, llvm::DebugLoc&>(polly::ScopDetection::DetectionContext&, bool, llvm::BasicBlock*&&, llvm::DebugLoc&&&) const
Line
Count
Source
277
26
                                   Args &&... Arguments) const {
278
26
279
26
  if (
!Context.Verifying26
)
{26
280
26
    RejectLog &Log = Context.Log;
281
26
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
26
283
26
    if (PollyTrackFailures)
284
26
      Log.report(RejectReason);
285
26
286
26
    DEBUG(dbgs() << RejectReason->getMessage());
287
26
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
26
292
26
  return false;
293
26
}
bool polly::ScopDetection::invalid<polly::ReportEntry, llvm::BasicBlock*>(polly::ScopDetection::DetectionContext&, bool, llvm::BasicBlock*&&) const
Line
Count
Source
277
83
                                   Args &&... Arguments) const {
278
83
279
83
  if (
!Context.Verifying83
)
{83
280
83
    RejectLog &Log = Context.Log;
281
83
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
83
283
83
    if (PollyTrackFailures)
284
83
      Log.report(RejectReason);
285
83
286
83
    DEBUG(dbgs() << RejectReason->getMessage());
287
83
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
83
292
83
  return false;
293
83
}
bool polly::ScopDetection::invalid<polly::ReportIrreducibleRegion, llvm::Region*, llvm::DebugLoc&>(polly::ScopDetection::DetectionContext&, bool, llvm::Region*&&, llvm::DebugLoc&&&) const
Line
Count
Source
277
3
                                   Args &&... Arguments) const {
278
3
279
3
  if (
!Context.Verifying3
)
{3
280
3
    RejectLog &Log = Context.Log;
281
3
    std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
282
3
283
3
    if (PollyTrackFailures)
284
3
      Log.report(RejectReason);
285
3
286
3
    DEBUG(dbgs() << RejectReason->getMessage());
287
3
    DEBUG(dbgs() << "\n");
288
0
  } else {
289
0
    assert(!Assert && "Verification of detected scop failed");
290
0
  }
291
3
292
3
  return false;
293
3
}
294
295
3.29k
bool ScopDetection::isMaxRegionInScop(const Region &R, bool Verify) const {
296
3.29k
  if (!ValidRegions.count(&R))
297
2.35k
    return false;
298
3.29k
299
943
  
if (943
Verify943
)
{943
300
943
    DetectionContextMap.erase(getBBPairForRegion(&R));
301
943
    const auto &It = DetectionContextMap.insert(std::make_pair(
302
943
        getBBPairForRegion(&R),
303
943
        DetectionContext(const_cast<Region &>(R), *AA, false /*verifying*/)));
304
943
    DetectionContext &Context = It.first->second;
305
943
    return isValidRegion(Context);
306
943
  }
307
943
308
0
  return true;
309
943
}
310
311
4
std::string ScopDetection::regionIsInvalidBecause(const Region *R) const {
312
4
  // Get the first error we found. Even in keep-going mode, this is the first
313
4
  // reason that caused the candidate to be rejected.
314
4
  auto *Log = lookupRejectionLog(R);
315
4
316
4
  // This can happen when we marked a region invalid, but didn't track
317
4
  // an error for it.
318
4
  if (
!Log || 4
!Log->hasErrors()3
)
319
4
    return "";
320
4
321
0
  RejectReasonPtr RR = *Log->begin();
322
0
  return RR->getMessage();
323
4
}
324
325
bool ScopDetection::addOverApproximatedRegion(Region *AR,
326
636
                                              DetectionContext &Context) const {
327
636
328
636
  // If we already know about Ar we can exit.
329
636
  if (!Context.NonAffineSubRegionSet.insert(AR))
330
60
    return true;
331
636
332
636
  // All loops in the region have to be overapproximated too if there
333
636
  // are accesses that depend on the iteration count.
334
636
335
1.43k
  
for (BasicBlock *BB : AR->blocks()) 576
{1.43k
336
1.43k
    Loop *L = LI->getLoopFor(BB);
337
1.43k
    if (AR->contains(L))
338
227
      Context.BoxedLoopsSet.insert(L);
339
1.43k
  }
340
576
341
489
  return (AllowNonAffineSubLoops || Context.BoxedLoopsSet.empty());
342
636
}
343
344
bool ScopDetection::onlyValidRequiredInvariantLoads(
345
34.0k
    InvariantLoadsSetTy &RequiredILS, DetectionContext &Context) const {
346
34.0k
  Region &CurRegion = Context.CurRegion;
347
34.0k
  const DataLayout &DL = CurRegion.getEntry()->getModule()->getDataLayout();
348
34.0k
349
34.0k
  if (
!PollyInvariantLoadHoisting && 34.0k
!RequiredILS.empty()26.8k
)
350
351
    return false;
351
34.0k
352
33.6k
  
for (LoadInst *Load : RequiredILS) 33.6k
{1.51k
353
1.51k
    if (!isHoistableLoad(Load, CurRegion, *LI, *SE, *DT))
354
136
      return false;
355
1.51k
356
1.38k
    
for (auto NonAffineRegion : Context.NonAffineSubRegionSet) 1.38k
{334
357
334
358
334
      if (isSafeToLoadUnconditionally(Load->getPointerOperand(),
359
334
                                      Load->getAlignment(), DL))
360
16
        continue;
361
334
362
318
      
if (318
NonAffineRegion->contains(Load) &&318
363
14
          Load->getParent() != NonAffineRegion->getEntry())
364
14
        return false;
365
318
    }
366
1.38k
  }
367
33.6k
368
33.5k
  Context.RequiredILS.insert(RequiredILS.begin(), RequiredILS.end());
369
33.5k
370
33.5k
  return true;
371
33.6k
}
372
373
bool ScopDetection::involvesMultiplePtrs(const SCEV *S0, const SCEV *S1,
374
11.0k
                                         Loop *Scope) const {
375
11.0k
  SetVector<Value *> Values;
376
11.0k
  findValues(S0, *SE, Values);
377
11.0k
  if (S1)
378
3.60k
    findValues(S1, *SE, Values);
379
11.0k
380
11.0k
  SmallPtrSet<Value *, 8> PtrVals;
381
4.77k
  for (auto *V : Values) {
382
4.77k
    if (auto *P2I = dyn_cast<PtrToIntInst>(V))
383
2
      V = P2I->getOperand(0);
384
4.77k
385
4.77k
    if (!V->getType()->isPointerTy())
386
4.71k
      continue;
387
4.77k
388
59
    auto *PtrSCEV = SE->getSCEVAtScope(V, Scope);
389
59
    if (isa<SCEVConstant>(PtrSCEV))
390
2
      continue;
391
59
392
57
    auto *BasePtr = dyn_cast<SCEVUnknown>(SE->getPointerBase(PtrSCEV));
393
57
    if (!BasePtr)
394
0
      return true;
395
57
396
57
    auto *BasePtrVal = BasePtr->getValue();
397
57
    if (
PtrVals.insert(BasePtrVal).second57
)
{57
398
57
      for (auto *PtrVal : PtrVals)
399
57
        
if (57
PtrVal != BasePtrVal && 57
!AA->isNoAlias(PtrVal, BasePtrVal)0
)
400
0
          return true;
401
57
    }
402
57
  }
403
11.0k
404
11.0k
  return false;
405
11.0k
}
406
407
bool ScopDetection::isAffine(const SCEV *S, Loop *Scope,
408
34.7k
                             DetectionContext &Context) const {
409
34.7k
410
34.7k
  InvariantLoadsSetTy AccessILS;
411
34.7k
  if (!isAffineExpr(&Context.CurRegion, Scope, S, *SE, &AccessILS))
412
751
    return false;
413
34.7k
414
34.0k
  
if (34.0k
!onlyValidRequiredInvariantLoads(AccessILS, Context)34.0k
)
415
501
    return false;
416
34.0k
417
33.5k
  return true;
418
34.0k
}
419
420
bool ScopDetection::isValidSwitch(BasicBlock &BB, SwitchInst *SI,
421
                                  Value *Condition, bool IsLoopBranch,
422
47
                                  DetectionContext &Context) const {
423
47
  Loop *L = LI->getLoopFor(&BB);
424
47
  const SCEV *ConditionSCEV = SE->getSCEVAtScope(Condition, L);
425
47
426
47
  if (
IsLoopBranch && 47
L->isLoopLatch(&BB)5
)
427
1
    return false;
428
47
429
47
  // Check for invalid usage of different pointers in one expression.
430
46
  
if (46
involvesMultiplePtrs(ConditionSCEV, nullptr, L)46
)
431
0
    return false;
432
46
433
46
  
if (46
isAffine(ConditionSCEV, L, Context)46
)
434
44
    return true;
435
46
436
2
  
if (2
AllowNonAffineSubRegions &&2
437
2
      addOverApproximatedRegion(RI->getRegionFor(&BB), Context))
438
2
    return true;
439
2
440
0
  return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB,
441
0
                                     ConditionSCEV, ConditionSCEV, SI);
442
2
}
443
444
bool ScopDetection::isValidBranch(BasicBlock &BB, BranchInst *BI,
445
                                  Value *Condition, bool IsLoopBranch,
446
23.8k
                                  DetectionContext &Context) const {
447
23.8k
448
23.8k
  // Constant integer conditions are always affine.
449
23.8k
  if (isa<ConstantInt>(Condition))
450
12.7k
    return true;
451
23.8k
452
11.1k
  
if (BinaryOperator *11.1k
BinOp11.1k
= dyn_cast<BinaryOperator>(Condition))
{103
453
103
    auto Opcode = BinOp->getOpcode();
454
103
    if (
Opcode == Instruction::And || 103
Opcode == Instruction::Or92
)
{103
455
103
      Value *Op0 = BinOp->getOperand(0);
456
103
      Value *Op1 = BinOp->getOperand(1);
457
103
      return isValidBranch(BB, BI, Op0, IsLoopBranch, Context) &&
458
103
             isValidBranch(BB, BI, Op1, IsLoopBranch, Context);
459
103
    }
460
103
  }
461
11.1k
462
11.1k
  // Non constant conditions of branches need to be ICmpInst.
463
11.0k
  
if (11.0k
!isa<ICmpInst>(Condition)11.0k
)
{95
464
95
    if (
!IsLoopBranch && 95
AllowNonAffineSubRegions95
&&
465
95
        addOverApproximatedRegion(RI->getRegionFor(&BB), Context))
466
95
      return true;
467
0
    return invalid<ReportInvalidCond>(Context, /*Assert=*/true, BI, &BB);
468
95
  }
469
11.0k
470
10.9k
  ICmpInst *ICmp = cast<ICmpInst>(Condition);
471
10.9k
472
10.9k
  // Are both operands of the ICmp affine?
473
10.9k
  if (isa<UndefValue>(ICmp->getOperand(0)) ||
474
10.9k
      isa<UndefValue>(ICmp->getOperand(1)))
475
5
    return invalid<ReportUndefOperand>(Context, /*Assert=*/true, &BB, ICmp);
476
10.9k
477
10.9k
  Loop *L = LI->getLoopFor(&BB);
478
10.9k
  const SCEV *LHS = SE->getSCEVAtScope(ICmp->getOperand(0), L);
479
10.9k
  const SCEV *RHS = SE->getSCEVAtScope(ICmp->getOperand(1), L);
480
10.9k
481
10.9k
  // If unsigned operations are not allowed try to approximate the region.
482
10.9k
  if (
ICmp->isUnsigned() && 10.9k
!PollyAllowUnsignedOperations68
)
483
0
    
return !IsLoopBranch && 0
AllowNonAffineSubRegions0
&&
484
0
           addOverApproximatedRegion(RI->getRegionFor(&BB), Context);
485
10.9k
486
10.9k
  // Check for invalid usage of different pointers in one expression.
487
10.9k
  
if (10.9k
ICmp->isEquality() && 10.9k
involvesMultiplePtrs(LHS, nullptr, L)7.36k
&&
488
0
      involvesMultiplePtrs(RHS, nullptr, L))
489
0
    return false;
490
10.9k
491
10.9k
  // Check for invalid usage of different pointers in a relational comparison.
492
10.9k
  
if (10.9k
ICmp->isRelational() && 10.9k
involvesMultiplePtrs(LHS, RHS, L)3.60k
)
493
0
    return false;
494
10.9k
495
10.9k
  
if (10.9k
isAffine(LHS, L, Context) && 10.9k
isAffine(RHS, L, Context)10.6k
)
496
10.3k
    return true;
497
10.9k
498
585
  
if (585
!IsLoopBranch && 585
AllowNonAffineSubRegions479
&&
499
477
      addOverApproximatedRegion(RI->getRegionFor(&BB), Context))
500
474
    return true;
501
585
502
111
  
if (111
IsLoopBranch111
)
503
106
    return false;
504
111
505
5
  return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB, LHS, RHS,
506
5
                                     ICmp);
507
111
}
508
509
bool ScopDetection::isValidCFG(BasicBlock &BB, bool IsLoopBranch,
510
                               bool AllowUnreachable,
511
23.8k
                               DetectionContext &Context) const {
512
23.8k
  Region &CurRegion = Context.CurRegion;
513
23.8k
514
23.8k
  TerminatorInst *TI = BB.getTerminator();
515
23.8k
516
23.8k
  if (
AllowUnreachable && 23.8k
isa<UnreachableInst>(TI)128
)
517
0
    return true;
518
23.8k
519
23.8k
  // Return instructions are only valid if the region is the top level region.
520
23.8k
  
if (23.8k
isa<ReturnInst>(TI) && 23.8k
!CurRegion.getExit()0
&&
TI->getNumOperands() == 00
)
521
0
    return true;
522
23.8k
523
23.8k
  Value *Condition = getConditionFromTerminator(TI);
524
23.8k
525
23.8k
  if (!Condition)
526
0
    return invalid<ReportInvalidTerminator>(Context, /*Assert=*/true, &BB);
527
23.8k
528
23.8k
  // UndefValue is not allowed as condition.
529
23.8k
  
if (23.8k
isa<UndefValue>(Condition)23.8k
)
530
154
    return invalid<ReportUndefCond>(Context, /*Assert=*/true, TI, &BB);
531
23.8k
532
23.7k
  
if (BranchInst *23.7k
BI23.7k
= dyn_cast<BranchInst>(TI))
533
23.6k
    return isValidBranch(BB, BI, Condition, IsLoopBranch, Context);
534
23.7k
535
47
  SwitchInst *SI = dyn_cast<SwitchInst>(TI);
536
47
  assert(SI && "Terminator was neither branch nor switch");
537
47
538
47
  return isValidSwitch(BB, SI, Condition, IsLoopBranch, Context);
539
23.7k
}
540
541
bool ScopDetection::isValidCallInst(CallInst &CI,
542
194
                                    DetectionContext &Context) const {
543
194
  if (CI.doesNotReturn())
544
0
    return false;
545
194
546
194
  
if (194
CI.doesNotAccessMemory()194
)
547
89
    return true;
548
194
549
105
  
if (auto *105
II105
= dyn_cast<IntrinsicInst>(&CI))
550
66
    
if (66
isValidIntrinsicInst(*II, Context)66
)
551
54
      return true;
552
105
553
51
  Function *CalledFunction = CI.getCalledFunction();
554
51
555
51
  // Indirect calls are not supported.
556
51
  if (CalledFunction == nullptr)
557
0
    return false;
558
51
559
51
  
if (51
AllowModrefCall51
)
{39
560
39
    switch (AA->getModRefBehavior(CalledFunction)) {
561
0
    case FMRB_UnknownModRefBehavior:
562
0
      return false;
563
21
    case FMRB_DoesNotAccessMemory:
564
21
    case FMRB_OnlyReadsMemory:
565
21
      // Implicitly disable delinearization since we have an unknown
566
21
      // accesses with an unknown access function.
567
21
      Context.HasUnknownAccess = true;
568
21
      Context.AST.add(&CI);
569
21
      return true;
570
18
    case FMRB_OnlyReadsArgumentPointees:
571
18
    case FMRB_OnlyAccessesArgumentPointees:
572
56
      for (const auto &Arg : CI.arg_operands()) {
573
56
        if (!Arg->getType()->isPointerTy())
574
28
          continue;
575
56
576
56
        // Bail if a pointer argument has a base address not known to
577
56
        // ScalarEvolution. Note that a zero pointer is acceptable.
578
28
        auto *ArgSCEV = SE->getSCEVAtScope(Arg, LI->getLoopFor(CI.getParent()));
579
28
        if (ArgSCEV->isZero())
580
14
          continue;
581
28
582
14
        auto *BP = dyn_cast<SCEVUnknown>(SE->getPointerBase(ArgSCEV));
583
14
        if (!BP)
584
0
          return false;
585
14
586
14
        // Implicitly disable delinearization since we have an unknown
587
14
        // accesses with an unknown access function.
588
14
        Context.HasUnknownAccess = true;
589
14
      }
590
18
591
18
      Context.AST.add(&CI);
592
18
      return true;
593
0
    case FMRB_DoesNotReadMemory:
594
0
    case FMRB_OnlyAccessesInaccessibleMem:
595
0
    case FMRB_OnlyAccessesInaccessibleOrArgMem:
596
0
      return false;
597
39
    }
598
39
  }
599
51
600
12
  return false;
601
51
}
602
603
bool ScopDetection::isValidIntrinsicInst(IntrinsicInst &II,
604
66
                                         DetectionContext &Context) const {
605
66
  if (isIgnoredIntrinsic(&II))
606
27
    return true;
607
66
608
66
  // The closest loop surrounding the call instruction.
609
39
  Loop *L = LI->getLoopFor(II.getParent());
610
39
611
39
  // The access function and base pointer for memory intrinsics.
612
39
  const SCEV *AF;
613
39
  const SCEVUnknown *BP;
614
39
615
39
  switch (II.getIntrinsicID()) {
616
39
  // Memory intrinsics that can be represented are supported.
617
16
  case llvm::Intrinsic::memmove:
618
16
  case llvm::Intrinsic::memcpy:
619
16
    AF = SE->getSCEVAtScope(cast<MemTransferInst>(II).getSource(), L);
620
16
    if (
!AF->isZero()16
)
{16
621
16
      BP = dyn_cast<SCEVUnknown>(SE->getPointerBase(AF));
622
16
      // Bail if the source pointer is not valid.
623
16
      if (!isValidAccess(&II, AF, BP, Context))
624
0
        return false;
625
16
    }
626
16
  // Fall through
627
33
  case llvm::Intrinsic::memset:
628
33
    AF = SE->getSCEVAtScope(cast<MemIntrinsic>(II).getDest(), L);
629
33
    if (
!AF->isZero()33
)
{29
630
29
      BP = dyn_cast<SCEVUnknown>(SE->getPointerBase(AF));
631
29
      // Bail if the destination pointer is not valid.
632
29
      if (!isValidAccess(&II, AF, BP, Context))
633
0
        return false;
634
29
    }
635
33
636
33
    // Bail if the length is not affine.
637
33
    
if (33
!isAffine(SE->getSCEVAtScope(cast<MemIntrinsic>(II).getLength(), L), L,33
638
33
                  Context))
639
6
      return false;
640
33
641
27
    return true;
642
6
  default:
643
6
    break;
644
39
  }
645
39
646
6
  return false;
647
39
}
648
649
bool ScopDetection::isInvariant(Value &Val, const Region &Reg,
650
10.5k
                                DetectionContext &Ctx) const {
651
10.5k
  // A reference to function argument or constant value is invariant.
652
10.5k
  if (
isa<Argument>(Val) || 10.5k
isa<Constant>(Val)3.08k
)
653
8.18k
    return true;
654
10.5k
655
2.38k
  Instruction *I = dyn_cast<Instruction>(&Val);
656
2.38k
  if (!I)
657
0
    return false;
658
2.38k
659
2.38k
  
if (2.38k
!Reg.contains(I)2.38k
)
660
1.93k
    return true;
661
2.38k
662
2.38k
  // Loads within the SCoP may read arbitrary values, need to hoist them. If it
663
2.38k
  // is not hoistable, it will be rejected later, but here we assume it is and
664
2.38k
  // that makes the value invariant.
665
444
  
if (auto 444
LI444
= dyn_cast<LoadInst>(I))
{434
666
434
    Ctx.RequiredILS.insert(LI);
667
434
    return true;
668
434
  }
669
444
670
10
  return false;
671
444
}
672
673
/// Remove smax of smax(0, size) expressions from a SCEV expression and
674
/// register the '...' components.
675
///
676
/// Array access expressions as they are generated by gfortran contain smax(0,
677
/// size) expressions that confuse the 'normal' delinearization algorithm.
678
/// However, if we extract such expressions before the normal delinearization
679
/// takes place they can actually help to identify array size expressions in
680
/// fortran accesses. For the subsequently following delinearization the smax(0,
681
/// size) component can be replaced by just 'size'. This is correct as we will
682
/// always add and verify the assumption that for all subscript expressions
683
/// 'exp' the inequality 0 <= exp < size holds. Hence, we will also verify
684
/// that 0 <= size, which means smax(0, size) == size.
685
class SCEVRemoveMax : public SCEVRewriteVisitor<SCEVRemoveMax> {
686
public:
687
  static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
688
1.22k
                             std::vector<const SCEV *> *Terms = nullptr) {
689
1.22k
    SCEVRemoveMax Rewriter(SE, Terms);
690
1.22k
    return Rewriter.visit(Scev);
691
1.22k
  }
692
693
  SCEVRemoveMax(ScalarEvolution &SE, std::vector<const SCEV *> *Terms)
694
1.22k
      : SCEVRewriteVisitor(SE), Terms(Terms) {}
695
696
56
  const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
697
56
    if (
(Expr->getNumOperands() == 2) && 56
Expr->getOperand(0)->isZero()56
)
{56
698
56
      auto Res = visit(Expr->getOperand(1));
699
56
      if (Terms)
700
28
        (*Terms).push_back(Res);
701
56
      return Res;
702
56
    }
703
56
704
0
    return Expr;
705
56
  }
706
707
private:
708
  std::vector<const SCEV *> *Terms;
709
};
710
711
SmallVector<const SCEV *, 4>
712
ScopDetection::getDelinearizationTerms(DetectionContext &Context,
713
391
                                       const SCEVUnknown *BasePointer) const {
714
391
  SmallVector<const SCEV *, 4> Terms;
715
633
  for (const auto &Pair : Context.Accesses[BasePointer]) {
716
633
    std::vector<const SCEV *> MaxTerms;
717
633
    SCEVRemoveMax::rewrite(Pair.second, *SE, &MaxTerms);
718
633
    if (
MaxTerms.size() > 0633
)
{16
719
16
      Terms.insert(Terms.begin(), MaxTerms.begin(), MaxTerms.end());
720
16
      continue;
721
16
    }
722
633
    // In case the outermost expression is a plain add, we check if any of its
723
633
    // terms has the form 4 * %inst * %param * %param ..., aka a term that
724
633
    // contains a product between a parameter and an instruction that is
725
633
    // inside the scop. Such instructions, if allowed at all, are instructions
726
633
    // SCEV can not represent, but Polly is still looking through. As a
727
633
    // result, these instructions can depend on induction variables and are
728
633
    // most likely no array sizes. However, terms that are multiplied with
729
633
    // them are likely candidates for array sizes.
730
617
    
if (auto *617
AF617
= dyn_cast<SCEVAddExpr>(Pair.second))
{8
731
17
      for (auto Op : AF->operands()) {
732
17
        if (auto *AF2 = dyn_cast<SCEVAddRecExpr>(Op))
733
4
          SE->collectParametricTerms(AF2, Terms);
734
17
        if (auto *
AF217
= dyn_cast<SCEVMulExpr>(Op))
{8
735
8
          SmallVector<const SCEV *, 0> Operands;
736
8
737
24
          for (auto *MulOp : AF2->operands()) {
738
24
            if (auto *Const = dyn_cast<SCEVConstant>(MulOp))
739
6
              Operands.push_back(Const);
740
24
            if (auto *
Unknown24
= dyn_cast<SCEVUnknown>(MulOp))
{16
741
16
              if (auto *
Inst16
= dyn_cast<Instruction>(Unknown->getValue()))
{4
742
4
                if (!Context.CurRegion.contains(Inst))
743
0
                  Operands.push_back(MulOp);
744
4
745
12
              } else {
746
12
                Operands.push_back(MulOp);
747
12
              }
748
16
            }
749
24
          }
750
8
          if (Operands.size())
751
7
            Terms.push_back(SE->getMulExpr(Operands));
752
8
        }
753
17
      }
754
8
    }
755
617
    if (Terms.empty())
756
433
      SE->collectParametricTerms(Pair.second, Terms);
757
617
  }
758
391
  return Terms;
759
391
}
760
761
bool ScopDetection::hasValidArraySizes(DetectionContext &Context,
762
                                       SmallVectorImpl<const SCEV *> &Sizes,
763
                                       const SCEVUnknown *BasePointer,
764
391
                                       Loop *Scope) const {
765
391
  Value *BaseValue = BasePointer->getValue();
766
391
  Region &CurRegion = Context.CurRegion;
767
977
  for (const SCEV *DelinearizedSize : Sizes) {
768
977
    if (
!isAffine(DelinearizedSize, Scope, Context)977
)
{10
769
10
      Sizes.clear();
770
10
      break;
771
10
    }
772
967
    
if (auto *967
Unknown967
= dyn_cast<SCEVUnknown>(DelinearizedSize))
{589
773
589
      auto *V = dyn_cast<Value>(Unknown->getValue());
774
589
      if (auto *
Load589
= dyn_cast<LoadInst>(V))
{176
775
176
        if (Context.CurRegion.contains(Load) &&
776
24
            isHoistableLoad(Load, CurRegion, *LI, *SE, *DT))
777
24
          Context.RequiredILS.insert(Load);
778
176
        continue;
779
176
      }
780
589
    }
781
791
    
if (791
hasScalarDepsInsideRegion(DelinearizedSize, &CurRegion, Scope, false)791
)
782
0
      return invalid<ReportNonAffineAccess>(
783
0
          Context, /*Assert=*/true, DelinearizedSize,
784
0
          Context.Accesses[BasePointer].front().first, BaseValue);
785
791
  }
786
391
787
391
  // No array shape derived.
788
391
  
if (391
Sizes.empty()391
)
{61
789
61
    if (AllowNonAffine)
790
35
      return true;
791
61
792
29
    
for (const auto &Pair : Context.Accesses[BasePointer]) 26
{29
793
29
      const Instruction *Insn = Pair.first;
794
29
      const SCEV *AF = Pair.second;
795
29
796
29
      if (
!isAffine(AF, Scope, Context)29
)
{28
797
28
        invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF, Insn,
798
28
                                       BaseValue);
799
28
        if (!KeepGoing)
800
25
          return false;
801
28
      }
802
29
    }
803
1
    return false;
804
26
  }
805
330
  return true;
806
391
}
807
808
// We first store the resulting memory accesses in TempMemoryAccesses. Only
809
// if the access functions for all memory accesses have been successfully
810
// delinearized we continue. Otherwise, we either report a failure or, if
811
// non-affine accesses are allowed, we drop the information. In case the
812
// information is dropped the memory accesses need to be overapproximated
813
// when translated to a polyhedral representation.
814
bool ScopDetection::computeAccessFunctions(
815
    DetectionContext &Context, const SCEVUnknown *BasePointer,
816
365
    std::shared_ptr<ArrayShape> Shape) const {
817
365
  Value *BaseValue = BasePointer->getValue();
818
365
  bool BasePtrHasNonAffine = false;
819
365
  MapInsnToMemAcc TempMemoryAccesses;
820
594
  for (const auto &Pair : Context.Accesses[BasePointer]) {
821
594
    const Instruction *Insn = Pair.first;
822
594
    auto *AF = Pair.second;
823
594
    AF = SCEVRemoveMax::rewrite(AF, *SE);
824
594
    bool IsNonAffine = false;
825
594
    TempMemoryAccesses.insert(std::make_pair(Insn, MemAcc(Insn, Shape)));
826
594
    MemAcc *Acc = &TempMemoryAccesses.find(Insn)->second;
827
594
    auto *Scope = LI->getLoopFor(Insn->getParent());
828
594
829
594
    if (
!AF594
)
{0
830
0
      if (isAffine(Pair.second, Scope, Context))
831
0
        Acc->DelinearizedSubscripts.push_back(Pair.second);
832
0
      else
833
0
        IsNonAffine = true;
834
594
    } else {
835
594
      SE->computeAccessFunctions(AF, Acc->DelinearizedSubscripts,
836
594
                                 Shape->DelinearizedSizes);
837
594
      if (Acc->DelinearizedSubscripts.size() == 0)
838
78
        IsNonAffine = true;
839
594
      for (const SCEV *S : Acc->DelinearizedSubscripts)
840
1.54k
        
if (1.54k
!isAffine(S, Scope, Context)1.54k
)
841
4
          IsNonAffine = true;
842
594
    }
843
594
844
594
    // (Possibly) report non affine access
845
594
    if (
IsNonAffine594
)
{82
846
82
      BasePtrHasNonAffine = true;
847
82
      if (!AllowNonAffine)
848
6
        invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, Pair.second,
849
6
                                       Insn, BaseValue);
850
82
      if (
!KeepGoing && 82
!AllowNonAffine70
)
851
2
        return false;
852
82
    }
853
594
  }
854
365
855
363
  
if (363
!BasePtrHasNonAffine363
)
856
323
    Context.InsnToMemAcc.insert(TempMemoryAccesses.begin(),
857
323
                                TempMemoryAccesses.end());
858
363
859
363
  return true;
860
365
}
861
862
bool ScopDetection::hasBaseAffineAccesses(DetectionContext &Context,
863
                                          const SCEVUnknown *BasePointer,
864
391
                                          Loop *Scope) const {
865
391
  auto Shape = std::shared_ptr<ArrayShape>(new ArrayShape(BasePointer));
866
391
867
391
  auto Terms = getDelinearizationTerms(Context, BasePointer);
868
391
869
391
  SE->findArrayDimensions(Terms, Shape->DelinearizedSizes,
870
391
                          Context.ElementSize[BasePointer]);
871
391
872
391
  if (!hasValidArraySizes(Context, Shape->DelinearizedSizes, BasePointer,
873
391
                          Scope))
874
26
    return false;
875
391
876
365
  return computeAccessFunctions(Context, BasePointer, Shape);
877
391
}
878
879
2.62k
bool ScopDetection::hasAffineMemoryAccesses(DetectionContext &Context) const {
880
2.62k
  // TODO: If we have an unknown access and other non-affine accesses we do
881
2.62k
  //       not try to delinearize them for now.
882
2.62k
  if (
Context.HasUnknownAccess && 2.62k
!Context.NonAffineAccesses.empty()35
)
883
12
    return AllowNonAffine;
884
2.62k
885
2.61k
  
for (auto &Pair : Context.NonAffineAccesses) 2.61k
{391
886
391
    auto *BasePointer = Pair.first;
887
391
    auto *Scope = Pair.second;
888
391
    if (
!hasBaseAffineAccesses(Context, BasePointer, Scope)391
)
{28
889
28
      if (KeepGoing)
890
1
        continue;
891
28
      else
892
27
        return false;
893
28
    }
894
391
  }
895
2.58k
  return true;
896
2.61k
}
897
898
bool ScopDetection::isValidAccess(Instruction *Inst, const SCEV *AF,
899
                                  const SCEVUnknown *BP,
900
10.5k
                                  DetectionContext &Context) const {
901
10.5k
902
10.5k
  if (!BP)
903
0
    return invalid<ReportNoBasePtr>(Context, /*Assert=*/true, Inst);
904
10.5k
905
10.5k
  auto *BV = BP->getValue();
906
10.5k
  if (isa<UndefValue>(BV))
907
5
    return invalid<ReportUndefBasePtr>(Context, /*Assert=*/true, Inst);
908
10.5k
909
10.5k
  // FIXME: Think about allowing IntToPtrInst
910
10.5k
  
if (IntToPtrInst *10.5k
Inst10.5k
= dyn_cast<IntToPtrInst>(BV))
911
1
    return invalid<ReportIntToPtr>(Context, /*Assert=*/true, Inst);
912
10.5k
913
10.5k
  // Check that the base address of the access is invariant in the current
914
10.5k
  // region.
915
10.5k
  
if (10.5k
!isInvariant(*BV, Context.CurRegion, Context)10.5k
)
916
10
    return invalid<ReportVariantBasePtr>(Context, /*Assert=*/true, BV, Inst);
917
10.5k
918
10.5k
  AF = SE->getMinusSCEV(AF, BP);
919
10.5k
920
10.5k
  const SCEV *Size;
921
10.5k
  if (
!isa<MemIntrinsic>(Inst)10.5k
)
{10.5k
922
10.5k
    Size = SE->getElementSize(Inst);
923
45
  } else {
924
45
    auto *SizeTy =
925
45
        SE->getEffectiveSCEVType(PointerType::getInt8PtrTy(SE->getContext()));
926
45
    Size = SE->getConstant(SizeTy, 8);
927
45
  }
928
10.5k
929
10.5k
  if (
Context.ElementSize[BP]10.5k
)
{6.09k
930
6.09k
    if (
!AllowDifferentTypes && 6.09k
Context.ElementSize[BP] != Size0
)
931
0
      return invalid<ReportDifferentArrayElementSize>(Context, /*Assert=*/true,
932
0
                                                      Inst, BV);
933
6.09k
934
6.09k
    Context.ElementSize[BP] = SE->getSMinExpr(Size, Context.ElementSize[BP]);
935
4.46k
  } else {
936
4.46k
    Context.ElementSize[BP] = Size;
937
4.46k
  }
938
10.5k
939
10.5k
  bool IsVariantInNonAffineLoop = false;
940
10.5k
  SetVector<const Loop *> Loops;
941
10.5k
  findLoops(AF, Loops);
942
10.5k
  for (const Loop *L : Loops)
943
6.31k
    
if (6.31k
Context.BoxedLoopsSet.count(L)6.31k
)
944
39
      IsVariantInNonAffineLoop = true;
945
10.5k
946
10.5k
  auto *Scope = LI->getLoopFor(Inst->getParent());
947
10.5k
  bool IsAffine = !IsVariantInNonAffineLoop && isAffine(AF, Scope, Context);
948
10.5k
  // Do not try to delinearize memory intrinsics and force them to be affine.
949
10.5k
  if (
isa<MemIntrinsic>(Inst) && 10.5k
!IsAffine45
)
{0
950
0
    return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF, Inst,
951
0
                                          BV);
952
10.5k
  } else 
if (10.5k
PollyDelinearize && 10.5k
!IsVariantInNonAffineLoop10.5k
)
{10.4k
953
10.4k
    Context.Accesses[BP].push_back({Inst, AF});
954
10.4k
955
10.4k
    if (!IsAffine)
956
600
      Context.NonAffineAccesses.insert(
957
600
          std::make_pair(BP, LI->getLoopFor(Inst->getParent())));
958
68
  } else 
if (68
!AllowNonAffine && 68
!IsAffine28
)
{22
959
22
    return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF, Inst,
960
22
                                          BV);
961
22
  }
962
10.5k
963
10.5k
  
if (10.5k
IgnoreAliasing10.5k
)
964
428
    return true;
965
10.5k
966
10.5k
  // Check if the base pointer of the memory access does alias with
967
10.5k
  // any other pointer. This cannot be handled at the moment.
968
10.1k
  AAMDNodes AATags;
969
10.1k
  Inst->getAAMetadata(AATags);
970
10.1k
  AliasSet &AS = Context.AST.getAliasSetForPointer(
971
10.1k
      BP->getValue(), MemoryLocation::UnknownSize, AATags);
972
10.1k
973
10.1k
  if (
!AS.isMustAlias()10.1k
)
{2.93k
974
2.93k
    if (
PollyUseRuntimeAliasChecks2.93k
)
{2.93k
975
2.93k
      bool CanBuildRunTimeCheck = true;
976
2.93k
      // The run-time alias check places code that involves the base pointer at
977
2.93k
      // the beginning of the SCoP. This breaks if the base pointer is defined
978
2.93k
      // inside the scop. Hence, we can only create a run-time check if we are
979
2.93k
      // sure the base pointer is not an instruction defined inside the scop.
980
2.93k
      // However, we can ignore loads that will be hoisted.
981
10.5k
      for (const auto &Ptr : AS) {
982
10.5k
        Instruction *Inst = dyn_cast<Instruction>(Ptr.getValue());
983
10.5k
        if (
Inst && 10.5k
Context.CurRegion.contains(Inst)2.22k
)
{2.09k
984
2.09k
          auto *Load = dyn_cast<LoadInst>(Inst);
985
2.09k
          if (
Load && 2.09k
isHoistableLoad(Load, Context.CurRegion, *LI, *SE, *DT)2.09k
)
{2.09k
986
2.09k
            Context.RequiredILS.insert(Load);
987
2.09k
            continue;
988
2.09k
          }
989
2.09k
990
2
          CanBuildRunTimeCheck = false;
991
2
          break;
992
2.09k
        }
993
10.5k
      }
994
2.93k
995
2.93k
      if (CanBuildRunTimeCheck)
996
2.93k
        return true;
997
2.93k
    }
998
3
    return invalid<ReportAlias>(Context, /*Assert=*/true, Inst, AS);
999
2.93k
  }
1000
10.1k
1001
7.17k
  return true;
1002
10.1k
}
1003
1004
bool ScopDetection::isValidMemoryAccess(MemAccInst Inst,
1005
10.5k
                                        DetectionContext &Context) const {
1006
10.5k
  Value *Ptr = Inst.getPointerOperand();
1007
10.5k
  Loop *L = LI->getLoopFor(Inst->getParent());
1008
10.5k
  const SCEV *AccessFunction = SE->getSCEVAtScope(Ptr, L);
1009
10.5k
  const SCEVUnknown *BasePointer;
1010
10.5k
1011
10.5k
  BasePointer = dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
1012
10.5k
1013
10.5k
  return isValidAccess(Inst, AccessFunction, BasePointer, Context);
1014
10.5k
}
1015
1016
bool ScopDetection::isValidInstruction(Instruction &Inst,
1017
45.4k
                                       DetectionContext &Context) const {
1018
84.9k
  for (auto &Op : Inst.operands()) {
1019
84.9k
    auto *OpInst = dyn_cast<Instruction>(&Op);
1020
84.9k
1021
84.9k
    if (!OpInst)
1022
34.5k
      continue;
1023
84.9k
1024
50.4k
    
if (50.4k
isErrorBlock(*OpInst->getParent(), Context.CurRegion, *LI, *DT)50.4k
)
1025
2
      return false;
1026
50.4k
  }
1027
45.4k
1028
45.4k
  
if (45.4k
isa<LandingPadInst>(&Inst) || 45.4k
isa<ResumeInst>(&Inst)45.4k
)
1029
0
    return false;
1030
45.4k
1031
45.4k
  // We only check the call instruction but not invoke instruction.
1032
45.4k
  
if (CallInst *45.4k
CI45.4k
= dyn_cast<CallInst>(&Inst))
{194
1033
194
    if (isValidCallInst(*CI, Context))
1034
182
      return true;
1035
194
1036
12
    return invalid<ReportFuncCall>(Context, /*Assert=*/true, &Inst);
1037
194
  }
1038
45.4k
1039
45.2k
  
if (45.2k
!Inst.mayReadOrWriteMemory()45.2k
)
{34.6k
1040
34.6k
    if (!isa<AllocaInst>(Inst))
1041
34.6k
      return true;
1042
34.6k
1043
0
    return invalid<ReportAlloca>(Context, /*Assert=*/true, &Inst);
1044
34.6k
  }
1045
45.2k
1046
45.2k
  // Check the access function.
1047
10.5k
  
if (auto 10.5k
MemInst10.5k
= MemAccInst::dyn_cast(Inst))
{10.5k
1048
10.5k
    Context.hasStores |= isa<StoreInst>(MemInst);
1049
10.5k
    Context.hasLoads |= isa<LoadInst>(MemInst);
1050
10.5k
    if (!MemInst.isSimple())
1051
0
      return invalid<ReportNonSimpleMemoryAccess>(Context, /*Assert=*/true,
1052
0
                                                  &Inst);
1053
10.5k
1054
10.5k
    return isValidMemoryAccess(MemInst, Context);
1055
10.5k
  }
1056
10.5k
1057
10.5k
  // We do not know this instruction, therefore we assume it is invalid.
1058
51
  return invalid<ReportUnknownInst>(Context, /*Assert=*/true, &Inst);
1059
10.5k
}
1060
1061
/// Check whether @p L has exiting blocks.
1062
///
1063
/// @param L The loop of interest
1064
///
1065
/// @return True if the loop has exiting blocks, false otherwise.
1066
4.40k
static bool hasExitingBlocks(Loop *L) {
1067
4.40k
  SmallVector<BasicBlock *, 4> ExitingBlocks;
1068
4.40k
  L->getExitingBlocks(ExitingBlocks);
1069
4.40k
  return !ExitingBlocks.empty();
1070
4.40k
}
1071
1072
bool ScopDetection::canUseISLTripCount(Loop *L,
1073
4.38k
                                       DetectionContext &Context) const {
1074
4.38k
  // Ensure the loop has valid exiting blocks as well as latches, otherwise we
1075
4.38k
  // need to overapproximate it as a boxed loop.
1076
4.38k
  SmallVector<BasicBlock *, 4> LoopControlBlocks;
1077
4.38k
  L->getExitingBlocks(LoopControlBlocks);
1078
4.38k
  L->getLoopLatches(LoopControlBlocks);
1079
8.64k
  for (BasicBlock *ControlBB : LoopControlBlocks) {
1080
8.64k
    if (!isValidCFG(*ControlBB, true, false, Context))
1081
205
      return false;
1082
8.64k
  }
1083
4.38k
1084
4.38k
  // We can use ISL to compute the trip count of L.
1085
4.18k
  return true;
1086
4.38k
}
1087
1088
4.40k
bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const {
1089
4.40k
  // Loops that contain part but not all of the blocks of a region cannot be
1090
4.40k
  // handled by the schedule generation. Such loop constructs can happen
1091
4.40k
  // because a region can contain BBs that have no path to the exit block
1092
4.40k
  // (Infinite loops, UnreachableInst), but such blocks are never part of a
1093
4.40k
  // loop.
1094
4.40k
  //
1095
4.40k
  // _______________
1096
4.40k
  // | Loop Header | <-----------.
1097
4.40k
  // ---------------             |
1098
4.40k
  //        |                    |
1099
4.40k
  // _______________       ______________
1100
4.40k
  // | RegionEntry |-----> | RegionExit |----->
1101
4.40k
  // ---------------       --------------
1102
4.40k
  //        |
1103
4.40k
  // _______________
1104
4.40k
  // | EndlessLoop | <--.
1105
4.40k
  // ---------------    |
1106
4.40k
  //       |            |
1107
4.40k
  //       \------------/
1108
4.40k
  //
1109
4.40k
  // In the example above, the loop (LoopHeader,RegionEntry,RegionExit) is
1110
4.40k
  // neither entirely contained in the region RegionEntry->RegionExit
1111
4.40k
  // (containing RegionEntry,EndlessLoop) nor is the region entirely contained
1112
4.40k
  // in the loop.
1113
4.40k
  // The block EndlessLoop is contained in the region because Region::contains
1114
4.40k
  // tests whether it is not dominated by RegionExit. This is probably to not
1115
4.40k
  // having to query the PostdominatorTree. Instead of an endless loop, a dead
1116
4.40k
  // end can also be formed by an UnreachableInst. This case is already caught
1117
4.40k
  // by isErrorBlock(). We hence only have to reject endless loops here.
1118
4.40k
  if (!hasExitingBlocks(L))
1119
16
    return invalid<ReportLoopHasNoExit>(Context, /*Assert=*/true, L);
1120
4.40k
1121
4.38k
  
if (4.38k
canUseISLTripCount(L, Context)4.38k
)
1122
4.18k
    return true;
1123
4.38k
1124
205
  
if (205
AllowNonAffineSubLoops && 205
AllowNonAffineSubRegions62
)
{62
1125
62
    Region *R = RI->getRegionFor(L->getHeader());
1126
73
    while (
R != &Context.CurRegion && 73
!R->contains(L)57
)
1127
11
      R = R->getParent();
1128
62
1129
62
    if (addOverApproximatedRegion(R, Context))
1130
62
      return true;
1131
62
  }
1132
205
1133
143
  const SCEV *LoopCount = SE->getBackedgeTakenCount(L);
1134
143
  return invalid<ReportLoopBound>(Context, /*Assert=*/true, L, LoopCount);
1135
205
}
1136
1137
/// Return the number of loops in @p L (incl. @p L) that have a trip
1138
///        count that is not known to be less than @MinProfitableTrips.
1139
ScopDetection::LoopStats
1140
ScopDetection::countBeneficialSubLoops(Loop *L, ScalarEvolution &SE,
1141
4.35k
                                       unsigned MinProfitableTrips) {
1142
4.35k
  auto *TripCount = SE.getBackedgeTakenCount(L);
1143
4.35k
1144
4.35k
  int NumLoops = 1;
1145
4.35k
  int MaxLoopDepth = 1;
1146
4.35k
  if (auto *TripCountC = dyn_cast<SCEVConstant>(TripCount))
1147
2.44k
    
if (2.44k
TripCountC->getType()->getScalarSizeInBits() <= 642.44k
)
1148
2.43k
      
if (2.43k
TripCountC->getValue()->getZExtValue() <= MinProfitableTrips2.43k
)
1149
183
        NumLoops -= 1;
1150
4.35k
1151
1.20k
  for (auto &SubLoop : *L) {
1152
1.20k
    LoopStats Stats = countBeneficialSubLoops(SubLoop, SE, MinProfitableTrips);
1153
1.20k
    NumLoops += Stats.NumLoops;
1154
1.20k
    MaxLoopDepth = std::max(MaxLoopDepth, Stats.MaxDepth + 1);
1155
1.20k
  }
1156
4.35k
1157
4.35k
  return {NumLoops, MaxLoopDepth};
1158
4.35k
}
1159
1160
ScopDetection::LoopStats
1161
ScopDetection::countBeneficialLoops(Region *R, ScalarEvolution &SE,
1162
3.00k
                                    LoopInfo &LI, unsigned MinProfitableTrips) {
1163
3.00k
  int LoopNum = 0;
1164
3.00k
  int MaxLoopDepth = 0;
1165
3.00k
1166
3.00k
  auto L = LI.getLoopFor(R->getEntry());
1167
1.65k
  L = L ? 
R->outermostLoopInRegion(L)1.65k
:
nullptr1.34k
;
1168
1.58k
  L = L ? 
L->getParentLoop()1.58k
:
nullptr1.41k
;
1169
3.00k
1170
3.00k
  auto SubLoops =
1171
2.95k
      L ? 
L->getSubLoopsVector()49
:
std::vector<Loop *>(LI.begin(), LI.end())2.95k
;
1172
3.00k
1173
3.00k
  for (auto &SubLoop : SubLoops)
1174
3.33k
    
if (3.33k
R->contains(SubLoop)3.33k
)
{3.14k
1175
3.14k
      LoopStats Stats =
1176
3.14k
          countBeneficialSubLoops(SubLoop, SE, MinProfitableTrips);
1177
3.14k
      LoopNum += Stats.NumLoops;
1178
3.14k
      MaxLoopDepth = std::max(MaxLoopDepth, Stats.MaxDepth);
1179
3.14k
    }
1180
3.00k
1181
3.00k
  return {LoopNum, MaxLoopDepth};
1182
3.00k
}
1183
1184
1.02k
Region *ScopDetection::expandRegion(Region &R) {
1185
1.02k
  // Initial no valid region was found (greater than R)
1186
1.02k
  std::unique_ptr<Region> LastValidRegion;
1187
1.02k
  auto ExpandedRegion = std::unique_ptr<Region>(R.getExpandedRegion());
1188
1.02k
1189
1.02k
  DEBUG(dbgs() << "\tExpanding " << R.getNameStr() << "\n");
1190
1.02k
1191
1.45k
  while (
ExpandedRegion1.45k
)
{479
1192
479
    const auto &It = DetectionContextMap.insert(std::make_pair(
1193
479
        getBBPairForRegion(ExpandedRegion.get()),
1194
479
        DetectionContext(*ExpandedRegion, *AA, false /*verifying*/)));
1195
479
    DetectionContext &Context = It.first->second;
1196
479
    DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n");
1197
479
    // Only expand when we did not collect errors.
1198
479
1199
479
    if (
!Context.Log.hasErrors()479
)
{479
1200
479
      // If the exit is valid check all blocks
1201
479
      //  - if true, a valid region was found => store it + keep expanding
1202
479
      //  - if false, .tbd. => stop  (should this really end the loop?)
1203
479
      if (
!allBlocksValid(Context) || 479
Context.Log.hasErrors()433
)
{47
1204
47
        removeCachedResults(*ExpandedRegion);
1205
47
        DetectionContextMap.erase(It.first);
1206
47
        break;
1207
47
      }
1208
479
1209
479
      // Store this region, because it is the greatest valid (encountered so
1210
479
      // far).
1211
432
      
if (432
LastValidRegion432
)
{237
1212
237
        removeCachedResults(*LastValidRegion);
1213
237
        DetectionContextMap.erase(getBBPairForRegion(LastValidRegion.get()));
1214
237
      }
1215
432
      LastValidRegion = std::move(ExpandedRegion);
1216
432
1217
432
      // Create and test the next greater region (if any)
1218
432
      ExpandedRegion =
1219
432
          std::unique_ptr<Region>(LastValidRegion->getExpandedRegion());
1220
432
1221
0
    } else {
1222
0
      // Create and test the next greater region (if any)
1223
0
      removeCachedResults(*ExpandedRegion);
1224
0
      DetectionContextMap.erase(It.first);
1225
0
      ExpandedRegion =
1226
0
          std::unique_ptr<Region>(ExpandedRegion->getExpandedRegion());
1227
0
    }
1228
479
  }
1229
1.02k
1230
1.02k
  DEBUG({
1231
1.02k
    if (LastValidRegion)
1232
1.02k
      dbgs() << "\tto " << LastValidRegion->getNameStr() << "\n";
1233
1.02k
    else
1234
1.02k
      dbgs() << "\tExpanding " << R.getNameStr() << " failed\n";
1235
1.02k
  });
1236
1.02k
1237
1.02k
  return LastValidRegion.release();
1238
1.02k
}
1239
40
static bool regionWithoutLoops(Region &R, LoopInfo *LI) {
1240
40
  for (const BasicBlock *BB : R.blocks())
1241
44
    
if (44
R.contains(LI->getLoopFor(BB))44
)
1242
39
      return false;
1243
40
1244
1
  return true;
1245
40
}
1246
1247
473
void ScopDetection::removeCachedResultsRecursively(const Region &R) {
1248
464
  for (auto &SubRegion : R) {
1249
464
    if (
ValidRegions.count(SubRegion.get())464
)
{186
1250
186
      removeCachedResults(*SubRegion.get());
1251
186
    } else
1252
278
      removeCachedResultsRecursively(*SubRegion);
1253
464
  }
1254
473
}
1255
1256
2.20k
void ScopDetection::removeCachedResults(const Region &R) {
1257
2.20k
  ValidRegions.remove(&R);
1258
2.20k
}
1259
1260
2.75k
void ScopDetection::findScops(Region &R) {
1261
2.75k
  const auto &It = DetectionContextMap.insert(std::make_pair(
1262
2.75k
      getBBPairForRegion(&R), DetectionContext(R, *AA, false /*verifying*/)));
1263
2.75k
  DetectionContext &Context = It.first->second;
1264
2.75k
1265
2.75k
  bool RegionIsValid = false;
1266
2.75k
  if (
!PollyProcessUnprofitable && 2.75k
regionWithoutLoops(R, LI)40
)
1267
1
    invalid<ReportUnprofitable>(Context, /*Assert=*/true, &R);
1268
2.75k
  else
1269
2.75k
    RegionIsValid = isValidRegion(Context);
1270
2.75k
1271
1.21k
  bool HasErrors = !RegionIsValid || Context.Log.size() > 0;
1272
2.75k
1273
2.75k
  if (
HasErrors2.75k
)
{1.54k
1274
1.54k
    removeCachedResults(R);
1275
1.21k
  } else {
1276
1.21k
    ValidRegions.insert(&R);
1277
1.21k
    return;
1278
1.21k
  }
1279
2.75k
1280
1.54k
  for (auto &SubRegion : R)
1281
1.63k
    findScops(*SubRegion);
1282
1.54k
1283
1.54k
  // Try to expand regions.
1284
1.54k
  //
1285
1.54k
  // As the region tree normally only contains canonical regions, non canonical
1286
1.54k
  // regions that form a Scop are not found. Therefore, those non canonical
1287
1.54k
  // regions are checked by expanding the canonical ones.
1288
1.54k
1289
1.54k
  std::vector<Region *> ToExpand;
1290
1.54k
1291
1.54k
  for (auto &SubRegion : R)
1292
1.63k
    ToExpand.push_back(SubRegion.get());
1293
1.54k
1294
1.63k
  for (Region *CurrentRegion : ToExpand) {
1295
1.63k
    // Skip invalid regions. Regions may become invalid, if they are element of
1296
1.63k
    // an already expanded region.
1297
1.63k
    if (!ValidRegions.count(CurrentRegion))
1298
609
      continue;
1299
1.63k
1300
1.63k
    // Skip regions that had errors.
1301
1.02k
    bool HadErrors = lookupRejectionLog(CurrentRegion)->hasErrors();
1302
1.02k
    if (HadErrors)
1303
0
      continue;
1304
1.02k
1305
1.02k
    Region *ExpandedR = expandRegion(*CurrentRegion);
1306
1.02k
1307
1.02k
    if (!ExpandedR)
1308
832
      continue;
1309
1.02k
1310
195
    R.addSubRegion(ExpandedR, true);
1311
195
    ValidRegions.insert(ExpandedR);
1312
195
    removeCachedResults(*CurrentRegion);
1313
195
    removeCachedResultsRecursively(*ExpandedR);
1314
195
  }
1315
1.54k
}
1316
1317
2.94k
bool ScopDetection::allBlocksValid(DetectionContext &Context) const {
1318
2.94k
  Region &CurRegion = Context.CurRegion;
1319
2.94k
1320
15.9k
  for (const BasicBlock *BB : CurRegion.blocks()) {
1321
15.9k
    Loop *L = LI->getLoopFor(BB);
1322
15.9k
    if (
L && 15.9k
L->getHeader() == BB12.7k
&&
CurRegion.contains(L)4.45k
&&
1323
4.40k
        
(!isValidLoop(L, Context) && 4.40k
!KeepGoing159
))
1324
159
      return false;
1325
15.9k
  }
1326
2.94k
1327
15.2k
  
for (BasicBlock *BB : CurRegion.blocks()) 2.78k
{15.2k
1328
15.2k
    bool IsErrorBlock = isErrorBlock(*BB, CurRegion, *LI, *DT);
1329
15.2k
1330
15.2k
    // Also check exception blocks (and possibly register them as non-affine
1331
15.2k
    // regions). Even though exception blocks are not modeled, we use them
1332
15.2k
    // to forward-propagate domain constraints during ScopInfo construction.
1333
15.2k
    if (
!isValidCFG(*BB, false, IsErrorBlock, Context) && 15.2k
!KeepGoing66
)
1334
66
      return false;
1335
15.2k
1336
15.1k
    
if (15.1k
IsErrorBlock15.1k
)
1337
127
      continue;
1338
15.1k
1339
60.3k
    
for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); 15.0k
I != E60.3k
;
++I45.3k
)
1340
45.4k
      
if (45.4k
!isValidInstruction(*I, Context) && 45.4k
!KeepGoing106
)
1341
97
        return false;
1342
15.0k
  }
1343
2.78k
1344
2.62k
  
if (2.62k
!hasAffineMemoryAccesses(Context)2.62k
)
1345
33
    return false;
1346
2.62k
1347
2.59k
  return true;
1348
2.62k
}
1349
1350
bool ScopDetection::hasSufficientCompute(DetectionContext &Context,
1351
8
                                         int NumLoops) const {
1352
8
  int InstCount = 0;
1353
8
1354
8
  if (NumLoops == 0)
1355
0
    return false;
1356
8
1357
8
  for (auto *BB : Context.CurRegion.blocks())
1358
36
    
if (36
Context.CurRegion.contains(LI->getLoopFor(BB))36
)
1359
36
      InstCount += BB->size();
1360
8
1361
8
  InstCount = InstCount / NumLoops;
1362
8
1363
8
  return InstCount >= ProfitabilityMinPerLoopInstructions;
1364
8
}
1365
1366
bool ScopDetection::hasPossiblyDistributableLoop(
1367
10
    DetectionContext &Context) const {
1368
10
  for (auto *BB : Context.CurRegion.blocks()) {
1369
10
    auto *L = LI->getLoopFor(BB);
1370
10
    if (!Context.CurRegion.contains(L))
1371
0
      continue;
1372
10
    
if (10
Context.BoxedLoopsSet.count(L)10
)
1373
0
      continue;
1374
10
    unsigned StmtsWithStoresInLoops = 0;
1375
74
    for (auto *LBB : L->blocks()) {
1376
74
      bool MemStore = false;
1377
74
      for (auto &I : *LBB)
1378
303
        MemStore |= isa<StoreInst>(&I);
1379
74
      StmtsWithStoresInLoops += MemStore;
1380
74
    }
1381
10
    return (StmtsWithStoresInLoops > 1);
1382
10
  }
1383
0
  return false;
1384
10
}
1385
1386
1.02k
bool ScopDetection::isProfitableRegion(DetectionContext &Context) const {
1387
1.02k
  Region &CurRegion = Context.CurRegion;
1388
1.02k
1389
1.02k
  if (PollyProcessUnprofitable)
1390
1.00k
    return true;
1391
1.02k
1392
1.02k
  // We can probably not do a lot on scops that only write or only read
1393
1.02k
  // data.
1394
19
  
if (19
!Context.hasStores || 19
!Context.hasLoads18
)
1395
2
    return invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
1396
19
1397
17
  int NumLoops =
1398
17
      countBeneficialLoops(&CurRegion, *SE, *LI, MIN_LOOP_TRIP_COUNT).NumLoops;
1399
17
  int NumAffineLoops = NumLoops - Context.BoxedLoopsSet.size();
1400
17
1401
17
  // Scops with at least two loops may allow either loop fusion or tiling and
1402
17
  // are consequently interesting to look at.
1403
17
  if (NumAffineLoops >= 2)
1404
3
    return true;
1405
17
1406
17
  // A loop with multiple non-trivial blocks migt be amendable to distribution.
1407
14
  
if (14
NumAffineLoops == 1 && 14
hasPossiblyDistributableLoop(Context)10
)
1408
2
    return true;
1409
14
1410
14
  // Scops that contain a loop with a non-trivial amount of computation per
1411
14
  // loop-iteration are interesting as we may be able to parallelize such
1412
14
  // loops. Individual loops that have only a small amount of computation
1413
14
  // per-iteration are performance-wise very fragile as any change to the
1414
14
  // loop induction variables may affect performance. To not cause spurious
1415
14
  // performance regressions, we do not consider such loops.
1416
12
  
if (12
NumAffineLoops == 1 && 12
hasSufficientCompute(Context, NumLoops)8
)
1417
1
    return true;
1418
12
1419
11
  return invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
1420
12
}
1421
1422
3.69k
bool ScopDetection::isValidRegion(DetectionContext &Context) const {
1423
3.69k
  Region &CurRegion = Context.CurRegion;
1424
3.69k
1425
3.69k
  DEBUG(dbgs() << "Checking region: " << CurRegion.getNameStr() << "\n\t");
1426
3.69k
1427
3.69k
  if (
CurRegion.isTopLevelRegion()3.69k
)
{1.12k
1428
1.12k
    DEBUG(dbgs() << "Top level region is invalid\n");
1429
1.12k
    return false;
1430
1.12k
  }
1431
3.69k
1432
2.57k
  DebugLoc DbgLoc;
1433
2.57k
  if (
isa<UnreachableInst>(CurRegion.getExit()->getTerminator())2.57k
)
{26
1434
26
    DEBUG(dbgs() << "Unreachable in exit\n");
1435
26
    return invalid<ReportUnreachableInExit>(Context, /*Assert=*/true,
1436
26
                                            CurRegion.getExit(), DbgLoc);
1437
26
  }
1438
2.57k
1439
2.55k
  
if (2.55k
!CurRegion.getEntry()->getName().count(OnlyRegion)2.55k
)
{0
1440
0
    DEBUG({
1441
0
      dbgs() << "Region entry does not match -polly-region-only";
1442
0
      dbgs() << "\n";
1443
0
    });
1444
0
    return false;
1445
0
  }
1446
2.55k
1447
2.55k
  // SCoP cannot contain the entry block of the function, because we need
1448
2.55k
  // to insert alloca instruction there when translate scalar to array.
1449
2.55k
  
if (2.55k
CurRegion.getEntry() ==2.55k
1450
2.55k
      &(CurRegion.getEntry()->getParent()->getEntryBlock()))
1451
83
    return invalid<ReportEntry>(Context, /*Assert=*/true, CurRegion.getEntry());
1452
2.55k
1453
2.46k
  
if (2.46k
!allBlocksValid(Context)2.46k
)
1454
309
    return false;
1455
2.46k
1456
2.16k
  
if (2.16k
!isReducibleRegion(CurRegion, DbgLoc)2.16k
)
1457
3
    return invalid<ReportIrreducibleRegion>(Context, /*Assert=*/true,
1458
3
                                            &CurRegion, DbgLoc);
1459
2.16k
1460
2.15k
  
DEBUG2.15k
(dbgs() << "OK\n");2.15k
1461
2.15k
  return true;
1462
2.16k
}
1463
1464
0
void ScopDetection::markFunctionAsInvalid(Function *F) {
1465
0
  F->addFnAttr(PollySkipFnAttr);
1466
0
}
1467
1468
1.14k
bool ScopDetection::isValidFunction(llvm::Function &F) {
1469
1.14k
  return !F.hasFnAttribute(PollySkipFnAttr);
1470
1.14k
}
1471
1472
2
void ScopDetection::printLocations(llvm::Function &F) {
1473
2
  for (const Region *R : *this) {
1474
2
    unsigned LineEntry, LineExit;
1475
2
    std::string FileName;
1476
2
1477
2
    getDebugLocation(R, LineEntry, LineExit, FileName);
1478
2
    DiagnosticScopFound Diagnostic(F, FileName, LineEntry, LineExit);
1479
2
    F.getContext().diagnose(Diagnostic);
1480
2
  }
1481
2
}
1482
1483
1.12k
void ScopDetection::emitMissedRemarks(const Function &F) {
1484
2.95k
  for (auto &DIt : DetectionContextMap) {
1485
2.95k
    auto &DC = DIt.getSecond();
1486
2.95k
    if (DC.Log.hasErrors())
1487
430
      emitRejectionRemarks(DIt.getFirst(), DC.Log);
1488
2.95k
  }
1489
1.12k
}
1490
1491
2.16k
bool ScopDetection::isReducibleRegion(Region &R, DebugLoc &DbgLoc) const {
1492
2.16k
  /// Enum for coloring BBs in Region.
1493
2.16k
  ///
1494
2.16k
  /// WHITE - Unvisited BB in DFS walk.
1495
2.16k
  /// GREY - BBs which are currently on the DFS stack for processing.
1496
2.16k
  /// BLACK - Visited and completely processed BB.
1497
2.16k
  enum Color { WHITE, GREY, BLACK };
1498
2.16k
1499
2.16k
  BasicBlock *REntry = R.getEntry();
1500
2.16k
  BasicBlock *RExit = R.getExit();
1501
2.16k
  // Map to match the color of a BasicBlock during the DFS walk.
1502
2.16k
  DenseMap<const BasicBlock *, Color> BBColorMap;
1503
2.16k
  // Stack keeping track of current BB and index of next child to be processed.
1504
2.16k
  std::stack<std::pair<BasicBlock *, unsigned>> DFSStack;
1505
2.16k
1506
2.16k
  unsigned AdjacentBlockIndex = 0;
1507
2.16k
  BasicBlock *CurrBB, *SuccBB;
1508
2.16k
  CurrBB = REntry;
1509
2.16k
1510
2.16k
  // Initialize the map for all BB with WHITE color.
1511
2.16k
  for (auto *BB : R.blocks())
1512
9.35k
    BBColorMap[BB] = WHITE;
1513
2.16k
1514
2.16k
  // Process the entry block of the Region.
1515
2.16k
  BBColorMap[CurrBB] = GREY;
1516
2.16k
  DFSStack.push(std::make_pair(CurrBB, 0));
1517
2.16k
1518
18.6k
  while (
!DFSStack.empty()18.6k
)
{16.5k
1519
16.5k
    // Get next BB on stack to be processed.
1520
16.5k
    CurrBB = DFSStack.top().first;
1521
16.5k
    AdjacentBlockIndex = DFSStack.top().second;
1522
16.5k
    DFSStack.pop();
1523
16.5k
1524
16.5k
    // Loop to iterate over the successors of current BB.
1525
16.5k
    const TerminatorInst *TInst = CurrBB->getTerminator();
1526
16.5k
    unsigned NSucc = TInst->getNumSuccessors();
1527
22.5k
    for (unsigned I = AdjacentBlockIndex; I < NSucc;
1528
13.2k
         
++I, ++AdjacentBlockIndex6.04k
)
{13.2k
1529
13.2k
      SuccBB = TInst->getSuccessor(I);
1530
13.2k
1531
13.2k
      // Checks for region exit block and self-loops in BB.
1532
13.2k
      if (
SuccBB == RExit || 13.2k
SuccBB == CurrBB10.6k
)
1533
3.35k
        continue;
1534
13.2k
1535
13.2k
      // WHITE indicates an unvisited BB in DFS walk.
1536
9.88k
      
if (9.88k
BBColorMap[SuccBB] == WHITE9.88k
)
{7.19k
1537
7.19k
        // Push the current BB and the index of the next child to be visited.
1538
7.19k
        DFSStack.push(std::make_pair(CurrBB, I + 1));
1539
7.19k
        // Push the next BB to be processed.
1540
7.19k
        DFSStack.push(std::make_pair(SuccBB, 0));
1541
7.19k
        // First time the BB is being processed.
1542
7.19k
        BBColorMap[SuccBB] = GREY;
1543
7.19k
        break;
1544
2.68k
      } else 
if (2.68k
BBColorMap[SuccBB] == GREY2.68k
)
{2.05k
1545
2.05k
        // GREY indicates a loop in the control flow.
1546
2.05k
        // If the destination dominates the source, it is a natural loop
1547
2.05k
        // else, an irreducible control flow in the region is detected.
1548
2.05k
        if (
!DT->dominates(SuccBB, CurrBB)2.05k
)
{3
1549
3
          // Get debug info of instruction which causes irregular control flow.
1550
3
          DbgLoc = TInst->getDebugLoc();
1551
3
          return false;
1552
3
        }
1553
2.05k
      }
1554
9.88k
    }
1555
16.5k
1556
16.5k
    // If all children of current BB have been processed,
1557
16.5k
    // then mark that BB as fully processed.
1558
16.5k
    
if (16.5k
AdjacentBlockIndex == NSucc16.5k
)
1559
9.33k
      BBColorMap[CurrBB] = BLACK;
1560
16.5k
  }
1561
2.16k
1562
2.15k
  return true;
1563
2.16k
}
1564
1565
void updateLoopCountStatistic(ScopDetection::LoopStats Stats,
1566
2.04k
                              bool OnlyProfitable) {
1567
2.04k
  if (
!OnlyProfitable2.04k
)
{1.02k
1568
1.02k
    NumLoopsInScop += Stats.NumLoops;
1569
1.02k
    MaxNumLoopsInScop =
1570
1.02k
        std::max(MaxNumLoopsInScop.getValue(), (unsigned)Stats.NumLoops);
1571
1.02k
    if (Stats.MaxDepth == 1)
1572
667
      NumScopsDepthOne++;
1573
360
    else 
if (360
Stats.MaxDepth == 2360
)
1574
195
      NumScopsDepthTwo++;
1575
165
    else 
if (165
Stats.MaxDepth == 3165
)
1576
66
      NumScopsDepthThree++;
1577
99
    else 
if (99
Stats.MaxDepth == 499
)
1578
4
      NumScopsDepthFour++;
1579
95
    else 
if (95
Stats.MaxDepth == 595
)
1580
0
      NumScopsDepthFive++;
1581
95
    else
1582
95
      NumScopsDepthLarger++;
1583
1.01k
  } else {
1584
1.01k
    NumLoopsInProfScop += Stats.NumLoops;
1585
1.01k
    MaxNumLoopsInProfScop =
1586
1.01k
        std::max(MaxNumLoopsInProfScop.getValue(), (unsigned)Stats.NumLoops);
1587
1.01k
    if (Stats.MaxDepth == 1)
1588
661
      NumProfScopsDepthOne++;
1589
353
    else 
if (353
Stats.MaxDepth == 2353
)
1590
189
      NumProfScopsDepthTwo++;
1591
164
    else 
if (164
Stats.MaxDepth == 3164
)
1592
66
      NumProfScopsDepthThree++;
1593
98
    else 
if (98
Stats.MaxDepth == 498
)
1594
3
      NumProfScopsDepthFour++;
1595
95
    else 
if (95
Stats.MaxDepth == 595
)
1596
0
      NumProfScopsDepthFive++;
1597
95
    else
1598
95
      NumProfScopsDepthLarger++;
1599
1.01k
  }
1600
2.04k
}
1601
1602
1.14k
bool ScopDetection::runOnFunction(llvm::Function &F) {
1603
1.14k
  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1604
1.14k
  RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
1605
1.14k
  if (
!PollyProcessUnprofitable && 1.14k
LI->empty()19
)
1606
0
    return false;
1607
1.14k
1608
1.14k
  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
1609
1.14k
  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1610
1.14k
  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1611
1.14k
  Region *TopRegion = RI->getTopLevelRegion();
1612
1.14k
1613
1.14k
  releaseMemory();
1614
1.14k
1615
1.14k
  if (
OnlyFunction != "" && 1.14k
!F.getName().count(OnlyFunction)0
)
1616
0
    return false;
1617
1.14k
1618
1.14k
  
if (1.14k
!isValidFunction(F)1.14k
)
1619
27
    return false;
1620
1.14k
1621
1.12k
  findScops(*TopRegion);
1622
1.12k
1623
1.12k
  NumScopRegions += ValidRegions.size();
1624
1.12k
1625
1.12k
  // Prune non-profitable regions.
1626
2.95k
  for (auto &DIt : DetectionContextMap) {
1627
2.95k
    auto &DC = DIt.getSecond();
1628
2.95k
    if (DC.Log.hasErrors())
1629
417
      continue;
1630
2.53k
    
if (2.53k
!ValidRegions.count(&DC.CurRegion)2.53k
)
1631
1.50k
      continue;
1632
1.02k
    LoopStats Stats = countBeneficialLoops(&DC.CurRegion, *SE, *LI, 0);
1633
1.02k
    updateLoopCountStatistic(Stats, false /* OnlyProfitable */);
1634
1.02k
    if (
isProfitableRegion(DC)1.02k
)
{1.01k
1635
1.01k
      updateLoopCountStatistic(Stats, true /* OnlyProfitable */);
1636
1.01k
      continue;
1637
1.01k
    }
1638
1.02k
1639
13
    ValidRegions.remove(&DC.CurRegion);
1640
13
  }
1641
1.12k
1642
1.12k
  NumProfScopRegions += ValidRegions.size();
1643
1.12k
  NumLoopsOverall += countBeneficialLoops(TopRegion, *SE, *LI, 0).NumLoops;
1644
1.12k
1645
1.12k
  // Only makes sense when we tracked errors.
1646
1.12k
  if (PollyTrackFailures)
1647
1.12k
    emitMissedRemarks(F);
1648
1.12k
1649
1.12k
  if (ReportLevel)
1650
2
    printLocations(F);
1651
1.12k
1652
1.12k
  assert(ValidRegions.size() <= DetectionContextMap.size() &&
1653
1.12k
         "Cached more results than valid regions");
1654
1.12k
  return false;
1655
1.14k
}
1656
1657
ScopDetection::DetectionContext *
1658
1.97k
ScopDetection::getDetectionContext(const Region *R) const {
1659
1.97k
  auto DCMIt = DetectionContextMap.find(getBBPairForRegion(R));
1660
1.97k
  if (DCMIt == DetectionContextMap.end())
1661
1
    return nullptr;
1662
1.97k
  return &DCMIt->second;
1663
1.97k
}
1664
1665
1.03k
const RejectLog *ScopDetection::lookupRejectionLog(const Region *R) const {
1666
1.03k
  const DetectionContext *DC = getDetectionContext(R);
1667
1.03k
  return DC ? 
&DC->Log1.03k
:
nullptr1
;
1668
1.03k
}
1669
1670
0
void polly::ScopDetection::verifyRegion(const Region &R) const {
1671
0
  assert(isMaxRegionInScop(R) && "Expect R is a valid region.");
1672
0
1673
0
  DetectionContext Context(const_cast<Region &>(R), *AA, true /*verifying*/);
1674
0
  isValidRegion(Context);
1675
0
}
1676
1677
0
void polly::ScopDetection::verifyAnalysis() const {
1678
0
  if (!VerifyScops)
1679
0
    return;
1680
0
1681
0
  for (const Region *R : ValidRegions)
1682
0
    verifyRegion(*R);
1683
0
}
1684
1685
1.02k
void ScopDetection::getAnalysisUsage(AnalysisUsage &AU) const {
1686
1.02k
  AU.addRequired<LoopInfoWrapperPass>();
1687
1.02k
  AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
1688
1.02k
  AU.addRequired<DominatorTreeWrapperPass>();
1689
1.02k
  // We also need AA and RegionInfo when we are verifying analysis.
1690
1.02k
  AU.addRequiredTransitive<AAResultsWrapperPass>();
1691
1.02k
  AU.addRequiredTransitive<RegionInfoPass>();
1692
1.02k
  AU.setPreservesAll();
1693
1.02k
}
1694
1695
120
void ScopDetection::print(raw_ostream &OS, const Module *) const {
1696
120
  for (const Region *R : ValidRegions)
1697
72
    OS << "Valid Region for Scop: " << R->getNameStr() << '\n';
1698
120
1699
120
  OS << "\n";
1700
120
}
1701
1702
2.29k
void ScopDetection::releaseMemory() {
1703
2.29k
  ValidRegions.clear();
1704
2.29k
  DetectionContextMap.clear();
1705
2.29k
1706
2.29k
  // Do not clear the invalid function set.
1707
2.29k
}
1708
1709
char ScopDetection::ID = 0;
1710
1711
0
Pass *polly::createScopDetectionPass() { return new ScopDetection(); }
1712
1713
39.7k
INITIALIZE_PASS_BEGIN39.7k
(ScopDetection, "polly-detect",39.7k
1714
39.7k
                      "Polly - Detect static control parts (SCoPs)", false,
1715
39.7k
                      false);
1716
39.7k
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
1717
39.7k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
1718
39.7k
INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
1719
39.7k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
1720
39.7k
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
1721
39.7k
INITIALIZE_PASS_END(ScopDetection, "polly-detect",
1722
                    "Polly - Detect static control parts (SCoPs)", false, false)