Bug Summary

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