Coverage Report

Created: 2017-03-27 23:01

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