Bug Summary

File:tools/polly/lib/Analysis/ScopInfo.cpp
Warning:line 2565, column 5
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ScopInfo.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-8/lib/clang/8.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/polly/lib -I /build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/polly/include -I /build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/External/pet/include -I /build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-8~svn345461/tools/polly/include -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn345461/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/8.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -Wno-long-long -Wno-unused-parameter -Wwrite-strings -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/tools/polly/lib -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fno-rtti -fobjc-runtime=gcc -fno-common -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-10-27-211344-32123-1 -x c++ /build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp -faddrsig
1//===- ScopInfo.cpp -------------------------------------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Create a polyhedral description for a static control flow region.
11//
12// The pass creates a polyhedral description of the Scops detected by the Scop
13// detection derived from their LLVM-IR code.
14//
15// This representation is shared among several tools in the polyhedral
16// community, which are e.g. Cloog, Pluto, Loopo, Graphite.
17//
18//===----------------------------------------------------------------------===//
19
20#include "polly/ScopInfo.h"
21#include "polly/LinkAllPasses.h"
22#include "polly/Options.h"
23#include "polly/ScopBuilder.h"
24#include "polly/ScopDetection.h"
25#include "polly/Support/GICHelper.h"
26#include "polly/Support/ISLOStream.h"
27#include "polly/Support/ISLTools.h"
28#include "polly/Support/SCEVAffinator.h"
29#include "polly/Support/SCEVValidator.h"
30#include "polly/Support/ScopHelper.h"
31#include "llvm/ADT/APInt.h"
32#include "llvm/ADT/ArrayRef.h"
33#include "llvm/ADT/DenseMap.h"
34#include "llvm/ADT/DenseSet.h"
35#include "llvm/ADT/PostOrderIterator.h"
36#include "llvm/ADT/STLExtras.h"
37#include "llvm/ADT/SetVector.h"
38#include "llvm/ADT/SmallPtrSet.h"
39#include "llvm/ADT/SmallSet.h"
40#include "llvm/ADT/SmallVector.h"
41#include "llvm/ADT/Statistic.h"
42#include "llvm/ADT/StringExtras.h"
43#include "llvm/ADT/StringMap.h"
44#include "llvm/Analysis/AliasAnalysis.h"
45#include "llvm/Analysis/AliasSetTracker.h"
46#include "llvm/Analysis/AssumptionCache.h"
47#include "llvm/Analysis/Loads.h"
48#include "llvm/Analysis/LoopInfo.h"
49#include "llvm/Analysis/OptimizationRemarkEmitter.h"
50#include "llvm/Analysis/RegionInfo.h"
51#include "llvm/Analysis/RegionIterator.h"
52#include "llvm/Analysis/ScalarEvolution.h"
53#include "llvm/Analysis/ScalarEvolutionExpressions.h"
54#include "llvm/IR/Argument.h"
55#include "llvm/IR/BasicBlock.h"
56#include "llvm/IR/CFG.h"
57#include "llvm/IR/ConstantRange.h"
58#include "llvm/IR/Constants.h"
59#include "llvm/IR/DataLayout.h"
60#include "llvm/IR/DebugLoc.h"
61#include "llvm/IR/DerivedTypes.h"
62#include "llvm/IR/DiagnosticInfo.h"
63#include "llvm/IR/Dominators.h"
64#include "llvm/IR/Function.h"
65#include "llvm/IR/InstrTypes.h"
66#include "llvm/IR/Instruction.h"
67#include "llvm/IR/Instructions.h"
68#include "llvm/IR/IntrinsicInst.h"
69#include "llvm/IR/Module.h"
70#include "llvm/IR/PassManager.h"
71#include "llvm/IR/Type.h"
72#include "llvm/IR/Use.h"
73#include "llvm/IR/User.h"
74#include "llvm/IR/Value.h"
75#include "llvm/Pass.h"
76#include "llvm/Support/Casting.h"
77#include "llvm/Support/CommandLine.h"
78#include "llvm/Support/Compiler.h"
79#include "llvm/Support/Debug.h"
80#include "llvm/Support/ErrorHandling.h"
81#include "llvm/Support/MathExtras.h"
82#include "llvm/Support/raw_ostream.h"
83#include "isl/aff.h"
84#include "isl/constraint.h"
85#include "isl/local_space.h"
86#include "isl/map.h"
87#include "isl/options.h"
88#include "isl/printer.h"
89#include "isl/schedule.h"
90#include "isl/schedule_node.h"
91#include "isl/set.h"
92#include "isl/union_map.h"
93#include "isl/union_set.h"
94#include "isl/val.h"
95#include <algorithm>
96#include <cassert>
97#include <cstdlib>
98#include <cstring>
99#include <deque>
100#include <iterator>
101#include <memory>
102#include <string>
103#include <tuple>
104#include <utility>
105#include <vector>
106
107using namespace llvm;
108using namespace polly;
109
110#define DEBUG_TYPE"polly-scops" "polly-scops"
111
112STATISTIC(AssumptionsAliasing, "Number of aliasing assumptions taken.")static llvm::Statistic AssumptionsAliasing = {"polly-scops", "AssumptionsAliasing"
, "Number of aliasing assumptions taken.", {0}, {false}}
;
113STATISTIC(AssumptionsInbounds, "Number of inbounds assumptions taken.")static llvm::Statistic AssumptionsInbounds = {"polly-scops", "AssumptionsInbounds"
, "Number of inbounds assumptions taken.", {0}, {false}}
;
114STATISTIC(AssumptionsWrapping, "Number of wrapping assumptions taken.")static llvm::Statistic AssumptionsWrapping = {"polly-scops", "AssumptionsWrapping"
, "Number of wrapping assumptions taken.", {0}, {false}}
;
115STATISTIC(AssumptionsUnsigned, "Number of unsigned assumptions taken.")static llvm::Statistic AssumptionsUnsigned = {"polly-scops", "AssumptionsUnsigned"
, "Number of unsigned assumptions taken.", {0}, {false}}
;
116STATISTIC(AssumptionsComplexity, "Number of too complex SCoPs.")static llvm::Statistic AssumptionsComplexity = {"polly-scops"
, "AssumptionsComplexity", "Number of too complex SCoPs.", {0
}, {false}}
;
117STATISTIC(AssumptionsUnprofitable, "Number of unprofitable SCoPs.")static llvm::Statistic AssumptionsUnprofitable = {"polly-scops"
, "AssumptionsUnprofitable", "Number of unprofitable SCoPs.",
{0}, {false}}
;
118STATISTIC(AssumptionsErrorBlock, "Number of error block assumptions taken.")static llvm::Statistic AssumptionsErrorBlock = {"polly-scops"
, "AssumptionsErrorBlock", "Number of error block assumptions taken."
, {0}, {false}}
;
119STATISTIC(AssumptionsInfiniteLoop, "Number of bounded loop assumptions taken.")static llvm::Statistic AssumptionsInfiniteLoop = {"polly-scops"
, "AssumptionsInfiniteLoop", "Number of bounded loop assumptions taken."
, {0}, {false}}
;
120STATISTIC(AssumptionsInvariantLoad,static llvm::Statistic AssumptionsInvariantLoad = {"polly-scops"
, "AssumptionsInvariantLoad", "Number of invariant loads assumptions taken."
, {0}, {false}}
121 "Number of invariant loads assumptions taken.")static llvm::Statistic AssumptionsInvariantLoad = {"polly-scops"
, "AssumptionsInvariantLoad", "Number of invariant loads assumptions taken."
, {0}, {false}}
;
122STATISTIC(AssumptionsDelinearization,static llvm::Statistic AssumptionsDelinearization = {"polly-scops"
, "AssumptionsDelinearization", "Number of delinearization assumptions taken."
, {0}, {false}}
123 "Number of delinearization assumptions taken.")static llvm::Statistic AssumptionsDelinearization = {"polly-scops"
, "AssumptionsDelinearization", "Number of delinearization assumptions taken."
, {0}, {false}}
;
124
125STATISTIC(NumScops, "Number of feasible SCoPs after ScopInfo")static llvm::Statistic NumScops = {"polly-scops", "NumScops",
"Number of feasible SCoPs after ScopInfo", {0}, {false}}
;
126STATISTIC(NumLoopsInScop, "Number of loops in scops")static llvm::Statistic NumLoopsInScop = {"polly-scops", "NumLoopsInScop"
, "Number of loops in scops", {0}, {false}}
;
127STATISTIC(NumBoxedLoops, "Number of boxed loops in SCoPs after ScopInfo")static llvm::Statistic NumBoxedLoops = {"polly-scops", "NumBoxedLoops"
, "Number of boxed loops in SCoPs after ScopInfo", {0}, {false
}}
;
128STATISTIC(NumAffineLoops, "Number of affine loops in SCoPs after ScopInfo")static llvm::Statistic NumAffineLoops = {"polly-scops", "NumAffineLoops"
, "Number of affine loops in SCoPs after ScopInfo", {0}, {false
}}
;
129
130STATISTIC(NumScopsDepthZero, "Number of scops with maximal loop depth 0")static llvm::Statistic NumScopsDepthZero = {"polly-scops", "NumScopsDepthZero"
, "Number of scops with maximal loop depth 0", {0}, {false}}
;
131STATISTIC(NumScopsDepthOne, "Number of scops with maximal loop depth 1")static llvm::Statistic NumScopsDepthOne = {"polly-scops", "NumScopsDepthOne"
, "Number of scops with maximal loop depth 1", {0}, {false}}
;
132STATISTIC(NumScopsDepthTwo, "Number of scops with maximal loop depth 2")static llvm::Statistic NumScopsDepthTwo = {"polly-scops", "NumScopsDepthTwo"
, "Number of scops with maximal loop depth 2", {0}, {false}}
;
133STATISTIC(NumScopsDepthThree, "Number of scops with maximal loop depth 3")static llvm::Statistic NumScopsDepthThree = {"polly-scops", "NumScopsDepthThree"
, "Number of scops with maximal loop depth 3", {0}, {false}}
;
134STATISTIC(NumScopsDepthFour, "Number of scops with maximal loop depth 4")static llvm::Statistic NumScopsDepthFour = {"polly-scops", "NumScopsDepthFour"
, "Number of scops with maximal loop depth 4", {0}, {false}}
;
135STATISTIC(NumScopsDepthFive, "Number of scops with maximal loop depth 5")static llvm::Statistic NumScopsDepthFive = {"polly-scops", "NumScopsDepthFive"
, "Number of scops with maximal loop depth 5", {0}, {false}}
;
136STATISTIC(NumScopsDepthLarger,static llvm::Statistic NumScopsDepthLarger = {"polly-scops", "NumScopsDepthLarger"
, "Number of scops with maximal loop depth 6 and larger", {0}
, {false}}
137 "Number of scops with maximal loop depth 6 and larger")static llvm::Statistic NumScopsDepthLarger = {"polly-scops", "NumScopsDepthLarger"
, "Number of scops with maximal loop depth 6 and larger", {0}
, {false}}
;
138STATISTIC(MaxNumLoopsInScop, "Maximal number of loops in scops")static llvm::Statistic MaxNumLoopsInScop = {"polly-scops", "MaxNumLoopsInScop"
, "Maximal number of loops in scops", {0}, {false}}
;
139
140STATISTIC(NumValueWrites, "Number of scalar value writes after ScopInfo")static llvm::Statistic NumValueWrites = {"polly-scops", "NumValueWrites"
, "Number of scalar value writes after ScopInfo", {0}, {false
}}
;
141STATISTIC(static llvm::Statistic NumValueWritesInLoops = {"polly-scops"
, "NumValueWritesInLoops", "Number of scalar value writes nested in affine loops after ScopInfo"
, {0}, {false}}
142 NumValueWritesInLoops,static llvm::Statistic NumValueWritesInLoops = {"polly-scops"
, "NumValueWritesInLoops", "Number of scalar value writes nested in affine loops after ScopInfo"
, {0}, {false}}
143 "Number of scalar value writes nested in affine loops after ScopInfo")static llvm::Statistic NumValueWritesInLoops = {"polly-scops"
, "NumValueWritesInLoops", "Number of scalar value writes nested in affine loops after ScopInfo"
, {0}, {false}}
;
144STATISTIC(NumPHIWrites, "Number of scalar phi writes after ScopInfo")static llvm::Statistic NumPHIWrites = {"polly-scops", "NumPHIWrites"
, "Number of scalar phi writes after ScopInfo", {0}, {false}}
;
145STATISTIC(NumPHIWritesInLoops,static llvm::Statistic NumPHIWritesInLoops = {"polly-scops", "NumPHIWritesInLoops"
, "Number of scalar phi writes nested in affine loops after ScopInfo"
, {0}, {false}}
146 "Number of scalar phi writes nested in affine loops after ScopInfo")static llvm::Statistic NumPHIWritesInLoops = {"polly-scops", "NumPHIWritesInLoops"
, "Number of scalar phi writes nested in affine loops after ScopInfo"
, {0}, {false}}
;
147STATISTIC(NumSingletonWrites, "Number of singleton writes after ScopInfo")static llvm::Statistic NumSingletonWrites = {"polly-scops", "NumSingletonWrites"
, "Number of singleton writes after ScopInfo", {0}, {false}}
;
148STATISTIC(NumSingletonWritesInLoops,static llvm::Statistic NumSingletonWritesInLoops = {"polly-scops"
, "NumSingletonWritesInLoops", "Number of singleton writes nested in affine loops after ScopInfo"
, {0}, {false}}
149 "Number of singleton writes nested in affine loops after ScopInfo")static llvm::Statistic NumSingletonWritesInLoops = {"polly-scops"
, "NumSingletonWritesInLoops", "Number of singleton writes nested in affine loops after ScopInfo"
, {0}, {false}}
;
150
151// The maximal number of basic sets we allow during domain construction to
152// be created. More complex scops will result in very high compile time and
153// are also unlikely to result in good code
154static int const MaxDisjunctsInDomain = 20;
155
156// The number of disjunct in the context after which we stop to add more
157// disjuncts. This parameter is there to avoid exponential growth in the
158// number of disjunct when adding non-convex sets to the context.
159static int const MaxDisjunctsInContext = 4;
160
161// The maximal number of dimensions we allow during invariant load construction.
162// More complex access ranges will result in very high compile time and are also
163// unlikely to result in good code. This value is very high and should only
164// trigger for corner cases (e.g., the "dct_luma" function in h264, SPEC2006).
165static int const MaxDimensionsInAccessRange = 9;
166
167static cl::opt<int>
168 OptComputeOut("polly-analysis-computeout",
169 cl::desc("Bound the scop analysis by a maximal amount of "
170 "computational steps (0 means no bound)"),
171 cl::Hidden, cl::init(800000), cl::ZeroOrMore,
172 cl::cat(PollyCategory));
173
174static cl::opt<bool> PollyRemarksMinimal(
175 "polly-remarks-minimal",
176 cl::desc("Do not emit remarks about assumptions that are known"),
177 cl::Hidden, cl::ZeroOrMore, cl::init(false), cl::cat(PollyCategory));
178
179static cl::opt<int> RunTimeChecksMaxAccessDisjuncts(
180 "polly-rtc-max-array-disjuncts",
181 cl::desc("The maximal number of disjunts allowed in memory accesses to "
182 "to build RTCs."),
183 cl::Hidden, cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory));
184
185static cl::opt<unsigned> RunTimeChecksMaxParameters(
186 "polly-rtc-max-parameters",
187 cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden,
188 cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory));
189
190static cl::opt<unsigned> RunTimeChecksMaxArraysPerGroup(
191 "polly-rtc-max-arrays-per-group",
192 cl::desc("The maximal number of arrays to compare in each alias group."),
193 cl::Hidden, cl::ZeroOrMore, cl::init(20), cl::cat(PollyCategory));
194
195static cl::opt<std::string> UserContextStr(
196 "polly-context", cl::value_desc("isl parameter set"),
197 cl::desc("Provide additional constraints on the context parameters"),
198 cl::init(""), cl::cat(PollyCategory));
199
200static cl::opt<bool>
201 IslOnErrorAbort("polly-on-isl-error-abort",
202 cl::desc("Abort if an isl error is encountered"),
203 cl::init(true), cl::cat(PollyCategory));
204
205static cl::opt<bool> PollyPreciseInbounds(
206 "polly-precise-inbounds",
207 cl::desc("Take more precise inbounds assumptions (do not scale well)"),
208 cl::Hidden, cl::init(false), cl::cat(PollyCategory));
209
210static cl::opt<bool>
211 PollyIgnoreInbounds("polly-ignore-inbounds",
212 cl::desc("Do not take inbounds assumptions at all"),
213 cl::Hidden, cl::init(false), cl::cat(PollyCategory));
214
215static cl::opt<bool> PollyIgnoreParamBounds(
216 "polly-ignore-parameter-bounds",
217 cl::desc(
218 "Do not add parameter bounds and do no gist simplify sets accordingly"),
219 cl::Hidden, cl::init(false), cl::cat(PollyCategory));
220
221static cl::opt<bool> PollyAllowDereferenceOfAllFunctionParams(
222 "polly-allow-dereference-of-all-function-parameters",
223 cl::desc(
224 "Treat all parameters to functions that are pointers as dereferencible."
225 " This is useful for invariant load hoisting, since we can generate"
226 " less runtime checks. This is only valid if all pointers to functions"
227 " are always initialized, so that Polly can choose to hoist"
228 " their loads. "),
229 cl::Hidden, cl::init(false), cl::cat(PollyCategory));
230
231static cl::opt<bool> PollyPreciseFoldAccesses(
232 "polly-precise-fold-accesses",
233 cl::desc("Fold memory accesses to model more possible delinearizations "
234 "(does not scale well)"),
235 cl::Hidden, cl::init(false), cl::cat(PollyCategory));
236
237bool polly::UseInstructionNames;
238
239static cl::opt<bool, true> XUseInstructionNames(
240 "polly-use-llvm-names",
241 cl::desc("Use LLVM-IR names when deriving statement names"),
242 cl::location(UseInstructionNames), cl::Hidden, cl::init(false),
243 cl::ZeroOrMore, cl::cat(PollyCategory));
244
245static cl::opt<bool> PollyPrintInstructions(
246 "polly-print-instructions", cl::desc("Output instructions per ScopStmt"),
247 cl::Hidden, cl::Optional, cl::init(false), cl::cat(PollyCategory));
248
249//===----------------------------------------------------------------------===//
250
251// Create a sequence of two schedules. Either argument may be null and is
252// interpreted as the empty schedule. Can also return null if both schedules are
253// empty.
254static isl::schedule combineInSequence(isl::schedule Prev, isl::schedule Succ) {
255 if (!Prev)
256 return Succ;
257 if (!Succ)
258 return Prev;
259
260 return Prev.sequence(Succ);
261}
262
263static isl::set addRangeBoundsToSet(isl::set S, const ConstantRange &Range,
264 int dim, isl::dim type) {
265 isl::val V;
266 isl::ctx Ctx = S.get_ctx();
267
268 // The upper and lower bound for a parameter value is derived either from
269 // the data type of the parameter or from the - possibly more restrictive -
270 // range metadata.
271 V = valFromAPInt(Ctx.get(), Range.getSignedMin(), true);
272 S = S.lower_bound_val(type, dim, V);
273 V = valFromAPInt(Ctx.get(), Range.getSignedMax(), true);
274 S = S.upper_bound_val(type, dim, V);
275
276 if (Range.isFullSet())
277 return S;
278
279 if (S.n_basic_set() > MaxDisjunctsInContext)
280 return S;
281
282 // In case of signed wrapping, we can refine the set of valid values by
283 // excluding the part not covered by the wrapping range.
284 if (Range.isSignWrappedSet()) {
285 V = valFromAPInt(Ctx.get(), Range.getLower(), true);
286 isl::set SLB = S.lower_bound_val(type, dim, V);
287
288 V = valFromAPInt(Ctx.get(), Range.getUpper(), true);
289 V = V.sub_ui(1);
290 isl::set SUB = S.upper_bound_val(type, dim, V);
291 S = SLB.unite(SUB);
292 }
293
294 return S;
295}
296
297static const ScopArrayInfo *identifyBasePtrOriginSAI(Scop *S, Value *BasePtr) {
298 LoadInst *BasePtrLI = dyn_cast<LoadInst>(BasePtr);
299 if (!BasePtrLI)
300 return nullptr;
301
302 if (!S->contains(BasePtrLI))
303 return nullptr;
304
305 ScalarEvolution &SE = *S->getSE();
306
307 auto *OriginBaseSCEV =
308 SE.getPointerBase(SE.getSCEV(BasePtrLI->getPointerOperand()));
309 if (!OriginBaseSCEV)
310 return nullptr;
311
312 auto *OriginBaseSCEVUnknown = dyn_cast<SCEVUnknown>(OriginBaseSCEV);
313 if (!OriginBaseSCEVUnknown)
314 return nullptr;
315
316 return S->getScopArrayInfo(OriginBaseSCEVUnknown->getValue(),
317 MemoryKind::Array);
318}
319
320ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *ElementType, isl::ctx Ctx,
321 ArrayRef<const SCEV *> Sizes, MemoryKind Kind,
322 const DataLayout &DL, Scop *S,
323 const char *BaseName)
324 : BasePtr(BasePtr), ElementType(ElementType), Kind(Kind), DL(DL), S(*S) {
325 std::string BasePtrName =
326 BaseName ? BaseName
327 : getIslCompatibleName("MemRef", BasePtr, S->getNextArrayIdx(),
328 Kind == MemoryKind::PHI ? "__phi" : "",
329 UseInstructionNames);
330 Id = isl::id::alloc(Ctx, BasePtrName, this);
331
332 updateSizes(Sizes);
333
334 if (!BasePtr || Kind != MemoryKind::Array) {
335 BasePtrOriginSAI = nullptr;
336 return;
337 }
338
339 BasePtrOriginSAI = identifyBasePtrOriginSAI(S, BasePtr);
340 if (BasePtrOriginSAI)
341 const_cast<ScopArrayInfo *>(BasePtrOriginSAI)->addDerivedSAI(this);
342}
343
344ScopArrayInfo::~ScopArrayInfo() = default;
345
346isl::space ScopArrayInfo::getSpace() const {
347 auto Space = isl::space(Id.get_ctx(), 0, getNumberOfDimensions());
348 Space = Space.set_tuple_id(isl::dim::set, Id);
349 return Space;
350}
351
352bool ScopArrayInfo::isReadOnly() {
353 isl::union_set WriteSet = S.getWrites().range();
354 isl::space Space = getSpace();
355 WriteSet = WriteSet.extract_set(Space);
356
357 return bool(WriteSet.is_empty());
358}
359
360bool ScopArrayInfo::isCompatibleWith(const ScopArrayInfo *Array) const {
361 if (Array->getElementType() != getElementType())
362 return false;
363
364 if (Array->getNumberOfDimensions() != getNumberOfDimensions())
365 return false;
366
367 for (unsigned i = 0; i < getNumberOfDimensions(); i++)
368 if (Array->getDimensionSize(i) != getDimensionSize(i))
369 return false;
370
371 return true;
372}
373
374void ScopArrayInfo::updateElementType(Type *NewElementType) {
375 if (NewElementType == ElementType)
376 return;
377
378 auto OldElementSize = DL.getTypeAllocSizeInBits(ElementType);
379 auto NewElementSize = DL.getTypeAllocSizeInBits(NewElementType);
380
381 if (NewElementSize == OldElementSize || NewElementSize == 0)
382 return;
383
384 if (NewElementSize % OldElementSize == 0 && NewElementSize < OldElementSize) {
385 ElementType = NewElementType;
386 } else {
387 auto GCD = GreatestCommonDivisor64(NewElementSize, OldElementSize);
388 ElementType = IntegerType::get(ElementType->getContext(), GCD);
389 }
390}
391
392/// Make the ScopArrayInfo model a Fortran Array
393void ScopArrayInfo::applyAndSetFAD(Value *FAD) {
394 assert(FAD && "got invalid Fortran array descriptor")((FAD && "got invalid Fortran array descriptor") ? static_cast
<void> (0) : __assert_fail ("FAD && \"got invalid Fortran array descriptor\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 394, __PRETTY_FUNCTION__))
;
395 if (this->FAD) {
396 assert(this->FAD == FAD &&((this->FAD == FAD && "receiving different array descriptors for same array"
) ? static_cast<void> (0) : __assert_fail ("this->FAD == FAD && \"receiving different array descriptors for same array\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 397, __PRETTY_FUNCTION__))
397 "receiving different array descriptors for same array")((this->FAD == FAD && "receiving different array descriptors for same array"
) ? static_cast<void> (0) : __assert_fail ("this->FAD == FAD && \"receiving different array descriptors for same array\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 397, __PRETTY_FUNCTION__))
;
398 return;
399 }
400
401 assert(DimensionSizesPw.size() > 0 && !DimensionSizesPw[0])((DimensionSizesPw.size() > 0 && !DimensionSizesPw
[0]) ? static_cast<void> (0) : __assert_fail ("DimensionSizesPw.size() > 0 && !DimensionSizesPw[0]"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 401, __PRETTY_FUNCTION__))
;
402 assert(!this->FAD)((!this->FAD) ? static_cast<void> (0) : __assert_fail
("!this->FAD", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 402, __PRETTY_FUNCTION__))
;
403 this->FAD = FAD;
404
405 isl::space Space(S.getIslCtx(), 1, 0);
406
407 std::string param_name = getName();
408 param_name += "_fortranarr_size";
409 isl::id IdPwAff = isl::id::alloc(S.getIslCtx(), param_name, this);
410
411 Space = Space.set_dim_id(isl::dim::param, 0, IdPwAff);
412 isl::pw_aff PwAff =
413 isl::aff::var_on_domain(isl::local_space(Space), isl::dim::param, 0);
414
415 DimensionSizesPw[0] = PwAff;
416}
417
418bool ScopArrayInfo::updateSizes(ArrayRef<const SCEV *> NewSizes,
419 bool CheckConsistency) {
420 int SharedDims = std::min(NewSizes.size(), DimensionSizes.size());
421 int ExtraDimsNew = NewSizes.size() - SharedDims;
422 int ExtraDimsOld = DimensionSizes.size() - SharedDims;
423
424 if (CheckConsistency) {
425 for (int i = 0; i < SharedDims; i++) {
426 auto *NewSize = NewSizes[i + ExtraDimsNew];
427 auto *KnownSize = DimensionSizes[i + ExtraDimsOld];
428 if (NewSize && KnownSize && NewSize != KnownSize)
429 return false;
430 }
431
432 if (DimensionSizes.size() >= NewSizes.size())
433 return true;
434 }
435
436 DimensionSizes.clear();
437 DimensionSizes.insert(DimensionSizes.begin(), NewSizes.begin(),
438 NewSizes.end());
439 DimensionSizesPw.clear();
440 for (const SCEV *Expr : DimensionSizes) {
441 if (!Expr) {
442 DimensionSizesPw.push_back(nullptr);
443 continue;
444 }
445 isl::pw_aff Size = S.getPwAffOnly(Expr);
446 DimensionSizesPw.push_back(Size);
447 }
448 return true;
449}
450
451std::string ScopArrayInfo::getName() const { return Id.get_name(); }
452
453int ScopArrayInfo::getElemSizeInBytes() const {
454 return DL.getTypeAllocSize(ElementType);
455}
456
457isl::id ScopArrayInfo::getBasePtrId() const { return Id; }
458
459#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
460LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void ScopArrayInfo::dump() const { print(errs()); }
461#endif
462
463void ScopArrayInfo::print(raw_ostream &OS, bool SizeAsPwAff) const {
464 OS.indent(8) << *getElementType() << " " << getName();
465 unsigned u = 0;
466 // If this is a Fortran array, then we can print the outermost dimension
467 // as a isl_pw_aff even though there is no SCEV information.
468 bool IsOutermostSizeKnown = SizeAsPwAff && FAD;
469
470 if (!IsOutermostSizeKnown && getNumberOfDimensions() > 0 &&
471 !getDimensionSize(0)) {
472 OS << "[*]";
473 u++;
474 }
475 for (; u < getNumberOfDimensions(); u++) {
476 OS << "[";
477
478 if (SizeAsPwAff) {
479 isl::pw_aff Size = getDimensionSizePw(u);
480 OS << " " << Size << " ";
481 } else {
482 OS << *getDimensionSize(u);
483 }
484
485 OS << "]";
486 }
487
488 OS << ";";
489
490 if (BasePtrOriginSAI)
491 OS << " [BasePtrOrigin: " << BasePtrOriginSAI->getName() << "]";
492
493 OS << " // Element size " << getElemSizeInBytes() << "\n";
494}
495
496const ScopArrayInfo *
497ScopArrayInfo::getFromAccessFunction(isl::pw_multi_aff PMA) {
498 isl::id Id = PMA.get_tuple_id(isl::dim::out);
499 assert(!Id.is_null() && "Output dimension didn't have an ID")((!Id.is_null() && "Output dimension didn't have an ID"
) ? static_cast<void> (0) : __assert_fail ("!Id.is_null() && \"Output dimension didn't have an ID\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 499, __PRETTY_FUNCTION__))
;
500 return getFromId(Id);
501}
502
503const ScopArrayInfo *ScopArrayInfo::getFromId(isl::id Id) {
504 void *User = Id.get_user();
505 const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
506 return SAI;
507}
508
509void MemoryAccess::wrapConstantDimensions() {
510 auto *SAI = getScopArrayInfo();
511 isl::space ArraySpace = SAI->getSpace();
512 isl::ctx Ctx = ArraySpace.get_ctx();
513 unsigned DimsArray = SAI->getNumberOfDimensions();
514
515 isl::multi_aff DivModAff = isl::multi_aff::identity(
516 ArraySpace.map_from_domain_and_range(ArraySpace));
517 isl::local_space LArraySpace = isl::local_space(ArraySpace);
518
519 // Begin with last dimension, to iteratively carry into higher dimensions.
520 for (int i = DimsArray - 1; i > 0; i--) {
521 auto *DimSize = SAI->getDimensionSize(i);
522 auto *DimSizeCst = dyn_cast<SCEVConstant>(DimSize);
523
524 // This transformation is not applicable to dimensions with dynamic size.
525 if (!DimSizeCst)
526 continue;
527
528 // This transformation is not applicable to dimensions of size zero.
529 if (DimSize->isZero())
530 continue;
531
532 isl::val DimSizeVal =
533 valFromAPInt(Ctx.get(), DimSizeCst->getAPInt(), false);
534 isl::aff Var = isl::aff::var_on_domain(LArraySpace, isl::dim::set, i);
535 isl::aff PrevVar =
536 isl::aff::var_on_domain(LArraySpace, isl::dim::set, i - 1);
537
538 // Compute: index % size
539 // Modulo must apply in the divide of the previous iteration, if any.
540 isl::aff Modulo = Var.mod(DimSizeVal);
541 Modulo = Modulo.pullback(DivModAff);
542
543 // Compute: floor(index / size)
544 isl::aff Divide = Var.div(isl::aff(LArraySpace, DimSizeVal));
545 Divide = Divide.floor();
546 Divide = Divide.add(PrevVar);
547 Divide = Divide.pullback(DivModAff);
548
549 // Apply Modulo and Divide.
550 DivModAff = DivModAff.set_aff(i, Modulo);
551 DivModAff = DivModAff.set_aff(i - 1, Divide);
552 }
553
554 // Apply all modulo/divides on the accesses.
555 isl::map Relation = AccessRelation;
556 Relation = Relation.apply_range(isl::map::from_multi_aff(DivModAff));
557 Relation = Relation.detect_equalities();
558 AccessRelation = Relation;
559}
560
561void MemoryAccess::updateDimensionality() {
562 auto *SAI = getScopArrayInfo();
563 isl::space ArraySpace = SAI->getSpace();
564 isl::space AccessSpace = AccessRelation.get_space().range();
565 isl::ctx Ctx = ArraySpace.get_ctx();
566
567 auto DimsArray = ArraySpace.dim(isl::dim::set);
568 auto DimsAccess = AccessSpace.dim(isl::dim::set);
569 auto DimsMissing = DimsArray - DimsAccess;
570
571 auto *BB = getStatement()->getEntryBlock();
572 auto &DL = BB->getModule()->getDataLayout();
573 unsigned ArrayElemSize = SAI->getElemSizeInBytes();
574 unsigned ElemBytes = DL.getTypeAllocSize(getElementType());
575
576 isl::map Map = isl::map::from_domain_and_range(
577 isl::set::universe(AccessSpace), isl::set::universe(ArraySpace));
578
579 for (unsigned i = 0; i < DimsMissing; i++)
580 Map = Map.fix_si(isl::dim::out, i, 0);
581
582 for (unsigned i = DimsMissing; i < DimsArray; i++)
583 Map = Map.equate(isl::dim::in, i - DimsMissing, isl::dim::out, i);
584
585 AccessRelation = AccessRelation.apply_range(Map);
586
587 // For the non delinearized arrays, divide the access function of the last
588 // subscript by the size of the elements in the array.
589 //
590 // A stride one array access in C expressed as A[i] is expressed in
591 // LLVM-IR as something like A[i * elementsize]. This hides the fact that
592 // two subsequent values of 'i' index two values that are stored next to
593 // each other in memory. By this division we make this characteristic
594 // obvious again. If the base pointer was accessed with offsets not divisible
595 // by the accesses element size, we will have chosen a smaller ArrayElemSize
596 // that divides the offsets of all accesses to this base pointer.
597 if (DimsAccess == 1) {
598 isl::val V = isl::val(Ctx, ArrayElemSize);
599 AccessRelation = AccessRelation.floordiv_val(V);
600 }
601
602 // We currently do this only if we added at least one dimension, which means
603 // some dimension's indices have not been specified, an indicator that some
604 // index values have been added together.
605 // TODO: Investigate general usefulness; Effect on unit tests is to make index
606 // expressions more complicated.
607 if (DimsMissing)
608 wrapConstantDimensions();
609
610 if (!isAffine())
611 computeBoundsOnAccessRelation(ArrayElemSize);
612
613 // Introduce multi-element accesses in case the type loaded by this memory
614 // access is larger than the canonical element type of the array.
615 //
616 // An access ((float *)A)[i] to an array char *A is modeled as
617 // {[i] -> A[o] : 4 i <= o <= 4 i + 3
618 if (ElemBytes > ArrayElemSize) {
619 assert(ElemBytes % ArrayElemSize == 0 &&((ElemBytes % ArrayElemSize == 0 && "Loaded element size should be multiple of canonical element size"
) ? static_cast<void> (0) : __assert_fail ("ElemBytes % ArrayElemSize == 0 && \"Loaded element size should be multiple of canonical element size\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 620, __PRETTY_FUNCTION__))
620 "Loaded element size should be multiple of canonical element size")((ElemBytes % ArrayElemSize == 0 && "Loaded element size should be multiple of canonical element size"
) ? static_cast<void> (0) : __assert_fail ("ElemBytes % ArrayElemSize == 0 && \"Loaded element size should be multiple of canonical element size\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 620, __PRETTY_FUNCTION__))
;
621 isl::map Map = isl::map::from_domain_and_range(
622 isl::set::universe(ArraySpace), isl::set::universe(ArraySpace));
623 for (unsigned i = 0; i < DimsArray - 1; i++)
624 Map = Map.equate(isl::dim::in, i, isl::dim::out, i);
625
626 isl::constraint C;
627 isl::local_space LS;
628
629 LS = isl::local_space(Map.get_space());
630 int Num = ElemBytes / getScopArrayInfo()->getElemSizeInBytes();
631
632 C = isl::constraint::alloc_inequality(LS);
633 C = C.set_constant_val(isl::val(Ctx, Num - 1));
634 C = C.set_coefficient_si(isl::dim::in, DimsArray - 1, 1);
635 C = C.set_coefficient_si(isl::dim::out, DimsArray - 1, -1);
636 Map = Map.add_constraint(C);
637
638 C = isl::constraint::alloc_inequality(LS);
639 C = C.set_coefficient_si(isl::dim::in, DimsArray - 1, -1);
640 C = C.set_coefficient_si(isl::dim::out, DimsArray - 1, 1);
641 C = C.set_constant_val(isl::val(Ctx, 0));
642 Map = Map.add_constraint(C);
643 AccessRelation = AccessRelation.apply_range(Map);
644 }
645}
646
647const std::string
648MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) {
649 switch (RT) {
650 case MemoryAccess::RT_NONE:
651 llvm_unreachable("Requested a reduction operator string for a memory "::llvm::llvm_unreachable_internal("Requested a reduction operator string for a memory "
"access which isn't a reduction", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 652)
652 "access which isn't a reduction")::llvm::llvm_unreachable_internal("Requested a reduction operator string for a memory "
"access which isn't a reduction", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 652)
;
653 case MemoryAccess::RT_ADD:
654 return "+";
655 case MemoryAccess::RT_MUL:
656 return "*";
657 case MemoryAccess::RT_BOR:
658 return "|";
659 case MemoryAccess::RT_BXOR:
660 return "^";
661 case MemoryAccess::RT_BAND:
662 return "&";
663 }
664 llvm_unreachable("Unknown reduction type")::llvm::llvm_unreachable_internal("Unknown reduction type", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 664)
;
665}
666
667const ScopArrayInfo *MemoryAccess::getOriginalScopArrayInfo() const {
668 isl::id ArrayId = getArrayId();
669 void *User = ArrayId.get_user();
670 const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
671 return SAI;
672}
673
674const ScopArrayInfo *MemoryAccess::getLatestScopArrayInfo() const {
675 isl::id ArrayId = getLatestArrayId();
676 void *User = ArrayId.get_user();
677 const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
678 return SAI;
679}
680
681isl::id MemoryAccess::getOriginalArrayId() const {
682 return AccessRelation.get_tuple_id(isl::dim::out);
683}
684
685isl::id MemoryAccess::getLatestArrayId() const {
686 if (!hasNewAccessRelation())
687 return getOriginalArrayId();
688 return NewAccessRelation.get_tuple_id(isl::dim::out);
689}
690
691isl::map MemoryAccess::getAddressFunction() const {
692 return getAccessRelation().lexmin();
693}
694
695isl::pw_multi_aff
696MemoryAccess::applyScheduleToAccessRelation(isl::union_map USchedule) const {
697 isl::map Schedule, ScheduledAccRel;
698 isl::union_set UDomain;
699
700 UDomain = getStatement()->getDomain();
701 USchedule = USchedule.intersect_domain(UDomain);
702 Schedule = isl::map::from_union_map(USchedule);
703 ScheduledAccRel = getAddressFunction().apply_domain(Schedule);
704 return isl::pw_multi_aff::from_map(ScheduledAccRel);
705}
706
707isl::map MemoryAccess::getOriginalAccessRelation() const {
708 return AccessRelation;
709}
710
711std::string MemoryAccess::getOriginalAccessRelationStr() const {
712 return AccessRelation.to_str();
713}
714
715isl::space MemoryAccess::getOriginalAccessRelationSpace() const {
716 return AccessRelation.get_space();
717}
718
719isl::map MemoryAccess::getNewAccessRelation() const {
720 return NewAccessRelation;
721}
722
723std::string MemoryAccess::getNewAccessRelationStr() const {
724 return NewAccessRelation.to_str();
725}
726
727std::string MemoryAccess::getAccessRelationStr() const {
728 return getAccessRelation().to_str();
729}
730
731isl::basic_map MemoryAccess::createBasicAccessMap(ScopStmt *Statement) {
732 isl::space Space = isl::space(Statement->getIslCtx(), 0, 1);
733 Space = Space.align_params(Statement->getDomainSpace());
734
735 return isl::basic_map::from_domain_and_range(
736 isl::basic_set::universe(Statement->getDomainSpace()),
737 isl::basic_set::universe(Space));
738}
739
740// Formalize no out-of-bound access assumption
741//
742// When delinearizing array accesses we optimistically assume that the
743// delinearized accesses do not access out of bound locations (the subscript
744// expression of each array evaluates for each statement instance that is
745// executed to a value that is larger than zero and strictly smaller than the
746// size of the corresponding dimension). The only exception is the outermost
747// dimension for which we do not need to assume any upper bound. At this point
748// we formalize this assumption to ensure that at code generation time the
749// relevant run-time checks can be generated.
750//
751// To find the set of constraints necessary to avoid out of bound accesses, we
752// first build the set of data locations that are not within array bounds. We
753// then apply the reverse access relation to obtain the set of iterations that
754// may contain invalid accesses and reduce this set of iterations to the ones
755// that are actually executed by intersecting them with the domain of the
756// statement. If we now project out all loop dimensions, we obtain a set of
757// parameters that may cause statement instances to be executed that may
758// possibly yield out of bound memory accesses. The complement of these
759// constraints is the set of constraints that needs to be assumed to ensure such
760// statement instances are never executed.
761void MemoryAccess::assumeNoOutOfBound() {
762 if (PollyIgnoreInbounds)
763 return;
764 auto *SAI = getScopArrayInfo();
765 isl::space Space = getOriginalAccessRelationSpace().range();
766 isl::set Outside = isl::set::empty(Space);
767 for (int i = 1, Size = Space.dim(isl::dim::set); i < Size; ++i) {
768 isl::local_space LS(Space);
769 isl::pw_aff Var = isl::pw_aff::var_on_domain(LS, isl::dim::set, i);
770 isl::pw_aff Zero = isl::pw_aff(LS);
771
772 isl::set DimOutside = Var.lt_set(Zero);
773 isl::pw_aff SizeE = SAI->getDimensionSizePw(i);
774 SizeE = SizeE.add_dims(isl::dim::in, Space.dim(isl::dim::set));
775 SizeE = SizeE.set_tuple_id(isl::dim::in, Space.get_tuple_id(isl::dim::set));
776 DimOutside = DimOutside.unite(SizeE.le_set(Var));
777
778 Outside = Outside.unite(DimOutside);
779 }
780
781 Outside = Outside.apply(getAccessRelation().reverse());
782 Outside = Outside.intersect(Statement->getDomain());
783 Outside = Outside.params();
784
785 // Remove divs to avoid the construction of overly complicated assumptions.
786 // Doing so increases the set of parameter combinations that are assumed to
787 // not appear. This is always save, but may make the resulting run-time check
788 // bail out more often than strictly necessary.
789 Outside = Outside.remove_divs();
790 Outside = Outside.complement();
791 const auto &Loc = getAccessInstruction()
792 ? getAccessInstruction()->getDebugLoc()
793 : DebugLoc();
794 if (!PollyPreciseInbounds)
795 Outside = Outside.gist_params(Statement->getDomain().params());
796 Statement->getParent()->recordAssumption(INBOUNDS, Outside, Loc,
797 AS_ASSUMPTION);
798}
799
800void MemoryAccess::buildMemIntrinsicAccessRelation() {
801 assert(isMemoryIntrinsic())((isMemoryIntrinsic()) ? static_cast<void> (0) : __assert_fail
("isMemoryIntrinsic()", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 801, __PRETTY_FUNCTION__))
;
802 assert(Subscripts.size() == 2 && Sizes.size() == 1)((Subscripts.size() == 2 && Sizes.size() == 1) ? static_cast
<void> (0) : __assert_fail ("Subscripts.size() == 2 && Sizes.size() == 1"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 802, __PRETTY_FUNCTION__))
;
803
804 isl::pw_aff SubscriptPWA = getPwAff(Subscripts[0]);
805 isl::map SubscriptMap = isl::map::from_pw_aff(SubscriptPWA);
806
807 isl::map LengthMap;
808 if (Subscripts[1] == nullptr) {
809 LengthMap = isl::map::universe(SubscriptMap.get_space());
810 } else {
811 isl::pw_aff LengthPWA = getPwAff(Subscripts[1]);
812 LengthMap = isl::map::from_pw_aff(LengthPWA);
813 isl::space RangeSpace = LengthMap.get_space().range();
814 LengthMap = LengthMap.apply_range(isl::map::lex_gt(RangeSpace));
815 }
816 LengthMap = LengthMap.lower_bound_si(isl::dim::out, 0, 0);
817 LengthMap = LengthMap.align_params(SubscriptMap.get_space());
818 SubscriptMap = SubscriptMap.align_params(LengthMap.get_space());
819 LengthMap = LengthMap.sum(SubscriptMap);
820 AccessRelation =
821 LengthMap.set_tuple_id(isl::dim::in, getStatement()->getDomainId());
822}
823
824void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
825 ScalarEvolution *SE = Statement->getParent()->getSE();
826
827 auto MAI = MemAccInst(getAccessInstruction());
828 if (isa<MemIntrinsic>(MAI))
829 return;
830
831 Value *Ptr = MAI.getPointerOperand();
832 if (!Ptr || !SE->isSCEVable(Ptr->getType()))
833 return;
834
835 auto *PtrSCEV = SE->getSCEV(Ptr);
836 if (isa<SCEVCouldNotCompute>(PtrSCEV))
837 return;
838
839 auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
840 if (BasePtrSCEV && !isa<SCEVCouldNotCompute>(BasePtrSCEV))
841 PtrSCEV = SE->getMinusSCEV(PtrSCEV, BasePtrSCEV);
842
843 const ConstantRange &Range = SE->getSignedRange(PtrSCEV);
844 if (Range.isFullSet())
845 return;
846
847 if (Range.isWrappedSet() || Range.isSignWrappedSet())
848 return;
849
850 bool isWrapping = Range.isSignWrappedSet();
851
852 unsigned BW = Range.getBitWidth();
853 const auto One = APInt(BW, 1);
854 const auto LB = isWrapping ? Range.getLower() : Range.getSignedMin();
855 const auto UB = isWrapping ? (Range.getUpper() - One) : Range.getSignedMax();
856
857 auto Min = LB.sdiv(APInt(BW, ElementSize));
858 auto Max = UB.sdiv(APInt(BW, ElementSize)) + One;
859
860 assert(Min.sle(Max) && "Minimum expected to be less or equal than max")((Min.sle(Max) && "Minimum expected to be less or equal than max"
) ? static_cast<void> (0) : __assert_fail ("Min.sle(Max) && \"Minimum expected to be less or equal than max\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 860, __PRETTY_FUNCTION__))
;
861
862 isl::map Relation = AccessRelation;
863 isl::set AccessRange = Relation.range();
864 AccessRange = addRangeBoundsToSet(AccessRange, ConstantRange(Min, Max), 0,
865 isl::dim::set);
866 AccessRelation = Relation.intersect_range(AccessRange);
867}
868
869void MemoryAccess::foldAccessRelation() {
870 if (Sizes.size() < 2 || isa<SCEVConstant>(Sizes[1]))
871 return;
872
873 int Size = Subscripts.size();
874
875 isl::map NewAccessRelation = AccessRelation;
876
877 for (int i = Size - 2; i >= 0; --i) {
878 isl::space Space;
879 isl::map MapOne, MapTwo;
880 isl::pw_aff DimSize = getPwAff(Sizes[i + 1]);
881
882 isl::space SpaceSize = DimSize.get_space();
883 isl::id ParamId = SpaceSize.get_dim_id(isl::dim::param, 0);
884
885 Space = AccessRelation.get_space();
886 Space = Space.range().map_from_set();
887 Space = Space.align_params(SpaceSize);
888
889 int ParamLocation = Space.find_dim_by_id(isl::dim::param, ParamId);
890
891 MapOne = isl::map::universe(Space);
892 for (int j = 0; j < Size; ++j)
893 MapOne = MapOne.equate(isl::dim::in, j, isl::dim::out, j);
894 MapOne = MapOne.lower_bound_si(isl::dim::in, i + 1, 0);
895
896 MapTwo = isl::map::universe(Space);
897 for (int j = 0; j < Size; ++j)
898 if (j < i || j > i + 1)
899 MapTwo = MapTwo.equate(isl::dim::in, j, isl::dim::out, j);
900
901 isl::local_space LS(Space);
902 isl::constraint C;
903 C = isl::constraint::alloc_equality(LS);
904 C = C.set_constant_si(-1);
905 C = C.set_coefficient_si(isl::dim::in, i, 1);
906 C = C.set_coefficient_si(isl::dim::out, i, -1);
907 MapTwo = MapTwo.add_constraint(C);
908 C = isl::constraint::alloc_equality(LS);
909 C = C.set_coefficient_si(isl::dim::in, i + 1, 1);
910 C = C.set_coefficient_si(isl::dim::out, i + 1, -1);
911 C = C.set_coefficient_si(isl::dim::param, ParamLocation, 1);
912 MapTwo = MapTwo.add_constraint(C);
913 MapTwo = MapTwo.upper_bound_si(isl::dim::in, i + 1, -1);
914
915 MapOne = MapOne.unite(MapTwo);
916 NewAccessRelation = NewAccessRelation.apply_range(MapOne);
917 }
918
919 isl::id BaseAddrId = getScopArrayInfo()->getBasePtrId();
920 isl::space Space = Statement->getDomainSpace();
921 NewAccessRelation = NewAccessRelation.set_tuple_id(
922 isl::dim::in, Space.get_tuple_id(isl::dim::set));
923 NewAccessRelation = NewAccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
924 NewAccessRelation = NewAccessRelation.gist_domain(Statement->getDomain());
925
926 // Access dimension folding might in certain cases increase the number of
927 // disjuncts in the memory access, which can possibly complicate the generated
928 // run-time checks and can lead to costly compilation.
929 if (!PollyPreciseFoldAccesses &&
930 NewAccessRelation.n_basic_map() > AccessRelation.n_basic_map()) {
931 } else {
932 AccessRelation = NewAccessRelation;
933 }
934}
935
936/// Check if @p Expr is divisible by @p Size.
937static bool isDivisible(const SCEV *Expr, unsigned Size, ScalarEvolution &SE) {
938 assert(Size != 0)((Size != 0) ? static_cast<void> (0) : __assert_fail ("Size != 0"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 938, __PRETTY_FUNCTION__))
;
939 if (Size == 1)
940 return true;
941
942 // Only one factor needs to be divisible.
943 if (auto *MulExpr = dyn_cast<SCEVMulExpr>(Expr)) {
944 for (auto *FactorExpr : MulExpr->operands())
945 if (isDivisible(FactorExpr, Size, SE))
946 return true;
947 return false;
948 }
949
950 // For other n-ary expressions (Add, AddRec, Max,...) all operands need
951 // to be divisible.
952 if (auto *NAryExpr = dyn_cast<SCEVNAryExpr>(Expr)) {
953 for (auto *OpExpr : NAryExpr->operands())
954 if (!isDivisible(OpExpr, Size, SE))
955 return false;
956 return true;
957 }
958
959 auto *SizeSCEV = SE.getConstant(Expr->getType(), Size);
960 auto *UDivSCEV = SE.getUDivExpr(Expr, SizeSCEV);
961 auto *MulSCEV = SE.getMulExpr(UDivSCEV, SizeSCEV);
962 return MulSCEV == Expr;
963}
964
965void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
966 assert(AccessRelation.is_null() && "AccessRelation already built")((AccessRelation.is_null() && "AccessRelation already built"
) ? static_cast<void> (0) : __assert_fail ("AccessRelation.is_null() && \"AccessRelation already built\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 966, __PRETTY_FUNCTION__))
;
967
968 // Initialize the invalid domain which describes all iterations for which the
969 // access relation is not modeled correctly.
970 isl::set StmtInvalidDomain = getStatement()->getInvalidDomain();
971 InvalidDomain = isl::set::empty(StmtInvalidDomain.get_space());
972
973 isl::ctx Ctx = Id.get_ctx();
974 isl::id BaseAddrId = SAI->getBasePtrId();
975
976 if (getAccessInstruction() && isa<MemIntrinsic>(getAccessInstruction())) {
977 buildMemIntrinsicAccessRelation();
978 AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
979 return;
980 }
981
982 if (!isAffine()) {
983 // We overapproximate non-affine accesses with a possible access to the
984 // whole array. For read accesses it does not make a difference, if an
985 // access must or may happen. However, for write accesses it is important to
986 // differentiate between writes that must happen and writes that may happen.
987 if (AccessRelation.is_null())
988 AccessRelation = createBasicAccessMap(Statement);
989
990 AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
991 return;
992 }
993
994 isl::space Space = isl::space(Ctx, 0, Statement->getNumIterators(), 0);
995 AccessRelation = isl::map::universe(Space);
996
997 for (int i = 0, Size = Subscripts.size(); i < Size; ++i) {
998 isl::pw_aff Affine = getPwAff(Subscripts[i]);
999 isl::map SubscriptMap = isl::map::from_pw_aff(Affine);
1000 AccessRelation = AccessRelation.flat_range_product(SubscriptMap);
1001 }
1002
1003 Space = Statement->getDomainSpace();
1004 AccessRelation = AccessRelation.set_tuple_id(
1005 isl::dim::in, Space.get_tuple_id(isl::dim::set));
1006 AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
1007
1008 AccessRelation = AccessRelation.gist_domain(Statement->getDomain());
1009}
1010
1011MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst,
1012 AccessType AccType, Value *BaseAddress,
1013 Type *ElementType, bool Affine,
1014 ArrayRef<const SCEV *> Subscripts,
1015 ArrayRef<const SCEV *> Sizes, Value *AccessValue,
1016 MemoryKind Kind)
1017 : Kind(Kind), AccType(AccType), Statement(Stmt), InvalidDomain(nullptr),
1018 BaseAddr(BaseAddress), ElementType(ElementType),
1019 Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),
1020 AccessValue(AccessValue), IsAffine(Affine),
1021 Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
1022 NewAccessRelation(nullptr), FAD(nullptr) {
1023 static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
1024 const std::string Access = TypeStrings[AccType] + utostr(Stmt->size());
1025
1026 std::string IdName = Stmt->getBaseName() + Access;
1027 Id = isl::id::alloc(Stmt->getParent()->getIslCtx(), IdName, this);
1028}
1029
1030MemoryAccess::MemoryAccess(ScopStmt *Stmt, AccessType AccType, isl::map AccRel)
1031 : Kind(MemoryKind::Array), AccType(AccType), Statement(Stmt),
1032 InvalidDomain(nullptr), AccessRelation(nullptr),
1033 NewAccessRelation(AccRel), FAD(nullptr) {
1034 isl::id ArrayInfoId = NewAccessRelation.get_tuple_id(isl::dim::out);
1035 auto *SAI = ScopArrayInfo::getFromId(ArrayInfoId);
1036 Sizes.push_back(nullptr);
1037 for (unsigned i = 1; i < SAI->getNumberOfDimensions(); i++)
1038 Sizes.push_back(SAI->getDimensionSize(i));
1039 ElementType = SAI->getElementType();
1040 BaseAddr = SAI->getBasePtr();
1041 static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
1042 const std::string Access = TypeStrings[AccType] + utostr(Stmt->size());
1043
1044 std::string IdName = Stmt->getBaseName() + Access;
1045 Id = isl::id::alloc(Stmt->getParent()->getIslCtx(), IdName, this);
1046}
1047
1048MemoryAccess::~MemoryAccess() = default;
1049
1050void MemoryAccess::realignParams() {
1051 isl::set Ctx = Statement->getParent()->getContext();
1052 InvalidDomain = InvalidDomain.gist_params(Ctx);
1053 AccessRelation = AccessRelation.gist_params(Ctx);
1054}
1055
1056const std::string MemoryAccess::getReductionOperatorStr() const {
1057 return MemoryAccess::getReductionOperatorStr(getReductionType());
1058}
1059
1060isl::id MemoryAccess::getId() const { return Id; }
1061
1062raw_ostream &polly::operator<<(raw_ostream &OS,
1063 MemoryAccess::ReductionType RT) {
1064 if (RT == MemoryAccess::RT_NONE)
1065 OS << "NONE";
1066 else
1067 OS << MemoryAccess::getReductionOperatorStr(RT);
1068 return OS;
1069}
1070
1071void MemoryAccess::setFortranArrayDescriptor(Value *FAD) { this->FAD = FAD; }
1072
1073void MemoryAccess::print(raw_ostream &OS) const {
1074 switch (AccType) {
1075 case READ:
1076 OS.indent(12) << "ReadAccess :=\t";
1077 break;
1078 case MUST_WRITE:
1079 OS.indent(12) << "MustWriteAccess :=\t";
1080 break;
1081 case MAY_WRITE:
1082 OS.indent(12) << "MayWriteAccess :=\t";
1083 break;
1084 }
1085
1086 OS << "[Reduction Type: " << getReductionType() << "] ";
1087
1088 if (FAD) {
1089 OS << "[Fortran array descriptor: " << FAD->getName();
1090 OS << "] ";
1091 };
1092
1093 OS << "[Scalar: " << isScalarKind() << "]\n";
1094 OS.indent(16) << getOriginalAccessRelationStr() << ";\n";
1095 if (hasNewAccessRelation())
1096 OS.indent(11) << "new: " << getNewAccessRelationStr() << ";\n";
1097}
1098
1099#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1100LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void MemoryAccess::dump() const { print(errs()); }
1101#endif
1102
1103isl::pw_aff MemoryAccess::getPwAff(const SCEV *E) {
1104 auto *Stmt = getStatement();
1105 PWACtx PWAC = Stmt->getParent()->getPwAff(E, Stmt->getEntryBlock());
1106 isl::set StmtDom = getStatement()->getDomain();
1107 StmtDom = StmtDom.reset_tuple_id();
1108 isl::set NewInvalidDom = StmtDom.intersect(PWAC.second);
1109 InvalidDomain = InvalidDomain.unite(NewInvalidDom);
1110 return PWAC.first;
1111}
1112
1113// Create a map in the size of the provided set domain, that maps from the
1114// one element of the provided set domain to another element of the provided
1115// set domain.
1116// The mapping is limited to all points that are equal in all but the last
1117// dimension and for which the last dimension of the input is strict smaller
1118// than the last dimension of the output.
1119//
1120// getEqualAndLarger(set[i0, i1, ..., iX]):
1121//
1122// set[i0, i1, ..., iX] -> set[o0, o1, ..., oX]
1123// : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1), iX < oX
1124//
1125static isl::map getEqualAndLarger(isl::space SetDomain) {
1126 isl::space Space = SetDomain.map_from_set();
1127 isl::map Map = isl::map::universe(Space);
1128 unsigned lastDimension = Map.dim(isl::dim::in) - 1;
1129
1130 // Set all but the last dimension to be equal for the input and output
1131 //
1132 // input[i0, i1, ..., iX] -> output[o0, o1, ..., oX]
1133 // : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1)
1134 for (unsigned i = 0; i < lastDimension; ++i)
1135 Map = Map.equate(isl::dim::in, i, isl::dim::out, i);
1136
1137 // Set the last dimension of the input to be strict smaller than the
1138 // last dimension of the output.
1139 //
1140 // input[?,?,?,...,iX] -> output[?,?,?,...,oX] : iX < oX
1141 Map = Map.order_lt(isl::dim::in, lastDimension, isl::dim::out, lastDimension);
1142 return Map;
1143}
1144
1145isl::set MemoryAccess::getStride(isl::map Schedule) const {
1146 isl::map AccessRelation = getAccessRelation();
1147 isl::space Space = Schedule.get_space().range();
1148 isl::map NextScatt = getEqualAndLarger(Space);
1149
1150 Schedule = Schedule.reverse();
1151 NextScatt = NextScatt.lexmin();
1152
1153 NextScatt = NextScatt.apply_range(Schedule);
1154 NextScatt = NextScatt.apply_range(AccessRelation);
1155 NextScatt = NextScatt.apply_domain(Schedule);
1156 NextScatt = NextScatt.apply_domain(AccessRelation);
1157
1158 isl::set Deltas = NextScatt.deltas();
1159 return Deltas;
1160}
1161
1162bool MemoryAccess::isStrideX(isl::map Schedule, int StrideWidth) const {
1163 isl::set Stride, StrideX;
1164 bool IsStrideX;
1165
1166 Stride = getStride(Schedule);
1167 StrideX = isl::set::universe(Stride.get_space());
1168 for (unsigned i = 0; i < StrideX.dim(isl::dim::set) - 1; i++)
1169 StrideX = StrideX.fix_si(isl::dim::set, i, 0);
1170 StrideX = StrideX.fix_si(isl::dim::set, StrideX.dim(isl::dim::set) - 1,
1171 StrideWidth);
1172 IsStrideX = Stride.is_subset(StrideX);
1173
1174 return IsStrideX;
1175}
1176
1177bool MemoryAccess::isStrideZero(isl::map Schedule) const {
1178 return isStrideX(Schedule, 0);
1179}
1180
1181bool MemoryAccess::isStrideOne(isl::map Schedule) const {
1182 return isStrideX(Schedule, 1);
1183}
1184
1185void MemoryAccess::setAccessRelation(isl::map NewAccess) {
1186 AccessRelation = NewAccess;
1187}
1188
1189void MemoryAccess::setNewAccessRelation(isl::map NewAccess) {
1190 assert(NewAccess)((NewAccess) ? static_cast<void> (0) : __assert_fail ("NewAccess"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1190, __PRETTY_FUNCTION__))
;
1191
1192#ifndef NDEBUG
1193 // Check domain space compatibility.
1194 isl::space NewSpace = NewAccess.get_space();
1195 isl::space NewDomainSpace = NewSpace.domain();
1196 isl::space OriginalDomainSpace = getStatement()->getDomainSpace();
1197 assert(OriginalDomainSpace.has_equal_tuples(NewDomainSpace))((OriginalDomainSpace.has_equal_tuples(NewDomainSpace)) ? static_cast
<void> (0) : __assert_fail ("OriginalDomainSpace.has_equal_tuples(NewDomainSpace)"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1197, __PRETTY_FUNCTION__))
;
1198
1199 // Reads must be executed unconditionally. Writes might be executed in a
1200 // subdomain only.
1201 if (isRead()) {
1202 // Check whether there is an access for every statement instance.
1203 isl::set StmtDomain = getStatement()->getDomain();
1204 StmtDomain =
1205 StmtDomain.intersect_params(getStatement()->getParent()->getContext());
1206 isl::set NewDomain = NewAccess.domain();
1207 assert(StmtDomain.is_subset(NewDomain) &&((StmtDomain.is_subset(NewDomain) && "Partial READ accesses not supported"
) ? static_cast<void> (0) : __assert_fail ("StmtDomain.is_subset(NewDomain) && \"Partial READ accesses not supported\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1208, __PRETTY_FUNCTION__))
1208 "Partial READ accesses not supported")((StmtDomain.is_subset(NewDomain) && "Partial READ accesses not supported"
) ? static_cast<void> (0) : __assert_fail ("StmtDomain.is_subset(NewDomain) && \"Partial READ accesses not supported\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1208, __PRETTY_FUNCTION__))
;
1209 }
1210
1211 isl::space NewAccessSpace = NewAccess.get_space();
1212 assert(NewAccessSpace.has_tuple_id(isl::dim::set) &&((NewAccessSpace.has_tuple_id(isl::dim::set) && "Must specify the array that is accessed"
) ? static_cast<void> (0) : __assert_fail ("NewAccessSpace.has_tuple_id(isl::dim::set) && \"Must specify the array that is accessed\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1213, __PRETTY_FUNCTION__))
1213 "Must specify the array that is accessed")((NewAccessSpace.has_tuple_id(isl::dim::set) && "Must specify the array that is accessed"
) ? static_cast<void> (0) : __assert_fail ("NewAccessSpace.has_tuple_id(isl::dim::set) && \"Must specify the array that is accessed\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1213, __PRETTY_FUNCTION__))
;
1214 isl::id NewArrayId = NewAccessSpace.get_tuple_id(isl::dim::set);
1215 auto *SAI = static_cast<ScopArrayInfo *>(NewArrayId.get_user());
1216 assert(SAI && "Must set a ScopArrayInfo")((SAI && "Must set a ScopArrayInfo") ? static_cast<
void> (0) : __assert_fail ("SAI && \"Must set a ScopArrayInfo\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1216, __PRETTY_FUNCTION__))
;
1217
1218 if (SAI->isArrayKind() && SAI->getBasePtrOriginSAI()) {
1219 InvariantEquivClassTy *EqClass =
1220 getStatement()->getParent()->lookupInvariantEquivClass(
1221 SAI->getBasePtr());
1222 assert(EqClass &&((EqClass && "Access functions to indirect arrays must have an invariant and "
"hoisted base pointer") ? static_cast<void> (0) : __assert_fail
("EqClass && \"Access functions to indirect arrays must have an invariant and \" \"hoisted base pointer\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1224, __PRETTY_FUNCTION__))
1223 "Access functions to indirect arrays must have an invariant and "((EqClass && "Access functions to indirect arrays must have an invariant and "
"hoisted base pointer") ? static_cast<void> (0) : __assert_fail
("EqClass && \"Access functions to indirect arrays must have an invariant and \" \"hoisted base pointer\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1224, __PRETTY_FUNCTION__))
1224 "hoisted base pointer")((EqClass && "Access functions to indirect arrays must have an invariant and "
"hoisted base pointer") ? static_cast<void> (0) : __assert_fail
("EqClass && \"Access functions to indirect arrays must have an invariant and \" \"hoisted base pointer\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1224, __PRETTY_FUNCTION__))
;
1225 }
1226
1227 // Check whether access dimensions correspond to number of dimensions of the
1228 // accesses array.
1229 auto Dims = SAI->getNumberOfDimensions();
1230 assert(NewAccessSpace.dim(isl::dim::set) == Dims &&((NewAccessSpace.dim(isl::dim::set) == Dims && "Access dims must match array dims"
) ? static_cast<void> (0) : __assert_fail ("NewAccessSpace.dim(isl::dim::set) == Dims && \"Access dims must match array dims\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1231, __PRETTY_FUNCTION__))
1231 "Access dims must match array dims")((NewAccessSpace.dim(isl::dim::set) == Dims && "Access dims must match array dims"
) ? static_cast<void> (0) : __assert_fail ("NewAccessSpace.dim(isl::dim::set) == Dims && \"Access dims must match array dims\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1231, __PRETTY_FUNCTION__))
;
1232#endif
1233
1234 NewAccess = NewAccess.gist_domain(getStatement()->getDomain());
1235 NewAccessRelation = NewAccess;
1236}
1237
1238bool MemoryAccess::isLatestPartialAccess() const {
1239 isl::set StmtDom = getStatement()->getDomain();
1240 isl::set AccDom = getLatestAccessRelation().domain();
1241
1242 return !StmtDom.is_subset(AccDom);
1243}
1244
1245//===----------------------------------------------------------------------===//
1246
1247isl::map ScopStmt::getSchedule() const {
1248 isl::set Domain = getDomain();
1249 if (Domain.is_empty())
1250 return isl::map::from_aff(isl::aff(isl::local_space(getDomainSpace())));
1251 auto Schedule = getParent()->getSchedule();
1252 if (!Schedule)
1253 return nullptr;
1254 Schedule = Schedule.intersect_domain(isl::union_set(Domain));
1255 if (Schedule.is_empty())
1256 return isl::map::from_aff(isl::aff(isl::local_space(getDomainSpace())));
1257 isl::map M = M.from_union_map(Schedule);
1258 M = M.coalesce();
1259 M = M.gist_domain(Domain);
1260 M = M.coalesce();
1261 return M;
1262}
1263
1264void ScopStmt::restrictDomain(isl::set NewDomain) {
1265 assert(NewDomain.is_subset(Domain) &&((NewDomain.is_subset(Domain) && "New domain is not a subset of old domain!"
) ? static_cast<void> (0) : __assert_fail ("NewDomain.is_subset(Domain) && \"New domain is not a subset of old domain!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1266, __PRETTY_FUNCTION__))
1266 "New domain is not a subset of old domain!")((NewDomain.is_subset(Domain) && "New domain is not a subset of old domain!"
) ? static_cast<void> (0) : __assert_fail ("NewDomain.is_subset(Domain) && \"New domain is not a subset of old domain!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1266, __PRETTY_FUNCTION__))
;
1267 Domain = NewDomain;
1268}
1269
1270void ScopStmt::addAccess(MemoryAccess *Access, bool Prepend) {
1271 Instruction *AccessInst = Access->getAccessInstruction();
1272
1273 if (Access->isArrayKind()) {
1274 MemoryAccessList &MAL = InstructionToAccess[AccessInst];
1275 MAL.emplace_front(Access);
1276 } else if (Access->isValueKind() && Access->isWrite()) {
1277 Instruction *AccessVal = cast<Instruction>(Access->getAccessValue());
1278 assert(!ValueWrites.lookup(AccessVal))((!ValueWrites.lookup(AccessVal)) ? static_cast<void> (
0) : __assert_fail ("!ValueWrites.lookup(AccessVal)", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1278, __PRETTY_FUNCTION__))
;
1279
1280 ValueWrites[AccessVal] = Access;
1281 } else if (Access->isValueKind() && Access->isRead()) {
1282 Value *AccessVal = Access->getAccessValue();
1283 assert(!ValueReads.lookup(AccessVal))((!ValueReads.lookup(AccessVal)) ? static_cast<void> (0
) : __assert_fail ("!ValueReads.lookup(AccessVal)", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1283, __PRETTY_FUNCTION__))
;
1284
1285 ValueReads[AccessVal] = Access;
1286 } else if (Access->isAnyPHIKind() && Access->isWrite()) {
1287 PHINode *PHI = cast<PHINode>(Access->getAccessValue());
1288 assert(!PHIWrites.lookup(PHI))((!PHIWrites.lookup(PHI)) ? static_cast<void> (0) : __assert_fail
("!PHIWrites.lookup(PHI)", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1288, __PRETTY_FUNCTION__))
;
1289
1290 PHIWrites[PHI] = Access;
1291 } else if (Access->isAnyPHIKind() && Access->isRead()) {
1292 PHINode *PHI = cast<PHINode>(Access->getAccessValue());
1293 assert(!PHIReads.lookup(PHI))((!PHIReads.lookup(PHI)) ? static_cast<void> (0) : __assert_fail
("!PHIReads.lookup(PHI)", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1293, __PRETTY_FUNCTION__))
;
1294
1295 PHIReads[PHI] = Access;
1296 }
1297
1298 if (Prepend) {
1299 MemAccs.insert(MemAccs.begin(), Access);
1300 return;
1301 }
1302 MemAccs.push_back(Access);
1303}
1304
1305void ScopStmt::realignParams() {
1306 for (MemoryAccess *MA : *this)
1307 MA->realignParams();
1308
1309 isl::set Ctx = Parent.getContext();
1310 InvalidDomain = InvalidDomain.gist_params(Ctx);
1311 Domain = Domain.gist_params(Ctx);
1312}
1313
1314/// Add @p BSet to set @p BoundedParts if @p BSet is bounded.
1315static isl::set collectBoundedParts(isl::set S) {
1316 isl::set BoundedParts = isl::set::empty(S.get_space());
1317 for (isl::basic_set BSet : S.get_basic_set_list())
1318 if (BSet.is_bounded())
1319 BoundedParts = BoundedParts.unite(isl::set(BSet));
1320 return BoundedParts;
1321}
1322
1323/// Compute the (un)bounded parts of @p S wrt. to dimension @p Dim.
1324///
1325/// @returns A separation of @p S into first an unbounded then a bounded subset,
1326/// both with regards to the dimension @p Dim.
1327static std::pair<isl::set, isl::set> partitionSetParts(isl::set S,
1328 unsigned Dim) {
1329 for (unsigned u = 0, e = S.n_dim(); u < e; u++)
1330 S = S.lower_bound_si(isl::dim::set, u, 0);
1331
1332 unsigned NumDimsS = S.n_dim();
1333 isl::set OnlyDimS = S;
1334
1335 // Remove dimensions that are greater than Dim as they are not interesting.
1336 assert(NumDimsS >= Dim + 1)((NumDimsS >= Dim + 1) ? static_cast<void> (0) : __assert_fail
("NumDimsS >= Dim + 1", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1336, __PRETTY_FUNCTION__))
;
1337 OnlyDimS = OnlyDimS.project_out(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);
1338
1339 // Create artificial parametric upper bounds for dimensions smaller than Dim
1340 // as we are not interested in them.
1341 OnlyDimS = OnlyDimS.insert_dims(isl::dim::param, 0, Dim);
1342
1343 for (unsigned u = 0; u < Dim; u++) {
1344 isl::constraint C = isl::constraint::alloc_inequality(
1345 isl::local_space(OnlyDimS.get_space()));
1346 C = C.set_coefficient_si(isl::dim::param, u, 1);
1347 C = C.set_coefficient_si(isl::dim::set, u, -1);
1348 OnlyDimS = OnlyDimS.add_constraint(C);
1349 }
1350
1351 // Collect all bounded parts of OnlyDimS.
1352 isl::set BoundedParts = collectBoundedParts(OnlyDimS);
1353
1354 // Create the dimensions greater than Dim again.
1355 BoundedParts =
1356 BoundedParts.insert_dims(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);
1357
1358 // Remove the artificial upper bound parameters again.
1359 BoundedParts = BoundedParts.remove_dims(isl::dim::param, 0, Dim);
1360
1361 isl::set UnboundedParts = S.subtract(BoundedParts);
1362 return std::make_pair(UnboundedParts, BoundedParts);
1363}
1364
1365/// Create the conditions under which @p L @p Pred @p R is true.
1366static isl::set buildConditionSet(ICmpInst::Predicate Pred, isl::pw_aff L,
1367 isl::pw_aff R) {
1368 switch (Pred) {
1369 case ICmpInst::ICMP_EQ:
1370 return L.eq_set(R);
1371 case ICmpInst::ICMP_NE:
1372 return L.ne_set(R);
1373 case ICmpInst::ICMP_SLT:
1374 return L.lt_set(R);
1375 case ICmpInst::ICMP_SLE:
1376 return L.le_set(R);
1377 case ICmpInst::ICMP_SGT:
1378 return L.gt_set(R);
1379 case ICmpInst::ICMP_SGE:
1380 return L.ge_set(R);
1381 case ICmpInst::ICMP_ULT:
1382 return L.lt_set(R);
1383 case ICmpInst::ICMP_UGT:
1384 return L.gt_set(R);
1385 case ICmpInst::ICMP_ULE:
1386 return L.le_set(R);
1387 case ICmpInst::ICMP_UGE:
1388 return L.ge_set(R);
1389 default:
1390 llvm_unreachable("Non integer predicate not supported")::llvm::llvm_unreachable_internal("Non integer predicate not supported"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1390)
;
1391 }
1392}
1393
1394/// Compute the isl representation for the SCEV @p E in this BB.
1395///
1396/// @param S The Scop in which @p BB resides in.
1397/// @param BB The BB for which isl representation is to be
1398/// computed.
1399/// @param InvalidDomainMap A map of BB to their invalid domains.
1400/// @param E The SCEV that should be translated.
1401/// @param NonNegative Flag to indicate the @p E has to be non-negative.
1402///
1403/// Note that this function will also adjust the invalid context accordingly.
1404
1405__isl_give isl_pw_aff *
1406getPwAff(Scop &S, BasicBlock *BB,
1407 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap, const SCEV *E,
1408 bool NonNegative = false) {
1409 PWACtx PWAC = S.getPwAff(E, BB, NonNegative);
1410 InvalidDomainMap[BB] = InvalidDomainMap[BB].unite(PWAC.second);
1411 return PWAC.first.release();
1412}
1413
1414/// Build the conditions sets for the switch @p SI in the @p Domain.
1415///
1416/// This will fill @p ConditionSets with the conditions under which control
1417/// will be moved from @p SI to its successors. Hence, @p ConditionSets will
1418/// have as many elements as @p SI has successors.
1419bool buildConditionSets(Scop &S, BasicBlock *BB, SwitchInst *SI, Loop *L,
1420 __isl_keep isl_set *Domain,
1421 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
1422 SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
1423 Value *Condition = getConditionFromTerminator(SI);
1424 assert(Condition && "No condition for switch")((Condition && "No condition for switch") ? static_cast
<void> (0) : __assert_fail ("Condition && \"No condition for switch\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1424, __PRETTY_FUNCTION__))
;
1425
1426 ScalarEvolution &SE = *S.getSE();
1427 isl_pw_aff *LHS, *RHS;
1428 LHS = getPwAff(S, BB, InvalidDomainMap, SE.getSCEVAtScope(Condition, L));
1429
1430 unsigned NumSuccessors = SI->getNumSuccessors();
1431 ConditionSets.resize(NumSuccessors);
1432 for (auto &Case : SI->cases()) {
1433 unsigned Idx = Case.getSuccessorIndex();
1434 ConstantInt *CaseValue = Case.getCaseValue();
1435
1436 RHS = getPwAff(S, BB, InvalidDomainMap, SE.getSCEV(CaseValue));
1437 isl_set *CaseConditionSet =
1438 buildConditionSet(ICmpInst::ICMP_EQ, isl::manage_copy(LHS),
1439 isl::manage(RHS))
1440 .release();
1441 ConditionSets[Idx] = isl_set_coalesce(
1442 isl_set_intersect(CaseConditionSet, isl_set_copy(Domain)));
1443 }
1444
1445 assert(ConditionSets[0] == nullptr && "Default condition set was set")((ConditionSets[0] == nullptr && "Default condition set was set"
) ? static_cast<void> (0) : __assert_fail ("ConditionSets[0] == nullptr && \"Default condition set was set\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1445, __PRETTY_FUNCTION__))
;
1446 isl_set *ConditionSetUnion = isl_set_copy(ConditionSets[1]);
1447 for (unsigned u = 2; u < NumSuccessors; u++)
1448 ConditionSetUnion =
1449 isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u]));
1450 ConditionSets[0] = isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion);
1451
1452 isl_pw_aff_free(LHS);
1453
1454 return true;
1455}
1456
1457/// Build condition sets for unsigned ICmpInst(s).
1458/// Special handling is required for unsigned operands to ensure that if
1459/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst
1460/// it should wrap around.
1461///
1462/// @param IsStrictUpperBound holds information on the predicate relation
1463/// between TestVal and UpperBound, i.e,
1464/// TestVal < UpperBound OR TestVal <= UpperBound
1465__isl_give isl_set *
1466buildUnsignedConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
1467 __isl_keep isl_set *Domain, const SCEV *SCEV_TestVal,
1468 const SCEV *SCEV_UpperBound,
1469 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
1470 bool IsStrictUpperBound) {
1471 // Do not take NonNeg assumption on TestVal
1472 // as it might have MSB (Sign bit) set.
1473 isl_pw_aff *TestVal = getPwAff(S, BB, InvalidDomainMap, SCEV_TestVal, false);
1474 // Take NonNeg assumption on UpperBound.
1475 isl_pw_aff *UpperBound =
1476 getPwAff(S, BB, InvalidDomainMap, SCEV_UpperBound, true);
1477
1478 // 0 <= TestVal
1479 isl_set *First =
1480 isl_pw_aff_le_set(isl_pw_aff_zero_on_domain(isl_local_space_from_space(
1481 isl_pw_aff_get_domain_space(TestVal))),
1482 isl_pw_aff_copy(TestVal));
1483
1484 isl_set *Second;
1485 if (IsStrictUpperBound)
1486 // TestVal < UpperBound
1487 Second = isl_pw_aff_lt_set(TestVal, UpperBound);
1488 else
1489 // TestVal <= UpperBound
1490 Second = isl_pw_aff_le_set(TestVal, UpperBound);
1491
1492 isl_set *ConsequenceCondSet = isl_set_intersect(First, Second);
1493 return ConsequenceCondSet;
1494}
1495
1496/// Build the conditions sets for the branch condition @p Condition in
1497/// the @p Domain.
1498///
1499/// This will fill @p ConditionSets with the conditions under which control
1500/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
1501/// have as many elements as @p TI has successors. If @p TI is nullptr the
1502/// context under which @p Condition is true/false will be returned as the
1503/// new elements of @p ConditionSets.
1504bool buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
1505 Instruction *TI, Loop *L, __isl_keep isl_set *Domain,
1506 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
1507 SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
1508 ScalarEvolution &SE = *S.getSE();
1509 isl_set *ConsequenceCondSet = nullptr;
1510
1511 if (auto Load = dyn_cast<LoadInst>(Condition)) {
1512 const SCEV *LHSSCEV = SE.getSCEVAtScope(Load, L);
1513 const SCEV *RHSSCEV = SE.getZero(LHSSCEV->getType());
1514 bool NonNeg = false;
1515 isl_pw_aff *LHS = getPwAff(S, BB, InvalidDomainMap, LHSSCEV, NonNeg);
1516 isl_pw_aff *RHS = getPwAff(S, BB, InvalidDomainMap, RHSSCEV, NonNeg);
1517 ConsequenceCondSet = buildConditionSet(ICmpInst::ICMP_SLE, isl::manage(LHS),
1518 isl::manage(RHS))
1519 .release();
1520 } else if (auto *PHI = dyn_cast<PHINode>(Condition)) {
1521 auto *Unique = dyn_cast<ConstantInt>(
1522 getUniqueNonErrorValue(PHI, &S.getRegion(), *S.getLI(), *S.getDT()));
1523
1524 if (Unique->isZero())
1525 ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
1526 else
1527 ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
1528 } else if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {
1529 if (CCond->isZero())
1530 ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
1531 else
1532 ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
1533 } else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {
1534 auto Opcode = BinOp->getOpcode();
1535 assert(Opcode == Instruction::And || Opcode == Instruction::Or)((Opcode == Instruction::And || Opcode == Instruction::Or) ? static_cast
<void> (0) : __assert_fail ("Opcode == Instruction::And || Opcode == Instruction::Or"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1535, __PRETTY_FUNCTION__))
;
1536
1537 bool Valid = buildConditionSets(S, BB, BinOp->getOperand(0), TI, L, Domain,
1538 InvalidDomainMap, ConditionSets) &&
1539 buildConditionSets(S, BB, BinOp->getOperand(1), TI, L, Domain,
1540 InvalidDomainMap, ConditionSets);
1541 if (!Valid) {
1542 while (!ConditionSets.empty())
1543 isl_set_free(ConditionSets.pop_back_val());
1544 return false;
1545 }
1546
1547 isl_set_free(ConditionSets.pop_back_val());
1548 isl_set *ConsCondPart0 = ConditionSets.pop_back_val();
1549 isl_set_free(ConditionSets.pop_back_val());
1550 isl_set *ConsCondPart1 = ConditionSets.pop_back_val();
1551
1552 if (Opcode == Instruction::And)
1553 ConsequenceCondSet = isl_set_intersect(ConsCondPart0, ConsCondPart1);
1554 else
1555 ConsequenceCondSet = isl_set_union(ConsCondPart0, ConsCondPart1);
1556 } else {
1557 auto *ICond = dyn_cast<ICmpInst>(Condition);
1558 assert(ICond &&((ICond && "Condition of exiting branch was neither constant nor ICmp!"
) ? static_cast<void> (0) : __assert_fail ("ICond && \"Condition of exiting branch was neither constant nor ICmp!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1559, __PRETTY_FUNCTION__))
1559 "Condition of exiting branch was neither constant nor ICmp!")((ICond && "Condition of exiting branch was neither constant nor ICmp!"
) ? static_cast<void> (0) : __assert_fail ("ICond && \"Condition of exiting branch was neither constant nor ICmp!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1559, __PRETTY_FUNCTION__))
;
1560
1561 LoopInfo &LI = *S.getLI();
1562 DominatorTree &DT = *S.getDT();
1563 Region &R = S.getRegion();
1564
1565 isl_pw_aff *LHS, *RHS;
1566 // For unsigned comparisons we assumed the signed bit of neither operand
1567 // to be set. The comparison is equal to a signed comparison under this
1568 // assumption.
1569 bool NonNeg = ICond->isUnsigned();
1570 const SCEV *LeftOperand = SE.getSCEVAtScope(ICond->getOperand(0), L),
1571 *RightOperand = SE.getSCEVAtScope(ICond->getOperand(1), L);
1572
1573 LeftOperand = tryForwardThroughPHI(LeftOperand, R, SE, LI, DT);
1574 RightOperand = tryForwardThroughPHI(RightOperand, R, SE, LI, DT);
1575
1576 switch (ICond->getPredicate()) {
1577 case ICmpInst::ICMP_ULT:
1578 ConsequenceCondSet =
1579 buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand,
1580 RightOperand, InvalidDomainMap, true);
1581 break;
1582 case ICmpInst::ICMP_ULE:
1583 ConsequenceCondSet =
1584 buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand,
1585 RightOperand, InvalidDomainMap, false);
1586 break;
1587 case ICmpInst::ICMP_UGT:
1588 ConsequenceCondSet =
1589 buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand,
1590 LeftOperand, InvalidDomainMap, true);
1591 break;
1592 case ICmpInst::ICMP_UGE:
1593 ConsequenceCondSet =
1594 buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand,
1595 LeftOperand, InvalidDomainMap, false);
1596 break;
1597 default:
1598 LHS = getPwAff(S, BB, InvalidDomainMap, LeftOperand, NonNeg);
1599 RHS = getPwAff(S, BB, InvalidDomainMap, RightOperand, NonNeg);
1600 ConsequenceCondSet = buildConditionSet(ICond->getPredicate(),
1601 isl::manage(LHS), isl::manage(RHS))
1602 .release();
1603 break;
1604 }
1605 }
1606
1607 // If no terminator was given we are only looking for parameter constraints
1608 // under which @p Condition is true/false.
1609 if (!TI)
1610 ConsequenceCondSet = isl_set_params(ConsequenceCondSet);
1611 assert(ConsequenceCondSet)((ConsequenceCondSet) ? static_cast<void> (0) : __assert_fail
("ConsequenceCondSet", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1611, __PRETTY_FUNCTION__))
;
1612 ConsequenceCondSet = isl_set_coalesce(
1613 isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain)));
1614
1615 isl_set *AlternativeCondSet = nullptr;
1616 bool TooComplex =
1617 isl_set_n_basic_set(ConsequenceCondSet) >= MaxDisjunctsInDomain;
1618
1619 if (!TooComplex) {
1620 AlternativeCondSet = isl_set_subtract(isl_set_copy(Domain),
1621 isl_set_copy(ConsequenceCondSet));
1622 TooComplex =
1623 isl_set_n_basic_set(AlternativeCondSet) >= MaxDisjunctsInDomain;
1624 }
1625
1626 if (TooComplex) {
1627 S.invalidate(COMPLEXITY, TI ? TI->getDebugLoc() : DebugLoc(),
1628 TI ? TI->getParent() : nullptr /* BasicBlock */);
1629 isl_set_free(AlternativeCondSet);
1630 isl_set_free(ConsequenceCondSet);
1631 return false;
1632 }
1633
1634 ConditionSets.push_back(ConsequenceCondSet);
1635 ConditionSets.push_back(isl_set_coalesce(AlternativeCondSet));
1636
1637 return true;
1638}
1639
1640/// Build the conditions sets for the terminator @p TI in the @p Domain.
1641///
1642/// This will fill @p ConditionSets with the conditions under which control
1643/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
1644/// have as many elements as @p TI has successors.
1645bool buildConditionSets(Scop &S, BasicBlock *BB, Instruction *TI, Loop *L,
1646 __isl_keep isl_set *Domain,
1647 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
1648 SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
1649 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
1650 return buildConditionSets(S, BB, SI, L, Domain, InvalidDomainMap,
1651 ConditionSets);
1652
1653 assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.")((isa<BranchInst>(TI) && "Terminator was neither branch nor switch."
) ? static_cast<void> (0) : __assert_fail ("isa<BranchInst>(TI) && \"Terminator was neither branch nor switch.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1653, __PRETTY_FUNCTION__))
;
1654
1655 if (TI->getNumSuccessors() == 1) {
1656 ConditionSets.push_back(isl_set_copy(Domain));
1657 return true;
1658 }
1659
1660 Value *Condition = getConditionFromTerminator(TI);
1661 assert(Condition && "No condition for Terminator")((Condition && "No condition for Terminator") ? static_cast
<void> (0) : __assert_fail ("Condition && \"No condition for Terminator\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1661, __PRETTY_FUNCTION__))
;
1662
1663 return buildConditionSets(S, BB, Condition, TI, L, Domain, InvalidDomainMap,
1664 ConditionSets);
1665}
1666
1667ScopStmt::ScopStmt(Scop &parent, Region &R, StringRef Name,
1668 Loop *SurroundingLoop,
1669 std::vector<Instruction *> EntryBlockInstructions)
1670 : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), R(&R),
1671 Build(nullptr), BaseName(Name), SurroundingLoop(SurroundingLoop),
1672 Instructions(EntryBlockInstructions) {}
1673
1674ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, StringRef Name,
1675 Loop *SurroundingLoop,
1676 std::vector<Instruction *> Instructions)
1677 : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(&bb),
1678 Build(nullptr), BaseName(Name), SurroundingLoop(SurroundingLoop),
1679 Instructions(Instructions) {}
1680
1681ScopStmt::ScopStmt(Scop &parent, isl::map SourceRel, isl::map TargetRel,
1682 isl::set NewDomain)
1683 : Parent(parent), InvalidDomain(nullptr), Domain(NewDomain),
1684 Build(nullptr) {
1685 BaseName = getIslCompatibleName("CopyStmt_", "",
1686 std::to_string(parent.getCopyStmtsNum()));
1687 isl::id Id = isl::id::alloc(getIslCtx(), getBaseName(), this);
1688 Domain = Domain.set_tuple_id(Id);
1689 TargetRel = TargetRel.set_tuple_id(isl::dim::in, Id);
1690 auto *Access =
1691 new MemoryAccess(this, MemoryAccess::AccessType::MUST_WRITE, TargetRel);
1692 parent.addAccessFunction(Access);
1693 addAccess(Access);
1694 SourceRel = SourceRel.set_tuple_id(isl::dim::in, Id);
1695 Access = new MemoryAccess(this, MemoryAccess::AccessType::READ, SourceRel);
1696 parent.addAccessFunction(Access);
1697 addAccess(Access);
1698}
1699
1700ScopStmt::~ScopStmt() = default;
1701
1702std::string ScopStmt::getDomainStr() const { return Domain.to_str(); }
1703
1704std::string ScopStmt::getScheduleStr() const {
1705 auto *S = getSchedule().release();
1706 if (!S)
1707 return {};
1708 auto Str = stringFromIslObj(S);
1709 isl_map_free(S);
1710 return Str;
1711}
1712
1713void ScopStmt::setInvalidDomain(isl::set ID) { InvalidDomain = ID; }
1714
1715BasicBlock *ScopStmt::getEntryBlock() const {
1716 if (isBlockStmt())
1717 return getBasicBlock();
1718 return getRegion()->getEntry();
1719}
1720
1721unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); }
1722
1723const char *ScopStmt::getBaseName() const { return BaseName.c_str(); }
1724
1725Loop *ScopStmt::getLoopForDimension(unsigned Dimension) const {
1726 return NestLoops[Dimension];
1727}
1728
1729isl::ctx ScopStmt::getIslCtx() const { return Parent.getIslCtx(); }
1730
1731isl::set ScopStmt::getDomain() const { return Domain; }
1732
1733isl::space ScopStmt::getDomainSpace() const { return Domain.get_space(); }
1734
1735isl::id ScopStmt::getDomainId() const { return Domain.get_tuple_id(); }
1736
1737void ScopStmt::printInstructions(raw_ostream &OS) const {
1738 OS << "Instructions {\n";
1739
1740 for (Instruction *Inst : Instructions)
1741 OS.indent(16) << *Inst << "\n";
1742
1743 OS.indent(12) << "}\n";
1744}
1745
1746void ScopStmt::print(raw_ostream &OS, bool PrintInstructions) const {
1747 OS << "\t" << getBaseName() << "\n";
1748 OS.indent(12) << "Domain :=\n";
1749
1750 if (Domain) {
1751 OS.indent(16) << getDomainStr() << ";\n";
1752 } else
1753 OS.indent(16) << "n/a\n";
1754
1755 OS.indent(12) << "Schedule :=\n";
1756
1757 if (Domain) {
1758 OS.indent(16) << getScheduleStr() << ";\n";
1759 } else
1760 OS.indent(16) << "n/a\n";
1761
1762 for (MemoryAccess *Access : MemAccs)
1763 Access->print(OS);
1764
1765 if (PrintInstructions)
1766 printInstructions(OS.indent(12));
1767}
1768
1769#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1770LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void ScopStmt::dump() const { print(dbgs(), true); }
1771#endif
1772
1773void ScopStmt::removeAccessData(MemoryAccess *MA) {
1774 if (MA->isRead() && MA->isOriginalValueKind()) {
1775 bool Found = ValueReads.erase(MA->getAccessValue());
1776 (void)Found;
1777 assert(Found && "Expected access data not found")((Found && "Expected access data not found") ? static_cast
<void> (0) : __assert_fail ("Found && \"Expected access data not found\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1777, __PRETTY_FUNCTION__))
;
1778 }
1779 if (MA->isWrite() && MA->isOriginalValueKind()) {
1780 bool Found = ValueWrites.erase(cast<Instruction>(MA->getAccessValue()));
1781 (void)Found;
1782 assert(Found && "Expected access data not found")((Found && "Expected access data not found") ? static_cast
<void> (0) : __assert_fail ("Found && \"Expected access data not found\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1782, __PRETTY_FUNCTION__))
;
1783 }
1784 if (MA->isWrite() && MA->isOriginalAnyPHIKind()) {
1785 bool Found = PHIWrites.erase(cast<PHINode>(MA->getAccessInstruction()));
1786 (void)Found;
1787 assert(Found && "Expected access data not found")((Found && "Expected access data not found") ? static_cast
<void> (0) : __assert_fail ("Found && \"Expected access data not found\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1787, __PRETTY_FUNCTION__))
;
1788 }
1789 if (MA->isRead() && MA->isOriginalAnyPHIKind()) {
1790 bool Found = PHIReads.erase(cast<PHINode>(MA->getAccessInstruction()));
1791 (void)Found;
1792 assert(Found && "Expected access data not found")((Found && "Expected access data not found") ? static_cast
<void> (0) : __assert_fail ("Found && \"Expected access data not found\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1792, __PRETTY_FUNCTION__))
;
1793 }
1794}
1795
1796void ScopStmt::removeMemoryAccess(MemoryAccess *MA) {
1797 // Remove the memory accesses from this statement together with all scalar
1798 // accesses that were caused by it. MemoryKind::Value READs have no access
1799 // instruction, hence would not be removed by this function. However, it is
1800 // only used for invariant LoadInst accesses, its arguments are always affine,
1801 // hence synthesizable, and therefore there are no MemoryKind::Value READ
1802 // accesses to be removed.
1803 auto Predicate = [&](MemoryAccess *Acc) {
1804 return Acc->getAccessInstruction() == MA->getAccessInstruction();
1805 };
1806 for (auto *MA : MemAccs) {
1807 if (Predicate(MA)) {
1808 removeAccessData(MA);
1809 Parent.removeAccessData(MA);
1810 }
1811 }
1812 MemAccs.erase(std::remove_if(MemAccs.begin(), MemAccs.end(), Predicate),
1813 MemAccs.end());
1814 InstructionToAccess.erase(MA->getAccessInstruction());
1815}
1816
1817void ScopStmt::removeSingleMemoryAccess(MemoryAccess *MA, bool AfterHoisting) {
1818 if (AfterHoisting) {
1819 auto MAIt = std::find(MemAccs.begin(), MemAccs.end(), MA);
1820 assert(MAIt != MemAccs.end())((MAIt != MemAccs.end()) ? static_cast<void> (0) : __assert_fail
("MAIt != MemAccs.end()", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1820, __PRETTY_FUNCTION__))
;
1821 MemAccs.erase(MAIt);
1822
1823 removeAccessData(MA);
1824 Parent.removeAccessData(MA);
1825 }
1826
1827 auto It = InstructionToAccess.find(MA->getAccessInstruction());
1828 if (It != InstructionToAccess.end()) {
1829 It->second.remove(MA);
1830 if (It->second.empty())
1831 InstructionToAccess.erase(MA->getAccessInstruction());
1832 }
1833}
1834
1835MemoryAccess *ScopStmt::ensureValueRead(Value *V) {
1836 MemoryAccess *Access = lookupInputAccessOf(V);
1837 if (Access)
1838 return Access;
1839
1840 ScopArrayInfo *SAI =
1841 Parent.getOrCreateScopArrayInfo(V, V->getType(), {}, MemoryKind::Value);
1842 Access = new MemoryAccess(this, nullptr, MemoryAccess::READ, V, V->getType(),
1843 true, {}, {}, V, MemoryKind::Value);
1844 Parent.addAccessFunction(Access);
1845 Access->buildAccessRelation(SAI);
1846 addAccess(Access);
1847 Parent.addAccessData(Access);
1848 return Access;
1849}
1850
1851raw_ostream &polly::operator<<(raw_ostream &OS, const ScopStmt &S) {
1852 S.print(OS, PollyPrintInstructions);
1853 return OS;
1854}
1855
1856//===----------------------------------------------------------------------===//
1857/// Scop class implement
1858
1859void Scop::setContext(isl::set NewContext) {
1860 Context = NewContext.align_params(Context.get_space());
1861}
1862
1863namespace {
1864
1865/// Remap parameter values but keep AddRecs valid wrt. invariant loads.
1866struct SCEVSensitiveParameterRewriter
1867 : public SCEVRewriteVisitor<SCEVSensitiveParameterRewriter> {
1868 const ValueToValueMap &VMap;
1869
1870public:
1871 SCEVSensitiveParameterRewriter(const ValueToValueMap &VMap,
1872 ScalarEvolution &SE)
1873 : SCEVRewriteVisitor(SE), VMap(VMap) {}
1874
1875 static const SCEV *rewrite(const SCEV *E, ScalarEvolution &SE,
1876 const ValueToValueMap &VMap) {
1877 SCEVSensitiveParameterRewriter SSPR(VMap, SE);
1878 return SSPR.visit(E);
1879 }
1880
1881 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
1882 auto *Start = visit(E->getStart());
1883 auto *AddRec = SE.getAddRecExpr(SE.getConstant(E->getType(), 0),
1884 visit(E->getStepRecurrence(SE)),
1885 E->getLoop(), SCEV::FlagAnyWrap);
1886 return SE.getAddExpr(Start, AddRec);
1887 }
1888
1889 const SCEV *visitUnknown(const SCEVUnknown *E) {
1890 if (auto *NewValue = VMap.lookup(E->getValue()))
1891 return SE.getUnknown(NewValue);
1892 return E;
1893 }
1894};
1895
1896/// Check whether we should remap a SCEV expression.
1897struct SCEVFindInsideScop : public SCEVTraversal<SCEVFindInsideScop> {
1898 const ValueToValueMap &VMap;
1899 bool FoundInside = false;
1900 const Scop *S;
1901
1902public:
1903 SCEVFindInsideScop(const ValueToValueMap &VMap, ScalarEvolution &SE,
1904 const Scop *S)
1905 : SCEVTraversal(*this), VMap(VMap), S(S) {}
1906
1907 static bool hasVariant(const SCEV *E, ScalarEvolution &SE,
1908 const ValueToValueMap &VMap, const Scop *S) {
1909 SCEVFindInsideScop SFIS(VMap, SE, S);
1910 SFIS.visitAll(E);
1911 return SFIS.FoundInside;
1912 }
1913
1914 bool follow(const SCEV *E) {
1915 if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(E)) {
1916 FoundInside |= S->getRegion().contains(AddRec->getLoop());
1917 } else if (auto *Unknown = dyn_cast<SCEVUnknown>(E)) {
1918 if (Instruction *I = dyn_cast<Instruction>(Unknown->getValue()))
1919 FoundInside |= S->getRegion().contains(I) && !VMap.count(I);
1920 }
1921 return !FoundInside;
1922 }
1923
1924 bool isDone() { return FoundInside; }
1925};
1926} // end anonymous namespace
1927
1928const SCEV *Scop::getRepresentingInvariantLoadSCEV(const SCEV *E) const {
1929 // Check whether it makes sense to rewrite the SCEV. (ScalarEvolution
1930 // doesn't like addition between an AddRec and an expression that
1931 // doesn't have a dominance relationship with it.)
1932 if (SCEVFindInsideScop::hasVariant(E, *SE, InvEquivClassVMap, this))
1933 return E;
1934
1935 // Rewrite SCEV.
1936 return SCEVSensitiveParameterRewriter::rewrite(E, *SE, InvEquivClassVMap);
1937}
1938
1939// This table of function names is used to translate parameter names in more
1940// human-readable names. This makes it easier to interpret Polly analysis
1941// results.
1942StringMap<std::string> KnownNames = {
1943 {"_Z13get_global_idj", "global_id"},
1944 {"_Z12get_local_idj", "local_id"},
1945 {"_Z15get_global_sizej", "global_size"},
1946 {"_Z14get_local_sizej", "local_size"},
1947 {"_Z12get_work_dimv", "work_dim"},
1948 {"_Z17get_global_offsetj", "global_offset"},
1949 {"_Z12get_group_idj", "group_id"},
1950 {"_Z14get_num_groupsj", "num_groups"},
1951};
1952
1953static std::string getCallParamName(CallInst *Call) {
1954 std::string Result;
1955 raw_string_ostream OS(Result);
1956 std::string Name = Call->getCalledFunction()->getName();
1957
1958 auto Iterator = KnownNames.find(Name);
1959 if (Iterator != KnownNames.end())
1960 Name = "__" + Iterator->getValue();
1961 OS << Name;
1962 for (auto &Operand : Call->arg_operands()) {
1963 ConstantInt *Op = cast<ConstantInt>(&Operand);
1964 OS << "_" << Op->getValue();
1965 }
1966 OS.flush();
1967 return Result;
1968}
1969
1970void Scop::createParameterId(const SCEV *Parameter) {
1971 assert(Parameters.count(Parameter))((Parameters.count(Parameter)) ? static_cast<void> (0) :
__assert_fail ("Parameters.count(Parameter)", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1971, __PRETTY_FUNCTION__))
;
1972 assert(!ParameterIds.count(Parameter))((!ParameterIds.count(Parameter)) ? static_cast<void> (
0) : __assert_fail ("!ParameterIds.count(Parameter)", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 1972, __PRETTY_FUNCTION__))
;
1973
1974 std::string ParameterName = "p_" + std::to_string(getNumParams() - 1);
1975
1976 if (const SCEVUnknown *ValueParameter = dyn_cast<SCEVUnknown>(Parameter)) {
1977 Value *Val = ValueParameter->getValue();
1978 CallInst *Call = dyn_cast<CallInst>(Val);
1979
1980 if (Call && isConstCall(Call)) {
1981 ParameterName = getCallParamName(Call);
1982 } else if (UseInstructionNames) {
1983 // If this parameter references a specific Value and this value has a name
1984 // we use this name as it is likely to be unique and more useful than just
1985 // a number.
1986 if (Val->hasName())
1987 ParameterName = Val->getName();
1988 else if (LoadInst *LI = dyn_cast<LoadInst>(Val)) {
1989 auto *LoadOrigin = LI->getPointerOperand()->stripInBoundsOffsets();
1990 if (LoadOrigin->hasName()) {
1991 ParameterName += "_loaded_from_";
1992 ParameterName +=
1993 LI->getPointerOperand()->stripInBoundsOffsets()->getName();
1994 }
1995 }
1996 }
1997
1998 ParameterName = getIslCompatibleName("", ParameterName, "");
1999 }
2000
2001 isl::id Id = isl::id::alloc(getIslCtx(), ParameterName,
2002 const_cast<void *>((const void *)Parameter));
2003 ParameterIds[Parameter] = Id;
2004}
2005
2006void Scop::addParams(const ParameterSetTy &NewParameters) {
2007 for (const SCEV *Parameter : NewParameters) {
2008 // Normalize the SCEV to get the representing element for an invariant load.
2009 Parameter = extractConstantFactor(Parameter, *SE).second;
2010 Parameter = getRepresentingInvariantLoadSCEV(Parameter);
2011
2012 if (Parameters.insert(Parameter))
2013 createParameterId(Parameter);
2014 }
2015}
2016
2017isl::id Scop::getIdForParam(const SCEV *Parameter) const {
2018 // Normalize the SCEV to get the representing element for an invariant load.
2019 Parameter = getRepresentingInvariantLoadSCEV(Parameter);
2020 return ParameterIds.lookup(Parameter);
2021}
2022
2023isl::set Scop::addNonEmptyDomainConstraints(isl::set C) const {
2024 isl::set DomainContext = getDomains().params();
2025 return C.intersect_params(DomainContext);
2026}
2027
2028bool Scop::isDominatedBy(const DominatorTree &DT, BasicBlock *BB) const {
2029 return DT.dominates(BB, getEntry());
2030}
2031
2032void Scop::addUserAssumptions(
2033 AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI,
2034 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
2035 for (auto &Assumption : AC.assumptions()) {
2036 auto *CI = dyn_cast_or_null<CallInst>(Assumption);
2037 if (!CI || CI->getNumArgOperands() != 1)
2038 continue;
2039
2040 bool InScop = contains(CI);
2041 if (!InScop && !isDominatedBy(DT, CI->getParent()))
2042 continue;
2043
2044 auto *L = LI.getLoopFor(CI->getParent());
2045 auto *Val = CI->getArgOperand(0);
2046 ParameterSetTy DetectedParams;
2047 if (!isAffineConstraint(Val, &R, L, *SE, DetectedParams)) {
2048 ORE.emit(
2049 OptimizationRemarkAnalysis(DEBUG_TYPE"polly-scops", "IgnoreUserAssumption", CI)
2050 << "Non-affine user assumption ignored.");
2051 continue;
2052 }
2053
2054 // Collect all newly introduced parameters.
2055 ParameterSetTy NewParams;
2056 for (auto *Param : DetectedParams) {
2057 Param = extractConstantFactor(Param, *SE).second;
2058 Param = getRepresentingInvariantLoadSCEV(Param);
2059 if (Parameters.count(Param))
2060 continue;
2061 NewParams.insert(Param);
2062 }
2063
2064 SmallVector<isl_set *, 2> ConditionSets;
2065 auto *TI = InScop ? CI->getParent()->getTerminator() : nullptr;
2066 BasicBlock *BB = InScop ? CI->getParent() : getRegion().getEntry();
2067 auto *Dom = InScop ? DomainMap[BB].copy() : Context.copy();
2068 assert(Dom && "Cannot propagate a nullptr.")((Dom && "Cannot propagate a nullptr.") ? static_cast
<void> (0) : __assert_fail ("Dom && \"Cannot propagate a nullptr.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2068, __PRETTY_FUNCTION__))
;
2069 bool Valid = buildConditionSets(*this, BB, Val, TI, L, Dom,
2070 InvalidDomainMap, ConditionSets);
2071 isl_set_free(Dom);
2072
2073 if (!Valid)
2074 continue;
2075
2076 isl_set *AssumptionCtx = nullptr;
2077 if (InScop) {
2078 AssumptionCtx = isl_set_complement(isl_set_params(ConditionSets[1]));
2079 isl_set_free(ConditionSets[0]);
2080 } else {
2081 AssumptionCtx = isl_set_complement(ConditionSets[1]);
2082 AssumptionCtx = isl_set_intersect(AssumptionCtx, ConditionSets[0]);
2083 }
2084
2085 // Project out newly introduced parameters as they are not otherwise useful.
2086 if (!NewParams.empty()) {
2087 for (unsigned u = 0; u < isl_set_n_param(AssumptionCtx); u++) {
2088 auto *Id = isl_set_get_dim_id(AssumptionCtx, isl_dim_param, u);
2089 auto *Param = static_cast<const SCEV *>(isl_id_get_user(Id));
2090 isl_id_free(Id);
2091
2092 if (!NewParams.count(Param))
2093 continue;
2094
2095 AssumptionCtx =
2096 isl_set_project_out(AssumptionCtx, isl_dim_param, u--, 1);
2097 }
2098 }
2099 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE"polly-scops", "UserAssumption", CI)
2100 << "Use user assumption: " << stringFromIslObj(AssumptionCtx));
2101 Context = Context.intersect(isl::manage(AssumptionCtx));
2102 }
2103}
2104
2105void Scop::addUserContext() {
2106 if (UserContextStr.empty())
2107 return;
2108
2109 isl::set UserContext = isl::set(getIslCtx(), UserContextStr.c_str());
2110 isl::space Space = getParamSpace();
2111 if (Space.dim(isl::dim::param) != UserContext.dim(isl::dim::param)) {
2112 std::string SpaceStr = Space.to_str();
2113 errs() << "Error: the context provided in -polly-context has not the same "
2114 << "number of dimensions than the computed context. Due to this "
2115 << "mismatch, the -polly-context option is ignored. Please provide "
2116 << "the context in the parameter space: " << SpaceStr << ".\n";
2117 return;
2118 }
2119
2120 for (unsigned i = 0; i < Space.dim(isl::dim::param); i++) {
2121 std::string NameContext = Context.get_dim_name(isl::dim::param, i);
2122 std::string NameUserContext = UserContext.get_dim_name(isl::dim::param, i);
2123
2124 if (NameContext != NameUserContext) {
2125 std::string SpaceStr = Space.to_str();
2126 errs() << "Error: the name of dimension " << i
2127 << " provided in -polly-context "
2128 << "is '" << NameUserContext << "', but the name in the computed "
2129 << "context is '" << NameContext
2130 << "'. Due to this name mismatch, "
2131 << "the -polly-context option is ignored. Please provide "
2132 << "the context in the parameter space: " << SpaceStr << ".\n";
2133 return;
2134 }
2135
2136 UserContext = UserContext.set_dim_id(isl::dim::param, i,
2137 Space.get_dim_id(isl::dim::param, i));
2138 }
2139
2140 Context = Context.intersect(UserContext);
2141}
2142
2143void Scop::buildInvariantEquivalenceClasses() {
2144 DenseMap<std::pair<const SCEV *, Type *>, LoadInst *> EquivClasses;
2145
2146 const InvariantLoadsSetTy &RIL = getRequiredInvariantLoads();
2147 for (LoadInst *LInst : RIL) {
2148 const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
2149
2150 Type *Ty = LInst->getType();
2151 LoadInst *&ClassRep = EquivClasses[std::make_pair(PointerSCEV, Ty)];
2152 if (ClassRep) {
2153 InvEquivClassVMap[LInst] = ClassRep;
2154 continue;
2155 }
2156
2157 ClassRep = LInst;
2158 InvariantEquivClasses.emplace_back(
2159 InvariantEquivClassTy{PointerSCEV, MemoryAccessList(), nullptr, Ty});
2160 }
2161}
2162
2163void Scop::buildContext() {
2164 isl::space Space = isl::space::params_alloc(getIslCtx(), 0);
2165 Context = isl::set::universe(Space);
2166 InvalidContext = isl::set::empty(Space);
2167 AssumedContext = isl::set::universe(Space);
2168}
2169
2170void Scop::addParameterBounds() {
2171 unsigned PDim = 0;
2172 for (auto *Parameter : Parameters) {
2173 ConstantRange SRange = SE->getSignedRange(Parameter);
2174 Context = addRangeBoundsToSet(Context, SRange, PDim++, isl::dim::param);
2175 }
2176}
2177
2178static std::vector<isl::id> getFortranArrayIds(Scop::array_range Arrays) {
2179 std::vector<isl::id> OutermostSizeIds;
2180 for (auto Array : Arrays) {
2181 // To check if an array is a Fortran array, we check if it has a isl_pw_aff
2182 // for its outermost dimension. Fortran arrays will have this since the
2183 // outermost dimension size can be picked up from their runtime description.
2184 // TODO: actually need to check if it has a FAD, but for now this works.
2185 if (Array->getNumberOfDimensions() > 0) {
2186 isl::pw_aff PwAff = Array->getDimensionSizePw(0);
2187 if (!PwAff)
2188 continue;
2189
2190 isl::id Id = PwAff.get_dim_id(isl::dim::param, 0);
2191 assert(!Id.is_null() &&((!Id.is_null() && "Invalid Id for PwAff expression in Fortran array"
) ? static_cast<void> (0) : __assert_fail ("!Id.is_null() && \"Invalid Id for PwAff expression in Fortran array\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2192, __PRETTY_FUNCTION__))
2192 "Invalid Id for PwAff expression in Fortran array")((!Id.is_null() && "Invalid Id for PwAff expression in Fortran array"
) ? static_cast<void> (0) : __assert_fail ("!Id.is_null() && \"Invalid Id for PwAff expression in Fortran array\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2192, __PRETTY_FUNCTION__))
;
2193 OutermostSizeIds.push_back(Id);
2194 }
2195 }
2196 return OutermostSizeIds;
2197}
2198
2199// The FORTRAN array size parameters are known to be non-negative.
2200static isl::set boundFortranArrayParams(isl::set Context,
2201 Scop::array_range Arrays) {
2202 std::vector<isl::id> OutermostSizeIds;
2203 OutermostSizeIds = getFortranArrayIds(Arrays);
2204
2205 for (isl::id Id : OutermostSizeIds) {
2206 int dim = Context.find_dim_by_id(isl::dim::param, Id);
2207 Context = Context.lower_bound_si(isl::dim::param, dim, 0);
2208 }
2209
2210 return Context;
2211}
2212
2213void Scop::realignParams() {
2214 if (PollyIgnoreParamBounds)
2215 return;
2216
2217 // Add all parameters into a common model.
2218 isl::space Space = getFullParamSpace();
2219
2220 // Align the parameters of all data structures to the model.
2221 Context = Context.align_params(Space);
2222
2223 // Bound the size of the fortran array dimensions.
2224 Context = boundFortranArrayParams(Context, arrays());
2225
2226 // As all parameters are known add bounds to them.
2227 addParameterBounds();
2228
2229 for (ScopStmt &Stmt : *this)
2230 Stmt.realignParams();
2231 // Simplify the schedule according to the context too.
2232 Schedule = Schedule.gist_domain_params(getContext());
2233}
2234
2235static isl::set simplifyAssumptionContext(isl::set AssumptionContext,
2236 const Scop &S) {
2237 // If we have modeled all blocks in the SCoP that have side effects we can
2238 // simplify the context with the constraints that are needed for anything to
2239 // be executed at all. However, if we have error blocks in the SCoP we already
2240 // assumed some parameter combinations cannot occur and removed them from the
2241 // domains, thus we cannot use the remaining domain to simplify the
2242 // assumptions.
2243 if (!S.hasErrorBlock()) {
2244 auto DomainParameters = S.getDomains().params();
2245 AssumptionContext = AssumptionContext.gist_params(DomainParameters);
2246 }
2247
2248 AssumptionContext = AssumptionContext.gist_params(S.getContext());
2249 return AssumptionContext;
2250}
2251
2252void Scop::simplifyContexts() {
2253 // The parameter constraints of the iteration domains give us a set of
2254 // constraints that need to hold for all cases where at least a single
2255 // statement iteration is executed in the whole scop. We now simplify the
2256 // assumed context under the assumption that such constraints hold and at
2257 // least a single statement iteration is executed. For cases where no
2258 // statement instances are executed, the assumptions we have taken about
2259 // the executed code do not matter and can be changed.
2260 //
2261 // WARNING: This only holds if the assumptions we have taken do not reduce
2262 // the set of statement instances that are executed. Otherwise we
2263 // may run into a case where the iteration domains suggest that
2264 // for a certain set of parameter constraints no code is executed,
2265 // but in the original program some computation would have been
2266 // performed. In such a case, modifying the run-time conditions and
2267 // possibly influencing the run-time check may cause certain scops
2268 // to not be executed.
2269 //
2270 // Example:
2271 //
2272 // When delinearizing the following code:
2273 //
2274 // for (long i = 0; i < 100; i++)
2275 // for (long j = 0; j < m; j++)
2276 // A[i+p][j] = 1.0;
2277 //
2278 // we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as
2279 // otherwise we would access out of bound data. Now, knowing that code is
2280 // only executed for the case m >= 0, it is sufficient to assume p >= 0.
2281 AssumedContext = simplifyAssumptionContext(AssumedContext, *this);
2282 InvalidContext = InvalidContext.align_params(getParamSpace());
2283}
2284
2285/// Add the minimal/maximal access in @p Set to @p User.
2286///
2287/// @return True if more accesses should be added, false if we reached the
2288/// maximal number of run-time checks to be generated.
2289static bool buildMinMaxAccess(isl::set Set,
2290 Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S) {
2291 isl::pw_multi_aff MinPMA, MaxPMA;
2292 isl::pw_aff LastDimAff;
2293 isl::aff OneAff;
2294 unsigned Pos;
2295
2296 Set = Set.remove_divs();
2297 polly::simplify(Set);
2298
2299 if (Set.n_basic_set() > RunTimeChecksMaxAccessDisjuncts)
2300 Set = Set.simple_hull();
2301
2302 // Restrict the number of parameters involved in the access as the lexmin/
2303 // lexmax computation will take too long if this number is high.
2304 //
2305 // Experiments with a simple test case using an i7 4800MQ:
2306 //
2307 // #Parameters involved | Time (in sec)
2308 // 6 | 0.01
2309 // 7 | 0.04
2310 // 8 | 0.12
2311 // 9 | 0.40
2312 // 10 | 1.54
2313 // 11 | 6.78
2314 // 12 | 30.38
2315 //
2316 if (isl_set_n_param(Set.get()) > RunTimeChecksMaxParameters) {
2317 unsigned InvolvedParams = 0;
2318 for (unsigned u = 0, e = isl_set_n_param(Set.get()); u < e; u++)
2319 if (Set.involves_dims(isl::dim::param, u, 1))
2320 InvolvedParams++;
2321
2322 if (InvolvedParams > RunTimeChecksMaxParameters)
2323 return false;
2324 }
2325
2326 MinPMA = Set.lexmin_pw_multi_aff();
2327 MaxPMA = Set.lexmax_pw_multi_aff();
2328
2329 MinPMA = MinPMA.coalesce();
2330 MaxPMA = MaxPMA.coalesce();
2331
2332 // Adjust the last dimension of the maximal access by one as we want to
2333 // enclose the accessed memory region by MinPMA and MaxPMA. The pointer
2334 // we test during code generation might now point after the end of the
2335 // allocated array but we will never dereference it anyway.
2336 assert((!MaxPMA || MaxPMA.dim(isl::dim::out)) &&(((!MaxPMA || MaxPMA.dim(isl::dim::out)) && "Assumed at least one output dimension"
) ? static_cast<void> (0) : __assert_fail ("(!MaxPMA || MaxPMA.dim(isl::dim::out)) && \"Assumed at least one output dimension\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2337, __PRETTY_FUNCTION__))
2337 "Assumed at least one output dimension")(((!MaxPMA || MaxPMA.dim(isl::dim::out)) && "Assumed at least one output dimension"
) ? static_cast<void> (0) : __assert_fail ("(!MaxPMA || MaxPMA.dim(isl::dim::out)) && \"Assumed at least one output dimension\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2337, __PRETTY_FUNCTION__))
;
2338
2339 Pos = MaxPMA.dim(isl::dim::out) - 1;
2340 LastDimAff = MaxPMA.get_pw_aff(Pos);
2341 OneAff = isl::aff(isl::local_space(LastDimAff.get_domain_space()));
2342 OneAff = OneAff.add_constant_si(1);
2343 LastDimAff = LastDimAff.add(OneAff);
2344 MaxPMA = MaxPMA.set_pw_aff(Pos, LastDimAff);
2345
2346 if (!MinPMA || !MaxPMA)
2347 return false;
2348
2349 MinMaxAccesses.push_back(std::make_pair(MinPMA, MaxPMA));
2350
2351 return true;
2352}
2353
2354static isl::set getAccessDomain(MemoryAccess *MA) {
2355 isl::set Domain = MA->getStatement()->getDomain();
2356 Domain = Domain.project_out(isl::dim::set, 0, Domain.n_dim());
2357 return Domain.reset_tuple_id();
2358}
2359
2360/// Wrapper function to calculate minimal/maximal accesses to each array.
2361static bool calculateMinMaxAccess(Scop::AliasGroupTy AliasGroup, Scop &S,
2362 Scop::MinMaxVectorTy &MinMaxAccesses) {
2363 MinMaxAccesses.reserve(AliasGroup.size());
2364
2365 isl::union_set Domains = S.getDomains();
2366 isl::union_map Accesses = isl::union_map::empty(S.getParamSpace());
2367
2368 for (MemoryAccess *MA : AliasGroup)
2369 Accesses = Accesses.add_map(MA->getAccessRelation());
2370
2371 Accesses = Accesses.intersect_domain(Domains);
2372 isl::union_set Locations = Accesses.range();
2373
2374 bool LimitReached = false;
2375 for (isl::set Set : Locations.get_set_list()) {
2376 LimitReached |= !buildMinMaxAccess(Set, MinMaxAccesses, S);
2377 if (LimitReached)
2378 break;
2379 }
2380
2381 return !LimitReached;
2382}
2383
2384/// Helper to treat non-affine regions and basic blocks the same.
2385///
2386///{
2387
2388/// Return the block that is the representing block for @p RN.
2389static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
2390 return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
2391 : RN->getNodeAs<BasicBlock>();
2392}
2393
2394/// Return the @p idx'th block that is executed after @p RN.
2395static inline BasicBlock *
2396getRegionNodeSuccessor(RegionNode *RN, Instruction *TI, unsigned idx) {
2397 if (RN->isSubRegion()) {
2398 assert(idx == 0)((idx == 0) ? static_cast<void> (0) : __assert_fail ("idx == 0"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2398, __PRETTY_FUNCTION__))
;
2399 return RN->getNodeAs<Region>()->getExit();
2400 }
2401 return TI->getSuccessor(idx);
2402}
2403
2404/// Return the smallest loop surrounding @p RN.
2405static inline Loop *getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) {
2406 if (!RN->isSubRegion()) {
2407 BasicBlock *BB = RN->getNodeAs<BasicBlock>();
2408 Loop *L = LI.getLoopFor(BB);
2409
2410 // Unreachable statements are not considered to belong to a LLVM loop, as
2411 // they are not part of an actual loop in the control flow graph.
2412 // Nevertheless, we handle certain unreachable statements that are common
2413 // when modeling run-time bounds checks as being part of the loop to be
2414 // able to model them and to later eliminate the run-time bounds checks.
2415 //
2416 // Specifically, for basic blocks that terminate in an unreachable and
2417 // where the immediate predecessor is part of a loop, we assume these
2418 // basic blocks belong to the loop the predecessor belongs to. This
2419 // allows us to model the following code.
2420 //
2421 // for (i = 0; i < N; i++) {
2422 // if (i > 1024)
2423 // abort(); <- this abort might be translated to an
2424 // unreachable
2425 //
2426 // A[i] = ...
2427 // }
2428 if (!L && isa<UnreachableInst>(BB->getTerminator()) && BB->getPrevNode())
2429 L = LI.getLoopFor(BB->getPrevNode());
2430 return L;
2431 }
2432
2433 Region *NonAffineSubRegion = RN->getNodeAs<Region>();
2434 Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry());
2435 while (L && NonAffineSubRegion->contains(L))
2436 L = L->getParentLoop();
2437 return L;
2438}
2439
2440/// Get the number of blocks in @p L.
2441///
2442/// The number of blocks in a loop are the number of basic blocks actually
2443/// belonging to the loop, as well as all single basic blocks that the loop
2444/// exits to and which terminate in an unreachable instruction. We do not
2445/// allow such basic blocks in the exit of a scop, hence they belong to the
2446/// scop and represent run-time conditions which we want to model and
2447/// subsequently speculate away.
2448///
2449/// @see getRegionNodeLoop for additional details.
2450unsigned getNumBlocksInLoop(Loop *L) {
2451 unsigned NumBlocks = L->getNumBlocks();
2452 SmallVector<BasicBlock *, 4> ExitBlocks;
2453 L->getExitBlocks(ExitBlocks);
2454
2455 for (auto ExitBlock : ExitBlocks) {
2456 if (isa<UnreachableInst>(ExitBlock->getTerminator()))
2457 NumBlocks++;
2458 }
2459 return NumBlocks;
2460}
2461
2462static inline unsigned getNumBlocksInRegionNode(RegionNode *RN) {
2463 if (!RN->isSubRegion())
2464 return 1;
2465
2466 Region *R = RN->getNodeAs<Region>();
2467 return std::distance(R->block_begin(), R->block_end());
2468}
2469
2470static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI,
2471 const DominatorTree &DT) {
2472 if (!RN->isSubRegion())
2473 return isErrorBlock(*RN->getNodeAs<BasicBlock>(), R, LI, DT);
2474 for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())
2475 if (isErrorBlock(*BB, R, LI, DT))
2476 return true;
2477 return false;
2478}
2479
2480///}
2481
2482isl::set Scop::getDomainConditions(const ScopStmt *Stmt) const {
2483 return getDomainConditions(Stmt->getEntryBlock());
2484}
2485
2486isl::set Scop::getDomainConditions(BasicBlock *BB) const {
2487 auto DIt = DomainMap.find(BB);
2488 if (DIt != DomainMap.end())
2489 return DIt->getSecond();
2490
2491 auto &RI = *R.getRegionInfo();
2492 auto *BBR = RI.getRegionFor(BB);
2493 while (BBR->getEntry() == BB)
2494 BBR = BBR->getParent();
2495 return getDomainConditions(BBR->getEntry());
2496}
2497
2498bool Scop::buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI,
2499 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
2500 bool IsOnlyNonAffineRegion = isNonAffineSubRegion(R);
2501 auto *EntryBB = R->getEntry();
2502 auto *L = IsOnlyNonAffineRegion ? nullptr : LI.getLoopFor(EntryBB);
1
Assuming 'IsOnlyNonAffineRegion' is 0
2
'?' condition is false
2503 int LD = getRelativeLoopDepth(L);
2504 auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx().get(), 0, LD + 1));
2505
2506 while (LD-- >= 0) {
3
Loop condition is true. Entering loop body
4
Assuming the condition is false
5
Loop condition is false. Execution continues on line 2510
2507 L = L->getParentLoop();
2508 }
2509
2510 InvalidDomainMap[EntryBB] = isl::manage(isl_set_empty(isl_set_get_space(S)));
2511 DomainMap[EntryBB] = isl::manage(S);
2512
2513 if (IsOnlyNonAffineRegion)
6
Taking false branch
2514 return !containsErrorBlock(R->getNode(), *R, LI, DT);
2515
2516 if (!buildDomainsWithBranchConstraints(R, DT, LI, InvalidDomainMap))
7
Calling 'Scop::buildDomainsWithBranchConstraints'
2517 return false;
2518
2519 if (!propagateDomainConstraints(R, DT, LI, InvalidDomainMap))
2520 return false;
2521
2522 // Error blocks and blocks dominated by them have been assumed to never be
2523 // executed. Representing them in the Scop does not add any value. In fact,
2524 // it is likely to cause issues during construction of the ScopStmts. The
2525 // contents of error blocks have not been verified to be expressible and
2526 // will cause problems when building up a ScopStmt for them.
2527 // Furthermore, basic blocks dominated by error blocks may reference
2528 // instructions in the error block which, if the error block is not modeled,
2529 // can themselves not be constructed properly. To this end we will replace
2530 // the domains of error blocks and those only reachable via error blocks
2531 // with an empty set. Additionally, we will record for each block under which
2532 // parameter combination it would be reached via an error block in its
2533 // InvalidDomain. This information is needed during load hoisting.
2534 if (!propagateInvalidStmtDomains(R, DT, LI, InvalidDomainMap))
2535 return false;
2536
2537 return true;
2538}
2539
2540/// Adjust the dimensions of @p Dom that was constructed for @p OldL
2541/// to be compatible to domains constructed for loop @p NewL.
2542///
2543/// This function assumes @p NewL and @p OldL are equal or there is a CFG
2544/// edge from @p OldL to @p NewL.
2545static isl::set adjustDomainDimensions(Scop &S, isl::set Dom, Loop *OldL,
2546 Loop *NewL) {
2547 // If the loops are the same there is nothing to do.
2548 if (NewL == OldL)
31
Assuming 'NewL' is not equal to 'OldL'
32
Taking false branch
2549 return Dom;
2550
2551 int OldDepth = S.getRelativeLoopDepth(OldL);
2552 int NewDepth = S.getRelativeLoopDepth(NewL);
2553 // If both loops are non-affine loops there is nothing to do.
2554 if (OldDepth == -1 && NewDepth == -1)
33
Assuming the condition is false
2555 return Dom;
2556
2557 // Distinguish three cases:
2558 // 1) The depth is the same but the loops are not.
2559 // => One loop was left one was entered.
2560 // 2) The depth increased from OldL to NewL.
2561 // => One loop was entered, none was left.
2562 // 3) The depth decreased from OldL to NewL.
2563 // => Loops were left were difference of the depths defines how many.
2564 if (OldDepth == NewDepth) {
34
Assuming 'OldDepth' is equal to 'NewDepth'
35
Taking true branch
2565 assert(OldL->getParentLoop() == NewL->getParentLoop())((OldL->getParentLoop() == NewL->getParentLoop()) ? static_cast
<void> (0) : __assert_fail ("OldL->getParentLoop() == NewL->getParentLoop()"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2565, __PRETTY_FUNCTION__))
;
36
Within the expansion of the macro 'assert':
a
Called C++ object pointer is null
2566 Dom = Dom.project_out(isl::dim::set, NewDepth, 1);
2567 Dom = Dom.add_dims(isl::dim::set, 1);
2568 } else if (OldDepth < NewDepth) {
2569 assert(OldDepth + 1 == NewDepth)((OldDepth + 1 == NewDepth) ? static_cast<void> (0) : __assert_fail
("OldDepth + 1 == NewDepth", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2569, __PRETTY_FUNCTION__))
;
2570 auto &R = S.getRegion();
2571 (void)R;
2572 assert(NewL->getParentLoop() == OldL ||((NewL->getParentLoop() == OldL || ((!OldL || !R.contains(
OldL)) && R.contains(NewL))) ? static_cast<void>
(0) : __assert_fail ("NewL->getParentLoop() == OldL || ((!OldL || !R.contains(OldL)) && R.contains(NewL))"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2573, __PRETTY_FUNCTION__))
2573 ((!OldL || !R.contains(OldL)) && R.contains(NewL)))((NewL->getParentLoop() == OldL || ((!OldL || !R.contains(
OldL)) && R.contains(NewL))) ? static_cast<void>
(0) : __assert_fail ("NewL->getParentLoop() == OldL || ((!OldL || !R.contains(OldL)) && R.contains(NewL))"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2573, __PRETTY_FUNCTION__))
;
2574 Dom = Dom.add_dims(isl::dim::set, 1);
2575 } else {
2576 assert(OldDepth > NewDepth)((OldDepth > NewDepth) ? static_cast<void> (0) : __assert_fail
("OldDepth > NewDepth", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2576, __PRETTY_FUNCTION__))
;
2577 int Diff = OldDepth - NewDepth;
2578 int NumDim = Dom.n_dim();
2579 assert(NumDim >= Diff)((NumDim >= Diff) ? static_cast<void> (0) : __assert_fail
("NumDim >= Diff", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2579, __PRETTY_FUNCTION__))
;
2580 Dom = Dom.project_out(isl::dim::set, NumDim - Diff, Diff);
2581 }
2582
2583 return Dom;
2584}
2585
2586bool Scop::propagateInvalidStmtDomains(
2587 Region *R, DominatorTree &DT, LoopInfo &LI,
2588 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
2589 ReversePostOrderTraversal<Region *> RTraversal(R);
2590 for (auto *RN : RTraversal) {
2591
2592 // Recurse for affine subregions but go on for basic blocks and non-affine
2593 // subregions.
2594 if (RN->isSubRegion()) {
2595 Region *SubRegion = RN->getNodeAs<Region>();
2596 if (!isNonAffineSubRegion(SubRegion)) {
2597 propagateInvalidStmtDomains(SubRegion, DT, LI, InvalidDomainMap);
2598 continue;
2599 }
2600 }
2601
2602 bool ContainsErrorBlock = containsErrorBlock(RN, getRegion(), LI, DT);
2603 BasicBlock *BB = getRegionNodeBasicBlock(RN);
2604 isl::set &Domain = DomainMap[BB];
2605 assert(Domain && "Cannot propagate a nullptr")((Domain && "Cannot propagate a nullptr") ? static_cast
<void> (0) : __assert_fail ("Domain && \"Cannot propagate a nullptr\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2605, __PRETTY_FUNCTION__))
;
2606
2607 isl::set InvalidDomain = InvalidDomainMap[BB];
2608
2609 bool IsInvalidBlock = ContainsErrorBlock || Domain.is_subset(InvalidDomain);
2610
2611 if (!IsInvalidBlock) {
2612 InvalidDomain = InvalidDomain.intersect(Domain);
2613 } else {
2614 InvalidDomain = Domain;
2615 isl::set DomPar = Domain.params();
2616 recordAssumption(ERRORBLOCK, DomPar, BB->getTerminator()->getDebugLoc(),
2617 AS_RESTRICTION);
2618 Domain = isl::set::empty(Domain.get_space());
2619 }
2620
2621 if (InvalidDomain.is_empty()) {
2622 InvalidDomainMap[BB] = InvalidDomain;
2623 continue;
2624 }
2625
2626 auto *BBLoop = getRegionNodeLoop(RN, LI);
2627 auto *TI = BB->getTerminator();
2628 unsigned NumSuccs = RN->isSubRegion() ? 1 : TI->getNumSuccessors();
2629 for (unsigned u = 0; u < NumSuccs; u++) {
2630 auto *SuccBB = getRegionNodeSuccessor(RN, TI, u);
2631
2632 // Skip successors outside the SCoP.
2633 if (!contains(SuccBB))
2634 continue;
2635
2636 // Skip backedges.
2637 if (DT.dominates(SuccBB, BB))
2638 continue;
2639
2640 Loop *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, getBoxedLoops());
2641
2642 auto AdjustedInvalidDomain =
2643 adjustDomainDimensions(*this, InvalidDomain, BBLoop, SuccBBLoop);
2644
2645 isl::set SuccInvalidDomain = InvalidDomainMap[SuccBB];
2646 SuccInvalidDomain = SuccInvalidDomain.unite(AdjustedInvalidDomain);
2647 SuccInvalidDomain = SuccInvalidDomain.coalesce();
2648 unsigned NumConjucts = SuccInvalidDomain.n_basic_set();
2649
2650 InvalidDomainMap[SuccBB] = SuccInvalidDomain;
2651
2652 // Check if the maximal number of domain disjunctions was reached.
2653 // In case this happens we will bail.
2654 if (NumConjucts < MaxDisjunctsInDomain)
2655 continue;
2656
2657 InvalidDomainMap.erase(BB);
2658 invalidate(COMPLEXITY, TI->getDebugLoc(), TI->getParent());
2659 return false;
2660 }
2661
2662 InvalidDomainMap[BB] = InvalidDomain;
2663 }
2664
2665 return true;
2666}
2667
2668void Scop::propagateDomainConstraintsToRegionExit(
2669 BasicBlock *BB, Loop *BBLoop,
2670 SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, LoopInfo &LI,
2671 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
2672 // Check if the block @p BB is the entry of a region. If so we propagate it's
2673 // domain to the exit block of the region. Otherwise we are done.
2674 auto *RI = R.getRegionInfo();
2675 auto *BBReg = RI ? RI->getRegionFor(BB) : nullptr;
21
Assuming 'RI' is non-null
22
'?' condition is true
2676 auto *ExitBB = BBReg ? BBReg->getExit() : nullptr;
23
Assuming 'BBReg' is non-null
24
'?' condition is true
2677 if (!BBReg || BBReg->getEntry() != BB || !contains(ExitBB))
25
Assuming the condition is false
26
Assuming the condition is false
27
Taking false branch
2678 return;
2679
2680 // Do not propagate the domain if there is a loop backedge inside the region
2681 // that would prevent the exit block from being executed.
2682 auto *L = BBLoop;
2683 while (L && contains(L)) {
28
Assuming 'L' is null
2684 SmallVector<BasicBlock *, 4> LatchBBs;
2685 BBLoop->getLoopLatches(LatchBBs);
2686 for (auto *LatchBB : LatchBBs)
2687 if (BB != LatchBB && BBReg->contains(LatchBB))
2688 return;
2689 L = L->getParentLoop();
2690 }
2691
2692 isl::set Domain = DomainMap[BB];
2693 assert(Domain && "Cannot propagate a nullptr")((Domain && "Cannot propagate a nullptr") ? static_cast
<void> (0) : __assert_fail ("Domain && \"Cannot propagate a nullptr\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2693, __PRETTY_FUNCTION__))
;
2694
2695 Loop *ExitBBLoop = getFirstNonBoxedLoopFor(ExitBB, LI, getBoxedLoops());
2696
2697 // Since the dimensions of @p BB and @p ExitBB might be different we have to
2698 // adjust the domain before we can propagate it.
2699 isl::set AdjustedDomain =
2700 adjustDomainDimensions(*this, Domain, BBLoop, ExitBBLoop);
29
Passing null pointer value via 3rd parameter 'OldL'
30
Calling 'adjustDomainDimensions'
2701 isl::set &ExitDomain = DomainMap[ExitBB];
2702
2703 // If the exit domain is not yet created we set it otherwise we "add" the
2704 // current domain.
2705 ExitDomain = ExitDomain ? AdjustedDomain.unite(ExitDomain) : AdjustedDomain;
2706
2707 // Initialize the invalid domain.
2708 InvalidDomainMap[ExitBB] = ExitDomain.empty(ExitDomain.get_space());
2709
2710 FinishedExitBlocks.insert(ExitBB);
2711}
2712
2713bool Scop::buildDomainsWithBranchConstraints(
2714 Region *R, DominatorTree &DT, LoopInfo &LI,
2715 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
2716 // To create the domain for each block in R we iterate over all blocks and
2717 // subregions in R and propagate the conditions under which the current region
2718 // element is executed. To this end we iterate in reverse post order over R as
2719 // it ensures that we first visit all predecessors of a region node (either a
2720 // basic block or a subregion) before we visit the region node itself.
2721 // Initially, only the domain for the SCoP region entry block is set and from
2722 // there we propagate the current domain to all successors, however we add the
2723 // condition that the successor is actually executed next.
2724 // As we are only interested in non-loop carried constraints here we can
2725 // simply skip loop back edges.
2726
2727 SmallPtrSet<BasicBlock *, 8> FinishedExitBlocks;
2728 ReversePostOrderTraversal<Region *> RTraversal(R);
2729 for (auto *RN : RTraversal) {
2730 // Recurse for affine subregions but go on for basic blocks and non-affine
2731 // subregions.
2732 if (RN->isSubRegion()) {
8
Assuming the condition is true
9
Taking true branch
13
Assuming the condition is false
14
Taking false branch
2733 Region *SubRegion = RN->getNodeAs<Region>();
2734 if (!isNonAffineSubRegion(SubRegion)) {
10
Assuming the condition is true
11
Taking true branch
2735 if (!buildDomainsWithBranchConstraints(SubRegion, DT, LI,
12
Calling 'Scop::buildDomainsWithBranchConstraints'
2736 InvalidDomainMap))
2737 return false;
2738 continue;
2739 }
2740 }
2741
2742 if (containsErrorBlock(RN, getRegion(), LI, DT))
15
Assuming the condition is false
16
Taking false branch
2743 HasErrorBlock = true;
2744
2745 BasicBlock *BB = getRegionNodeBasicBlock(RN);
2746 Instruction *TI = BB->getTerminator();
2747
2748 if (isa<UnreachableInst>(TI))
17
Taking false branch
2749 continue;
2750
2751 isl::set Domain = DomainMap.lookup(BB);
2752 if (!Domain)
18
Taking false branch
2753 continue;
2754 MaxLoopDepth = std::max(MaxLoopDepth, isl_set_n_dim(Domain.get()));
2755
2756 auto *BBLoop = getRegionNodeLoop(RN, LI);
2757 // Propagate the domain from BB directly to blocks that have a superset
2758 // domain, at the moment only region exit nodes of regions that start in BB.
2759 propagateDomainConstraintsToRegionExit(BB, BBLoop, FinishedExitBlocks, LI,
19
Passing value via 2nd parameter 'BBLoop'
20
Calling 'Scop::propagateDomainConstraintsToRegionExit'
2760 InvalidDomainMap);
2761
2762 // If all successors of BB have been set a domain through the propagation
2763 // above we do not need to build condition sets but can just skip this
2764 // block. However, it is important to note that this is a local property
2765 // with regards to the region @p R. To this end FinishedExitBlocks is a
2766 // local variable.
2767 auto IsFinishedRegionExit = [&FinishedExitBlocks](BasicBlock *SuccBB) {
2768 return FinishedExitBlocks.count(SuccBB);
2769 };
2770 if (std::all_of(succ_begin(BB), succ_end(BB), IsFinishedRegionExit))
2771 continue;
2772
2773 // Build the condition sets for the successor nodes of the current region
2774 // node. If it is a non-affine subregion we will always execute the single
2775 // exit node, hence the single entry node domain is the condition set. For
2776 // basic blocks we use the helper function buildConditionSets.
2777 SmallVector<isl_set *, 8> ConditionSets;
2778 if (RN->isSubRegion())
2779 ConditionSets.push_back(Domain.copy());
2780 else if (!buildConditionSets(*this, BB, TI, BBLoop, Domain.get(),
2781 InvalidDomainMap, ConditionSets))
2782 return false;
2783
2784 // Now iterate over the successors and set their initial domain based on
2785 // their condition set. We skip back edges here and have to be careful when
2786 // we leave a loop not to keep constraints over a dimension that doesn't
2787 // exist anymore.
2788 assert(RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size())((RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets
.size()) ? static_cast<void> (0) : __assert_fail ("RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size()"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2788, __PRETTY_FUNCTION__))
;
2789 for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) {
2790 isl::set CondSet = isl::manage(ConditionSets[u]);
2791 BasicBlock *SuccBB = getRegionNodeSuccessor(RN, TI, u);
2792
2793 // Skip blocks outside the region.
2794 if (!contains(SuccBB))
2795 continue;
2796
2797 // If we propagate the domain of some block to "SuccBB" we do not have to
2798 // adjust the domain.
2799 if (FinishedExitBlocks.count(SuccBB))
2800 continue;
2801
2802 // Skip back edges.
2803 if (DT.dominates(SuccBB, BB))
2804 continue;
2805
2806 Loop *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, getBoxedLoops());
2807
2808 CondSet = adjustDomainDimensions(*this, CondSet, BBLoop, SuccBBLoop);
2809
2810 // Set the domain for the successor or merge it with an existing domain in
2811 // case there are multiple paths (without loop back edges) to the
2812 // successor block.
2813 isl::set &SuccDomain = DomainMap[SuccBB];
2814
2815 if (SuccDomain) {
2816 SuccDomain = SuccDomain.unite(CondSet).coalesce();
2817 } else {
2818 // Initialize the invalid domain.
2819 InvalidDomainMap[SuccBB] = CondSet.empty(CondSet.get_space());
2820 SuccDomain = CondSet;
2821 }
2822
2823 SuccDomain = SuccDomain.detect_equalities();
2824
2825 // Check if the maximal number of domain disjunctions was reached.
2826 // In case this happens we will clean up and bail.
2827 if (SuccDomain.n_basic_set() < MaxDisjunctsInDomain)
2828 continue;
2829
2830 invalidate(COMPLEXITY, DebugLoc());
2831 while (++u < ConditionSets.size())
2832 isl_set_free(ConditionSets[u]);
2833 return false;
2834 }
2835 }
2836
2837 return true;
2838}
2839
2840isl::set Scop::getPredecessorDomainConstraints(BasicBlock *BB, isl::set Domain,
2841 DominatorTree &DT,
2842 LoopInfo &LI) {
2843 // If @p BB is the ScopEntry we are done
2844 if (R.getEntry() == BB)
2845 return isl::set::universe(Domain.get_space());
2846
2847 // The region info of this function.
2848 auto &RI = *R.getRegionInfo();
2849
2850 Loop *BBLoop = getFirstNonBoxedLoopFor(BB, LI, getBoxedLoops());
2851
2852 // A domain to collect all predecessor domains, thus all conditions under
2853 // which the block is executed. To this end we start with the empty domain.
2854 isl::set PredDom = isl::set::empty(Domain.get_space());
2855
2856 // Set of regions of which the entry block domain has been propagated to BB.
2857 // all predecessors inside any of the regions can be skipped.
2858 SmallSet<Region *, 8> PropagatedRegions;
2859
2860 for (auto *PredBB : predecessors(BB)) {
2861 // Skip backedges.
2862 if (DT.dominates(BB, PredBB))
2863 continue;
2864
2865 // If the predecessor is in a region we used for propagation we can skip it.
2866 auto PredBBInRegion = [PredBB](Region *PR) { return PR->contains(PredBB); };
2867 if (std::any_of(PropagatedRegions.begin(), PropagatedRegions.end(),
2868 PredBBInRegion)) {
2869 continue;
2870 }
2871
2872 // Check if there is a valid region we can use for propagation, thus look
2873 // for a region that contains the predecessor and has @p BB as exit block.
2874 auto *PredR = RI.getRegionFor(PredBB);
2875 while (PredR->getExit() != BB && !PredR->contains(BB))
2876 PredR->getParent();
2877
2878 // If a valid region for propagation was found use the entry of that region
2879 // for propagation, otherwise the PredBB directly.
2880 if (PredR->getExit() == BB) {
2881 PredBB = PredR->getEntry();
2882 PropagatedRegions.insert(PredR);
2883 }
2884
2885 isl::set PredBBDom = getDomainConditions(PredBB);
2886 Loop *PredBBLoop = getFirstNonBoxedLoopFor(PredBB, LI, getBoxedLoops());
2887 PredBBDom = adjustDomainDimensions(*this, PredBBDom, PredBBLoop, BBLoop);
2888 PredDom = PredDom.unite(PredBBDom);
2889 }
2890
2891 return PredDom;
2892}
2893
2894bool Scop::propagateDomainConstraints(
2895 Region *R, DominatorTree &DT, LoopInfo &LI,
2896 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
2897 // Iterate over the region R and propagate the domain constrains from the
2898 // predecessors to the current node. In contrast to the
2899 // buildDomainsWithBranchConstraints function, this one will pull the domain
2900 // information from the predecessors instead of pushing it to the successors.
2901 // Additionally, we assume the domains to be already present in the domain
2902 // map here. However, we iterate again in reverse post order so we know all
2903 // predecessors have been visited before a block or non-affine subregion is
2904 // visited.
2905
2906 ReversePostOrderTraversal<Region *> RTraversal(R);
2907 for (auto *RN : RTraversal) {
2908 // Recurse for affine subregions but go on for basic blocks and non-affine
2909 // subregions.
2910 if (RN->isSubRegion()) {
2911 Region *SubRegion = RN->getNodeAs<Region>();
2912 if (!isNonAffineSubRegion(SubRegion)) {
2913 if (!propagateDomainConstraints(SubRegion, DT, LI, InvalidDomainMap))
2914 return false;
2915 continue;
2916 }
2917 }
2918
2919 BasicBlock *BB = getRegionNodeBasicBlock(RN);
2920 isl::set &Domain = DomainMap[BB];
2921 assert(Domain)((Domain) ? static_cast<void> (0) : __assert_fail ("Domain"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2921, __PRETTY_FUNCTION__))
;
2922
2923 // Under the union of all predecessor conditions we can reach this block.
2924 isl::set PredDom = getPredecessorDomainConstraints(BB, Domain, DT, LI);
2925 Domain = Domain.intersect(PredDom).coalesce();
2926 Domain = Domain.align_params(getParamSpace());
2927
2928 Loop *BBLoop = getRegionNodeLoop(RN, LI);
2929 if (BBLoop && BBLoop->getHeader() == BB && contains(BBLoop))
2930 if (!addLoopBoundsToHeaderDomain(BBLoop, LI, InvalidDomainMap))
2931 return false;
2932 }
2933
2934 return true;
2935}
2936
2937/// Create a map to map from a given iteration to a subsequent iteration.
2938///
2939/// This map maps from SetSpace -> SetSpace where the dimensions @p Dim
2940/// is incremented by one and all other dimensions are equal, e.g.,
2941/// [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3]
2942///
2943/// if @p Dim is 2 and @p SetSpace has 4 dimensions.
2944static isl::map createNextIterationMap(isl::space SetSpace, unsigned Dim) {
2945 isl::space MapSpace = SetSpace.map_from_set();
2946 isl::map NextIterationMap = isl::map::universe(MapSpace);
2947 for (unsigned u = 0; u < NextIterationMap.dim(isl::dim::in); u++)
2948 if (u != Dim)
2949 NextIterationMap =
2950 NextIterationMap.equate(isl::dim::in, u, isl::dim::out, u);
2951 isl::constraint C =
2952 isl::constraint::alloc_equality(isl::local_space(MapSpace));
2953 C = C.set_constant_si(1);
2954 C = C.set_coefficient_si(isl::dim::in, Dim, 1);
2955 C = C.set_coefficient_si(isl::dim::out, Dim, -1);
2956 NextIterationMap = NextIterationMap.add_constraint(C);
2957 return NextIterationMap;
2958}
2959
2960bool Scop::addLoopBoundsToHeaderDomain(
2961 Loop *L, LoopInfo &LI, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
2962 int LoopDepth = getRelativeLoopDepth(L);
2963 assert(LoopDepth >= 0 && "Loop in region should have at least depth one")((LoopDepth >= 0 && "Loop in region should have at least depth one"
) ? static_cast<void> (0) : __assert_fail ("LoopDepth >= 0 && \"Loop in region should have at least depth one\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2963, __PRETTY_FUNCTION__))
;
2964
2965 BasicBlock *HeaderBB = L->getHeader();
2966 assert(DomainMap.count(HeaderBB))((DomainMap.count(HeaderBB)) ? static_cast<void> (0) : __assert_fail
("DomainMap.count(HeaderBB)", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2966, __PRETTY_FUNCTION__))
;
2967 isl::set &HeaderBBDom = DomainMap[HeaderBB];
2968
2969 isl::map NextIterationMap =
2970 createNextIterationMap(HeaderBBDom.get_space(), LoopDepth);
2971
2972 isl::set UnionBackedgeCondition = HeaderBBDom.empty(HeaderBBDom.get_space());
2973
2974 SmallVector<BasicBlock *, 4> LatchBlocks;
2975 L->getLoopLatches(LatchBlocks);
2976
2977 for (BasicBlock *LatchBB : LatchBlocks) {
2978 // If the latch is only reachable via error statements we skip it.
2979 isl::set LatchBBDom = DomainMap.lookup(LatchBB);
2980 if (!LatchBBDom)
2981 continue;
2982
2983 isl::set BackedgeCondition = nullptr;
2984
2985 Instruction *TI = LatchBB->getTerminator();
2986 BranchInst *BI = dyn_cast<BranchInst>(TI);
2987 assert(BI && "Only branch instructions allowed in loop latches")((BI && "Only branch instructions allowed in loop latches"
) ? static_cast<void> (0) : __assert_fail ("BI && \"Only branch instructions allowed in loop latches\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 2987, __PRETTY_FUNCTION__))
;
2988
2989 if (BI->isUnconditional())
2990 BackedgeCondition = LatchBBDom;
2991 else {
2992 SmallVector<isl_set *, 8> ConditionSets;
2993 int idx = BI->getSuccessor(0) != HeaderBB;
2994 if (!buildConditionSets(*this, LatchBB, TI, L, LatchBBDom.get(),
2995 InvalidDomainMap, ConditionSets))
2996 return false;
2997
2998 // Free the non back edge condition set as we do not need it.
2999 isl_set_free(ConditionSets[1 - idx]);
3000
3001 BackedgeCondition = isl::manage(ConditionSets[idx]);
3002 }
3003
3004 int LatchLoopDepth = getRelativeLoopDepth(LI.getLoopFor(LatchBB));
3005 assert(LatchLoopDepth >= LoopDepth)((LatchLoopDepth >= LoopDepth) ? static_cast<void> (
0) : __assert_fail ("LatchLoopDepth >= LoopDepth", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 3005, __PRETTY_FUNCTION__))
;
3006 BackedgeCondition = BackedgeCondition.project_out(
3007 isl::dim::set, LoopDepth + 1, LatchLoopDepth - LoopDepth);
3008 UnionBackedgeCondition = UnionBackedgeCondition.unite(BackedgeCondition);
3009 }
3010
3011 isl::map ForwardMap = ForwardMap.lex_le(HeaderBBDom.get_space());
3012 for (int i = 0; i < LoopDepth; i++)
3013 ForwardMap = ForwardMap.equate(isl::dim::in, i, isl::dim::out, i);
3014
3015 isl::set UnionBackedgeConditionComplement =
3016 UnionBackedgeCondition.complement();
3017 UnionBackedgeConditionComplement =
3018 UnionBackedgeConditionComplement.lower_bound_si(isl::dim::set, LoopDepth,
3019 0);
3020 UnionBackedgeConditionComplement =
3021 UnionBackedgeConditionComplement.apply(ForwardMap);
3022 HeaderBBDom = HeaderBBDom.subtract(UnionBackedgeConditionComplement);
3023 HeaderBBDom = HeaderBBDom.apply(NextIterationMap);
3024
3025 auto Parts = partitionSetParts(HeaderBBDom, LoopDepth);
3026 HeaderBBDom = Parts.second;
3027
3028 // Check if there is a <nsw> tagged AddRec for this loop and if so do not add
3029 // the bounded assumptions to the context as they are already implied by the
3030 // <nsw> tag.
3031 if (Affinator.hasNSWAddRecForLoop(L))
3032 return true;
3033
3034 isl::set UnboundedCtx = Parts.first.params();
3035 recordAssumption(INFINITELOOP, UnboundedCtx,
3036 HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION);
3037 return true;
3038}
3039
3040MemoryAccess *Scop::lookupBasePtrAccess(MemoryAccess *MA) {
3041 Value *PointerBase = MA->getOriginalBaseAddr();
3042
3043 auto *PointerBaseInst = dyn_cast<Instruction>(PointerBase);
3044 if (!PointerBaseInst)
3045 return nullptr;
3046
3047 auto *BasePtrStmt = getStmtFor(PointerBaseInst);
3048 if (!BasePtrStmt)
3049 return nullptr;
3050
3051 return BasePtrStmt->getArrayAccessOrNULLFor(PointerBaseInst);
3052}
3053
3054bool Scop::hasNonHoistableBasePtrInScop(MemoryAccess *MA,
3055 isl::union_map Writes) {
3056 if (auto *BasePtrMA = lookupBasePtrAccess(MA)) {
3057 return getNonHoistableCtx(BasePtrMA, Writes).is_null();
3058 }
3059
3060 Value *BaseAddr = MA->getOriginalBaseAddr();
3061 if (auto *BasePtrInst = dyn_cast<Instruction>(BaseAddr))
3062 if (!isa<LoadInst>(BasePtrInst))
3063 return contains(BasePtrInst);
3064
3065 return false;
3066}
3067
3068bool Scop::buildAliasChecks(AliasAnalysis &AA) {
3069 if (!PollyUseRuntimeAliasChecks)
3070 return true;
3071
3072 if (buildAliasGroups(AA)) {
3073 // Aliasing assumptions do not go through addAssumption but we still want to
3074 // collect statistics so we do it here explicitly.
3075 if (MinMaxAliasGroups.size())
3076 AssumptionsAliasing++;
3077 return true;
3078 }
3079
3080 // If a problem occurs while building the alias groups we need to delete
3081 // this SCoP and pretend it wasn't valid in the first place. To this end
3082 // we make the assumed context infeasible.
3083 invalidate(ALIASING, DebugLoc());
3084
3085 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for "
<< getNameStr() << " could not be created as the number of parameters involved "
"is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust "
"the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n"
; } } while (false)
3086 dbgs() << "\n\nNOTE: Run time checks for " << getNameStr()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for "
<< getNameStr() << " could not be created as the number of parameters involved "
"is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust "
"the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n"
; } } while (false)
3087 << " could not be created as the number of parameters involved "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for "
<< getNameStr() << " could not be created as the number of parameters involved "
"is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust "
"the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n"
; } } while (false)
3088 "is too high. The SCoP will be "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for "
<< getNameStr() << " could not be created as the number of parameters involved "
"is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust "
"the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n"
; } } while (false)
3089 "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for "
<< getNameStr() << " could not be created as the number of parameters involved "
"is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust "
"the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n"
; } } while (false)
3090 "the maximal number of parameters but be advised that the "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for "
<< getNameStr() << " could not be created as the number of parameters involved "
"is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust "
"the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n"
; } } while (false)
3091 "compile time might increase exponentially.\n\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for "
<< getNameStr() << " could not be created as the number of parameters involved "
"is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust "
"the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n"
; } } while (false)
;
3092 return false;
3093}
3094
3095std::tuple<Scop::AliasGroupVectorTy, DenseSet<const ScopArrayInfo *>>
3096Scop::buildAliasGroupsForAccesses(AliasAnalysis &AA) {
3097 AliasSetTracker AST(AA);
3098
3099 DenseMap<Value *, MemoryAccess *> PtrToAcc;
3100 DenseSet<const ScopArrayInfo *> HasWriteAccess;
3101 for (ScopStmt &Stmt : *this) {
3102
3103 isl::set StmtDomain = Stmt.getDomain();
3104 bool StmtDomainEmpty = StmtDomain.is_empty();
3105
3106 // Statements with an empty domain will never be executed.
3107 if (StmtDomainEmpty)
3108 continue;
3109
3110 for (MemoryAccess *MA : Stmt) {
3111 if (MA->isScalarKind())
3112 continue;
3113 if (!MA->isRead())
3114 HasWriteAccess.insert(MA->getScopArrayInfo());
3115 MemAccInst Acc(MA->getAccessInstruction());
3116 if (MA->isRead() && isa<MemTransferInst>(Acc))
3117 PtrToAcc[cast<MemTransferInst>(Acc)->getRawSource()] = MA;
3118 else
3119 PtrToAcc[Acc.getPointerOperand()] = MA;
3120 AST.add(Acc);
3121 }
3122 }
3123
3124 AliasGroupVectorTy AliasGroups;
3125 for (AliasSet &AS : AST) {
3126 if (AS.isMustAlias() || AS.isForwardingAliasSet())
3127 continue;
3128 AliasGroupTy AG;
3129 for (auto &PR : AS)
3130 AG.push_back(PtrToAcc[PR.getValue()]);
3131 if (AG.size() < 2)
3132 continue;
3133 AliasGroups.push_back(std::move(AG));
3134 }
3135
3136 return std::make_tuple(AliasGroups, HasWriteAccess);
3137}
3138
3139void Scop::splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups) {
3140 for (unsigned u = 0; u < AliasGroups.size(); u++) {
3141 AliasGroupTy NewAG;
3142 AliasGroupTy &AG = AliasGroups[u];
3143 AliasGroupTy::iterator AGI = AG.begin();
3144 isl::set AGDomain = getAccessDomain(*AGI);
3145 while (AGI != AG.end()) {
3146 MemoryAccess *MA = *AGI;
3147 isl::set MADomain = getAccessDomain(MA);
3148 if (AGDomain.is_disjoint(MADomain)) {
3149 NewAG.push_back(MA);
3150 AGI = AG.erase(AGI);
3151 } else {
3152 AGDomain = AGDomain.unite(MADomain);
3153 AGI++;
3154 }
3155 }
3156 if (NewAG.size() > 1)
3157 AliasGroups.push_back(std::move(NewAG));
3158 }
3159}
3160
3161bool Scop::buildAliasGroups(AliasAnalysis &AA) {
3162 // To create sound alias checks we perform the following steps:
3163 // o) We partition each group into read only and non read only accesses.
3164 // o) For each group with more than one base pointer we then compute minimal
3165 // and maximal accesses to each array of a group in read only and non
3166 // read only partitions separately.
3167 AliasGroupVectorTy AliasGroups;
3168 DenseSet<const ScopArrayInfo *> HasWriteAccess;
3169
3170 std::tie(AliasGroups, HasWriteAccess) = buildAliasGroupsForAccesses(AA);
3171
3172 splitAliasGroupsByDomain(AliasGroups);
3173
3174 for (AliasGroupTy &AG : AliasGroups) {
3175 if (!hasFeasibleRuntimeContext())
3176 return false;
3177
3178 {
3179 IslMaxOperationsGuard MaxOpGuard(getIslCtx().get(), OptComputeOut);
3180 bool Valid = buildAliasGroup(AG, HasWriteAccess);
3181 if (!Valid)
3182 return false;
3183 }
3184 if (isl_ctx_last_error(getIslCtx().get()) == isl_error_quota) {
3185 invalidate(COMPLEXITY, DebugLoc());
3186 return false;
3187 }
3188 }
3189
3190 return true;
3191}
3192
3193bool Scop::buildAliasGroup(Scop::AliasGroupTy &AliasGroup,
3194 DenseSet<const ScopArrayInfo *> HasWriteAccess) {
3195 AliasGroupTy ReadOnlyAccesses;
3196 AliasGroupTy ReadWriteAccesses;
3197 SmallPtrSet<const ScopArrayInfo *, 4> ReadWriteArrays;
3198 SmallPtrSet<const ScopArrayInfo *, 4> ReadOnlyArrays;
3199
3200 if (AliasGroup.size() < 2)
3201 return true;
3202
3203 for (MemoryAccess *Access : AliasGroup) {
3204 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE"polly-scops", "PossibleAlias",
3205 Access->getAccessInstruction())
3206 << "Possibly aliasing pointer, use restrict keyword.");
3207 const ScopArrayInfo *Array = Access->getScopArrayInfo();
3208 if (HasWriteAccess.count(Array)) {
3209 ReadWriteArrays.insert(Array);
3210 ReadWriteAccesses.push_back(Access);
3211 } else {
3212 ReadOnlyArrays.insert(Array);
3213 ReadOnlyAccesses.push_back(Access);
3214 }
3215 }
3216
3217 // If there are no read-only pointers, and less than two read-write pointers,
3218 // no alias check is needed.
3219 if (ReadOnlyAccesses.empty() && ReadWriteArrays.size() <= 1)
3220 return true;
3221
3222 // If there is no read-write pointer, no alias check is needed.
3223 if (ReadWriteArrays.empty())
3224 return true;
3225
3226 // For non-affine accesses, no alias check can be generated as we cannot
3227 // compute a sufficiently tight lower and upper bound: bail out.
3228 for (MemoryAccess *MA : AliasGroup) {
3229 if (!MA->isAffine()) {
3230 invalidate(ALIASING, MA->getAccessInstruction()->getDebugLoc(),
3231 MA->getAccessInstruction()->getParent());
3232 return false;
3233 }
3234 }
3235
3236 // Ensure that for all memory accesses for which we generate alias checks,
3237 // their base pointers are available.
3238 for (MemoryAccess *MA : AliasGroup) {
3239 if (MemoryAccess *BasePtrMA = lookupBasePtrAccess(MA))
3240 addRequiredInvariantLoad(
3241 cast<LoadInst>(BasePtrMA->getAccessInstruction()));
3242 }
3243
3244 MinMaxAliasGroups.emplace_back();
3245 MinMaxVectorPairTy &pair = MinMaxAliasGroups.back();
3246 MinMaxVectorTy &MinMaxAccessesReadWrite = pair.first;
3247 MinMaxVectorTy &MinMaxAccessesReadOnly = pair.second;
3248
3249 bool Valid;
3250
3251 Valid =
3252 calculateMinMaxAccess(ReadWriteAccesses, *this, MinMaxAccessesReadWrite);
3253
3254 if (!Valid)
3255 return false;
3256
3257 // Bail out if the number of values we need to compare is too large.
3258 // This is important as the number of comparisons grows quadratically with
3259 // the number of values we need to compare.
3260 if (MinMaxAccessesReadWrite.size() + ReadOnlyArrays.size() >
3261 RunTimeChecksMaxArraysPerGroup)
3262 return false;
3263
3264 Valid =
3265 calculateMinMaxAccess(ReadOnlyAccesses, *this, MinMaxAccessesReadOnly);
3266
3267 if (!Valid)
3268 return false;
3269
3270 return true;
3271}
3272
3273/// Get the smallest loop that contains @p S but is not in @p S.
3274static Loop *getLoopSurroundingScop(Scop &S, LoopInfo &LI) {
3275 // Start with the smallest loop containing the entry and expand that
3276 // loop until it contains all blocks in the region. If there is a loop
3277 // containing all blocks in the region check if it is itself contained
3278 // and if so take the parent loop as it will be the smallest containing
3279 // the region but not contained by it.
3280 Loop *L = LI.getLoopFor(S.getEntry());
3281 while (L) {
3282 bool AllContained = true;
3283 for (auto *BB : S.blocks())
3284 AllContained &= L->contains(BB);
3285 if (AllContained)
3286 break;
3287 L = L->getParentLoop();
3288 }
3289
3290 return L ? (S.contains(L) ? L->getParentLoop() : L) : nullptr;
3291}
3292
3293int Scop::NextScopID = 0;
3294
3295std::string Scop::CurrentFunc;
3296
3297int Scop::getNextID(std::string ParentFunc) {
3298 if (ParentFunc != CurrentFunc) {
3299 CurrentFunc = ParentFunc;
3300 NextScopID = 0;
3301 }
3302 return NextScopID++;
3303}
3304
3305Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI,
3306 DominatorTree &DT, ScopDetection::DetectionContext &DC,
3307 OptimizationRemarkEmitter &ORE)
3308 : IslCtx(isl_ctx_alloc(), isl_ctx_free), SE(&ScalarEvolution), DT(&DT),
3309 R(R), name(None), HasSingleExitEdge(R.getExitingBlock()), DC(DC),
3310 ORE(ORE), Affinator(this, LI),
3311 ID(getNextID((*R.getEntry()->getParent()).getName().str())) {
3312 if (IslOnErrorAbort)
3313 isl_options_set_on_error(getIslCtx().get(), ISL_ON_ERROR_ABORT2);
3314 buildContext();
3315}
3316
3317Scop::~Scop() = default;
3318
3319void Scop::foldSizeConstantsToRight() {
3320 isl::union_set Accessed = getAccesses().range();
3321
3322 for (auto Array : arrays()) {
3323 if (Array->getNumberOfDimensions() <= 1)
3324 continue;
3325
3326 isl::space Space = Array->getSpace();
3327 Space = Space.align_params(Accessed.get_space());
3328
3329 if (!Accessed.contains(Space))
3330 continue;
3331
3332 isl::set Elements = Accessed.extract_set(Space);
3333 isl::map Transform = isl::map::universe(Array->getSpace().map_from_set());
3334
3335 std::vector<int> Int;
3336 int Dims = Elements.dim(isl::dim::set);
3337 for (int i = 0; i < Dims; i++) {
3338 isl::set DimOnly = isl::set(Elements).project_out(isl::dim::set, 0, i);
3339 DimOnly = DimOnly.project_out(isl::dim::set, 1, Dims - i - 1);
3340 DimOnly = DimOnly.lower_bound_si(isl::dim::set, 0, 0);
3341
3342 isl::basic_set DimHull = DimOnly.affine_hull();
3343
3344 if (i == Dims - 1) {
3345 Int.push_back(1);
3346 Transform = Transform.equate(isl::dim::in, i, isl::dim::out, i);
3347 continue;
3348 }
3349
3350 if (DimHull.dim(isl::dim::div) == 1) {
3351 isl::aff Diff = DimHull.get_div(0);
3352 isl::val Val = Diff.get_denominator_val();
3353
3354 int ValInt = 1;
3355 if (Val.is_int()) {
3356 auto ValAPInt = APIntFromVal(Val);
3357 if (ValAPInt.isSignedIntN(32))
3358 ValInt = ValAPInt.getSExtValue();
3359 } else {
3360 }
3361
3362 Int.push_back(ValInt);
3363 isl::constraint C = isl::constraint::alloc_equality(
3364 isl::local_space(Transform.get_space()));
3365 C = C.set_coefficient_si(isl::dim::out, i, ValInt);
3366 C = C.set_coefficient_si(isl::dim::in, i, -1);
3367 Transform = Transform.add_constraint(C);
3368 continue;
3369 }
3370
3371 isl::basic_set ZeroSet = isl::basic_set(DimHull);
3372 ZeroSet = ZeroSet.fix_si(isl::dim::set, 0, 0);
3373
3374 int ValInt = 1;
3375 if (ZeroSet.is_equal(DimHull)) {
3376 ValInt = 0;
3377 }
3378
3379 Int.push_back(ValInt);
3380 Transform = Transform.equate(isl::dim::in, i, isl::dim::out, i);
3381 }
3382
3383 isl::set MappedElements = isl::map(Transform).domain();
3384 if (!Elements.is_subset(MappedElements))
3385 continue;
3386
3387 bool CanFold = true;
3388 if (Int[0] <= 1)
3389 CanFold = false;
3390
3391 unsigned NumDims = Array->getNumberOfDimensions();
3392 for (unsigned i = 1; i < NumDims - 1; i++)
3393 if (Int[0] != Int[i] && Int[i])
3394 CanFold = false;
3395
3396 if (!CanFold)
3397 continue;
3398
3399 for (auto &Access : AccessFunctions)
3400 if (Access->getScopArrayInfo() == Array)
3401 Access->setAccessRelation(
3402 Access->getAccessRelation().apply_range(Transform));
3403
3404 std::vector<const SCEV *> Sizes;
3405 for (unsigned i = 0; i < NumDims; i++) {
3406 auto Size = Array->getDimensionSize(i);
3407
3408 if (i == NumDims - 1)
3409 Size = SE->getMulExpr(Size, SE->getConstant(Size->getType(), Int[0]));
3410 Sizes.push_back(Size);
3411 }
3412
3413 Array->updateSizes(Sizes, false /* CheckConsistency */);
3414 }
3415}
3416
3417void Scop::markFortranArrays() {
3418 for (ScopStmt &Stmt : Stmts) {
3419 for (MemoryAccess *MemAcc : Stmt) {
3420 Value *FAD = MemAcc->getFortranArrayDescriptor();
3421 if (!FAD)
3422 continue;
3423
3424 // TODO: const_cast-ing to edit
3425 ScopArrayInfo *SAI =
3426 const_cast<ScopArrayInfo *>(MemAcc->getLatestScopArrayInfo());
3427 assert(SAI && "memory access into a Fortran array does not "((SAI && "memory access into a Fortran array does not "
"have an associated ScopArrayInfo") ? static_cast<void>
(0) : __assert_fail ("SAI && \"memory access into a Fortran array does not \" \"have an associated ScopArrayInfo\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 3428, __PRETTY_FUNCTION__))
3428 "have an associated ScopArrayInfo")((SAI && "memory access into a Fortran array does not "
"have an associated ScopArrayInfo") ? static_cast<void>
(0) : __assert_fail ("SAI && \"memory access into a Fortran array does not \" \"have an associated ScopArrayInfo\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 3428, __PRETTY_FUNCTION__))
;
3429 SAI->applyAndSetFAD(FAD);
3430 }
3431 }
3432}
3433
3434void Scop::finalizeAccesses() {
3435 updateAccessDimensionality();
3436 foldSizeConstantsToRight();
3437 foldAccessRelations();
3438 assumeNoOutOfBounds();
3439 markFortranArrays();
3440}
3441
3442void Scop::updateAccessDimensionality() {
3443 // Check all array accesses for each base pointer and find a (virtual) element
3444 // size for the base pointer that divides all access functions.
3445 for (ScopStmt &Stmt : *this)
3446 for (MemoryAccess *Access : Stmt) {
3447 if (!Access->isArrayKind())
3448 continue;
3449 ScopArrayInfo *Array =
3450 const_cast<ScopArrayInfo *>(Access->getScopArrayInfo());
3451
3452 if (Array->getNumberOfDimensions() != 1)
3453 continue;
3454 unsigned DivisibleSize = Array->getElemSizeInBytes();
3455 const SCEV *Subscript = Access->getSubscript(0);
3456 while (!isDivisible(Subscript, DivisibleSize, *SE))
3457 DivisibleSize /= 2;
3458 auto *Ty = IntegerType::get(SE->getContext(), DivisibleSize * 8);
3459 Array->updateElementType(Ty);
3460 }
3461
3462 for (auto &Stmt : *this)
3463 for (auto &Access : Stmt)
3464 Access->updateDimensionality();
3465}
3466
3467void Scop::foldAccessRelations() {
3468 for (auto &Stmt : *this)
3469 for (auto &Access : Stmt)
3470 Access->foldAccessRelation();
3471}
3472
3473void Scop::assumeNoOutOfBounds() {
3474 for (auto &Stmt : *this)
3475 for (auto &Access : Stmt)
3476 Access->assumeNoOutOfBound();
3477}
3478
3479void Scop::removeFromStmtMap(ScopStmt &Stmt) {
3480 for (Instruction *Inst : Stmt.getInstructions())
3481 InstStmtMap.erase(Inst);
3482
3483 if (Stmt.isRegionStmt()) {
3484 for (BasicBlock *BB : Stmt.getRegion()->blocks()) {
3485 StmtMap.erase(BB);
3486 // Skip entry basic block, as its instructions are already deleted as
3487 // part of the statement's instruction list.
3488 if (BB == Stmt.getEntryBlock())
3489 continue;
3490 for (Instruction &Inst : *BB)
3491 InstStmtMap.erase(&Inst);
3492 }
3493 } else {
3494 auto StmtMapIt = StmtMap.find(Stmt.getBasicBlock());
3495 if (StmtMapIt != StmtMap.end())
3496 StmtMapIt->second.erase(std::remove(StmtMapIt->second.begin(),
3497 StmtMapIt->second.end(), &Stmt),
3498 StmtMapIt->second.end());
3499 for (Instruction *Inst : Stmt.getInstructions())
3500 InstStmtMap.erase(Inst);
3501 }
3502}
3503
3504void Scop::removeStmts(std::function<bool(ScopStmt &)> ShouldDelete,
3505 bool AfterHoisting) {
3506 for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) {
3507 if (!ShouldDelete(*StmtIt)) {
3508 StmtIt++;
3509 continue;
3510 }
3511
3512 // Start with removing all of the statement's accesses including erasing it
3513 // from all maps that are pointing to them.
3514 // Make a temporary copy because removing MAs invalidates the iterator.
3515 SmallVector<MemoryAccess *, 16> MAList(StmtIt->begin(), StmtIt->end());
3516 for (MemoryAccess *MA : MAList)
3517 StmtIt->removeSingleMemoryAccess(MA, AfterHoisting);
3518
3519 removeFromStmtMap(*StmtIt);
3520 StmtIt = Stmts.erase(StmtIt);
3521 }
3522}
3523
3524void Scop::removeStmtNotInDomainMap() {
3525 auto ShouldDelete = [this](ScopStmt &Stmt) -> bool {
3526 isl::set Domain = DomainMap.lookup(Stmt.getEntryBlock());
3527 if (!Domain)
3528 return true;
3529 return Domain.is_empty();
3530 };
3531 removeStmts(ShouldDelete, false);
3532}
3533
3534void Scop::simplifySCoP(bool AfterHoisting) {
3535 auto ShouldDelete = [AfterHoisting](ScopStmt &Stmt) -> bool {
3536 // Never delete statements that contain calls to debug functions.
3537 if (hasDebugCall(&Stmt))
3538 return false;
3539
3540 bool RemoveStmt = Stmt.isEmpty();
3541
3542 // Remove read only statements only after invariant load hoisting.
3543 if (!RemoveStmt && AfterHoisting) {
3544 bool OnlyRead = true;
3545 for (MemoryAccess *MA : Stmt) {
3546 if (MA->isRead())
3547 continue;
3548
3549 OnlyRead = false;
3550 break;
3551 }
3552
3553 RemoveStmt = OnlyRead;
3554 }
3555 return RemoveStmt;
3556 };
3557
3558 removeStmts(ShouldDelete, AfterHoisting);
3559}
3560
3561InvariantEquivClassTy *Scop::lookupInvariantEquivClass(Value *Val) {
3562 LoadInst *LInst = dyn_cast<LoadInst>(Val);
3563 if (!LInst)
3564 return nullptr;
3565
3566 if (Value *Rep = InvEquivClassVMap.lookup(LInst))
3567 LInst = cast<LoadInst>(Rep);
3568
3569 Type *Ty = LInst->getType();
3570 const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
3571 for (auto &IAClass : InvariantEquivClasses) {
3572 if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType)
3573 continue;
3574
3575 auto &MAs = IAClass.InvariantAccesses;
3576 for (auto *MA : MAs)
3577 if (MA->getAccessInstruction() == Val)
3578 return &IAClass;
3579 }
3580
3581 return nullptr;
3582}
3583
3584bool isAParameter(llvm::Value *maybeParam, const Function &F) {
3585 for (const llvm::Argument &Arg : F.args())
3586 if (&Arg == maybeParam)
3587 return true;
3588
3589 return false;
3590}
3591
3592bool Scop::canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty,
3593 bool MAInvalidCtxIsEmpty,
3594 bool NonHoistableCtxIsEmpty) {
3595 LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
3596 const DataLayout &DL = LInst->getParent()->getModule()->getDataLayout();
3597 if (PollyAllowDereferenceOfAllFunctionParams &&
3598 isAParameter(LInst->getPointerOperand(), getFunction()))
3599 return true;
3600
3601 // TODO: We can provide more information for better but more expensive
3602 // results.
3603 if (!isDereferenceableAndAlignedPointer(LInst->getPointerOperand(),
3604 LInst->getAlignment(), DL))
3605 return false;
3606
3607 // If the location might be overwritten we do not hoist it unconditionally.
3608 //
3609 // TODO: This is probably too conservative.
3610 if (!NonHoistableCtxIsEmpty)
3611 return false;
3612
3613 // If a dereferenceable load is in a statement that is modeled precisely we
3614 // can hoist it.
3615 if (StmtInvalidCtxIsEmpty && MAInvalidCtxIsEmpty)
3616 return true;
3617
3618 // Even if the statement is not modeled precisely we can hoist the load if it
3619 // does not involve any parameters that might have been specialized by the
3620 // statement domain.
3621 for (unsigned u = 0, e = MA->getNumSubscripts(); u < e; u++)
3622 if (!isa<SCEVConstant>(MA->getSubscript(u)))
3623 return false;
3624 return true;
3625}
3626
3627void Scop::addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs) {
3628 if (InvMAs.empty())
3629 return;
3630
3631 isl::set StmtInvalidCtx = Stmt.getInvalidContext();
3632 bool StmtInvalidCtxIsEmpty = StmtInvalidCtx.is_empty();
3633
3634 // Get the context under which the statement is executed but remove the error
3635 // context under which this statement is reached.
3636 isl::set DomainCtx = Stmt.getDomain().params();
3637 DomainCtx = DomainCtx.subtract(StmtInvalidCtx);
3638
3639 if (DomainCtx.n_basic_set() >= MaxDisjunctsInDomain) {
3640 auto *AccInst = InvMAs.front().MA->getAccessInstruction();
3641 invalidate(COMPLEXITY, AccInst->getDebugLoc(), AccInst->getParent());
3642 return;
3643 }
3644
3645 // Project out all parameters that relate to loads in the statement. Otherwise
3646 // we could have cyclic dependences on the constraints under which the
3647 // hoisted loads are executed and we could not determine an order in which to
3648 // pre-load them. This happens because not only lower bounds are part of the
3649 // domain but also upper bounds.
3650 for (auto &InvMA : InvMAs) {
3651 auto *MA = InvMA.MA;
3652 Instruction *AccInst = MA->getAccessInstruction();
3653 if (SE->isSCEVable(AccInst->getType())) {
3654 SetVector<Value *> Values;
3655 for (const SCEV *Parameter : Parameters) {
3656 Values.clear();
3657 findValues(Parameter, *SE, Values);
3658 if (!Values.count(AccInst))
3659 continue;
3660
3661 if (isl::id ParamId = getIdForParam(Parameter)) {
3662 int Dim = DomainCtx.find_dim_by_id(isl::dim::param, ParamId);
3663 if (Dim >= 0)
3664 DomainCtx = DomainCtx.eliminate(isl::dim::param, Dim, 1);
3665 }
3666 }
3667 }
3668 }
3669
3670 for (auto &InvMA : InvMAs) {
3671 auto *MA = InvMA.MA;
3672 isl::set NHCtx = InvMA.NonHoistableCtx;
3673
3674 // Check for another invariant access that accesses the same location as
3675 // MA and if found consolidate them. Otherwise create a new equivalence
3676 // class at the end of InvariantEquivClasses.
3677 LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
3678 Type *Ty = LInst->getType();
3679 const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
3680
3681 isl::set MAInvalidCtx = MA->getInvalidContext();
3682 bool NonHoistableCtxIsEmpty = NHCtx.is_empty();
3683 bool MAInvalidCtxIsEmpty = MAInvalidCtx.is_empty();
3684
3685 isl::set MACtx;
3686 // Check if we know that this pointer can be speculatively accessed.
3687 if (canAlwaysBeHoisted(MA, StmtInvalidCtxIsEmpty, MAInvalidCtxIsEmpty,
3688 NonHoistableCtxIsEmpty)) {
3689 MACtx = isl::set::universe(DomainCtx.get_space());
3690 } else {
3691 MACtx = DomainCtx;
3692 MACtx = MACtx.subtract(MAInvalidCtx.unite(NHCtx));
3693 MACtx = MACtx.gist_params(getContext());
3694 }
3695
3696 bool Consolidated = false;
3697 for (auto &IAClass : InvariantEquivClasses) {
3698 if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType)
3699 continue;
3700
3701 // If the pointer and the type is equal check if the access function wrt.
3702 // to the domain is equal too. It can happen that the domain fixes
3703 // parameter values and these can be different for distinct part of the
3704 // SCoP. If this happens we cannot consolidate the loads but need to
3705 // create a new invariant load equivalence class.
3706 auto &MAs = IAClass.InvariantAccesses;
3707 if (!MAs.empty()) {
3708 auto *LastMA = MAs.front();
3709
3710 isl::set AR = MA->getAccessRelation().range();
3711 isl::set LastAR = LastMA->getAccessRelation().range();
3712 bool SameAR = AR.is_equal(LastAR);
3713
3714 if (!SameAR)
3715 continue;
3716 }
3717
3718 // Add MA to the list of accesses that are in this class.
3719 MAs.push_front(MA);
3720
3721 Consolidated = true;
3722
3723 // Unify the execution context of the class and this statement.
3724 isl::set IAClassDomainCtx = IAClass.ExecutionContext;
3725 if (IAClassDomainCtx)
3726 IAClassDomainCtx = IAClassDomainCtx.unite(MACtx).coalesce();
3727 else
3728 IAClassDomainCtx = MACtx;
3729 IAClass.ExecutionContext = IAClassDomainCtx;
3730 break;
3731 }
3732
3733 if (Consolidated)
3734 continue;
3735
3736 MACtx = MACtx.coalesce();
3737
3738 // If we did not consolidate MA, thus did not find an equivalence class
3739 // for it, we create a new one.
3740 InvariantEquivClasses.emplace_back(
3741 InvariantEquivClassTy{PointerSCEV, MemoryAccessList{MA}, MACtx, Ty});
3742 }
3743}
3744
3745/// Check if an access range is too complex.
3746///
3747/// An access range is too complex, if it contains either many disjuncts or
3748/// very complex expressions. As a simple heuristic, we assume if a set to
3749/// be too complex if the sum of existentially quantified dimensions and
3750/// set dimensions is larger than a threshold. This reliably detects both
3751/// sets with many disjuncts as well as sets with many divisions as they
3752/// arise in h264.
3753///
3754/// @param AccessRange The range to check for complexity.
3755///
3756/// @returns True if the access range is too complex.
3757static bool isAccessRangeTooComplex(isl::set AccessRange) {
3758 unsigned NumTotalDims = 0;
3759
3760 for (isl::basic_set BSet : AccessRange.get_basic_set_list()) {
3761 NumTotalDims += BSet.dim(isl::dim::div);
3762 NumTotalDims += BSet.dim(isl::dim::set);
3763 }
3764
3765 if (NumTotalDims > MaxDimensionsInAccessRange)
3766 return true;
3767
3768 return false;
3769}
3770
3771isl::set Scop::getNonHoistableCtx(MemoryAccess *Access, isl::union_map Writes) {
3772 // TODO: Loads that are not loop carried, hence are in a statement with
3773 // zero iterators, are by construction invariant, though we
3774 // currently "hoist" them anyway. This is necessary because we allow
3775 // them to be treated as parameters (e.g., in conditions) and our code
3776 // generation would otherwise use the old value.
3777
3778 auto &Stmt = *Access->getStatement();
3779 BasicBlock *BB = Stmt.getEntryBlock();
3780
3781 if (Access->isScalarKind() || Access->isWrite() || !Access->isAffine() ||
3782 Access->isMemoryIntrinsic())
3783 return nullptr;
3784
3785 // Skip accesses that have an invariant base pointer which is defined but
3786 // not loaded inside the SCoP. This can happened e.g., if a readnone call
3787 // returns a pointer that is used as a base address. However, as we want
3788 // to hoist indirect pointers, we allow the base pointer to be defined in
3789 // the region if it is also a memory access. Each ScopArrayInfo object
3790 // that has a base pointer origin has a base pointer that is loaded and
3791 // that it is invariant, thus it will be hoisted too. However, if there is
3792 // no base pointer origin we check that the base pointer is defined
3793 // outside the region.
3794 auto *LI = cast<LoadInst>(Access->getAccessInstruction());
3795 if (hasNonHoistableBasePtrInScop(Access, Writes))
3796 return nullptr;
3797
3798 isl::map AccessRelation = Access->getAccessRelation();
3799 assert(!AccessRelation.is_empty())((!AccessRelation.is_empty()) ? static_cast<void> (0) :
__assert_fail ("!AccessRelation.is_empty()", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 3799, __PRETTY_FUNCTION__))
;
3800
3801 if (AccessRelation.involves_dims(isl::dim::in, 0, Stmt.getNumIterators()))
3802 return nullptr;
3803
3804 AccessRelation = AccessRelation.intersect_domain(Stmt.getDomain());
3805 isl::set SafeToLoad;
3806
3807 auto &DL = getFunction().getParent()->getDataLayout();
3808 if (isSafeToLoadUnconditionally(LI->getPointerOperand(), LI->getAlignment(),
3809 DL)) {
3810 SafeToLoad = isl::set::universe(AccessRelation.get_space().range());
3811 } else if (BB != LI->getParent()) {
3812 // Skip accesses in non-affine subregions as they might not be executed
3813 // under the same condition as the entry of the non-affine subregion.
3814 return nullptr;
3815 } else {
3816 SafeToLoad = AccessRelation.range();
3817 }
3818
3819 if (isAccessRangeTooComplex(AccessRelation.range()))
3820 return nullptr;
3821
3822 isl::union_map Written = Writes.intersect_range(SafeToLoad);
3823 isl::set WrittenCtx = Written.params();
3824 bool IsWritten = !WrittenCtx.is_empty();
3825
3826 if (!IsWritten)
3827 return WrittenCtx;
3828
3829 WrittenCtx = WrittenCtx.remove_divs();
3830 bool TooComplex = WrittenCtx.n_basic_set() >= MaxDisjunctsInDomain;
3831 if (TooComplex || !isRequiredInvariantLoad(LI))
3832 return nullptr;
3833
3834 addAssumption(INVARIANTLOAD, WrittenCtx, LI->getDebugLoc(), AS_RESTRICTION,
3835 LI->getParent());
3836 return WrittenCtx;
3837}
3838
3839void Scop::verifyInvariantLoads() {
3840 auto &RIL = getRequiredInvariantLoads();
3841 for (LoadInst *LI : RIL) {
3842 assert(LI && contains(LI))((LI && contains(LI)) ? static_cast<void> (0) :
__assert_fail ("LI && contains(LI)", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 3842, __PRETTY_FUNCTION__))
;
3843 // If there exists a statement in the scop which has a memory access for
3844 // @p LI, then mark this scop as infeasible for optimization.
3845 for (ScopStmt &Stmt : Stmts)
3846 if (Stmt.getArrayAccessOrNULLFor(LI)) {
3847 invalidate(INVARIANTLOAD, LI->getDebugLoc(), LI->getParent());
3848 return;
3849 }
3850 }
3851}
3852
3853void Scop::hoistInvariantLoads() {
3854 if (!PollyInvariantLoadHoisting)
3855 return;
3856
3857 isl::union_map Writes = getWrites();
3858 for (ScopStmt &Stmt : *this) {
3859 InvariantAccessesTy InvariantAccesses;
3860
3861 for (MemoryAccess *Access : Stmt)
3862 if (isl::set NHCtx = getNonHoistableCtx(Access, Writes))
3863 InvariantAccesses.push_back({Access, NHCtx});
3864
3865 // Transfer the memory access from the statement to the SCoP.
3866 for (auto InvMA : InvariantAccesses)
3867 Stmt.removeMemoryAccess(InvMA.MA);
3868 addInvariantLoads(Stmt, InvariantAccesses);
3869 }
3870}
3871
3872/// Find the canonical scop array info object for a set of invariant load
3873/// hoisted loads. The canonical array is the one that corresponds to the
3874/// first load in the list of accesses which is used as base pointer of a
3875/// scop array.
3876static const ScopArrayInfo *findCanonicalArray(Scop *S,
3877 MemoryAccessList &Accesses) {
3878 for (MemoryAccess *Access : Accesses) {
3879 const ScopArrayInfo *CanonicalArray = S->getScopArrayInfoOrNull(
3880 Access->getAccessInstruction(), MemoryKind::Array);
3881 if (CanonicalArray)
3882 return CanonicalArray;
3883 }
3884 return nullptr;
3885}
3886
3887/// Check if @p Array severs as base array in an invariant load.
3888static bool isUsedForIndirectHoistedLoad(Scop *S, const ScopArrayInfo *Array) {
3889 for (InvariantEquivClassTy &EqClass2 : S->getInvariantAccesses())
3890 for (MemoryAccess *Access2 : EqClass2.InvariantAccesses)
3891 if (Access2->getScopArrayInfo() == Array)
3892 return true;
3893 return false;
3894}
3895
3896/// Replace the base pointer arrays in all memory accesses referencing @p Old,
3897/// with a reference to @p New.
3898static void replaceBasePtrArrays(Scop *S, const ScopArrayInfo *Old,
3899 const ScopArrayInfo *New) {
3900 for (ScopStmt &Stmt : *S)
3901 for (MemoryAccess *Access : Stmt) {
3902 if (Access->getLatestScopArrayInfo() != Old)
3903 continue;
3904
3905 isl::id Id = New->getBasePtrId();
3906 isl::map Map = Access->getAccessRelation();
3907 Map = Map.set_tuple_id(isl::dim::out, Id);
3908 Access->setAccessRelation(Map);
3909 }
3910}
3911
3912void Scop::canonicalizeDynamicBasePtrs() {
3913 for (InvariantEquivClassTy &EqClass : InvariantEquivClasses) {
3914 MemoryAccessList &BasePtrAccesses = EqClass.InvariantAccesses;
3915
3916 const ScopArrayInfo *CanonicalBasePtrSAI =
3917 findCanonicalArray(this, BasePtrAccesses);
3918
3919 if (!CanonicalBasePtrSAI)
3920 continue;
3921
3922 for (MemoryAccess *BasePtrAccess : BasePtrAccesses) {
3923 const ScopArrayInfo *BasePtrSAI = getScopArrayInfoOrNull(
3924 BasePtrAccess->getAccessInstruction(), MemoryKind::Array);
3925 if (!BasePtrSAI || BasePtrSAI == CanonicalBasePtrSAI ||
3926 !BasePtrSAI->isCompatibleWith(CanonicalBasePtrSAI))
3927 continue;
3928
3929 // we currently do not canonicalize arrays where some accesses are
3930 // hoisted as invariant loads. If we would, we need to update the access
3931 // function of the invariant loads as well. However, as this is not a
3932 // very common situation, we leave this for now to avoid further
3933 // complexity increases.
3934 if (isUsedForIndirectHoistedLoad(this, BasePtrSAI))
3935 continue;
3936
3937 replaceBasePtrArrays(this, BasePtrSAI, CanonicalBasePtrSAI);
3938 }
3939 }
3940}
3941
3942ScopArrayInfo *Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType,
3943 ArrayRef<const SCEV *> Sizes,
3944 MemoryKind Kind,
3945 const char *BaseName) {
3946 assert((BasePtr || BaseName) &&(((BasePtr || BaseName) && "BasePtr and BaseName can not be nullptr at the same time."
) ? static_cast<void> (0) : __assert_fail ("(BasePtr || BaseName) && \"BasePtr and BaseName can not be nullptr at the same time.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 3947, __PRETTY_FUNCTION__))
3947 "BasePtr and BaseName can not be nullptr at the same time.")(((BasePtr || BaseName) && "BasePtr and BaseName can not be nullptr at the same time."
) ? static_cast<void> (0) : __assert_fail ("(BasePtr || BaseName) && \"BasePtr and BaseName can not be nullptr at the same time.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 3947, __PRETTY_FUNCTION__))
;
3948 assert(!(BasePtr && BaseName) && "BaseName is redundant.")((!(BasePtr && BaseName) && "BaseName is redundant."
) ? static_cast<void> (0) : __assert_fail ("!(BasePtr && BaseName) && \"BaseName is redundant.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 3948, __PRETTY_FUNCTION__))
;
3949 auto &SAI = BasePtr ? ScopArrayInfoMap[std::make_pair(BasePtr, Kind)]
3950 : ScopArrayNameMap[BaseName];
3951 if (!SAI) {
3952 auto &DL = getFunction().getParent()->getDataLayout();
3953 SAI.reset(new ScopArrayInfo(BasePtr, ElementType, getIslCtx(), Sizes, Kind,
3954 DL, this, BaseName));
3955 ScopArrayInfoSet.insert(SAI.get());
3956 } else {
3957 SAI->updateElementType(ElementType);
3958 // In case of mismatching array sizes, we bail out by setting the run-time
3959 // context to false.
3960 if (!SAI->updateSizes(Sizes))
3961 invalidate(DELINEARIZATION, DebugLoc());
3962 }
3963 return SAI.get();
3964}
3965
3966ScopArrayInfo *Scop::createScopArrayInfo(Type *ElementType,
3967 const std::string &BaseName,
3968 const std::vector<unsigned> &Sizes) {
3969 auto *DimSizeType = Type::getInt64Ty(getSE()->getContext());
3970 std::vector<const SCEV *> SCEVSizes;
3971
3972 for (auto size : Sizes)
3973 if (size)
3974 SCEVSizes.push_back(getSE()->getConstant(DimSizeType, size, false));
3975 else
3976 SCEVSizes.push_back(nullptr);
3977
3978 auto *SAI = getOrCreateScopArrayInfo(nullptr, ElementType, SCEVSizes,
3979 MemoryKind::Array, BaseName.c_str());
3980 return SAI;
3981}
3982
3983const ScopArrayInfo *Scop::getScopArrayInfoOrNull(Value *BasePtr,
3984 MemoryKind Kind) {
3985 auto *SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)].get();
3986 return SAI;
3987}
3988
3989const ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr, MemoryKind Kind) {
3990 auto *SAI = getScopArrayInfoOrNull(BasePtr, Kind);
3991 assert(SAI && "No ScopArrayInfo available for this base pointer")((SAI && "No ScopArrayInfo available for this base pointer"
) ? static_cast<void> (0) : __assert_fail ("SAI && \"No ScopArrayInfo available for this base pointer\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 3991, __PRETTY_FUNCTION__))
;
3992 return SAI;
3993}
3994
3995std::string Scop::getContextStr() const { return getContext().to_str(); }
3996
3997std::string Scop::getAssumedContextStr() const {
3998 assert(AssumedContext && "Assumed context not yet built")((AssumedContext && "Assumed context not yet built") ?
static_cast<void> (0) : __assert_fail ("AssumedContext && \"Assumed context not yet built\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 3998, __PRETTY_FUNCTION__))
;
3999 return AssumedContext.to_str();
4000}
4001
4002std::string Scop::getInvalidContextStr() const {
4003 return InvalidContext.to_str();
4004}
4005
4006std::string Scop::getNameStr() const {
4007 std::string ExitName, EntryName;
4008 std::tie(EntryName, ExitName) = getEntryExitStr();
4009 return EntryName + "---" + ExitName;
4010}
4011
4012std::pair<std::string, std::string> Scop::getEntryExitStr() const {
4013 std::string ExitName, EntryName;
4014 raw_string_ostream ExitStr(ExitName);
4015 raw_string_ostream EntryStr(EntryName);
4016
4017 R.getEntry()->printAsOperand(EntryStr, false);
4018 EntryStr.str();
4019
4020 if (R.getExit()) {
4021 R.getExit()->printAsOperand(ExitStr, false);
4022 ExitStr.str();
4023 } else
4024 ExitName = "FunctionExit";
4025
4026 return std::make_pair(EntryName, ExitName);
4027}
4028
4029isl::set Scop::getContext() const { return Context; }
4030isl::space Scop::getParamSpace() const { return getContext().get_space(); }
4031
4032isl::space Scop::getFullParamSpace() const {
4033 std::vector<isl::id> FortranIDs;
4034 FortranIDs = getFortranArrayIds(arrays());
4035
4036 isl::space Space = isl::space::params_alloc(
4037 getIslCtx(), ParameterIds.size() + FortranIDs.size());
4038
4039 unsigned PDim = 0;
4040 for (const SCEV *Parameter : Parameters) {
4041 isl::id Id = getIdForParam(Parameter);
4042 Space = Space.set_dim_id(isl::dim::param, PDim++, Id);
4043 }
4044
4045 for (isl::id Id : FortranIDs)
4046 Space = Space.set_dim_id(isl::dim::param, PDim++, Id);
4047
4048 return Space;
4049}
4050
4051isl::set Scop::getAssumedContext() const {
4052 assert(AssumedContext && "Assumed context not yet built")((AssumedContext && "Assumed context not yet built") ?
static_cast<void> (0) : __assert_fail ("AssumedContext && \"Assumed context not yet built\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4052, __PRETTY_FUNCTION__))
;
4053 return AssumedContext;
4054}
4055
4056bool Scop::isProfitable(bool ScalarsAreUnprofitable) const {
4057 if (PollyProcessUnprofitable)
4058 return true;
4059
4060 if (isEmpty())
4061 return false;
4062
4063 unsigned OptimizableStmtsOrLoops = 0;
4064 for (auto &Stmt : *this) {
4065 if (Stmt.getNumIterators() == 0)
4066 continue;
4067
4068 bool ContainsArrayAccs = false;
4069 bool ContainsScalarAccs = false;
4070 for (auto *MA : Stmt) {
4071 if (MA->isRead())
4072 continue;
4073 ContainsArrayAccs |= MA->isLatestArrayKind();
4074 ContainsScalarAccs |= MA->isLatestScalarKind();
4075 }
4076
4077 if (!ScalarsAreUnprofitable || (ContainsArrayAccs && !ContainsScalarAccs))
4078 OptimizableStmtsOrLoops += Stmt.getNumIterators();
4079 }
4080
4081 return OptimizableStmtsOrLoops > 1;
4082}
4083
4084bool Scop::hasFeasibleRuntimeContext() const {
4085 auto PositiveContext = getAssumedContext();
4086 auto NegativeContext = getInvalidContext();
4087 PositiveContext = addNonEmptyDomainConstraints(PositiveContext);
4088 // addNonEmptyDomainConstraints returns null if ScopStmts have a null domain
4089 if (!PositiveContext)
4090 return false;
4091
4092 bool IsFeasible = !(PositiveContext.is_empty() ||
4093 PositiveContext.is_subset(NegativeContext));
4094 if (!IsFeasible)
4095 return false;
4096
4097 auto DomainContext = getDomains().params();
4098 IsFeasible = !DomainContext.is_subset(NegativeContext);
4099 IsFeasible &= !Context.is_subset(NegativeContext);
4100
4101 return IsFeasible;
4102}
4103
4104static std::string toString(AssumptionKind Kind) {
4105 switch (Kind) {
4106 case ALIASING:
4107 return "No-aliasing";
4108 case INBOUNDS:
4109 return "Inbounds";
4110 case WRAPPING:
4111 return "No-overflows";
4112 case UNSIGNED:
4113 return "Signed-unsigned";
4114 case COMPLEXITY:
4115 return "Low complexity";
4116 case PROFITABLE:
4117 return "Profitable";
4118 case ERRORBLOCK:
4119 return "No-error";
4120 case INFINITELOOP:
4121 return "Finite loop";
4122 case INVARIANTLOAD:
4123 return "Invariant load";
4124 case DELINEARIZATION:
4125 return "Delinearization";
4126 }
4127 llvm_unreachable("Unknown AssumptionKind!")::llvm::llvm_unreachable_internal("Unknown AssumptionKind!", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4127)
;
4128}
4129
4130bool Scop::isEffectiveAssumption(isl::set Set, AssumptionSign Sign) {
4131 if (Sign == AS_ASSUMPTION) {
4132 if (Context.is_subset(Set))
4133 return false;
4134
4135 if (AssumedContext.is_subset(Set))
4136 return false;
4137 } else {
4138 if (Set.is_disjoint(Context))
4139 return false;
4140
4141 if (Set.is_subset(InvalidContext))
4142 return false;
4143 }
4144 return true;
4145}
4146
4147bool Scop::trackAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
4148 AssumptionSign Sign, BasicBlock *BB) {
4149 if (PollyRemarksMinimal && !isEffectiveAssumption(Set, Sign))
4150 return false;
4151
4152 // Do never emit trivial assumptions as they only clutter the output.
4153 if (!PollyRemarksMinimal) {
4154 isl::set Univ;
4155 if (Sign == AS_ASSUMPTION)
4156 Univ = isl::set::universe(Set.get_space());
4157
4158 bool IsTrivial = (Sign == AS_RESTRICTION && Set.is_empty()) ||
4159 (Sign == AS_ASSUMPTION && Univ.is_equal(Set));
4160
4161 if (IsTrivial)
4162 return false;
4163 }
4164
4165 switch (Kind) {
4166 case ALIASING:
4167 AssumptionsAliasing++;
4168 break;
4169 case INBOUNDS:
4170 AssumptionsInbounds++;
4171 break;
4172 case WRAPPING:
4173 AssumptionsWrapping++;
4174 break;
4175 case UNSIGNED:
4176 AssumptionsUnsigned++;
4177 break;
4178 case COMPLEXITY:
4179 AssumptionsComplexity++;
4180 break;
4181 case PROFITABLE:
4182 AssumptionsUnprofitable++;
4183 break;
4184 case ERRORBLOCK:
4185 AssumptionsErrorBlock++;
4186 break;
4187 case INFINITELOOP:
4188 AssumptionsInfiniteLoop++;
4189 break;
4190 case INVARIANTLOAD:
4191 AssumptionsInvariantLoad++;
4192 break;
4193 case DELINEARIZATION:
4194 AssumptionsDelinearization++;
4195 break;
4196 }
4197
4198 auto Suffix = Sign == AS_ASSUMPTION ? " assumption:\t" : " restriction:\t";
4199 std::string Msg = toString(Kind) + Suffix + Set.to_str();
4200 if (BB)
4201 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE"polly-scops", "AssumpRestrict", Loc, BB)
4202 << Msg);
4203 else
4204 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE"polly-scops", "AssumpRestrict", Loc,
4205 R.getEntry())
4206 << Msg);
4207 return true;
4208}
4209
4210void Scop::addAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
4211 AssumptionSign Sign, BasicBlock *BB) {
4212 // Simplify the assumptions/restrictions first.
4213 Set = Set.gist_params(getContext());
4214
4215 if (!trackAssumption(Kind, Set, Loc, Sign, BB))
4216 return;
4217
4218 if (Sign == AS_ASSUMPTION)
4219 AssumedContext = AssumedContext.intersect(Set).coalesce();
4220 else
4221 InvalidContext = InvalidContext.unite(Set).coalesce();
4222}
4223
4224void Scop::recordAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
4225 AssumptionSign Sign, BasicBlock *BB) {
4226 assert((Set.is_params() || BB) &&(((Set.is_params() || BB) && "Assumptions without a basic block must be parameter sets"
) ? static_cast<void> (0) : __assert_fail ("(Set.is_params() || BB) && \"Assumptions without a basic block must be parameter sets\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4227, __PRETTY_FUNCTION__))
4227 "Assumptions without a basic block must be parameter sets")(((Set.is_params() || BB) && "Assumptions without a basic block must be parameter sets"
) ? static_cast<void> (0) : __assert_fail ("(Set.is_params() || BB) && \"Assumptions without a basic block must be parameter sets\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4227, __PRETTY_FUNCTION__))
;
4228 RecordedAssumptions.push_back({Kind, Sign, Set, Loc, BB});
4229}
4230
4231void Scop::addRecordedAssumptions() {
4232 while (!RecordedAssumptions.empty()) {
4233 Assumption AS = RecordedAssumptions.pop_back_val();
4234
4235 if (!AS.BB) {
4236 addAssumption(AS.Kind, AS.Set, AS.Loc, AS.Sign, nullptr /* BasicBlock */);
4237 continue;
4238 }
4239
4240 // If the domain was deleted the assumptions are void.
4241 isl_set *Dom = getDomainConditions(AS.BB).release();
4242 if (!Dom)
4243 continue;
4244
4245 // If a basic block was given use its domain to simplify the assumption.
4246 // In case of restrictions we know they only have to hold on the domain,
4247 // thus we can intersect them with the domain of the block. However, for
4248 // assumptions the domain has to imply them, thus:
4249 // _ _____
4250 // Dom => S <==> A v B <==> A - B
4251 //
4252 // To avoid the complement we will register A - B as a restriction not an
4253 // assumption.
4254 isl_set *S = AS.Set.copy();
4255 if (AS.Sign == AS_RESTRICTION)
4256 S = isl_set_params(isl_set_intersect(S, Dom));
4257 else /* (AS.Sign == AS_ASSUMPTION) */
4258 S = isl_set_params(isl_set_subtract(Dom, S));
4259
4260 addAssumption(AS.Kind, isl::manage(S), AS.Loc, AS_RESTRICTION, AS.BB);
4261 }
4262}
4263
4264void Scop::invalidate(AssumptionKind Kind, DebugLoc Loc, BasicBlock *BB) {
4265 LLVM_DEBUG(dbgs() << "Invalidate SCoP because of reason " << Kind << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "Invalidate SCoP because of reason "
<< Kind << "\n"; } } while (false)
;
4266 addAssumption(Kind, isl::set::empty(getParamSpace()), Loc, AS_ASSUMPTION, BB);
4267}
4268
4269isl::set Scop::getInvalidContext() const { return InvalidContext; }
4270
4271void Scop::printContext(raw_ostream &OS) const {
4272 OS << "Context:\n";
4273 OS.indent(4) << Context << "\n";
4274
4275 OS.indent(4) << "Assumed Context:\n";
4276 OS.indent(4) << AssumedContext << "\n";
4277
4278 OS.indent(4) << "Invalid Context:\n";
4279 OS.indent(4) << InvalidContext << "\n";
4280
4281 unsigned Dim = 0;
4282 for (const SCEV *Parameter : Parameters)
4283 OS.indent(4) << "p" << Dim++ << ": " << *Parameter << "\n";
4284}
4285
4286void Scop::printAliasAssumptions(raw_ostream &OS) const {
4287 int noOfGroups = 0;
4288 for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups) {
4289 if (Pair.second.size() == 0)
4290 noOfGroups += 1;
4291 else
4292 noOfGroups += Pair.second.size();
4293 }
4294
4295 OS.indent(4) << "Alias Groups (" << noOfGroups << "):\n";
4296 if (MinMaxAliasGroups.empty()) {
4297 OS.indent(8) << "n/a\n";
4298 return;
4299 }
4300
4301 for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups) {
4302
4303 // If the group has no read only accesses print the write accesses.
4304 if (Pair.second.empty()) {
4305 OS.indent(8) << "[[";
4306 for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) {
4307 OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second
4308 << ">";
4309 }
4310 OS << " ]]\n";
4311 }
4312
4313 for (const MinMaxAccessTy &MMAReadOnly : Pair.second) {
4314 OS.indent(8) << "[[";
4315 OS << " <" << MMAReadOnly.first << ", " << MMAReadOnly.second << ">";
4316 for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) {
4317 OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second
4318 << ">";
4319 }
4320 OS << " ]]\n";
4321 }
4322 }
4323}
4324
4325void Scop::printStatements(raw_ostream &OS, bool PrintInstructions) const {
4326 OS << "Statements {\n";
4327
4328 for (const ScopStmt &Stmt : *this) {
4329 OS.indent(4);
4330 Stmt.print(OS, PrintInstructions);
4331 }
4332
4333 OS.indent(4) << "}\n";
4334}
4335
4336void Scop::printArrayInfo(raw_ostream &OS) const {
4337 OS << "Arrays {\n";
4338
4339 for (auto &Array : arrays())
4340 Array->print(OS);
4341
4342 OS.indent(4) << "}\n";
4343
4344 OS.indent(4) << "Arrays (Bounds as pw_affs) {\n";
4345
4346 for (auto &Array : arrays())
4347 Array->print(OS, /* SizeAsPwAff */ true);
4348
4349 OS.indent(4) << "}\n";
4350}
4351
4352void Scop::print(raw_ostream &OS, bool PrintInstructions) const {
4353 OS.indent(4) << "Function: " << getFunction().getName() << "\n";
4354 OS.indent(4) << "Region: " << getNameStr() << "\n";
4355 OS.indent(4) << "Max Loop Depth: " << getMaxLoopDepth() << "\n";
4356 OS.indent(4) << "Invariant Accesses: {\n";
4357 for (const auto &IAClass : InvariantEquivClasses) {
4358 const auto &MAs = IAClass.InvariantAccesses;
4359 if (MAs.empty()) {
4360 OS.indent(12) << "Class Pointer: " << *IAClass.IdentifyingPointer << "\n";
4361 } else {
4362 MAs.front()->print(OS);
4363 OS.indent(12) << "Execution Context: " << IAClass.ExecutionContext
4364 << "\n";
4365 }
4366 }
4367 OS.indent(4) << "}\n";
4368 printContext(OS.indent(4));
4369 printArrayInfo(OS.indent(4));
4370 printAliasAssumptions(OS);
4371 printStatements(OS.indent(4), PrintInstructions);
4372}
4373
4374#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4375LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void Scop::dump() const { print(dbgs(), true); }
4376#endif
4377
4378isl::ctx Scop::getIslCtx() const { return IslCtx.get(); }
4379
4380__isl_give PWACtx Scop::getPwAff(const SCEV *E, BasicBlock *BB,
4381 bool NonNegative) {
4382 // First try to use the SCEVAffinator to generate a piecewise defined
4383 // affine function from @p E in the context of @p BB. If that tasks becomes to
4384 // complex the affinator might return a nullptr. In such a case we invalidate
4385 // the SCoP and return a dummy value. This way we do not need to add error
4386 // handling code to all users of this function.
4387 auto PWAC = Affinator.getPwAff(E, BB);
4388 if (PWAC.first) {
4389 // TODO: We could use a heuristic and either use:
4390 // SCEVAffinator::takeNonNegativeAssumption
4391 // or
4392 // SCEVAffinator::interpretAsUnsigned
4393 // to deal with unsigned or "NonNegative" SCEVs.
4394 if (NonNegative)
4395 Affinator.takeNonNegativeAssumption(PWAC);
4396 return PWAC;
4397 }
4398
4399 auto DL = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
4400 invalidate(COMPLEXITY, DL, BB);
4401 return Affinator.getPwAff(SE->getZero(E->getType()), BB);
4402}
4403
4404isl::union_set Scop::getDomains() const {
4405 isl_space *EmptySpace = isl_space_params_alloc(getIslCtx().get(), 0);
4406 isl_union_set *Domain = isl_union_set_empty(EmptySpace);
4407
4408 for (const ScopStmt &Stmt : *this)
4409 Domain = isl_union_set_add_set(Domain, Stmt.getDomain().release());
4410
4411 return isl::manage(Domain);
4412}
4413
4414isl::pw_aff Scop::getPwAffOnly(const SCEV *E, BasicBlock *BB) {
4415 PWACtx PWAC = getPwAff(E, BB);
4416 return PWAC.first;
4417}
4418
4419isl::union_map
4420Scop::getAccessesOfType(std::function<bool(MemoryAccess &)> Predicate) {
4421 isl::union_map Accesses = isl::union_map::empty(getParamSpace());
4422
4423 for (ScopStmt &Stmt : *this) {
4424 for (MemoryAccess *MA : Stmt) {
4425 if (!Predicate(*MA))
4426 continue;
4427
4428 isl::set Domain = Stmt.getDomain();
4429 isl::map AccessDomain = MA->getAccessRelation();
4430 AccessDomain = AccessDomain.intersect_domain(Domain);
4431 Accesses = Accesses.add_map(AccessDomain);
4432 }
4433 }
4434
4435 return Accesses.coalesce();
4436}
4437
4438isl::union_map Scop::getMustWrites() {
4439 return getAccessesOfType([](MemoryAccess &MA) { return MA.isMustWrite(); });
4440}
4441
4442isl::union_map Scop::getMayWrites() {
4443 return getAccessesOfType([](MemoryAccess &MA) { return MA.isMayWrite(); });
4444}
4445
4446isl::union_map Scop::getWrites() {
4447 return getAccessesOfType([](MemoryAccess &MA) { return MA.isWrite(); });
4448}
4449
4450isl::union_map Scop::getReads() {
4451 return getAccessesOfType([](MemoryAccess &MA) { return MA.isRead(); });
4452}
4453
4454isl::union_map Scop::getAccesses() {
4455 return getAccessesOfType([](MemoryAccess &MA) { return true; });
4456}
4457
4458isl::union_map Scop::getAccesses(ScopArrayInfo *Array) {
4459 return getAccessesOfType(
4460 [Array](MemoryAccess &MA) { return MA.getScopArrayInfo() == Array; });
4461}
4462
4463// Check whether @p Node is an extension node.
4464//
4465// @return true if @p Node is an extension node.
4466isl_bool isNotExtNode(__isl_keep isl_schedule_node *Node, void *User) {
4467 if (isl_schedule_node_get_type(Node) == isl_schedule_node_extension)
4468 return isl_bool_error;
4469 else
4470 return isl_bool_true;
4471}
4472
4473bool Scop::containsExtensionNode(isl::schedule Schedule) {
4474 return isl_schedule_foreach_schedule_node_top_down(
4475 Schedule.get(), isNotExtNode, nullptr) == isl_stat_error;
4476}
4477
4478isl::union_map Scop::getSchedule() const {
4479 auto Tree = getScheduleTree();
4480 if (containsExtensionNode(Tree))
4481 return nullptr;
4482
4483 return Tree.get_map();
4484}
4485
4486isl::schedule Scop::getScheduleTree() const {
4487 return Schedule.intersect_domain(getDomains());
4488}
4489
4490void Scop::setSchedule(isl::union_map NewSchedule) {
4491 auto S = isl::schedule::from_domain(getDomains());
4492 Schedule = S.insert_partial_schedule(
4493 isl::multi_union_pw_aff::from_union_map(NewSchedule));
4494 ScheduleModified = true;
4495}
4496
4497void Scop::setScheduleTree(isl::schedule NewSchedule) {
4498 Schedule = NewSchedule;
4499 ScheduleModified = true;
4500}
4501
4502bool Scop::restrictDomains(isl::union_set Domain) {
4503 bool Changed = false;
4504 for (ScopStmt &Stmt : *this) {
4505 isl::union_set StmtDomain = isl::union_set(Stmt.getDomain());
4506 isl::union_set NewStmtDomain = StmtDomain.intersect(Domain);
4507
4508 if (StmtDomain.is_subset(NewStmtDomain))
4509 continue;
4510
4511 Changed = true;
4512
4513 NewStmtDomain = NewStmtDomain.coalesce();
4514
4515 if (NewStmtDomain.is_empty())
4516 Stmt.restrictDomain(isl::set::empty(Stmt.getDomainSpace()));
4517 else
4518 Stmt.restrictDomain(isl::set(NewStmtDomain));
4519 }
4520 return Changed;
4521}
4522
4523ScalarEvolution *Scop::getSE() const { return SE; }
4524
4525// Create an isl_multi_union_aff that defines an identity mapping from the
4526// elements of USet to their N-th dimension.
4527//
4528// # Example:
4529//
4530// Domain: { A[i,j]; B[i,j,k] }
4531// N: 1
4532//
4533// Resulting Mapping: { {A[i,j] -> [(j)]; B[i,j,k] -> [(j)] }
4534//
4535// @param USet A union set describing the elements for which to generate a
4536// mapping.
4537// @param N The dimension to map to.
4538// @returns A mapping from USet to its N-th dimension.
4539static isl::multi_union_pw_aff mapToDimension(isl::union_set USet, int N) {
4540 assert(N >= 0)((N >= 0) ? static_cast<void> (0) : __assert_fail ("N >= 0"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4540, __PRETTY_FUNCTION__))
;
4541 assert(USet)((USet) ? static_cast<void> (0) : __assert_fail ("USet"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4541, __PRETTY_FUNCTION__))
;
4542 assert(!USet.is_empty())((!USet.is_empty()) ? static_cast<void> (0) : __assert_fail
("!USet.is_empty()", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4542, __PRETTY_FUNCTION__))
;
4543
4544 auto Result = isl::union_pw_multi_aff::empty(USet.get_space());
4545
4546 for (isl::set S : USet.get_set_list()) {
4547 int Dim = S.dim(isl::dim::set);
4548 auto PMA = isl::pw_multi_aff::project_out_map(S.get_space(), isl::dim::set,
4549 N, Dim - N);
4550 if (N > 1)
4551 PMA = PMA.drop_dims(isl::dim::out, 0, N - 1);
4552
4553 Result = Result.add_pw_multi_aff(PMA);
4554 }
4555
4556 return isl::multi_union_pw_aff(isl::union_pw_multi_aff(Result));
4557}
4558
4559void Scop::addScopStmt(BasicBlock *BB, StringRef Name, Loop *SurroundingLoop,
4560 std::vector<Instruction *> Instructions) {
4561 assert(BB && "Unexpected nullptr!")((BB && "Unexpected nullptr!") ? static_cast<void>
(0) : __assert_fail ("BB && \"Unexpected nullptr!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4561, __PRETTY_FUNCTION__))
;
4562 Stmts.emplace_back(*this, *BB, Name, SurroundingLoop, Instructions);
4563 auto *Stmt = &Stmts.back();
4564 StmtMap[BB].push_back(Stmt);
4565 for (Instruction *Inst : Instructions) {
4566 assert(!InstStmtMap.count(Inst) &&((!InstStmtMap.count(Inst) && "Unexpected statement corresponding to the instruction."
) ? static_cast<void> (0) : __assert_fail ("!InstStmtMap.count(Inst) && \"Unexpected statement corresponding to the instruction.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4567, __PRETTY_FUNCTION__))
4567 "Unexpected statement corresponding to the instruction.")((!InstStmtMap.count(Inst) && "Unexpected statement corresponding to the instruction."
) ? static_cast<void> (0) : __assert_fail ("!InstStmtMap.count(Inst) && \"Unexpected statement corresponding to the instruction.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4567, __PRETTY_FUNCTION__))
;
4568 InstStmtMap[Inst] = Stmt;
4569 }
4570}
4571
4572void Scop::addScopStmt(Region *R, StringRef Name, Loop *SurroundingLoop,
4573 std::vector<Instruction *> Instructions) {
4574 assert(R && "Unexpected nullptr!")((R && "Unexpected nullptr!") ? static_cast<void>
(0) : __assert_fail ("R && \"Unexpected nullptr!\"",
"/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4574, __PRETTY_FUNCTION__))
;
4575 Stmts.emplace_back(*this, *R, Name, SurroundingLoop, Instructions);
4576 auto *Stmt = &Stmts.back();
4577
4578 for (Instruction *Inst : Instructions) {
4579 assert(!InstStmtMap.count(Inst) &&((!InstStmtMap.count(Inst) && "Unexpected statement corresponding to the instruction."
) ? static_cast<void> (0) : __assert_fail ("!InstStmtMap.count(Inst) && \"Unexpected statement corresponding to the instruction.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4580, __PRETTY_FUNCTION__))
4580 "Unexpected statement corresponding to the instruction.")((!InstStmtMap.count(Inst) && "Unexpected statement corresponding to the instruction."
) ? static_cast<void> (0) : __assert_fail ("!InstStmtMap.count(Inst) && \"Unexpected statement corresponding to the instruction.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4580, __PRETTY_FUNCTION__))
;
4581 InstStmtMap[Inst] = Stmt;
4582 }
4583
4584 for (BasicBlock *BB : R->blocks()) {
4585 StmtMap[BB].push_back(Stmt);
4586 if (BB == R->getEntry())
4587 continue;
4588 for (Instruction &Inst : *BB) {
4589 assert(!InstStmtMap.count(&Inst) &&((!InstStmtMap.count(&Inst) && "Unexpected statement corresponding to the instruction."
) ? static_cast<void> (0) : __assert_fail ("!InstStmtMap.count(&Inst) && \"Unexpected statement corresponding to the instruction.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4590, __PRETTY_FUNCTION__))
4590 "Unexpected statement corresponding to the instruction.")((!InstStmtMap.count(&Inst) && "Unexpected statement corresponding to the instruction."
) ? static_cast<void> (0) : __assert_fail ("!InstStmtMap.count(&Inst) && \"Unexpected statement corresponding to the instruction.\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4590, __PRETTY_FUNCTION__))
;
4591 InstStmtMap[&Inst] = Stmt;
4592 }
4593 }
4594}
4595
4596ScopStmt *Scop::addScopStmt(isl::map SourceRel, isl::map TargetRel,
4597 isl::set Domain) {
4598#ifndef NDEBUG
4599 isl::set SourceDomain = SourceRel.domain();
4600 isl::set TargetDomain = TargetRel.domain();
4601 assert(Domain.is_subset(TargetDomain) &&((Domain.is_subset(TargetDomain) && "Target access not defined for complete statement domain"
) ? static_cast<void> (0) : __assert_fail ("Domain.is_subset(TargetDomain) && \"Target access not defined for complete statement domain\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4602, __PRETTY_FUNCTION__))
4602 "Target access not defined for complete statement domain")((Domain.is_subset(TargetDomain) && "Target access not defined for complete statement domain"
) ? static_cast<void> (0) : __assert_fail ("Domain.is_subset(TargetDomain) && \"Target access not defined for complete statement domain\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4602, __PRETTY_FUNCTION__))
;
4603 assert(Domain.is_subset(SourceDomain) &&((Domain.is_subset(SourceDomain) && "Source access not defined for complete statement domain"
) ? static_cast<void> (0) : __assert_fail ("Domain.is_subset(SourceDomain) && \"Source access not defined for complete statement domain\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4604, __PRETTY_FUNCTION__))
4604 "Source access not defined for complete statement domain")((Domain.is_subset(SourceDomain) && "Source access not defined for complete statement domain"
) ? static_cast<void> (0) : __assert_fail ("Domain.is_subset(SourceDomain) && \"Source access not defined for complete statement domain\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4604, __PRETTY_FUNCTION__))
;
4605#endif
4606 Stmts.emplace_back(*this, SourceRel, TargetRel, Domain);
4607 CopyStmtsNum++;
4608 return &(Stmts.back());
4609}
4610
4611void Scop::buildSchedule(LoopInfo &LI) {
4612 Loop *L = getLoopSurroundingScop(*this, LI);
4613 LoopStackTy LoopStack({LoopStackElementTy(L, nullptr, 0)});
4614 buildSchedule(getRegion().getNode(), LoopStack, LI);
4615 assert(LoopStack.size() == 1 && LoopStack.back().L == L)((LoopStack.size() == 1 && LoopStack.back().L == L) ?
static_cast<void> (0) : __assert_fail ("LoopStack.size() == 1 && LoopStack.back().L == L"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4615, __PRETTY_FUNCTION__))
;
4616 Schedule = LoopStack[0].Schedule;
4617}
4618
4619/// To generate a schedule for the elements in a Region we traverse the Region
4620/// in reverse-post-order and add the contained RegionNodes in traversal order
4621/// to the schedule of the loop that is currently at the top of the LoopStack.
4622/// For loop-free codes, this results in a correct sequential ordering.
4623///
4624/// Example:
4625/// bb1(0)
4626/// / \.
4627/// bb2(1) bb3(2)
4628/// \ / \.
4629/// bb4(3) bb5(4)
4630/// \ /
4631/// bb6(5)
4632///
4633/// Including loops requires additional processing. Whenever a loop header is
4634/// encountered, the corresponding loop is added to the @p LoopStack. Starting
4635/// from an empty schedule, we first process all RegionNodes that are within
4636/// this loop and complete the sequential schedule at this loop-level before
4637/// processing about any other nodes. To implement this
4638/// loop-nodes-first-processing, the reverse post-order traversal is
4639/// insufficient. Hence, we additionally check if the traversal yields
4640/// sub-regions or blocks that are outside the last loop on the @p LoopStack.
4641/// These region-nodes are then queue and only traverse after the all nodes
4642/// within the current loop have been processed.
4643void Scop::buildSchedule(Region *R, LoopStackTy &LoopStack, LoopInfo &LI) {
4644 Loop *OuterScopLoop = getLoopSurroundingScop(*this, LI);
4645
4646 ReversePostOrderTraversal<Region *> RTraversal(R);
4647 std::deque<RegionNode *> WorkList(RTraversal.begin(), RTraversal.end());
4648 std::deque<RegionNode *> DelayList;
4649 bool LastRNWaiting = false;
4650
4651 // Iterate over the region @p R in reverse post-order but queue
4652 // sub-regions/blocks iff they are not part of the last encountered but not
4653 // completely traversed loop. The variable LastRNWaiting is a flag to indicate
4654 // that we queued the last sub-region/block from the reverse post-order
4655 // iterator. If it is set we have to explore the next sub-region/block from
4656 // the iterator (if any) to guarantee progress. If it is not set we first try
4657 // the next queued sub-region/blocks.
4658 while (!WorkList.empty() || !DelayList.empty()) {
4659 RegionNode *RN;
4660
4661 if ((LastRNWaiting && !WorkList.empty()) || DelayList.empty()) {
4662 RN = WorkList.front();
4663 WorkList.pop_front();
4664 LastRNWaiting = false;
4665 } else {
4666 RN = DelayList.front();
4667 DelayList.pop_front();
4668 }
4669
4670 Loop *L = getRegionNodeLoop(RN, LI);
4671 if (!contains(L))
4672 L = OuterScopLoop;
4673
4674 Loop *LastLoop = LoopStack.back().L;
4675 if (LastLoop != L) {
4676 if (LastLoop && !LastLoop->contains(L)) {
4677 LastRNWaiting = true;
4678 DelayList.push_back(RN);
4679 continue;
4680 }
4681 LoopStack.push_back({L, nullptr, 0});
4682 }
4683 buildSchedule(RN, LoopStack, LI);
4684 }
4685}
4686
4687void Scop::buildSchedule(RegionNode *RN, LoopStackTy &LoopStack, LoopInfo &LI) {
4688 if (RN->isSubRegion()) {
4689 auto *LocalRegion = RN->getNodeAs<Region>();
4690 if (!isNonAffineSubRegion(LocalRegion)) {
4691 buildSchedule(LocalRegion, LoopStack, LI);
4692 return;
4693 }
4694 }
4695
4696 assert(LoopStack.rbegin() != LoopStack.rend())((LoopStack.rbegin() != LoopStack.rend()) ? static_cast<void
> (0) : __assert_fail ("LoopStack.rbegin() != LoopStack.rend()"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4696, __PRETTY_FUNCTION__))
;
4697 auto LoopData = LoopStack.rbegin();
4698 LoopData->NumBlocksProcessed += getNumBlocksInRegionNode(RN);
4699
4700 for (auto *Stmt : getStmtListFor(RN)) {
4701 isl::union_set UDomain{Stmt->getDomain()};
4702 auto StmtSchedule = isl::schedule::from_domain(UDomain);
4703 LoopData->Schedule = combineInSequence(LoopData->Schedule, StmtSchedule);
4704 }
4705
4706 // Check if we just processed the last node in this loop. If we did, finalize
4707 // the loop by:
4708 //
4709 // - adding new schedule dimensions
4710 // - folding the resulting schedule into the parent loop schedule
4711 // - dropping the loop schedule from the LoopStack.
4712 //
4713 // Then continue to check surrounding loops, which might also have been
4714 // completed by this node.
4715 size_t Dimension = LoopStack.size();
4716 while (LoopData->L &&
4717 LoopData->NumBlocksProcessed == getNumBlocksInLoop(LoopData->L)) {
4718 isl::schedule Schedule = LoopData->Schedule;
4719 auto NumBlocksProcessed = LoopData->NumBlocksProcessed;
4720
4721 assert(std::next(LoopData) != LoopStack.rend())((std::next(LoopData) != LoopStack.rend()) ? static_cast<void
> (0) : __assert_fail ("std::next(LoopData) != LoopStack.rend()"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4721, __PRETTY_FUNCTION__))
;
4722 ++LoopData;
4723 --Dimension;
4724
4725 if (Schedule) {
4726 isl::union_set Domain = Schedule.get_domain();
4727 isl::multi_union_pw_aff MUPA = mapToDimension(Domain, Dimension);
4728 Schedule = Schedule.insert_partial_schedule(MUPA);
4729 LoopData->Schedule = combineInSequence(LoopData->Schedule, Schedule);
4730 }
4731
4732 LoopData->NumBlocksProcessed += NumBlocksProcessed;
4733 }
4734 // Now pop all loops processed up there from the LoopStack
4735 LoopStack.erase(LoopStack.begin() + Dimension, LoopStack.end());
4736}
4737
4738ArrayRef<ScopStmt *> Scop::getStmtListFor(BasicBlock *BB) const {
4739 auto StmtMapIt = StmtMap.find(BB);
4740 if (StmtMapIt == StmtMap.end())
4741 return {};
4742 return StmtMapIt->second;
4743}
4744
4745ScopStmt *Scop::getIncomingStmtFor(const Use &U) const {
4746 auto *PHI = cast<PHINode>(U.getUser());
4747 BasicBlock *IncomingBB = PHI->getIncomingBlock(U);
4748
4749 // If the value is a non-synthesizable from the incoming block, use the
4750 // statement that contains it as user statement.
4751 if (auto *IncomingInst = dyn_cast<Instruction>(U.get())) {
4752 if (IncomingInst->getParent() == IncomingBB) {
4753 if (ScopStmt *IncomingStmt = getStmtFor(IncomingInst))
4754 return IncomingStmt;
4755 }
4756 }
4757
4758 // Otherwise, use the epilogue/last statement.
4759 return getLastStmtFor(IncomingBB);
4760}
4761
4762ScopStmt *Scop::getLastStmtFor(BasicBlock *BB) const {
4763 ArrayRef<ScopStmt *> StmtList = getStmtListFor(BB);
4764 if (!StmtList.empty())
4765 return StmtList.back();
4766 return nullptr;
4767}
4768
4769ArrayRef<ScopStmt *> Scop::getStmtListFor(RegionNode *RN) const {
4770 if (RN->isSubRegion())
4771 return getStmtListFor(RN->getNodeAs<Region>());
4772 return getStmtListFor(RN->getNodeAs<BasicBlock>());
4773}
4774
4775ArrayRef<ScopStmt *> Scop::getStmtListFor(Region *R) const {
4776 return getStmtListFor(R->getEntry());
4777}
4778
4779int Scop::getRelativeLoopDepth(const Loop *L) const {
4780 if (!L || !R.contains(L))
4781 return -1;
4782 // outermostLoopInRegion always returns nullptr for top level regions
4783 if (R.isTopLevelRegion()) {
4784 // LoopInfo's depths start at 1, we start at 0
4785 return L->getLoopDepth() - 1;
4786 } else {
4787 Loop *OuterLoop = R.outermostLoopInRegion(const_cast<Loop *>(L));
4788 assert(OuterLoop)((OuterLoop) ? static_cast<void> (0) : __assert_fail ("OuterLoop"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4788, __PRETTY_FUNCTION__))
;
4789 return L->getLoopDepth() - OuterLoop->getLoopDepth();
4790 }
4791}
4792
4793ScopArrayInfo *Scop::getArrayInfoByName(const std::string BaseName) {
4794 for (auto &SAI : arrays()) {
4795 if (SAI->getName() == BaseName)
4796 return SAI;
4797 }
4798 return nullptr;
4799}
4800
4801void Scop::addAccessData(MemoryAccess *Access) {
4802 const ScopArrayInfo *SAI = Access->getOriginalScopArrayInfo();
4803 assert(SAI && "can only use after access relations have been constructed")((SAI && "can only use after access relations have been constructed"
) ? static_cast<void> (0) : __assert_fail ("SAI && \"can only use after access relations have been constructed\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4803, __PRETTY_FUNCTION__))
;
4804
4805 if (Access->isOriginalValueKind() && Access->isRead())
4806 ValueUseAccs[SAI].push_back(Access);
4807 else if (Access->isOriginalAnyPHIKind() && Access->isWrite())
4808 PHIIncomingAccs[SAI].push_back(Access);
4809}
4810
4811void Scop::removeAccessData(MemoryAccess *Access) {
4812 if (Access->isOriginalValueKind() && Access->isWrite()) {
4813 ValueDefAccs.erase(Access->getAccessValue());
4814 } else if (Access->isOriginalValueKind() && Access->isRead()) {
4815 auto &Uses = ValueUseAccs[Access->getScopArrayInfo()];
4816 auto NewEnd = std::remove(Uses.begin(), Uses.end(), Access);
4817 Uses.erase(NewEnd, Uses.end());
4818 } else if (Access->isOriginalPHIKind() && Access->isRead()) {
4819 PHINode *PHI = cast<PHINode>(Access->getAccessInstruction());
4820 PHIReadAccs.erase(PHI);
4821 } else if (Access->isOriginalAnyPHIKind() && Access->isWrite()) {
4822 auto &Incomings = PHIIncomingAccs[Access->getScopArrayInfo()];
4823 auto NewEnd = std::remove(Incomings.begin(), Incomings.end(), Access);
4824 Incomings.erase(NewEnd, Incomings.end());
4825 }
4826}
4827
4828MemoryAccess *Scop::getValueDef(const ScopArrayInfo *SAI) const {
4829 assert(SAI->isValueKind())((SAI->isValueKind()) ? static_cast<void> (0) : __assert_fail
("SAI->isValueKind()", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4829, __PRETTY_FUNCTION__))
;
4830
4831 Instruction *Val = dyn_cast<Instruction>(SAI->getBasePtr());
4832 if (!Val)
4833 return nullptr;
4834
4835 return ValueDefAccs.lookup(Val);
4836}
4837
4838ArrayRef<MemoryAccess *> Scop::getValueUses(const ScopArrayInfo *SAI) const {
4839 assert(SAI->isValueKind())((SAI->isValueKind()) ? static_cast<void> (0) : __assert_fail
("SAI->isValueKind()", "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4839, __PRETTY_FUNCTION__))
;
4840 auto It = ValueUseAccs.find(SAI);
4841 if (It == ValueUseAccs.end())
4842 return {};
4843 return It->second;
4844}
4845
4846MemoryAccess *Scop::getPHIRead(const ScopArrayInfo *SAI) const {
4847 assert(SAI->isPHIKind() || SAI->isExitPHIKind())((SAI->isPHIKind() || SAI->isExitPHIKind()) ? static_cast
<void> (0) : __assert_fail ("SAI->isPHIKind() || SAI->isExitPHIKind()"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4847, __PRETTY_FUNCTION__))
;
4848
4849 if (SAI->isExitPHIKind())
4850 return nullptr;
4851
4852 PHINode *PHI = cast<PHINode>(SAI->getBasePtr());
4853 return PHIReadAccs.lookup(PHI);
4854}
4855
4856ArrayRef<MemoryAccess *> Scop::getPHIIncomings(const ScopArrayInfo *SAI) const {
4857 assert(SAI->isPHIKind() || SAI->isExitPHIKind())((SAI->isPHIKind() || SAI->isExitPHIKind()) ? static_cast
<void> (0) : __assert_fail ("SAI->isPHIKind() || SAI->isExitPHIKind()"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4857, __PRETTY_FUNCTION__))
;
4858 auto It = PHIIncomingAccs.find(SAI);
4859 if (It == PHIIncomingAccs.end())
4860 return {};
4861 return It->second;
4862}
4863
4864bool Scop::isEscaping(Instruction *Inst) {
4865 assert(contains(Inst) && "The concept of escaping makes only sense for "((contains(Inst) && "The concept of escaping makes only sense for "
"values defined inside the SCoP") ? static_cast<void> (
0) : __assert_fail ("contains(Inst) && \"The concept of escaping makes only sense for \" \"values defined inside the SCoP\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4866, __PRETTY_FUNCTION__))
4866 "values defined inside the SCoP")((contains(Inst) && "The concept of escaping makes only sense for "
"values defined inside the SCoP") ? static_cast<void> (
0) : __assert_fail ("contains(Inst) && \"The concept of escaping makes only sense for \" \"values defined inside the SCoP\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4866, __PRETTY_FUNCTION__))
;
4867
4868 for (Use &Use : Inst->uses()) {
4869 BasicBlock *UserBB = getUseBlock(Use);
4870 if (!contains(UserBB))
4871 return true;
4872
4873 // When the SCoP region exit needs to be simplified, PHIs in the region exit
4874 // move to a new basic block such that its incoming blocks are not in the
4875 // SCoP anymore.
4876 if (hasSingleExitEdge() && isa<PHINode>(Use.getUser()) &&
4877 isExit(cast<PHINode>(Use.getUser())->getParent()))
4878 return true;
4879 }
4880 return false;
4881}
4882
4883Scop::ScopStatistics Scop::getStatistics() const {
4884 ScopStatistics Result;
4885#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS1)
4886 auto LoopStat = ScopDetection::countBeneficialLoops(&R, *SE, *getLI(), 0);
4887
4888 int NumTotalLoops = LoopStat.NumLoops;
4889 Result.NumBoxedLoops = getBoxedLoops().size();
4890 Result.NumAffineLoops = NumTotalLoops - Result.NumBoxedLoops;
4891
4892 for (const ScopStmt &Stmt : *this) {
4893 isl::set Domain = Stmt.getDomain().intersect_params(getContext());
4894 bool IsInLoop = Stmt.getNumIterators() >= 1;
4895 for (MemoryAccess *MA : Stmt) {
4896 if (!MA->isWrite())
4897 continue;
4898
4899 if (MA->isLatestValueKind()) {
4900 Result.NumValueWrites += 1;
4901 if (IsInLoop)
4902 Result.NumValueWritesInLoops += 1;
4903 }
4904
4905 if (MA->isLatestAnyPHIKind()) {
4906 Result.NumPHIWrites += 1;
4907 if (IsInLoop)
4908 Result.NumPHIWritesInLoops += 1;
4909 }
4910
4911 isl::set AccSet =
4912 MA->getAccessRelation().intersect_domain(Domain).range();
4913 if (AccSet.is_singleton()) {
4914 Result.NumSingletonWrites += 1;
4915 if (IsInLoop)
4916 Result.NumSingletonWritesInLoops += 1;
4917 }
4918 }
4919 }
4920#endif
4921 return Result;
4922}
4923
4924raw_ostream &polly::operator<<(raw_ostream &OS, const Scop &scop) {
4925 scop.print(OS, PollyPrintInstructions);
4926 return OS;
4927}
4928
4929//===----------------------------------------------------------------------===//
4930void ScopInfoRegionPass::getAnalysisUsage(AnalysisUsage &AU) const {
4931 AU.addRequired<LoopInfoWrapperPass>();
4932 AU.addRequired<RegionInfoPass>();
4933 AU.addRequired<DominatorTreeWrapperPass>();
4934 AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
4935 AU.addRequiredTransitive<ScopDetectionWrapperPass>();
4936 AU.addRequired<AAResultsWrapperPass>();
4937 AU.addRequired<AssumptionCacheTracker>();
4938 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
4939 AU.setPreservesAll();
4940}
4941
4942void updateLoopCountStatistic(ScopDetection::LoopStats Stats,
4943 Scop::ScopStatistics ScopStats) {
4944 assert(Stats.NumLoops == ScopStats.NumAffineLoops + ScopStats.NumBoxedLoops)((Stats.NumLoops == ScopStats.NumAffineLoops + ScopStats.NumBoxedLoops
) ? static_cast<void> (0) : __assert_fail ("Stats.NumLoops == ScopStats.NumAffineLoops + ScopStats.NumBoxedLoops"
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 4944, __PRETTY_FUNCTION__))
;
4945
4946 NumScops++;
4947 NumLoopsInScop += Stats.NumLoops;
4948 MaxNumLoopsInScop =
4949 std::max(MaxNumLoopsInScop.getValue(), (unsigned)Stats.NumLoops);
4950
4951 if (Stats.MaxDepth == 0)
4952 NumScopsDepthZero++;
4953 else if (Stats.MaxDepth == 1)
4954 NumScopsDepthOne++;
4955 else if (Stats.MaxDepth == 2)
4956 NumScopsDepthTwo++;
4957 else if (Stats.MaxDepth == 3)
4958 NumScopsDepthThree++;
4959 else if (Stats.MaxDepth == 4)
4960 NumScopsDepthFour++;
4961 else if (Stats.MaxDepth == 5)
4962 NumScopsDepthFive++;
4963 else
4964 NumScopsDepthLarger++;
4965
4966 NumAffineLoops += ScopStats.NumAffineLoops;
4967 NumBoxedLoops += ScopStats.NumBoxedLoops;
4968
4969 NumValueWrites += ScopStats.NumValueWrites;
4970 NumValueWritesInLoops += ScopStats.NumValueWritesInLoops;
4971 NumPHIWrites += ScopStats.NumPHIWrites;
4972 NumPHIWritesInLoops += ScopStats.NumPHIWritesInLoops;
4973 NumSingletonWrites += ScopStats.NumSingletonWrites;
4974 NumSingletonWritesInLoops += ScopStats.NumSingletonWritesInLoops;
4975}
4976
4977bool ScopInfoRegionPass::runOnRegion(Region *R, RGPassManager &RGM) {
4978 auto &SD = getAnalysis<ScopDetectionWrapperPass>().getSD();
4979
4980 if (!SD.isMaxRegionInScop(*R))
4981 return false;
4982
4983 Function *F = R->getEntry()->getParent();
4984 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
4985 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
4986 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
4987 auto const &DL = F->getParent()->getDataLayout();
4988 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
4989 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(*F);
4990 auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
4991
4992 ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE, ORE);
4993 S = SB.getScop(); // take ownership of scop object
4994
4995#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS1)
4996 if (S) {
4997 ScopDetection::LoopStats Stats =
4998 ScopDetection::countBeneficialLoops(&S->getRegion(), SE, LI, 0);
4999 updateLoopCountStatistic(Stats, S->getStatistics());
5000 }
5001#endif
5002
5003 return false;
5004}
5005
5006void ScopInfoRegionPass::print(raw_ostream &OS, const Module *) const {
5007 if (S)
5008 S->print(OS, PollyPrintInstructions);
5009 else
5010 OS << "Invalid Scop!\n";
5011}
5012
5013char ScopInfoRegionPass::ID = 0;
5014
5015Pass *polly::createScopInfoRegionPassPass() { return new ScopInfoRegionPass(); }
5016
5017INITIALIZE_PASS_BEGIN(ScopInfoRegionPass, "polly-scops",static void *initializeScopInfoRegionPassPassOnce(PassRegistry
&Registry) {
5018 "Polly - Create polyhedral description of Scops", false,static void *initializeScopInfoRegionPassPassOnce(PassRegistry
&Registry) {
5019 false)static void *initializeScopInfoRegionPassPassOnce(PassRegistry
&Registry) {
;
5020INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);;
5021INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry);;
5022INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)initializeLoopInfoWrapperPassPass(Registry);;
5023INITIALIZE_PASS_DEPENDENCY(RegionInfoPass)initializeRegionInfoPassPass(Registry);;
5024INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)initializeScalarEvolutionWrapperPassPass(Registry);;
5025INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass)initializeScopDetectionWrapperPassPass(Registry);;
5026INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);;
5027INITIALIZE_PASS_END(ScopInfoRegionPass, "polly-scops",PassInfo *PI = new PassInfo( "Polly - Create polyhedral description of Scops"
, "polly-scops", &ScopInfoRegionPass::ID, PassInfo::NormalCtor_t
(callDefaultCtor<ScopInfoRegionPass>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeScopInfoRegionPassPassFlag; void llvm::initializeScopInfoRegionPassPass
(PassRegistry &Registry) { llvm::call_once(InitializeScopInfoRegionPassPassFlag
, initializeScopInfoRegionPassPassOnce, std::ref(Registry)); }
5028 "Polly - Create polyhedral description of Scops", false,PassInfo *PI = new PassInfo( "Polly - Create polyhedral description of Scops"
, "polly-scops", &ScopInfoRegionPass::ID, PassInfo::NormalCtor_t
(callDefaultCtor<ScopInfoRegionPass>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeScopInfoRegionPassPassFlag; void llvm::initializeScopInfoRegionPassPass
(PassRegistry &Registry) { llvm::call_once(InitializeScopInfoRegionPassPassFlag
, initializeScopInfoRegionPassPassOnce, std::ref(Registry)); }
5029 false)PassInfo *PI = new PassInfo( "Polly - Create polyhedral description of Scops"
, "polly-scops", &ScopInfoRegionPass::ID, PassInfo::NormalCtor_t
(callDefaultCtor<ScopInfoRegionPass>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeScopInfoRegionPassPassFlag; void llvm::initializeScopInfoRegionPassPass
(PassRegistry &Registry) { llvm::call_once(InitializeScopInfoRegionPassPassFlag
, initializeScopInfoRegionPassPassOnce, std::ref(Registry)); }
5030
5031//===----------------------------------------------------------------------===//
5032ScopInfo::ScopInfo(const DataLayout &DL, ScopDetection &SD, ScalarEvolution &SE,
5033 LoopInfo &LI, AliasAnalysis &AA, DominatorTree &DT,
5034 AssumptionCache &AC, OptimizationRemarkEmitter &ORE)
5035 : DL(DL), SD(SD), SE(SE), LI(LI), AA(AA), DT(DT), AC(AC), ORE(ORE) {
5036 recompute();
5037}
5038
5039void ScopInfo::recompute() {
5040 RegionToScopMap.clear();
5041 /// Create polyhedral description of scops for all the valid regions of a
5042 /// function.
5043 for (auto &It : SD) {
5044 Region *R = const_cast<Region *>(It);
5045 if (!SD.isMaxRegionInScop(*R))
5046 continue;
5047
5048 ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE, ORE);
5049 std::unique_ptr<Scop> S = SB.getScop();
5050 if (!S)
5051 continue;
5052#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS1)
5053 ScopDetection::LoopStats Stats =
5054 ScopDetection::countBeneficialLoops(&S->getRegion(), SE, LI, 0);
5055 updateLoopCountStatistic(Stats, S->getStatistics());
5056#endif
5057 bool Inserted = RegionToScopMap.insert({R, std::move(S)}).second;
5058 assert(Inserted && "Building Scop for the same region twice!")((Inserted && "Building Scop for the same region twice!"
) ? static_cast<void> (0) : __assert_fail ("Inserted && \"Building Scop for the same region twice!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/tools/polly/lib/Analysis/ScopInfo.cpp"
, 5058, __PRETTY_FUNCTION__))
;
5059 (void)Inserted;
5060 }
5061}
5062
5063bool ScopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
5064 FunctionAnalysisManager::Invalidator &Inv) {
5065 // Check whether the analysis, all analyses on functions have been preserved
5066 // or anything we're holding references to is being invalidated
5067 auto PAC = PA.getChecker<ScopInfoAnalysis>();
5068 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
5069 Inv.invalidate<ScopAnalysis>(F, PA) ||
5070 Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
5071 Inv.invalidate<LoopAnalysis>(F, PA) ||
5072 Inv.invalidate<AAManager>(F, PA) ||
5073 Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||
5074 Inv.invalidate<AssumptionAnalysis>(F, PA);
5075}
5076
5077AnalysisKey ScopInfoAnalysis::Key;
5078
5079ScopInfoAnalysis::Result ScopInfoAnalysis::run(Function &F,
5080 FunctionAnalysisManager &FAM) {
5081 auto &SD = FAM.getResult<ScopAnalysis>(F);
5082 auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
5083 auto &LI = FAM.getResult<LoopAnalysis>(F);
5084 auto &AA = FAM.getResult<AAManager>(F);
5085 auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
5086 auto &AC = FAM.getResult<AssumptionAnalysis>(F);
5087 auto &DL = F.getParent()->getDataLayout();
5088 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
5089 return {DL, SD, SE, LI, AA, DT, AC, ORE};
5090}
5091
5092PreservedAnalyses ScopInfoPrinterPass::run(Function &F,
5093 FunctionAnalysisManager &FAM) {
5094 auto &SI = FAM.getResult<ScopInfoAnalysis>(F);
5095 // Since the legacy PM processes Scops in bottom up, we print them in reverse
5096 // order here to keep the output persistent
5097 for (auto &It : reverse(SI)) {
5098 if (It.second)
5099 It.second->print(Stream, PollyPrintInstructions);
5100 else
5101 Stream << "Invalid Scop!\n";
5102 }
5103 return PreservedAnalyses::all();
5104}
5105
5106void ScopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
5107 AU.addRequired<LoopInfoWrapperPass>();
5108 AU.addRequired<RegionInfoPass>();
5109 AU.addRequired<DominatorTreeWrapperPass>();
5110 AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
5111 AU.addRequiredTransitive<ScopDetectionWrapperPass>();
5112 AU.addRequired<AAResultsWrapperPass>();
5113 AU.addRequired<AssumptionCacheTracker>();
5114 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
5115 AU.setPreservesAll();
5116}
5117
5118bool ScopInfoWrapperPass::runOnFunction(Function &F) {
5119 auto &SD = getAnalysis<ScopDetectionWrapperPass>().getSD();
5120 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
5121 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
5122 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
5123 auto const &DL = F.getParent()->getDataLayout();
5124 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
5125 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
5126 auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
5127
5128 Result.reset(new ScopInfo{DL, SD, SE, LI, AA, DT, AC, ORE});
5129 return false;
5130}
5131
5132void ScopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
5133 for (auto &It : *Result) {
5134 if (It.second)
5135 It.second->print(OS, PollyPrintInstructions);
5136 else
5137 OS << "Invalid Scop!\n";
5138 }
5139}
5140
5141char ScopInfoWrapperPass::ID = 0;
5142
5143Pass *polly::createScopInfoWrapperPassPass() {
5144 return new ScopInfoWrapperPass();
5145}
5146
5147INITIALIZE_PASS_BEGIN(static void *initializeScopInfoWrapperPassPassOnce(PassRegistry
&Registry) {
5148 ScopInfoWrapperPass, "polly-function-scops",static void *initializeScopInfoWrapperPassPassOnce(PassRegistry
&Registry) {
5149 "Polly - Create polyhedral description of all Scops of a function", false,static void *initializeScopInfoWrapperPassPassOnce(PassRegistry
&Registry) {
5150 false)static void *initializeScopInfoWrapperPassPassOnce(PassRegistry
&Registry) {
;
5151INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);;
5152INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry);;
5153INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)initializeLoopInfoWrapperPassPass(Registry);;
5154INITIALIZE_PASS_DEPENDENCY(RegionInfoPass)initializeRegionInfoPassPass(Registry);;
5155INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)initializeScalarEvolutionWrapperPassPass(Registry);;
5156INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass)initializeScopDetectionWrapperPassPass(Registry);;
5157INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);;
5158INITIALIZE_PASS_END(PassInfo *PI = new PassInfo( "Polly - Create polyhedral description of all Scops of a function"
, "polly-function-scops", &ScopInfoWrapperPass::ID, PassInfo
::NormalCtor_t(callDefaultCtor<ScopInfoWrapperPass>), false
, false); Registry.registerPass(*PI, true); return PI; } static
llvm::once_flag InitializeScopInfoWrapperPassPassFlag; void llvm
::initializeScopInfoWrapperPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeScopInfoWrapperPassPassFlag, initializeScopInfoWrapperPassPassOnce
, std::ref(Registry)); }
5159 ScopInfoWrapperPass, "polly-function-scops",PassInfo *PI = new PassInfo( "Polly - Create polyhedral description of all Scops of a function"
, "polly-function-scops", &ScopInfoWrapperPass::ID, PassInfo
::NormalCtor_t(callDefaultCtor<ScopInfoWrapperPass>), false
, false); Registry.registerPass(*PI, true); return PI; } static
llvm::once_flag InitializeScopInfoWrapperPassPassFlag; void llvm
::initializeScopInfoWrapperPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeScopInfoWrapperPassPassFlag, initializeScopInfoWrapperPassPassOnce
, std::ref(Registry)); }
5160 "Polly - Create polyhedral description of all Scops of a function", false,PassInfo *PI = new PassInfo( "Polly - Create polyhedral description of all Scops of a function"
, "polly-function-scops", &ScopInfoWrapperPass::ID, PassInfo
::NormalCtor_t(callDefaultCtor<ScopInfoWrapperPass>), false
, false); Registry.registerPass(*PI, true); return PI; } static
llvm::once_flag InitializeScopInfoWrapperPassPassFlag; void llvm
::initializeScopInfoWrapperPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeScopInfoWrapperPassPassFlag, initializeScopInfoWrapperPassPassOnce
, std::ref(Registry)); }
5161 false)PassInfo *PI = new PassInfo( "Polly - Create polyhedral description of all Scops of a function"
, "polly-function-scops", &ScopInfoWrapperPass::ID, PassInfo
::NormalCtor_t(callDefaultCtor<ScopInfoWrapperPass>), false
, false); Registry.registerPass(*PI, true); return PI; } static
llvm::once_flag InitializeScopInfoWrapperPassPassFlag; void llvm
::initializeScopInfoWrapperPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeScopInfoWrapperPassPassFlag, initializeScopInfoWrapperPassPassOnce
, std::ref(Registry)); }