Bug Summary

File:polly/lib/Analysis/ScopBuilder.cpp
Warning:line 453, column 9
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

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