blob: 4c5c95af6e6e1097cbc78e2316294298b8d090d0 [file] [log] [blame]
Eugene Zelenkoa32707d2017-08-25 21:35:27 +00001//===- ScopDetection.cpp - Detect Scops -----------------------------------===//
Tobias Grosser75805372011-04-29 06:27:02 +00002//
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//
Michael Krusea6d48f52017-06-08 12:06:15 +000016// Every Scop fulfills these restrictions:
Tobias Grosser75805372011-04-29 06:27:02 +000017//
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//
Johannes Doerfertcea61932016-02-21 19:13:19 +000037// Function calls and intrinsics that do not have side effects (readnone)
38// or memory intrinsics (memset, memcpy, memmove) are allowed.
Tobias Grosser75805372011-04-29 06:27:02 +000039//
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
Tobias Grosser5624d3c2015-12-21 12:38:56 +000047#include "polly/ScopDetection.h"
Tobias Grosser75805372011-04-29 06:27:02 +000048#include "polly/LinkAllPasses.h"
Tobias Grosser637bd632013-05-07 07:31:10 +000049#include "polly/Options.h"
Tobias Grosserba0d0922015-05-09 09:13:42 +000050#include "polly/ScopDetectionDiagnostic.h"
Tobias Grosser120db6b2011-11-07 12:58:54 +000051#include "polly/Support/SCEVValidator.h"
Eugene Zelenkoa32707d2017-08-25 21:35:27 +000052#include "polly/Support/ScopHelper.h"
Tobias Grossera63b7ce2015-05-03 05:21:36 +000053#include "polly/Support/ScopLocation.h"
Eugene Zelenkoa32707d2017-08-25 21:35:27 +000054#include "llvm/ADT/DenseMap.h"
55#include "llvm/ADT/SetVector.h"
56#include "llvm/ADT/SmallPtrSet.h"
57#include "llvm/ADT/SmallVector.h"
Tobias Grosser75805372011-04-29 06:27:02 +000058#include "llvm/ADT/Statistic.h"
Eugene Zelenkoa32707d2017-08-25 21:35:27 +000059#include "llvm/ADT/StringRef.h"
Tobias Grosser75805372011-04-29 06:27:02 +000060#include "llvm/Analysis/AliasAnalysis.h"
Tobias Grosser8bd7f3c2017-03-09 11:36:00 +000061#include "llvm/Analysis/Loads.h"
Tobias Grosser6e9f25a2011-11-09 22:35:00 +000062#include "llvm/Analysis/LoopInfo.h"
Eugene Zelenkoa32707d2017-08-25 21:35:27 +000063#include "llvm/Analysis/MemoryLocation.h"
Adam Nemete0f15412017-10-09 23:49:08 +000064#include "llvm/Analysis/OptimizationRemarkEmitter.h"
Eugene Zelenkoa32707d2017-08-25 21:35:27 +000065#include "llvm/Analysis/RegionInfo.h"
Tobias Grosser6e9f25a2011-11-09 22:35:00 +000066#include "llvm/Analysis/ScalarEvolution.h"
Tobias Grosserb8710b52011-11-10 12:44:50 +000067#include "llvm/Analysis/ScalarEvolutionExpressions.h"
Eugene Zelenkoa32707d2017-08-25 21:35:27 +000068#include "llvm/IR/BasicBlock.h"
69#include "llvm/IR/Constants.h"
70#include "llvm/IR/DebugLoc.h"
71#include "llvm/IR/DerivedTypes.h"
Tobias Grosser8519f892013-12-18 10:49:53 +000072#include "llvm/IR/DiagnosticInfo.h"
73#include "llvm/IR/DiagnosticPrinter.h"
Eugene Zelenkoa32707d2017-08-25 21:35:27 +000074#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"
Tobias Grosserba0d0922015-05-09 09:13:42 +000079#include "llvm/IR/IntrinsicInst.h"
Eugene Zelenkoa32707d2017-08-25 21:35:27 +000080#include "llvm/IR/Intrinsics.h"
Chandler Carruth6b96c242014-03-06 00:47:27 +000081#include "llvm/IR/LLVMContext.h"
Eugene Zelenkoa32707d2017-08-25 21:35:27 +000082#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"
Tobias Grosser75805372011-04-29 06:27:02 +000090#include "llvm/Support/Debug.h"
Eugene Zelenkoa32707d2017-08-25 21:35:27 +000091#include "llvm/Support/ErrorHandling.h"
Siddharth Bhate2699b52017-07-24 12:40:52 +000092#include "llvm/Support/Regex.h"
Eugene Zelenkoa32707d2017-08-25 21:35:27 +000093#include "llvm/Support/raw_ostream.h"
94#include <algorithm>
95#include <cassert>
96#include <memory>
Tobias Grosser1c3a6d72016-01-22 09:44:37 +000097#include <stack>
Eugene Zelenkoa32707d2017-08-25 21:35:27 +000098#include <string>
99#include <utility>
100#include <vector>
Tobias Grosser60b54f12011-11-08 15:41:28 +0000101
Tobias Grosser75805372011-04-29 06:27:02 +0000102using namespace llvm;
103using namespace polly;
104
Chandler Carruth95fef942014-04-22 03:30:19 +0000105#define DEBUG_TYPE "polly-detect"
106
Tobias Grosserc1a269b2015-12-21 21:00:43 +0000107// 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.
111static 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
Tobias Grosser575aca82015-10-06 16:10:29 +0000117bool polly::PollyProcessUnprofitable;
Eugene Zelenkoa32707d2017-08-25 21:35:27 +0000118
Tobias Grosser575aca82015-10-06 16:10:29 +0000119static 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));
Tobias Grosserd1e33e72015-02-19 05:31:07 +0000125
Siddharth Bhat286c9162017-06-09 08:23:40 +0000126static cl::list<std::string> OnlyFunctions(
Tobias Grosser483a90d2014-07-09 10:50:10 +0000127 "polly-only-func",
Siddharth Bhate2699b52017-07-24 12:40:52 +0000128 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."),
Siddharth Bhat286c9162017-06-09 08:23:40 +0000132 cl::ZeroOrMore, cl::CommaSeparated, cl::cat(PollyCategory));
Tobias Grosser2ff87232011-10-23 11:17:06 +0000133
Siddharth Bhat0a1177b2017-07-28 11:47:24 +0000134static 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
Siddharth Bhatb46847c2017-08-17 21:57:23 +0000142bool polly::PollyAllowFullFunction;
Eugene Zelenkoa32707d2017-08-25 21:35:27 +0000143
Siddharth Bhatb46847c2017-08-17 21:57:23 +0000144static 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));
Tobias Grosserd8945ba2017-05-19 12:13:02 +0000149
Tobias Grosser483a90d2014-07-09 10:50:10 +0000150static 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));
Tobias Grosser4449e522014-01-27 14:24:53 +0000156
Tobias Grosser60cd9322011-11-10 12:47:26 +0000157static cl::opt<bool>
Tobias Grosser483a90d2014-07-09 10:50:10 +0000158 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));
Tobias Grosser2ff87232011-10-23 11:17:06 +0000162
Johannes Doerfertbda81432016-12-02 17:55:41 +0000163bool polly::PollyAllowUnsignedOperations;
Eugene Zelenkoa32707d2017-08-25 21:35:27 +0000164
Johannes Doerfertbda81432016-12-02 17:55:41 +0000165static 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
Johannes Doerfertb164c792014-09-18 11:17:17 +0000171bool polly::PollyUseRuntimeAliasChecks;
Eugene Zelenkoa32707d2017-08-25 21:35:27 +0000172
Johannes Doerfertb164c792014-09-18 11:17:17 +0000173static 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
Tobias Grosser637bd632013-05-07 07:31:10 +0000179static cl::opt<bool>
Tobias Grosser483a90d2014-07-09 10:50:10 +0000180 ReportLevel("polly-report",
181 cl::desc("Print information about the activities of Polly"),
182 cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
Tobias Grosser531891e2012-11-01 16:45:20 +0000183
Tobias Grosser8ebdc2d2016-02-07 08:48:57 +0000184static cl::opt<bool> AllowDifferentTypes(
185 "polly-allow-differing-element-types",
186 cl::desc("Allow different element types for array accesses"), cl::Hidden,
Tobias Grossera2ee0032016-02-16 14:37:24 +0000187 cl::init(true), cl::ZeroOrMore, cl::cat(PollyCategory));
Tobias Grosser8ebdc2d2016-02-07 08:48:57 +0000188
Tobias Grosser531891e2012-11-01 16:45:20 +0000189static cl::opt<bool>
Tobias Grosser483a90d2014-07-09 10:50:10 +0000190 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));
Tobias Grossera1879642011-12-20 10:43:14 +0000194
Tobias Grosser898a6362016-03-23 06:40:15 +0000195static 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
Johannes Doerfertba65c162015-02-24 11:45:21 +0000201static cl::opt<bool> AllowNonAffineSubRegions(
202 "polly-allow-nonaffine-branches",
203 cl::desc("Allow non affine conditions for branches"), cl::Hidden,
Johannes Doerferta36842f2015-02-26 11:09:24 +0000204 cl::init(true), cl::ZeroOrMore, cl::cat(PollyCategory));
Johannes Doerfertba65c162015-02-24 11:45:21 +0000205
Johannes Doerfertf3e98f42015-04-12 22:52:20 +0000206static 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
Tobias Grosserc7d3fc52013-07-25 03:02:29 +0000212static cl::opt<bool, true>
Tobias Grosser483a90d2014-07-09 10:50:10 +0000213 TrackFailures("polly-detect-track-failures",
214 cl::desc("Track failure strings in detecting scop regions"),
215 cl::location(PollyTrackFailures), cl::Hidden, cl::ZeroOrMore,
Andreas Simbuerger3efe40b2014-08-17 10:09:03 +0000216 cl::init(true), cl::cat(PollyCategory));
Tobias Grosserc7d3fc52013-07-25 03:02:29 +0000217
Andreas Simbuerger04472402014-05-24 09:25:10 +0000218static 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
Sebastian Pop18016682014-04-08 21:20:44 +0000223static cl::opt<bool, true>
Tobias Grosser483a90d2014-07-09 10:50:10 +0000224 PollyDelinearizeX("polly-delinearize",
225 cl::desc("Delinearize array access functions"),
226 cl::location(PollyDelinearize), cl::Hidden,
Tobias Grosser6973cb62015-03-08 15:21:18 +0000227 cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory));
Sebastian Pop18016682014-04-08 21:20:44 +0000228
Tobias Grossera1689932014-02-18 18:49:49 +0000229static cl::opt<bool>
Tobias Grosser483a90d2014-07-09 10:50:10 +0000230 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));
Tobias Grossera1689932014-02-18 18:49:49 +0000234
Tobias Grosser8fa3e4c2016-02-26 16:43:35 +0000235bool polly::PollyInvariantLoadHoisting;
Eugene Zelenkoa32707d2017-08-25 21:35:27 +0000236
Tobias Grosser8fa3e4c2016-02-26 16:43:35 +0000237static cl::opt<bool, true> XPollyInvariantLoadHoisting(
238 "polly-invariant-load-hoisting", cl::desc("Hoist invariant loads."),
239 cl::location(PollyInvariantLoadHoisting), cl::Hidden, cl::ZeroOrMore,
Tobias Grosser74814e12016-08-15 16:43:36 +0000240 cl::init(false), cl::cat(PollyCategory));
Tobias Grosser8fa3e4c2016-02-26 16:43:35 +0000241
Tobias Grosserc80d6972016-09-02 06:33:33 +0000242/// The minimal trip count under which loops are considered unprofitable.
Johannes Doerferte526de52015-09-21 19:10:11 +0000243static const unsigned MIN_LOOP_TRIP_COUNT = 8;
244
Tobias Grosserc7d3fc52013-07-25 03:02:29 +0000245bool polly::PollyTrackFailures = false;
Sebastian Pop18016682014-04-08 21:20:44 +0000246bool polly::PollyDelinearize = false;
Johannes Doerfert43e1ead2014-07-15 21:06:48 +0000247StringRef polly::PollySkipFnAttr = "polly.skip.fn";
Tobias Grosserc7d3fc52013-07-25 03:02:29 +0000248
Tobias Grosser75805372011-04-29 06:27:02 +0000249//===----------------------------------------------------------------------===//
250// Statistics.
251
Tobias Grosserb45ae562016-11-26 07:37:46 +0000252STATISTIC(NumScopRegions, "Number of scops");
253STATISTIC(NumLoopsInScop, "Number of loops in scops");
Tobias Grosserfcc3ad52018-04-18 20:03:36 +0000254STATISTIC(NumScopsDepthZero, "Number of scops with maximal loop depth 0");
Tobias Grosserb45ae562016-11-26 07:37:46 +0000255STATISTIC(NumScopsDepthOne, "Number of scops with maximal loop depth 1");
256STATISTIC(NumScopsDepthTwo, "Number of scops with maximal loop depth 2");
257STATISTIC(NumScopsDepthThree, "Number of scops with maximal loop depth 3");
258STATISTIC(NumScopsDepthFour, "Number of scops with maximal loop depth 4");
259STATISTIC(NumScopsDepthFive, "Number of scops with maximal loop depth 5");
260STATISTIC(NumScopsDepthLarger,
261 "Number of scops with maximal loop depth 6 and larger");
262STATISTIC(NumProfScopRegions, "Number of scops (profitable scops only)");
263STATISTIC(NumLoopsInProfScop,
264 "Number of loops in scops (profitable scops only)");
265STATISTIC(NumLoopsOverall, "Number of total loops");
Tobias Grosserfcc3ad52018-04-18 20:03:36 +0000266STATISTIC(NumProfScopsDepthZero,
267 "Number of scops with maximal loop depth 0 (profitable scops only)");
Tobias Grosserb45ae562016-11-26 07:37:46 +0000268STATISTIC(NumProfScopsDepthOne,
269 "Number of scops with maximal loop depth 1 (profitable scops only)");
270STATISTIC(NumProfScopsDepthTwo,
271 "Number of scops with maximal loop depth 2 (profitable scops only)");
272STATISTIC(NumProfScopsDepthThree,
273 "Number of scops with maximal loop depth 3 (profitable scops only)");
274STATISTIC(NumProfScopsDepthFour,
275 "Number of scops with maximal loop depth 4 (profitable scops only)");
276STATISTIC(NumProfScopsDepthFive,
277 "Number of scops with maximal loop depth 5 (profitable scops only)");
Tobias Grosser21a059a2017-01-16 14:08:10 +0000278STATISTIC(NumProfScopsDepthLarger,
279 "Number of scops with maximal loop depth 6 and larger "
280 "(profitable scops only)");
Tobias Grosser9fe37df2017-02-12 10:52:57 +0000281STATISTIC(MaxNumLoopsInScop, "Maximal number of loops in scops");
282STATISTIC(MaxNumLoopsInProfScop,
283 "Maximal number of loops in scops (profitable scops only)");
Tobias Grosser75805372011-04-29 06:27:02 +0000284
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000285static void updateLoopCountStatistic(ScopDetection::LoopStats Stats,
286 bool OnlyProfitable);
287
Eugene Zelenkoa32707d2017-08-25 21:35:27 +0000288namespace {
289
Tobias Grosser8519f892013-12-18 10:49:53 +0000290class DiagnosticScopFound : public DiagnosticInfo {
291private:
292 static int PluginDiagnosticKind;
293
294 Function &F;
295 std::string FileName;
296 unsigned EntryLine, ExitLine;
297
298public:
Tobias Grosser1b12f462013-12-18 11:14:36 +0000299 DiagnosticScopFound(Function &F, std::string FileName, unsigned EntryLine,
300 unsigned ExitLine)
Tobias Grosser8519f892013-12-18 10:49:53 +0000301 : DiagnosticInfo(PluginDiagnosticKind, DS_Note), F(F), FileName(FileName),
Tobias Grosser1b12f462013-12-18 11:14:36 +0000302 EntryLine(EntryLine), ExitLine(ExitLine) {}
Tobias Grosser8519f892013-12-18 10:49:53 +0000303
Eugene Zelenkoa32707d2017-08-25 21:35:27 +0000304 void print(DiagnosticPrinter &DP) const override;
Tobias Grosser8519f892013-12-18 10:49:53 +0000305
306 static bool classof(const DiagnosticInfo *DI) {
307 return DI->getKind() == PluginDiagnosticKind;
308 }
309};
Eugene Zelenkoa32707d2017-08-25 21:35:27 +0000310} // namespace
311
Tobias Grosserdb6db502016-04-01 07:15:19 +0000312int DiagnosticScopFound::PluginDiagnosticKind =
313 getNextAvailablePluginDiagnosticKind();
Tobias Grosser8519f892013-12-18 10:49:53 +0000314
Tobias Grosser8519f892013-12-18 10:49:53 +0000315void DiagnosticScopFound::print(DiagnosticPrinter &DP) const {
Tobias Grosser1b12f462013-12-18 11:14:36 +0000316 DP << "Polly detected an optimizable loop region (scop) in function '" << F
317 << "'\n";
Tobias Grosser8519f892013-12-18 10:49:53 +0000318
319 if (FileName.empty()) {
320 DP << "Scop location is unknown. Compile with debug info "
321 "(-g) to get more precise information. ";
Tobias Grosser1b12f462013-12-18 11:14:36 +0000322 return;
Tobias Grosser8519f892013-12-18 10:49:53 +0000323 }
324
325 DP << FileName << ":" << EntryLine << ": Start of scop\n";
326 DP << FileName << ":" << ExitLine << ": End of scop";
327}
328
Siddharth Bhat0a1177b2017-07-28 11:47:24 +0000329/// Check if a string matches any regex in a list of regexes.
330/// @param Str the input string to match against.
331/// @param RegexList a list of strings that are regular expressions.
332static bool doesStringMatchAnyRegex(StringRef Str,
333 const cl::list<std::string> &RegexList) {
334 for (auto RegexStr : RegexList) {
Siddharth Bhate2699b52017-07-24 12:40:52 +0000335 Regex R(RegexStr);
336
337 std::string Err;
338 if (!R.isValid(Err))
Siddharth Bhat0a1177b2017-07-28 11:47:24 +0000339 report_fatal_error("invalid regex given as input to polly: " + Err, true);
Siddharth Bhate2699b52017-07-24 12:40:52 +0000340
Siddharth Bhat0a1177b2017-07-28 11:47:24 +0000341 if (R.match(Str))
Siddharth Bhat286c9162017-06-09 08:23:40 +0000342 return true;
Siddharth Bhate2699b52017-07-24 12:40:52 +0000343 }
Siddharth Bhat286c9162017-06-09 08:23:40 +0000344 return false;
345}
Tobias Grosser75805372011-04-29 06:27:02 +0000346//===----------------------------------------------------------------------===//
347// ScopDetection.
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000348
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000349ScopDetection::ScopDetection(Function &F, const DominatorTree &DT,
350 ScalarEvolution &SE, LoopInfo &LI, RegionInfo &RI,
Eli Friedmane737fc12017-07-17 23:58:33 +0000351 AliasAnalysis &AA, OptimizationRemarkEmitter &ORE)
352 : DT(DT), SE(SE), LI(LI), RI(RI), AA(AA), ORE(ORE) {
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000353 if (!PollyProcessUnprofitable && LI.empty())
354 return;
355
356 Region *TopRegion = RI.getTopLevelRegion();
357
Eugene Zelenkoa32707d2017-08-25 21:35:27 +0000358 if (!OnlyFunctions.empty() &&
Siddharth Bhat0a1177b2017-07-28 11:47:24 +0000359 !doesStringMatchAnyRegex(F.getName(), OnlyFunctions))
360 return;
361
362 if (doesStringMatchAnyRegex(F.getName(), IgnoredFunctions))
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000363 return;
364
365 if (!isValidFunction(F))
366 return;
367
368 findScops(*TopRegion);
369
370 NumScopRegions += ValidRegions.size();
371
372 // Prune non-profitable regions.
373 for (auto &DIt : DetectionContextMap) {
374 auto &DC = DIt.getSecond();
375 if (DC.Log.hasErrors())
376 continue;
377 if (!ValidRegions.count(&DC.CurRegion))
378 continue;
379 LoopStats Stats = countBeneficialLoops(&DC.CurRegion, SE, LI, 0);
380 updateLoopCountStatistic(Stats, false /* OnlyProfitable */);
381 if (isProfitableRegion(DC)) {
382 updateLoopCountStatistic(Stats, true /* OnlyProfitable */);
383 continue;
384 }
385
386 ValidRegions.remove(&DC.CurRegion);
387 }
388
389 NumProfScopRegions += ValidRegions.size();
390 NumLoopsOverall += countBeneficialLoops(TopRegion, SE, LI, 0).NumLoops;
391
392 // Only makes sense when we tracked errors.
393 if (PollyTrackFailures)
394 emitMissedRemarks(F);
395
396 if (ReportLevel)
397 printLocations(F);
398
399 assert(ValidRegions.size() <= DetectionContextMap.size() &&
400 "Cached more results than valid regions");
Johannes Doerfertb164c792014-09-18 11:17:17 +0000401}
402
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000403template <class RR, typename... Args>
404inline bool ScopDetection::invalid(DetectionContext &Context, bool Assert,
405 Args &&... Arguments) const {
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000406 if (!Context.Verifying) {
Andreas Simbuerger4870e092014-05-24 09:25:01 +0000407 RejectLog &Log = Context.Log;
408 std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000409
Andreas Simbuerger8a00c9b2014-05-24 09:25:06 +0000410 if (PollyTrackFailures)
Andreas Simbuerger4870e092014-05-24 09:25:01 +0000411 Log.report(RejectReason);
Andreas Simbuerger4870e092014-05-24 09:25:01 +0000412
413 DEBUG(dbgs() << RejectReason->getMessage());
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000414 DEBUG(dbgs() << "\n");
415 } else {
416 assert(!Assert && "Verification of detected scop failed");
417 }
418
419 return false;
420}
421
Tobias Grossera1689932014-02-18 18:49:49 +0000422bool ScopDetection::isMaxRegionInScop(const Region &R, bool Verify) const {
423 if (!ValidRegions.count(&R))
424 return false;
425
Johannes Doerfert3f1c2852015-02-19 18:11:50 +0000426 if (Verify) {
Johannes Doerfert6c7639b2016-05-12 18:50:01 +0000427 DetectionContextMap.erase(getBBPairForRegion(&R));
428 const auto &It = DetectionContextMap.insert(std::make_pair(
429 getBBPairForRegion(&R),
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000430 DetectionContext(const_cast<Region &>(R), AA, false /*verifying*/)));
Tobias Grosser907090c2015-10-25 10:55:35 +0000431 DetectionContext &Context = It.first->second;
Johannes Doerfert3f1c2852015-02-19 18:11:50 +0000432 return isValidRegion(Context);
433 }
Tobias Grossera1689932014-02-18 18:49:49 +0000434
435 return true;
Tobias Grosser75805372011-04-29 06:27:02 +0000436}
437
Tobias Grosser4f129a62011-10-08 00:30:55 +0000438std::string ScopDetection::regionIsInvalidBecause(const Region *R) const {
Andreas Simbuerger8a00c9b2014-05-24 09:25:06 +0000439 // Get the first error we found. Even in keep-going mode, this is the first
440 // reason that caused the candidate to be rejected.
Johannes Doerfert6c7639b2016-05-12 18:50:01 +0000441 auto *Log = lookupRejectionLog(R);
Andreas Simbuerger83ed8612014-06-12 07:25:08 +0000442
443 // This can happen when we marked a region invalid, but didn't track
444 // an error for it.
Johannes Doerfert6c7639b2016-05-12 18:50:01 +0000445 if (!Log || !Log->hasErrors())
Andreas Simbuerger83ed8612014-06-12 07:25:08 +0000446 return "";
447
Johannes Doerfert6c7639b2016-05-12 18:50:01 +0000448 RejectReasonPtr RR = *Log->begin();
Andreas Simbuerger83ed8612014-06-12 07:25:08 +0000449 return RR->getMessage();
Tobias Grosser4f129a62011-10-08 00:30:55 +0000450}
451
Johannes Doerfertf3e98f42015-04-12 22:52:20 +0000452bool ScopDetection::addOverApproximatedRegion(Region *AR,
453 DetectionContext &Context) const {
Johannes Doerfertf3e98f42015-04-12 22:52:20 +0000454 // If we already know about Ar we can exit.
455 if (!Context.NonAffineSubRegionSet.insert(AR))
456 return true;
457
458 // All loops in the region have to be overapproximated too if there
459 // are accesses that depend on the iteration count.
Michael Kruse41f046a2016-06-27 19:00:49 +0000460
Johannes Doerfertf3e98f42015-04-12 22:52:20 +0000461 for (BasicBlock *BB : AR->blocks()) {
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000462 Loop *L = LI.getLoopFor(BB);
Tobias Grosser349d1c32016-09-20 17:05:22 +0000463 if (AR->contains(L))
Johannes Doerfertf3e98f42015-04-12 22:52:20 +0000464 Context.BoxedLoopsSet.insert(L);
Johannes Doerfertba65c162015-02-24 11:45:21 +0000465 }
Johannes Doerfertf3e98f42015-04-12 22:52:20 +0000466
467 return (AllowNonAffineSubLoops || Context.BoxedLoopsSet.empty());
Johannes Doerfertba65c162015-02-24 11:45:21 +0000468}
469
Johannes Doerfert09e36972015-10-07 20:17:36 +0000470bool ScopDetection::onlyValidRequiredInvariantLoads(
471 InvariantLoadsSetTy &RequiredILS, DetectionContext &Context) const {
472 Region &CurRegion = Context.CurRegion;
Tobias Grosser7b5a4df2017-04-11 04:59:13 +0000473 const DataLayout &DL = CurRegion.getEntry()->getModule()->getDataLayout();
Johannes Doerfert09e36972015-10-07 20:17:36 +0000474
Tobias Grosser8fa3e4c2016-02-26 16:43:35 +0000475 if (!PollyInvariantLoadHoisting && !RequiredILS.empty())
476 return false;
477
Tobias Grosser1c787e02017-03-02 12:15:37 +0000478 for (LoadInst *Load : RequiredILS) {
Tobias Grosser3f25a7e2017-05-04 10:16:20 +0000479 // If we already know a load has been accepted as required invariant, we
480 // already run the validation below once and consequently don't need to
481 // run it again. Hence, we return early. For certain test cases (e.g.,
482 // COSMO this avoids us spending 50% of scop-detection time in this
483 // very function (and its children).
484 if (Context.RequiredILS.count(Load))
485 continue;
486
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000487 if (!isHoistableLoad(Load, CurRegion, LI, SE, DT))
Johannes Doerfert09e36972015-10-07 20:17:36 +0000488 return false;
489
Tobias Grosser8bd7f3c2017-03-09 11:36:00 +0000490 for (auto NonAffineRegion : Context.NonAffineSubRegionSet) {
Tobias Grosser8bd7f3c2017-03-09 11:36:00 +0000491 if (isSafeToLoadUnconditionally(Load->getPointerOperand(),
492 Load->getAlignment(), DL))
493 continue;
494
Tobias Grosser1c787e02017-03-02 12:15:37 +0000495 if (NonAffineRegion->contains(Load) &&
496 Load->getParent() != NonAffineRegion->getEntry())
497 return false;
Tobias Grosser8bd7f3c2017-03-09 11:36:00 +0000498 }
Tobias Grosser1c787e02017-03-02 12:15:37 +0000499 }
500
Johannes Doerfert09e36972015-10-07 20:17:36 +0000501 Context.RequiredILS.insert(RequiredILS.begin(), RequiredILS.end());
502
503 return true;
504}
505
Johannes Doerferta94ae1a2016-12-02 17:49:52 +0000506bool ScopDetection::involvesMultiplePtrs(const SCEV *S0, const SCEV *S1,
507 Loop *Scope) const {
508 SetVector<Value *> Values;
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000509 findValues(S0, SE, Values);
Johannes Doerferta94ae1a2016-12-02 17:49:52 +0000510 if (S1)
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000511 findValues(S1, SE, Values);
Johannes Doerferta94ae1a2016-12-02 17:49:52 +0000512
513 SmallPtrSet<Value *, 8> PtrVals;
514 for (auto *V : Values) {
515 if (auto *P2I = dyn_cast<PtrToIntInst>(V))
516 V = P2I->getOperand(0);
517
518 if (!V->getType()->isPointerTy())
519 continue;
520
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000521 auto *PtrSCEV = SE.getSCEVAtScope(V, Scope);
Johannes Doerferta94ae1a2016-12-02 17:49:52 +0000522 if (isa<SCEVConstant>(PtrSCEV))
523 continue;
524
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000525 auto *BasePtr = dyn_cast<SCEVUnknown>(SE.getPointerBase(PtrSCEV));
Johannes Doerferta94ae1a2016-12-02 17:49:52 +0000526 if (!BasePtr)
527 return true;
528
529 auto *BasePtrVal = BasePtr->getValue();
530 if (PtrVals.insert(BasePtrVal).second) {
531 for (auto *PtrVal : PtrVals)
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000532 if (PtrVal != BasePtrVal && !AA.isNoAlias(PtrVal, BasePtrVal))
Johannes Doerferta94ae1a2016-12-02 17:49:52 +0000533 return true;
534 }
535 }
536
537 return false;
538}
539
Michael Kruse09eb4452016-03-03 22:10:47 +0000540bool ScopDetection::isAffine(const SCEV *S, Loop *Scope,
Johannes Doerfertec8a2172016-04-25 13:32:36 +0000541 DetectionContext &Context) const {
Johannes Doerfert09e36972015-10-07 20:17:36 +0000542 InvariantLoadsSetTy AccessILS;
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000543 if (!isAffineExpr(&Context.CurRegion, Scope, S, SE, &AccessILS))
Johannes Doerfert09e36972015-10-07 20:17:36 +0000544 return false;
545
546 if (!onlyValidRequiredInvariantLoads(AccessILS, Context))
547 return false;
548
549 return true;
550}
551
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000552bool ScopDetection::isValidSwitch(BasicBlock &BB, SwitchInst *SI,
Johannes Doerfert757a32b2015-10-04 14:54:27 +0000553 Value *Condition, bool IsLoopBranch,
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000554 DetectionContext &Context) const {
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000555 Loop *L = LI.getLoopFor(&BB);
556 const SCEV *ConditionSCEV = SE.getSCEVAtScope(Condition, L);
Tobias Grosser75805372011-04-29 06:27:02 +0000557
Tobias Grosserbbaeda32016-11-10 05:20:29 +0000558 if (IsLoopBranch && L->isLoopLatch(&BB))
559 return false;
560
Johannes Doerferta94ae1a2016-12-02 17:49:52 +0000561 // Check for invalid usage of different pointers in one expression.
562 if (involvesMultiplePtrs(ConditionSCEV, nullptr, L))
563 return false;
564
Michael Kruse09eb4452016-03-03 22:10:47 +0000565 if (isAffine(ConditionSCEV, L, Context))
Johannes Doerfert757a32b2015-10-04 14:54:27 +0000566 return true;
Tobias Grosser75805372011-04-29 06:27:02 +0000567
Tobias Grosserbbaeda32016-11-10 05:20:29 +0000568 if (AllowNonAffineSubRegions &&
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000569 addOverApproximatedRegion(RI.getRegionFor(&BB), Context))
Johannes Doerfert757a32b2015-10-04 14:54:27 +0000570 return true;
571
Johannes Doerfert757a32b2015-10-04 14:54:27 +0000572 return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB,
573 ConditionSCEV, ConditionSCEV, SI);
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000574}
575
576bool ScopDetection::isValidBranch(BasicBlock &BB, BranchInst *BI,
Johannes Doerfert757a32b2015-10-04 14:54:27 +0000577 Value *Condition, bool IsLoopBranch,
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000578 DetectionContext &Context) const {
Tobias Grosserbbaeda32016-11-10 05:20:29 +0000579 // Constant integer conditions are always affine.
580 if (isa<ConstantInt>(Condition))
581 return true;
582
Johannes Doerfert9b1f9c82015-10-11 13:21:03 +0000583 if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {
584 auto Opcode = BinOp->getOpcode();
585 if (Opcode == Instruction::And || Opcode == Instruction::Or) {
586 Value *Op0 = BinOp->getOperand(0);
587 Value *Op1 = BinOp->getOperand(1);
588 return isValidBranch(BB, BI, Op0, IsLoopBranch, Context) &&
589 isValidBranch(BB, BI, Op1, IsLoopBranch, Context);
590 }
591 }
592
Tobias Grosser0a62b2d2017-09-25 16:37:15 +0000593 if (auto PHI = dyn_cast<PHINode>(Condition)) {
594 auto *Unique = dyn_cast_or_null<ConstantInt>(
595 getUniqueNonErrorValue(PHI, &Context.CurRegion, LI, DT));
596 if (Unique && (Unique->isZero() || Unique->isOne()))
597 return true;
598 }
599
Tobias Grosser5e531df2017-09-25 20:27:15 +0000600 if (auto Load = dyn_cast<LoadInst>(Condition))
Michael Krusec0133992017-10-01 22:19:28 +0000601 if (!IsLoopBranch && Context.CurRegion.contains(Load)) {
Tobias Grosser5e531df2017-09-25 20:27:15 +0000602 Context.RequiredILS.insert(Load);
603 return true;
604 }
605
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000606 // Non constant conditions of branches need to be ICmpInst.
607 if (!isa<ICmpInst>(Condition)) {
Johannes Doerfert757a32b2015-10-04 14:54:27 +0000608 if (!IsLoopBranch && AllowNonAffineSubRegions &&
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000609 addOverApproximatedRegion(RI.getRegionFor(&BB), Context))
Johannes Doerfert757a32b2015-10-04 14:54:27 +0000610 return true;
611 return invalid<ReportInvalidCond>(Context, /*Assert=*/true, BI, &BB);
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000612 }
Tobias Grosser75805372011-04-29 06:27:02 +0000613
Johannes Doerfert757a32b2015-10-04 14:54:27 +0000614 ICmpInst *ICmp = cast<ICmpInst>(Condition);
Tobias Grosser75805372011-04-29 06:27:02 +0000615
Johannes Doerfert757a32b2015-10-04 14:54:27 +0000616 // Are both operands of the ICmp affine?
617 if (isa<UndefValue>(ICmp->getOperand(0)) ||
618 isa<UndefValue>(ICmp->getOperand(1)))
619 return invalid<ReportUndefOperand>(Context, /*Assert=*/true, &BB, ICmp);
Tobias Grosser75805372011-04-29 06:27:02 +0000620
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000621 Loop *L = LI.getLoopFor(&BB);
622 const SCEV *LHS = SE.getSCEVAtScope(ICmp->getOperand(0), L);
623 const SCEV *RHS = SE.getSCEVAtScope(ICmp->getOperand(1), L);
Tobias Grosser75805372011-04-29 06:27:02 +0000624
Tobias Grosseree457592017-09-24 09:25:30 +0000625 LHS = tryForwardThroughPHI(LHS, Context.CurRegion, SE, LI, DT);
626 RHS = tryForwardThroughPHI(RHS, Context.CurRegion, SE, LI, DT);
627
Johannes Doerfertbda81432016-12-02 17:55:41 +0000628 // If unsigned operations are not allowed try to approximate the region.
629 if (ICmp->isUnsigned() && !PollyAllowUnsignedOperations)
630 return !IsLoopBranch && AllowNonAffineSubRegions &&
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000631 addOverApproximatedRegion(RI.getRegionFor(&BB), Context);
Johannes Doerfertbda81432016-12-02 17:55:41 +0000632
Johannes Doerferta94ae1a2016-12-02 17:49:52 +0000633 // Check for invalid usage of different pointers in one expression.
634 if (ICmp->isEquality() && involvesMultiplePtrs(LHS, nullptr, L) &&
635 involvesMultiplePtrs(RHS, nullptr, L))
636 return false;
637
638 // Check for invalid usage of different pointers in a relational comparison.
639 if (ICmp->isRelational() && involvesMultiplePtrs(LHS, RHS, L))
640 return false;
641
Michael Kruse09eb4452016-03-03 22:10:47 +0000642 if (isAffine(LHS, L, Context) && isAffine(RHS, L, Context))
Johannes Doerfert757a32b2015-10-04 14:54:27 +0000643 return true;
Tobias Grosser75805372011-04-29 06:27:02 +0000644
Johannes Doerfert757a32b2015-10-04 14:54:27 +0000645 if (!IsLoopBranch && AllowNonAffineSubRegions &&
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000646 addOverApproximatedRegion(RI.getRegionFor(&BB), Context))
Johannes Doerfert757a32b2015-10-04 14:54:27 +0000647 return true;
648
649 if (IsLoopBranch)
650 return false;
651
652 return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB, LHS, RHS,
653 ICmp);
Tobias Grosser75805372011-04-29 06:27:02 +0000654}
655
Johannes Doerfert757a32b2015-10-04 14:54:27 +0000656bool ScopDetection::isValidCFG(BasicBlock &BB, bool IsLoopBranch,
Tobias Grosserb76cd3c2015-11-11 08:42:20 +0000657 bool AllowUnreachable,
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000658 DetectionContext &Context) const {
659 Region &CurRegion = Context.CurRegion;
660
661 TerminatorInst *TI = BB.getTerminator();
662
Tobias Grosserb76cd3c2015-11-11 08:42:20 +0000663 if (AllowUnreachable && isa<UnreachableInst>(TI))
664 return true;
665
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000666 // Return instructions are only valid if the region is the top level region.
Philip Pfaffe1a0128f2017-05-24 18:39:39 +0000667 if (isa<ReturnInst>(TI) && CurRegion.isTopLevelRegion())
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000668 return true;
669
670 Value *Condition = getConditionFromTerminator(TI);
671
672 if (!Condition)
673 return invalid<ReportInvalidTerminator>(Context, /*Assert=*/true, &BB);
674
675 // UndefValue is not allowed as condition.
676 if (isa<UndefValue>(Condition))
677 return invalid<ReportUndefCond>(Context, /*Assert=*/true, TI, &BB);
678
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000679 if (BranchInst *BI = dyn_cast<BranchInst>(TI))
Johannes Doerfert757a32b2015-10-04 14:54:27 +0000680 return isValidBranch(BB, BI, Condition, IsLoopBranch, Context);
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000681
682 SwitchInst *SI = dyn_cast<SwitchInst>(TI);
683 assert(SI && "Terminator was neither branch nor switch");
684
Johannes Doerfert757a32b2015-10-04 14:54:27 +0000685 return isValidSwitch(BB, SI, Condition, IsLoopBranch, Context);
Johannes Doerfert9a132f32015-09-28 09:33:22 +0000686}
687
Johannes Doerfertcea61932016-02-21 19:13:19 +0000688bool ScopDetection::isValidCallInst(CallInst &CI,
689 DetectionContext &Context) const {
Johannes Doerfert3f500fa2015-01-25 18:07:30 +0000690 if (CI.doesNotReturn())
Tobias Grosser75805372011-04-29 06:27:02 +0000691 return false;
692
693 if (CI.doesNotAccessMemory())
694 return true;
695
Johannes Doerfertcea61932016-02-21 19:13:19 +0000696 if (auto *II = dyn_cast<IntrinsicInst>(&CI))
Johannes Doerferta7920982016-02-25 14:08:48 +0000697 if (isValidIntrinsicInst(*II, Context))
698 return true;
Johannes Doerfertcea61932016-02-21 19:13:19 +0000699
Tobias Grosser75805372011-04-29 06:27:02 +0000700 Function *CalledFunction = CI.getCalledFunction();
701
702 // Indirect calls are not supported.
Tobias Grosser8dd653d2016-06-22 16:22:00 +0000703 if (CalledFunction == nullptr)
Tobias Grosser75805372011-04-29 06:27:02 +0000704 return false;
705
Michael Kruse5369ea52018-04-20 18:55:44 +0000706 if (isDebugCall(&CI)) {
707 DEBUG(dbgs() << "Allow call to debug function: "
708 << CalledFunction->getName() << '\n');
709 return true;
710 }
711
Tobias Grosser898a6362016-03-23 06:40:15 +0000712 if (AllowModrefCall) {
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000713 switch (AA.getModRefBehavior(CalledFunction)) {
Tobias Grosserb94e9b32016-11-21 09:04:45 +0000714 case FMRB_UnknownModRefBehavior:
Tobias Grosser898a6362016-03-23 06:40:15 +0000715 return false;
Tobias Grosserb94e9b32016-11-21 09:04:45 +0000716 case FMRB_DoesNotAccessMemory:
717 case FMRB_OnlyReadsMemory:
Johannes Doerferta7920982016-02-25 14:08:48 +0000718 // Implicitly disable delinearization since we have an unknown
719 // accesses with an unknown access function.
720 Context.HasUnknownAccess = true;
Tobias Grosser898a6362016-03-23 06:40:15 +0000721 Context.AST.add(&CI);
722 return true;
Tobias Grosserb94e9b32016-11-21 09:04:45 +0000723 case FMRB_OnlyReadsArgumentPointees:
724 case FMRB_OnlyAccessesArgumentPointees:
Tobias Grosser898a6362016-03-23 06:40:15 +0000725 for (const auto &Arg : CI.arg_operands()) {
726 if (!Arg->getType()->isPointerTy())
727 continue;
Johannes Doerferta7920982016-02-25 14:08:48 +0000728
Tobias Grosser898a6362016-03-23 06:40:15 +0000729 // Bail if a pointer argument has a base address not known to
730 // ScalarEvolution. Note that a zero pointer is acceptable.
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000731 auto *ArgSCEV = SE.getSCEVAtScope(Arg, LI.getLoopFor(CI.getParent()));
Tobias Grosser898a6362016-03-23 06:40:15 +0000732 if (ArgSCEV->isZero())
733 continue;
734
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000735 auto *BP = dyn_cast<SCEVUnknown>(SE.getPointerBase(ArgSCEV));
Tobias Grosser898a6362016-03-23 06:40:15 +0000736 if (!BP)
737 return false;
738
739 // Implicitly disable delinearization since we have an unknown
740 // accesses with an unknown access function.
741 Context.HasUnknownAccess = true;
742 }
743
744 Context.AST.add(&CI);
745 return true;
Weiming Zhao7614e172016-07-11 18:27:52 +0000746 case FMRB_DoesNotReadMemory:
Tobias Grosser70d27092016-11-13 19:27:24 +0000747 case FMRB_OnlyAccessesInaccessibleMem:
748 case FMRB_OnlyAccessesInaccessibleOrArgMem:
Weiming Zhao7614e172016-07-11 18:27:52 +0000749 return false;
Tobias Grosser898a6362016-03-23 06:40:15 +0000750 }
Johannes Doerferta7920982016-02-25 14:08:48 +0000751 }
752
Johannes Doerfertcea61932016-02-21 19:13:19 +0000753 return false;
754}
755
756bool ScopDetection::isValidIntrinsicInst(IntrinsicInst &II,
757 DetectionContext &Context) const {
758 if (isIgnoredIntrinsic(&II))
Tobias Grosser9c0ffe32015-08-30 16:57:15 +0000759 return true;
Johannes Doerfert3f500fa2015-01-25 18:07:30 +0000760
Johannes Doerfertcea61932016-02-21 19:13:19 +0000761 // The closest loop surrounding the call instruction.
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000762 Loop *L = LI.getLoopFor(II.getParent());
Johannes Doerfertcea61932016-02-21 19:13:19 +0000763
764 // The access function and base pointer for memory intrinsics.
765 const SCEV *AF;
766 const SCEVUnknown *BP;
767
768 switch (II.getIntrinsicID()) {
769 // Memory intrinsics that can be represented are supported.
Eugene Zelenkoa32707d2017-08-25 21:35:27 +0000770 case Intrinsic::memmove:
771 case Intrinsic::memcpy:
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000772 AF = SE.getSCEVAtScope(cast<MemTransferInst>(II).getSource(), L);
Johannes Doerfert733ea342016-03-24 13:50:04 +0000773 if (!AF->isZero()) {
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000774 BP = dyn_cast<SCEVUnknown>(SE.getPointerBase(AF));
Johannes Doerfert733ea342016-03-24 13:50:04 +0000775 // Bail if the source pointer is not valid.
776 if (!isValidAccess(&II, AF, BP, Context))
777 return false;
778 }
Johannes Doerfertcea61932016-02-21 19:13:19 +0000779 // Fall through
Eugene Zelenkoa32707d2017-08-25 21:35:27 +0000780 case Intrinsic::memset:
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000781 AF = SE.getSCEVAtScope(cast<MemIntrinsic>(II).getDest(), L);
Johannes Doerfert733ea342016-03-24 13:50:04 +0000782 if (!AF->isZero()) {
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000783 BP = dyn_cast<SCEVUnknown>(SE.getPointerBase(AF));
Johannes Doerfert733ea342016-03-24 13:50:04 +0000784 // Bail if the destination pointer is not valid.
785 if (!isValidAccess(&II, AF, BP, Context))
786 return false;
787 }
Johannes Doerfertcea61932016-02-21 19:13:19 +0000788
789 // Bail if the length is not affine.
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000790 if (!isAffine(SE.getSCEVAtScope(cast<MemIntrinsic>(II).getLength(), L), L,
Johannes Doerfertcea61932016-02-21 19:13:19 +0000791 Context))
792 return false;
793
794 return true;
795 default:
796 break;
797 }
798
Tobias Grosser75805372011-04-29 06:27:02 +0000799 return false;
800}
801
Michael Kruse5a4ec5c2017-03-07 20:28:43 +0000802bool ScopDetection::isInvariant(Value &Val, const Region &Reg,
803 DetectionContext &Ctx) const {
Tobias Grosser458fb782014-01-28 12:58:58 +0000804 // A reference to function argument or constant value is invariant.
805 if (isa<Argument>(Val) || isa<Constant>(Val))
806 return true;
807
Michael Kruse5a4ec5c2017-03-07 20:28:43 +0000808 Instruction *I = dyn_cast<Instruction>(&Val);
Tobias Grosser458fb782014-01-28 12:58:58 +0000809 if (!I)
810 return false;
811
812 if (!Reg.contains(I))
813 return true;
814
Michael Kruse5a4ec5c2017-03-07 20:28:43 +0000815 // Loads within the SCoP may read arbitrary values, need to hoist them. If it
816 // is not hoistable, it will be rejected later, but here we assume it is and
817 // that makes the value invariant.
818 if (auto LI = dyn_cast<LoadInst>(I)) {
819 Ctx.RequiredILS.insert(LI);
820 return true;
821 }
822
Michael Kruse6744efa8d2017-03-08 15:14:46 +0000823 return false;
Tobias Grosser458fb782014-01-28 12:58:58 +0000824}
825
Eugene Zelenkoa32707d2017-08-25 21:35:27 +0000826namespace {
827
Tobias Grosserc80d6972016-09-02 06:33:33 +0000828/// Remove smax of smax(0, size) expressions from a SCEV expression and
Tobias Grosser2f8e43d2015-11-24 17:06:38 +0000829/// register the '...' components.
830///
Michael Krusea6d48f52017-06-08 12:06:15 +0000831/// Array access expressions as they are generated by GFortran contain smax(0,
Tobias Grosser2f8e43d2015-11-24 17:06:38 +0000832/// size) expressions that confuse the 'normal' delinearization algorithm.
833/// However, if we extract such expressions before the normal delinearization
834/// takes place they can actually help to identify array size expressions in
Michael Krusea6d48f52017-06-08 12:06:15 +0000835/// Fortran accesses. For the subsequently following delinearization the smax(0,
Tobias Grosser2f8e43d2015-11-24 17:06:38 +0000836/// size) component can be replaced by just 'size'. This is correct as we will
837/// always add and verify the assumption that for all subscript expressions
838/// 'exp' the inequality 0 <= exp < size holds. Hence, we will also verify
839/// that 0 <= size, which means smax(0, size) == size.
Tobias Grosserebb626e2016-10-29 06:19:34 +0000840class SCEVRemoveMax : public SCEVRewriteVisitor<SCEVRemoveMax> {
Tobias Grosser2f8e43d2015-11-24 17:06:38 +0000841public:
Eugene Zelenkoa32707d2017-08-25 21:35:27 +0000842 SCEVRemoveMax(ScalarEvolution &SE, std::vector<const SCEV *> *Terms)
843 : SCEVRewriteVisitor(SE), Terms(Terms) {}
844
Tobias Grosserebb626e2016-10-29 06:19:34 +0000845 static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
846 std::vector<const SCEV *> *Terms = nullptr) {
847 SCEVRemoveMax Rewriter(SE, Terms);
848 return Rewriter.visit(Scev);
Tobias Grosser2f8e43d2015-11-24 17:06:38 +0000849 }
850
Tobias Grosser2f8e43d2015-11-24 17:06:38 +0000851 const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
Michael Kruse8fc28962015-12-20 14:42:32 +0000852 if ((Expr->getNumOperands() == 2) && Expr->getOperand(0)->isZero()) {
Tobias Grosser2f8e43d2015-11-24 17:06:38 +0000853 auto Res = visit(Expr->getOperand(1));
854 if (Terms)
855 (*Terms).push_back(Res);
856 return Res;
857 }
858
859 return Expr;
860 }
861
Tobias Grosser2f8e43d2015-11-24 17:06:38 +0000862private:
Tobias Grosser2f8e43d2015-11-24 17:06:38 +0000863 std::vector<const SCEV *> *Terms;
864};
Eugene Zelenkoa32707d2017-08-25 21:35:27 +0000865} // namespace
866
Tobias Grosserd68ba422015-11-24 05:00:36 +0000867SmallVector<const SCEV *, 4>
868ScopDetection::getDelinearizationTerms(DetectionContext &Context,
869 const SCEVUnknown *BasePointer) const {
870 SmallVector<const SCEV *, 4> Terms;
871 for (const auto &Pair : Context.Accesses[BasePointer]) {
Tobias Grosser2f8e43d2015-11-24 17:06:38 +0000872 std::vector<const SCEV *> MaxTerms;
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000873 SCEVRemoveMax::rewrite(Pair.second, SE, &MaxTerms);
Eugene Zelenkoa32707d2017-08-25 21:35:27 +0000874 if (!MaxTerms.empty()) {
Tobias Grosser2f8e43d2015-11-24 17:06:38 +0000875 Terms.insert(Terms.begin(), MaxTerms.begin(), MaxTerms.end());
876 continue;
877 }
Tobias Grosserd68ba422015-11-24 05:00:36 +0000878 // In case the outermost expression is a plain add, we check if any of its
879 // terms has the form 4 * %inst * %param * %param ..., aka a term that
880 // contains a product between a parameter and an instruction that is
881 // inside the scop. Such instructions, if allowed at all, are instructions
882 // SCEV can not represent, but Polly is still looking through. As a
883 // result, these instructions can depend on induction variables and are
884 // most likely no array sizes. However, terms that are multiplied with
885 // them are likely candidates for array sizes.
886 if (auto *AF = dyn_cast<SCEVAddExpr>(Pair.second)) {
887 for (auto Op : AF->operands()) {
888 if (auto *AF2 = dyn_cast<SCEVAddRecExpr>(Op))
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000889 SE.collectParametricTerms(AF2, Terms);
Tobias Grosserd68ba422015-11-24 05:00:36 +0000890 if (auto *AF2 = dyn_cast<SCEVMulExpr>(Op)) {
891 SmallVector<const SCEV *, 0> Operands;
Johannes Doerfertfb79a962015-02-23 14:18:28 +0000892
Tobias Grosserd68ba422015-11-24 05:00:36 +0000893 for (auto *MulOp : AF2->operands()) {
894 if (auto *Const = dyn_cast<SCEVConstant>(MulOp))
895 Operands.push_back(Const);
896 if (auto *Unknown = dyn_cast<SCEVUnknown>(MulOp)) {
897 if (auto *Inst = dyn_cast<Instruction>(Unknown->getValue())) {
898 if (!Context.CurRegion.contains(Inst))
Tobias Grosser1b13dde2015-06-29 14:44:22 +0000899 Operands.push_back(MulOp);
Tobias Grosserd68ba422015-11-24 05:00:36 +0000900
901 } else {
902 Operands.push_back(MulOp);
Tobias Grosser1b13dde2015-06-29 14:44:22 +0000903 }
904 }
Tobias Grosser1b13dde2015-06-29 14:44:22 +0000905 }
Tobias Grosserd68ba422015-11-24 05:00:36 +0000906 if (Operands.size())
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000907 Terms.push_back(SE.getMulExpr(Operands));
Tobias Grosser1b13dde2015-06-29 14:44:22 +0000908 }
909 }
Tobias Grosser230acc42014-09-13 14:47:55 +0000910 }
Tobias Grosserd68ba422015-11-24 05:00:36 +0000911 if (Terms.empty())
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000912 SE.collectParametricTerms(Pair.second, Terms);
Tobias Grosserd68ba422015-11-24 05:00:36 +0000913 }
914 return Terms;
915}
Sebastian Pope8863b82014-05-12 19:02:02 +0000916
Tobias Grosserd68ba422015-11-24 05:00:36 +0000917bool ScopDetection::hasValidArraySizes(DetectionContext &Context,
918 SmallVectorImpl<const SCEV *> &Sizes,
Michael Krusec7e0d9c2016-03-01 21:44:06 +0000919 const SCEVUnknown *BasePointer,
920 Loop *Scope) const {
Tobias Grosser1e55db32017-05-27 15:18:53 +0000921 // If no sizes were found, all sizes are trivially valid. We allow this case
922 // to make it possible to pass known-affine accesses to the delinearization to
923 // try to recover some interesting multi-dimensional accesses, but to still
924 // allow the already known to be affine access in case the delinearization
925 // fails. In such situations, the delinearization will just return a Sizes
926 // array of size zero.
927 if (Sizes.size() == 0)
928 return true;
929
Tobias Grosserd68ba422015-11-24 05:00:36 +0000930 Value *BaseValue = BasePointer->getValue();
931 Region &CurRegion = Context.CurRegion;
932 for (const SCEV *DelinearizedSize : Sizes) {
Johannes Doerfertec8a2172016-04-25 13:32:36 +0000933 if (!isAffine(DelinearizedSize, Scope, Context)) {
Tobias Grosserd68ba422015-11-24 05:00:36 +0000934 Sizes.clear();
935 break;
Tobias Grosser5528dcd2015-10-25 08:40:38 +0000936 }
Tobias Grosserd68ba422015-11-24 05:00:36 +0000937 if (auto *Unknown = dyn_cast<SCEVUnknown>(DelinearizedSize)) {
938 auto *V = dyn_cast<Value>(Unknown->getValue());
939 if (auto *Load = dyn_cast<LoadInst>(V)) {
940 if (Context.CurRegion.contains(Load) &&
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000941 isHoistableLoad(Load, CurRegion, LI, SE, DT))
Tobias Grosserd68ba422015-11-24 05:00:36 +0000942 Context.RequiredILS.insert(Load);
Tobias Grosser230acc42014-09-13 14:47:55 +0000943 continue;
Tobias Grosser230acc42014-09-13 14:47:55 +0000944 }
Sebastian Pop46e1ecd2014-05-09 22:45:15 +0000945 }
Siddharth Bhata1b20862017-07-13 12:18:56 +0000946 if (hasScalarDepsInsideRegion(DelinearizedSize, &CurRegion, Scope, false,
947 Context.RequiredILS))
Tobias Grosserbfaf1ae2015-12-21 09:09:39 +0000948 return invalid<ReportNonAffineAccess>(
Tobias Grosserd68ba422015-11-24 05:00:36 +0000949 Context, /*Assert=*/true, DelinearizedSize,
950 Context.Accesses[BasePointer].front().first, BaseValue);
951 }
Tobias Grosser230acc42014-09-13 14:47:55 +0000952
Tobias Grosserd68ba422015-11-24 05:00:36 +0000953 // No array shape derived.
954 if (Sizes.empty()) {
955 if (AllowNonAffine)
956 return true;
957
Tobias Grosser230acc42014-09-13 14:47:55 +0000958 for (const auto &Pair : Context.Accesses[BasePointer]) {
959 const Instruction *Insn = Pair.first;
Tobias Grosserd68ba422015-11-24 05:00:36 +0000960 const SCEV *AF = Pair.second;
Tobias Grosser230acc42014-09-13 14:47:55 +0000961
Johannes Doerfertec8a2172016-04-25 13:32:36 +0000962 if (!isAffine(AF, Scope, Context)) {
Tobias Grosserd68ba422015-11-24 05:00:36 +0000963 invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF, Insn,
964 BaseValue);
965 if (!KeepGoing)
Tobias Grosser230acc42014-09-13 14:47:55 +0000966 return false;
967 }
968 }
Tobias Grosserd68ba422015-11-24 05:00:36 +0000969 return false;
Sebastian Pop46e1ecd2014-05-09 22:45:15 +0000970 }
Sebastian Pope8863b82014-05-12 19:02:02 +0000971 return true;
Sebastian Pop46e1ecd2014-05-09 22:45:15 +0000972}
973
Tobias Grosserd68ba422015-11-24 05:00:36 +0000974// We first store the resulting memory accesses in TempMemoryAccesses. Only
975// if the access functions for all memory accesses have been successfully
976// delinearized we continue. Otherwise, we either report a failure or, if
977// non-affine accesses are allowed, we drop the information. In case the
978// information is dropped the memory accesses need to be overapproximated
979// when translated to a polyhedral representation.
980bool ScopDetection::computeAccessFunctions(
981 DetectionContext &Context, const SCEVUnknown *BasePointer,
982 std::shared_ptr<ArrayShape> Shape) const {
983 Value *BaseValue = BasePointer->getValue();
984 bool BasePtrHasNonAffine = false;
985 MapInsnToMemAcc TempMemoryAccesses;
986 for (const auto &Pair : Context.Accesses[BasePointer]) {
987 const Instruction *Insn = Pair.first;
988 auto *AF = Pair.second;
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000989 AF = SCEVRemoveMax::rewrite(AF, SE);
Tobias Grosserd68ba422015-11-24 05:00:36 +0000990 bool IsNonAffine = false;
991 TempMemoryAccesses.insert(std::make_pair(Insn, MemAcc(Insn, Shape)));
992 MemAcc *Acc = &TempMemoryAccesses.find(Insn)->second;
Philip Pfaffe5cc87e32017-05-12 14:37:29 +0000993 auto *Scope = LI.getLoopFor(Insn->getParent());
Tobias Grosserd68ba422015-11-24 05:00:36 +0000994
995 if (!AF) {
Johannes Doerfertec8a2172016-04-25 13:32:36 +0000996 if (isAffine(Pair.second, Scope, Context))
Tobias Grosserd68ba422015-11-24 05:00:36 +0000997 Acc->DelinearizedSubscripts.push_back(Pair.second);
998 else
999 IsNonAffine = true;
1000 } else {
Tobias Grosser1e55db32017-05-27 15:18:53 +00001001 if (Shape->DelinearizedSizes.size() == 0) {
1002 Acc->DelinearizedSubscripts.push_back(AF);
1003 } else {
1004 SE.computeAccessFunctions(AF, Acc->DelinearizedSubscripts,
1005 Shape->DelinearizedSizes);
1006 if (Acc->DelinearizedSubscripts.size() == 0)
1007 IsNonAffine = true;
1008 }
Tobias Grosserd68ba422015-11-24 05:00:36 +00001009 for (const SCEV *S : Acc->DelinearizedSubscripts)
Johannes Doerfertec8a2172016-04-25 13:32:36 +00001010 if (!isAffine(S, Scope, Context))
Tobias Grosserd68ba422015-11-24 05:00:36 +00001011 IsNonAffine = true;
1012 }
1013
1014 // (Possibly) report non affine access
1015 if (IsNonAffine) {
1016 BasePtrHasNonAffine = true;
1017 if (!AllowNonAffine)
1018 invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, Pair.second,
1019 Insn, BaseValue);
1020 if (!KeepGoing && !AllowNonAffine)
1021 return false;
1022 }
1023 }
1024
1025 if (!BasePtrHasNonAffine)
Hongbin Zheng22623202016-02-15 00:20:58 +00001026 Context.InsnToMemAcc.insert(TempMemoryAccesses.begin(),
1027 TempMemoryAccesses.end());
Tobias Grosserd68ba422015-11-24 05:00:36 +00001028
1029 return true;
1030}
1031
Michael Krusec7e0d9c2016-03-01 21:44:06 +00001032bool ScopDetection::hasBaseAffineAccesses(DetectionContext &Context,
1033 const SCEVUnknown *BasePointer,
1034 Loop *Scope) const {
Tobias Grosserd68ba422015-11-24 05:00:36 +00001035 auto Shape = std::shared_ptr<ArrayShape>(new ArrayShape(BasePointer));
1036
1037 auto Terms = getDelinearizationTerms(Context, BasePointer);
1038
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001039 SE.findArrayDimensions(Terms, Shape->DelinearizedSizes,
1040 Context.ElementSize[BasePointer]);
Tobias Grosserd68ba422015-11-24 05:00:36 +00001041
Michael Krusec7e0d9c2016-03-01 21:44:06 +00001042 if (!hasValidArraySizes(Context, Shape->DelinearizedSizes, BasePointer,
1043 Scope))
Tobias Grosserd68ba422015-11-24 05:00:36 +00001044 return false;
1045
1046 return computeAccessFunctions(Context, BasePointer, Shape);
1047}
1048
1049bool ScopDetection::hasAffineMemoryAccesses(DetectionContext &Context) const {
Johannes Doerferta7920982016-02-25 14:08:48 +00001050 // TODO: If we have an unknown access and other non-affine accesses we do
1051 // not try to delinearize them for now.
1052 if (Context.HasUnknownAccess && !Context.NonAffineAccesses.empty())
1053 return AllowNonAffine;
1054
Michael Krusec7e0d9c2016-03-01 21:44:06 +00001055 for (auto &Pair : Context.NonAffineAccesses) {
1056 auto *BasePointer = Pair.first;
1057 auto *Scope = Pair.second;
1058 if (!hasBaseAffineAccesses(Context, BasePointer, Scope)) {
Tobias Grosserd68ba422015-11-24 05:00:36 +00001059 if (KeepGoing)
1060 continue;
1061 else
1062 return false;
1063 }
Michael Krusec7e0d9c2016-03-01 21:44:06 +00001064 }
Tobias Grosserd68ba422015-11-24 05:00:36 +00001065 return true;
1066}
1067
Johannes Doerfertcea61932016-02-21 19:13:19 +00001068bool ScopDetection::isValidAccess(Instruction *Inst, const SCEV *AF,
1069 const SCEVUnknown *BP,
1070 DetectionContext &Context) const {
Johannes Doerfertfb79a962015-02-23 14:18:28 +00001071
Johannes Doerfertcea61932016-02-21 19:13:19 +00001072 if (!BP)
Michael Kruse70131d32016-01-27 17:09:17 +00001073 return invalid<ReportNoBasePtr>(Context, /*Assert=*/true, Inst);
Tobias Grosserb8710b52011-11-10 12:44:50 +00001074
Johannes Doerfertcea61932016-02-21 19:13:19 +00001075 auto *BV = BP->getValue();
1076 if (isa<UndefValue>(BV))
Michael Kruse70131d32016-01-27 17:09:17 +00001077 return invalid<ReportUndefBasePtr>(Context, /*Assert=*/true, Inst);
Tobias Grosserb8710b52011-11-10 12:44:50 +00001078
Johannes Doerfertcea61932016-02-21 19:13:19 +00001079 // FIXME: Think about allowing IntToPtrInst
1080 if (IntToPtrInst *Inst = dyn_cast<IntToPtrInst>(BV))
1081 return invalid<ReportIntToPtr>(Context, /*Assert=*/true, Inst);
1082
Tobias Grosser458fb782014-01-28 12:58:58 +00001083 // Check that the base address of the access is invariant in the current
1084 // region.
Michael Kruse5a4ec5c2017-03-07 20:28:43 +00001085 if (!isInvariant(*BV, Context.CurRegion, Context))
Johannes Doerfertcea61932016-02-21 19:13:19 +00001086 return invalid<ReportVariantBasePtr>(Context, /*Assert=*/true, BV, Inst);
Tobias Grosser458fb782014-01-28 12:58:58 +00001087
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001088 AF = SE.getMinusSCEV(AF, BP);
Tobias Grosserb8710b52011-11-10 12:44:50 +00001089
Johannes Doerfertcea61932016-02-21 19:13:19 +00001090 const SCEV *Size;
1091 if (!isa<MemIntrinsic>(Inst)) {
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001092 Size = SE.getElementSize(Inst);
Tobias Grosser8ebdc2d2016-02-07 08:48:57 +00001093 } else {
Johannes Doerfertcea61932016-02-21 19:13:19 +00001094 auto *SizeTy =
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001095 SE.getEffectiveSCEVType(PointerType::getInt8PtrTy(SE.getContext()));
1096 Size = SE.getConstant(SizeTy, 8);
Tobias Grosser8ebdc2d2016-02-07 08:48:57 +00001097 }
Tobias Grosserbcd4eff2014-09-13 14:47:40 +00001098
Johannes Doerfertcea61932016-02-21 19:13:19 +00001099 if (Context.ElementSize[BP]) {
1100 if (!AllowDifferentTypes && Context.ElementSize[BP] != Size)
1101 return invalid<ReportDifferentArrayElementSize>(Context, /*Assert=*/true,
1102 Inst, BV);
1103
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001104 Context.ElementSize[BP] = SE.getSMinExpr(Size, Context.ElementSize[BP]);
Johannes Doerfertcea61932016-02-21 19:13:19 +00001105 } else {
1106 Context.ElementSize[BP] = Size;
1107 }
1108
1109 bool IsVariantInNonAffineLoop = false;
Johannes Doerfertf3e98f42015-04-12 22:52:20 +00001110 SetVector<const Loop *> Loops;
Johannes Doerfertcea61932016-02-21 19:13:19 +00001111 findLoops(AF, Loops);
Johannes Doerfertf3e98f42015-04-12 22:52:20 +00001112 for (const Loop *L : Loops)
1113 if (Context.BoxedLoopsSet.count(L))
Johannes Doerfertcea61932016-02-21 19:13:19 +00001114 IsVariantInNonAffineLoop = true;
Johannes Doerfertf3e98f42015-04-12 22:52:20 +00001115
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001116 auto *Scope = LI.getLoopFor(Inst->getParent());
Johannes Doerfertec8a2172016-04-25 13:32:36 +00001117 bool IsAffine = !IsVariantInNonAffineLoop && isAffine(AF, Scope, Context);
Johannes Doerfertcea61932016-02-21 19:13:19 +00001118 // Do not try to delinearize memory intrinsics and force them to be affine.
1119 if (isa<MemIntrinsic>(Inst) && !IsAffine) {
1120 return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF, Inst,
1121 BV);
1122 } else if (PollyDelinearize && !IsVariantInNonAffineLoop) {
1123 Context.Accesses[BP].push_back({Inst, AF});
Sebastian Pop46e1ecd2014-05-09 22:45:15 +00001124
Tobias Grosser1e55db32017-05-27 15:18:53 +00001125 if (!IsAffine || hasIVParams(AF))
Michael Krusec7e0d9c2016-03-01 21:44:06 +00001126 Context.NonAffineAccesses.insert(
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001127 std::make_pair(BP, LI.getLoopFor(Inst->getParent())));
Johannes Doerfertcea61932016-02-21 19:13:19 +00001128 } else if (!AllowNonAffine && !IsAffine) {
1129 return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF, Inst,
1130 BV);
Sebastian Pop18016682014-04-08 21:20:44 +00001131 }
Tobias Grosser75805372011-04-29 06:27:02 +00001132
Tobias Grosser1eedb672014-09-24 21:04:29 +00001133 if (IgnoreAliasing)
Sebastian Pop8c2d7532013-07-03 22:50:36 +00001134 return true;
Tobias Grosserfff5adc2011-11-10 13:21:43 +00001135
Sebastian Pop8c2d7532013-07-03 22:50:36 +00001136 // Check if the base pointer of the memory access does alias with
1137 // any other pointer. This cannot be handled at the moment.
Benjamin Kramerae81abf2014-10-05 11:58:57 +00001138 AAMDNodes AATags;
Johannes Doerfertcea61932016-02-21 19:13:19 +00001139 Inst->getAAMetadata(AATags);
Benjamin Kramerae81abf2014-10-05 11:58:57 +00001140 AliasSet &AS = Context.AST.getAliasSetForPointer(
Johannes Doerfertcea61932016-02-21 19:13:19 +00001141 BP->getValue(), MemoryLocation::UnknownSize, AATags);
Tobias Grosser428b3e42013-02-04 15:46:25 +00001142
Tobias Grosser1eedb672014-09-24 21:04:29 +00001143 if (!AS.isMustAlias()) {
1144 if (PollyUseRuntimeAliasChecks) {
1145 bool CanBuildRunTimeCheck = true;
1146 // The run-time alias check places code that involves the base pointer at
1147 // the beginning of the SCoP. This breaks if the base pointer is defined
1148 // inside the scop. Hence, we can only create a run-time check if we are
1149 // sure the base pointer is not an instruction defined inside the scop.
Johannes Doerfert09e36972015-10-07 20:17:36 +00001150 // However, we can ignore loads that will be hoisted.
Tobias Grosser1eedb672014-09-24 21:04:29 +00001151 for (const auto &Ptr : AS) {
1152 Instruction *Inst = dyn_cast<Instruction>(Ptr.getValue());
Johannes Doerfertcea61932016-02-21 19:13:19 +00001153 if (Inst && Context.CurRegion.contains(Inst)) {
Johannes Doerfert09e36972015-10-07 20:17:36 +00001154 auto *Load = dyn_cast<LoadInst>(Inst);
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001155 if (Load && isHoistableLoad(Load, Context.CurRegion, LI, SE, DT)) {
Johannes Doerfert09e36972015-10-07 20:17:36 +00001156 Context.RequiredILS.insert(Load);
1157 continue;
1158 }
1159
Tobias Grosser1eedb672014-09-24 21:04:29 +00001160 CanBuildRunTimeCheck = false;
1161 break;
1162 }
1163 }
1164
1165 if (CanBuildRunTimeCheck)
1166 return true;
1167 }
Michael Kruse70131d32016-01-27 17:09:17 +00001168 return invalid<ReportAlias>(Context, /*Assert=*/true, Inst, AS);
Tobias Grosser1eedb672014-09-24 21:04:29 +00001169 }
Tobias Grosser75805372011-04-29 06:27:02 +00001170
1171 return true;
1172}
1173
Johannes Doerfertcea61932016-02-21 19:13:19 +00001174bool ScopDetection::isValidMemoryAccess(MemAccInst Inst,
1175 DetectionContext &Context) const {
1176 Value *Ptr = Inst.getPointerOperand();
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001177 Loop *L = LI.getLoopFor(Inst->getParent());
1178 const SCEV *AccessFunction = SE.getSCEVAtScope(Ptr, L);
Johannes Doerfertcea61932016-02-21 19:13:19 +00001179 const SCEVUnknown *BasePointer;
1180
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001181 BasePointer = dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
Johannes Doerfertcea61932016-02-21 19:13:19 +00001182
1183 return isValidAccess(Inst, AccessFunction, BasePointer, Context);
1184}
1185
Tobias Grosser75805372011-04-29 06:27:02 +00001186bool ScopDetection::isValidInstruction(Instruction &Inst,
1187 DetectionContext &Context) const {
Tobias Grosserb12b0062015-11-11 12:44:18 +00001188 for (auto &Op : Inst.operands()) {
1189 auto *OpInst = dyn_cast<Instruction>(&Op);
1190
1191 if (!OpInst)
1192 continue;
1193
Tobias Grosser1f93d0f2017-09-26 15:00:10 +00001194 if (isErrorBlock(*OpInst->getParent(), Context.CurRegion, LI, DT)) {
1195 auto *PHI = dyn_cast<PHINode>(OpInst);
1196 if (PHI) {
1197 for (User *U : PHI->users()) {
1198 if (!isa<TerminatorInst>(U))
1199 return false;
1200 }
1201 } else {
1202 return false;
1203 }
1204 }
Tobias Grosserb12b0062015-11-11 12:44:18 +00001205 }
1206
Johannes Doerfert81c41b92016-04-09 21:55:58 +00001207 if (isa<LandingPadInst>(&Inst) || isa<ResumeInst>(&Inst))
1208 return false;
1209
Tobias Grosser75805372011-04-29 06:27:02 +00001210 // We only check the call instruction but not invoke instruction.
1211 if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
Johannes Doerfertcea61932016-02-21 19:13:19 +00001212 if (isValidCallInst(*CI, Context))
Tobias Grosser75805372011-04-29 06:27:02 +00001213 return true;
1214
Andreas Simbuerger01a37a02014-04-02 11:54:01 +00001215 return invalid<ReportFuncCall>(Context, /*Assert=*/true, &Inst);
Tobias Grosser75805372011-04-29 06:27:02 +00001216 }
1217
Tobias Grosser1f0236d2016-11-21 09:07:30 +00001218 if (!Inst.mayReadOrWriteMemory()) {
Tobias Grosser5b1a7f22013-07-22 03:50:33 +00001219 if (!isa<AllocaInst>(Inst))
1220 return true;
Tobias Grosser75805372011-04-29 06:27:02 +00001221
Andreas Simbuerger01a37a02014-04-02 11:54:01 +00001222 return invalid<ReportAlloca>(Context, /*Assert=*/true, &Inst);
Tobias Grosser75805372011-04-29 06:27:02 +00001223 }
1224
1225 // Check the access function.
Michael Kruse70131d32016-01-27 17:09:17 +00001226 if (auto MemInst = MemAccInst::dyn_cast(Inst)) {
Hongbin Zheng8efb22e2016-02-27 01:49:58 +00001227 Context.hasStores |= isa<StoreInst>(MemInst);
1228 Context.hasLoads |= isa<LoadInst>(MemInst);
Michael Kruse70131d32016-01-27 17:09:17 +00001229 if (!MemInst.isSimple())
1230 return invalid<ReportNonSimpleMemoryAccess>(Context, /*Assert=*/true,
1231 &Inst);
Tobias Grosserbf45e742015-10-25 13:48:40 +00001232
Michael Kruse70131d32016-01-27 17:09:17 +00001233 return isValidMemoryAccess(MemInst, Context);
Tobias Grosserd1e33e72015-02-19 05:31:07 +00001234 }
Tobias Grosser75805372011-04-29 06:27:02 +00001235
1236 // We do not know this instruction, therefore we assume it is invalid.
Andreas Simbuerger01a37a02014-04-02 11:54:01 +00001237 return invalid<ReportUnknownInst>(Context, /*Assert=*/true, &Inst);
Tobias Grosser75805372011-04-29 06:27:02 +00001238}
1239
Tobias Grosser6d0970f2017-08-24 19:47:15 +00001240/// Check whether @p L has exiting blocks.
1241///
1242/// @param L The loop of interest
1243///
1244/// @return True if the loop has exiting blocks, false otherwise.
1245static bool hasExitingBlocks(Loop *L) {
1246 SmallVector<BasicBlock *, 4> ExitingBlocks;
1247 L->getExitingBlocks(ExitingBlocks);
1248 return !ExitingBlocks.empty();
1249}
1250
Johannes Doerfertd020b772015-08-27 06:53:52 +00001251bool ScopDetection::canUseISLTripCount(Loop *L,
1252 DetectionContext &Context) const {
Johannes Doerfert30ffb6f2015-10-04 14:53:18 +00001253 // Ensure the loop has valid exiting blocks as well as latches, otherwise we
1254 // need to overapproximate it as a boxed loop.
1255 SmallVector<BasicBlock *, 4> LoopControlBlocks;
Tobias Grosser151ae322016-04-03 19:36:52 +00001256 L->getExitingBlocks(LoopControlBlocks);
Johannes Doerfertd5edbd62016-04-03 23:09:06 +00001257 L->getLoopLatches(LoopControlBlocks);
Johannes Doerfert30ffb6f2015-10-04 14:53:18 +00001258 for (BasicBlock *ControlBB : LoopControlBlocks) {
Tobias Grosserb76cd3c2015-11-11 08:42:20 +00001259 if (!isValidCFG(*ControlBB, true, false, Context))
Johannes Doerfertd020b772015-08-27 06:53:52 +00001260 return false;
1261 }
1262
Johannes Doerfertd020b772015-08-27 06:53:52 +00001263 // We can use ISL to compute the trip count of L.
1264 return true;
1265}
1266
Tobias Grosser75805372011-04-29 06:27:02 +00001267bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const {
Tobias Grosser349d1c32016-09-20 17:05:22 +00001268 // Loops that contain part but not all of the blocks of a region cannot be
1269 // handled by the schedule generation. Such loop constructs can happen
1270 // because a region can contain BBs that have no path to the exit block
Tobias Grosser6d0970f2017-08-24 19:47:15 +00001271 // (Infinite loops, UnreachableInst), but such blocks are never part of a
1272 // loop.
1273 //
1274 // _______________
1275 // | Loop Header | <-----------.
1276 // --------------- |
1277 // | |
1278 // _______________ ______________
1279 // | RegionEntry |-----> | RegionExit |----->
1280 // --------------- --------------
1281 // |
1282 // _______________
1283 // | EndlessLoop | <--.
1284 // --------------- |
1285 // | |
1286 // \------------/
1287 //
1288 // In the example above, the loop (LoopHeader,RegionEntry,RegionExit) is
1289 // neither entirely contained in the region RegionEntry->RegionExit
1290 // (containing RegionEntry,EndlessLoop) nor is the region entirely contained
1291 // in the loop.
1292 // The block EndlessLoop is contained in the region because Region::contains
1293 // tests whether it is not dominated by RegionExit. This is probably to not
1294 // having to query the PostdominatorTree. Instead of an endless loop, a dead
1295 // end can also be formed by an UnreachableInst. This case is already caught
1296 // by isErrorBlock(). We hence only have to reject endless loops here.
1297 if (!hasExitingBlocks(L))
1298 return invalid<ReportLoopHasNoExit>(Context, /*Assert=*/true, L);
Tobias Grosser349d1c32016-09-20 17:05:22 +00001299
Michael Krusebeffdb92018-04-25 18:53:33 +00001300 // The algorithm for domain construction assumes that loops has only a single
1301 // exit block (and hence corresponds to a subregion). Note that we cannot use
1302 // L->getExitBlock() because it does not check whether all exiting edges point
1303 // to the same BB.
1304 SmallVector<BasicBlock *, 4> ExitBlocks;
1305 L->getExitBlocks(ExitBlocks);
1306 BasicBlock *TheExitBlock = ExitBlocks[0];
1307 for (BasicBlock *ExitBB : ExitBlocks) {
1308 if (TheExitBlock != ExitBB)
1309 return invalid<ReportLoopHasMultipleExits>(Context, /*Assert=*/true, L);
1310 }
1311
Johannes Doerfertf61df692015-10-04 14:56:08 +00001312 if (canUseISLTripCount(L, Context))
Johannes Doerfertba65c162015-02-24 11:45:21 +00001313 return true;
Johannes Doerfertf3e98f42015-04-12 22:52:20 +00001314
Johannes Doerfertb68cffb2015-09-10 15:27:46 +00001315 if (AllowNonAffineSubLoops && AllowNonAffineSubRegions) {
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001316 Region *R = RI.getRegionFor(L->getHeader());
Johannes Doerfert757a32b2015-10-04 14:54:27 +00001317 while (R != &Context.CurRegion && !R->contains(L))
1318 R = R->getParent();
1319
1320 if (addOverApproximatedRegion(R, Context))
1321 return true;
Johannes Doerfertf3e98f42015-04-12 22:52:20 +00001322 }
Tobias Grosser75805372011-04-29 06:27:02 +00001323
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001324 const SCEV *LoopCount = SE.getBackedgeTakenCount(L);
Johannes Doerfertba65c162015-02-24 11:45:21 +00001325 return invalid<ReportLoopBound>(Context, /*Assert=*/true, L, LoopCount);
Tobias Grosser75805372011-04-29 06:27:02 +00001326}
1327
Tobias Grosserc80d6972016-09-02 06:33:33 +00001328/// Return the number of loops in @p L (incl. @p L) that have a trip
Tobias Grosserb45ae562016-11-26 07:37:46 +00001329/// count that is not known to be less than @MinProfitableTrips.
1330ScopDetection::LoopStats
1331ScopDetection::countBeneficialSubLoops(Loop *L, ScalarEvolution &SE,
Tobias Grossercd01a362017-02-17 08:12:36 +00001332 unsigned MinProfitableTrips) {
Johannes Doerfert7175bdf2015-09-20 14:56:54 +00001333 auto *TripCount = SE.getBackedgeTakenCount(L);
1334
Tobias Grosserb45ae562016-11-26 07:37:46 +00001335 int NumLoops = 1;
1336 int MaxLoopDepth = 1;
Michael Kruse7fac28fa2017-08-23 13:29:59 +00001337 if (MinProfitableTrips > 0)
1338 if (auto *TripCountC = dyn_cast<SCEVConstant>(TripCount))
1339 if (TripCountC->getType()->getScalarSizeInBits() <= 64)
1340 if (TripCountC->getValue()->getZExtValue() <= MinProfitableTrips)
1341 NumLoops -= 1;
Johannes Doerfert7175bdf2015-09-20 14:56:54 +00001342
Tobias Grosserb45ae562016-11-26 07:37:46 +00001343 for (auto &SubLoop : *L) {
1344 LoopStats Stats = countBeneficialSubLoops(SubLoop, SE, MinProfitableTrips);
1345 NumLoops += Stats.NumLoops;
Tobias Grosser65ce9362017-02-17 08:08:54 +00001346 MaxLoopDepth = std::max(MaxLoopDepth, Stats.MaxDepth + 1);
Tobias Grosserb45ae562016-11-26 07:37:46 +00001347 }
Johannes Doerfert7175bdf2015-09-20 14:56:54 +00001348
Tobias Grosserb45ae562016-11-26 07:37:46 +00001349 return {NumLoops, MaxLoopDepth};
Johannes Doerfert7175bdf2015-09-20 14:56:54 +00001350}
1351
Tobias Grosserb45ae562016-11-26 07:37:46 +00001352ScopDetection::LoopStats
Tobias Grossercd01a362017-02-17 08:12:36 +00001353ScopDetection::countBeneficialLoops(Region *R, ScalarEvolution &SE,
1354 LoopInfo &LI, unsigned MinProfitableTrips) {
Johannes Doerfertf61df692015-10-04 14:56:08 +00001355 int LoopNum = 0;
Tobias Grosserb45ae562016-11-26 07:37:46 +00001356 int MaxLoopDepth = 0;
Tobias Grossered21a1f2015-08-27 16:55:18 +00001357
Tobias Grossercd01a362017-02-17 08:12:36 +00001358 auto L = LI.getLoopFor(R->getEntry());
Tobias Grosser93ab5582017-08-27 21:39:25 +00001359
1360 // If L is fully contained in R, move to first loop surrounding R. Otherwise,
1361 // L is either nullptr or already surrounding R.
1362 if (L && R->contains(L)) {
1363 L = R->outermostLoopInRegion(L);
1364 L = L->getParentLoop();
1365 }
Tobias Grossered21a1f2015-08-27 16:55:18 +00001366
Tobias Grosser050e0cb2015-08-31 12:08:11 +00001367 auto SubLoops =
Tobias Grossercd01a362017-02-17 08:12:36 +00001368 L ? L->getSubLoopsVector() : std::vector<Loop *>(LI.begin(), LI.end());
Tobias Grosser050e0cb2015-08-31 12:08:11 +00001369
1370 for (auto &SubLoop : SubLoops)
Tobias Grosserb45ae562016-11-26 07:37:46 +00001371 if (R->contains(SubLoop)) {
1372 LoopStats Stats =
Tobias Grossercd01a362017-02-17 08:12:36 +00001373 countBeneficialSubLoops(SubLoop, SE, MinProfitableTrips);
Tobias Grosserb45ae562016-11-26 07:37:46 +00001374 LoopNum += Stats.NumLoops;
1375 MaxLoopDepth = std::max(MaxLoopDepth, Stats.MaxDepth);
1376 }
Tobias Grosser050e0cb2015-08-31 12:08:11 +00001377
Tobias Grosserb45ae562016-11-26 07:37:46 +00001378 return {LoopNum, MaxLoopDepth};
Tobias Grossered21a1f2015-08-27 16:55:18 +00001379}
1380
Tobias Grosser75805372011-04-29 06:27:02 +00001381Region *ScopDetection::expandRegion(Region &R) {
Hongbin Zhenged986ab2012-04-07 15:14:28 +00001382 // Initial no valid region was found (greater than R)
Tobias Grosserd5d93ec2015-06-04 17:59:54 +00001383 std::unique_ptr<Region> LastValidRegion;
1384 auto ExpandedRegion = std::unique_ptr<Region>(R.getExpandedRegion());
Tobias Grosser75805372011-04-29 06:27:02 +00001385
1386 DEBUG(dbgs() << "\tExpanding " << R.getNameStr() << "\n");
1387
Hongbin Zhenged986ab2012-04-07 15:14:28 +00001388 while (ExpandedRegion) {
Siddharth Bhatc0f5f4d2017-12-05 00:06:09 +00001389 const auto &It = DetectionContextMap.insert(std::make_pair(
1390 getBBPairForRegion(ExpandedRegion.get()),
1391 DetectionContext(*ExpandedRegion, AA, false /*verifying*/)));
Johannes Doerfertc06b7d62015-10-07 20:46:06 +00001392 DetectionContext &Context = It.first->second;
Hongbin Zhenged986ab2012-04-07 15:14:28 +00001393 DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n");
Andreas Simbuergerb379edb2014-06-27 06:21:14 +00001394 // Only expand when we did not collect errors.
Tobias Grosser75805372011-04-29 06:27:02 +00001395
Johannes Doerfert717b8662015-09-08 21:44:27 +00001396 if (!Context.Log.hasErrors()) {
Hongbin Zhenged986ab2012-04-07 15:14:28 +00001397 // If the exit is valid check all blocks
1398 // - if true, a valid region was found => store it + keep expanding
1399 // - if false, .tbd. => stop (should this really end the loop?)
Johannes Doerferte46925f2015-10-01 10:59:14 +00001400 if (!allBlocksValid(Context) || Context.Log.hasErrors()) {
1401 removeCachedResults(*ExpandedRegion);
Michael Krusea6cc0d32016-08-08 22:39:32 +00001402 DetectionContextMap.erase(It.first);
Andreas Simbuergerb379edb2014-06-27 06:21:14 +00001403 break;
Johannes Doerferte46925f2015-10-01 10:59:14 +00001404 }
Andreas Simbuergerb379edb2014-06-27 06:21:14 +00001405
Tobias Grosserd7e58642013-04-10 06:55:45 +00001406 // Store this region, because it is the greatest valid (encountered so
1407 // far).
Michael Krusea6cc0d32016-08-08 22:39:32 +00001408 if (LastValidRegion) {
1409 removeCachedResults(*LastValidRegion);
1410 DetectionContextMap.erase(getBBPairForRegion(LastValidRegion.get()));
1411 }
Tobias Grosserd5d93ec2015-06-04 17:59:54 +00001412 LastValidRegion = std::move(ExpandedRegion);
Hongbin Zhenged986ab2012-04-07 15:14:28 +00001413
1414 // Create and test the next greater region (if any)
Tobias Grosserd5d93ec2015-06-04 17:59:54 +00001415 ExpandedRegion =
1416 std::unique_ptr<Region>(LastValidRegion->getExpandedRegion());
Hongbin Zhenged986ab2012-04-07 15:14:28 +00001417
1418 } else {
1419 // Create and test the next greater region (if any)
Johannes Doerfertc06b7d62015-10-07 20:46:06 +00001420 removeCachedResults(*ExpandedRegion);
Michael Krusea6cc0d32016-08-08 22:39:32 +00001421 DetectionContextMap.erase(It.first);
Tobias Grosserd5d93ec2015-06-04 17:59:54 +00001422 ExpandedRegion =
1423 std::unique_ptr<Region>(ExpandedRegion->getExpandedRegion());
Tobias Grosser75805372011-04-29 06:27:02 +00001424 }
Tobias Grosser75805372011-04-29 06:27:02 +00001425 }
1426
Tobias Grosser378a9f22013-11-16 19:34:11 +00001427 DEBUG({
1428 if (LastValidRegion)
1429 dbgs() << "\tto " << LastValidRegion->getNameStr() << "\n";
1430 else
1431 dbgs() << "\tExpanding " << R.getNameStr() << " failed\n";
1432 });
Tobias Grosser75805372011-04-29 06:27:02 +00001433
Tobias Grosserd5d93ec2015-06-04 17:59:54 +00001434 return LastValidRegion.release();
Tobias Grosser75805372011-04-29 06:27:02 +00001435}
Eugene Zelenkoa32707d2017-08-25 21:35:27 +00001436
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001437static bool regionWithoutLoops(Region &R, LoopInfo &LI) {
Tobias Grosser26108892014-04-02 20:18:19 +00001438 for (const BasicBlock *BB : R.blocks())
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001439 if (R.contains(LI.getLoopFor(BB)))
Sebastian Pop2c9ec2e2013-06-03 16:35:37 +00001440 return false;
1441
1442 return true;
1443}
Tobias Grosser75805372011-04-29 06:27:02 +00001444
Tobias Grosserb45ae562016-11-26 07:37:46 +00001445void ScopDetection::removeCachedResultsRecursively(const Region &R) {
David Blaikieb035f6d2014-04-15 18:45:27 +00001446 for (auto &SubRegion : R) {
Johannes Doerferte46925f2015-10-01 10:59:14 +00001447 if (ValidRegions.count(SubRegion.get())) {
1448 removeCachedResults(*SubRegion.get());
Johannes Doerferte46925f2015-10-01 10:59:14 +00001449 } else
Tobias Grosserb45ae562016-11-26 07:37:46 +00001450 removeCachedResultsRecursively(*SubRegion);
Tobias Grosser28a70c52014-01-29 19:05:30 +00001451 }
Tobias Grosser28a70c52014-01-29 19:05:30 +00001452}
1453
Johannes Doerferte46925f2015-10-01 10:59:14 +00001454void ScopDetection::removeCachedResults(const Region &R) {
1455 ValidRegions.remove(&R);
Johannes Doerferte46925f2015-10-01 10:59:14 +00001456}
1457
Tobias Grosser75805372011-04-29 06:27:02 +00001458void ScopDetection::findScops(Region &R) {
Johannes Doerfert6c7639b2016-05-12 18:50:01 +00001459 const auto &It = DetectionContextMap.insert(std::make_pair(
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001460 getBBPairForRegion(&R), DetectionContext(R, AA, false /*verifying*/)));
Johannes Doerfertc06b7d62015-10-07 20:46:06 +00001461 DetectionContext &Context = It.first->second;
Johannes Doerfert6a4d81c2015-03-08 15:11:50 +00001462
1463 bool RegionIsValid = false;
Michael Kruse0b566812016-02-29 16:54:18 +00001464 if (!PollyProcessUnprofitable && regionWithoutLoops(R, LI))
Johannes Doerfert6a4d81c2015-03-08 15:11:50 +00001465 invalid<ReportUnprofitable>(Context, /*Assert=*/true, &R);
Michael Kruse0b566812016-02-29 16:54:18 +00001466 else
Johannes Doerfert6a4d81c2015-03-08 15:11:50 +00001467 RegionIsValid = isValidRegion(Context);
1468
Johannes Doerfert3f1c2852015-02-19 18:11:50 +00001469 bool HasErrors = !RegionIsValid || Context.Log.size() > 0;
Andreas Simbuerger04472402014-05-24 09:25:10 +00001470
Johannes Doerferte46925f2015-10-01 10:59:14 +00001471 if (HasErrors) {
1472 removeCachedResults(R);
1473 } else {
Tobias Grosser75805372011-04-29 06:27:02 +00001474 ValidRegions.insert(&R);
1475 return;
1476 }
1477
David Blaikieb035f6d2014-04-15 18:45:27 +00001478 for (auto &SubRegion : R)
Tobias Grosser00dc3092014-03-02 12:02:46 +00001479 findScops(*SubRegion);
Tobias Grosser75805372011-04-29 06:27:02 +00001480
1481 // Try to expand regions.
1482 //
1483 // As the region tree normally only contains canonical regions, non canonical
1484 // regions that form a Scop are not found. Therefore, those non canonical
1485 // regions are checked by expanding the canonical ones.
1486
Tobias Grosser0d1eee32013-02-05 11:56:05 +00001487 std::vector<Region *> ToExpand;
Tobias Grosser75805372011-04-29 06:27:02 +00001488
David Blaikieb035f6d2014-04-15 18:45:27 +00001489 for (auto &SubRegion : R)
1490 ToExpand.push_back(SubRegion.get());
Tobias Grosser75805372011-04-29 06:27:02 +00001491
Tobias Grosser26108892014-04-02 20:18:19 +00001492 for (Region *CurrentRegion : ToExpand) {
Tobias Grosser75805372011-04-29 06:27:02 +00001493 // Skip invalid regions. Regions may become invalid, if they are element of
1494 // an already expanded region.
David Peixotto8da2b932014-10-22 20:39:07 +00001495 if (!ValidRegions.count(CurrentRegion))
Tobias Grosser75805372011-04-29 06:27:02 +00001496 continue;
1497
Johannes Doerfert6c7639b2016-05-12 18:50:01 +00001498 // Skip regions that had errors.
1499 bool HadErrors = lookupRejectionLog(CurrentRegion)->hasErrors();
1500 if (HadErrors)
1501 continue;
1502
Tobias Grosser75805372011-04-29 06:27:02 +00001503 Region *ExpandedR = expandRegion(*CurrentRegion);
1504
1505 if (!ExpandedR)
1506 continue;
1507
1508 R.addSubRegion(ExpandedR, true);
1509 ValidRegions.insert(ExpandedR);
Johannes Doerferte46925f2015-10-01 10:59:14 +00001510 removeCachedResults(*CurrentRegion);
Tobias Grosserb45ae562016-11-26 07:37:46 +00001511 removeCachedResultsRecursively(*ExpandedR);
Tobias Grosser75805372011-04-29 06:27:02 +00001512 }
1513}
1514
1515bool ScopDetection::allBlocksValid(DetectionContext &Context) const {
Johannes Doerfertfb79a962015-02-23 14:18:28 +00001516 Region &CurRegion = Context.CurRegion;
Tobias Grosser75805372011-04-29 06:27:02 +00001517
Johannes Doerfertfb79a962015-02-23 14:18:28 +00001518 for (const BasicBlock *BB : CurRegion.blocks()) {
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001519 Loop *L = LI.getLoopFor(BB);
Tobias Grossera3aa4232017-07-15 22:42:17 +00001520 if (L && L->getHeader() == BB) {
1521 if (CurRegion.contains(L)) {
1522 if (!isValidLoop(L, Context) && !KeepGoing)
1523 return false;
1524 } else {
1525 SmallVector<BasicBlock *, 1> Latches;
1526 L->getLoopLatches(Latches);
1527 for (BasicBlock *Latch : Latches)
1528 if (CurRegion.contains(Latch))
1529 return invalid<ReportLoopOnlySomeLatches>(Context, /*Assert=*/true,
1530 L);
1531 }
1532 }
Sebastian Popb88ea5e2013-06-11 22:20:32 +00001533 }
1534
Johannes Doerfert90db75e2015-09-10 17:51:27 +00001535 for (BasicBlock *BB : CurRegion.blocks()) {
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001536 bool IsErrorBlock = isErrorBlock(*BB, CurRegion, LI, DT);
Tobias Grosserb76cd3c2015-11-11 08:42:20 +00001537
1538 // Also check exception blocks (and possibly register them as non-affine
1539 // regions). Even though exception blocks are not modeled, we use them
1540 // to forward-propagate domain constraints during ScopInfo construction.
1541 if (!isValidCFG(*BB, false, IsErrorBlock, Context) && !KeepGoing)
1542 return false;
1543
1544 if (IsErrorBlock)
Johannes Doerfert90db75e2015-09-10 17:51:27 +00001545 continue;
1546
Tobias Grosser1d191902014-03-03 13:13:55 +00001547 for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ++I)
Andreas Simbuerger04472402014-05-24 09:25:10 +00001548 if (!isValidInstruction(*I, Context) && !KeepGoing)
Sebastian Pop8ca899c2013-06-14 20:20:43 +00001549 return false;
Johannes Doerfert90db75e2015-09-10 17:51:27 +00001550 }
Tobias Grosser75805372011-04-29 06:27:02 +00001551
Sebastian Pope8863b82014-05-12 19:02:02 +00001552 if (!hasAffineMemoryAccesses(Context))
Sebastian Pop46e1ecd2014-05-09 22:45:15 +00001553 return false;
1554
Tobias Grosser75805372011-04-29 06:27:02 +00001555 return true;
1556}
1557
Tobias Grosserc1a269b2015-12-21 21:00:43 +00001558bool ScopDetection::hasSufficientCompute(DetectionContext &Context,
1559 int NumLoops) const {
1560 int InstCount = 0;
1561
Tobias Grosserb316dc12016-09-08 14:08:05 +00001562 if (NumLoops == 0)
1563 return false;
1564
Tobias Grosserc1a269b2015-12-21 21:00:43 +00001565 for (auto *BB : Context.CurRegion.blocks())
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001566 if (Context.CurRegion.contains(LI.getLoopFor(BB)))
Tobias Grosserc6424ae2015-12-22 17:38:59 +00001567 InstCount += BB->size();
Tobias Grosserc1a269b2015-12-21 21:00:43 +00001568
1569 InstCount = InstCount / NumLoops;
1570
1571 return InstCount >= ProfitabilityMinPerLoopInstructions;
1572}
1573
Johannes Doerfertbf9473b2016-05-10 14:42:30 +00001574bool ScopDetection::hasPossiblyDistributableLoop(
1575 DetectionContext &Context) const {
1576 for (auto *BB : Context.CurRegion.blocks()) {
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001577 auto *L = LI.getLoopFor(BB);
Johannes Doerfertbf9473b2016-05-10 14:42:30 +00001578 if (!Context.CurRegion.contains(L))
1579 continue;
1580 if (Context.BoxedLoopsSet.count(L))
1581 continue;
1582 unsigned StmtsWithStoresInLoops = 0;
1583 for (auto *LBB : L->blocks()) {
1584 bool MemStore = false;
1585 for (auto &I : *LBB)
1586 MemStore |= isa<StoreInst>(&I);
1587 StmtsWithStoresInLoops += MemStore;
1588 }
1589 return (StmtsWithStoresInLoops > 1);
1590 }
1591 return false;
1592}
1593
Tobias Grosser97fc5bb2015-12-21 12:14:48 +00001594bool ScopDetection::isProfitableRegion(DetectionContext &Context) const {
1595 Region &CurRegion = Context.CurRegion;
1596
1597 if (PollyProcessUnprofitable)
1598 return true;
1599
1600 // We can probably not do a lot on scops that only write or only read
1601 // data.
1602 if (!Context.hasStores || !Context.hasLoads)
1603 return invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
1604
Tobias Grossercd01a362017-02-17 08:12:36 +00001605 int NumLoops =
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001606 countBeneficialLoops(&CurRegion, SE, LI, MIN_LOOP_TRIP_COUNT).NumLoops;
Tobias Grosser97fc5bb2015-12-21 12:14:48 +00001607 int NumAffineLoops = NumLoops - Context.BoxedLoopsSet.size();
Tobias Grosser97fc5bb2015-12-21 12:14:48 +00001608
Tobias Grosserc1a269b2015-12-21 21:00:43 +00001609 // Scops with at least two loops may allow either loop fusion or tiling and
1610 // are consequently interesting to look at.
1611 if (NumAffineLoops >= 2)
1612 return true;
1613
Michael Krusea6d48f52017-06-08 12:06:15 +00001614 // A loop with multiple non-trivial blocks might be amendable to distribution.
Johannes Doerfertbf9473b2016-05-10 14:42:30 +00001615 if (NumAffineLoops == 1 && hasPossiblyDistributableLoop(Context))
1616 return true;
1617
Tobias Grosserc1a269b2015-12-21 21:00:43 +00001618 // Scops that contain a loop with a non-trivial amount of computation per
1619 // loop-iteration are interesting as we may be able to parallelize such
1620 // loops. Individual loops that have only a small amount of computation
1621 // per-iteration are performance-wise very fragile as any change to the
1622 // loop induction variables may affect performance. To not cause spurious
1623 // performance regressions, we do not consider such loops.
1624 if (NumAffineLoops == 1 && hasSufficientCompute(Context, NumLoops))
1625 return true;
1626
1627 return invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
Tobias Grosser97fc5bb2015-12-21 12:14:48 +00001628}
1629
Tobias Grosser75805372011-04-29 06:27:02 +00001630bool ScopDetection::isValidRegion(DetectionContext &Context) const {
Johannes Doerfertfb79a962015-02-23 14:18:28 +00001631 Region &CurRegion = Context.CurRegion;
Tobias Grosser75805372011-04-29 06:27:02 +00001632
Johannes Doerfertfb79a962015-02-23 14:18:28 +00001633 DEBUG(dbgs() << "Checking region: " << CurRegion.getNameStr() << "\n\t");
Tobias Grosser75805372011-04-29 06:27:02 +00001634
Siddharth Bhatb46847c2017-08-17 21:57:23 +00001635 if (!PollyAllowFullFunction && CurRegion.isTopLevelRegion()) {
Tobias Grosserf084edd2014-10-22 23:00:03 +00001636 DEBUG(dbgs() << "Top level region is invalid\n");
Tobias Grosser75805372011-04-29 06:27:02 +00001637 return false;
1638 }
1639
Tobias Grosser134a5722017-03-07 15:50:43 +00001640 DebugLoc DbgLoc;
Philip Pfaffe1a0128f2017-05-24 18:39:39 +00001641 if (CurRegion.getExit() &&
1642 isa<UnreachableInst>(CurRegion.getExit()->getTerminator())) {
Tobias Grosser134a5722017-03-07 15:50:43 +00001643 DEBUG(dbgs() << "Unreachable in exit\n");
1644 return invalid<ReportUnreachableInExit>(Context, /*Assert=*/true,
1645 CurRegion.getExit(), DbgLoc);
1646 }
1647
Johannes Doerfertfb79a962015-02-23 14:18:28 +00001648 if (!CurRegion.getEntry()->getName().count(OnlyRegion)) {
Tobias Grosser4449e522014-01-27 14:24:53 +00001649 DEBUG({
1650 dbgs() << "Region entry does not match -polly-region-only";
1651 dbgs() << "\n";
1652 });
1653 return false;
1654 }
1655
Tobias Grosserd654c252012-04-10 18:12:19 +00001656 // SCoP cannot contain the entry block of the function, because we need
Tobias Grosser75805372011-04-29 06:27:02 +00001657 // to insert alloca instruction there when translate scalar to array.
Siddharth Bhatb46847c2017-08-17 21:57:23 +00001658 if (!PollyAllowFullFunction &&
Tobias Grosserd8945ba2017-05-19 12:13:02 +00001659 CurRegion.getEntry() ==
1660 &(CurRegion.getEntry()->getParent()->getEntryBlock()))
Johannes Doerfertfb79a962015-02-23 14:18:28 +00001661 return invalid<ReportEntry>(Context, /*Assert=*/true, CurRegion.getEntry());
Tobias Grosser75805372011-04-29 06:27:02 +00001662
Hongbin Zheng94868e62012-04-07 12:29:17 +00001663 if (!allBlocksValid(Context))
Tobias Grosser75805372011-04-29 06:27:02 +00001664 return false;
1665
Tobias Grosser1c3a6d72016-01-22 09:44:37 +00001666 if (!isReducibleRegion(CurRegion, DbgLoc))
1667 return invalid<ReportIrreducibleRegion>(Context, /*Assert=*/true,
1668 &CurRegion, DbgLoc);
1669
Tobias Grosser75805372011-04-29 06:27:02 +00001670 DEBUG(dbgs() << "OK\n");
1671 return true;
1672}
1673
Tobias Grosser629109b2016-08-03 12:00:07 +00001674void ScopDetection::markFunctionAsInvalid(Function *F) {
Johannes Doerfert43e1ead2014-07-15 21:06:48 +00001675 F->addFnAttr(PollySkipFnAttr);
1676}
1677
Eugene Zelenkoa32707d2017-08-25 21:35:27 +00001678bool ScopDetection::isValidFunction(Function &F) {
Johannes Doerfert43e1ead2014-07-15 21:06:48 +00001679 return !F.hasFnAttribute(PollySkipFnAttr);
Tobias Grosser75805372011-04-29 06:27:02 +00001680}
1681
Eugene Zelenkoa32707d2017-08-25 21:35:27 +00001682void ScopDetection::printLocations(Function &F) {
Tobias Grosser26108892014-04-02 20:18:19 +00001683 for (const Region *R : *this) {
Tobias Grosser531891e2012-11-01 16:45:20 +00001684 unsigned LineEntry, LineExit;
1685 std::string FileName;
1686
Tobias Grosser00dc3092014-03-02 12:02:46 +00001687 getDebugLocation(R, LineEntry, LineExit, FileName);
Tobias Grosser8519f892013-12-18 10:49:53 +00001688 DiagnosticScopFound Diagnostic(F, FileName, LineEntry, LineExit);
1689 F.getContext().diagnose(Diagnostic);
Tobias Grosser531891e2012-11-01 16:45:20 +00001690 }
1691}
1692
Johannes Doerfert6c7639b2016-05-12 18:50:01 +00001693void ScopDetection::emitMissedRemarks(const Function &F) {
1694 for (auto &DIt : DetectionContextMap) {
1695 auto &DC = DIt.getSecond();
1696 if (DC.Log.hasErrors())
Eli Friedmane737fc12017-07-17 23:58:33 +00001697 emitRejectionRemarks(DIt.getFirst(), DC.Log, ORE);
Andreas Simbuerger5569bf32014-06-26 10:06:40 +00001698 }
1699}
1700
Tobias Grosser1c3a6d72016-01-22 09:44:37 +00001701bool ScopDetection::isReducibleRegion(Region &R, DebugLoc &DbgLoc) const {
Tobias Grosserc80d6972016-09-02 06:33:33 +00001702 /// Enum for coloring BBs in Region.
Tobias Grosseref6ae702016-06-11 09:00:37 +00001703 ///
1704 /// WHITE - Unvisited BB in DFS walk.
1705 /// GREY - BBs which are currently on the DFS stack for processing.
1706 /// BLACK - Visited and completely processed BB.
1707 enum Color { WHITE, GREY, BLACK };
1708
Tobias Grosser1c3a6d72016-01-22 09:44:37 +00001709 BasicBlock *REntry = R.getEntry();
1710 BasicBlock *RExit = R.getExit();
1711 // Map to match the color of a BasicBlock during the DFS walk.
1712 DenseMap<const BasicBlock *, Color> BBColorMap;
1713 // Stack keeping track of current BB and index of next child to be processed.
1714 std::stack<std::pair<BasicBlock *, unsigned>> DFSStack;
1715
1716 unsigned AdjacentBlockIndex = 0;
1717 BasicBlock *CurrBB, *SuccBB;
1718 CurrBB = REntry;
1719
1720 // Initialize the map for all BB with WHITE color.
1721 for (auto *BB : R.blocks())
Johannes Doerfert469db6a2016-05-19 12:36:43 +00001722 BBColorMap[BB] = WHITE;
Tobias Grosser1c3a6d72016-01-22 09:44:37 +00001723
1724 // Process the entry block of the Region.
Johannes Doerfert469db6a2016-05-19 12:36:43 +00001725 BBColorMap[CurrBB] = GREY;
Tobias Grosser1c3a6d72016-01-22 09:44:37 +00001726 DFSStack.push(std::make_pair(CurrBB, 0));
1727
1728 while (!DFSStack.empty()) {
1729 // Get next BB on stack to be processed.
1730 CurrBB = DFSStack.top().first;
1731 AdjacentBlockIndex = DFSStack.top().second;
1732 DFSStack.pop();
1733
1734 // Loop to iterate over the successors of current BB.
1735 const TerminatorInst *TInst = CurrBB->getTerminator();
1736 unsigned NSucc = TInst->getNumSuccessors();
1737 for (unsigned I = AdjacentBlockIndex; I < NSucc;
1738 ++I, ++AdjacentBlockIndex) {
1739 SuccBB = TInst->getSuccessor(I);
1740
1741 // Checks for region exit block and self-loops in BB.
1742 if (SuccBB == RExit || SuccBB == CurrBB)
1743 continue;
1744
1745 // WHITE indicates an unvisited BB in DFS walk.
Johannes Doerfert469db6a2016-05-19 12:36:43 +00001746 if (BBColorMap[SuccBB] == WHITE) {
Tobias Grosser1c3a6d72016-01-22 09:44:37 +00001747 // Push the current BB and the index of the next child to be visited.
1748 DFSStack.push(std::make_pair(CurrBB, I + 1));
1749 // Push the next BB to be processed.
1750 DFSStack.push(std::make_pair(SuccBB, 0));
1751 // First time the BB is being processed.
Johannes Doerfert469db6a2016-05-19 12:36:43 +00001752 BBColorMap[SuccBB] = GREY;
Tobias Grosser1c3a6d72016-01-22 09:44:37 +00001753 break;
Johannes Doerfert469db6a2016-05-19 12:36:43 +00001754 } else if (BBColorMap[SuccBB] == GREY) {
Tobias Grosser1c3a6d72016-01-22 09:44:37 +00001755 // GREY indicates a loop in the control flow.
1756 // If the destination dominates the source, it is a natural loop
1757 // else, an irreducible control flow in the region is detected.
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001758 if (!DT.dominates(SuccBB, CurrBB)) {
Tobias Grosser1c3a6d72016-01-22 09:44:37 +00001759 // Get debug info of instruction which causes irregular control flow.
1760 DbgLoc = TInst->getDebugLoc();
1761 return false;
1762 }
1763 }
1764 }
1765
1766 // If all children of current BB have been processed,
1767 // then mark that BB as fully processed.
1768 if (AdjacentBlockIndex == NSucc)
Johannes Doerfert469db6a2016-05-19 12:36:43 +00001769 BBColorMap[CurrBB] = BLACK;
Tobias Grosser1c3a6d72016-01-22 09:44:37 +00001770 }
1771
1772 return true;
1773}
1774
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001775static void updateLoopCountStatistic(ScopDetection::LoopStats Stats,
1776 bool OnlyProfitable) {
Tobias Grosserb45ae562016-11-26 07:37:46 +00001777 if (!OnlyProfitable) {
1778 NumLoopsInScop += Stats.NumLoops;
Tobias Grosser9fe37df2017-02-12 10:52:57 +00001779 MaxNumLoopsInScop =
1780 std::max(MaxNumLoopsInScop.getValue(), (unsigned)Stats.NumLoops);
Tobias Grosserfcc3ad52018-04-18 20:03:36 +00001781 if (Stats.MaxDepth == 0)
1782 NumScopsDepthZero++;
1783 else if (Stats.MaxDepth == 1)
Tobias Grosserb45ae562016-11-26 07:37:46 +00001784 NumScopsDepthOne++;
1785 else if (Stats.MaxDepth == 2)
1786 NumScopsDepthTwo++;
1787 else if (Stats.MaxDepth == 3)
1788 NumScopsDepthThree++;
1789 else if (Stats.MaxDepth == 4)
1790 NumScopsDepthFour++;
1791 else if (Stats.MaxDepth == 5)
1792 NumScopsDepthFive++;
1793 else
1794 NumScopsDepthLarger++;
1795 } else {
1796 NumLoopsInProfScop += Stats.NumLoops;
Tobias Grosser9fe37df2017-02-12 10:52:57 +00001797 MaxNumLoopsInProfScop =
1798 std::max(MaxNumLoopsInProfScop.getValue(), (unsigned)Stats.NumLoops);
Tobias Grosserfcc3ad52018-04-18 20:03:36 +00001799 if (Stats.MaxDepth == 0)
1800 NumProfScopsDepthZero++;
1801 else if (Stats.MaxDepth == 1)
Tobias Grosserb45ae562016-11-26 07:37:46 +00001802 NumProfScopsDepthOne++;
1803 else if (Stats.MaxDepth == 2)
1804 NumProfScopsDepthTwo++;
1805 else if (Stats.MaxDepth == 3)
1806 NumProfScopsDepthThree++;
1807 else if (Stats.MaxDepth == 4)
1808 NumProfScopsDepthFour++;
1809 else if (Stats.MaxDepth == 5)
1810 NumProfScopsDepthFive++;
1811 else
1812 NumProfScopsDepthLarger++;
1813 }
1814}
1815
Johannes Doerfert1dafea42016-05-23 09:07:08 +00001816ScopDetection::DetectionContext *
Johannes Doerfertc06b7d62015-10-07 20:46:06 +00001817ScopDetection::getDetectionContext(const Region *R) const {
Johannes Doerfert6c7639b2016-05-12 18:50:01 +00001818 auto DCMIt = DetectionContextMap.find(getBBPairForRegion(R));
Johannes Doerfertc06b7d62015-10-07 20:46:06 +00001819 if (DCMIt == DetectionContextMap.end())
1820 return nullptr;
1821 return &DCMIt->second;
Johannes Doerfertba65c162015-02-24 11:45:21 +00001822}
1823
Johannes Doerfert6c7639b2016-05-12 18:50:01 +00001824const RejectLog *ScopDetection::lookupRejectionLog(const Region *R) const {
1825 const DetectionContext *DC = getDetectionContext(R);
1826 return DC ? &DC->Log : nullptr;
1827}
1828
Eugene Zelenkoa32707d2017-08-25 21:35:27 +00001829void ScopDetection::verifyRegion(const Region &R) const {
Tobias Grosser75805372011-04-29 06:27:02 +00001830 assert(isMaxRegionInScop(R) && "Expect R is a valid region.");
Johannes Doerfertf3e98f42015-04-12 22:52:20 +00001831
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001832 DetectionContext Context(const_cast<Region &>(R), AA, true /*verifying*/);
Tobias Grosser75805372011-04-29 06:27:02 +00001833 isValidRegion(Context);
1834}
1835
Eugene Zelenkoa32707d2017-08-25 21:35:27 +00001836void ScopDetection::verifyAnalysis() const {
Tobias Grossera1689932014-02-18 18:49:49 +00001837 if (!VerifyScops)
1838 return;
1839
Tobias Grosser26108892014-04-02 20:18:19 +00001840 for (const Region *R : ValidRegions)
Tobias Grosser00dc3092014-03-02 12:02:46 +00001841 verifyRegion(*R);
Tobias Grosser75805372011-04-29 06:27:02 +00001842}
1843
Eugene Zelenkoa32707d2017-08-25 21:35:27 +00001844bool ScopDetectionWrapperPass::runOnFunction(Function &F) {
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001845 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1846 auto &RI = getAnalysis<RegionInfoPass>().getRegionInfo();
1847 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
1848 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1849 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
Eli Friedmane737fc12017-07-17 23:58:33 +00001850 auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
1851 Result.reset(new ScopDetection(F, DT, SE, LI, RI, AA, ORE));
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001852 return false;
1853}
1854
1855void ScopDetectionWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
Chandler Carruthf5579872015-01-17 14:16:56 +00001856 AU.addRequired<LoopInfoWrapperPass>();
Michael Kruse6a19d592016-10-17 13:29:20 +00001857 AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
Johannes Doerfert08d90a32015-10-07 20:32:43 +00001858 AU.addRequired<DominatorTreeWrapperPass>();
Eli Friedmane737fc12017-07-17 23:58:33 +00001859 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
Tobias Grosser75805372011-04-29 06:27:02 +00001860 // We also need AA and RegionInfo when we are verifying analysis.
Chandler Carruth66ef16b2015-09-09 22:13:56 +00001861 AU.addRequiredTransitive<AAResultsWrapperPass>();
Matt Arsenault8ca36812014-07-19 18:40:17 +00001862 AU.addRequiredTransitive<RegionInfoPass>();
Tobias Grosser75805372011-04-29 06:27:02 +00001863 AU.setPreservesAll();
1864}
1865
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001866void ScopDetectionWrapperPass::print(raw_ostream &OS, const Module *) const {
1867 for (const Region *R : Result->ValidRegions)
Tobias Grosser00dc3092014-03-02 12:02:46 +00001868 OS << "Valid Region for Scop: " << R->getNameStr() << '\n';
Tobias Grosser75805372011-04-29 06:27:02 +00001869
1870 OS << "\n";
1871}
1872
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001873ScopDetectionWrapperPass::ScopDetectionWrapperPass() : FunctionPass(ID) {
1874 // Disable runtime alias checks if we ignore aliasing all together.
1875 if (IgnoreAliasing)
1876 PollyUseRuntimeAliasChecks = false;
Tobias Grosser75805372011-04-29 06:27:02 +00001877}
Eugene Zelenkoa32707d2017-08-25 21:35:27 +00001878
Philip Pfaffef5a43942017-08-02 11:08:01 +00001879ScopAnalysis::ScopAnalysis() {
1880 // Disable runtime alias checks if we ignore aliasing all together.
1881 if (IgnoreAliasing)
1882 PollyUseRuntimeAliasChecks = false;
1883}
Tobias Grosser75805372011-04-29 06:27:02 +00001884
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001885void ScopDetectionWrapperPass::releaseMemory() { Result.reset(); }
Tobias Grosser75805372011-04-29 06:27:02 +00001886
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001887char ScopDetectionWrapperPass::ID;
Tobias Grosser4d96c8d2013-03-23 01:05:07 +00001888
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001889AnalysisKey ScopAnalysis::Key;
1890
1891ScopDetection ScopAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
1892 auto &LI = FAM.getResult<LoopAnalysis>(F);
1893 auto &RI = FAM.getResult<RegionInfoAnalysis>(F);
1894 auto &AA = FAM.getResult<AAManager>(F);
1895 auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
1896 auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
Eli Friedmane737fc12017-07-17 23:58:33 +00001897 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
1898 return {F, DT, SE, LI, RI, AA, ORE};
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001899}
1900
1901PreservedAnalyses ScopAnalysisPrinterPass::run(Function &F,
1902 FunctionAnalysisManager &FAM) {
Eugene Zelenkoa32707d2017-08-25 21:35:27 +00001903 OS << "Detected Scops in Function " << F.getName() << "\n";
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001904 auto &SD = FAM.getResult<ScopAnalysis>(F);
1905 for (const Region *R : SD.ValidRegions)
Eugene Zelenkoa32707d2017-08-25 21:35:27 +00001906 OS << "Valid Region for Scop: " << R->getNameStr() << '\n';
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001907
Eugene Zelenkoa32707d2017-08-25 21:35:27 +00001908 OS << "\n";
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001909 return PreservedAnalyses::all();
1910}
1911
1912Pass *polly::createScopDetectionWrapperPassPass() {
1913 return new ScopDetectionWrapperPass();
1914}
1915
1916INITIALIZE_PASS_BEGIN(ScopDetectionWrapperPass, "polly-detect",
Tobias Grosser73600b82011-10-08 00:30:40 +00001917 "Polly - Detect static control parts (SCoPs)", false,
Tobias Grosser4d96c8d2013-03-23 01:05:07 +00001918 false);
Chandler Carruth66ef16b2015-09-09 22:13:56 +00001919INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
Chandler Carruthf5579872015-01-17 14:16:56 +00001920INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
Matt Arsenault8ca36812014-07-19 18:40:17 +00001921INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
Johannes Doerfert08d90a32015-10-07 20:32:43 +00001922INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
Tobias Grosserc5bcf242015-08-17 10:57:08 +00001923INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
Eli Friedmane737fc12017-07-17 23:58:33 +00001924INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass);
Philip Pfaffe5cc87e32017-05-12 14:37:29 +00001925INITIALIZE_PASS_END(ScopDetectionWrapperPass, "polly-detect",
Tobias Grosser73600b82011-10-08 00:30:40 +00001926 "Polly - Detect static control parts (SCoPs)", false, false)