Coverage Report

Created: 2019-04-21 11:35

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