Bug Summary

File:tools/polly/lib/Analysis/ScopBuilder.cpp
Warning:line 1640, column 18
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 ScopBuilder.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/tools/polly/lib -I /build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib -I /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/tools/polly/include -I /build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/External/pet/include -I /build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-10~svn374877/tools/polly/include -I /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/include -I /build/llvm-toolchain-snapshot-10~svn374877/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.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++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/tools/polly/lib -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~svn374877=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fno-rtti -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fno-common -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2019-10-15-233810-7101-1 -x c++ /build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp
1//===- ScopBuilder.cpp ----------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Create a polyhedral description for a static control flow region.
10//
11// The pass creates a polyhedral description of the Scops detected by the SCoP
12// detection derived from their LLVM-IR code.
13//
14//===----------------------------------------------------------------------===//
15
16#include "polly/ScopBuilder.h"
17#include "polly/Options.h"
18#include "polly/ScopDetection.h"
19#include "polly/ScopInfo.h"
20#include "polly/Support/GICHelper.h"
21#include "polly/Support/ISLTools.h"
22#include "polly/Support/SCEVValidator.h"
23#include "polly/Support/ScopHelper.h"
24#include "polly/Support/VirtualInstruction.h"
25#include "llvm/ADT/ArrayRef.h"
26#include "llvm/ADT/EquivalenceClasses.h"
27#include "llvm/ADT/PostOrderIterator.h"
28#include "llvm/ADT/SmallSet.h"
29#include "llvm/ADT/Statistic.h"
30#include "llvm/Analysis/AliasAnalysis.h"
31#include "llvm/Analysis/AssumptionCache.h"
32#include "llvm/Analysis/Loads.h"
33#include "llvm/Analysis/LoopInfo.h"
34#include "llvm/Analysis/OptimizationRemarkEmitter.h"
35#include "llvm/Analysis/RegionInfo.h"
36#include "llvm/Analysis/RegionIterator.h"
37#include "llvm/Analysis/ScalarEvolution.h"
38#include "llvm/Analysis/ScalarEvolutionExpressions.h"
39#include "llvm/IR/BasicBlock.h"
40#include "llvm/IR/DataLayout.h"
41#include "llvm/IR/DebugLoc.h"
42#include "llvm/IR/DerivedTypes.h"
43#include "llvm/IR/Dominators.h"
44#include "llvm/IR/Function.h"
45#include "llvm/IR/InstrTypes.h"
46#include "llvm/IR/Instruction.h"
47#include "llvm/IR/Instructions.h"
48#include "llvm/IR/Type.h"
49#include "llvm/IR/Use.h"
50#include "llvm/IR/Value.h"
51#include "llvm/Support/CommandLine.h"
52#include "llvm/Support/Compiler.h"
53#include "llvm/Support/Debug.h"
54#include "llvm/Support/ErrorHandling.h"
55#include "llvm/Support/raw_ostream.h"
56#include <cassert>
57
58using namespace llvm;
59using namespace polly;
60
61#define DEBUG_TYPE"polly-scops" "polly-scops"
62
63STATISTIC(ScopFound, "Number of valid Scops")static llvm::Statistic ScopFound = {"polly-scops", "ScopFound"
, "Number of valid Scops"}
;
64STATISTIC(RichScopFound, "Number of Scops containing a loop")static llvm::Statistic RichScopFound = {"polly-scops", "RichScopFound"
, "Number of Scops containing a loop"}
;
65STATISTIC(InfeasibleScops,static llvm::Statistic InfeasibleScops = {"polly-scops", "InfeasibleScops"
, "Number of SCoPs with statically infeasible context."}
66 "Number of SCoPs with statically infeasible context.")static llvm::Statistic InfeasibleScops = {"polly-scops", "InfeasibleScops"
, "Number of SCoPs with statically infeasible context."}
;
67
68bool polly::ModelReadOnlyScalars;
69
70// The maximal number of dimensions we allow during invariant load construction.
71// More complex access ranges will result in very high compile time and are also
72// unlikely to result in good code. This value is very high and should only
73// trigger for corner cases (e.g., the "dct_luma" function in h264, SPEC2006).
74static int const MaxDimensionsInAccessRange = 9;
75
76static cl::opt<bool, true> XModelReadOnlyScalars(
77 "polly-analyze-read-only-scalars",
78 cl::desc("Model read-only scalar values in the scop description"),
79 cl::location(ModelReadOnlyScalars), cl::Hidden, cl::ZeroOrMore,
80 cl::init(true), cl::cat(PollyCategory));
81
82static cl::opt<int>
83 OptComputeOut("polly-analysis-computeout",
84 cl::desc("Bound the scop analysis by a maximal amount of "
85 "computational steps (0 means no bound)"),
86 cl::Hidden, cl::init(800000), cl::ZeroOrMore,
87 cl::cat(PollyCategory));
88
89static cl::opt<bool> PollyAllowDereferenceOfAllFunctionParams(
90 "polly-allow-dereference-of-all-function-parameters",
91 cl::desc(
92 "Treat all parameters to functions that are pointers as dereferencible."
93 " This is useful for invariant load hoisting, since we can generate"
94 " less runtime checks. This is only valid if all pointers to functions"
95 " are always initialized, so that Polly can choose to hoist"
96 " their loads. "),
97 cl::Hidden, cl::init(false), cl::cat(PollyCategory));
98
99static cl::opt<unsigned> RunTimeChecksMaxArraysPerGroup(
100 "polly-rtc-max-arrays-per-group",
101 cl::desc("The maximal number of arrays to compare in each alias group."),
102 cl::Hidden, cl::ZeroOrMore, cl::init(20), cl::cat(PollyCategory));
103
104static cl::opt<int> RunTimeChecksMaxAccessDisjuncts(
105 "polly-rtc-max-array-disjuncts",
106 cl::desc("The maximal number of disjunts allowed in memory accesses to "
107 "to build RTCs."),
108 cl::Hidden, cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory));
109
110static cl::opt<unsigned> RunTimeChecksMaxParameters(
111 "polly-rtc-max-parameters",
112 cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden,
113 cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory));
114
115static cl::opt<bool> UnprofitableScalarAccs(
116 "polly-unprofitable-scalar-accs",
117 cl::desc("Count statements with scalar accesses as not optimizable"),
118 cl::Hidden, cl::init(false), cl::cat(PollyCategory));
119
120static cl::opt<std::string> UserContextStr(
121 "polly-context", cl::value_desc("isl parameter set"),
122 cl::desc("Provide additional constraints on the context parameters"),
123 cl::init(""), cl::cat(PollyCategory));
124
125static cl::opt<bool> DetectFortranArrays(
126 "polly-detect-fortran-arrays",
127 cl::desc("Detect Fortran arrays and use this for code generation"),
128 cl::Hidden, cl::init(false), cl::cat(PollyCategory));
129
130static cl::opt<bool> DetectReductions("polly-detect-reductions",
131 cl::desc("Detect and exploit reductions"),
132 cl::Hidden, cl::ZeroOrMore,
133 cl::init(true), cl::cat(PollyCategory));
134
135// Multiplicative reductions can be disabled separately as these kind of
136// operations can overflow easily. Additive reductions and bit operations
137// are in contrast pretty stable.
138static cl::opt<bool> DisableMultiplicativeReductions(
139 "polly-disable-multiplicative-reductions",
140 cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore,
141 cl::init(false), cl::cat(PollyCategory));
142
143enum class GranularityChoice { BasicBlocks, ScalarIndependence, Stores };
144
145static cl::opt<GranularityChoice> StmtGranularity(
146 "polly-stmt-granularity",
147 cl::desc(
148 "Algorithm to use for splitting basic blocks into multiple statements"),
149 cl::values(clEnumValN(GranularityChoice::BasicBlocks, "bb",llvm::cl::OptionEnumValue { "bb", int(GranularityChoice::BasicBlocks
), "One statement per basic block" }
150 "One statement per basic block")llvm::cl::OptionEnumValue { "bb", int(GranularityChoice::BasicBlocks
), "One statement per basic block" }
,
151 clEnumValN(GranularityChoice::ScalarIndependence, "scalar-indep",llvm::cl::OptionEnumValue { "scalar-indep", int(GranularityChoice
::ScalarIndependence), "Scalar independence heuristic" }
152 "Scalar independence heuristic")llvm::cl::OptionEnumValue { "scalar-indep", int(GranularityChoice
::ScalarIndependence), "Scalar independence heuristic" }
,
153 clEnumValN(GranularityChoice::Stores, "store",llvm::cl::OptionEnumValue { "store", int(GranularityChoice::Stores
), "Store-level granularity" }
154 "Store-level granularity")llvm::cl::OptionEnumValue { "store", int(GranularityChoice::Stores
), "Store-level granularity" }
),
155 cl::init(GranularityChoice::ScalarIndependence), cl::cat(PollyCategory));
156
157/// Helper to treat non-affine regions and basic blocks the same.
158///
159///{
160
161/// Return the block that is the representing block for @p RN.
162static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
163 return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
164 : RN->getNodeAs<BasicBlock>();
165}
166
167/// Return the @p idx'th block that is executed after @p RN.
168static inline BasicBlock *
169getRegionNodeSuccessor(RegionNode *RN, Instruction *TI, unsigned idx) {
170 if (RN->isSubRegion()) {
171 assert(idx == 0)((idx == 0) ? static_cast<void> (0) : __assert_fail ("idx == 0"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 171, __PRETTY_FUNCTION__))
;
172 return RN->getNodeAs<Region>()->getExit();
173 }
174 return TI->getSuccessor(idx);
175}
176
177static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI,
178 const DominatorTree &DT) {
179 if (!RN->isSubRegion())
180 return isErrorBlock(*RN->getNodeAs<BasicBlock>(), R, LI, DT);
181 for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())
182 if (isErrorBlock(*BB, R, LI, DT))
183 return true;
184 return false;
185}
186
187///}
188
189/// Create a map to map from a given iteration to a subsequent iteration.
190///
191/// This map maps from SetSpace -> SetSpace where the dimensions @p Dim
192/// is incremented by one and all other dimensions are equal, e.g.,
193/// [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3]
194///
195/// if @p Dim is 2 and @p SetSpace has 4 dimensions.
196static isl::map createNextIterationMap(isl::space SetSpace, unsigned Dim) {
197 isl::space MapSpace = SetSpace.map_from_set();
198 isl::map NextIterationMap = isl::map::universe(MapSpace);
199 for (unsigned u = 0; u < NextIterationMap.dim(isl::dim::in); u++)
200 if (u != Dim)
201 NextIterationMap =
202 NextIterationMap.equate(isl::dim::in, u, isl::dim::out, u);
203 isl::constraint C =
204 isl::constraint::alloc_equality(isl::local_space(MapSpace));
205 C = C.set_constant_si(1);
206 C = C.set_coefficient_si(isl::dim::in, Dim, 1);
207 C = C.set_coefficient_si(isl::dim::out, Dim, -1);
208 NextIterationMap = NextIterationMap.add_constraint(C);
209 return NextIterationMap;
210}
211
212/// Add @p BSet to set @p BoundedParts if @p BSet is bounded.
213static isl::set collectBoundedParts(isl::set S) {
214 isl::set BoundedParts = isl::set::empty(S.get_space());
215 for (isl::basic_set BSet : S.get_basic_set_list())
216 if (BSet.is_bounded())
217 BoundedParts = BoundedParts.unite(isl::set(BSet));
218 return BoundedParts;
219}
220
221/// Compute the (un)bounded parts of @p S wrt. to dimension @p Dim.
222///
223/// @returns A separation of @p S into first an unbounded then a bounded subset,
224/// both with regards to the dimension @p Dim.
225static std::pair<isl::set, isl::set> partitionSetParts(isl::set S,
226 unsigned Dim) {
227 for (unsigned u = 0, e = S.n_dim(); u < e; u++)
228 S = S.lower_bound_si(isl::dim::set, u, 0);
229
230 unsigned NumDimsS = S.n_dim();
231 isl::set OnlyDimS = S;
232
233 // Remove dimensions that are greater than Dim as they are not interesting.
234 assert(NumDimsS >= Dim + 1)((NumDimsS >= Dim + 1) ? static_cast<void> (0) : __assert_fail
("NumDimsS >= Dim + 1", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 234, __PRETTY_FUNCTION__))
;
235 OnlyDimS = OnlyDimS.project_out(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);
236
237 // Create artificial parametric upper bounds for dimensions smaller than Dim
238 // as we are not interested in them.
239 OnlyDimS = OnlyDimS.insert_dims(isl::dim::param, 0, Dim);
240
241 for (unsigned u = 0; u < Dim; u++) {
242 isl::constraint C = isl::constraint::alloc_inequality(
243 isl::local_space(OnlyDimS.get_space()));
244 C = C.set_coefficient_si(isl::dim::param, u, 1);
245 C = C.set_coefficient_si(isl::dim::set, u, -1);
246 OnlyDimS = OnlyDimS.add_constraint(C);
247 }
248
249 // Collect all bounded parts of OnlyDimS.
250 isl::set BoundedParts = collectBoundedParts(OnlyDimS);
251
252 // Create the dimensions greater than Dim again.
253 BoundedParts =
254 BoundedParts.insert_dims(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);
255
256 // Remove the artificial upper bound parameters again.
257 BoundedParts = BoundedParts.remove_dims(isl::dim::param, 0, Dim);
258
259 isl::set UnboundedParts = S.subtract(BoundedParts);
260 return std::make_pair(UnboundedParts, BoundedParts);
261}
262
263/// Create the conditions under which @p L @p Pred @p R is true.
264static isl::set buildConditionSet(ICmpInst::Predicate Pred, isl::pw_aff L,
265 isl::pw_aff R) {
266 switch (Pred) {
267 case ICmpInst::ICMP_EQ:
268 return L.eq_set(R);
269 case ICmpInst::ICMP_NE:
270 return L.ne_set(R);
271 case ICmpInst::ICMP_SLT:
272 return L.lt_set(R);
273 case ICmpInst::ICMP_SLE:
274 return L.le_set(R);
275 case ICmpInst::ICMP_SGT:
276 return L.gt_set(R);
277 case ICmpInst::ICMP_SGE:
278 return L.ge_set(R);
279 case ICmpInst::ICMP_ULT:
280 return L.lt_set(R);
281 case ICmpInst::ICMP_UGT:
282 return L.gt_set(R);
283 case ICmpInst::ICMP_ULE:
284 return L.le_set(R);
285 case ICmpInst::ICMP_UGE:
286 return L.ge_set(R);
287 default:
288 llvm_unreachable("Non integer predicate not supported")::llvm::llvm_unreachable_internal("Non integer predicate not supported"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 288)
;
289 }
290}
291
292isl::set ScopBuilder::adjustDomainDimensions(isl::set Dom, Loop *OldL,
293 Loop *NewL) {
294 // If the loops are the same there is nothing to do.
295 if (NewL == OldL)
296 return Dom;
297
298 int OldDepth = scop->getRelativeLoopDepth(OldL);
299 int NewDepth = scop->getRelativeLoopDepth(NewL);
300 // If both loops are non-affine loops there is nothing to do.
301 if (OldDepth == -1 && NewDepth == -1)
302 return Dom;
303
304 // Distinguish three cases:
305 // 1) The depth is the same but the loops are not.
306 // => One loop was left one was entered.
307 // 2) The depth increased from OldL to NewL.
308 // => One loop was entered, none was left.
309 // 3) The depth decreased from OldL to NewL.
310 // => Loops were left were difference of the depths defines how many.
311 if (OldDepth == NewDepth) {
312 assert(OldL->getParentLoop() == NewL->getParentLoop())((OldL->getParentLoop() == NewL->getParentLoop()) ? static_cast
<void> (0) : __assert_fail ("OldL->getParentLoop() == NewL->getParentLoop()"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 312, __PRETTY_FUNCTION__))
;
313 Dom = Dom.project_out(isl::dim::set, NewDepth, 1);
314 Dom = Dom.add_dims(isl::dim::set, 1);
315 } else if (OldDepth < NewDepth) {
316 assert(OldDepth + 1 == NewDepth)((OldDepth + 1 == NewDepth) ? static_cast<void> (0) : __assert_fail
("OldDepth + 1 == NewDepth", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 316, __PRETTY_FUNCTION__))
;
317 auto &R = scop->getRegion();
318 (void)R;
319 assert(NewL->getParentLoop() == OldL ||((NewL->getParentLoop() == OldL || ((!OldL || !R.contains(
OldL)) && R.contains(NewL))) ? static_cast<void>
(0) : __assert_fail ("NewL->getParentLoop() == OldL || ((!OldL || !R.contains(OldL)) && R.contains(NewL))"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 320, __PRETTY_FUNCTION__))
320 ((!OldL || !R.contains(OldL)) && R.contains(NewL)))((NewL->getParentLoop() == OldL || ((!OldL || !R.contains(
OldL)) && R.contains(NewL))) ? static_cast<void>
(0) : __assert_fail ("NewL->getParentLoop() == OldL || ((!OldL || !R.contains(OldL)) && R.contains(NewL))"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 320, __PRETTY_FUNCTION__))
;
321 Dom = Dom.add_dims(isl::dim::set, 1);
322 } else {
323 assert(OldDepth > NewDepth)((OldDepth > NewDepth) ? static_cast<void> (0) : __assert_fail
("OldDepth > NewDepth", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 323, __PRETTY_FUNCTION__))
;
324 int Diff = OldDepth - NewDepth;
325 int NumDim = Dom.n_dim();
326 assert(NumDim >= Diff)((NumDim >= Diff) ? static_cast<void> (0) : __assert_fail
("NumDim >= Diff", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 326, __PRETTY_FUNCTION__))
;
327 Dom = Dom.project_out(isl::dim::set, NumDim - Diff, Diff);
328 }
329
330 return Dom;
331}
332
333/// Compute the isl representation for the SCEV @p E in this BB.
334///
335/// @param BB The BB for which isl representation is to be
336/// computed.
337/// @param InvalidDomainMap A map of BB to their invalid domains.
338/// @param E The SCEV that should be translated.
339/// @param NonNegative Flag to indicate the @p E has to be non-negative.
340///
341/// Note that this function will also adjust the invalid context accordingly.
342
343__isl_give isl_pw_aff *
344ScopBuilder::getPwAff(BasicBlock *BB,
345 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
346 const SCEV *E, bool NonNegative) {
347 PWACtx PWAC = scop->getPwAff(E, BB, NonNegative);
348 InvalidDomainMap[BB] = InvalidDomainMap[BB].unite(PWAC.second);
349 return PWAC.first.release();
350}
351
352/// Build condition sets for unsigned ICmpInst(s).
353/// Special handling is required for unsigned operands to ensure that if
354/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst
355/// it should wrap around.
356///
357/// @param IsStrictUpperBound holds information on the predicate relation
358/// between TestVal and UpperBound, i.e,
359/// TestVal < UpperBound OR TestVal <= UpperBound
360__isl_give isl_set *ScopBuilder::buildUnsignedConditionSets(
361 BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain,
362 const SCEV *SCEV_TestVal, const SCEV *SCEV_UpperBound,
363 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
364 bool IsStrictUpperBound) {
365 // Do not take NonNeg assumption on TestVal
366 // as it might have MSB (Sign bit) set.
367 isl_pw_aff *TestVal = getPwAff(BB, InvalidDomainMap, SCEV_TestVal, false);
368 // Take NonNeg assumption on UpperBound.
369 isl_pw_aff *UpperBound =
370 getPwAff(BB, InvalidDomainMap, SCEV_UpperBound, true);
371
372 // 0 <= TestVal
373 isl_set *First =
374 isl_pw_aff_le_set(isl_pw_aff_zero_on_domain(isl_local_space_from_space(
375 isl_pw_aff_get_domain_space(TestVal))),
376 isl_pw_aff_copy(TestVal));
377
378 isl_set *Second;
379 if (IsStrictUpperBound)
380 // TestVal < UpperBound
381 Second = isl_pw_aff_lt_set(TestVal, UpperBound);
382 else
383 // TestVal <= UpperBound
384 Second = isl_pw_aff_le_set(TestVal, UpperBound);
385
386 isl_set *ConsequenceCondSet = isl_set_intersect(First, Second);
387 return ConsequenceCondSet;
388}
389
390bool ScopBuilder::buildConditionSets(
391 BasicBlock *BB, SwitchInst *SI, Loop *L, __isl_keep isl_set *Domain,
392 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
393 SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
394 Value *Condition = getConditionFromTerminator(SI);
395 assert(Condition && "No condition for switch")((Condition && "No condition for switch") ? static_cast
<void> (0) : __assert_fail ("Condition && \"No condition for switch\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 395, __PRETTY_FUNCTION__))
;
396
397 isl_pw_aff *LHS, *RHS;
398 LHS = getPwAff(BB, InvalidDomainMap, SE.getSCEVAtScope(Condition, L));
399
400 unsigned NumSuccessors = SI->getNumSuccessors();
401 ConditionSets.resize(NumSuccessors);
402 for (auto &Case : SI->cases()) {
403 unsigned Idx = Case.getSuccessorIndex();
404 ConstantInt *CaseValue = Case.getCaseValue();
405
406 RHS = getPwAff(BB, InvalidDomainMap, SE.getSCEV(CaseValue));
407 isl_set *CaseConditionSet =
408 buildConditionSet(ICmpInst::ICMP_EQ, isl::manage_copy(LHS),
409 isl::manage(RHS))
410 .release();
411 ConditionSets[Idx] = isl_set_coalesce(
412 isl_set_intersect(CaseConditionSet, isl_set_copy(Domain)));
413 }
414
415 assert(ConditionSets[0] == nullptr && "Default condition set was set")((ConditionSets[0] == nullptr && "Default condition set was set"
) ? static_cast<void> (0) : __assert_fail ("ConditionSets[0] == nullptr && \"Default condition set was set\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 415, __PRETTY_FUNCTION__))
;
416 isl_set *ConditionSetUnion = isl_set_copy(ConditionSets[1]);
417 for (unsigned u = 2; u < NumSuccessors; u++)
418 ConditionSetUnion =
419 isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u]));
420 ConditionSets[0] = isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion);
421
422 isl_pw_aff_free(LHS);
423
424 return true;
425}
426
427bool ScopBuilder::buildConditionSets(
428 BasicBlock *BB, Value *Condition, Instruction *TI, Loop *L,
429 __isl_keep isl_set *Domain,
430 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
431 SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
432 isl_set *ConsequenceCondSet = nullptr;
433
434 if (auto Load = dyn_cast<LoadInst>(Condition)) {
435 const SCEV *LHSSCEV = SE.getSCEVAtScope(Load, L);
436 const SCEV *RHSSCEV = SE.getZero(LHSSCEV->getType());
437 bool NonNeg = false;
438 isl_pw_aff *LHS = getPwAff(BB, InvalidDomainMap, LHSSCEV, NonNeg);
439 isl_pw_aff *RHS = getPwAff(BB, InvalidDomainMap, RHSSCEV, NonNeg);
440 ConsequenceCondSet = buildConditionSet(ICmpInst::ICMP_SLE, isl::manage(LHS),
441 isl::manage(RHS))
442 .release();
443 } else if (auto *PHI = dyn_cast<PHINode>(Condition)) {
444 auto *Unique = dyn_cast<ConstantInt>(
445 getUniqueNonErrorValue(PHI, &scop->getRegion(), LI, DT));
446
447 if (Unique->isZero())
448 ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
449 else
450 ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
451 } else if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {
452 if (CCond->isZero())
453 ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
454 else
455 ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
456 } else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {
457 auto Opcode = BinOp->getOpcode();
458 assert(Opcode == Instruction::And || Opcode == Instruction::Or)((Opcode == Instruction::And || Opcode == Instruction::Or) ? static_cast
<void> (0) : __assert_fail ("Opcode == Instruction::And || Opcode == Instruction::Or"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 458, __PRETTY_FUNCTION__))
;
459
460 bool Valid = buildConditionSets(BB, BinOp->getOperand(0), TI, L, Domain,
461 InvalidDomainMap, ConditionSets) &&
462 buildConditionSets(BB, BinOp->getOperand(1), TI, L, Domain,
463 InvalidDomainMap, ConditionSets);
464 if (!Valid) {
465 while (!ConditionSets.empty())
466 isl_set_free(ConditionSets.pop_back_val());
467 return false;
468 }
469
470 isl_set_free(ConditionSets.pop_back_val());
471 isl_set *ConsCondPart0 = ConditionSets.pop_back_val();
472 isl_set_free(ConditionSets.pop_back_val());
473 isl_set *ConsCondPart1 = ConditionSets.pop_back_val();
474
475 if (Opcode == Instruction::And)
476 ConsequenceCondSet = isl_set_intersect(ConsCondPart0, ConsCondPart1);
477 else
478 ConsequenceCondSet = isl_set_union(ConsCondPart0, ConsCondPart1);
479 } else {
480 auto *ICond = dyn_cast<ICmpInst>(Condition);
481 assert(ICond &&((ICond && "Condition of exiting branch was neither constant nor ICmp!"
) ? static_cast<void> (0) : __assert_fail ("ICond && \"Condition of exiting branch was neither constant nor ICmp!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 482, __PRETTY_FUNCTION__))
482 "Condition of exiting branch was neither constant nor ICmp!")((ICond && "Condition of exiting branch was neither constant nor ICmp!"
) ? static_cast<void> (0) : __assert_fail ("ICond && \"Condition of exiting branch was neither constant nor ICmp!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 482, __PRETTY_FUNCTION__))
;
483
484 Region &R = scop->getRegion();
485
486 isl_pw_aff *LHS, *RHS;
487 // For unsigned comparisons we assumed the signed bit of neither operand
488 // to be set. The comparison is equal to a signed comparison under this
489 // assumption.
490 bool NonNeg = ICond->isUnsigned();
491 const SCEV *LeftOperand = SE.getSCEVAtScope(ICond->getOperand(0), L),
492 *RightOperand = SE.getSCEVAtScope(ICond->getOperand(1), L);
493
494 LeftOperand = tryForwardThroughPHI(LeftOperand, R, SE, LI, DT);
495 RightOperand = tryForwardThroughPHI(RightOperand, R, SE, LI, DT);
496
497 switch (ICond->getPredicate()) {
498 case ICmpInst::ICMP_ULT:
499 ConsequenceCondSet =
500 buildUnsignedConditionSets(BB, Condition, Domain, LeftOperand,
501 RightOperand, InvalidDomainMap, true);
502 break;
503 case ICmpInst::ICMP_ULE:
504 ConsequenceCondSet =
505 buildUnsignedConditionSets(BB, Condition, Domain, LeftOperand,
506 RightOperand, InvalidDomainMap, false);
507 break;
508 case ICmpInst::ICMP_UGT:
509 ConsequenceCondSet =
510 buildUnsignedConditionSets(BB, Condition, Domain, RightOperand,
511 LeftOperand, InvalidDomainMap, true);
512 break;
513 case ICmpInst::ICMP_UGE:
514 ConsequenceCondSet =
515 buildUnsignedConditionSets(BB, Condition, Domain, RightOperand,
516 LeftOperand, InvalidDomainMap, false);
517 break;
518 default:
519 LHS = getPwAff(BB, InvalidDomainMap, LeftOperand, NonNeg);
520 RHS = getPwAff(BB, InvalidDomainMap, RightOperand, NonNeg);
521 ConsequenceCondSet = buildConditionSet(ICond->getPredicate(),
522 isl::manage(LHS), isl::manage(RHS))
523 .release();
524 break;
525 }
526 }
527
528 // If no terminator was given we are only looking for parameter constraints
529 // under which @p Condition is true/false.
530 if (!TI)
531 ConsequenceCondSet = isl_set_params(ConsequenceCondSet);
532 assert(ConsequenceCondSet)((ConsequenceCondSet) ? static_cast<void> (0) : __assert_fail
("ConsequenceCondSet", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 532, __PRETTY_FUNCTION__))
;
533 ConsequenceCondSet = isl_set_coalesce(
534 isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain)));
535
536 isl_set *AlternativeCondSet = nullptr;
537 bool TooComplex =
538 isl_set_n_basic_set(ConsequenceCondSet) >= MaxDisjunctsInDomain;
539
540 if (!TooComplex) {
541 AlternativeCondSet = isl_set_subtract(isl_set_copy(Domain),
542 isl_set_copy(ConsequenceCondSet));
543 TooComplex =
544 isl_set_n_basic_set(AlternativeCondSet) >= MaxDisjunctsInDomain;
545 }
546
547 if (TooComplex) {
548 scop->invalidate(COMPLEXITY, TI ? TI->getDebugLoc() : DebugLoc(),
549 TI ? TI->getParent() : nullptr /* BasicBlock */);
550 isl_set_free(AlternativeCondSet);
551 isl_set_free(ConsequenceCondSet);
552 return false;
553 }
554
555 ConditionSets.push_back(ConsequenceCondSet);
556 ConditionSets.push_back(isl_set_coalesce(AlternativeCondSet));
557
558 return true;
559}
560
561bool ScopBuilder::buildConditionSets(
562 BasicBlock *BB, Instruction *TI, Loop *L, __isl_keep isl_set *Domain,
563 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
564 SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
565 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
566 return buildConditionSets(BB, SI, L, Domain, InvalidDomainMap,
567 ConditionSets);
568
569 assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.")((isa<BranchInst>(TI) && "Terminator was neither branch nor switch."
) ? static_cast<void> (0) : __assert_fail ("isa<BranchInst>(TI) && \"Terminator was neither branch nor switch.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 569, __PRETTY_FUNCTION__))
;
570
571 if (TI->getNumSuccessors() == 1) {
572 ConditionSets.push_back(isl_set_copy(Domain));
573 return true;
574 }
575
576 Value *Condition = getConditionFromTerminator(TI);
577 assert(Condition && "No condition for Terminator")((Condition && "No condition for Terminator") ? static_cast
<void> (0) : __assert_fail ("Condition && \"No condition for Terminator\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 577, __PRETTY_FUNCTION__))
;
578
579 return buildConditionSets(BB, Condition, TI, L, Domain, InvalidDomainMap,
580 ConditionSets);
581}
582
583bool ScopBuilder::propagateDomainConstraints(
584 Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
585 // Iterate over the region R and propagate the domain constrains from the
586 // predecessors to the current node. In contrast to the
587 // buildDomainsWithBranchConstraints function, this one will pull the domain
588 // information from the predecessors instead of pushing it to the successors.
589 // Additionally, we assume the domains to be already present in the domain
590 // map here. However, we iterate again in reverse post order so we know all
591 // predecessors have been visited before a block or non-affine subregion is
592 // visited.
593
594 ReversePostOrderTraversal<Region *> RTraversal(R);
595 for (auto *RN : RTraversal) {
596 // Recurse for affine subregions but go on for basic blocks and non-affine
597 // subregions.
598 if (RN->isSubRegion()) {
599 Region *SubRegion = RN->getNodeAs<Region>();
600 if (!scop->isNonAffineSubRegion(SubRegion)) {
601 if (!propagateDomainConstraints(SubRegion, InvalidDomainMap))
602 return false;
603 continue;
604 }
605 }
606
607 BasicBlock *BB = getRegionNodeBasicBlock(RN);
608 isl::set &Domain = scop->getOrInitEmptyDomain(BB);
609 assert(Domain)((Domain) ? static_cast<void> (0) : __assert_fail ("Domain"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 609, __PRETTY_FUNCTION__))
;
610
611 // Under the union of all predecessor conditions we can reach this block.
612 isl::set PredDom = getPredecessorDomainConstraints(BB, Domain);
613 Domain = Domain.intersect(PredDom).coalesce();
614 Domain = Domain.align_params(scop->getParamSpace());
615
616 Loop *BBLoop = getRegionNodeLoop(RN, LI);
617 if (BBLoop && BBLoop->getHeader() == BB && scop->contains(BBLoop))
618 if (!addLoopBoundsToHeaderDomain(BBLoop, InvalidDomainMap))
619 return false;
620 }
621
622 return true;
623}
624
625void ScopBuilder::propagateDomainConstraintsToRegionExit(
626 BasicBlock *BB, Loop *BBLoop,
627 SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks,
628 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
629 // Check if the block @p BB is the entry of a region. If so we propagate it's
630 // domain to the exit block of the region. Otherwise we are done.
631 auto *RI = scop->getRegion().getRegionInfo();
632 auto *BBReg = RI ? RI->getRegionFor(BB) : nullptr;
633 auto *ExitBB = BBReg ? BBReg->getExit() : nullptr;
634 if (!BBReg || BBReg->getEntry() != BB || !scop->contains(ExitBB))
635 return;
636
637 // Do not propagate the domain if there is a loop backedge inside the region
638 // that would prevent the exit block from being executed.
639 auto *L = BBLoop;
640 while (L && scop->contains(L)) {
641 SmallVector<BasicBlock *, 4> LatchBBs;
642 BBLoop->getLoopLatches(LatchBBs);
643 for (auto *LatchBB : LatchBBs)
644 if (BB != LatchBB && BBReg->contains(LatchBB))
645 return;
646 L = L->getParentLoop();
647 }
648
649 isl::set Domain = scop->getOrInitEmptyDomain(BB);
650 assert(Domain && "Cannot propagate a nullptr")((Domain && "Cannot propagate a nullptr") ? static_cast
<void> (0) : __assert_fail ("Domain && \"Cannot propagate a nullptr\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 650, __PRETTY_FUNCTION__))
;
651
652 Loop *ExitBBLoop = getFirstNonBoxedLoopFor(ExitBB, LI, scop->getBoxedLoops());
653
654 // Since the dimensions of @p BB and @p ExitBB might be different we have to
655 // adjust the domain before we can propagate it.
656 isl::set AdjustedDomain = adjustDomainDimensions(Domain, BBLoop, ExitBBLoop);
657 isl::set &ExitDomain = scop->getOrInitEmptyDomain(ExitBB);
658
659 // If the exit domain is not yet created we set it otherwise we "add" the
660 // current domain.
661 ExitDomain = ExitDomain ? AdjustedDomain.unite(ExitDomain) : AdjustedDomain;
662
663 // Initialize the invalid domain.
664 InvalidDomainMap[ExitBB] = ExitDomain.empty(ExitDomain.get_space());
665
666 FinishedExitBlocks.insert(ExitBB);
667}
668
669isl::set ScopBuilder::getPredecessorDomainConstraints(BasicBlock *BB,
670 isl::set Domain) {
671 // If @p BB is the ScopEntry we are done
672 if (scop->getRegion().getEntry() == BB)
673 return isl::set::universe(Domain.get_space());
674
675 // The region info of this function.
676 auto &RI = *scop->getRegion().getRegionInfo();
677
678 Loop *BBLoop = getFirstNonBoxedLoopFor(BB, LI, scop->getBoxedLoops());
679
680 // A domain to collect all predecessor domains, thus all conditions under
681 // which the block is executed. To this end we start with the empty domain.
682 isl::set PredDom = isl::set::empty(Domain.get_space());
683
684 // Set of regions of which the entry block domain has been propagated to BB.
685 // all predecessors inside any of the regions can be skipped.
686 SmallSet<Region *, 8> PropagatedRegions;
687
688 for (auto *PredBB : predecessors(BB)) {
689 // Skip backedges.
690 if (DT.dominates(BB, PredBB))
691 continue;
692
693 // If the predecessor is in a region we used for propagation we can skip it.
694 auto PredBBInRegion = [PredBB](Region *PR) { return PR->contains(PredBB); };
695 if (std::any_of(PropagatedRegions.begin(), PropagatedRegions.end(),
696 PredBBInRegion)) {
697 continue;
698 }
699
700 // Check if there is a valid region we can use for propagation, thus look
701 // for a region that contains the predecessor and has @p BB as exit block.
702 auto *PredR = RI.getRegionFor(PredBB);
703 while (PredR->getExit() != BB && !PredR->contains(BB))
704 PredR->getParent();
705
706 // If a valid region for propagation was found use the entry of that region
707 // for propagation, otherwise the PredBB directly.
708 if (PredR->getExit() == BB) {
709 PredBB = PredR->getEntry();
710 PropagatedRegions.insert(PredR);
711 }
712
713 isl::set PredBBDom = scop->getDomainConditions(PredBB);
714 Loop *PredBBLoop =
715 getFirstNonBoxedLoopFor(PredBB, LI, scop->getBoxedLoops());
716 PredBBDom = adjustDomainDimensions(PredBBDom, PredBBLoop, BBLoop);
717 PredDom = PredDom.unite(PredBBDom);
718 }
719
720 return PredDom;
721}
722
723bool ScopBuilder::addLoopBoundsToHeaderDomain(
724 Loop *L, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
725 int LoopDepth = scop->getRelativeLoopDepth(L);
726 assert(LoopDepth >= 0 && "Loop in region should have at least depth one")((LoopDepth >= 0 && "Loop in region should have at least depth one"
) ? static_cast<void> (0) : __assert_fail ("LoopDepth >= 0 && \"Loop in region should have at least depth one\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 726, __PRETTY_FUNCTION__))
;
727
728 BasicBlock *HeaderBB = L->getHeader();
729 assert(scop->isDomainDefined(HeaderBB))((scop->isDomainDefined(HeaderBB)) ? static_cast<void>
(0) : __assert_fail ("scop->isDomainDefined(HeaderBB)", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 729, __PRETTY_FUNCTION__))
;
730 isl::set &HeaderBBDom = scop->getOrInitEmptyDomain(HeaderBB);
731
732 isl::map NextIterationMap =
733 createNextIterationMap(HeaderBBDom.get_space(), LoopDepth);
734
735 isl::set UnionBackedgeCondition = HeaderBBDom.empty(HeaderBBDom.get_space());
736
737 SmallVector<BasicBlock *, 4> LatchBlocks;
738 L->getLoopLatches(LatchBlocks);
739
740 for (BasicBlock *LatchBB : LatchBlocks) {
741 // If the latch is only reachable via error statements we skip it.
742 if (!scop->isDomainDefined(LatchBB))
743 continue;
744
745 isl::set LatchBBDom = scop->getDomainConditions(LatchBB);
746
747 isl::set BackedgeCondition = nullptr;
748
749 Instruction *TI = LatchBB->getTerminator();
750 BranchInst *BI = dyn_cast<BranchInst>(TI);
751 assert(BI && "Only branch instructions allowed in loop latches")((BI && "Only branch instructions allowed in loop latches"
) ? static_cast<void> (0) : __assert_fail ("BI && \"Only branch instructions allowed in loop latches\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 751, __PRETTY_FUNCTION__))
;
752
753 if (BI->isUnconditional())
754 BackedgeCondition = LatchBBDom;
755 else {
756 SmallVector<isl_set *, 8> ConditionSets;
757 int idx = BI->getSuccessor(0) != HeaderBB;
758 if (!buildConditionSets(LatchBB, TI, L, LatchBBDom.get(),
759 InvalidDomainMap, ConditionSets))
760 return false;
761
762 // Free the non back edge condition set as we do not need it.
763 isl_set_free(ConditionSets[1 - idx]);
764
765 BackedgeCondition = isl::manage(ConditionSets[idx]);
766 }
767
768 int LatchLoopDepth = scop->getRelativeLoopDepth(LI.getLoopFor(LatchBB));
769 assert(LatchLoopDepth >= LoopDepth)((LatchLoopDepth >= LoopDepth) ? static_cast<void> (
0) : __assert_fail ("LatchLoopDepth >= LoopDepth", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 769, __PRETTY_FUNCTION__))
;
770 BackedgeCondition = BackedgeCondition.project_out(
771 isl::dim::set, LoopDepth + 1, LatchLoopDepth - LoopDepth);
772 UnionBackedgeCondition = UnionBackedgeCondition.unite(BackedgeCondition);
773 }
774
775 isl::map ForwardMap = ForwardMap.lex_le(HeaderBBDom.get_space());
776 for (int i = 0; i < LoopDepth; i++)
777 ForwardMap = ForwardMap.equate(isl::dim::in, i, isl::dim::out, i);
778
779 isl::set UnionBackedgeConditionComplement =
780 UnionBackedgeCondition.complement();
781 UnionBackedgeConditionComplement =
782 UnionBackedgeConditionComplement.lower_bound_si(isl::dim::set, LoopDepth,
783 0);
784 UnionBackedgeConditionComplement =
785 UnionBackedgeConditionComplement.apply(ForwardMap);
786 HeaderBBDom = HeaderBBDom.subtract(UnionBackedgeConditionComplement);
787 HeaderBBDom = HeaderBBDom.apply(NextIterationMap);
788
789 auto Parts = partitionSetParts(HeaderBBDom, LoopDepth);
790 HeaderBBDom = Parts.second;
791
792 // Check if there is a <nsw> tagged AddRec for this loop and if so do not add
793 // the bounded assumptions to the context as they are already implied by the
794 // <nsw> tag.
795 if (scop->hasNSWAddRecForLoop(L))
796 return true;
797
798 isl::set UnboundedCtx = Parts.first.params();
799 scop->recordAssumption(INFINITELOOP, UnboundedCtx,
800 HeaderBB->getTerminator()->getDebugLoc(),
801 AS_RESTRICTION);
802 return true;
803}
804
805void ScopBuilder::buildInvariantEquivalenceClasses() {
806 DenseMap<std::pair<const SCEV *, Type *>, LoadInst *> EquivClasses;
807
808 const InvariantLoadsSetTy &RIL = scop->getRequiredInvariantLoads();
809 for (LoadInst *LInst : RIL) {
810 const SCEV *PointerSCEV = SE.getSCEV(LInst->getPointerOperand());
811
812 Type *Ty = LInst->getType();
813 LoadInst *&ClassRep = EquivClasses[std::make_pair(PointerSCEV, Ty)];
814 if (ClassRep) {
815 scop->addInvariantLoadMapping(LInst, ClassRep);
816 continue;
817 }
818
819 ClassRep = LInst;
820 scop->addInvariantEquivClass(
821 InvariantEquivClassTy{PointerSCEV, MemoryAccessList(), nullptr, Ty});
822 }
823}
824
825bool ScopBuilder::buildDomains(
826 Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
827 bool IsOnlyNonAffineRegion = scop->isNonAffineSubRegion(R);
828 auto *EntryBB = R->getEntry();
829 auto *L = IsOnlyNonAffineRegion ? nullptr : LI.getLoopFor(EntryBB);
830 int LD = scop->getRelativeLoopDepth(L);
831 auto *S =
832 isl_set_universe(isl_space_set_alloc(scop->getIslCtx().get(), 0, LD + 1));
833
834 InvalidDomainMap[EntryBB] = isl::manage(isl_set_empty(isl_set_get_space(S)));
835 isl::noexceptions::set Domain = isl::manage(S);
836 scop->setDomain(EntryBB, Domain);
837
838 if (IsOnlyNonAffineRegion)
839 return !containsErrorBlock(R->getNode(), *R, LI, DT);
840
841 if (!buildDomainsWithBranchConstraints(R, InvalidDomainMap))
842 return false;
843
844 if (!propagateDomainConstraints(R, InvalidDomainMap))
845 return false;
846
847 // Error blocks and blocks dominated by them have been assumed to never be
848 // executed. Representing them in the Scop does not add any value. In fact,
849 // it is likely to cause issues during construction of the ScopStmts. The
850 // contents of error blocks have not been verified to be expressible and
851 // will cause problems when building up a ScopStmt for them.
852 // Furthermore, basic blocks dominated by error blocks may reference
853 // instructions in the error block which, if the error block is not modeled,
854 // can themselves not be constructed properly. To this end we will replace
855 // the domains of error blocks and those only reachable via error blocks
856 // with an empty set. Additionally, we will record for each block under which
857 // parameter combination it would be reached via an error block in its
858 // InvalidDomain. This information is needed during load hoisting.
859 if (!propagateInvalidStmtDomains(R, InvalidDomainMap))
860 return false;
861
862 return true;
863}
864
865bool ScopBuilder::buildDomainsWithBranchConstraints(
866 Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
867 // To create the domain for each block in R we iterate over all blocks and
868 // subregions in R and propagate the conditions under which the current region
869 // element is executed. To this end we iterate in reverse post order over R as
870 // it ensures that we first visit all predecessors of a region node (either a
871 // basic block or a subregion) before we visit the region node itself.
872 // Initially, only the domain for the SCoP region entry block is set and from
873 // there we propagate the current domain to all successors, however we add the
874 // condition that the successor is actually executed next.
875 // As we are only interested in non-loop carried constraints here we can
876 // simply skip loop back edges.
877
878 SmallPtrSet<BasicBlock *, 8> FinishedExitBlocks;
879 ReversePostOrderTraversal<Region *> RTraversal(R);
880 for (auto *RN : RTraversal) {
881 // Recurse for affine subregions but go on for basic blocks and non-affine
882 // subregions.
883 if (RN->isSubRegion()) {
884 Region *SubRegion = RN->getNodeAs<Region>();
885 if (!scop->isNonAffineSubRegion(SubRegion)) {
886 if (!buildDomainsWithBranchConstraints(SubRegion, InvalidDomainMap))
887 return false;
888 continue;
889 }
890 }
891
892 if (containsErrorBlock(RN, scop->getRegion(), LI, DT))
893 scop->notifyErrorBlock();
894 ;
895
896 BasicBlock *BB = getRegionNodeBasicBlock(RN);
897 Instruction *TI = BB->getTerminator();
898
899 if (isa<UnreachableInst>(TI))
900 continue;
901
902 if (!scop->isDomainDefined(BB))
903 continue;
904 isl::set Domain = scop->getDomainConditions(BB);
905
906 scop->updateMaxLoopDepth(isl_set_n_dim(Domain.get()));
907
908 auto *BBLoop = getRegionNodeLoop(RN, LI);
909 // Propagate the domain from BB directly to blocks that have a superset
910 // domain, at the moment only region exit nodes of regions that start in BB.
911 propagateDomainConstraintsToRegionExit(BB, BBLoop, FinishedExitBlocks,
912 InvalidDomainMap);
913
914 // If all successors of BB have been set a domain through the propagation
915 // above we do not need to build condition sets but can just skip this
916 // block. However, it is important to note that this is a local property
917 // with regards to the region @p R. To this end FinishedExitBlocks is a
918 // local variable.
919 auto IsFinishedRegionExit = [&FinishedExitBlocks](BasicBlock *SuccBB) {
920 return FinishedExitBlocks.count(SuccBB);
921 };
922 if (std::all_of(succ_begin(BB), succ_end(BB), IsFinishedRegionExit))
923 continue;
924
925 // Build the condition sets for the successor nodes of the current region
926 // node. If it is a non-affine subregion we will always execute the single
927 // exit node, hence the single entry node domain is the condition set. For
928 // basic blocks we use the helper function buildConditionSets.
929 SmallVector<isl_set *, 8> ConditionSets;
930 if (RN->isSubRegion())
931 ConditionSets.push_back(Domain.copy());
932 else if (!buildConditionSets(BB, TI, BBLoop, Domain.get(), InvalidDomainMap,
933 ConditionSets))
934 return false;
935
936 // Now iterate over the successors and set their initial domain based on
937 // their condition set. We skip back edges here and have to be careful when
938 // we leave a loop not to keep constraints over a dimension that doesn't
939 // exist anymore.
940 assert(RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size())((RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets
.size()) ? static_cast<void> (0) : __assert_fail ("RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size()"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 940, __PRETTY_FUNCTION__))
;
941 for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) {
942 isl::set CondSet = isl::manage(ConditionSets[u]);
943 BasicBlock *SuccBB = getRegionNodeSuccessor(RN, TI, u);
944
945 // Skip blocks outside the region.
946 if (!scop->contains(SuccBB))
947 continue;
948
949 // If we propagate the domain of some block to "SuccBB" we do not have to
950 // adjust the domain.
951 if (FinishedExitBlocks.count(SuccBB))
952 continue;
953
954 // Skip back edges.
955 if (DT.dominates(SuccBB, BB))
956 continue;
957
958 Loop *SuccBBLoop =
959 getFirstNonBoxedLoopFor(SuccBB, LI, scop->getBoxedLoops());
960
961 CondSet = adjustDomainDimensions(CondSet, BBLoop, SuccBBLoop);
962
963 // Set the domain for the successor or merge it with an existing domain in
964 // case there are multiple paths (without loop back edges) to the
965 // successor block.
966 isl::set &SuccDomain = scop->getOrInitEmptyDomain(SuccBB);
967
968 if (SuccDomain) {
969 SuccDomain = SuccDomain.unite(CondSet).coalesce();
970 } else {
971 // Initialize the invalid domain.
972 InvalidDomainMap[SuccBB] = CondSet.empty(CondSet.get_space());
973 SuccDomain = CondSet;
974 }
975
976 SuccDomain = SuccDomain.detect_equalities();
977
978 // Check if the maximal number of domain disjunctions was reached.
979 // In case this happens we will clean up and bail.
980 if (SuccDomain.n_basic_set() < MaxDisjunctsInDomain)
981 continue;
982
983 scop->invalidate(COMPLEXITY, DebugLoc());
984 while (++u < ConditionSets.size())
985 isl_set_free(ConditionSets[u]);
986 return false;
987 }
988 }
989
990 return true;
991}
992
993bool ScopBuilder::propagateInvalidStmtDomains(
994 Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
995 ReversePostOrderTraversal<Region *> RTraversal(R);
996 for (auto *RN : RTraversal) {
997
998 // Recurse for affine subregions but go on for basic blocks and non-affine
999 // subregions.
1000 if (RN->isSubRegion()) {
1001 Region *SubRegion = RN->getNodeAs<Region>();
1002 if (!scop->isNonAffineSubRegion(SubRegion)) {
1003 propagateInvalidStmtDomains(SubRegion, InvalidDomainMap);
1004 continue;
1005 }
1006 }
1007
1008 bool ContainsErrorBlock = containsErrorBlock(RN, scop->getRegion(), LI, DT);
1009 BasicBlock *BB = getRegionNodeBasicBlock(RN);
1010 isl::set &Domain = scop->getOrInitEmptyDomain(BB);
1011 assert(Domain && "Cannot propagate a nullptr")((Domain && "Cannot propagate a nullptr") ? static_cast
<void> (0) : __assert_fail ("Domain && \"Cannot propagate a nullptr\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1011, __PRETTY_FUNCTION__))
;
1012
1013 isl::set InvalidDomain = InvalidDomainMap[BB];
1014
1015 bool IsInvalidBlock = ContainsErrorBlock || Domain.is_subset(InvalidDomain);
1016
1017 if (!IsInvalidBlock) {
1018 InvalidDomain = InvalidDomain.intersect(Domain);
1019 } else {
1020 InvalidDomain = Domain;
1021 isl::set DomPar = Domain.params();
1022 scop->recordAssumption(ERRORBLOCK, DomPar,
1023 BB->getTerminator()->getDebugLoc(),
1024 AS_RESTRICTION);
1025 Domain = isl::set::empty(Domain.get_space());
1026 }
1027
1028 if (InvalidDomain.is_empty()) {
1029 InvalidDomainMap[BB] = InvalidDomain;
1030 continue;
1031 }
1032
1033 auto *BBLoop = getRegionNodeLoop(RN, LI);
1034 auto *TI = BB->getTerminator();
1035 unsigned NumSuccs = RN->isSubRegion() ? 1 : TI->getNumSuccessors();
1036 for (unsigned u = 0; u < NumSuccs; u++) {
1037 auto *SuccBB = getRegionNodeSuccessor(RN, TI, u);
1038
1039 // Skip successors outside the SCoP.
1040 if (!scop->contains(SuccBB))
1041 continue;
1042
1043 // Skip backedges.
1044 if (DT.dominates(SuccBB, BB))
1045 continue;
1046
1047 Loop *SuccBBLoop =
1048 getFirstNonBoxedLoopFor(SuccBB, LI, scop->getBoxedLoops());
1049
1050 auto AdjustedInvalidDomain =
1051 adjustDomainDimensions(InvalidDomain, BBLoop, SuccBBLoop);
1052
1053 isl::set SuccInvalidDomain = InvalidDomainMap[SuccBB];
1054 SuccInvalidDomain = SuccInvalidDomain.unite(AdjustedInvalidDomain);
1055 SuccInvalidDomain = SuccInvalidDomain.coalesce();
1056
1057 InvalidDomainMap[SuccBB] = SuccInvalidDomain;
1058
1059 // Check if the maximal number of domain disjunctions was reached.
1060 // In case this happens we will bail.
1061 if (SuccInvalidDomain.n_basic_set() < MaxDisjunctsInDomain)
1062 continue;
1063
1064 InvalidDomainMap.erase(BB);
1065 scop->invalidate(COMPLEXITY, TI->getDebugLoc(), TI->getParent());
1066 return false;
1067 }
1068
1069 InvalidDomainMap[BB] = InvalidDomain;
1070 }
1071
1072 return true;
1073}
1074
1075void ScopBuilder::buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI,
1076 Region *NonAffineSubRegion,
1077 bool IsExitBlock) {
1078 // PHI nodes that are in the exit block of the region, hence if IsExitBlock is
1079 // true, are not modeled as ordinary PHI nodes as they are not part of the
1080 // region. However, we model the operands in the predecessor blocks that are
1081 // part of the region as regular scalar accesses.
1082
1083 // If we can synthesize a PHI we can skip it, however only if it is in
1084 // the region. If it is not it can only be in the exit block of the region.
1085 // In this case we model the operands but not the PHI itself.
1086 auto *Scope = LI.getLoopFor(PHI->getParent());
1087 if (!IsExitBlock && canSynthesize(PHI, *scop, &SE, Scope))
1088 return;
1089
1090 // PHI nodes are modeled as if they had been demoted prior to the SCoP
1091 // detection. Hence, the PHI is a load of a new memory location in which the
1092 // incoming value was written at the end of the incoming basic block.
1093 bool OnlyNonAffineSubRegionOperands = true;
1094 for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
1095 Value *Op = PHI->getIncomingValue(u);
1096 BasicBlock *OpBB = PHI->getIncomingBlock(u);
1097 ScopStmt *OpStmt = scop->getIncomingStmtFor(PHI->getOperandUse(u));
1098
1099 // Do not build PHI dependences inside a non-affine subregion, but make
1100 // sure that the necessary scalar values are still made available.
1101 if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB)) {
1102 auto *OpInst = dyn_cast<Instruction>(Op);
1103 if (!OpInst || !NonAffineSubRegion->contains(OpInst))
1104 ensureValueRead(Op, OpStmt);
1105 continue;
1106 }
1107
1108 OnlyNonAffineSubRegionOperands = false;
1109 ensurePHIWrite(PHI, OpStmt, OpBB, Op, IsExitBlock);
1110 }
1111
1112 if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) {
1113 addPHIReadAccess(PHIStmt, PHI);
1114 }
1115}
1116
1117void ScopBuilder::buildScalarDependences(ScopStmt *UserStmt,
1118 Instruction *Inst) {
1119 assert(!isa<PHINode>(Inst))((!isa<PHINode>(Inst)) ? static_cast<void> (0) : __assert_fail
("!isa<PHINode>(Inst)", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1119, __PRETTY_FUNCTION__))
;
1120
1121 // Pull-in required operands.
1122 for (Use &Op : Inst->operands())
1123 ensureValueRead(Op.get(), UserStmt);
1124}
1125
1126// Create a sequence of two schedules. Either argument may be null and is
1127// interpreted as the empty schedule. Can also return null if both schedules are
1128// empty.
1129static isl::schedule combineInSequence(isl::schedule Prev, isl::schedule Succ) {
1130 if (!Prev)
1131 return Succ;
1132 if (!Succ)
1133 return Prev;
1134
1135 return Prev.sequence(Succ);
1136}
1137
1138// Create an isl_multi_union_aff that defines an identity mapping from the
1139// elements of USet to their N-th dimension.
1140//
1141// # Example:
1142//
1143// Domain: { A[i,j]; B[i,j,k] }
1144// N: 1
1145//
1146// Resulting Mapping: { {A[i,j] -> [(j)]; B[i,j,k] -> [(j)] }
1147//
1148// @param USet A union set describing the elements for which to generate a
1149// mapping.
1150// @param N The dimension to map to.
1151// @returns A mapping from USet to its N-th dimension.
1152static isl::multi_union_pw_aff mapToDimension(isl::union_set USet, int N) {
1153 assert(N >= 0)((N >= 0) ? static_cast<void> (0) : __assert_fail ("N >= 0"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1153, __PRETTY_FUNCTION__))
;
1154 assert(USet)((USet) ? static_cast<void> (0) : __assert_fail ("USet"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1154, __PRETTY_FUNCTION__))
;
1155 assert(!USet.is_empty())((!USet.is_empty()) ? static_cast<void> (0) : __assert_fail
("!USet.is_empty()", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1155, __PRETTY_FUNCTION__))
;
1156
1157 auto Result = isl::union_pw_multi_aff::empty(USet.get_space());
1158
1159 for (isl::set S : USet.get_set_list()) {
1160 int Dim = S.dim(isl::dim::set);
1161 auto PMA = isl::pw_multi_aff::project_out_map(S.get_space(), isl::dim::set,
1162 N, Dim - N);
1163 if (N > 1)
1164 PMA = PMA.drop_dims(isl::dim::out, 0, N - 1);
1165
1166 Result = Result.add_pw_multi_aff(PMA);
1167 }
1168
1169 return isl::multi_union_pw_aff(isl::union_pw_multi_aff(Result));
1170}
1171
1172void ScopBuilder::buildSchedule() {
1173 Loop *L = getLoopSurroundingScop(*scop, LI);
1174 LoopStackTy LoopStack({LoopStackElementTy(L, nullptr, 0)});
1175 buildSchedule(scop->getRegion().getNode(), LoopStack);
1176 assert(LoopStack.size() == 1 && LoopStack.back().L == L)((LoopStack.size() == 1 && LoopStack.back().L == L) ?
static_cast<void> (0) : __assert_fail ("LoopStack.size() == 1 && LoopStack.back().L == L"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1176, __PRETTY_FUNCTION__))
;
1177 scop->setScheduleTree(LoopStack[0].Schedule);
1178}
1179
1180/// To generate a schedule for the elements in a Region we traverse the Region
1181/// in reverse-post-order and add the contained RegionNodes in traversal order
1182/// to the schedule of the loop that is currently at the top of the LoopStack.
1183/// For loop-free codes, this results in a correct sequential ordering.
1184///
1185/// Example:
1186/// bb1(0)
1187/// / \.
1188/// bb2(1) bb3(2)
1189/// \ / \.
1190/// bb4(3) bb5(4)
1191/// \ /
1192/// bb6(5)
1193///
1194/// Including loops requires additional processing. Whenever a loop header is
1195/// encountered, the corresponding loop is added to the @p LoopStack. Starting
1196/// from an empty schedule, we first process all RegionNodes that are within
1197/// this loop and complete the sequential schedule at this loop-level before
1198/// processing about any other nodes. To implement this
1199/// loop-nodes-first-processing, the reverse post-order traversal is
1200/// insufficient. Hence, we additionally check if the traversal yields
1201/// sub-regions or blocks that are outside the last loop on the @p LoopStack.
1202/// These region-nodes are then queue and only traverse after the all nodes
1203/// within the current loop have been processed.
1204void ScopBuilder::buildSchedule(Region *R, LoopStackTy &LoopStack) {
1205 Loop *OuterScopLoop = getLoopSurroundingScop(*scop, LI);
1206
1207 ReversePostOrderTraversal<Region *> RTraversal(R);
1208 std::deque<RegionNode *> WorkList(RTraversal.begin(), RTraversal.end());
1209 std::deque<RegionNode *> DelayList;
1210 bool LastRNWaiting = false;
1211
1212 // Iterate over the region @p R in reverse post-order but queue
1213 // sub-regions/blocks iff they are not part of the last encountered but not
1214 // completely traversed loop. The variable LastRNWaiting is a flag to indicate
1215 // that we queued the last sub-region/block from the reverse post-order
1216 // iterator. If it is set we have to explore the next sub-region/block from
1217 // the iterator (if any) to guarantee progress. If it is not set we first try
1218 // the next queued sub-region/blocks.
1219 while (!WorkList.empty() || !DelayList.empty()) {
1220 RegionNode *RN;
1221
1222 if ((LastRNWaiting && !WorkList.empty()) || DelayList.empty()) {
1223 RN = WorkList.front();
1224 WorkList.pop_front();
1225 LastRNWaiting = false;
1226 } else {
1227 RN = DelayList.front();
1228 DelayList.pop_front();
1229 }
1230
1231 Loop *L = getRegionNodeLoop(RN, LI);
1232 if (!scop->contains(L))
1233 L = OuterScopLoop;
1234
1235 Loop *LastLoop = LoopStack.back().L;
1236 if (LastLoop != L) {
1237 if (LastLoop && !LastLoop->contains(L)) {
1238 LastRNWaiting = true;
1239 DelayList.push_back(RN);
1240 continue;
1241 }
1242 LoopStack.push_back({L, nullptr, 0});
1243 }
1244 buildSchedule(RN, LoopStack);
1245 }
1246}
1247
1248void ScopBuilder::buildSchedule(RegionNode *RN, LoopStackTy &LoopStack) {
1249 if (RN->isSubRegion()) {
1250 auto *LocalRegion = RN->getNodeAs<Region>();
1251 if (!scop->isNonAffineSubRegion(LocalRegion)) {
1252 buildSchedule(LocalRegion, LoopStack);
1253 return;
1254 }
1255 }
1256
1257 assert(LoopStack.rbegin() != LoopStack.rend())((LoopStack.rbegin() != LoopStack.rend()) ? static_cast<void
> (0) : __assert_fail ("LoopStack.rbegin() != LoopStack.rend()"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1257, __PRETTY_FUNCTION__))
;
1258 auto LoopData = LoopStack.rbegin();
1259 LoopData->NumBlocksProcessed += getNumBlocksInRegionNode(RN);
1260
1261 for (auto *Stmt : scop->getStmtListFor(RN)) {
1262 isl::union_set UDomain{Stmt->getDomain()};
1263 auto StmtSchedule = isl::schedule::from_domain(UDomain);
1264 LoopData->Schedule = combineInSequence(LoopData->Schedule, StmtSchedule);
1265 }
1266
1267 // Check if we just processed the last node in this loop. If we did, finalize
1268 // the loop by:
1269 //
1270 // - adding new schedule dimensions
1271 // - folding the resulting schedule into the parent loop schedule
1272 // - dropping the loop schedule from the LoopStack.
1273 //
1274 // Then continue to check surrounding loops, which might also have been
1275 // completed by this node.
1276 size_t Dimension = LoopStack.size();
1277 while (LoopData->L &&
1278 LoopData->NumBlocksProcessed == getNumBlocksInLoop(LoopData->L)) {
1279 isl::schedule Schedule = LoopData->Schedule;
1280 auto NumBlocksProcessed = LoopData->NumBlocksProcessed;
1281
1282 assert(std::next(LoopData) != LoopStack.rend())((std::next(LoopData) != LoopStack.rend()) ? static_cast<void
> (0) : __assert_fail ("std::next(LoopData) != LoopStack.rend()"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1282, __PRETTY_FUNCTION__))
;
1283 ++LoopData;
1284 --Dimension;
1285
1286 if (Schedule) {
1287 isl::union_set Domain = Schedule.get_domain();
1288 isl::multi_union_pw_aff MUPA = mapToDimension(Domain, Dimension);
1289 Schedule = Schedule.insert_partial_schedule(MUPA);
1290 LoopData->Schedule = combineInSequence(LoopData->Schedule, Schedule);
1291 }
1292
1293 LoopData->NumBlocksProcessed += NumBlocksProcessed;
1294 }
1295 // Now pop all loops processed up there from the LoopStack
1296 LoopStack.erase(LoopStack.begin() + Dimension, LoopStack.end());
1297}
1298
1299void ScopBuilder::buildEscapingDependences(Instruction *Inst) {
1300 // Check for uses of this instruction outside the scop. Because we do not
1301 // iterate over such instructions and therefore did not "ensure" the existence
1302 // of a write, we must determine such use here.
1303 if (scop->isEscaping(Inst))
1304 ensureValueWrite(Inst);
1305}
1306
1307/// Check that a value is a Fortran Array descriptor.
1308///
1309/// We check if V has the following structure:
1310/// %"struct.array1_real(kind=8)" = type { i8*, i<zz>, i<zz>,
1311/// [<num> x %struct.descriptor_dimension] }
1312///
1313///
1314/// %struct.descriptor_dimension = type { i<zz>, i<zz>, i<zz> }
1315///
1316/// 1. V's type name starts with "struct.array"
1317/// 2. V's type has layout as shown.
1318/// 3. Final member of V's type has name "struct.descriptor_dimension",
1319/// 4. "struct.descriptor_dimension" has layout as shown.
1320/// 5. Consistent use of i<zz> where <zz> is some fixed integer number.
1321///
1322/// We are interested in such types since this is the code that dragonegg
1323/// generates for Fortran array descriptors.
1324///
1325/// @param V the Value to be checked.
1326///
1327/// @returns True if V is a Fortran array descriptor, False otherwise.
1328bool isFortranArrayDescriptor(Value *V) {
1329 PointerType *PTy = dyn_cast<PointerType>(V->getType());
1330
1331 if (!PTy)
1332 return false;
1333
1334 Type *Ty = PTy->getElementType();
1335 assert(Ty && "Ty expected to be initialized")((Ty && "Ty expected to be initialized") ? static_cast
<void> (0) : __assert_fail ("Ty && \"Ty expected to be initialized\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1335, __PRETTY_FUNCTION__))
;
1336 auto *StructArrTy = dyn_cast<StructType>(Ty);
1337
1338 if (!(StructArrTy && StructArrTy->hasName()))
1339 return false;
1340
1341 if (!StructArrTy->getName().startswith("struct.array"))
1342 return false;
1343
1344 if (StructArrTy->getNumElements() != 4)
1345 return false;
1346
1347 const ArrayRef<Type *> ArrMemberTys = StructArrTy->elements();
1348
1349 // i8* match
1350 if (ArrMemberTys[0] != Type::getInt8PtrTy(V->getContext()))
1351 return false;
1352
1353 // Get a reference to the int type and check that all the members
1354 // share the same int type
1355 Type *IntTy = ArrMemberTys[1];
1356 if (ArrMemberTys[2] != IntTy)
1357 return false;
1358
1359 // type: [<num> x %struct.descriptor_dimension]
1360 ArrayType *DescriptorDimArrayTy = dyn_cast<ArrayType>(ArrMemberTys[3]);
1361 if (!DescriptorDimArrayTy)
1362 return false;
1363
1364 // type: %struct.descriptor_dimension := type { ixx, ixx, ixx }
1365 StructType *DescriptorDimTy =
1366 dyn_cast<StructType>(DescriptorDimArrayTy->getElementType());
1367
1368 if (!(DescriptorDimTy && DescriptorDimTy->hasName()))
1369 return false;
1370
1371 if (DescriptorDimTy->getName() != "struct.descriptor_dimension")
1372 return false;
1373
1374 if (DescriptorDimTy->getNumElements() != 3)
1375 return false;
1376
1377 for (auto MemberTy : DescriptorDimTy->elements()) {
1378 if (MemberTy != IntTy)
1379 return false;
1380 }
1381
1382 return true;
1383}
1384
1385Value *ScopBuilder::findFADAllocationVisible(MemAccInst Inst) {
1386 // match: 4.1 & 4.2 store/load
1387 if (!isa<LoadInst>(Inst) && !isa<StoreInst>(Inst))
1388 return nullptr;
1389
1390 // match: 4
1391 if (Inst.getAlignment() != 8)
1392 return nullptr;
1393
1394 Value *Address = Inst.getPointerOperand();
1395
1396 const BitCastInst *Bitcast = nullptr;
1397 // [match: 3]
1398 if (auto *Slot = dyn_cast<GetElementPtrInst>(Address)) {
1399 Value *TypedMem = Slot->getPointerOperand();
1400 // match: 2
1401 Bitcast = dyn_cast<BitCastInst>(TypedMem);
1402 } else {
1403 // match: 2
1404 Bitcast = dyn_cast<BitCastInst>(Address);
1405 }
1406
1407 if (!Bitcast)
1408 return nullptr;
1409
1410 auto *MallocMem = Bitcast->getOperand(0);
1411
1412 // match: 1
1413 auto *MallocCall = dyn_cast<CallInst>(MallocMem);
1414 if (!MallocCall)
1415 return nullptr;
1416
1417 Function *MallocFn = MallocCall->getCalledFunction();
1418 if (!(MallocFn && MallocFn->hasName() && MallocFn->getName() == "malloc"))
1419 return nullptr;
1420
1421 // Find all uses the malloc'd memory.
1422 // We are looking for a "store" into a struct with the type being the Fortran
1423 // descriptor type
1424 for (auto user : MallocMem->users()) {
1425 /// match: 5
1426 auto *MallocStore = dyn_cast<StoreInst>(user);
1427 if (!MallocStore)
1428 continue;
1429
1430 auto *DescriptorGEP =
1431 dyn_cast<GEPOperator>(MallocStore->getPointerOperand());
1432 if (!DescriptorGEP)
1433 continue;
1434
1435 // match: 5
1436 auto DescriptorType =
1437 dyn_cast<StructType>(DescriptorGEP->getSourceElementType());
1438 if (!(DescriptorType && DescriptorType->hasName()))
1439 continue;
1440
1441 Value *Descriptor = dyn_cast<Value>(DescriptorGEP->getPointerOperand());
1442
1443 if (!Descriptor)
1444 continue;
1445
1446 if (!isFortranArrayDescriptor(Descriptor))
1447 continue;
1448
1449 return Descriptor;
1450 }
1451
1452 return nullptr;
1453}
1454
1455Value *ScopBuilder::findFADAllocationInvisible(MemAccInst Inst) {
1456 // match: 3
1457 if (!isa<LoadInst>(Inst) && !isa<StoreInst>(Inst))
1458 return nullptr;
1459
1460 Value *Slot = Inst.getPointerOperand();
1461
1462 LoadInst *MemLoad = nullptr;
1463 // [match: 2]
1464 if (auto *SlotGEP = dyn_cast<GetElementPtrInst>(Slot)) {
1465 // match: 1
1466 MemLoad = dyn_cast<LoadInst>(SlotGEP->getPointerOperand());
1467 } else {
1468 // match: 1
1469 MemLoad = dyn_cast<LoadInst>(Slot);
1470 }
1471
1472 if (!MemLoad)
1473 return nullptr;
1474
1475 auto *BitcastOperator =
1476 dyn_cast<BitCastOperator>(MemLoad->getPointerOperand());
1477 if (!BitcastOperator)
1478 return nullptr;
1479
1480 Value *Descriptor = dyn_cast<Value>(BitcastOperator->getOperand(0));
1481 if (!Descriptor)
1482 return nullptr;
1483
1484 if (!isFortranArrayDescriptor(Descriptor))
1485 return nullptr;
1486
1487 return Descriptor;
1488}
1489
1490void ScopBuilder::addRecordedAssumptions() {
1491 for (auto &AS : llvm::reverse(scop->recorded_assumptions())) {
1492
1493 if (!AS.BB) {
1494 scop->addAssumption(AS.Kind, AS.Set, AS.Loc, AS.Sign,
1495 nullptr /* BasicBlock */);
1496 continue;
1497 }
1498
1499 // If the domain was deleted the assumptions are void.
1500 isl_set *Dom = scop->getDomainConditions(AS.BB).release();
1501 if (!Dom)
1502 continue;
1503
1504 // If a basic block was given use its domain to simplify the assumption.
1505 // In case of restrictions we know they only have to hold on the domain,
1506 // thus we can intersect them with the domain of the block. However, for
1507 // assumptions the domain has to imply them, thus:
1508 // _ _____
1509 // Dom => S <==> A v B <==> A - B
1510 //
1511 // To avoid the complement we will register A - B as a restriction not an
1512 // assumption.
1513 isl_set *S = AS.Set.copy();
1514 if (AS.Sign == AS_RESTRICTION)
1515 S = isl_set_params(isl_set_intersect(S, Dom));
1516 else /* (AS.Sign == AS_ASSUMPTION) */
1517 S = isl_set_params(isl_set_subtract(Dom, S));
1518
1519 scop->addAssumption(AS.Kind, isl::manage(S), AS.Loc, AS_RESTRICTION, AS.BB);
1520 }
1521 scop->clearRecordedAssumptions();
1522}
1523
1524void ScopBuilder::addUserAssumptions(
1525 AssumptionCache &AC, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
1526 for (auto &Assumption : AC.assumptions()) {
1527 auto *CI = dyn_cast_or_null<CallInst>(Assumption);
1528 if (!CI || CI->getNumArgOperands() != 1)
1529 continue;
1530
1531 bool InScop = scop->contains(CI);
1532 if (!InScop && !scop->isDominatedBy(DT, CI->getParent()))
1533 continue;
1534
1535 auto *L = LI.getLoopFor(CI->getParent());
1536 auto *Val = CI->getArgOperand(0);
1537 ParameterSetTy DetectedParams;
1538 auto &R = scop->getRegion();
1539 if (!isAffineConstraint(Val, &R, L, SE, DetectedParams)) {
1540 ORE.emit(
1541 OptimizationRemarkAnalysis(DEBUG_TYPE"polly-scops", "IgnoreUserAssumption", CI)
1542 << "Non-affine user assumption ignored.");
1543 continue;
1544 }
1545
1546 // Collect all newly introduced parameters.
1547 ParameterSetTy NewParams;
1548 for (auto *Param : DetectedParams) {
1549 Param = extractConstantFactor(Param, SE).second;
1550 Param = scop->getRepresentingInvariantLoadSCEV(Param);
1551 if (scop->isParam(Param))
1552 continue;
1553 NewParams.insert(Param);
1554 }
1555
1556 SmallVector<isl_set *, 2> ConditionSets;
1557 auto *TI = InScop ? CI->getParent()->getTerminator() : nullptr;
1558 BasicBlock *BB = InScop ? CI->getParent() : R.getEntry();
1559 auto *Dom = InScop ? isl_set_copy(scop->getDomainConditions(BB).get())
1560 : isl_set_copy(scop->getContext().get());
1561 assert(Dom && "Cannot propagate a nullptr.")((Dom && "Cannot propagate a nullptr.") ? static_cast
<void> (0) : __assert_fail ("Dom && \"Cannot propagate a nullptr.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1561, __PRETTY_FUNCTION__))
;
1562 bool Valid = buildConditionSets(BB, Val, TI, L, Dom, InvalidDomainMap,
1563 ConditionSets);
1564 isl_set_free(Dom);
1565
1566 if (!Valid)
1567 continue;
1568
1569 isl_set *AssumptionCtx = nullptr;
1570 if (InScop) {
1571 AssumptionCtx = isl_set_complement(isl_set_params(ConditionSets[1]));
1572 isl_set_free(ConditionSets[0]);
1573 } else {
1574 AssumptionCtx = isl_set_complement(ConditionSets[1]);
1575 AssumptionCtx = isl_set_intersect(AssumptionCtx, ConditionSets[0]);
1576 }
1577
1578 // Project out newly introduced parameters as they are not otherwise useful.
1579 if (!NewParams.empty()) {
1580 for (unsigned u = 0; u < isl_set_n_param(AssumptionCtx); u++) {
1581 auto *Id = isl_set_get_dim_id(AssumptionCtx, isl_dim_param, u);
1582 auto *Param = static_cast<const SCEV *>(isl_id_get_user(Id));
1583 isl_id_free(Id);
1584
1585 if (!NewParams.count(Param))
1586 continue;
1587
1588 AssumptionCtx =
1589 isl_set_project_out(AssumptionCtx, isl_dim_param, u--, 1);
1590 }
1591 }
1592 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE"polly-scops", "UserAssumption", CI)
1593 << "Use user assumption: " << stringFromIslObj(AssumptionCtx));
1594 isl::set newContext =
1595 scop->getContext().intersect(isl::manage(AssumptionCtx));
1596 scop->setContext(newContext);
1597 }
1598}
1599
1600bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) {
1601 Value *Val = Inst.getValueOperand();
1602 Type *ElementType = Val->getType();
1603 Value *Address = Inst.getPointerOperand();
1604 const SCEV *AccessFunction =
1605 SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
1606 const SCEVUnknown *BasePointer =
15
'BasePointer' initialized to a null pointer value
1607 dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
14
Assuming the object is not a 'SCEVUnknown'
1608 enum MemoryAccess::AccessType AccType =
1609 isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
16
Assuming 'Inst' is not a 'LoadInst'
17
'?' condition is false
1610
1611 if (auto *BitCast = dyn_cast<BitCastInst>(Address)) {
18
Assuming 'BitCast' is null
19
Taking false branch
1612 auto *Src = BitCast->getOperand(0);
1613 auto *SrcTy = Src->getType();
1614 auto *DstTy = BitCast->getType();
1615 // Do not try to delinearize non-sized (opaque) pointers.
1616 if ((SrcTy->isPointerTy() && !SrcTy->getPointerElementType()->isSized()) ||
1617 (DstTy->isPointerTy() && !DstTy->getPointerElementType()->isSized())) {
1618 return false;
1619 }
1620 if (SrcTy->isPointerTy() && DstTy->isPointerTy() &&
1621 DL.getTypeAllocSize(SrcTy->getPointerElementType()) ==
1622 DL.getTypeAllocSize(DstTy->getPointerElementType()))
1623 Address = Src;
1624 }
1625
1626 auto *GEP = dyn_cast<GetElementPtrInst>(Address);
1627 if (!GEP)
20
Assuming 'GEP' is non-null
21
Taking false branch
1628 return false;
1629
1630 std::vector<const SCEV *> Subscripts;
1631 std::vector<int> Sizes;
1632 std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, SE);
1633 auto *BasePtr = GEP->getOperand(0);
1634
1635 if (auto *BasePtrCast = dyn_cast<BitCastInst>(BasePtr))
22
Assuming 'BasePtrCast' is null
23
Taking false branch
1636 BasePtr = BasePtrCast->getOperand(0);
1637
1638 // Check for identical base pointers to ensure that we do not miss index
1639 // offsets that have been added before this GEP is applied.
1640 if (BasePtr != BasePointer->getValue())
24
Called C++ object pointer is null
1641 return false;
1642
1643 std::vector<const SCEV *> SizesSCEV;
1644
1645 const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
1646
1647 Loop *SurroundingLoop = Stmt->getSurroundingLoop();
1648 for (auto *Subscript : Subscripts) {
1649 InvariantLoadsSetTy AccessILS;
1650 if (!isAffineExpr(&scop->getRegion(), SurroundingLoop, Subscript, SE,
1651 &AccessILS))
1652 return false;
1653
1654 for (LoadInst *LInst : AccessILS)
1655 if (!ScopRIL.count(LInst))
1656 return false;
1657 }
1658
1659 if (Sizes.empty())
1660 return false;
1661
1662 SizesSCEV.push_back(nullptr);
1663
1664 for (auto V : Sizes)
1665 SizesSCEV.push_back(SE.getSCEV(
1666 ConstantInt::get(IntegerType::getInt64Ty(BasePtr->getContext()), V)));
1667
1668 addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,
1669 true, Subscripts, SizesSCEV, Val);
1670 return true;
1671}
1672
1673bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) {
1674 if (!PollyDelinearize)
1675 return false;
1676
1677 Value *Address = Inst.getPointerOperand();
1678 Value *Val = Inst.getValueOperand();
1679 Type *ElementType = Val->getType();
1680 unsigned ElementSize = DL.getTypeAllocSize(ElementType);
1681 enum MemoryAccess::AccessType AccType =
1682 isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
1683
1684 const SCEV *AccessFunction =
1685 SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
1686 const SCEVUnknown *BasePointer =
1687 dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
1688
1689 assert(BasePointer && "Could not find base pointer")((BasePointer && "Could not find base pointer") ? static_cast
<void> (0) : __assert_fail ("BasePointer && \"Could not find base pointer\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1689, __PRETTY_FUNCTION__))
;
1690
1691 auto &InsnToMemAcc = scop->getInsnToMemAccMap();
1692 auto AccItr = InsnToMemAcc.find(Inst);
1693 if (AccItr == InsnToMemAcc.end())
1694 return false;
1695
1696 std::vector<const SCEV *> Sizes = {nullptr};
1697
1698 Sizes.insert(Sizes.end(), AccItr->second.Shape->DelinearizedSizes.begin(),
1699 AccItr->second.Shape->DelinearizedSizes.end());
1700
1701 // In case only the element size is contained in the 'Sizes' array, the
1702 // access does not access a real multi-dimensional array. Hence, we allow
1703 // the normal single-dimensional access construction to handle this.
1704 if (Sizes.size() == 1)
1705 return false;
1706
1707 // Remove the element size. This information is already provided by the
1708 // ElementSize parameter. In case the element size of this access and the
1709 // element size used for delinearization differs the delinearization is
1710 // incorrect. Hence, we invalidate the scop.
1711 //
1712 // TODO: Handle delinearization with differing element sizes.
1713 auto DelinearizedSize =
1714 cast<SCEVConstant>(Sizes.back())->getAPInt().getSExtValue();
1715 Sizes.pop_back();
1716 if (ElementSize != DelinearizedSize)
1717 scop->invalidate(DELINEARIZATION, Inst->getDebugLoc(), Inst->getParent());
1718
1719 addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,
1720 true, AccItr->second.DelinearizedSubscripts, Sizes, Val);
1721 return true;
1722}
1723
1724bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) {
1725 auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Inst);
1726
1727 if (MemIntr == nullptr)
1728 return false;
1729
1730 auto *L = LI.getLoopFor(Inst->getParent());
1731 auto *LengthVal = SE.getSCEVAtScope(MemIntr->getLength(), L);
1732 assert(LengthVal)((LengthVal) ? static_cast<void> (0) : __assert_fail ("LengthVal"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1732, __PRETTY_FUNCTION__))
;
1733
1734 // Check if the length val is actually affine or if we overapproximate it
1735 InvariantLoadsSetTy AccessILS;
1736 const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
1737
1738 Loop *SurroundingLoop = Stmt->getSurroundingLoop();
1739 bool LengthIsAffine = isAffineExpr(&scop->getRegion(), SurroundingLoop,
1740 LengthVal, SE, &AccessILS);
1741 for (LoadInst *LInst : AccessILS)
1742 if (!ScopRIL.count(LInst))
1743 LengthIsAffine = false;
1744 if (!LengthIsAffine)
1745 LengthVal = nullptr;
1746
1747 auto *DestPtrVal = MemIntr->getDest();
1748 assert(DestPtrVal)((DestPtrVal) ? static_cast<void> (0) : __assert_fail (
"DestPtrVal", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1748, __PRETTY_FUNCTION__))
;
1749
1750 auto *DestAccFunc = SE.getSCEVAtScope(DestPtrVal, L);
1751 assert(DestAccFunc)((DestAccFunc) ? static_cast<void> (0) : __assert_fail (
"DestAccFunc", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1751, __PRETTY_FUNCTION__))
;
1752 // Ignore accesses to "NULL".
1753 // TODO: We could use this to optimize the region further, e.g., intersect
1754 // the context with
1755 // isl_set_complement(isl_set_params(getDomain()))
1756 // as we know it would be undefined to execute this instruction anyway.
1757 if (DestAccFunc->isZero())
1758 return true;
1759
1760 auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(DestAccFunc));
1761 assert(DestPtrSCEV)((DestPtrSCEV) ? static_cast<void> (0) : __assert_fail (
"DestPtrSCEV", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1761, __PRETTY_FUNCTION__))
;
1762 DestAccFunc = SE.getMinusSCEV(DestAccFunc, DestPtrSCEV);
1763 addArrayAccess(Stmt, Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),
1764 IntegerType::getInt8Ty(DestPtrVal->getContext()),
1765 LengthIsAffine, {DestAccFunc, LengthVal}, {nullptr},
1766 Inst.getValueOperand());
1767
1768 auto *MemTrans = dyn_cast<MemTransferInst>(MemIntr);
1769 if (!MemTrans)
1770 return true;
1771
1772 auto *SrcPtrVal = MemTrans->getSource();
1773 assert(SrcPtrVal)((SrcPtrVal) ? static_cast<void> (0) : __assert_fail ("SrcPtrVal"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1773, __PRETTY_FUNCTION__))
;
1774
1775 auto *SrcAccFunc = SE.getSCEVAtScope(SrcPtrVal, L);
1776 assert(SrcAccFunc)((SrcAccFunc) ? static_cast<void> (0) : __assert_fail (
"SrcAccFunc", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1776, __PRETTY_FUNCTION__))
;
1777 // Ignore accesses to "NULL".
1778 // TODO: See above TODO
1779 if (SrcAccFunc->isZero())
1780 return true;
1781
1782 auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(SrcAccFunc));
1783 assert(SrcPtrSCEV)((SrcPtrSCEV) ? static_cast<void> (0) : __assert_fail (
"SrcPtrSCEV", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1783, __PRETTY_FUNCTION__))
;
1784 SrcAccFunc = SE.getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
1785 addArrayAccess(Stmt, Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
1786 IntegerType::getInt8Ty(SrcPtrVal->getContext()),
1787 LengthIsAffine, {SrcAccFunc, LengthVal}, {nullptr},
1788 Inst.getValueOperand());
1789
1790 return true;
1791}
1792
1793bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) {
1794 auto *CI = dyn_cast_or_null<CallInst>(Inst);
1795
1796 if (CI == nullptr)
1797 return false;
1798
1799 if (CI->doesNotAccessMemory() || isIgnoredIntrinsic(CI) || isDebugCall(CI))
1800 return true;
1801
1802 bool ReadOnly = false;
1803 auto *AF = SE.getConstant(IntegerType::getInt64Ty(CI->getContext()), 0);
1804 auto *CalledFunction = CI->getCalledFunction();
1805 switch (AA.getModRefBehavior(CalledFunction)) {
1806 case FMRB_UnknownModRefBehavior:
1807 llvm_unreachable("Unknown mod ref behaviour cannot be represented.")::llvm::llvm_unreachable_internal("Unknown mod ref behaviour cannot be represented."
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1807)
;
1808 case FMRB_DoesNotAccessMemory:
1809 return true;
1810 case FMRB_DoesNotReadMemory:
1811 case FMRB_OnlyAccessesInaccessibleMem:
1812 case FMRB_OnlyAccessesInaccessibleOrArgMem:
1813 return false;
1814 case FMRB_OnlyReadsMemory:
1815 GlobalReads.emplace_back(Stmt, CI);
1816 return true;
1817 case FMRB_OnlyReadsArgumentPointees:
1818 ReadOnly = true;
1819 LLVM_FALLTHROUGH[[gnu::fallthrough]];
1820 case FMRB_OnlyAccessesArgumentPointees: {
1821 auto AccType = ReadOnly ? MemoryAccess::READ : MemoryAccess::MAY_WRITE;
1822 Loop *L = LI.getLoopFor(Inst->getParent());
1823 for (const auto &Arg : CI->arg_operands()) {
1824 if (!Arg->getType()->isPointerTy())
1825 continue;
1826
1827 auto *ArgSCEV = SE.getSCEVAtScope(Arg, L);
1828 if (ArgSCEV->isZero())
1829 continue;
1830
1831 auto *ArgBasePtr = cast<SCEVUnknown>(SE.getPointerBase(ArgSCEV));
1832 addArrayAccess(Stmt, Inst, AccType, ArgBasePtr->getValue(),
1833 ArgBasePtr->getType(), false, {AF}, {nullptr}, CI);
1834 }
1835 return true;
1836 }
1837 }
1838
1839 return true;
1840}
1841
1842void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) {
1843 Value *Address = Inst.getPointerOperand();
1844 Value *Val = Inst.getValueOperand();
1845 Type *ElementType = Val->getType();
1846 enum MemoryAccess::AccessType AccType =
1847 isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
1848
1849 const SCEV *AccessFunction =
1850 SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
1851 const SCEVUnknown *BasePointer =
1852 dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
1853
1854 assert(BasePointer && "Could not find base pointer")((BasePointer && "Could not find base pointer") ? static_cast
<void> (0) : __assert_fail ("BasePointer && \"Could not find base pointer\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 1854, __PRETTY_FUNCTION__))
;
1855 AccessFunction = SE.getMinusSCEV(AccessFunction, BasePointer);
1856
1857 // Check if the access depends on a loop contained in a non-affine subregion.
1858 bool isVariantInNonAffineLoop = false;
1859 SetVector<const Loop *> Loops;
1860 findLoops(AccessFunction, Loops);
1861 for (const Loop *L : Loops)
1862 if (Stmt->contains(L)) {
1863 isVariantInNonAffineLoop = true;
1864 break;
1865 }
1866
1867 InvariantLoadsSetTy AccessILS;
1868
1869 Loop *SurroundingLoop = Stmt->getSurroundingLoop();
1870 bool IsAffine = !isVariantInNonAffineLoop &&
1871 isAffineExpr(&scop->getRegion(), SurroundingLoop,
1872 AccessFunction, SE, &AccessILS);
1873
1874 const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
1875 for (LoadInst *LInst : AccessILS)
1876 if (!ScopRIL.count(LInst))
1877 IsAffine = false;
1878
1879 if (!IsAffine && AccType == MemoryAccess::MUST_WRITE)
1880 AccType = MemoryAccess::MAY_WRITE;
1881
1882 addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,
1883 IsAffine, {AccessFunction}, {nullptr}, Val);
1884}
1885
1886void ScopBuilder::buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt) {
1887 if (buildAccessMemIntrinsic(Inst, Stmt))
11
Taking false branch
1888 return;
1889
1890 if (buildAccessCallInst(Inst, Stmt))
12
Taking false branch
1891 return;
1892
1893 if (buildAccessMultiDimFixed(Inst, Stmt))
13
Calling 'ScopBuilder::buildAccessMultiDimFixed'
1894 return;
1895
1896 if (buildAccessMultiDimParam(Inst, Stmt))
1897 return;
1898
1899 buildAccessSingleDim(Inst, Stmt);
1900}
1901
1902void ScopBuilder::buildAccessFunctions() {
1903 for (auto &Stmt : *scop) {
1904 if (Stmt.isBlockStmt()) {
1905 buildAccessFunctions(&Stmt, *Stmt.getBasicBlock());
1906 continue;
1907 }
1908
1909 Region *R = Stmt.getRegion();
1910 for (BasicBlock *BB : R->blocks())
1911 buildAccessFunctions(&Stmt, *BB, R);
1912 }
1913
1914 // Build write accesses for values that are used after the SCoP.
1915 // The instructions defining them might be synthesizable and therefore not
1916 // contained in any statement, hence we iterate over the original instructions
1917 // to identify all escaping values.
1918 for (BasicBlock *BB : scop->getRegion().blocks()) {
1919 for (Instruction &Inst : *BB)
1920 buildEscapingDependences(&Inst);
1921 }
1922}
1923
1924bool ScopBuilder::shouldModelInst(Instruction *Inst, Loop *L) {
1925 return !Inst->isTerminator() && !isIgnoredIntrinsic(Inst) &&
1926 !canSynthesize(Inst, *scop, &SE, L);
1927}
1928
1929/// Generate a name for a statement.
1930///
1931/// @param BB The basic block the statement will represent.
1932/// @param BBIdx The index of the @p BB relative to other BBs/regions.
1933/// @param Count The index of the created statement in @p BB.
1934/// @param IsMain Whether this is the main of all statement for @p BB. If true,
1935/// no suffix will be added.
1936/// @param IsLast Uses a special indicator for the last statement of a BB.
1937static std::string makeStmtName(BasicBlock *BB, long BBIdx, int Count,
1938 bool IsMain, bool IsLast = false) {
1939 std::string Suffix;
1940 if (!IsMain) {
1941 if (UseInstructionNames)
1942 Suffix = '_';
1943 if (IsLast)
1944 Suffix += "last";
1945 else if (Count < 26)
1946 Suffix += 'a' + Count;
1947 else
1948 Suffix += std::to_string(Count);
1949 }
1950 return getIslCompatibleName("Stmt", BB, BBIdx, Suffix, UseInstructionNames);
1951}
1952
1953/// Generate a name for a statement that represents a non-affine subregion.
1954///
1955/// @param R The region the statement will represent.
1956/// @param RIdx The index of the @p R relative to other BBs/regions.
1957static std::string makeStmtName(Region *R, long RIdx) {
1958 return getIslCompatibleName("Stmt", R->getNameStr(), RIdx, "",
1959 UseInstructionNames);
1960}
1961
1962void ScopBuilder::buildSequentialBlockStmts(BasicBlock *BB, bool SplitOnStore) {
1963 Loop *SurroundingLoop = LI.getLoopFor(BB);
1964
1965 int Count = 0;
1966 long BBIdx = scop->getNextStmtIdx();
1967 std::vector<Instruction *> Instructions;
1968 for (Instruction &Inst : *BB) {
1969 if (shouldModelInst(&Inst, SurroundingLoop))
1970 Instructions.push_back(&Inst);
1971 if (Inst.getMetadata("polly_split_after") ||
1972 (SplitOnStore && isa<StoreInst>(Inst))) {
1973 std::string Name = makeStmtName(BB, BBIdx, Count, Count == 0);
1974 scop->addScopStmt(BB, Name, SurroundingLoop, Instructions);
1975 Count++;
1976 Instructions.clear();
1977 }
1978 }
1979
1980 std::string Name = makeStmtName(BB, BBIdx, Count, Count == 0);
1981 scop->addScopStmt(BB, Name, SurroundingLoop, Instructions);
1982}
1983
1984/// Is @p Inst an ordered instruction?
1985///
1986/// An unordered instruction is an instruction, such that a sequence of
1987/// unordered instructions can be permuted without changing semantics. Any
1988/// instruction for which this is not always the case is ordered.
1989static bool isOrderedInstruction(Instruction *Inst) {
1990 return Inst->mayHaveSideEffects() || Inst->mayReadOrWriteMemory();
1991}
1992
1993/// Join instructions to the same statement if one uses the scalar result of the
1994/// other.
1995static void joinOperandTree(EquivalenceClasses<Instruction *> &UnionFind,
1996 ArrayRef<Instruction *> ModeledInsts) {
1997 for (Instruction *Inst : ModeledInsts) {
1998 if (isa<PHINode>(Inst))
1999 continue;
2000
2001 for (Use &Op : Inst->operands()) {
2002 Instruction *OpInst = dyn_cast<Instruction>(Op.get());
2003 if (!OpInst)
2004 continue;
2005
2006 // Check if OpInst is in the BB and is a modeled instruction.
2007 auto OpVal = UnionFind.findValue(OpInst);
2008 if (OpVal == UnionFind.end())
2009 continue;
2010
2011 UnionFind.unionSets(Inst, OpInst);
2012 }
2013 }
2014}
2015
2016/// Ensure that the order of ordered instructions does not change.
2017///
2018/// If we encounter an ordered instruction enclosed in instructions belonging to
2019/// a different statement (which might as well contain ordered instructions, but
2020/// this is not tested here), join them.
2021static void
2022joinOrderedInstructions(EquivalenceClasses<Instruction *> &UnionFind,
2023 ArrayRef<Instruction *> ModeledInsts) {
2024 SetVector<Instruction *> SeenLeaders;
2025 for (Instruction *Inst : ModeledInsts) {
2026 if (!isOrderedInstruction(Inst))
2027 continue;
2028
2029 Instruction *Leader = UnionFind.getLeaderValue(Inst);
2030 // Since previous iterations might have merged sets, some items in
2031 // SeenLeaders are not leaders anymore. However, The new leader of
2032 // previously merged instructions must be one of the former leaders of
2033 // these merged instructions.
2034 bool Inserted = SeenLeaders.insert(Leader);
2035 if (Inserted)
2036 continue;
2037
2038 // Merge statements to close holes. Say, we have already seen statements A
2039 // and B, in this order. Then we see an instruction of A again and we would
2040 // see the pattern "A B A". This function joins all statements until the
2041 // only seen occurrence of A.
2042 for (Instruction *Prev : reverse(SeenLeaders)) {
2043 // We are backtracking from the last element until we see Inst's leader
2044 // in SeenLeaders and merge all into one set. Although leaders of
2045 // instructions change during the execution of this loop, it's irrelevant
2046 // as we are just searching for the element that we already confirmed is
2047 // in the list.
2048 if (Prev == Leader)
2049 break;
2050 UnionFind.unionSets(Prev, Leader);
2051 }
2052 }
2053}
2054
2055/// If the BasicBlock has an edge from itself, ensure that the PHI WRITEs for
2056/// the incoming values from this block are executed after the PHI READ.
2057///
2058/// Otherwise it could overwrite the incoming value from before the BB with the
2059/// value for the next execution. This can happen if the PHI WRITE is added to
2060/// the statement with the instruction that defines the incoming value (instead
2061/// of the last statement of the same BB). To ensure that the PHI READ and WRITE
2062/// are in order, we put both into the statement. PHI WRITEs are always executed
2063/// after PHI READs when they are in the same statement.
2064///
2065/// TODO: This is an overpessimization. We only have to ensure that the PHI
2066/// WRITE is not put into a statement containing the PHI itself. That could also
2067/// be done by
2068/// - having all (strongly connected) PHIs in a single statement,
2069/// - unite only the PHIs in the operand tree of the PHI WRITE (because it only
2070/// has a chance of being lifted before a PHI by being in a statement with a
2071/// PHI that comes before in the basic block), or
2072/// - when uniting statements, ensure that no (relevant) PHIs are overtaken.
2073static void joinOrderedPHIs(EquivalenceClasses<Instruction *> &UnionFind,
2074 ArrayRef<Instruction *> ModeledInsts) {
2075 for (Instruction *Inst : ModeledInsts) {
2076 PHINode *PHI = dyn_cast<PHINode>(Inst);
2077 if (!PHI)
2078 continue;
2079
2080 int Idx = PHI->getBasicBlockIndex(PHI->getParent());
2081 if (Idx < 0)
2082 continue;
2083
2084 Instruction *IncomingVal =
2085 dyn_cast<Instruction>(PHI->getIncomingValue(Idx));
2086 if (!IncomingVal)
2087 continue;
2088
2089 UnionFind.unionSets(PHI, IncomingVal);
2090 }
2091}
2092
2093void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) {
2094 Loop *L = LI.getLoopFor(BB);
2095
2096 // Extracting out modeled instructions saves us from checking
2097 // shouldModelInst() repeatedly.
2098 SmallVector<Instruction *, 32> ModeledInsts;
2099 EquivalenceClasses<Instruction *> UnionFind;
2100 Instruction *MainInst = nullptr, *MainLeader = nullptr;
2101 for (Instruction &Inst : *BB) {
2102 if (!shouldModelInst(&Inst, L))
2103 continue;
2104 ModeledInsts.push_back(&Inst);
2105 UnionFind.insert(&Inst);
2106
2107 // When a BB is split into multiple statements, the main statement is the
2108 // one containing the 'main' instruction. We select the first instruction
2109 // that is unlikely to be removed (because it has side-effects) as the main
2110 // one. It is used to ensure that at least one statement from the bb has the
2111 // same name as with -polly-stmt-granularity=bb.
2112 if (!MainInst && (isa<StoreInst>(Inst) ||
2113 (isa<CallInst>(Inst) && !isa<IntrinsicInst>(Inst))))
2114 MainInst = &Inst;
2115 }
2116
2117 joinOperandTree(UnionFind, ModeledInsts);
2118 joinOrderedInstructions(UnionFind, ModeledInsts);
2119 joinOrderedPHIs(UnionFind, ModeledInsts);
2120
2121 // The list of instructions for statement (statement represented by the leader
2122 // instruction). The order of statements instructions is reversed such that
2123 // the epilogue is first. This makes it easier to ensure that the epilogue is
2124 // the last statement.
2125 MapVector<Instruction *, std::vector<Instruction *>> LeaderToInstList;
2126
2127 // Collect the instructions of all leaders. UnionFind's member iterator
2128 // unfortunately are not in any specific order.
2129 for (Instruction &Inst : reverse(*BB)) {
2130 auto LeaderIt = UnionFind.findLeader(&Inst);
2131 if (LeaderIt == UnionFind.member_end())
2132 continue;
2133
2134 if (&Inst == MainInst)
2135 MainLeader = *LeaderIt;
2136 std::vector<Instruction *> &InstList = LeaderToInstList[*LeaderIt];
2137 InstList.push_back(&Inst);
2138 }
2139
2140 // Finally build the statements.
2141 int Count = 0;
2142 long BBIdx = scop->getNextStmtIdx();
2143 for (auto &Instructions : reverse(LeaderToInstList)) {
2144 std::vector<Instruction *> &InstList = Instructions.second;
2145
2146 // If there is no main instruction, make the first statement the main.
2147 bool IsMain = (MainInst ? MainLeader == Instructions.first : Count == 0);
2148
2149 std::reverse(InstList.begin(), InstList.end());
2150 std::string Name = makeStmtName(BB, BBIdx, Count, IsMain);
2151 scop->addScopStmt(BB, Name, L, std::move(InstList));
2152 Count += 1;
2153 }
2154
2155 // Unconditionally add an epilogue (last statement). It contains no
2156 // instructions, but holds the PHI write accesses for successor basic blocks,
2157 // if the incoming value is not defined in another statement if the same BB.
2158 // The epilogue becomes the main statement only if there is no other
2159 // statement that could become main.
2160 // The epilogue will be removed if no PHIWrite is added to it.
2161 std::string EpilogueName = makeStmtName(BB, BBIdx, Count, Count == 0, true);
2162 scop->addScopStmt(BB, EpilogueName, L, {});
2163}
2164
2165void ScopBuilder::buildStmts(Region &SR) {
2166 if (scop->isNonAffineSubRegion(&SR)) {
2167 std::vector<Instruction *> Instructions;
2168 Loop *SurroundingLoop =
2169 getFirstNonBoxedLoopFor(SR.getEntry(), LI, scop->getBoxedLoops());
2170 for (Instruction &Inst : *SR.getEntry())
2171 if (shouldModelInst(&Inst, SurroundingLoop))
2172 Instructions.push_back(&Inst);
2173 long RIdx = scop->getNextStmtIdx();
2174 std::string Name = makeStmtName(&SR, RIdx);
2175 scop->addScopStmt(&SR, Name, SurroundingLoop, Instructions);
2176 return;
2177 }
2178
2179 for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
2180 if (I->isSubRegion())
2181 buildStmts(*I->getNodeAs<Region>());
2182 else {
2183 BasicBlock *BB = I->getNodeAs<BasicBlock>();
2184 switch (StmtGranularity) {
2185 case GranularityChoice::BasicBlocks:
2186 buildSequentialBlockStmts(BB);
2187 break;
2188 case GranularityChoice::ScalarIndependence:
2189 buildEqivClassBlockStmts(BB);
2190 break;
2191 case GranularityChoice::Stores:
2192 buildSequentialBlockStmts(BB, true);
2193 break;
2194 }
2195 }
2196}
2197
2198void ScopBuilder::buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,
2199 Region *NonAffineSubRegion) {
2200 assert(((Stmt && "The exit BB is the only one that cannot be represented by a statement"
) ? static_cast<void> (0) : __assert_fail ("Stmt && \"The exit BB is the only one that cannot be represented by a statement\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 2202, __PRETTY_FUNCTION__))
2201 Stmt &&((Stmt && "The exit BB is the only one that cannot be represented by a statement"
) ? static_cast<void> (0) : __assert_fail ("Stmt && \"The exit BB is the only one that cannot be represented by a statement\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 2202, __PRETTY_FUNCTION__))
2202 "The exit BB is the only one that cannot be represented by a statement")((Stmt && "The exit BB is the only one that cannot be represented by a statement"
) ? static_cast<void> (0) : __assert_fail ("Stmt && \"The exit BB is the only one that cannot be represented by a statement\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 2202, __PRETTY_FUNCTION__))
;
2203 assert(Stmt->represents(&BB))((Stmt->represents(&BB)) ? static_cast<void> (0)
: __assert_fail ("Stmt->represents(&BB)", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 2203, __PRETTY_FUNCTION__))
;
2204
2205 // We do not build access functions for error blocks, as they may contain
2206 // instructions we can not model.
2207 if (isErrorBlock(BB, scop->getRegion(), LI, DT))
2208 return;
2209
2210 auto BuildAccessesForInst = [this, Stmt,
2211 NonAffineSubRegion](Instruction *Inst) {
2212 PHINode *PHI = dyn_cast<PHINode>(Inst);
2213 if (PHI)
2214 buildPHIAccesses(Stmt, PHI, NonAffineSubRegion, false);
2215
2216 if (auto MemInst = MemAccInst::dyn_cast(*Inst)) {
2217 assert(Stmt && "Cannot build access function in non-existing statement")((Stmt && "Cannot build access function in non-existing statement"
) ? static_cast<void> (0) : __assert_fail ("Stmt && \"Cannot build access function in non-existing statement\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 2217, __PRETTY_FUNCTION__))
;
2218 buildMemoryAccess(MemInst, Stmt);
2219 }
2220
2221 // PHI nodes have already been modeled above and terminators that are
2222 // not part of a non-affine subregion are fully modeled and regenerated
2223 // from the polyhedral domains. Hence, they do not need to be modeled as
2224 // explicit data dependences.
2225 if (!PHI)
2226 buildScalarDependences(Stmt, Inst);
2227 };
2228
2229 const InvariantLoadsSetTy &RIL = scop->getRequiredInvariantLoads();
2230 bool IsEntryBlock = (Stmt->getEntryBlock() == &BB);
2231 if (IsEntryBlock) {
2232 for (Instruction *Inst : Stmt->getInstructions())
2233 BuildAccessesForInst(Inst);
2234 if (Stmt->isRegionStmt())
2235 BuildAccessesForInst(BB.getTerminator());
2236 } else {
2237 for (Instruction &Inst : BB) {
2238 if (isIgnoredIntrinsic(&Inst))
2239 continue;
2240
2241 // Invariant loads already have been processed.
2242 if (isa<LoadInst>(Inst) && RIL.count(cast<LoadInst>(&Inst)))
2243 continue;
2244
2245 BuildAccessesForInst(&Inst);
2246 }
2247 }
2248}
2249
2250MemoryAccess *ScopBuilder::addMemoryAccess(
2251 ScopStmt *Stmt, Instruction *Inst, MemoryAccess::AccessType AccType,
2252 Value *BaseAddress, Type *ElementType, bool Affine, Value *AccessValue,
2253 ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
2254 MemoryKind Kind) {
2255 bool isKnownMustAccess = false;
2256
2257 // Accesses in single-basic block statements are always executed.
2258 if (Stmt->isBlockStmt())
2259 isKnownMustAccess = true;
2260
2261 if (Stmt->isRegionStmt()) {
2262 // Accesses that dominate the exit block of a non-affine region are always
2263 // executed. In non-affine regions there may exist MemoryKind::Values that
2264 // do not dominate the exit. MemoryKind::Values will always dominate the
2265 // exit and MemoryKind::PHIs only if there is at most one PHI_WRITE in the
2266 // non-affine region.
2267 if (Inst && DT.dominates(Inst->getParent(), Stmt->getRegion()->getExit()))
2268 isKnownMustAccess = true;
2269 }
2270
2271 // Non-affine PHI writes do not "happen" at a particular instruction, but
2272 // after exiting the statement. Therefore they are guaranteed to execute and
2273 // overwrite the old value.
2274 if (Kind == MemoryKind::PHI || Kind == MemoryKind::ExitPHI)
2275 isKnownMustAccess = true;
2276
2277 if (!isKnownMustAccess && AccType == MemoryAccess::MUST_WRITE)
2278 AccType = MemoryAccess::MAY_WRITE;
2279
2280 auto *Access = new MemoryAccess(Stmt, Inst, AccType, BaseAddress, ElementType,
2281 Affine, Subscripts, Sizes, AccessValue, Kind);
2282
2283 scop->addAccessFunction(Access);
2284 Stmt->addAccess(Access);
2285 return Access;
2286}
2287
2288void ScopBuilder::addArrayAccess(ScopStmt *Stmt, MemAccInst MemAccInst,
2289 MemoryAccess::AccessType AccType,
2290 Value *BaseAddress, Type *ElementType,
2291 bool IsAffine,
2292 ArrayRef<const SCEV *> Subscripts,
2293 ArrayRef<const SCEV *> Sizes,
2294 Value *AccessValue) {
2295 ArrayBasePointers.insert(BaseAddress);
2296 auto *MemAccess = addMemoryAccess(Stmt, MemAccInst, AccType, BaseAddress,
2297 ElementType, IsAffine, AccessValue,
2298 Subscripts, Sizes, MemoryKind::Array);
2299
2300 if (!DetectFortranArrays)
2301 return;
2302
2303 if (Value *FAD = findFADAllocationInvisible(MemAccInst))
2304 MemAccess->setFortranArrayDescriptor(FAD);
2305 else if (Value *FAD = findFADAllocationVisible(MemAccInst))
2306 MemAccess->setFortranArrayDescriptor(FAD);
2307}
2308
2309/// Check if @p Expr is divisible by @p Size.
2310static bool isDivisible(const SCEV *Expr, unsigned Size, ScalarEvolution &SE) {
2311 assert(Size != 0)((Size != 0) ? static_cast<void> (0) : __assert_fail ("Size != 0"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 2311, __PRETTY_FUNCTION__))
;
2312 if (Size == 1)
2313 return true;
2314
2315 // Only one factor needs to be divisible.
2316 if (auto *MulExpr = dyn_cast<SCEVMulExpr>(Expr)) {
2317 for (auto *FactorExpr : MulExpr->operands())
2318 if (isDivisible(FactorExpr, Size, SE))
2319 return true;
2320 return false;
2321 }
2322
2323 // For other n-ary expressions (Add, AddRec, Max,...) all operands need
2324 // to be divisible.
2325 if (auto *NAryExpr = dyn_cast<SCEVNAryExpr>(Expr)) {
2326 for (auto *OpExpr : NAryExpr->operands())
2327 if (!isDivisible(OpExpr, Size, SE))
2328 return false;
2329 return true;
2330 }
2331
2332 auto *SizeSCEV = SE.getConstant(Expr->getType(), Size);
2333 auto *UDivSCEV = SE.getUDivExpr(Expr, SizeSCEV);
2334 auto *MulSCEV = SE.getMulExpr(UDivSCEV, SizeSCEV);
2335 return MulSCEV == Expr;
2336}
2337
2338void ScopBuilder::foldSizeConstantsToRight() {
2339 isl::union_set Accessed = scop->getAccesses().range();
2340
2341 for (auto Array : scop->arrays()) {
2342 if (Array->getNumberOfDimensions() <= 1)
2343 continue;
2344
2345 isl::space Space = Array->getSpace();
2346 Space = Space.align_params(Accessed.get_space());
2347
2348 if (!Accessed.contains(Space))
2349 continue;
2350
2351 isl::set Elements = Accessed.extract_set(Space);
2352 isl::map Transform = isl::map::universe(Array->getSpace().map_from_set());
2353
2354 std::vector<int> Int;
2355 int Dims = Elements.dim(isl::dim::set);
2356 for (int i = 0; i < Dims; i++) {
2357 isl::set DimOnly = isl::set(Elements).project_out(isl::dim::set, 0, i);
2358 DimOnly = DimOnly.project_out(isl::dim::set, 1, Dims - i - 1);
2359 DimOnly = DimOnly.lower_bound_si(isl::dim::set, 0, 0);
2360
2361 isl::basic_set DimHull = DimOnly.affine_hull();
2362
2363 if (i == Dims - 1) {
2364 Int.push_back(1);
2365 Transform = Transform.equate(isl::dim::in, i, isl::dim::out, i);
2366 continue;
2367 }
2368
2369 if (DimHull.dim(isl::dim::div) == 1) {
2370 isl::aff Diff = DimHull.get_div(0);
2371 isl::val Val = Diff.get_denominator_val();
2372
2373 int ValInt = 1;
2374 if (Val.is_int()) {
2375 auto ValAPInt = APIntFromVal(Val);
2376 if (ValAPInt.isSignedIntN(32))
2377 ValInt = ValAPInt.getSExtValue();
2378 } else {
2379 }
2380
2381 Int.push_back(ValInt);
2382 isl::constraint C = isl::constraint::alloc_equality(
2383 isl::local_space(Transform.get_space()));
2384 C = C.set_coefficient_si(isl::dim::out, i, ValInt);
2385 C = C.set_coefficient_si(isl::dim::in, i, -1);
2386 Transform = Transform.add_constraint(C);
2387 continue;
2388 }
2389
2390 isl::basic_set ZeroSet = isl::basic_set(DimHull);
2391 ZeroSet = ZeroSet.fix_si(isl::dim::set, 0, 0);
2392
2393 int ValInt = 1;
2394 if (ZeroSet.is_equal(DimHull)) {
2395 ValInt = 0;
2396 }
2397
2398 Int.push_back(ValInt);
2399 Transform = Transform.equate(isl::dim::in, i, isl::dim::out, i);
2400 }
2401
2402 isl::set MappedElements = isl::map(Transform).domain();
2403 if (!Elements.is_subset(MappedElements))
2404 continue;
2405
2406 bool CanFold = true;
2407 if (Int[0] <= 1)
2408 CanFold = false;
2409
2410 unsigned NumDims = Array->getNumberOfDimensions();
2411 for (unsigned i = 1; i < NumDims - 1; i++)
2412 if (Int[0] != Int[i] && Int[i])
2413 CanFold = false;
2414
2415 if (!CanFold)
2416 continue;
2417
2418 for (auto &Access : scop->access_functions())
2419 if (Access->getScopArrayInfo() == Array)
2420 Access->setAccessRelation(
2421 Access->getAccessRelation().apply_range(Transform));
2422
2423 std::vector<const SCEV *> Sizes;
2424 for (unsigned i = 0; i < NumDims; i++) {
2425 auto Size = Array->getDimensionSize(i);
2426
2427 if (i == NumDims - 1)
2428 Size = SE.getMulExpr(Size, SE.getConstant(Size->getType(), Int[0]));
2429 Sizes.push_back(Size);
2430 }
2431
2432 Array->updateSizes(Sizes, false /* CheckConsistency */);
2433 }
2434}
2435
2436void ScopBuilder::markFortranArrays() {
2437 for (ScopStmt &Stmt : *scop) {
2438 for (MemoryAccess *MemAcc : Stmt) {
2439 Value *FAD = MemAcc->getFortranArrayDescriptor();
2440 if (!FAD)
2441 continue;
2442
2443 // TODO: const_cast-ing to edit
2444 ScopArrayInfo *SAI =
2445 const_cast<ScopArrayInfo *>(MemAcc->getLatestScopArrayInfo());
2446 assert(SAI && "memory access into a Fortran array does not "((SAI && "memory access into a Fortran array does not "
"have an associated ScopArrayInfo") ? static_cast<void>
(0) : __assert_fail ("SAI && \"memory access into a Fortran array does not \" \"have an associated ScopArrayInfo\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 2447, __PRETTY_FUNCTION__))
2447 "have an associated ScopArrayInfo")((SAI && "memory access into a Fortran array does not "
"have an associated ScopArrayInfo") ? static_cast<void>
(0) : __assert_fail ("SAI && \"memory access into a Fortran array does not \" \"have an associated ScopArrayInfo\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 2447, __PRETTY_FUNCTION__))
;
2448 SAI->applyAndSetFAD(FAD);
2449 }
2450 }
2451}
2452
2453void ScopBuilder::finalizeAccesses() {
2454 updateAccessDimensionality();
2455 foldSizeConstantsToRight();
2456 foldAccessRelations();
2457 assumeNoOutOfBounds();
2458 markFortranArrays();
2459}
2460
2461void ScopBuilder::updateAccessDimensionality() {
2462 // Check all array accesses for each base pointer and find a (virtual) element
2463 // size for the base pointer that divides all access functions.
2464 for (ScopStmt &Stmt : *scop)
2465 for (MemoryAccess *Access : Stmt) {
2466 if (!Access->isArrayKind())
2467 continue;
2468 ScopArrayInfo *Array =
2469 const_cast<ScopArrayInfo *>(Access->getScopArrayInfo());
2470
2471 if (Array->getNumberOfDimensions() != 1)
2472 continue;
2473 unsigned DivisibleSize = Array->getElemSizeInBytes();
2474 const SCEV *Subscript = Access->getSubscript(0);
2475 while (!isDivisible(Subscript, DivisibleSize, SE))
2476 DivisibleSize /= 2;
2477 auto *Ty = IntegerType::get(SE.getContext(), DivisibleSize * 8);
2478 Array->updateElementType(Ty);
2479 }
2480
2481 for (auto &Stmt : *scop)
2482 for (auto &Access : Stmt)
2483 Access->updateDimensionality();
2484}
2485
2486void ScopBuilder::foldAccessRelations() {
2487 for (auto &Stmt : *scop)
2488 for (auto &Access : Stmt)
2489 Access->foldAccessRelation();
2490}
2491
2492void ScopBuilder::assumeNoOutOfBounds() {
2493 for (auto &Stmt : *scop)
2494 for (auto &Access : Stmt)
2495 Access->assumeNoOutOfBound();
2496}
2497
2498void ScopBuilder::ensureValueWrite(Instruction *Inst) {
2499 // Find the statement that defines the value of Inst. That statement has to
2500 // write the value to make it available to those statements that read it.
2501 ScopStmt *Stmt = scop->getStmtFor(Inst);
2502
2503 // It is possible that the value is synthesizable within a loop (such that it
2504 // is not part of any statement), but not after the loop (where you need the
2505 // number of loop round-trips to synthesize it). In LCSSA-form a PHI node will
2506 // avoid this. In case the IR has no such PHI, use the last statement (where
2507 // the value is synthesizable) to write the value.
2508 if (!Stmt)
2509 Stmt = scop->getLastStmtFor(Inst->getParent());
2510
2511 // Inst not defined within this SCoP.
2512 if (!Stmt)
2513 return;
2514
2515 // Do not process further if the instruction is already written.
2516 if (Stmt->lookupValueWriteOf(Inst))
2517 return;
2518
2519 addMemoryAccess(Stmt, Inst, MemoryAccess::MUST_WRITE, Inst, Inst->getType(),
2520 true, Inst, ArrayRef<const SCEV *>(),
2521 ArrayRef<const SCEV *>(), MemoryKind::Value);
2522}
2523
2524void ScopBuilder::ensureValueRead(Value *V, ScopStmt *UserStmt) {
2525 // TODO: Make ScopStmt::ensureValueRead(Value*) offer the same functionality
2526 // to be able to replace this one. Currently, there is a split responsibility.
2527 // In a first step, the MemoryAccess is created, but without the
2528 // AccessRelation. In the second step by ScopStmt::buildAccessRelations(), the
2529 // AccessRelation is created. At least for scalar accesses, there is no new
2530 // information available at ScopStmt::buildAccessRelations(), so we could
2531 // create the AccessRelation right away. This is what
2532 // ScopStmt::ensureValueRead(Value*) does.
2533
2534 auto *Scope = UserStmt->getSurroundingLoop();
2535 auto VUse = VirtualUse::create(scop.get(), UserStmt, Scope, V, false);
2536 switch (VUse.getKind()) {
2537 case VirtualUse::Constant:
2538 case VirtualUse::Block:
2539 case VirtualUse::Synthesizable:
2540 case VirtualUse::Hoisted:
2541 case VirtualUse::Intra:
2542 // Uses of these kinds do not need a MemoryAccess.
2543 break;
2544
2545 case VirtualUse::ReadOnly:
2546 // Add MemoryAccess for invariant values only if requested.
2547 if (!ModelReadOnlyScalars)
2548 break;
2549
2550 LLVM_FALLTHROUGH[[gnu::fallthrough]];
2551 case VirtualUse::Inter:
2552
2553 // Do not create another MemoryAccess for reloading the value if one already
2554 // exists.
2555 if (UserStmt->lookupValueReadOf(V))
2556 break;
2557
2558 addMemoryAccess(UserStmt, nullptr, MemoryAccess::READ, V, V->getType(),
2559 true, V, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
2560 MemoryKind::Value);
2561
2562 // Inter-statement uses need to write the value in their defining statement.
2563 if (VUse.isInter())
2564 ensureValueWrite(cast<Instruction>(V));
2565 break;
2566 }
2567}
2568
2569void ScopBuilder::ensurePHIWrite(PHINode *PHI, ScopStmt *IncomingStmt,
2570 BasicBlock *IncomingBlock,
2571 Value *IncomingValue, bool IsExitBlock) {
2572 // As the incoming block might turn out to be an error statement ensure we
2573 // will create an exit PHI SAI object. It is needed during code generation
2574 // and would be created later anyway.
2575 if (IsExitBlock)
2576 scop->getOrCreateScopArrayInfo(PHI, PHI->getType(), {},
2577 MemoryKind::ExitPHI);
2578
2579 // This is possible if PHI is in the SCoP's entry block. The incoming blocks
2580 // from outside the SCoP's region have no statement representation.
2581 if (!IncomingStmt)
2582 return;
2583
2584 // Take care for the incoming value being available in the incoming block.
2585 // This must be done before the check for multiple PHI writes because multiple
2586 // exiting edges from subregion each can be the effective written value of the
2587 // subregion. As such, all of them must be made available in the subregion
2588 // statement.
2589 ensureValueRead(IncomingValue, IncomingStmt);
2590
2591 // Do not add more than one MemoryAccess per PHINode and ScopStmt.
2592 if (MemoryAccess *Acc = IncomingStmt->lookupPHIWriteOf(PHI)) {
2593 assert(Acc->getAccessInstruction() == PHI)((Acc->getAccessInstruction() == PHI) ? static_cast<void
> (0) : __assert_fail ("Acc->getAccessInstruction() == PHI"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 2593, __PRETTY_FUNCTION__))
;
2594 Acc->addIncoming(IncomingBlock, IncomingValue);
2595 return;
2596 }
2597
2598 MemoryAccess *Acc = addMemoryAccess(
2599 IncomingStmt, PHI, MemoryAccess::MUST_WRITE, PHI, PHI->getType(), true,
2600 PHI, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
2601 IsExitBlock ? MemoryKind::ExitPHI : MemoryKind::PHI);
2602 assert(Acc)((Acc) ? static_cast<void> (0) : __assert_fail ("Acc", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 2602, __PRETTY_FUNCTION__))
;
2603 Acc->addIncoming(IncomingBlock, IncomingValue);
2604}
2605
2606void ScopBuilder::addPHIReadAccess(ScopStmt *PHIStmt, PHINode *PHI) {
2607 addMemoryAccess(PHIStmt, PHI, MemoryAccess::READ, PHI, PHI->getType(), true,
2608 PHI, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
2609 MemoryKind::PHI);
2610}
2611
2612void ScopBuilder::buildDomain(ScopStmt &Stmt) {
2613 isl::id Id = isl::id::alloc(scop->getIslCtx(), Stmt.getBaseName(), &Stmt);
2614
2615 Stmt.Domain = scop->getDomainConditions(&Stmt);
2616 Stmt.Domain = Stmt.Domain.set_tuple_id(Id);
2617}
2618
2619void ScopBuilder::collectSurroundingLoops(ScopStmt &Stmt) {
2620 isl::set Domain = Stmt.getDomain();
2621 BasicBlock *BB = Stmt.getEntryBlock();
2622
2623 Loop *L = LI.getLoopFor(BB);
2624
2625 while (L && Stmt.isRegionStmt() && Stmt.getRegion()->contains(L))
2626 L = L->getParentLoop();
2627
2628 SmallVector<llvm::Loop *, 8> Loops;
2629
2630 while (L && Stmt.getParent()->getRegion().contains(L)) {
2631 Loops.push_back(L);
2632 L = L->getParentLoop();
2633 }
2634
2635 Stmt.NestLoops.insert(Stmt.NestLoops.begin(), Loops.rbegin(), Loops.rend());
2636}
2637
2638/// Return the reduction type for a given binary operator.
2639static MemoryAccess::ReductionType getReductionType(const BinaryOperator *BinOp,
2640 const Instruction *Load) {
2641 if (!BinOp)
2642 return MemoryAccess::RT_NONE;
2643 switch (BinOp->getOpcode()) {
2644 case Instruction::FAdd:
2645 if (!BinOp->isFast())
2646 return MemoryAccess::RT_NONE;
2647 LLVM_FALLTHROUGH[[gnu::fallthrough]];
2648 case Instruction::Add:
2649 return MemoryAccess::RT_ADD;
2650 case Instruction::Or:
2651 return MemoryAccess::RT_BOR;
2652 case Instruction::Xor:
2653 return MemoryAccess::RT_BXOR;
2654 case Instruction::And:
2655 return MemoryAccess::RT_BAND;
2656 case Instruction::FMul:
2657 if (!BinOp->isFast())
2658 return MemoryAccess::RT_NONE;
2659 LLVM_FALLTHROUGH[[gnu::fallthrough]];
2660 case Instruction::Mul:
2661 if (DisableMultiplicativeReductions)
2662 return MemoryAccess::RT_NONE;
2663 return MemoryAccess::RT_MUL;
2664 default:
2665 return MemoryAccess::RT_NONE;
2666 }
2667}
2668
2669void ScopBuilder::checkForReductions(ScopStmt &Stmt) {
2670 SmallVector<MemoryAccess *, 2> Loads;
2671 SmallVector<std::pair<MemoryAccess *, MemoryAccess *>, 4> Candidates;
2672
2673 // First collect candidate load-store reduction chains by iterating over all
2674 // stores and collecting possible reduction loads.
2675 for (MemoryAccess *StoreMA : Stmt) {
2676 if (StoreMA->isRead())
2677 continue;
2678
2679 Loads.clear();
2680 collectCandidateReductionLoads(StoreMA, Loads);
2681 for (MemoryAccess *LoadMA : Loads)
2682 Candidates.push_back(std::make_pair(LoadMA, StoreMA));
2683 }
2684
2685 // Then check each possible candidate pair.
2686 for (const auto &CandidatePair : Candidates) {
2687 bool Valid = true;
2688 isl::map LoadAccs = CandidatePair.first->getAccessRelation();
2689 isl::map StoreAccs = CandidatePair.second->getAccessRelation();
2690
2691 // Skip those with obviously unequal base addresses.
2692 if (!LoadAccs.has_equal_space(StoreAccs)) {
2693 continue;
2694 }
2695
2696 // And check if the remaining for overlap with other memory accesses.
2697 isl::map AllAccsRel = LoadAccs.unite(StoreAccs);
2698 AllAccsRel = AllAccsRel.intersect_domain(Stmt.getDomain());
2699 isl::set AllAccs = AllAccsRel.range();
2700
2701 for (MemoryAccess *MA : Stmt) {
2702 if (MA == CandidatePair.first || MA == CandidatePair.second)
2703 continue;
2704
2705 isl::map AccRel =
2706 MA->getAccessRelation().intersect_domain(Stmt.getDomain());
2707 isl::set Accs = AccRel.range();
2708
2709 if (AllAccs.has_equal_space(Accs)) {
2710 isl::set OverlapAccs = Accs.intersect(AllAccs);
2711 Valid = Valid && OverlapAccs.is_empty();
2712 }
2713 }
2714
2715 if (!Valid)
2716 continue;
2717
2718 const LoadInst *Load =
2719 dyn_cast<const LoadInst>(CandidatePair.first->getAccessInstruction());
2720 MemoryAccess::ReductionType RT =
2721 getReductionType(dyn_cast<BinaryOperator>(Load->user_back()), Load);
2722
2723 // If no overlapping access was found we mark the load and store as
2724 // reduction like.
2725 CandidatePair.first->markAsReductionLike(RT);
2726 CandidatePair.second->markAsReductionLike(RT);
2727 }
2728}
2729
2730void ScopBuilder::verifyInvariantLoads() {
2731 auto &RIL = scop->getRequiredInvariantLoads();
2732 for (LoadInst *LI : RIL) {
2733 assert(LI && scop->contains(LI))((LI && scop->contains(LI)) ? static_cast<void>
(0) : __assert_fail ("LI && scop->contains(LI)", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 2733, __PRETTY_FUNCTION__))
;
2734 // If there exists a statement in the scop which has a memory access for
2735 // @p LI, then mark this scop as infeasible for optimization.
2736 for (ScopStmt &Stmt : *scop)
2737 if (Stmt.getArrayAccessOrNULLFor(LI)) {
2738 scop->invalidate(INVARIANTLOAD, LI->getDebugLoc(), LI->getParent());
2739 return;
2740 }
2741 }
2742}
2743
2744void ScopBuilder::hoistInvariantLoads() {
2745 if (!PollyInvariantLoadHoisting)
2746 return;
2747
2748 isl::union_map Writes = scop->getWrites();
2749 for (ScopStmt &Stmt : *scop) {
2750 InvariantAccessesTy InvariantAccesses;
2751
2752 for (MemoryAccess *Access : Stmt)
2753 if (isl::set NHCtx = getNonHoistableCtx(Access, Writes))
2754 InvariantAccesses.push_back({Access, NHCtx});
2755
2756 // Transfer the memory access from the statement to the SCoP.
2757 for (auto InvMA : InvariantAccesses)
2758 Stmt.removeMemoryAccess(InvMA.MA);
2759 addInvariantLoads(Stmt, InvariantAccesses);
2760 }
2761}
2762
2763/// Check if an access range is too complex.
2764///
2765/// An access range is too complex, if it contains either many disjuncts or
2766/// very complex expressions. As a simple heuristic, we assume if a set to
2767/// be too complex if the sum of existentially quantified dimensions and
2768/// set dimensions is larger than a threshold. This reliably detects both
2769/// sets with many disjuncts as well as sets with many divisions as they
2770/// arise in h264.
2771///
2772/// @param AccessRange The range to check for complexity.
2773///
2774/// @returns True if the access range is too complex.
2775static bool isAccessRangeTooComplex(isl::set AccessRange) {
2776 int NumTotalDims = 0;
2777
2778 for (isl::basic_set BSet : AccessRange.get_basic_set_list()) {
2779 NumTotalDims += BSet.dim(isl::dim::div);
2780 NumTotalDims += BSet.dim(isl::dim::set);
2781 }
2782
2783 if (NumTotalDims > MaxDimensionsInAccessRange)
2784 return true;
2785
2786 return false;
2787}
2788
2789bool ScopBuilder::hasNonHoistableBasePtrInScop(MemoryAccess *MA,
2790 isl::union_map Writes) {
2791 if (auto *BasePtrMA = scop->lookupBasePtrAccess(MA)) {
2792 return getNonHoistableCtx(BasePtrMA, Writes).is_null();
2793 }
2794
2795 Value *BaseAddr = MA->getOriginalBaseAddr();
2796 if (auto *BasePtrInst = dyn_cast<Instruction>(BaseAddr))
2797 if (!isa<LoadInst>(BasePtrInst))
2798 return scop->contains(BasePtrInst);
2799
2800 return false;
2801}
2802
2803void ScopBuilder::addUserContext() {
2804 if (UserContextStr.empty())
2805 return;
2806
2807 isl::set UserContext = isl::set(scop->getIslCtx(), UserContextStr.c_str());
2808 isl::space Space = scop->getParamSpace();
2809 if (Space.dim(isl::dim::param) != UserContext.dim(isl::dim::param)) {
2810 std::string SpaceStr = Space.to_str();
2811 errs() << "Error: the context provided in -polly-context has not the same "
2812 << "number of dimensions than the computed context. Due to this "
2813 << "mismatch, the -polly-context option is ignored. Please provide "
2814 << "the context in the parameter space: " << SpaceStr << ".\n";
2815 return;
2816 }
2817
2818 for (unsigned i = 0; i < Space.dim(isl::dim::param); i++) {
2819 std::string NameContext =
2820 scop->getContext().get_dim_name(isl::dim::param, i);
2821 std::string NameUserContext = UserContext.get_dim_name(isl::dim::param, i);
2822
2823 if (NameContext != NameUserContext) {
2824 std::string SpaceStr = Space.to_str();
2825 errs() << "Error: the name of dimension " << i
2826 << " provided in -polly-context "
2827 << "is '" << NameUserContext << "', but the name in the computed "
2828 << "context is '" << NameContext
2829 << "'. Due to this name mismatch, "
2830 << "the -polly-context option is ignored. Please provide "
2831 << "the context in the parameter space: " << SpaceStr << ".\n";
2832 return;
2833 }
2834
2835 UserContext = UserContext.set_dim_id(isl::dim::param, i,
2836 Space.get_dim_id(isl::dim::param, i));
2837 }
2838 isl::set newContext = scop->getContext().intersect(UserContext);
2839 scop->setContext(newContext);
2840}
2841
2842isl::set ScopBuilder::getNonHoistableCtx(MemoryAccess *Access,
2843 isl::union_map Writes) {
2844 // TODO: Loads that are not loop carried, hence are in a statement with
2845 // zero iterators, are by construction invariant, though we
2846 // currently "hoist" them anyway. This is necessary because we allow
2847 // them to be treated as parameters (e.g., in conditions) and our code
2848 // generation would otherwise use the old value.
2849
2850 auto &Stmt = *Access->getStatement();
2851 BasicBlock *BB = Stmt.getEntryBlock();
2852
2853 if (Access->isScalarKind() || Access->isWrite() || !Access->isAffine() ||
2854 Access->isMemoryIntrinsic())
2855 return nullptr;
2856
2857 // Skip accesses that have an invariant base pointer which is defined but
2858 // not loaded inside the SCoP. This can happened e.g., if a readnone call
2859 // returns a pointer that is used as a base address. However, as we want
2860 // to hoist indirect pointers, we allow the base pointer to be defined in
2861 // the region if it is also a memory access. Each ScopArrayInfo object
2862 // that has a base pointer origin has a base pointer that is loaded and
2863 // that it is invariant, thus it will be hoisted too. However, if there is
2864 // no base pointer origin we check that the base pointer is defined
2865 // outside the region.
2866 auto *LI = cast<LoadInst>(Access->getAccessInstruction());
2867 if (hasNonHoistableBasePtrInScop(Access, Writes))
2868 return nullptr;
2869
2870 isl::map AccessRelation = Access->getAccessRelation();
2871 assert(!AccessRelation.is_empty())((!AccessRelation.is_empty()) ? static_cast<void> (0) :
__assert_fail ("!AccessRelation.is_empty()", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 2871, __PRETTY_FUNCTION__))
;
2872
2873 if (AccessRelation.involves_dims(isl::dim::in, 0, Stmt.getNumIterators()))
2874 return nullptr;
2875
2876 AccessRelation = AccessRelation.intersect_domain(Stmt.getDomain());
2877 isl::set SafeToLoad;
2878
2879 auto &DL = scop->getFunction().getParent()->getDataLayout();
2880 if (isSafeToLoadUnconditionally(LI->getPointerOperand(), LI->getType(),
2881 LI->getAlignment(), DL)) {
2882 SafeToLoad = isl::set::universe(AccessRelation.get_space().range());
2883 } else if (BB != LI->getParent()) {
2884 // Skip accesses in non-affine subregions as they might not be executed
2885 // under the same condition as the entry of the non-affine subregion.
2886 return nullptr;
2887 } else {
2888 SafeToLoad = AccessRelation.range();
2889 }
2890
2891 if (isAccessRangeTooComplex(AccessRelation.range()))
2892 return nullptr;
2893
2894 isl::union_map Written = Writes.intersect_range(SafeToLoad);
2895 isl::set WrittenCtx = Written.params();
2896 bool IsWritten = !WrittenCtx.is_empty();
2897
2898 if (!IsWritten)
2899 return WrittenCtx;
2900
2901 WrittenCtx = WrittenCtx.remove_divs();
2902 bool TooComplex = WrittenCtx.n_basic_set() >= MaxDisjunctsInDomain;
2903 if (TooComplex || !isRequiredInvariantLoad(LI))
2904 return nullptr;
2905
2906 scop->addAssumption(INVARIANTLOAD, WrittenCtx, LI->getDebugLoc(),
2907 AS_RESTRICTION, LI->getParent());
2908 return WrittenCtx;
2909}
2910
2911static bool isAParameter(llvm::Value *maybeParam, const Function &F) {
2912 for (const llvm::Argument &Arg : F.args())
2913 if (&Arg == maybeParam)
2914 return true;
2915
2916 return false;
2917}
2918
2919bool ScopBuilder::canAlwaysBeHoisted(MemoryAccess *MA,
2920 bool StmtInvalidCtxIsEmpty,
2921 bool MAInvalidCtxIsEmpty,
2922 bool NonHoistableCtxIsEmpty) {
2923 LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
2924 const DataLayout &DL = LInst->getParent()->getModule()->getDataLayout();
2925 if (PollyAllowDereferenceOfAllFunctionParams &&
2926 isAParameter(LInst->getPointerOperand(), scop->getFunction()))
2927 return true;
2928
2929 // TODO: We can provide more information for better but more expensive
2930 // results.
2931 if (!isDereferenceableAndAlignedPointer(LInst->getPointerOperand(),
2932 LInst->getType(),
2933 LInst->getAlignment(), DL))
2934 return false;
2935
2936 // If the location might be overwritten we do not hoist it unconditionally.
2937 //
2938 // TODO: This is probably too conservative.
2939 if (!NonHoistableCtxIsEmpty)
2940 return false;
2941
2942 // If a dereferenceable load is in a statement that is modeled precisely we
2943 // can hoist it.
2944 if (StmtInvalidCtxIsEmpty && MAInvalidCtxIsEmpty)
2945 return true;
2946
2947 // Even if the statement is not modeled precisely we can hoist the load if it
2948 // does not involve any parameters that might have been specialized by the
2949 // statement domain.
2950 for (unsigned u = 0, e = MA->getNumSubscripts(); u < e; u++)
2951 if (!isa<SCEVConstant>(MA->getSubscript(u)))
2952 return false;
2953 return true;
2954}
2955
2956void ScopBuilder::addInvariantLoads(ScopStmt &Stmt,
2957 InvariantAccessesTy &InvMAs) {
2958 if (InvMAs.empty())
2959 return;
2960
2961 isl::set StmtInvalidCtx = Stmt.getInvalidContext();
2962 bool StmtInvalidCtxIsEmpty = StmtInvalidCtx.is_empty();
2963
2964 // Get the context under which the statement is executed but remove the error
2965 // context under which this statement is reached.
2966 isl::set DomainCtx = Stmt.getDomain().params();
2967 DomainCtx = DomainCtx.subtract(StmtInvalidCtx);
2968
2969 if (DomainCtx.n_basic_set() >= MaxDisjunctsInDomain) {
2970 auto *AccInst = InvMAs.front().MA->getAccessInstruction();
2971 scop->invalidate(COMPLEXITY, AccInst->getDebugLoc(), AccInst->getParent());
2972 return;
2973 }
2974
2975 // Project out all parameters that relate to loads in the statement. Otherwise
2976 // we could have cyclic dependences on the constraints under which the
2977 // hoisted loads are executed and we could not determine an order in which to
2978 // pre-load them. This happens because not only lower bounds are part of the
2979 // domain but also upper bounds.
2980 for (auto &InvMA : InvMAs) {
2981 auto *MA = InvMA.MA;
2982 Instruction *AccInst = MA->getAccessInstruction();
2983 if (SE.isSCEVable(AccInst->getType())) {
2984 SetVector<Value *> Values;
2985 for (const SCEV *Parameter : scop->parameters()) {
2986 Values.clear();
2987 findValues(Parameter, SE, Values);
2988 if (!Values.count(AccInst))
2989 continue;
2990
2991 if (isl::id ParamId = scop->getIdForParam(Parameter)) {
2992 int Dim = DomainCtx.find_dim_by_id(isl::dim::param, ParamId);
2993 if (Dim >= 0)
2994 DomainCtx = DomainCtx.eliminate(isl::dim::param, Dim, 1);
2995 }
2996 }
2997 }
2998 }
2999
3000 for (auto &InvMA : InvMAs) {
3001 auto *MA = InvMA.MA;
3002 isl::set NHCtx = InvMA.NonHoistableCtx;
3003
3004 // Check for another invariant access that accesses the same location as
3005 // MA and if found consolidate them. Otherwise create a new equivalence
3006 // class at the end of InvariantEquivClasses.
3007 LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
3008 Type *Ty = LInst->getType();
3009 const SCEV *PointerSCEV = SE.getSCEV(LInst->getPointerOperand());
3010
3011 isl::set MAInvalidCtx = MA->getInvalidContext();
3012 bool NonHoistableCtxIsEmpty = NHCtx.is_empty();
3013 bool MAInvalidCtxIsEmpty = MAInvalidCtx.is_empty();
3014
3015 isl::set MACtx;
3016 // Check if we know that this pointer can be speculatively accessed.
3017 if (canAlwaysBeHoisted(MA, StmtInvalidCtxIsEmpty, MAInvalidCtxIsEmpty,
3018 NonHoistableCtxIsEmpty)) {
3019 MACtx = isl::set::universe(DomainCtx.get_space());
3020 } else {
3021 MACtx = DomainCtx;
3022 MACtx = MACtx.subtract(MAInvalidCtx.unite(NHCtx));
3023 MACtx = MACtx.gist_params(scop->getContext());
3024 }
3025
3026 bool Consolidated = false;
3027 for (auto &IAClass : scop->invariantEquivClasses()) {
3028 if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType)
3029 continue;
3030
3031 // If the pointer and the type is equal check if the access function wrt.
3032 // to the domain is equal too. It can happen that the domain fixes
3033 // parameter values and these can be different for distinct part of the
3034 // SCoP. If this happens we cannot consolidate the loads but need to
3035 // create a new invariant load equivalence class.
3036 auto &MAs = IAClass.InvariantAccesses;
3037 if (!MAs.empty()) {
3038 auto *LastMA = MAs.front();
3039
3040 isl::set AR = MA->getAccessRelation().range();
3041 isl::set LastAR = LastMA->getAccessRelation().range();
3042 bool SameAR = AR.is_equal(LastAR);
3043
3044 if (!SameAR)
3045 continue;
3046 }
3047
3048 // Add MA to the list of accesses that are in this class.
3049 MAs.push_front(MA);
3050
3051 Consolidated = true;
3052
3053 // Unify the execution context of the class and this statement.
3054 isl::set IAClassDomainCtx = IAClass.ExecutionContext;
3055 if (IAClassDomainCtx)
3056 IAClassDomainCtx = IAClassDomainCtx.unite(MACtx).coalesce();
3057 else
3058 IAClassDomainCtx = MACtx;
3059 IAClass.ExecutionContext = IAClassDomainCtx;
3060 break;
3061 }
3062
3063 if (Consolidated)
3064 continue;
3065
3066 MACtx = MACtx.coalesce();
3067
3068 // If we did not consolidate MA, thus did not find an equivalence class
3069 // for it, we create a new one.
3070 scop->addInvariantEquivClass(
3071 InvariantEquivClassTy{PointerSCEV, MemoryAccessList{MA}, MACtx, Ty});
3072 }
3073}
3074
3075void ScopBuilder::collectCandidateReductionLoads(
3076 MemoryAccess *StoreMA, SmallVectorImpl<MemoryAccess *> &Loads) {
3077 ScopStmt *Stmt = StoreMA->getStatement();
3078
3079 auto *Store = dyn_cast<StoreInst>(StoreMA->getAccessInstruction());
3080 if (!Store)
3081 return;
3082
3083 // Skip if there is not one binary operator between the load and the store
3084 auto *BinOp = dyn_cast<BinaryOperator>(Store->getValueOperand());
3085 if (!BinOp)
3086 return;
3087
3088 // Skip if the binary operators has multiple uses
3089 if (BinOp->getNumUses() != 1)
3090 return;
3091
3092 // Skip if the opcode of the binary operator is not commutative/associative
3093 if (!BinOp->isCommutative() || !BinOp->isAssociative())
3094 return;
3095
3096 // Skip if the binary operator is outside the current SCoP
3097 if (BinOp->getParent() != Store->getParent())
3098 return;
3099
3100 // Skip if it is a multiplicative reduction and we disabled them
3101 if (DisableMultiplicativeReductions &&
3102 (BinOp->getOpcode() == Instruction::Mul ||
3103 BinOp->getOpcode() == Instruction::FMul))
3104 return;
3105
3106 // Check the binary operator operands for a candidate load
3107 auto *PossibleLoad0 = dyn_cast<LoadInst>(BinOp->getOperand(0));
3108 auto *PossibleLoad1 = dyn_cast<LoadInst>(BinOp->getOperand(1));
3109 if (!PossibleLoad0 && !PossibleLoad1)
3110 return;
3111
3112 // A load is only a candidate if it cannot escape (thus has only this use)
3113 if (PossibleLoad0 && PossibleLoad0->getNumUses() == 1)
3114 if (PossibleLoad0->getParent() == Store->getParent())
3115 Loads.push_back(&Stmt->getArrayAccessFor(PossibleLoad0));
3116 if (PossibleLoad1 && PossibleLoad1->getNumUses() == 1)
3117 if (PossibleLoad1->getParent() == Store->getParent())
3118 Loads.push_back(&Stmt->getArrayAccessFor(PossibleLoad1));
3119}
3120
3121/// Find the canonical scop array info object for a set of invariant load
3122/// hoisted loads. The canonical array is the one that corresponds to the
3123/// first load in the list of accesses which is used as base pointer of a
3124/// scop array.
3125static const ScopArrayInfo *findCanonicalArray(Scop &S,
3126 MemoryAccessList &Accesses) {
3127 for (MemoryAccess *Access : Accesses) {
3128 const ScopArrayInfo *CanonicalArray = S.getScopArrayInfoOrNull(
3129 Access->getAccessInstruction(), MemoryKind::Array);
3130 if (CanonicalArray)
3131 return CanonicalArray;
3132 }
3133 return nullptr;
3134}
3135
3136/// Check if @p Array severs as base array in an invariant load.
3137static bool isUsedForIndirectHoistedLoad(Scop &S, const ScopArrayInfo *Array) {
3138 for (InvariantEquivClassTy &EqClass2 : S.getInvariantAccesses())
3139 for (MemoryAccess *Access2 : EqClass2.InvariantAccesses)
3140 if (Access2->getScopArrayInfo() == Array)
3141 return true;
3142 return false;
3143}
3144
3145/// Replace the base pointer arrays in all memory accesses referencing @p Old,
3146/// with a reference to @p New.
3147static void replaceBasePtrArrays(Scop &S, const ScopArrayInfo *Old,
3148 const ScopArrayInfo *New) {
3149 for (ScopStmt &Stmt : S)
3150 for (MemoryAccess *Access : Stmt) {
3151 if (Access->getLatestScopArrayInfo() != Old)
3152 continue;
3153
3154 isl::id Id = New->getBasePtrId();
3155 isl::map Map = Access->getAccessRelation();
3156 Map = Map.set_tuple_id(isl::dim::out, Id);
3157 Access->setAccessRelation(Map);
3158 }
3159}
3160
3161void ScopBuilder::canonicalizeDynamicBasePtrs() {
3162 for (InvariantEquivClassTy &EqClass : scop->InvariantEquivClasses) {
3163 MemoryAccessList &BasePtrAccesses = EqClass.InvariantAccesses;
3164
3165 const ScopArrayInfo *CanonicalBasePtrSAI =
3166 findCanonicalArray(*scop, BasePtrAccesses);
3167
3168 if (!CanonicalBasePtrSAI)
3169 continue;
3170
3171 for (MemoryAccess *BasePtrAccess : BasePtrAccesses) {
3172 const ScopArrayInfo *BasePtrSAI = scop->getScopArrayInfoOrNull(
3173 BasePtrAccess->getAccessInstruction(), MemoryKind::Array);
3174 if (!BasePtrSAI || BasePtrSAI == CanonicalBasePtrSAI ||
3175 !BasePtrSAI->isCompatibleWith(CanonicalBasePtrSAI))
3176 continue;
3177
3178 // we currently do not canonicalize arrays where some accesses are
3179 // hoisted as invariant loads. If we would, we need to update the access
3180 // function of the invariant loads as well. However, as this is not a
3181 // very common situation, we leave this for now to avoid further
3182 // complexity increases.
3183 if (isUsedForIndirectHoistedLoad(*scop, BasePtrSAI))
3184 continue;
3185
3186 replaceBasePtrArrays(*scop, BasePtrSAI, CanonicalBasePtrSAI);
3187 }
3188 }
3189}
3190
3191void ScopBuilder::buildAccessRelations(ScopStmt &Stmt) {
3192 for (MemoryAccess *Access : Stmt.MemAccs) {
3193 Type *ElementType = Access->getElementType();
3194
3195 MemoryKind Ty;
3196 if (Access->isPHIKind())
3197 Ty = MemoryKind::PHI;
3198 else if (Access->isExitPHIKind())
3199 Ty = MemoryKind::ExitPHI;
3200 else if (Access->isValueKind())
3201 Ty = MemoryKind::Value;
3202 else
3203 Ty = MemoryKind::Array;
3204
3205 auto *SAI = scop->getOrCreateScopArrayInfo(Access->getOriginalBaseAddr(),
3206 ElementType, Access->Sizes, Ty);
3207 Access->buildAccessRelation(SAI);
3208 scop->addAccessData(Access);
3209 }
3210}
3211
3212/// Add the minimal/maximal access in @p Set to @p User.
3213///
3214/// @return True if more accesses should be added, false if we reached the
3215/// maximal number of run-time checks to be generated.
3216static bool buildMinMaxAccess(isl::set Set,
3217 Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S) {
3218 isl::pw_multi_aff MinPMA, MaxPMA;
3219 isl::pw_aff LastDimAff;
3220 isl::aff OneAff;
3221 unsigned Pos;
3222
3223 Set = Set.remove_divs();
3224 polly::simplify(Set);
3225
3226 if (Set.n_basic_set() > RunTimeChecksMaxAccessDisjuncts)
3227 Set = Set.simple_hull();
3228
3229 // Restrict the number of parameters involved in the access as the lexmin/
3230 // lexmax computation will take too long if this number is high.
3231 //
3232 // Experiments with a simple test case using an i7 4800MQ:
3233 //
3234 // #Parameters involved | Time (in sec)
3235 // 6 | 0.01
3236 // 7 | 0.04
3237 // 8 | 0.12
3238 // 9 | 0.40
3239 // 10 | 1.54
3240 // 11 | 6.78
3241 // 12 | 30.38
3242 //
3243 if (isl_set_n_param(Set.get()) > RunTimeChecksMaxParameters) {
3244 unsigned InvolvedParams = 0;
3245 for (unsigned u = 0, e = isl_set_n_param(Set.get()); u < e; u++)
3246 if (Set.involves_dims(isl::dim::param, u, 1))
3247 InvolvedParams++;
3248
3249 if (InvolvedParams > RunTimeChecksMaxParameters)
3250 return false;
3251 }
3252
3253 MinPMA = Set.lexmin_pw_multi_aff();
3254 MaxPMA = Set.lexmax_pw_multi_aff();
3255
3256 MinPMA = MinPMA.coalesce();
3257 MaxPMA = MaxPMA.coalesce();
3258
3259 // Adjust the last dimension of the maximal access by one as we want to
3260 // enclose the accessed memory region by MinPMA and MaxPMA. The pointer
3261 // we test during code generation might now point after the end of the
3262 // allocated array but we will never dereference it anyway.
3263 assert((!MaxPMA || MaxPMA.dim(isl::dim::out)) &&(((!MaxPMA || MaxPMA.dim(isl::dim::out)) && "Assumed at least one output dimension"
) ? static_cast<void> (0) : __assert_fail ("(!MaxPMA || MaxPMA.dim(isl::dim::out)) && \"Assumed at least one output dimension\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 3264, __PRETTY_FUNCTION__))
3264 "Assumed at least one output dimension")(((!MaxPMA || MaxPMA.dim(isl::dim::out)) && "Assumed at least one output dimension"
) ? static_cast<void> (0) : __assert_fail ("(!MaxPMA || MaxPMA.dim(isl::dim::out)) && \"Assumed at least one output dimension\""
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 3264, __PRETTY_FUNCTION__))
;
3265
3266 Pos = MaxPMA.dim(isl::dim::out) - 1;
3267 LastDimAff = MaxPMA.get_pw_aff(Pos);
3268 OneAff = isl::aff(isl::local_space(LastDimAff.get_domain_space()));
3269 OneAff = OneAff.add_constant_si(1);
3270 LastDimAff = LastDimAff.add(OneAff);
3271 MaxPMA = MaxPMA.set_pw_aff(Pos, LastDimAff);
3272
3273 if (!MinPMA || !MaxPMA)
3274 return false;
3275
3276 MinMaxAccesses.push_back(std::make_pair(MinPMA, MaxPMA));
3277
3278 return true;
3279}
3280
3281/// Wrapper function to calculate minimal/maximal accesses to each array.
3282bool ScopBuilder::calculateMinMaxAccess(AliasGroupTy AliasGroup,
3283 Scop::MinMaxVectorTy &MinMaxAccesses) {
3284 MinMaxAccesses.reserve(AliasGroup.size());
3285
3286 isl::union_set Domains = scop->getDomains();
3287 isl::union_map Accesses = isl::union_map::empty(scop->getParamSpace());
3288
3289 for (MemoryAccess *MA : AliasGroup)
3290 Accesses = Accesses.add_map(MA->getAccessRelation());
3291
3292 Accesses = Accesses.intersect_domain(Domains);
3293 isl::union_set Locations = Accesses.range();
3294
3295 bool LimitReached = false;
3296 for (isl::set Set : Locations.get_set_list()) {
3297 LimitReached |= !buildMinMaxAccess(Set, MinMaxAccesses, *scop);
3298 if (LimitReached)
3299 break;
3300 }
3301
3302 return !LimitReached;
3303}
3304
3305static isl::set getAccessDomain(MemoryAccess *MA) {
3306 isl::set Domain = MA->getStatement()->getDomain();
3307 Domain = Domain.project_out(isl::dim::set, 0, Domain.n_dim());
3308 return Domain.reset_tuple_id();
3309}
3310
3311bool ScopBuilder::buildAliasChecks() {
3312 if (!PollyUseRuntimeAliasChecks)
3313 return true;
3314
3315 if (buildAliasGroups()) {
3316 // Aliasing assumptions do not go through addAssumption but we still want to
3317 // collect statistics so we do it here explicitly.
3318 if (scop->getAliasGroups().size())
3319 Scop::incrementNumberOfAliasingAssumptions(1);
3320 return true;
3321 }
3322
3323 // If a problem occurs while building the alias groups we need to delete
3324 // this SCoP and pretend it wasn't valid in the first place. To this end
3325 // we make the assumed context infeasible.
3326 scop->invalidate(ALIASING, DebugLoc());
3327
3328 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for "
<< scop->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)
3329 dbgs() << "\n\nNOTE: Run time checks for " << scop->getNameStr()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for "
<< scop->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)
3330 << " 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 "
<< scop->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)
3331 "is too high. The SCoP will be "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for "
<< scop->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)
3332 "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 "
<< scop->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)
3333 "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 "
<< scop->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)
3334 "compile time might increase exponentially.\n\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for "
<< scop->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)
;
3335 return false;
3336}
3337
3338std::tuple<ScopBuilder::AliasGroupVectorTy, DenseSet<const ScopArrayInfo *>>
3339ScopBuilder::buildAliasGroupsForAccesses() {
3340 AliasSetTracker AST(AA);
3341
3342 DenseMap<Value *, MemoryAccess *> PtrToAcc;
3343 DenseSet<const ScopArrayInfo *> HasWriteAccess;
3344 for (ScopStmt &Stmt : *scop) {
3345
3346 isl::set StmtDomain = Stmt.getDomain();
3347 bool StmtDomainEmpty = StmtDomain.is_empty();
3348
3349 // Statements with an empty domain will never be executed.
3350 if (StmtDomainEmpty)
3351 continue;
3352
3353 for (MemoryAccess *MA : Stmt) {
3354 if (MA->isScalarKind())
3355 continue;
3356 if (!MA->isRead())
3357 HasWriteAccess.insert(MA->getScopArrayInfo());
3358 MemAccInst Acc(MA->getAccessInstruction());
3359 if (MA->isRead() && isa<MemTransferInst>(Acc))
3360 PtrToAcc[cast<MemTransferInst>(Acc)->getRawSource()] = MA;
3361 else
3362 PtrToAcc[Acc.getPointerOperand()] = MA;
3363 AST.add(Acc);
3364 }
3365 }
3366
3367 AliasGroupVectorTy AliasGroups;
3368 for (AliasSet &AS : AST) {
3369 if (AS.isMustAlias() || AS.isForwardingAliasSet())
3370 continue;
3371 AliasGroupTy AG;
3372 for (auto &PR : AS)
3373 AG.push_back(PtrToAcc[PR.getValue()]);
3374 if (AG.size() < 2)
3375 continue;
3376 AliasGroups.push_back(std::move(AG));
3377 }
3378
3379 return std::make_tuple(AliasGroups, HasWriteAccess);
3380}
3381
3382bool ScopBuilder::buildAliasGroups() {
3383 // To create sound alias checks we perform the following steps:
3384 // o) We partition each group into read only and non read only accesses.
3385 // o) For each group with more than one base pointer we then compute minimal
3386 // and maximal accesses to each array of a group in read only and non
3387 // read only partitions separately.
3388 AliasGroupVectorTy AliasGroups;
3389 DenseSet<const ScopArrayInfo *> HasWriteAccess;
3390
3391 std::tie(AliasGroups, HasWriteAccess) = buildAliasGroupsForAccesses();
3392
3393 splitAliasGroupsByDomain(AliasGroups);
3394
3395 for (AliasGroupTy &AG : AliasGroups) {
3396 if (!scop->hasFeasibleRuntimeContext())
3397 return false;
3398
3399 {
3400 IslMaxOperationsGuard MaxOpGuard(scop->getIslCtx().get(), OptComputeOut);
3401 bool Valid = buildAliasGroup(AG, HasWriteAccess);
3402 if (!Valid)
3403 return false;
3404 }
3405 if (isl_ctx_last_error(scop->getIslCtx().get()) == isl_error_quota) {
3406 scop->invalidate(COMPLEXITY, DebugLoc());
3407 return false;
3408 }
3409 }
3410
3411 return true;
3412}
3413
3414bool ScopBuilder::buildAliasGroup(
3415 AliasGroupTy &AliasGroup, DenseSet<const ScopArrayInfo *> HasWriteAccess) {
3416 AliasGroupTy ReadOnlyAccesses;
3417 AliasGroupTy ReadWriteAccesses;
3418 SmallPtrSet<const ScopArrayInfo *, 4> ReadWriteArrays;
3419 SmallPtrSet<const ScopArrayInfo *, 4> ReadOnlyArrays;
3420
3421 if (AliasGroup.size() < 2)
3422 return true;
3423
3424 for (MemoryAccess *Access : AliasGroup) {
3425 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE"polly-scops", "PossibleAlias",
3426 Access->getAccessInstruction())
3427 << "Possibly aliasing pointer, use restrict keyword.");
3428 const ScopArrayInfo *Array = Access->getScopArrayInfo();
3429 if (HasWriteAccess.count(Array)) {
3430 ReadWriteArrays.insert(Array);
3431 ReadWriteAccesses.push_back(Access);
3432 } else {
3433 ReadOnlyArrays.insert(Array);
3434 ReadOnlyAccesses.push_back(Access);
3435 }
3436 }
3437
3438 // If there are no read-only pointers, and less than two read-write pointers,
3439 // no alias check is needed.
3440 if (ReadOnlyAccesses.empty() && ReadWriteArrays.size() <= 1)
3441 return true;
3442
3443 // If there is no read-write pointer, no alias check is needed.
3444 if (ReadWriteArrays.empty())
3445 return true;
3446
3447 // For non-affine accesses, no alias check can be generated as we cannot
3448 // compute a sufficiently tight lower and upper bound: bail out.
3449 for (MemoryAccess *MA : AliasGroup) {
3450 if (!MA->isAffine()) {
3451 scop->invalidate(ALIASING, MA->getAccessInstruction()->getDebugLoc(),
3452 MA->getAccessInstruction()->getParent());
3453 return false;
3454 }
3455 }
3456
3457 // Ensure that for all memory accesses for which we generate alias checks,
3458 // their base pointers are available.
3459 for (MemoryAccess *MA : AliasGroup) {
3460 if (MemoryAccess *BasePtrMA = scop->lookupBasePtrAccess(MA))
3461 scop->addRequiredInvariantLoad(
3462 cast<LoadInst>(BasePtrMA->getAccessInstruction()));
3463 }
3464
3465 // scop->getAliasGroups().emplace_back();
3466 // Scop::MinMaxVectorPairTy &pair = scop->getAliasGroups().back();
3467 Scop::MinMaxVectorTy MinMaxAccessesReadWrite;
3468 Scop::MinMaxVectorTy MinMaxAccessesReadOnly;
3469
3470 bool Valid;
3471
3472 Valid = calculateMinMaxAccess(ReadWriteAccesses, MinMaxAccessesReadWrite);
3473
3474 if (!Valid)
3475 return false;
3476
3477 // Bail out if the number of values we need to compare is too large.
3478 // This is important as the number of comparisons grows quadratically with
3479 // the number of values we need to compare.
3480 if (MinMaxAccessesReadWrite.size() + ReadOnlyArrays.size() >
3481 RunTimeChecksMaxArraysPerGroup)
3482 return false;
3483
3484 Valid = calculateMinMaxAccess(ReadOnlyAccesses, MinMaxAccessesReadOnly);
3485
3486 scop->addAliasGroup(MinMaxAccessesReadWrite, MinMaxAccessesReadOnly);
3487 if (!Valid)
3488 return false;
3489
3490 return true;
3491}
3492
3493void ScopBuilder::splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups) {
3494 for (unsigned u = 0; u < AliasGroups.size(); u++) {
3495 AliasGroupTy NewAG;
3496 AliasGroupTy &AG = AliasGroups[u];
3497 AliasGroupTy::iterator AGI = AG.begin();
3498 isl::set AGDomain = getAccessDomain(*AGI);
3499 while (AGI != AG.end()) {
3500 MemoryAccess *MA = *AGI;
3501 isl::set MADomain = getAccessDomain(MA);
3502 if (AGDomain.is_disjoint(MADomain)) {
3503 NewAG.push_back(MA);
3504 AGI = AG.erase(AGI);
3505 } else {
3506 AGDomain = AGDomain.unite(MADomain);
3507 AGI++;
3508 }
3509 }
3510 if (NewAG.size() > 1)
3511 AliasGroups.push_back(std::move(NewAG));
3512 }
3513}
3514
3515#ifndef NDEBUG
3516static void verifyUse(Scop *S, Use &Op, LoopInfo &LI) {
3517 auto PhysUse = VirtualUse::create(S, Op, &LI, false);
3518 auto VirtUse = VirtualUse::create(S, Op, &LI, true);
3519 assert(PhysUse.getKind() == VirtUse.getKind())((PhysUse.getKind() == VirtUse.getKind()) ? static_cast<void
> (0) : __assert_fail ("PhysUse.getKind() == VirtUse.getKind()"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 3519, __PRETTY_FUNCTION__))
;
3520}
3521
3522/// Check the consistency of every statement's MemoryAccesses.
3523///
3524/// The check is carried out by expecting the "physical" kind of use (derived
3525/// from the BasicBlocks instructions resides in) to be same as the "virtual"
3526/// kind of use (derived from a statement's MemoryAccess).
3527///
3528/// The "physical" uses are taken by ensureValueRead to determine whether to
3529/// create MemoryAccesses. When done, the kind of scalar access should be the
3530/// same no matter which way it was derived.
3531///
3532/// The MemoryAccesses might be changed by later SCoP-modifying passes and hence
3533/// can intentionally influence on the kind of uses (not corresponding to the
3534/// "physical" anymore, hence called "virtual"). The CodeGenerator therefore has
3535/// to pick up the virtual uses. But here in the code generator, this has not
3536/// happened yet, such that virtual and physical uses are equivalent.
3537static void verifyUses(Scop *S, LoopInfo &LI, DominatorTree &DT) {
3538 for (auto *BB : S->getRegion().blocks()) {
3539 for (auto &Inst : *BB) {
3540 auto *Stmt = S->getStmtFor(&Inst);
3541 if (!Stmt)
3542 continue;
3543
3544 if (isIgnoredIntrinsic(&Inst))
3545 continue;
3546
3547 // Branch conditions are encoded in the statement domains.
3548 if (Inst.isTerminator() && Stmt->isBlockStmt())
3549 continue;
3550
3551 // Verify all uses.
3552 for (auto &Op : Inst.operands())
3553 verifyUse(S, Op, LI);
3554
3555 // Stores do not produce values used by other statements.
3556 if (isa<StoreInst>(Inst))
3557 continue;
3558
3559 // For every value defined in the block, also check that a use of that
3560 // value in the same statement would not be an inter-statement use. It can
3561 // still be synthesizable or load-hoisted, but these kind of instructions
3562 // are not directly copied in code-generation.
3563 auto VirtDef =
3564 VirtualUse::create(S, Stmt, Stmt->getSurroundingLoop(), &Inst, true);
3565 assert(VirtDef.getKind() == VirtualUse::Synthesizable ||((VirtDef.getKind() == VirtualUse::Synthesizable || VirtDef.getKind
() == VirtualUse::Intra || VirtDef.getKind() == VirtualUse::Hoisted
) ? static_cast<void> (0) : __assert_fail ("VirtDef.getKind() == VirtualUse::Synthesizable || VirtDef.getKind() == VirtualUse::Intra || VirtDef.getKind() == VirtualUse::Hoisted"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 3567, __PRETTY_FUNCTION__))
3566 VirtDef.getKind() == VirtualUse::Intra ||((VirtDef.getKind() == VirtualUse::Synthesizable || VirtDef.getKind
() == VirtualUse::Intra || VirtDef.getKind() == VirtualUse::Hoisted
) ? static_cast<void> (0) : __assert_fail ("VirtDef.getKind() == VirtualUse::Synthesizable || VirtDef.getKind() == VirtualUse::Intra || VirtDef.getKind() == VirtualUse::Hoisted"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 3567, __PRETTY_FUNCTION__))
3567 VirtDef.getKind() == VirtualUse::Hoisted)((VirtDef.getKind() == VirtualUse::Synthesizable || VirtDef.getKind
() == VirtualUse::Intra || VirtDef.getKind() == VirtualUse::Hoisted
) ? static_cast<void> (0) : __assert_fail ("VirtDef.getKind() == VirtualUse::Synthesizable || VirtDef.getKind() == VirtualUse::Intra || VirtDef.getKind() == VirtualUse::Hoisted"
, "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 3567, __PRETTY_FUNCTION__))
;
3568 }
3569 }
3570
3571 if (S->hasSingleExitEdge())
3572 return;
3573
3574 // PHINodes in the SCoP region's exit block are also uses to be checked.
3575 if (!S->getRegion().isTopLevelRegion()) {
3576 for (auto &Inst : *S->getRegion().getExit()) {
3577 if (!isa<PHINode>(Inst))
3578 break;
3579
3580 for (auto &Op : Inst.operands())
3581 verifyUse(S, Op, LI);
3582 }
3583 }
3584}
3585#endif
3586
3587void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
3588 scop.reset(new Scop(R, SE, LI, DT, *SD.getDetectionContext(&R), ORE));
3589
3590 buildStmts(R);
3591
3592 // Create all invariant load instructions first. These are categorized as
3593 // 'synthesizable', therefore are not part of any ScopStmt but need to be
3594 // created somewhere.
3595 const InvariantLoadsSetTy &RIL = scop->getRequiredInvariantLoads();
3596 for (BasicBlock *BB : scop->getRegion().blocks()) {
3597 if (isErrorBlock(*BB, scop->getRegion(), LI, DT))
2
Assuming the condition is false
3
Taking false branch
3598 continue;
3599
3600 for (Instruction &Inst : *BB) {
3601 LoadInst *Load = dyn_cast<LoadInst>(&Inst);
4
Assuming the object is a 'LoadInst'
3602 if (!Load
4.1
'Load' is non-null
)
5
Taking false branch
3603 continue;
3604
3605 if (!RIL.count(Load))
6
Assuming the condition is false
7
Taking false branch
3606 continue;
3607
3608 // Invariant loads require a MemoryAccess to be created in some statement.
3609 // It is not important to which statement the MemoryAccess is added
3610 // because it will later be removed from the ScopStmt again. We chose the
3611 // first statement of the basic block the LoadInst is in.
3612 ArrayRef<ScopStmt *> List = scop->getStmtListFor(BB);
3613 assert(!List.empty())((!List.empty()) ? static_cast<void> (0) : __assert_fail
("!List.empty()", "/build/llvm-toolchain-snapshot-10~svn374877/tools/polly/lib/Analysis/ScopBuilder.cpp"
, 3613, __PRETTY_FUNCTION__))
;
8
Assuming the condition is true
9
'?' condition is true
3614 ScopStmt *RILStmt = List.front();
3615 buildMemoryAccess(Load, RILStmt);
10
Calling 'ScopBuilder::buildMemoryAccess'
3616 }
3617 }
3618 buildAccessFunctions();
3619
3620 // In case the region does not have an exiting block we will later (during
3621 // code generation) split the exit block. This will move potential PHI nodes
3622 // from the current exit block into the new region exiting block. Hence, PHI
3623 // nodes that are at this point not part of the region will be.
3624 // To handle these PHI nodes later we will now model their operands as scalar
3625 // accesses. Note that we do not model anything in the exit block if we have
3626 // an exiting block in the region, as there will not be any splitting later.
3627 if (!R.isTopLevelRegion() && !scop->hasSingleExitEdge()) {
3628 for (Instruction &Inst : *R.getExit()) {
3629 PHINode *PHI = dyn_cast<PHINode>(&Inst);
3630 if (!PHI)
3631 break;
3632
3633 buildPHIAccesses(nullptr, PHI, nullptr, true);
3634 }
3635 }
3636
3637 // Create memory accesses for global reads since all arrays are now known.
3638 auto *AF = SE.getConstant(IntegerType::getInt64Ty(SE.getContext()), 0);
3639 for (auto GlobalReadPair : GlobalReads) {
3640 ScopStmt *GlobalReadStmt = GlobalReadPair.first;
3641 Instruction *GlobalRead = GlobalReadPair.second;
3642 for (auto *BP : ArrayBasePointers)
3643 addArrayAccess(GlobalReadStmt, MemAccInst(GlobalRead), MemoryAccess::READ,
3644 BP, BP->getType(), false, {AF}, {nullptr}, GlobalRead);
3645 }
3646
3647 buildInvariantEquivalenceClasses();
3648
3649 /// A map from basic blocks to their invalid domains.
3650 DenseMap<BasicBlock *, isl::set> InvalidDomainMap;
3651
3652 if (!buildDomains(&R, InvalidDomainMap)) {
3653 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "Bailing-out because buildDomains encountered problems\n"
; } } while (false)
3654 dbgs() << "Bailing-out because buildDomains encountered problems\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "Bailing-out because buildDomains encountered problems\n"
; } } while (false)
;
3655 return;
3656 }
3657
3658 addUserAssumptions(AC, InvalidDomainMap);
3659
3660 // Initialize the invalid domain.
3661 for (ScopStmt &Stmt : scop->Stmts)
3662 if (Stmt.isBlockStmt())
3663 Stmt.setInvalidDomain(InvalidDomainMap[Stmt.getEntryBlock()]);
3664 else
3665 Stmt.setInvalidDomain(InvalidDomainMap[getRegionNodeBasicBlock(
3666 Stmt.getRegion()->getNode())]);
3667
3668 // Remove empty statements.
3669 // Exit early in case there are no executable statements left in this scop.
3670 scop->removeStmtNotInDomainMap();
3671 scop->simplifySCoP(false);
3672 if (scop->isEmpty()) {
3673 LLVM_DEBUG(dbgs() << "Bailing-out because SCoP is empty\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "Bailing-out because SCoP is empty\n"
; } } while (false)
;
3674 return;
3675 }
3676
3677 // The ScopStmts now have enough information to initialize themselves.
3678 for (ScopStmt &Stmt : *scop) {
3679 collectSurroundingLoops(Stmt);
3680
3681 buildDomain(Stmt);
3682 buildAccessRelations(Stmt);
3683
3684 if (DetectReductions)
3685 checkForReductions(Stmt);
3686 }
3687
3688 // Check early for a feasible runtime context.
3689 if (!scop->hasFeasibleRuntimeContext()) {
3690 LLVM_DEBUG(dbgs() << "Bailing-out because of unfeasible context (early)\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "Bailing-out because of unfeasible context (early)\n"
; } } while (false)
;
3691 return;
3692 }
3693
3694 // Check early for profitability. Afterwards it cannot change anymore,
3695 // only the runtime context could become infeasible.
3696 if (!scop->isProfitable(UnprofitableScalarAccs)) {
3697 scop->invalidate(PROFITABLE, DebugLoc());
3698 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "Bailing-out because SCoP is not considered profitable\n"
; } } while (false)
3699 dbgs() << "Bailing-out because SCoP is not considered profitable\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "Bailing-out because SCoP is not considered profitable\n"
; } } while (false)
;
3700 return;
3701 }
3702
3703 buildSchedule();
3704
3705 finalizeAccesses();
3706
3707 scop->realignParams();
3708 addUserContext();
3709
3710 // After the context was fully constructed, thus all our knowledge about
3711 // the parameters is in there, we add all recorded assumptions to the
3712 // assumed/invalid context.
3713 addRecordedAssumptions();
3714
3715 scop->simplifyContexts();
3716 if (!buildAliasChecks()) {
3717 LLVM_DEBUG(dbgs() << "Bailing-out because could not build alias checks\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "Bailing-out because could not build alias checks\n"
; } } while (false)
;
3718 return;
3719 }
3720
3721 hoistInvariantLoads();
3722 canonicalizeDynamicBasePtrs();
3723 verifyInvariantLoads();
3724 scop->simplifySCoP(true);
3725
3726 // Check late for a feasible runtime context because profitability did not
3727 // change.
3728 if (!scop->hasFeasibleRuntimeContext()) {
3729 LLVM_DEBUG(dbgs() << "Bailing-out because of unfeasible context (late)\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "Bailing-out because of unfeasible context (late)\n"
; } } while (false)
;
3730 return;
3731 }
3732
3733#ifndef NDEBUG
3734 verifyUses(scop.get(), LI, DT);
3735#endif
3736}
3737
3738ScopBuilder::ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
3739 const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
3740 ScopDetection &SD, ScalarEvolution &SE,
3741 OptimizationRemarkEmitter &ORE)
3742 : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE), ORE(ORE) {
3743 DebugLoc Beg, End;
3744 auto P = getBBPairForRegion(R);
3745 getDebugLocations(P, Beg, End);
3746
3747 std::string Msg = "SCoP begins here.";
3748 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE"polly-scops", "ScopEntry", Beg, P.first)
3749 << Msg);
3750
3751 buildScop(*R, AC);
1
Calling 'ScopBuilder::buildScop'
3752
3753 LLVM_DEBUG(dbgs() << *scop)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << *scop; } } while (false)
;
3754
3755 if (!scop->hasFeasibleRuntimeContext()) {
3756 InfeasibleScops++;
3757 Msg = "SCoP ends here but was dismissed.";
3758 LLVM_DEBUG(dbgs() << "SCoP detected but dismissed\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("polly-scops")) { dbgs() << "SCoP detected but dismissed\n"
; } } while (false)
;
3759 scop.reset();
3760 } else {
3761 Msg = "SCoP ends here.";
3762 ++ScopFound;
3763 if (scop->getMaxLoopDepth() > 0)
3764 ++RichScopFound;
3765 }
3766
3767 if (R->isTopLevelRegion())
3768 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE"polly-scops", "ScopEnd", End, P.first)
3769 << Msg);
3770 else
3771 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE"polly-scops", "ScopEnd", End, P.second)
3772 << Msg);
3773}