Coverage Report

Created: 2018-04-23 18:20

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