Coverage Report

Created: 2017-10-03 07:32

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