Bug Summary

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