Coverage Report

Created: 2019-02-20 07:29

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