File: | polly/lib/Analysis/ScopInfo.cpp |
Location: | line 2422, column 17 |
Description: | Called C++ object pointer is null |
1 | //===--------- ScopInfo.cpp - Create Scops from LLVM IR ------------------===// | |||
2 | // | |||
3 | // The LLVM Compiler Infrastructure | |||
4 | // | |||
5 | // This file is distributed under the University of Illinois Open Source | |||
6 | // License. See LICENSE.TXT for details. | |||
7 | // | |||
8 | //===----------------------------------------------------------------------===// | |||
9 | // | |||
10 | // Create a polyhedral description for a static control flow region. | |||
11 | // | |||
12 | // The pass creates a polyhedral description of the Scops detected by the Scop | |||
13 | // detection derived from their LLVM-IR code. | |||
14 | // | |||
15 | // This representation is shared among several tools in the polyhedral | |||
16 | // community, which are e.g. Cloog, Pluto, Loopo, Graphite. | |||
17 | // | |||
18 | //===----------------------------------------------------------------------===// | |||
19 | ||||
20 | #include "polly/ScopInfo.h" | |||
21 | #include "polly/LinkAllPasses.h" | |||
22 | #include "polly/Options.h" | |||
23 | #include "polly/Support/GICHelper.h" | |||
24 | #include "polly/Support/SCEVValidator.h" | |||
25 | #include "polly/Support/ScopHelper.h" | |||
26 | #include "llvm/ADT/DepthFirstIterator.h" | |||
27 | #include "llvm/ADT/MapVector.h" | |||
28 | #include "llvm/ADT/PostOrderIterator.h" | |||
29 | #include "llvm/ADT/STLExtras.h" | |||
30 | #include "llvm/ADT/SetVector.h" | |||
31 | #include "llvm/ADT/Statistic.h" | |||
32 | #include "llvm/ADT/StringExtras.h" | |||
33 | #include "llvm/Analysis/AliasAnalysis.h" | |||
34 | #include "llvm/Analysis/AssumptionCache.h" | |||
35 | #include "llvm/Analysis/LoopInfo.h" | |||
36 | #include "llvm/Analysis/LoopIterator.h" | |||
37 | #include "llvm/Analysis/RegionIterator.h" | |||
38 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" | |||
39 | #include "llvm/IR/DiagnosticInfo.h" | |||
40 | #include "llvm/Support/Debug.h" | |||
41 | #include "isl/aff.h" | |||
42 | #include "isl/constraint.h" | |||
43 | #include "isl/local_space.h" | |||
44 | #include "isl/map.h" | |||
45 | #include "isl/options.h" | |||
46 | #include "isl/printer.h" | |||
47 | #include "isl/schedule.h" | |||
48 | #include "isl/schedule_node.h" | |||
49 | #include "isl/set.h" | |||
50 | #include "isl/union_map.h" | |||
51 | #include "isl/union_set.h" | |||
52 | #include "isl/val.h" | |||
53 | #include <sstream> | |||
54 | #include <string> | |||
55 | #include <vector> | |||
56 | ||||
57 | using namespace llvm; | |||
58 | using namespace polly; | |||
59 | ||||
60 | #define DEBUG_TYPE"polly-scops" "polly-scops" | |||
61 | ||||
62 | STATISTIC(ScopFound, "Number of valid Scops")static llvm::Statistic ScopFound = { "polly-scops", "Number of valid Scops" , 0, 0 }; | |||
63 | STATISTIC(RichScopFound, "Number of Scops containing a loop")static llvm::Statistic RichScopFound = { "polly-scops", "Number of Scops containing a loop" , 0, 0 }; | |||
64 | ||||
65 | // The maximal number of basic sets we allow during domain construction to | |||
66 | // be created. More complex scops will result in very high compile time and | |||
67 | // are also unlikely to result in good code | |||
68 | static int const MaxConjunctsInDomain = 20; | |||
69 | ||||
70 | static cl::opt<bool> ModelReadOnlyScalars( | |||
71 | "polly-analyze-read-only-scalars", | |||
72 | cl::desc("Model read-only scalar values in the scop description"), | |||
73 | cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory)); | |||
74 | ||||
75 | // Multiplicative reductions can be disabled separately as these kind of | |||
76 | // operations can overflow easily. Additive reductions and bit operations | |||
77 | // are in contrast pretty stable. | |||
78 | static cl::opt<bool> DisableMultiplicativeReductions( | |||
79 | "polly-disable-multiplicative-reductions", | |||
80 | cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore, | |||
81 | cl::init(false), cl::cat(PollyCategory)); | |||
82 | ||||
83 | static cl::opt<unsigned> RunTimeChecksMaxParameters( | |||
84 | "polly-rtc-max-parameters", | |||
85 | cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden, | |||
86 | cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory)); | |||
87 | ||||
88 | static cl::opt<unsigned> RunTimeChecksMaxArraysPerGroup( | |||
89 | "polly-rtc-max-arrays-per-group", | |||
90 | cl::desc("The maximal number of arrays to compare in each alias group."), | |||
91 | cl::Hidden, cl::ZeroOrMore, cl::init(20), cl::cat(PollyCategory)); | |||
92 | static cl::opt<std::string> UserContextStr( | |||
93 | "polly-context", cl::value_desc("isl parameter set"), | |||
94 | cl::desc("Provide additional constraints on the context parameters"), | |||
95 | cl::init(""), cl::cat(PollyCategory)); | |||
96 | ||||
97 | static cl::opt<bool> DetectReductions("polly-detect-reductions", | |||
98 | cl::desc("Detect and exploit reductions"), | |||
99 | cl::Hidden, cl::ZeroOrMore, | |||
100 | cl::init(true), cl::cat(PollyCategory)); | |||
101 | ||||
102 | static cl::opt<int> MaxDisjunctsAssumed( | |||
103 | "polly-max-disjuncts-assumed", | |||
104 | cl::desc("The maximal number of disjuncts we allow in the assumption " | |||
105 | "context (this bounds compile time)"), | |||
106 | cl::Hidden, cl::ZeroOrMore, cl::init(150), cl::cat(PollyCategory)); | |||
107 | ||||
108 | static cl::opt<bool> IgnoreIntegerWrapping( | |||
109 | "polly-ignore-integer-wrapping", | |||
110 | cl::desc("Do not build run-time checks to proof absence of integer " | |||
111 | "wrapping"), | |||
112 | cl::Hidden, cl::ZeroOrMore, cl::init(false), cl::cat(PollyCategory)); | |||
113 | ||||
114 | //===----------------------------------------------------------------------===// | |||
115 | ||||
116 | // Create a sequence of two schedules. Either argument may be null and is | |||
117 | // interpreted as the empty schedule. Can also return null if both schedules are | |||
118 | // empty. | |||
119 | static __isl_give isl_schedule * | |||
120 | combineInSequence(__isl_take isl_schedule *Prev, | |||
121 | __isl_take isl_schedule *Succ) { | |||
122 | if (!Prev) | |||
123 | return Succ; | |||
124 | if (!Succ) | |||
125 | return Prev; | |||
126 | ||||
127 | return isl_schedule_sequence(Prev, Succ); | |||
128 | } | |||
129 | ||||
130 | static __isl_give isl_set *addRangeBoundsToSet(__isl_take isl_set *S, | |||
131 | const ConstantRange &Range, | |||
132 | int dim, | |||
133 | enum isl_dim_type type) { | |||
134 | isl_val *V; | |||
135 | isl_ctx *ctx = isl_set_get_ctx(S); | |||
136 | ||||
137 | bool useLowerUpperBound = Range.isSignWrappedSet() && !Range.isFullSet(); | |||
138 | const auto LB = useLowerUpperBound ? Range.getLower() : Range.getSignedMin(); | |||
139 | V = isl_valFromAPInt(ctx, LB, true); | |||
140 | isl_set *SLB = isl_set_lower_bound_val(isl_set_copy(S), type, dim, V); | |||
141 | ||||
142 | const auto UB = useLowerUpperBound ? Range.getUpper() : Range.getSignedMax(); | |||
143 | V = isl_valFromAPInt(ctx, UB, true); | |||
144 | if (useLowerUpperBound) | |||
145 | V = isl_val_sub_ui(V, 1); | |||
146 | isl_set *SUB = isl_set_upper_bound_val(S, type, dim, V); | |||
147 | ||||
148 | if (useLowerUpperBound) | |||
149 | return isl_set_union(SLB, SUB); | |||
150 | else | |||
151 | return isl_set_intersect(SLB, SUB); | |||
152 | } | |||
153 | ||||
154 | static const ScopArrayInfo *identifyBasePtrOriginSAI(Scop *S, Value *BasePtr) { | |||
155 | LoadInst *BasePtrLI = dyn_cast<LoadInst>(BasePtr); | |||
156 | if (!BasePtrLI) | |||
157 | return nullptr; | |||
158 | ||||
159 | if (!S->getRegion().contains(BasePtrLI)) | |||
160 | return nullptr; | |||
161 | ||||
162 | ScalarEvolution &SE = *S->getSE(); | |||
163 | ||||
164 | auto *OriginBaseSCEV = | |||
165 | SE.getPointerBase(SE.getSCEV(BasePtrLI->getPointerOperand())); | |||
166 | if (!OriginBaseSCEV) | |||
167 | return nullptr; | |||
168 | ||||
169 | auto *OriginBaseSCEVUnknown = dyn_cast<SCEVUnknown>(OriginBaseSCEV); | |||
170 | if (!OriginBaseSCEVUnknown) | |||
171 | return nullptr; | |||
172 | ||||
173 | return S->getScopArrayInfo(OriginBaseSCEVUnknown->getValue(), | |||
174 | ScopArrayInfo::MK_Array); | |||
175 | } | |||
176 | ||||
177 | ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *ElementType, isl_ctx *Ctx, | |||
178 | ArrayRef<const SCEV *> Sizes, enum MemoryKind Kind, | |||
179 | const DataLayout &DL, Scop *S) | |||
180 | : BasePtr(BasePtr), ElementType(ElementType), Kind(Kind), DL(DL), S(*S) { | |||
181 | std::string BasePtrName = | |||
182 | getIslCompatibleName("MemRef_", BasePtr, Kind == MK_PHI ? "__phi" : ""); | |||
183 | Id = isl_id_alloc(Ctx, BasePtrName.c_str(), this); | |||
184 | ||||
185 | updateSizes(Sizes); | |||
186 | BasePtrOriginSAI = identifyBasePtrOriginSAI(S, BasePtr); | |||
187 | if (BasePtrOriginSAI) | |||
188 | const_cast<ScopArrayInfo *>(BasePtrOriginSAI)->addDerivedSAI(this); | |||
189 | } | |||
190 | ||||
191 | __isl_give isl_space *ScopArrayInfo::getSpace() const { | |||
192 | auto Space = | |||
193 | isl_space_set_alloc(isl_id_get_ctx(Id), 0, getNumberOfDimensions()); | |||
194 | Space = isl_space_set_tuple_id(Space, isl_dim_set, isl_id_copy(Id)); | |||
195 | return Space; | |||
196 | } | |||
197 | ||||
198 | bool ScopArrayInfo::updateSizes(ArrayRef<const SCEV *> NewSizes) { | |||
199 | int SharedDims = std::min(NewSizes.size(), DimensionSizes.size()); | |||
200 | int ExtraDimsNew = NewSizes.size() - SharedDims; | |||
201 | int ExtraDimsOld = DimensionSizes.size() - SharedDims; | |||
202 | for (int i = 0; i < SharedDims; i++) | |||
203 | if (NewSizes[i + ExtraDimsNew] != DimensionSizes[i + ExtraDimsOld]) | |||
204 | return false; | |||
205 | ||||
206 | if (DimensionSizes.size() >= NewSizes.size()) | |||
207 | return true; | |||
208 | ||||
209 | DimensionSizes.clear(); | |||
210 | DimensionSizes.insert(DimensionSizes.begin(), NewSizes.begin(), | |||
211 | NewSizes.end()); | |||
212 | for (isl_pw_aff *Size : DimensionSizesPw) | |||
213 | isl_pw_aff_free(Size); | |||
214 | DimensionSizesPw.clear(); | |||
215 | for (const SCEV *Expr : DimensionSizes) { | |||
216 | isl_pw_aff *Size = S.getPwAff(Expr); | |||
217 | DimensionSizesPw.push_back(Size); | |||
218 | } | |||
219 | return true; | |||
220 | } | |||
221 | ||||
222 | ScopArrayInfo::~ScopArrayInfo() { | |||
223 | isl_id_free(Id); | |||
224 | for (isl_pw_aff *Size : DimensionSizesPw) | |||
225 | isl_pw_aff_free(Size); | |||
226 | } | |||
227 | ||||
228 | std::string ScopArrayInfo::getName() const { return isl_id_get_name(Id); } | |||
229 | ||||
230 | int ScopArrayInfo::getElemSizeInBytes() const { | |||
231 | return DL.getTypeAllocSize(ElementType); | |||
232 | } | |||
233 | ||||
234 | isl_id *ScopArrayInfo::getBasePtrId() const { return isl_id_copy(Id); } | |||
235 | ||||
236 | void ScopArrayInfo::dump() const { print(errs()); } | |||
237 | ||||
238 | void ScopArrayInfo::print(raw_ostream &OS, bool SizeAsPwAff) const { | |||
239 | OS.indent(8) << *getElementType() << " " << getName(); | |||
240 | if (getNumberOfDimensions() > 0) | |||
241 | OS << "[*]"; | |||
242 | for (unsigned u = 1; u < getNumberOfDimensions(); u++) { | |||
243 | OS << "["; | |||
244 | ||||
245 | if (SizeAsPwAff) { | |||
246 | auto Size = getDimensionSizePw(u); | |||
247 | OS << " " << Size << " "; | |||
248 | isl_pw_aff_free(Size); | |||
249 | } else { | |||
250 | OS << *getDimensionSize(u); | |||
251 | } | |||
252 | ||||
253 | OS << "]"; | |||
254 | } | |||
255 | ||||
256 | OS << ";"; | |||
257 | ||||
258 | if (BasePtrOriginSAI) | |||
259 | OS << " [BasePtrOrigin: " << BasePtrOriginSAI->getName() << "]"; | |||
260 | ||||
261 | OS << " // Element size " << getElemSizeInBytes() << "\n"; | |||
262 | } | |||
263 | ||||
264 | const ScopArrayInfo * | |||
265 | ScopArrayInfo::getFromAccessFunction(__isl_keep isl_pw_multi_aff *PMA) { | |||
266 | isl_id *Id = isl_pw_multi_aff_get_tuple_id(PMA, isl_dim_out); | |||
267 | assert(Id && "Output dimension didn't have an ID")((Id && "Output dimension didn't have an ID") ? static_cast <void> (0) : __assert_fail ("Id && \"Output dimension didn't have an ID\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 267, __PRETTY_FUNCTION__)); | |||
268 | return getFromId(Id); | |||
269 | } | |||
270 | ||||
271 | const ScopArrayInfo *ScopArrayInfo::getFromId(isl_id *Id) { | |||
272 | void *User = isl_id_get_user(Id); | |||
273 | const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User); | |||
274 | isl_id_free(Id); | |||
275 | return SAI; | |||
276 | } | |||
277 | ||||
278 | void MemoryAccess::updateDimensionality() { | |||
279 | auto ArraySpace = getScopArrayInfo()->getSpace(); | |||
280 | auto AccessSpace = isl_space_range(isl_map_get_space(AccessRelation)); | |||
281 | ||||
282 | auto DimsArray = isl_space_dim(ArraySpace, isl_dim_set); | |||
283 | auto DimsAccess = isl_space_dim(AccessSpace, isl_dim_set); | |||
284 | auto DimsMissing = DimsArray - DimsAccess; | |||
285 | ||||
286 | auto Map = isl_map_from_domain_and_range(isl_set_universe(AccessSpace), | |||
287 | isl_set_universe(ArraySpace)); | |||
288 | ||||
289 | for (unsigned i = 0; i < DimsMissing; i++) | |||
290 | Map = isl_map_fix_si(Map, isl_dim_out, i, 0); | |||
291 | ||||
292 | for (unsigned i = DimsMissing; i < DimsArray; i++) | |||
293 | Map = isl_map_equate(Map, isl_dim_in, i - DimsMissing, isl_dim_out, i); | |||
294 | ||||
295 | AccessRelation = isl_map_apply_range(AccessRelation, Map); | |||
296 | ||||
297 | assumeNoOutOfBound(); | |||
298 | } | |||
299 | ||||
300 | const std::string | |||
301 | MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) { | |||
302 | switch (RT) { | |||
303 | case MemoryAccess::RT_NONE: | |||
304 | llvm_unreachable("Requested a reduction operator string for a memory "::llvm::llvm_unreachable_internal("Requested a reduction operator string for a memory " "access which isn't a reduction", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 305) | |||
305 | "access which isn't a reduction")::llvm::llvm_unreachable_internal("Requested a reduction operator string for a memory " "access which isn't a reduction", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 305); | |||
306 | case MemoryAccess::RT_ADD: | |||
307 | return "+"; | |||
308 | case MemoryAccess::RT_MUL: | |||
309 | return "*"; | |||
310 | case MemoryAccess::RT_BOR: | |||
311 | return "|"; | |||
312 | case MemoryAccess::RT_BXOR: | |||
313 | return "^"; | |||
314 | case MemoryAccess::RT_BAND: | |||
315 | return "&"; | |||
316 | } | |||
317 | llvm_unreachable("Unknown reduction type")::llvm::llvm_unreachable_internal("Unknown reduction type", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 317); | |||
318 | return ""; | |||
319 | } | |||
320 | ||||
321 | /// @brief Return the reduction type for a given binary operator | |||
322 | static MemoryAccess::ReductionType getReductionType(const BinaryOperator *BinOp, | |||
323 | const Instruction *Load) { | |||
324 | if (!BinOp) | |||
325 | return MemoryAccess::RT_NONE; | |||
326 | switch (BinOp->getOpcode()) { | |||
327 | case Instruction::FAdd: | |||
328 | if (!BinOp->hasUnsafeAlgebra()) | |||
329 | return MemoryAccess::RT_NONE; | |||
330 | // Fall through | |||
331 | case Instruction::Add: | |||
332 | return MemoryAccess::RT_ADD; | |||
333 | case Instruction::Or: | |||
334 | return MemoryAccess::RT_BOR; | |||
335 | case Instruction::Xor: | |||
336 | return MemoryAccess::RT_BXOR; | |||
337 | case Instruction::And: | |||
338 | return MemoryAccess::RT_BAND; | |||
339 | case Instruction::FMul: | |||
340 | if (!BinOp->hasUnsafeAlgebra()) | |||
341 | return MemoryAccess::RT_NONE; | |||
342 | // Fall through | |||
343 | case Instruction::Mul: | |||
344 | if (DisableMultiplicativeReductions) | |||
345 | return MemoryAccess::RT_NONE; | |||
346 | return MemoryAccess::RT_MUL; | |||
347 | default: | |||
348 | return MemoryAccess::RT_NONE; | |||
349 | } | |||
350 | } | |||
351 | ||||
352 | /// @brief Derive the individual index expressions from a GEP instruction | |||
353 | /// | |||
354 | /// This function optimistically assumes the GEP references into a fixed size | |||
355 | /// array. If this is actually true, this function returns a list of array | |||
356 | /// subscript expressions as SCEV as well as a list of integers describing | |||
357 | /// the size of the individual array dimensions. Both lists have either equal | |||
358 | /// length of the size list is one element shorter in case there is no known | |||
359 | /// size available for the outermost array dimension. | |||
360 | /// | |||
361 | /// @param GEP The GetElementPtr instruction to analyze. | |||
362 | /// | |||
363 | /// @return A tuple with the subscript expressions and the dimension sizes. | |||
364 | static std::tuple<std::vector<const SCEV *>, std::vector<int>> | |||
365 | getIndexExpressionsFromGEP(GetElementPtrInst *GEP, ScalarEvolution &SE) { | |||
366 | std::vector<const SCEV *> Subscripts; | |||
367 | std::vector<int> Sizes; | |||
368 | ||||
369 | Type *Ty = GEP->getPointerOperandType(); | |||
370 | ||||
371 | bool DroppedFirstDim = false; | |||
372 | ||||
373 | for (unsigned i = 1; i < GEP->getNumOperands(); i++) { | |||
374 | ||||
375 | const SCEV *Expr = SE.getSCEV(GEP->getOperand(i)); | |||
376 | ||||
377 | if (i == 1) { | |||
378 | if (auto PtrTy = dyn_cast<PointerType>(Ty)) { | |||
379 | Ty = PtrTy->getElementType(); | |||
380 | } else if (auto ArrayTy = dyn_cast<ArrayType>(Ty)) { | |||
381 | Ty = ArrayTy->getElementType(); | |||
382 | } else { | |||
383 | Subscripts.clear(); | |||
384 | Sizes.clear(); | |||
385 | break; | |||
386 | } | |||
387 | if (auto Const = dyn_cast<SCEVConstant>(Expr)) | |||
388 | if (Const->getValue()->isZero()) { | |||
389 | DroppedFirstDim = true; | |||
390 | continue; | |||
391 | } | |||
392 | Subscripts.push_back(Expr); | |||
393 | continue; | |||
394 | } | |||
395 | ||||
396 | auto ArrayTy = dyn_cast<ArrayType>(Ty); | |||
397 | if (!ArrayTy) { | |||
398 | Subscripts.clear(); | |||
399 | Sizes.clear(); | |||
400 | break; | |||
401 | } | |||
402 | ||||
403 | Subscripts.push_back(Expr); | |||
404 | if (!(DroppedFirstDim && i == 2)) | |||
405 | Sizes.push_back(ArrayTy->getNumElements()); | |||
406 | ||||
407 | Ty = ArrayTy->getElementType(); | |||
408 | } | |||
409 | ||||
410 | return std::make_tuple(Subscripts, Sizes); | |||
411 | } | |||
412 | ||||
413 | MemoryAccess::~MemoryAccess() { | |||
414 | isl_id_free(Id); | |||
415 | isl_map_free(AccessRelation); | |||
416 | isl_map_free(NewAccessRelation); | |||
417 | } | |||
418 | ||||
419 | const ScopArrayInfo *MemoryAccess::getScopArrayInfo() const { | |||
420 | isl_id *ArrayId = getArrayId(); | |||
421 | void *User = isl_id_get_user(ArrayId); | |||
422 | const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User); | |||
423 | isl_id_free(ArrayId); | |||
424 | return SAI; | |||
425 | } | |||
426 | ||||
427 | __isl_give isl_id *MemoryAccess::getArrayId() const { | |||
428 | return isl_map_get_tuple_id(AccessRelation, isl_dim_out); | |||
429 | } | |||
430 | ||||
431 | __isl_give isl_pw_multi_aff *MemoryAccess::applyScheduleToAccessRelation( | |||
432 | __isl_take isl_union_map *USchedule) const { | |||
433 | isl_map *Schedule, *ScheduledAccRel; | |||
434 | isl_union_set *UDomain; | |||
435 | ||||
436 | UDomain = isl_union_set_from_set(getStatement()->getDomain()); | |||
437 | USchedule = isl_union_map_intersect_domain(USchedule, UDomain); | |||
438 | Schedule = isl_map_from_union_map(USchedule); | |||
439 | ScheduledAccRel = isl_map_apply_domain(getAccessRelation(), Schedule); | |||
440 | return isl_pw_multi_aff_from_map(ScheduledAccRel); | |||
441 | } | |||
442 | ||||
443 | __isl_give isl_map *MemoryAccess::getOriginalAccessRelation() const { | |||
444 | return isl_map_copy(AccessRelation); | |||
445 | } | |||
446 | ||||
447 | std::string MemoryAccess::getOriginalAccessRelationStr() const { | |||
448 | return stringFromIslObj(AccessRelation); | |||
449 | } | |||
450 | ||||
451 | __isl_give isl_space *MemoryAccess::getOriginalAccessRelationSpace() const { | |||
452 | return isl_map_get_space(AccessRelation); | |||
453 | } | |||
454 | ||||
455 | __isl_give isl_map *MemoryAccess::getNewAccessRelation() const { | |||
456 | return isl_map_copy(NewAccessRelation); | |||
457 | } | |||
458 | ||||
459 | std::string MemoryAccess::getNewAccessRelationStr() const { | |||
460 | return stringFromIslObj(NewAccessRelation); | |||
461 | } | |||
462 | ||||
463 | __isl_give isl_basic_map * | |||
464 | MemoryAccess::createBasicAccessMap(ScopStmt *Statement) { | |||
465 | isl_space *Space = isl_space_set_alloc(Statement->getIslCtx(), 0, 1); | |||
466 | Space = isl_space_align_params(Space, Statement->getDomainSpace()); | |||
467 | ||||
468 | return isl_basic_map_from_domain_and_range( | |||
469 | isl_basic_set_universe(Statement->getDomainSpace()), | |||
470 | isl_basic_set_universe(Space)); | |||
471 | } | |||
472 | ||||
473 | // Formalize no out-of-bound access assumption | |||
474 | // | |||
475 | // When delinearizing array accesses we optimistically assume that the | |||
476 | // delinearized accesses do not access out of bound locations (the subscript | |||
477 | // expression of each array evaluates for each statement instance that is | |||
478 | // executed to a value that is larger than zero and strictly smaller than the | |||
479 | // size of the corresponding dimension). The only exception is the outermost | |||
480 | // dimension for which we do not need to assume any upper bound. At this point | |||
481 | // we formalize this assumption to ensure that at code generation time the | |||
482 | // relevant run-time checks can be generated. | |||
483 | // | |||
484 | // To find the set of constraints necessary to avoid out of bound accesses, we | |||
485 | // first build the set of data locations that are not within array bounds. We | |||
486 | // then apply the reverse access relation to obtain the set of iterations that | |||
487 | // may contain invalid accesses and reduce this set of iterations to the ones | |||
488 | // that are actually executed by intersecting them with the domain of the | |||
489 | // statement. If we now project out all loop dimensions, we obtain a set of | |||
490 | // parameters that may cause statement instances to be executed that may | |||
491 | // possibly yield out of bound memory accesses. The complement of these | |||
492 | // constraints is the set of constraints that needs to be assumed to ensure such | |||
493 | // statement instances are never executed. | |||
494 | void MemoryAccess::assumeNoOutOfBound() { | |||
495 | isl_space *Space = isl_space_range(getOriginalAccessRelationSpace()); | |||
496 | isl_set *Outside = isl_set_empty(isl_space_copy(Space)); | |||
497 | for (int i = 1, Size = isl_space_dim(Space, isl_dim_set); i < Size; ++i) { | |||
498 | isl_local_space *LS = isl_local_space_from_space(isl_space_copy(Space)); | |||
499 | isl_pw_aff *Var = | |||
500 | isl_pw_aff_var_on_domain(isl_local_space_copy(LS), isl_dim_set, i); | |||
501 | isl_pw_aff *Zero = isl_pw_aff_zero_on_domain(LS); | |||
502 | ||||
503 | isl_set *DimOutside; | |||
504 | ||||
505 | DimOutside = isl_pw_aff_lt_set(isl_pw_aff_copy(Var), Zero); | |||
506 | isl_pw_aff *SizeE = getScopArrayInfo()->getDimensionSizePw(i); | |||
507 | SizeE = isl_pw_aff_add_dims(SizeE, isl_dim_in, | |||
508 | isl_space_dim(Space, isl_dim_set)); | |||
509 | SizeE = isl_pw_aff_set_tuple_id(SizeE, isl_dim_in, | |||
510 | isl_space_get_tuple_id(Space, isl_dim_set)); | |||
511 | ||||
512 | DimOutside = isl_set_union(DimOutside, isl_pw_aff_le_set(SizeE, Var)); | |||
513 | ||||
514 | Outside = isl_set_union(Outside, DimOutside); | |||
515 | } | |||
516 | ||||
517 | Outside = isl_set_apply(Outside, isl_map_reverse(getAccessRelation())); | |||
518 | Outside = isl_set_intersect(Outside, Statement->getDomain()); | |||
519 | Outside = isl_set_params(Outside); | |||
520 | ||||
521 | // Remove divs to avoid the construction of overly complicated assumptions. | |||
522 | // Doing so increases the set of parameter combinations that are assumed to | |||
523 | // not appear. This is always save, but may make the resulting run-time check | |||
524 | // bail out more often than strictly necessary. | |||
525 | Outside = isl_set_remove_divs(Outside); | |||
526 | Outside = isl_set_complement(Outside); | |||
527 | Statement->getParent()->addAssumption(INBOUNDS, Outside, | |||
528 | getAccessInstruction()->getDebugLoc()); | |||
529 | isl_space_free(Space); | |||
530 | } | |||
531 | ||||
532 | void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) { | |||
533 | ScalarEvolution *SE = Statement->getParent()->getSE(); | |||
534 | ||||
535 | Value *Ptr = getPointerOperand(*getAccessInstruction()); | |||
536 | if (!Ptr || !SE->isSCEVable(Ptr->getType())) | |||
537 | return; | |||
538 | ||||
539 | auto *PtrSCEV = SE->getSCEV(Ptr); | |||
540 | if (isa<SCEVCouldNotCompute>(PtrSCEV)) | |||
541 | return; | |||
542 | ||||
543 | auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV); | |||
544 | if (BasePtrSCEV && !isa<SCEVCouldNotCompute>(BasePtrSCEV)) | |||
545 | PtrSCEV = SE->getMinusSCEV(PtrSCEV, BasePtrSCEV); | |||
546 | ||||
547 | const ConstantRange &Range = SE->getSignedRange(PtrSCEV); | |||
548 | if (Range.isFullSet()) | |||
549 | return; | |||
550 | ||||
551 | bool isWrapping = Range.isSignWrappedSet(); | |||
552 | unsigned BW = Range.getBitWidth(); | |||
553 | const auto LB = isWrapping ? Range.getLower() : Range.getSignedMin(); | |||
554 | const auto UB = isWrapping ? Range.getUpper() : Range.getSignedMax(); | |||
555 | ||||
556 | auto Min = LB.sdiv(APInt(BW, ElementSize)); | |||
557 | auto Max = (UB - APInt(BW, 1)).sdiv(APInt(BW, ElementSize)); | |||
558 | ||||
559 | isl_set *AccessRange = isl_map_range(isl_map_copy(AccessRelation)); | |||
560 | AccessRange = | |||
561 | addRangeBoundsToSet(AccessRange, ConstantRange(Min, Max), 0, isl_dim_set); | |||
562 | AccessRelation = isl_map_intersect_range(AccessRelation, AccessRange); | |||
563 | } | |||
564 | ||||
565 | __isl_give isl_map *MemoryAccess::foldAccess(__isl_take isl_map *AccessRelation, | |||
566 | ScopStmt *Statement) { | |||
567 | int Size = Subscripts.size(); | |||
568 | ||||
569 | for (int i = Size - 2; i >= 0; --i) { | |||
570 | isl_space *Space; | |||
571 | isl_map *MapOne, *MapTwo; | |||
572 | isl_pw_aff *DimSize = Statement->getPwAff(Sizes[i]); | |||
573 | ||||
574 | isl_space *SpaceSize = isl_pw_aff_get_space(DimSize); | |||
575 | isl_pw_aff_free(DimSize); | |||
576 | isl_id *ParamId = isl_space_get_dim_id(SpaceSize, isl_dim_param, 0); | |||
577 | ||||
578 | Space = isl_map_get_space(AccessRelation); | |||
579 | Space = isl_space_map_from_set(isl_space_range(Space)); | |||
580 | Space = isl_space_align_params(Space, SpaceSize); | |||
581 | ||||
582 | int ParamLocation = isl_space_find_dim_by_id(Space, isl_dim_param, ParamId); | |||
583 | isl_id_free(ParamId); | |||
584 | ||||
585 | MapOne = isl_map_universe(isl_space_copy(Space)); | |||
586 | for (int j = 0; j < Size; ++j) | |||
587 | MapOne = isl_map_equate(MapOne, isl_dim_in, j, isl_dim_out, j); | |||
588 | MapOne = isl_map_lower_bound_si(MapOne, isl_dim_in, i + 1, 0); | |||
589 | ||||
590 | MapTwo = isl_map_universe(isl_space_copy(Space)); | |||
591 | for (int j = 0; j < Size; ++j) | |||
592 | if (j < i || j > i + 1) | |||
593 | MapTwo = isl_map_equate(MapTwo, isl_dim_in, j, isl_dim_out, j); | |||
594 | ||||
595 | isl_local_space *LS = isl_local_space_from_space(Space); | |||
596 | isl_constraint *C; | |||
597 | C = isl_equality_alloc(isl_local_space_copy(LS)); | |||
598 | C = isl_constraint_set_constant_si(C, -1); | |||
599 | C = isl_constraint_set_coefficient_si(C, isl_dim_in, i, 1); | |||
600 | C = isl_constraint_set_coefficient_si(C, isl_dim_out, i, -1); | |||
601 | MapTwo = isl_map_add_constraint(MapTwo, C); | |||
602 | C = isl_equality_alloc(LS); | |||
603 | C = isl_constraint_set_coefficient_si(C, isl_dim_in, i + 1, 1); | |||
604 | C = isl_constraint_set_coefficient_si(C, isl_dim_out, i + 1, -1); | |||
605 | C = isl_constraint_set_coefficient_si(C, isl_dim_param, ParamLocation, 1); | |||
606 | MapTwo = isl_map_add_constraint(MapTwo, C); | |||
607 | MapTwo = isl_map_upper_bound_si(MapTwo, isl_dim_in, i + 1, -1); | |||
608 | ||||
609 | MapOne = isl_map_union(MapOne, MapTwo); | |||
610 | AccessRelation = isl_map_apply_range(AccessRelation, MapOne); | |||
611 | } | |||
612 | return AccessRelation; | |||
613 | } | |||
614 | ||||
615 | /// @brief Check if @p Expr is divisible by @p Size. | |||
616 | static bool isDivisible(const SCEV *Expr, unsigned Size, ScalarEvolution &SE) { | |||
617 | ||||
618 | // Only one factor needs to be divisible. | |||
619 | if (auto *MulExpr = dyn_cast<SCEVMulExpr>(Expr)) { | |||
620 | for (auto *FactorExpr : MulExpr->operands()) | |||
621 | if (isDivisible(FactorExpr, Size, SE)) | |||
622 | return true; | |||
623 | return false; | |||
624 | } | |||
625 | ||||
626 | // For other n-ary expressions (Add, AddRec, Max,...) all operands need | |||
627 | // to be divisble. | |||
628 | if (auto *NAryExpr = dyn_cast<SCEVNAryExpr>(Expr)) { | |||
629 | for (auto *OpExpr : NAryExpr->operands()) | |||
630 | if (!isDivisible(OpExpr, Size, SE)) | |||
631 | return false; | |||
632 | return true; | |||
633 | } | |||
634 | ||||
635 | auto *SizeSCEV = SE.getConstant(Expr->getType(), Size); | |||
636 | auto *UDivSCEV = SE.getUDivExpr(Expr, SizeSCEV); | |||
637 | auto *MulSCEV = SE.getMulExpr(UDivSCEV, SizeSCEV); | |||
638 | return MulSCEV == Expr; | |||
639 | } | |||
640 | ||||
641 | void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) { | |||
642 | assert(!AccessRelation && "AccessReltation already built")((!AccessRelation && "AccessReltation already built") ? static_cast<void> (0) : __assert_fail ("!AccessRelation && \"AccessReltation already built\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 642, __PRETTY_FUNCTION__)); | |||
643 | ||||
644 | isl_ctx *Ctx = isl_id_get_ctx(Id); | |||
645 | isl_id *BaseAddrId = SAI->getBasePtrId(); | |||
646 | ||||
647 | if (!isAffine()) { | |||
648 | // We overapproximate non-affine accesses with a possible access to the | |||
649 | // whole array. For read accesses it does not make a difference, if an | |||
650 | // access must or may happen. However, for write accesses it is important to | |||
651 | // differentiate between writes that must happen and writes that may happen. | |||
652 | AccessRelation = isl_map_from_basic_map(createBasicAccessMap(Statement)); | |||
653 | AccessRelation = | |||
654 | isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId); | |||
655 | ||||
656 | computeBoundsOnAccessRelation(getElemSizeInBytes()); | |||
657 | return; | |||
658 | } | |||
659 | ||||
660 | Scop &S = *getStatement()->getParent(); | |||
661 | isl_space *Space = isl_space_alloc(Ctx, 0, Statement->getNumIterators(), 0); | |||
662 | AccessRelation = isl_map_universe(Space); | |||
663 | ||||
664 | for (int i = 0, Size = Subscripts.size(); i < Size; ++i) { | |||
665 | isl_pw_aff *Affine = Statement->getPwAff(Subscripts[i]); | |||
666 | ||||
667 | if (Size == 1) { | |||
668 | // For the non delinearized arrays, divide the access function of the last | |||
669 | // subscript by the size of the elements in the array. | |||
670 | // | |||
671 | // A stride one array access in C expressed as A[i] is expressed in | |||
672 | // LLVM-IR as something like A[i * elementsize]. This hides the fact that | |||
673 | // two subsequent values of 'i' index two values that are stored next to | |||
674 | // each other in memory. By this division we make this characteristic | |||
675 | // obvious again. However, if the index is not divisible by the element | |||
676 | // size we will bail out. | |||
677 | isl_val *v = isl_val_int_from_si(Ctx, getElemSizeInBytes()); | |||
678 | Affine = isl_pw_aff_scale_down_val(Affine, v); | |||
679 | ||||
680 | if (!isDivisible(Subscripts[0], getElemSizeInBytes(), *S.getSE())) | |||
681 | S.invalidate(ALIGNMENT, AccessInstruction->getDebugLoc()); | |||
682 | } | |||
683 | ||||
684 | isl_map *SubscriptMap = isl_map_from_pw_aff(Affine); | |||
685 | ||||
686 | AccessRelation = isl_map_flat_range_product(AccessRelation, SubscriptMap); | |||
687 | } | |||
688 | ||||
689 | if (Sizes.size() > 1 && !isa<SCEVConstant>(Sizes[0])) | |||
690 | AccessRelation = foldAccess(AccessRelation, Statement); | |||
691 | ||||
692 | Space = Statement->getDomainSpace(); | |||
693 | AccessRelation = isl_map_set_tuple_id( | |||
694 | AccessRelation, isl_dim_in, isl_space_get_tuple_id(Space, isl_dim_set)); | |||
695 | AccessRelation = | |||
696 | isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId); | |||
697 | ||||
698 | AccessRelation = isl_map_gist_domain(AccessRelation, Statement->getDomain()); | |||
699 | isl_space_free(Space); | |||
700 | } | |||
701 | ||||
702 | MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, | |||
703 | AccessType Type, Value *BaseAddress, | |||
704 | unsigned ElemBytes, bool Affine, | |||
705 | ArrayRef<const SCEV *> Subscripts, | |||
706 | ArrayRef<const SCEV *> Sizes, Value *AccessValue, | |||
707 | ScopArrayInfo::MemoryKind Kind, StringRef BaseName) | |||
708 | : Kind(Kind), AccType(Type), RedType(RT_NONE), Statement(Stmt), | |||
709 | BaseAddr(BaseAddress), BaseName(BaseName), ElemBytes(ElemBytes), | |||
710 | Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst), | |||
711 | AccessValue(AccessValue), IsAffine(Affine), | |||
712 | Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr), | |||
713 | NewAccessRelation(nullptr) { | |||
714 | ||||
715 | std::string IdName = "__polly_array_ref"; | |||
716 | Id = isl_id_alloc(Stmt->getParent()->getIslCtx(), IdName.c_str(), this); | |||
717 | } | |||
718 | ||||
719 | void MemoryAccess::realignParams() { | |||
720 | isl_space *ParamSpace = Statement->getParent()->getParamSpace(); | |||
721 | AccessRelation = isl_map_align_params(AccessRelation, ParamSpace); | |||
722 | } | |||
723 | ||||
724 | const std::string MemoryAccess::getReductionOperatorStr() const { | |||
725 | return MemoryAccess::getReductionOperatorStr(getReductionType()); | |||
726 | } | |||
727 | ||||
728 | __isl_give isl_id *MemoryAccess::getId() const { return isl_id_copy(Id); } | |||
729 | ||||
730 | raw_ostream &polly::operator<<(raw_ostream &OS, | |||
731 | MemoryAccess::ReductionType RT) { | |||
732 | if (RT == MemoryAccess::RT_NONE) | |||
733 | OS << "NONE"; | |||
734 | else | |||
735 | OS << MemoryAccess::getReductionOperatorStr(RT); | |||
736 | return OS; | |||
737 | } | |||
738 | ||||
739 | void MemoryAccess::print(raw_ostream &OS) const { | |||
740 | switch (AccType) { | |||
741 | case READ: | |||
742 | OS.indent(12) << "ReadAccess :=\t"; | |||
743 | break; | |||
744 | case MUST_WRITE: | |||
745 | OS.indent(12) << "MustWriteAccess :=\t"; | |||
746 | break; | |||
747 | case MAY_WRITE: | |||
748 | OS.indent(12) << "MayWriteAccess :=\t"; | |||
749 | break; | |||
750 | } | |||
751 | OS << "[Reduction Type: " << getReductionType() << "] "; | |||
752 | OS << "[Scalar: " << isScalarKind() << "]\n"; | |||
753 | OS.indent(16) << getOriginalAccessRelationStr() << ";\n"; | |||
754 | if (hasNewAccessRelation()) | |||
755 | OS.indent(11) << "new: " << getNewAccessRelationStr() << ";\n"; | |||
756 | } | |||
757 | ||||
758 | void MemoryAccess::dump() const { print(errs()); } | |||
759 | ||||
760 | // Create a map in the size of the provided set domain, that maps from the | |||
761 | // one element of the provided set domain to another element of the provided | |||
762 | // set domain. | |||
763 | // The mapping is limited to all points that are equal in all but the last | |||
764 | // dimension and for which the last dimension of the input is strict smaller | |||
765 | // than the last dimension of the output. | |||
766 | // | |||
767 | // getEqualAndLarger(set[i0, i1, ..., iX]): | |||
768 | // | |||
769 | // set[i0, i1, ..., iX] -> set[o0, o1, ..., oX] | |||
770 | // : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1), iX < oX | |||
771 | // | |||
772 | static isl_map *getEqualAndLarger(isl_space *setDomain) { | |||
773 | isl_space *Space = isl_space_map_from_set(setDomain); | |||
774 | isl_map *Map = isl_map_universe(Space); | |||
775 | unsigned lastDimension = isl_map_dim(Map, isl_dim_in) - 1; | |||
776 | ||||
777 | // Set all but the last dimension to be equal for the input and output | |||
778 | // | |||
779 | // input[i0, i1, ..., iX] -> output[o0, o1, ..., oX] | |||
780 | // : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1) | |||
781 | for (unsigned i = 0; i < lastDimension; ++i) | |||
782 | Map = isl_map_equate(Map, isl_dim_in, i, isl_dim_out, i); | |||
783 | ||||
784 | // Set the last dimension of the input to be strict smaller than the | |||
785 | // last dimension of the output. | |||
786 | // | |||
787 | // input[?,?,?,...,iX] -> output[?,?,?,...,oX] : iX < oX | |||
788 | Map = isl_map_order_lt(Map, isl_dim_in, lastDimension, isl_dim_out, | |||
789 | lastDimension); | |||
790 | return Map; | |||
791 | } | |||
792 | ||||
793 | __isl_give isl_set * | |||
794 | MemoryAccess::getStride(__isl_take const isl_map *Schedule) const { | |||
795 | isl_map *S = const_cast<isl_map *>(Schedule); | |||
796 | isl_map *AccessRelation = getAccessRelation(); | |||
797 | isl_space *Space = isl_space_range(isl_map_get_space(S)); | |||
798 | isl_map *NextScatt = getEqualAndLarger(Space); | |||
799 | ||||
800 | S = isl_map_reverse(S); | |||
801 | NextScatt = isl_map_lexmin(NextScatt); | |||
802 | ||||
803 | NextScatt = isl_map_apply_range(NextScatt, isl_map_copy(S)); | |||
804 | NextScatt = isl_map_apply_range(NextScatt, isl_map_copy(AccessRelation)); | |||
805 | NextScatt = isl_map_apply_domain(NextScatt, S); | |||
806 | NextScatt = isl_map_apply_domain(NextScatt, AccessRelation); | |||
807 | ||||
808 | isl_set *Deltas = isl_map_deltas(NextScatt); | |||
809 | return Deltas; | |||
810 | } | |||
811 | ||||
812 | bool MemoryAccess::isStrideX(__isl_take const isl_map *Schedule, | |||
813 | int StrideWidth) const { | |||
814 | isl_set *Stride, *StrideX; | |||
815 | bool IsStrideX; | |||
816 | ||||
817 | Stride = getStride(Schedule); | |||
818 | StrideX = isl_set_universe(isl_set_get_space(Stride)); | |||
819 | for (unsigned i = 0; i < isl_set_dim(StrideX, isl_dim_set) - 1; i++) | |||
820 | StrideX = isl_set_fix_si(StrideX, isl_dim_set, i, 0); | |||
821 | StrideX = isl_set_fix_si(StrideX, isl_dim_set, | |||
822 | isl_set_dim(StrideX, isl_dim_set) - 1, StrideWidth); | |||
823 | IsStrideX = isl_set_is_subset(Stride, StrideX); | |||
824 | ||||
825 | isl_set_free(StrideX); | |||
826 | isl_set_free(Stride); | |||
827 | ||||
828 | return IsStrideX; | |||
829 | } | |||
830 | ||||
831 | bool MemoryAccess::isStrideZero(const isl_map *Schedule) const { | |||
832 | return isStrideX(Schedule, 0); | |||
833 | } | |||
834 | ||||
835 | bool MemoryAccess::isStrideOne(const isl_map *Schedule) const { | |||
836 | return isStrideX(Schedule, 1); | |||
837 | } | |||
838 | ||||
839 | void MemoryAccess::setNewAccessRelation(isl_map *NewAccess) { | |||
840 | isl_map_free(NewAccessRelation); | |||
841 | NewAccessRelation = NewAccess; | |||
842 | } | |||
843 | ||||
844 | //===----------------------------------------------------------------------===// | |||
845 | ||||
846 | isl_map *ScopStmt::getSchedule() const { | |||
847 | isl_set *Domain = getDomain(); | |||
848 | if (isl_set_is_empty(Domain)) { | |||
849 | isl_set_free(Domain); | |||
850 | return isl_map_from_aff( | |||
851 | isl_aff_zero_on_domain(isl_local_space_from_space(getDomainSpace()))); | |||
852 | } | |||
853 | auto *Schedule = getParent()->getSchedule(); | |||
854 | Schedule = isl_union_map_intersect_domain( | |||
855 | Schedule, isl_union_set_from_set(isl_set_copy(Domain))); | |||
856 | if (isl_union_map_is_empty(Schedule)) { | |||
857 | isl_set_free(Domain); | |||
858 | isl_union_map_free(Schedule); | |||
859 | return isl_map_from_aff( | |||
860 | isl_aff_zero_on_domain(isl_local_space_from_space(getDomainSpace()))); | |||
861 | } | |||
862 | auto *M = isl_map_from_union_map(Schedule); | |||
863 | M = isl_map_coalesce(M); | |||
864 | M = isl_map_gist_domain(M, Domain); | |||
865 | M = isl_map_coalesce(M); | |||
866 | return M; | |||
867 | } | |||
868 | ||||
869 | __isl_give isl_pw_aff *ScopStmt::getPwAff(const SCEV *E) { | |||
870 | return getParent()->getPwAff(E, isBlockStmt() ? getBasicBlock() | |||
871 | : getRegion()->getEntry()); | |||
872 | } | |||
873 | ||||
874 | void ScopStmt::restrictDomain(__isl_take isl_set *NewDomain) { | |||
875 | assert(isl_set_is_subset(NewDomain, Domain) &&((isl_set_is_subset(NewDomain, Domain) && "New domain is not a subset of old domain!" ) ? static_cast<void> (0) : __assert_fail ("isl_set_is_subset(NewDomain, Domain) && \"New domain is not a subset of old domain!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 876, __PRETTY_FUNCTION__)) | |||
876 | "New domain is not a subset of old domain!")((isl_set_is_subset(NewDomain, Domain) && "New domain is not a subset of old domain!" ) ? static_cast<void> (0) : __assert_fail ("isl_set_is_subset(NewDomain, Domain) && \"New domain is not a subset of old domain!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 876, __PRETTY_FUNCTION__)); | |||
877 | isl_set_free(Domain); | |||
878 | Domain = NewDomain; | |||
879 | } | |||
880 | ||||
881 | void ScopStmt::buildAccessRelations() { | |||
882 | for (MemoryAccess *Access : MemAccs) { | |||
883 | Type *ElementType = Access->getAccessValue()->getType(); | |||
884 | ||||
885 | ScopArrayInfo::MemoryKind Ty; | |||
886 | if (Access->isPHIKind()) | |||
887 | Ty = ScopArrayInfo::MK_PHI; | |||
888 | else if (Access->isExitPHIKind()) | |||
889 | Ty = ScopArrayInfo::MK_ExitPHI; | |||
890 | else if (Access->isValueKind()) | |||
891 | Ty = ScopArrayInfo::MK_Value; | |||
892 | else | |||
893 | Ty = ScopArrayInfo::MK_Array; | |||
894 | ||||
895 | const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo( | |||
896 | Access->getBaseAddr(), ElementType, Access->Sizes, Ty); | |||
897 | ||||
898 | Access->buildAccessRelation(SAI); | |||
899 | } | |||
900 | } | |||
901 | ||||
902 | void ScopStmt::addAccess(MemoryAccess *Access) { | |||
903 | Instruction *AccessInst = Access->getAccessInstruction(); | |||
904 | ||||
905 | if (Access->isArrayKind()) { | |||
906 | MemoryAccessList &MAL = InstructionToAccess[AccessInst]; | |||
907 | MAL.emplace_front(Access); | |||
908 | } | |||
909 | ||||
910 | MemAccs.push_back(Access); | |||
911 | } | |||
912 | ||||
913 | void ScopStmt::realignParams() { | |||
914 | for (MemoryAccess *MA : *this) | |||
915 | MA->realignParams(); | |||
916 | ||||
917 | Domain = isl_set_align_params(Domain, Parent.getParamSpace()); | |||
918 | } | |||
919 | ||||
920 | /// @brief Add @p BSet to the set @p User if @p BSet is bounded. | |||
921 | static isl_stat collectBoundedParts(__isl_take isl_basic_set *BSet, | |||
922 | void *User) { | |||
923 | isl_set **BoundedParts = static_cast<isl_set **>(User); | |||
924 | if (isl_basic_set_is_bounded(BSet)) | |||
925 | *BoundedParts = isl_set_union(*BoundedParts, isl_set_from_basic_set(BSet)); | |||
926 | else | |||
927 | isl_basic_set_free(BSet); | |||
928 | return isl_stat_ok; | |||
929 | } | |||
930 | ||||
931 | /// @brief Return the bounded parts of @p S. | |||
932 | static __isl_give isl_set *collectBoundedParts(__isl_take isl_set *S) { | |||
933 | isl_set *BoundedParts = isl_set_empty(isl_set_get_space(S)); | |||
934 | isl_set_foreach_basic_set(S, collectBoundedParts, &BoundedParts); | |||
935 | isl_set_free(S); | |||
936 | return BoundedParts; | |||
937 | } | |||
938 | ||||
939 | /// @brief Compute the (un)bounded parts of @p S wrt. to dimension @p Dim. | |||
940 | /// | |||
941 | /// @returns A separation of @p S into first an unbounded then a bounded subset, | |||
942 | /// both with regards to the dimension @p Dim. | |||
943 | static std::pair<__isl_give isl_set *, __isl_give isl_set *> | |||
944 | partitionSetParts(__isl_take isl_set *S, unsigned Dim) { | |||
945 | ||||
946 | for (unsigned u = 0, e = isl_set_n_dim(S); u < e; u++) | |||
947 | S = isl_set_lower_bound_si(S, isl_dim_set, u, 0); | |||
948 | ||||
949 | unsigned NumDimsS = isl_set_n_dim(S); | |||
950 | isl_set *OnlyDimS = isl_set_copy(S); | |||
951 | ||||
952 | // Remove dimensions that are greater than Dim as they are not interesting. | |||
953 | assert(NumDimsS >= Dim + 1)((NumDimsS >= Dim + 1) ? static_cast<void> (0) : __assert_fail ("NumDimsS >= Dim + 1", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 953, __PRETTY_FUNCTION__)); | |||
954 | OnlyDimS = | |||
955 | isl_set_project_out(OnlyDimS, isl_dim_set, Dim + 1, NumDimsS - Dim - 1); | |||
956 | ||||
957 | // Create artificial parametric upper bounds for dimensions smaller than Dim | |||
958 | // as we are not interested in them. | |||
959 | OnlyDimS = isl_set_insert_dims(OnlyDimS, isl_dim_param, 0, Dim); | |||
960 | for (unsigned u = 0; u < Dim; u++) { | |||
961 | isl_constraint *C = isl_inequality_alloc( | |||
962 | isl_local_space_from_space(isl_set_get_space(OnlyDimS))); | |||
963 | C = isl_constraint_set_coefficient_si(C, isl_dim_param, u, 1); | |||
964 | C = isl_constraint_set_coefficient_si(C, isl_dim_set, u, -1); | |||
965 | OnlyDimS = isl_set_add_constraint(OnlyDimS, C); | |||
966 | } | |||
967 | ||||
968 | // Collect all bounded parts of OnlyDimS. | |||
969 | isl_set *BoundedParts = collectBoundedParts(OnlyDimS); | |||
970 | ||||
971 | // Create the dimensions greater than Dim again. | |||
972 | BoundedParts = isl_set_insert_dims(BoundedParts, isl_dim_set, Dim + 1, | |||
973 | NumDimsS - Dim - 1); | |||
974 | ||||
975 | // Remove the artificial upper bound parameters again. | |||
976 | BoundedParts = isl_set_remove_dims(BoundedParts, isl_dim_param, 0, Dim); | |||
977 | ||||
978 | isl_set *UnboundedParts = isl_set_subtract(S, isl_set_copy(BoundedParts)); | |||
979 | return std::make_pair(UnboundedParts, BoundedParts); | |||
980 | } | |||
981 | ||||
982 | /// @brief Set the dimension Ids from @p From in @p To. | |||
983 | static __isl_give isl_set *setDimensionIds(__isl_keep isl_set *From, | |||
984 | __isl_take isl_set *To) { | |||
985 | for (unsigned u = 0, e = isl_set_n_dim(From); u < e; u++) { | |||
986 | isl_id *DimId = isl_set_get_dim_id(From, isl_dim_set, u); | |||
987 | To = isl_set_set_dim_id(To, isl_dim_set, u, DimId); | |||
988 | } | |||
989 | return To; | |||
990 | } | |||
991 | ||||
992 | /// @brief Create the conditions under which @p L @p Pred @p R is true. | |||
993 | static __isl_give isl_set *buildConditionSet(ICmpInst::Predicate Pred, | |||
994 | __isl_take isl_pw_aff *L, | |||
995 | __isl_take isl_pw_aff *R) { | |||
996 | switch (Pred) { | |||
997 | case ICmpInst::ICMP_EQ: | |||
998 | return isl_pw_aff_eq_set(L, R); | |||
999 | case ICmpInst::ICMP_NE: | |||
1000 | return isl_pw_aff_ne_set(L, R); | |||
1001 | case ICmpInst::ICMP_SLT: | |||
1002 | return isl_pw_aff_lt_set(L, R); | |||
1003 | case ICmpInst::ICMP_SLE: | |||
1004 | return isl_pw_aff_le_set(L, R); | |||
1005 | case ICmpInst::ICMP_SGT: | |||
1006 | return isl_pw_aff_gt_set(L, R); | |||
1007 | case ICmpInst::ICMP_SGE: | |||
1008 | return isl_pw_aff_ge_set(L, R); | |||
1009 | case ICmpInst::ICMP_ULT: | |||
1010 | return isl_pw_aff_lt_set(L, R); | |||
1011 | case ICmpInst::ICMP_UGT: | |||
1012 | return isl_pw_aff_gt_set(L, R); | |||
1013 | case ICmpInst::ICMP_ULE: | |||
1014 | return isl_pw_aff_le_set(L, R); | |||
1015 | case ICmpInst::ICMP_UGE: | |||
1016 | return isl_pw_aff_ge_set(L, R); | |||
1017 | default: | |||
1018 | llvm_unreachable("Non integer predicate not supported")::llvm::llvm_unreachable_internal("Non integer predicate not supported" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1018); | |||
1019 | } | |||
1020 | } | |||
1021 | ||||
1022 | /// @brief Create the conditions under which @p L @p Pred @p R is true. | |||
1023 | /// | |||
1024 | /// Helper function that will make sure the dimensions of the result have the | |||
1025 | /// same isl_id's as the @p Domain. | |||
1026 | static __isl_give isl_set *buildConditionSet(ICmpInst::Predicate Pred, | |||
1027 | __isl_take isl_pw_aff *L, | |||
1028 | __isl_take isl_pw_aff *R, | |||
1029 | __isl_keep isl_set *Domain) { | |||
1030 | isl_set *ConsequenceCondSet = buildConditionSet(Pred, L, R); | |||
1031 | return setDimensionIds(Domain, ConsequenceCondSet); | |||
1032 | } | |||
1033 | ||||
1034 | /// @brief Build the conditions sets for the switch @p SI in the @p Domain. | |||
1035 | /// | |||
1036 | /// This will fill @p ConditionSets with the conditions under which control | |||
1037 | /// will be moved from @p SI to its successors. Hence, @p ConditionSets will | |||
1038 | /// have as many elements as @p SI has successors. | |||
1039 | static void | |||
1040 | buildConditionSets(Scop &S, SwitchInst *SI, Loop *L, __isl_keep isl_set *Domain, | |||
1041 | SmallVectorImpl<__isl_give isl_set *> &ConditionSets) { | |||
1042 | ||||
1043 | Value *Condition = getConditionFromTerminator(SI); | |||
1044 | assert(Condition && "No condition for switch")((Condition && "No condition for switch") ? static_cast <void> (0) : __assert_fail ("Condition && \"No condition for switch\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1044, __PRETTY_FUNCTION__)); | |||
1045 | ||||
1046 | ScalarEvolution &SE = *S.getSE(); | |||
1047 | BasicBlock *BB = SI->getParent(); | |||
1048 | isl_pw_aff *LHS, *RHS; | |||
1049 | LHS = S.getPwAff(SE.getSCEVAtScope(Condition, L), BB); | |||
1050 | ||||
1051 | unsigned NumSuccessors = SI->getNumSuccessors(); | |||
1052 | ConditionSets.resize(NumSuccessors); | |||
1053 | for (auto &Case : SI->cases()) { | |||
1054 | unsigned Idx = Case.getSuccessorIndex(); | |||
1055 | ConstantInt *CaseValue = Case.getCaseValue(); | |||
1056 | ||||
1057 | RHS = S.getPwAff(SE.getSCEV(CaseValue), BB); | |||
1058 | isl_set *CaseConditionSet = | |||
1059 | buildConditionSet(ICmpInst::ICMP_EQ, isl_pw_aff_copy(LHS), RHS, Domain); | |||
1060 | ConditionSets[Idx] = isl_set_coalesce( | |||
1061 | isl_set_intersect(CaseConditionSet, isl_set_copy(Domain))); | |||
1062 | } | |||
1063 | ||||
1064 | assert(ConditionSets[0] == nullptr && "Default condition set was set")((ConditionSets[0] == nullptr && "Default condition set was set" ) ? static_cast<void> (0) : __assert_fail ("ConditionSets[0] == nullptr && \"Default condition set was set\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1064, __PRETTY_FUNCTION__)); | |||
1065 | isl_set *ConditionSetUnion = isl_set_copy(ConditionSets[1]); | |||
1066 | for (unsigned u = 2; u < NumSuccessors; u++) | |||
1067 | ConditionSetUnion = | |||
1068 | isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u])); | |||
1069 | ConditionSets[0] = setDimensionIds( | |||
1070 | Domain, isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion)); | |||
1071 | ||||
1072 | S.markAsOptimized(); | |||
1073 | isl_pw_aff_free(LHS); | |||
1074 | } | |||
1075 | ||||
1076 | /// @brief Build the conditions sets for the branch condition @p Condition in | |||
1077 | /// the @p Domain. | |||
1078 | /// | |||
1079 | /// This will fill @p ConditionSets with the conditions under which control | |||
1080 | /// will be moved from @p TI to its successors. Hence, @p ConditionSets will | |||
1081 | /// have as many elements as @p TI has successors. If @p TI is nullptr the | |||
1082 | /// context under which @p Condition is true/false will be returned as the | |||
1083 | /// new elements of @p ConditionSets. | |||
1084 | static void | |||
1085 | buildConditionSets(Scop &S, Value *Condition, TerminatorInst *TI, Loop *L, | |||
1086 | __isl_keep isl_set *Domain, | |||
1087 | SmallVectorImpl<__isl_give isl_set *> &ConditionSets) { | |||
1088 | ||||
1089 | isl_set *ConsequenceCondSet = nullptr; | |||
1090 | if (auto *CCond = dyn_cast<ConstantInt>(Condition)) { | |||
1091 | if (CCond->isZero()) | |||
1092 | ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain)); | |||
1093 | else | |||
1094 | ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain)); | |||
1095 | } else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) { | |||
1096 | auto Opcode = BinOp->getOpcode(); | |||
1097 | assert(Opcode == Instruction::And || Opcode == Instruction::Or)((Opcode == Instruction::And || Opcode == Instruction::Or) ? static_cast <void> (0) : __assert_fail ("Opcode == Instruction::And || Opcode == Instruction::Or" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1097, __PRETTY_FUNCTION__)); | |||
1098 | ||||
1099 | buildConditionSets(S, BinOp->getOperand(0), TI, L, Domain, ConditionSets); | |||
1100 | buildConditionSets(S, BinOp->getOperand(1), TI, L, Domain, ConditionSets); | |||
1101 | ||||
1102 | isl_set_free(ConditionSets.pop_back_val()); | |||
1103 | isl_set *ConsCondPart0 = ConditionSets.pop_back_val(); | |||
1104 | isl_set_free(ConditionSets.pop_back_val()); | |||
1105 | isl_set *ConsCondPart1 = ConditionSets.pop_back_val(); | |||
1106 | ||||
1107 | if (Opcode == Instruction::And) | |||
1108 | ConsequenceCondSet = isl_set_intersect(ConsCondPart0, ConsCondPart1); | |||
1109 | else | |||
1110 | ConsequenceCondSet = isl_set_union(ConsCondPart0, ConsCondPart1); | |||
1111 | } else { | |||
1112 | auto *ICond = dyn_cast<ICmpInst>(Condition); | |||
1113 | assert(ICond &&((ICond && "Condition of exiting branch was neither constant nor ICmp!" ) ? static_cast<void> (0) : __assert_fail ("ICond && \"Condition of exiting branch was neither constant nor ICmp!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1114, __PRETTY_FUNCTION__)) | |||
1114 | "Condition of exiting branch was neither constant nor ICmp!")((ICond && "Condition of exiting branch was neither constant nor ICmp!" ) ? static_cast<void> (0) : __assert_fail ("ICond && \"Condition of exiting branch was neither constant nor ICmp!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1114, __PRETTY_FUNCTION__)); | |||
1115 | ||||
1116 | ScalarEvolution &SE = *S.getSE(); | |||
1117 | BasicBlock *BB = TI ? TI->getParent() : nullptr; | |||
1118 | isl_pw_aff *LHS, *RHS; | |||
1119 | LHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L), BB); | |||
1120 | RHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L), BB); | |||
1121 | ConsequenceCondSet = | |||
1122 | buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain); | |||
1123 | } | |||
1124 | ||||
1125 | // If no terminator was given we are only looking for parameter constraints | |||
1126 | // under which @p Condition is true/false. | |||
1127 | if (!TI) | |||
1128 | ConsequenceCondSet = isl_set_params(ConsequenceCondSet); | |||
1129 | ||||
1130 | assert(ConsequenceCondSet)((ConsequenceCondSet) ? static_cast<void> (0) : __assert_fail ("ConsequenceCondSet", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1130, __PRETTY_FUNCTION__)); | |||
1131 | isl_set *AlternativeCondSet = | |||
1132 | isl_set_complement(isl_set_copy(ConsequenceCondSet)); | |||
1133 | ||||
1134 | ConditionSets.push_back(isl_set_coalesce( | |||
1135 | isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain)))); | |||
1136 | ConditionSets.push_back(isl_set_coalesce( | |||
1137 | isl_set_intersect(AlternativeCondSet, isl_set_copy(Domain)))); | |||
1138 | } | |||
1139 | ||||
1140 | /// @brief Build the conditions sets for the terminator @p TI in the @p Domain. | |||
1141 | /// | |||
1142 | /// This will fill @p ConditionSets with the conditions under which control | |||
1143 | /// will be moved from @p TI to its successors. Hence, @p ConditionSets will | |||
1144 | /// have as many elements as @p TI has successors. | |||
1145 | static void | |||
1146 | buildConditionSets(Scop &S, TerminatorInst *TI, Loop *L, | |||
1147 | __isl_keep isl_set *Domain, | |||
1148 | SmallVectorImpl<__isl_give isl_set *> &ConditionSets) { | |||
1149 | ||||
1150 | if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) | |||
1151 | return buildConditionSets(S, SI, L, Domain, ConditionSets); | |||
1152 | ||||
1153 | assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.")((isa<BranchInst>(TI) && "Terminator was neither branch nor switch." ) ? static_cast<void> (0) : __assert_fail ("isa<BranchInst>(TI) && \"Terminator was neither branch nor switch.\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1153, __PRETTY_FUNCTION__)); | |||
1154 | ||||
1155 | if (TI->getNumSuccessors() == 1) { | |||
1156 | ConditionSets.push_back(isl_set_copy(Domain)); | |||
1157 | return; | |||
1158 | } | |||
1159 | ||||
1160 | Value *Condition = getConditionFromTerminator(TI); | |||
1161 | assert(Condition && "No condition for Terminator")((Condition && "No condition for Terminator") ? static_cast <void> (0) : __assert_fail ("Condition && \"No condition for Terminator\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1161, __PRETTY_FUNCTION__)); | |||
1162 | ||||
1163 | return buildConditionSets(S, Condition, TI, L, Domain, ConditionSets); | |||
1164 | } | |||
1165 | ||||
1166 | void ScopStmt::buildDomain() { | |||
1167 | isl_id *Id; | |||
1168 | ||||
1169 | Id = isl_id_alloc(getIslCtx(), getBaseName(), this); | |||
1170 | ||||
1171 | Domain = getParent()->getDomainConditions(this); | |||
1172 | Domain = isl_set_set_tuple_id(Domain, Id); | |||
1173 | } | |||
1174 | ||||
1175 | void ScopStmt::deriveAssumptionsFromGEP(GetElementPtrInst *GEP) { | |||
1176 | isl_ctx *Ctx = Parent.getIslCtx(); | |||
1177 | isl_local_space *LSpace = isl_local_space_from_space(getDomainSpace()); | |||
1178 | Type *Ty = GEP->getPointerOperandType(); | |||
1179 | ScalarEvolution &SE = *Parent.getSE(); | |||
1180 | ScopDetection &SD = Parent.getSD(); | |||
1181 | ||||
1182 | // The set of loads that are required to be invariant. | |||
1183 | auto &ScopRIL = *SD.getRequiredInvariantLoads(&Parent.getRegion()); | |||
1184 | ||||
1185 | std::vector<const SCEV *> Subscripts; | |||
1186 | std::vector<int> Sizes; | |||
1187 | ||||
1188 | std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, SE); | |||
1189 | ||||
1190 | if (auto *PtrTy = dyn_cast<PointerType>(Ty)) { | |||
1191 | Ty = PtrTy->getElementType(); | |||
1192 | } | |||
1193 | ||||
1194 | int IndexOffset = Subscripts.size() - Sizes.size(); | |||
1195 | ||||
1196 | assert(IndexOffset <= 1 && "Unexpected large index offset")((IndexOffset <= 1 && "Unexpected large index offset" ) ? static_cast<void> (0) : __assert_fail ("IndexOffset <= 1 && \"Unexpected large index offset\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1196, __PRETTY_FUNCTION__)); | |||
1197 | ||||
1198 | for (size_t i = 0; i < Sizes.size(); i++) { | |||
1199 | auto Expr = Subscripts[i + IndexOffset]; | |||
1200 | auto Size = Sizes[i]; | |||
1201 | ||||
1202 | InvariantLoadsSetTy AccessILS; | |||
1203 | if (!isAffineExpr(&Parent.getRegion(), Expr, SE, nullptr, &AccessILS)) | |||
1204 | continue; | |||
1205 | ||||
1206 | bool NonAffine = false; | |||
1207 | for (LoadInst *LInst : AccessILS) | |||
1208 | if (!ScopRIL.count(LInst)) | |||
1209 | NonAffine = true; | |||
1210 | ||||
1211 | if (NonAffine) | |||
1212 | continue; | |||
1213 | ||||
1214 | isl_pw_aff *AccessOffset = getPwAff(Expr); | |||
1215 | AccessOffset = | |||
1216 | isl_pw_aff_set_tuple_id(AccessOffset, isl_dim_in, getDomainId()); | |||
1217 | ||||
1218 | isl_pw_aff *DimSize = isl_pw_aff_from_aff(isl_aff_val_on_domain( | |||
1219 | isl_local_space_copy(LSpace), isl_val_int_from_si(Ctx, Size))); | |||
1220 | ||||
1221 | isl_set *OutOfBound = isl_pw_aff_ge_set(AccessOffset, DimSize); | |||
1222 | OutOfBound = isl_set_intersect(getDomain(), OutOfBound); | |||
1223 | OutOfBound = isl_set_params(OutOfBound); | |||
1224 | isl_set *InBound = isl_set_complement(OutOfBound); | |||
1225 | isl_set *Executed = isl_set_params(getDomain()); | |||
1226 | ||||
1227 | // A => B == !A or B | |||
1228 | isl_set *InBoundIfExecuted = | |||
1229 | isl_set_union(isl_set_complement(Executed), InBound); | |||
1230 | ||||
1231 | InBoundIfExecuted = isl_set_coalesce(InBoundIfExecuted); | |||
1232 | Parent.addAssumption(INBOUNDS, InBoundIfExecuted, GEP->getDebugLoc()); | |||
1233 | } | |||
1234 | ||||
1235 | isl_local_space_free(LSpace); | |||
1236 | } | |||
1237 | ||||
1238 | void ScopStmt::deriveAssumptions(BasicBlock *Block) { | |||
1239 | for (Instruction &Inst : *Block) | |||
1240 | if (auto *GEP = dyn_cast<GetElementPtrInst>(&Inst)) | |||
1241 | deriveAssumptionsFromGEP(GEP); | |||
1242 | } | |||
1243 | ||||
1244 | void ScopStmt::collectSurroundingLoops() { | |||
1245 | for (unsigned u = 0, e = isl_set_n_dim(Domain); u < e; u++) { | |||
1246 | isl_id *DimId = isl_set_get_dim_id(Domain, isl_dim_set, u); | |||
1247 | NestLoops.push_back(static_cast<Loop *>(isl_id_get_user(DimId))); | |||
1248 | isl_id_free(DimId); | |||
1249 | } | |||
1250 | } | |||
1251 | ||||
1252 | ScopStmt::ScopStmt(Scop &parent, Region &R) | |||
1253 | : Parent(parent), Domain(nullptr), BB(nullptr), R(&R), Build(nullptr) { | |||
1254 | ||||
1255 | BaseName = getIslCompatibleName("Stmt_", R.getNameStr(), ""); | |||
1256 | } | |||
1257 | ||||
1258 | ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb) | |||
1259 | : Parent(parent), Domain(nullptr), BB(&bb), R(nullptr), Build(nullptr) { | |||
1260 | ||||
1261 | BaseName = getIslCompatibleName("Stmt_", &bb, ""); | |||
1262 | } | |||
1263 | ||||
1264 | void ScopStmt::init() { | |||
1265 | assert(!Domain && "init must be called only once")((!Domain && "init must be called only once") ? static_cast <void> (0) : __assert_fail ("!Domain && \"init must be called only once\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1265, __PRETTY_FUNCTION__)); | |||
1266 | ||||
1267 | buildDomain(); | |||
1268 | collectSurroundingLoops(); | |||
1269 | buildAccessRelations(); | |||
1270 | ||||
1271 | if (BB) { | |||
1272 | deriveAssumptions(BB); | |||
1273 | } else { | |||
1274 | for (BasicBlock *Block : R->blocks()) { | |||
1275 | deriveAssumptions(Block); | |||
1276 | } | |||
1277 | } | |||
1278 | ||||
1279 | if (DetectReductions) | |||
1280 | checkForReductions(); | |||
1281 | } | |||
1282 | ||||
1283 | /// @brief Collect loads which might form a reduction chain with @p StoreMA | |||
1284 | /// | |||
1285 | /// Check if the stored value for @p StoreMA is a binary operator with one or | |||
1286 | /// two loads as operands. If the binary operand is commutative & associative, | |||
1287 | /// used only once (by @p StoreMA) and its load operands are also used only | |||
1288 | /// once, we have found a possible reduction chain. It starts at an operand | |||
1289 | /// load and includes the binary operator and @p StoreMA. | |||
1290 | /// | |||
1291 | /// Note: We allow only one use to ensure the load and binary operator cannot | |||
1292 | /// escape this block or into any other store except @p StoreMA. | |||
1293 | void ScopStmt::collectCandiateReductionLoads( | |||
1294 | MemoryAccess *StoreMA, SmallVectorImpl<MemoryAccess *> &Loads) { | |||
1295 | auto *Store = dyn_cast<StoreInst>(StoreMA->getAccessInstruction()); | |||
1296 | if (!Store) | |||
1297 | return; | |||
1298 | ||||
1299 | // Skip if there is not one binary operator between the load and the store | |||
1300 | auto *BinOp = dyn_cast<BinaryOperator>(Store->getValueOperand()); | |||
1301 | if (!BinOp) | |||
1302 | return; | |||
1303 | ||||
1304 | // Skip if the binary operators has multiple uses | |||
1305 | if (BinOp->getNumUses() != 1) | |||
1306 | return; | |||
1307 | ||||
1308 | // Skip if the opcode of the binary operator is not commutative/associative | |||
1309 | if (!BinOp->isCommutative() || !BinOp->isAssociative()) | |||
1310 | return; | |||
1311 | ||||
1312 | // Skip if the binary operator is outside the current SCoP | |||
1313 | if (BinOp->getParent() != Store->getParent()) | |||
1314 | return; | |||
1315 | ||||
1316 | // Skip if it is a multiplicative reduction and we disabled them | |||
1317 | if (DisableMultiplicativeReductions && | |||
1318 | (BinOp->getOpcode() == Instruction::Mul || | |||
1319 | BinOp->getOpcode() == Instruction::FMul)) | |||
1320 | return; | |||
1321 | ||||
1322 | // Check the binary operator operands for a candidate load | |||
1323 | auto *PossibleLoad0 = dyn_cast<LoadInst>(BinOp->getOperand(0)); | |||
1324 | auto *PossibleLoad1 = dyn_cast<LoadInst>(BinOp->getOperand(1)); | |||
1325 | if (!PossibleLoad0 && !PossibleLoad1) | |||
1326 | return; | |||
1327 | ||||
1328 | // A load is only a candidate if it cannot escape (thus has only this use) | |||
1329 | if (PossibleLoad0 && PossibleLoad0->getNumUses() == 1) | |||
1330 | if (PossibleLoad0->getParent() == Store->getParent()) | |||
1331 | Loads.push_back(&getArrayAccessFor(PossibleLoad0)); | |||
1332 | if (PossibleLoad1 && PossibleLoad1->getNumUses() == 1) | |||
1333 | if (PossibleLoad1->getParent() == Store->getParent()) | |||
1334 | Loads.push_back(&getArrayAccessFor(PossibleLoad1)); | |||
1335 | } | |||
1336 | ||||
1337 | /// @brief Check for reductions in this ScopStmt | |||
1338 | /// | |||
1339 | /// Iterate over all store memory accesses and check for valid binary reduction | |||
1340 | /// like chains. For all candidates we check if they have the same base address | |||
1341 | /// and there are no other accesses which overlap with them. The base address | |||
1342 | /// check rules out impossible reductions candidates early. The overlap check, | |||
1343 | /// together with the "only one user" check in collectCandiateReductionLoads, | |||
1344 | /// guarantees that none of the intermediate results will escape during | |||
1345 | /// execution of the loop nest. We basically check here that no other memory | |||
1346 | /// access can access the same memory as the potential reduction. | |||
1347 | void ScopStmt::checkForReductions() { | |||
1348 | SmallVector<MemoryAccess *, 2> Loads; | |||
1349 | SmallVector<std::pair<MemoryAccess *, MemoryAccess *>, 4> Candidates; | |||
1350 | ||||
1351 | // First collect candidate load-store reduction chains by iterating over all | |||
1352 | // stores and collecting possible reduction loads. | |||
1353 | for (MemoryAccess *StoreMA : MemAccs) { | |||
1354 | if (StoreMA->isRead()) | |||
1355 | continue; | |||
1356 | ||||
1357 | Loads.clear(); | |||
1358 | collectCandiateReductionLoads(StoreMA, Loads); | |||
1359 | for (MemoryAccess *LoadMA : Loads) | |||
1360 | Candidates.push_back(std::make_pair(LoadMA, StoreMA)); | |||
1361 | } | |||
1362 | ||||
1363 | // Then check each possible candidate pair. | |||
1364 | for (const auto &CandidatePair : Candidates) { | |||
1365 | bool Valid = true; | |||
1366 | isl_map *LoadAccs = CandidatePair.first->getAccessRelation(); | |||
1367 | isl_map *StoreAccs = CandidatePair.second->getAccessRelation(); | |||
1368 | ||||
1369 | // Skip those with obviously unequal base addresses. | |||
1370 | if (!isl_map_has_equal_space(LoadAccs, StoreAccs)) { | |||
1371 | isl_map_free(LoadAccs); | |||
1372 | isl_map_free(StoreAccs); | |||
1373 | continue; | |||
1374 | } | |||
1375 | ||||
1376 | // And check if the remaining for overlap with other memory accesses. | |||
1377 | isl_map *AllAccsRel = isl_map_union(LoadAccs, StoreAccs); | |||
1378 | AllAccsRel = isl_map_intersect_domain(AllAccsRel, getDomain()); | |||
1379 | isl_set *AllAccs = isl_map_range(AllAccsRel); | |||
1380 | ||||
1381 | for (MemoryAccess *MA : MemAccs) { | |||
1382 | if (MA == CandidatePair.first || MA == CandidatePair.second) | |||
1383 | continue; | |||
1384 | ||||
1385 | isl_map *AccRel = | |||
1386 | isl_map_intersect_domain(MA->getAccessRelation(), getDomain()); | |||
1387 | isl_set *Accs = isl_map_range(AccRel); | |||
1388 | ||||
1389 | if (isl_set_has_equal_space(AllAccs, Accs) || isl_set_free(Accs)) { | |||
1390 | isl_set *OverlapAccs = isl_set_intersect(Accs, isl_set_copy(AllAccs)); | |||
1391 | Valid = Valid && isl_set_is_empty(OverlapAccs); | |||
1392 | isl_set_free(OverlapAccs); | |||
1393 | } | |||
1394 | } | |||
1395 | ||||
1396 | isl_set_free(AllAccs); | |||
1397 | if (!Valid) | |||
1398 | continue; | |||
1399 | ||||
1400 | const LoadInst *Load = | |||
1401 | dyn_cast<const LoadInst>(CandidatePair.first->getAccessInstruction()); | |||
1402 | MemoryAccess::ReductionType RT = | |||
1403 | getReductionType(dyn_cast<BinaryOperator>(Load->user_back()), Load); | |||
1404 | ||||
1405 | // If no overlapping access was found we mark the load and store as | |||
1406 | // reduction like. | |||
1407 | CandidatePair.first->markAsReductionLike(RT); | |||
1408 | CandidatePair.second->markAsReductionLike(RT); | |||
1409 | } | |||
1410 | } | |||
1411 | ||||
1412 | std::string ScopStmt::getDomainStr() const { return stringFromIslObj(Domain); } | |||
1413 | ||||
1414 | std::string ScopStmt::getScheduleStr() const { | |||
1415 | auto *S = getSchedule(); | |||
1416 | auto Str = stringFromIslObj(S); | |||
1417 | isl_map_free(S); | |||
1418 | return Str; | |||
1419 | } | |||
1420 | ||||
1421 | unsigned ScopStmt::getNumParams() const { return Parent.getNumParams(); } | |||
1422 | ||||
1423 | unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); } | |||
1424 | ||||
1425 | const char *ScopStmt::getBaseName() const { return BaseName.c_str(); } | |||
1426 | ||||
1427 | const Loop *ScopStmt::getLoopForDimension(unsigned Dimension) const { | |||
1428 | return NestLoops[Dimension]; | |||
1429 | } | |||
1430 | ||||
1431 | isl_ctx *ScopStmt::getIslCtx() const { return Parent.getIslCtx(); } | |||
1432 | ||||
1433 | __isl_give isl_set *ScopStmt::getDomain() const { return isl_set_copy(Domain); } | |||
1434 | ||||
1435 | __isl_give isl_space *ScopStmt::getDomainSpace() const { | |||
1436 | return isl_set_get_space(Domain); | |||
1437 | } | |||
1438 | ||||
1439 | __isl_give isl_id *ScopStmt::getDomainId() const { | |||
1440 | return isl_set_get_tuple_id(Domain); | |||
1441 | } | |||
1442 | ||||
1443 | ScopStmt::~ScopStmt() { isl_set_free(Domain); } | |||
1444 | ||||
1445 | void ScopStmt::print(raw_ostream &OS) const { | |||
1446 | OS << "\t" << getBaseName() << "\n"; | |||
1447 | OS.indent(12) << "Domain :=\n"; | |||
1448 | ||||
1449 | if (Domain) { | |||
1450 | OS.indent(16) << getDomainStr() << ";\n"; | |||
1451 | } else | |||
1452 | OS.indent(16) << "n/a\n"; | |||
1453 | ||||
1454 | OS.indent(12) << "Schedule :=\n"; | |||
1455 | ||||
1456 | if (Domain) { | |||
1457 | OS.indent(16) << getScheduleStr() << ";\n"; | |||
1458 | } else | |||
1459 | OS.indent(16) << "n/a\n"; | |||
1460 | ||||
1461 | for (MemoryAccess *Access : MemAccs) | |||
1462 | Access->print(OS); | |||
1463 | } | |||
1464 | ||||
1465 | void ScopStmt::dump() const { print(dbgs()); } | |||
1466 | ||||
1467 | void ScopStmt::removeMemoryAccesses(MemoryAccessList &InvMAs) { | |||
1468 | // Remove all memory accesses in @p InvMAs from this statement | |||
1469 | // together with all scalar accesses that were caused by them. | |||
1470 | for (MemoryAccess *MA : InvMAs) { | |||
1471 | auto Predicate = [&](MemoryAccess *Acc) { | |||
1472 | return Acc->getAccessInstruction() == MA->getAccessInstruction(); | |||
1473 | }; | |||
1474 | MemAccs.erase(std::remove_if(MemAccs.begin(), MemAccs.end(), Predicate), | |||
1475 | MemAccs.end()); | |||
1476 | InstructionToAccess.erase(MA->getAccessInstruction()); | |||
1477 | } | |||
1478 | } | |||
1479 | ||||
1480 | //===----------------------------------------------------------------------===// | |||
1481 | /// Scop class implement | |||
1482 | ||||
1483 | void Scop::setContext(__isl_take isl_set *NewContext) { | |||
1484 | NewContext = isl_set_align_params(NewContext, isl_set_get_space(Context)); | |||
1485 | isl_set_free(Context); | |||
1486 | Context = NewContext; | |||
1487 | } | |||
1488 | ||||
1489 | /// @brief Remap parameter values but keep AddRecs valid wrt. invariant loads. | |||
1490 | struct SCEVSensitiveParameterRewriter | |||
1491 | : public SCEVVisitor<SCEVSensitiveParameterRewriter, const SCEV *> { | |||
1492 | ValueToValueMap &VMap; | |||
1493 | ScalarEvolution &SE; | |||
1494 | ||||
1495 | public: | |||
1496 | SCEVSensitiveParameterRewriter(ValueToValueMap &VMap, ScalarEvolution &SE) | |||
1497 | : VMap(VMap), SE(SE) {} | |||
1498 | ||||
1499 | static const SCEV *rewrite(const SCEV *E, ScalarEvolution &SE, | |||
1500 | ValueToValueMap &VMap) { | |||
1501 | SCEVSensitiveParameterRewriter SSPR(VMap, SE); | |||
1502 | return SSPR.visit(E); | |||
1503 | } | |||
1504 | ||||
1505 | const SCEV *visit(const SCEV *E) { | |||
1506 | return SCEVVisitor<SCEVSensitiveParameterRewriter, const SCEV *>::visit(E); | |||
1507 | } | |||
1508 | ||||
1509 | const SCEV *visitConstant(const SCEVConstant *E) { return E; } | |||
1510 | ||||
1511 | const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) { | |||
1512 | return SE.getTruncateExpr(visit(E->getOperand()), E->getType()); | |||
1513 | } | |||
1514 | ||||
1515 | const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *E) { | |||
1516 | return SE.getZeroExtendExpr(visit(E->getOperand()), E->getType()); | |||
1517 | } | |||
1518 | ||||
1519 | const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *E) { | |||
1520 | return SE.getSignExtendExpr(visit(E->getOperand()), E->getType()); | |||
1521 | } | |||
1522 | ||||
1523 | const SCEV *visitAddExpr(const SCEVAddExpr *E) { | |||
1524 | SmallVector<const SCEV *, 4> Operands; | |||
1525 | for (int i = 0, e = E->getNumOperands(); i < e; ++i) | |||
1526 | Operands.push_back(visit(E->getOperand(i))); | |||
1527 | return SE.getAddExpr(Operands); | |||
1528 | } | |||
1529 | ||||
1530 | const SCEV *visitMulExpr(const SCEVMulExpr *E) { | |||
1531 | SmallVector<const SCEV *, 4> Operands; | |||
1532 | for (int i = 0, e = E->getNumOperands(); i < e; ++i) | |||
1533 | Operands.push_back(visit(E->getOperand(i))); | |||
1534 | return SE.getMulExpr(Operands); | |||
1535 | } | |||
1536 | ||||
1537 | const SCEV *visitSMaxExpr(const SCEVSMaxExpr *E) { | |||
1538 | SmallVector<const SCEV *, 4> Operands; | |||
1539 | for (int i = 0, e = E->getNumOperands(); i < e; ++i) | |||
1540 | Operands.push_back(visit(E->getOperand(i))); | |||
1541 | return SE.getSMaxExpr(Operands); | |||
1542 | } | |||
1543 | ||||
1544 | const SCEV *visitUMaxExpr(const SCEVUMaxExpr *E) { | |||
1545 | SmallVector<const SCEV *, 4> Operands; | |||
1546 | for (int i = 0, e = E->getNumOperands(); i < e; ++i) | |||
1547 | Operands.push_back(visit(E->getOperand(i))); | |||
1548 | return SE.getUMaxExpr(Operands); | |||
1549 | } | |||
1550 | ||||
1551 | const SCEV *visitUDivExpr(const SCEVUDivExpr *E) { | |||
1552 | return SE.getUDivExpr(visit(E->getLHS()), visit(E->getRHS())); | |||
1553 | } | |||
1554 | ||||
1555 | const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) { | |||
1556 | auto *Start = visit(E->getStart()); | |||
1557 | auto *AddRec = SE.getAddRecExpr(SE.getConstant(E->getType(), 0), | |||
1558 | visit(E->getStepRecurrence(SE)), | |||
1559 | E->getLoop(), SCEV::FlagAnyWrap); | |||
1560 | return SE.getAddExpr(Start, AddRec); | |||
1561 | } | |||
1562 | ||||
1563 | const SCEV *visitUnknown(const SCEVUnknown *E) { | |||
1564 | if (auto *NewValue = VMap.lookup(E->getValue())) | |||
1565 | return SE.getUnknown(NewValue); | |||
1566 | return E; | |||
1567 | } | |||
1568 | }; | |||
1569 | ||||
1570 | const SCEV *Scop::getRepresentingInvariantLoadSCEV(const SCEV *S) { | |||
1571 | return SCEVSensitiveParameterRewriter::rewrite(S, *SE, InvEquivClassVMap); | |||
1572 | } | |||
1573 | ||||
1574 | void Scop::addParams(std::vector<const SCEV *> NewParameters) { | |||
1575 | for (const SCEV *Parameter : NewParameters) { | |||
1576 | Parameter = extractConstantFactor(Parameter, *SE).second; | |||
1577 | ||||
1578 | // Normalize the SCEV to get the representing element for an invariant load. | |||
1579 | Parameter = getRepresentingInvariantLoadSCEV(Parameter); | |||
1580 | ||||
1581 | if (ParameterIds.find(Parameter) != ParameterIds.end()) | |||
1582 | continue; | |||
1583 | ||||
1584 | int dimension = Parameters.size(); | |||
1585 | ||||
1586 | Parameters.push_back(Parameter); | |||
1587 | ParameterIds[Parameter] = dimension; | |||
1588 | } | |||
1589 | } | |||
1590 | ||||
1591 | __isl_give isl_id *Scop::getIdForParam(const SCEV *Parameter) { | |||
1592 | // Normalize the SCEV to get the representing element for an invariant load. | |||
1593 | Parameter = getRepresentingInvariantLoadSCEV(Parameter); | |||
1594 | ||||
1595 | ParamIdType::const_iterator IdIter = ParameterIds.find(Parameter); | |||
1596 | ||||
1597 | if (IdIter == ParameterIds.end()) | |||
1598 | return nullptr; | |||
1599 | ||||
1600 | std::string ParameterName; | |||
1601 | ||||
1602 | ParameterName = "p_" + utostr_32(IdIter->second); | |||
1603 | ||||
1604 | if (const SCEVUnknown *ValueParameter = dyn_cast<SCEVUnknown>(Parameter)) { | |||
1605 | Value *Val = ValueParameter->getValue(); | |||
1606 | ||||
1607 | // If this parameter references a specific Value and this value has a name | |||
1608 | // we use this name as it is likely to be unique and more useful than just | |||
1609 | // a number. | |||
1610 | if (Val->hasName()) | |||
1611 | ParameterName = Val->getName(); | |||
1612 | else if (LoadInst *LI = dyn_cast<LoadInst>(Val)) { | |||
1613 | auto LoadOrigin = LI->getPointerOperand()->stripInBoundsOffsets(); | |||
1614 | if (LoadOrigin->hasName()) { | |||
1615 | ParameterName += "_loaded_from_"; | |||
1616 | ParameterName += | |||
1617 | LI->getPointerOperand()->stripInBoundsOffsets()->getName(); | |||
1618 | } | |||
1619 | } | |||
1620 | } | |||
1621 | ||||
1622 | return isl_id_alloc(getIslCtx(), ParameterName.c_str(), | |||
1623 | const_cast<void *>((const void *)Parameter)); | |||
1624 | } | |||
1625 | ||||
1626 | isl_set *Scop::addNonEmptyDomainConstraints(isl_set *C) const { | |||
1627 | isl_set *DomainContext = isl_union_set_params(getDomains()); | |||
1628 | return isl_set_intersect_params(C, DomainContext); | |||
1629 | } | |||
1630 | ||||
1631 | void Scop::buildBoundaryContext() { | |||
1632 | if (IgnoreIntegerWrapping) { | |||
1633 | BoundaryContext = isl_set_universe(getParamSpace()); | |||
1634 | return; | |||
1635 | } | |||
1636 | ||||
1637 | BoundaryContext = Affinator.getWrappingContext(); | |||
1638 | ||||
1639 | // The isl_set_complement operation used to create the boundary context | |||
1640 | // can possibly become very expensive. We bound the compile time of | |||
1641 | // this operation by setting a compute out. | |||
1642 | // | |||
1643 | // TODO: We can probably get around using isl_set_complement and directly | |||
1644 | // AST generate BoundaryContext. | |||
1645 | long MaxOpsOld = isl_ctx_get_max_operations(getIslCtx()); | |||
1646 | isl_ctx_reset_operations(getIslCtx()); | |||
1647 | isl_ctx_set_max_operations(getIslCtx(), 300000); | |||
1648 | isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_CONTINUE1); | |||
1649 | ||||
1650 | BoundaryContext = isl_set_complement(BoundaryContext); | |||
1651 | ||||
1652 | if (isl_ctx_last_error(getIslCtx()) == isl_error_quota) { | |||
1653 | isl_set_free(BoundaryContext); | |||
1654 | BoundaryContext = isl_set_empty(getParamSpace()); | |||
1655 | } | |||
1656 | ||||
1657 | isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_ABORT2); | |||
1658 | isl_ctx_reset_operations(getIslCtx()); | |||
1659 | isl_ctx_set_max_operations(getIslCtx(), MaxOpsOld); | |||
1660 | BoundaryContext = isl_set_gist_params(BoundaryContext, getContext()); | |||
1661 | trackAssumption(WRAPPING, BoundaryContext, DebugLoc()); | |||
1662 | } | |||
1663 | ||||
1664 | void Scop::addUserAssumptions(AssumptionCache &AC) { | |||
1665 | auto *R = &getRegion(); | |||
1666 | auto &F = *R->getEntry()->getParent(); | |||
1667 | for (auto &Assumption : AC.assumptions()) { | |||
1668 | auto *CI = dyn_cast_or_null<CallInst>(Assumption); | |||
1669 | if (!CI || CI->getNumArgOperands() != 1) | |||
1670 | continue; | |||
1671 | if (!DT.dominates(CI->getParent(), R->getEntry())) | |||
1672 | continue; | |||
1673 | ||||
1674 | auto *Val = CI->getArgOperand(0); | |||
1675 | std::vector<const SCEV *> Params; | |||
1676 | if (!isAffineParamConstraint(Val, R, *SE, Params)) { | |||
1677 | emitOptimizationRemarkAnalysis(F.getContext(), DEBUG_TYPE"polly-scops", F, | |||
1678 | CI->getDebugLoc(), | |||
1679 | "Non-affine user assumption ignored."); | |||
1680 | continue; | |||
1681 | } | |||
1682 | ||||
1683 | addParams(Params); | |||
1684 | ||||
1685 | auto *L = LI.getLoopFor(CI->getParent()); | |||
1686 | SmallVector<isl_set *, 2> ConditionSets; | |||
1687 | buildConditionSets(*this, Val, nullptr, L, Context, ConditionSets); | |||
1688 | assert(ConditionSets.size() == 2)((ConditionSets.size() == 2) ? static_cast<void> (0) : __assert_fail ("ConditionSets.size() == 2", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1688, __PRETTY_FUNCTION__)); | |||
1689 | isl_set_free(ConditionSets[1]); | |||
1690 | ||||
1691 | auto *AssumptionCtx = ConditionSets[0]; | |||
1692 | emitOptimizationRemarkAnalysis( | |||
1693 | F.getContext(), DEBUG_TYPE"polly-scops", F, CI->getDebugLoc(), | |||
1694 | "Use user assumption: " + stringFromIslObj(AssumptionCtx)); | |||
1695 | Context = isl_set_intersect(Context, AssumptionCtx); | |||
1696 | } | |||
1697 | } | |||
1698 | ||||
1699 | void Scop::addUserContext() { | |||
1700 | if (UserContextStr.empty()) | |||
1701 | return; | |||
1702 | ||||
1703 | isl_set *UserContext = isl_set_read_from_str(IslCtx, UserContextStr.c_str()); | |||
1704 | isl_space *Space = getParamSpace(); | |||
1705 | if (isl_space_dim(Space, isl_dim_param) != | |||
1706 | isl_set_dim(UserContext, isl_dim_param)) { | |||
1707 | auto SpaceStr = isl_space_to_str(Space); | |||
1708 | errs() << "Error: the context provided in -polly-context has not the same " | |||
1709 | << "number of dimensions than the computed context. Due to this " | |||
1710 | << "mismatch, the -polly-context option is ignored. Please provide " | |||
1711 | << "the context in the parameter space: " << SpaceStr << ".\n"; | |||
1712 | free(SpaceStr); | |||
1713 | isl_set_free(UserContext); | |||
1714 | isl_space_free(Space); | |||
1715 | return; | |||
1716 | } | |||
1717 | ||||
1718 | for (unsigned i = 0; i < isl_space_dim(Space, isl_dim_param); i++) { | |||
1719 | auto NameContext = isl_set_get_dim_name(Context, isl_dim_param, i); | |||
1720 | auto NameUserContext = isl_set_get_dim_name(UserContext, isl_dim_param, i); | |||
1721 | ||||
1722 | if (strcmp(NameContext, NameUserContext) != 0) { | |||
1723 | auto SpaceStr = isl_space_to_str(Space); | |||
1724 | errs() << "Error: the name of dimension " << i | |||
1725 | << " provided in -polly-context " | |||
1726 | << "is '" << NameUserContext << "', but the name in the computed " | |||
1727 | << "context is '" << NameContext | |||
1728 | << "'. Due to this name mismatch, " | |||
1729 | << "the -polly-context option is ignored. Please provide " | |||
1730 | << "the context in the parameter space: " << SpaceStr << ".\n"; | |||
1731 | free(SpaceStr); | |||
1732 | isl_set_free(UserContext); | |||
1733 | isl_space_free(Space); | |||
1734 | return; | |||
1735 | } | |||
1736 | ||||
1737 | UserContext = | |||
1738 | isl_set_set_dim_id(UserContext, isl_dim_param, i, | |||
1739 | isl_space_get_dim_id(Space, isl_dim_param, i)); | |||
1740 | } | |||
1741 | ||||
1742 | Context = isl_set_intersect(Context, UserContext); | |||
1743 | isl_space_free(Space); | |||
1744 | } | |||
1745 | ||||
1746 | void Scop::buildInvariantEquivalenceClasses() { | |||
1747 | DenseMap<const SCEV *, LoadInst *> EquivClasses; | |||
1748 | ||||
1749 | const InvariantLoadsSetTy &RIL = *SD.getRequiredInvariantLoads(&getRegion()); | |||
1750 | for (LoadInst *LInst : RIL) { | |||
1751 | const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand()); | |||
1752 | ||||
1753 | LoadInst *&ClassRep = EquivClasses[PointerSCEV]; | |||
1754 | if (ClassRep) { | |||
1755 | InvEquivClassVMap[LInst] = ClassRep; | |||
1756 | continue; | |||
1757 | } | |||
1758 | ||||
1759 | ClassRep = LInst; | |||
1760 | InvariantEquivClasses.emplace_back(PointerSCEV, MemoryAccessList(), | |||
1761 | nullptr); | |||
1762 | } | |||
1763 | } | |||
1764 | ||||
1765 | void Scop::buildContext() { | |||
1766 | isl_space *Space = isl_space_params_alloc(IslCtx, 0); | |||
1767 | Context = isl_set_universe(isl_space_copy(Space)); | |||
1768 | AssumedContext = isl_set_universe(Space); | |||
1769 | } | |||
1770 | ||||
1771 | void Scop::addParameterBounds() { | |||
1772 | for (const auto &ParamID : ParameterIds) { | |||
1773 | int dim = ParamID.second; | |||
1774 | ||||
1775 | ConstantRange SRange = SE->getSignedRange(ParamID.first); | |||
1776 | ||||
1777 | Context = addRangeBoundsToSet(Context, SRange, dim, isl_dim_param); | |||
1778 | } | |||
1779 | } | |||
1780 | ||||
1781 | void Scop::realignParams() { | |||
1782 | // Add all parameters into a common model. | |||
1783 | isl_space *Space = isl_space_params_alloc(IslCtx, ParameterIds.size()); | |||
1784 | ||||
1785 | for (const auto &ParamID : ParameterIds) { | |||
1786 | const SCEV *Parameter = ParamID.first; | |||
1787 | isl_id *id = getIdForParam(Parameter); | |||
1788 | Space = isl_space_set_dim_id(Space, isl_dim_param, ParamID.second, id); | |||
1789 | } | |||
1790 | ||||
1791 | // Align the parameters of all data structures to the model. | |||
1792 | Context = isl_set_align_params(Context, Space); | |||
1793 | ||||
1794 | for (ScopStmt &Stmt : *this) | |||
1795 | Stmt.realignParams(); | |||
1796 | } | |||
1797 | ||||
1798 | static __isl_give isl_set * | |||
1799 | simplifyAssumptionContext(__isl_take isl_set *AssumptionContext, | |||
1800 | const Scop &S) { | |||
1801 | // If we modelt all blocks in the SCoP that have side effects we can simplify | |||
1802 | // the context with the constraints that are needed for anything to be | |||
1803 | // executed at all. However, if we have error blocks in the SCoP we already | |||
1804 | // assumed some parameter combinations cannot occure and removed them from the | |||
1805 | // domains, thus we cannot use the remaining domain to simplify the | |||
1806 | // assumptions. | |||
1807 | if (!S.hasErrorBlock()) { | |||
1808 | isl_set *DomainParameters = isl_union_set_params(S.getDomains()); | |||
1809 | AssumptionContext = | |||
1810 | isl_set_gist_params(AssumptionContext, DomainParameters); | |||
1811 | } | |||
1812 | ||||
1813 | AssumptionContext = isl_set_gist_params(AssumptionContext, S.getContext()); | |||
1814 | return AssumptionContext; | |||
1815 | } | |||
1816 | ||||
1817 | void Scop::simplifyContexts() { | |||
1818 | // The parameter constraints of the iteration domains give us a set of | |||
1819 | // constraints that need to hold for all cases where at least a single | |||
1820 | // statement iteration is executed in the whole scop. We now simplify the | |||
1821 | // assumed context under the assumption that such constraints hold and at | |||
1822 | // least a single statement iteration is executed. For cases where no | |||
1823 | // statement instances are executed, the assumptions we have taken about | |||
1824 | // the executed code do not matter and can be changed. | |||
1825 | // | |||
1826 | // WARNING: This only holds if the assumptions we have taken do not reduce | |||
1827 | // the set of statement instances that are executed. Otherwise we | |||
1828 | // may run into a case where the iteration domains suggest that | |||
1829 | // for a certain set of parameter constraints no code is executed, | |||
1830 | // but in the original program some computation would have been | |||
1831 | // performed. In such a case, modifying the run-time conditions and | |||
1832 | // possibly influencing the run-time check may cause certain scops | |||
1833 | // to not be executed. | |||
1834 | // | |||
1835 | // Example: | |||
1836 | // | |||
1837 | // When delinearizing the following code: | |||
1838 | // | |||
1839 | // for (long i = 0; i < 100; i++) | |||
1840 | // for (long j = 0; j < m; j++) | |||
1841 | // A[i+p][j] = 1.0; | |||
1842 | // | |||
1843 | // we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as | |||
1844 | // otherwise we would access out of bound data. Now, knowing that code is | |||
1845 | // only executed for the case m >= 0, it is sufficient to assume p >= 0. | |||
1846 | AssumedContext = simplifyAssumptionContext(AssumedContext, *this); | |||
1847 | BoundaryContext = simplifyAssumptionContext(BoundaryContext, *this); | |||
1848 | } | |||
1849 | ||||
1850 | /// @brief Add the minimal/maximal access in @p Set to @p User. | |||
1851 | static isl_stat buildMinMaxAccess(__isl_take isl_set *Set, void *User) { | |||
1852 | Scop::MinMaxVectorTy *MinMaxAccesses = (Scop::MinMaxVectorTy *)User; | |||
1853 | isl_pw_multi_aff *MinPMA, *MaxPMA; | |||
1854 | isl_pw_aff *LastDimAff; | |||
1855 | isl_aff *OneAff; | |||
1856 | unsigned Pos; | |||
1857 | ||||
1858 | // Restrict the number of parameters involved in the access as the lexmin/ | |||
1859 | // lexmax computation will take too long if this number is high. | |||
1860 | // | |||
1861 | // Experiments with a simple test case using an i7 4800MQ: | |||
1862 | // | |||
1863 | // #Parameters involved | Time (in sec) | |||
1864 | // 6 | 0.01 | |||
1865 | // 7 | 0.04 | |||
1866 | // 8 | 0.12 | |||
1867 | // 9 | 0.40 | |||
1868 | // 10 | 1.54 | |||
1869 | // 11 | 6.78 | |||
1870 | // 12 | 30.38 | |||
1871 | // | |||
1872 | if (isl_set_n_param(Set) > RunTimeChecksMaxParameters) { | |||
1873 | unsigned InvolvedParams = 0; | |||
1874 | for (unsigned u = 0, e = isl_set_n_param(Set); u < e; u++) | |||
1875 | if (isl_set_involves_dims(Set, isl_dim_param, u, 1)) | |||
1876 | InvolvedParams++; | |||
1877 | ||||
1878 | if (InvolvedParams > RunTimeChecksMaxParameters) { | |||
1879 | isl_set_free(Set); | |||
1880 | return isl_stat_error; | |||
1881 | } | |||
1882 | } | |||
1883 | ||||
1884 | Set = isl_set_remove_divs(Set); | |||
1885 | ||||
1886 | MinPMA = isl_set_lexmin_pw_multi_aff(isl_set_copy(Set)); | |||
1887 | MaxPMA = isl_set_lexmax_pw_multi_aff(isl_set_copy(Set)); | |||
1888 | ||||
1889 | MinPMA = isl_pw_multi_aff_coalesce(MinPMA); | |||
1890 | MaxPMA = isl_pw_multi_aff_coalesce(MaxPMA); | |||
1891 | ||||
1892 | // Adjust the last dimension of the maximal access by one as we want to | |||
1893 | // enclose the accessed memory region by MinPMA and MaxPMA. The pointer | |||
1894 | // we test during code generation might now point after the end of the | |||
1895 | // allocated array but we will never dereference it anyway. | |||
1896 | assert(isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) &&((isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) && "Assumed at least one output dimension" ) ? static_cast<void> (0) : __assert_fail ("isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) && \"Assumed at least one output dimension\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1897, __PRETTY_FUNCTION__)) | |||
1897 | "Assumed at least one output dimension")((isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) && "Assumed at least one output dimension" ) ? static_cast<void> (0) : __assert_fail ("isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) && \"Assumed at least one output dimension\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1897, __PRETTY_FUNCTION__)); | |||
1898 | Pos = isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) - 1; | |||
1899 | LastDimAff = isl_pw_multi_aff_get_pw_aff(MaxPMA, Pos); | |||
1900 | OneAff = isl_aff_zero_on_domain( | |||
1901 | isl_local_space_from_space(isl_pw_aff_get_domain_space(LastDimAff))); | |||
1902 | OneAff = isl_aff_add_constant_si(OneAff, 1); | |||
1903 | LastDimAff = isl_pw_aff_add(LastDimAff, isl_pw_aff_from_aff(OneAff)); | |||
1904 | MaxPMA = isl_pw_multi_aff_set_pw_aff(MaxPMA, Pos, LastDimAff); | |||
1905 | ||||
1906 | MinMaxAccesses->push_back(std::make_pair(MinPMA, MaxPMA)); | |||
1907 | ||||
1908 | isl_set_free(Set); | |||
1909 | return isl_stat_ok; | |||
1910 | } | |||
1911 | ||||
1912 | static __isl_give isl_set *getAccessDomain(MemoryAccess *MA) { | |||
1913 | isl_set *Domain = MA->getStatement()->getDomain(); | |||
1914 | Domain = isl_set_project_out(Domain, isl_dim_set, 0, isl_set_n_dim(Domain)); | |||
1915 | return isl_set_reset_tuple_id(Domain); | |||
1916 | } | |||
1917 | ||||
1918 | /// @brief Wrapper function to calculate minimal/maximal accesses to each array. | |||
1919 | static bool calculateMinMaxAccess(__isl_take isl_union_map *Accesses, | |||
1920 | __isl_take isl_union_set *Domains, | |||
1921 | Scop::MinMaxVectorTy &MinMaxAccesses) { | |||
1922 | ||||
1923 | Accesses = isl_union_map_intersect_domain(Accesses, Domains); | |||
1924 | isl_union_set *Locations = isl_union_map_range(Accesses); | |||
1925 | Locations = isl_union_set_coalesce(Locations); | |||
1926 | Locations = isl_union_set_detect_equalities(Locations); | |||
1927 | bool Valid = (0 == isl_union_set_foreach_set(Locations, buildMinMaxAccess, | |||
1928 | &MinMaxAccesses)); | |||
1929 | isl_union_set_free(Locations); | |||
1930 | return Valid; | |||
1931 | } | |||
1932 | ||||
1933 | /// @brief Helper to treat non-affine regions and basic blocks the same. | |||
1934 | /// | |||
1935 | ///{ | |||
1936 | ||||
1937 | /// @brief Return the block that is the representing block for @p RN. | |||
1938 | static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) { | |||
1939 | return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry() | |||
1940 | : RN->getNodeAs<BasicBlock>(); | |||
1941 | } | |||
1942 | ||||
1943 | /// @brief Return the @p idx'th block that is executed after @p RN. | |||
1944 | static inline BasicBlock * | |||
1945 | getRegionNodeSuccessor(RegionNode *RN, TerminatorInst *TI, unsigned idx) { | |||
1946 | if (RN->isSubRegion()) { | |||
1947 | assert(idx == 0)((idx == 0) ? static_cast<void> (0) : __assert_fail ("idx == 0" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 1947, __PRETTY_FUNCTION__)); | |||
1948 | return RN->getNodeAs<Region>()->getExit(); | |||
1949 | } | |||
1950 | return TI->getSuccessor(idx); | |||
1951 | } | |||
1952 | ||||
1953 | /// @brief Return the smallest loop surrounding @p RN. | |||
1954 | static inline Loop *getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) { | |||
1955 | if (!RN->isSubRegion()) | |||
1956 | return LI.getLoopFor(RN->getNodeAs<BasicBlock>()); | |||
1957 | ||||
1958 | Region *NonAffineSubRegion = RN->getNodeAs<Region>(); | |||
1959 | Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry()); | |||
1960 | while (L && NonAffineSubRegion->contains(L)) | |||
1961 | L = L->getParentLoop(); | |||
1962 | return L; | |||
1963 | } | |||
1964 | ||||
1965 | static inline unsigned getNumBlocksInRegionNode(RegionNode *RN) { | |||
1966 | if (!RN->isSubRegion()) | |||
1967 | return 1; | |||
1968 | ||||
1969 | unsigned NumBlocks = 0; | |||
1970 | Region *R = RN->getNodeAs<Region>(); | |||
1971 | for (auto BB : R->blocks()) { | |||
1972 | (void)BB; | |||
1973 | NumBlocks++; | |||
1974 | } | |||
1975 | return NumBlocks; | |||
1976 | } | |||
1977 | ||||
1978 | static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI, | |||
1979 | const DominatorTree &DT) { | |||
1980 | if (!RN->isSubRegion()) | |||
1981 | return isErrorBlock(*RN->getNodeAs<BasicBlock>(), R, LI, DT); | |||
1982 | for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks()) | |||
1983 | if (isErrorBlock(*BB, R, LI, DT)) | |||
1984 | return true; | |||
1985 | return false; | |||
1986 | } | |||
1987 | ||||
1988 | ///} | |||
1989 | ||||
1990 | static inline __isl_give isl_set *addDomainDimId(__isl_take isl_set *Domain, | |||
1991 | unsigned Dim, Loop *L) { | |||
1992 | Domain = isl_set_lower_bound_si(Domain, isl_dim_set, Dim, -1); | |||
1993 | isl_id *DimId = | |||
1994 | isl_id_alloc(isl_set_get_ctx(Domain), nullptr, static_cast<void *>(L)); | |||
1995 | return isl_set_set_dim_id(Domain, isl_dim_set, Dim, DimId); | |||
1996 | } | |||
1997 | ||||
1998 | isl_set *Scop::getDomainConditions(ScopStmt *Stmt) { | |||
1999 | BasicBlock *BB = Stmt->isBlockStmt() ? Stmt->getBasicBlock() | |||
2000 | : Stmt->getRegion()->getEntry(); | |||
2001 | return getDomainConditions(BB); | |||
2002 | } | |||
2003 | ||||
2004 | isl_set *Scop::getDomainConditions(BasicBlock *BB) { | |||
2005 | assert(DomainMap.count(BB) && "Requested BB did not have a domain")((DomainMap.count(BB) && "Requested BB did not have a domain" ) ? static_cast<void> (0) : __assert_fail ("DomainMap.count(BB) && \"Requested BB did not have a domain\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2005, __PRETTY_FUNCTION__)); | |||
2006 | return isl_set_copy(DomainMap[BB]); | |||
2007 | } | |||
2008 | ||||
2009 | void Scop::removeErrorBlockDomains() { | |||
2010 | auto removeDomains = [this](BasicBlock *Start) { | |||
2011 | auto BBNode = DT.getNode(Start); | |||
2012 | for (auto ErrorChild : depth_first(BBNode)) { | |||
2013 | auto ErrorChildBlock = ErrorChild->getBlock(); | |||
2014 | auto CurrentDomain = DomainMap[ErrorChildBlock]; | |||
2015 | auto Empty = isl_set_empty(isl_set_get_space(CurrentDomain)); | |||
2016 | DomainMap[ErrorChildBlock] = Empty; | |||
2017 | isl_set_free(CurrentDomain); | |||
2018 | } | |||
2019 | }; | |||
2020 | ||||
2021 | SmallVector<Region *, 4> Todo = {&R}; | |||
2022 | ||||
2023 | while (!Todo.empty()) { | |||
2024 | auto SubRegion = Todo.back(); | |||
2025 | Todo.pop_back(); | |||
2026 | ||||
2027 | if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) { | |||
2028 | for (auto &Child : *SubRegion) | |||
2029 | Todo.push_back(Child.get()); | |||
2030 | continue; | |||
2031 | } | |||
2032 | if (containsErrorBlock(SubRegion->getNode(), getRegion(), LI, DT)) | |||
2033 | removeDomains(SubRegion->getEntry()); | |||
2034 | } | |||
2035 | ||||
2036 | for (auto BB : R.blocks()) | |||
2037 | if (isErrorBlock(*BB, R, LI, DT)) | |||
2038 | removeDomains(BB); | |||
2039 | } | |||
2040 | ||||
2041 | void Scop::buildDomains(Region *R) { | |||
2042 | ||||
2043 | auto *EntryBB = R->getEntry(); | |||
2044 | int LD = getRelativeLoopDepth(LI.getLoopFor(EntryBB)); | |||
2045 | auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx(), 0, LD + 1)); | |||
2046 | ||||
2047 | Loop *L = LI.getLoopFor(EntryBB); | |||
2048 | while (LD-- >= 0) { | |||
2049 | S = addDomainDimId(S, LD + 1, L); | |||
2050 | L = L->getParentLoop(); | |||
2051 | } | |||
2052 | ||||
2053 | DomainMap[EntryBB] = S; | |||
2054 | ||||
2055 | if (SD.isNonAffineSubRegion(R, R)) | |||
2056 | return; | |||
2057 | ||||
2058 | buildDomainsWithBranchConstraints(R); | |||
2059 | propagateDomainConstraints(R); | |||
2060 | ||||
2061 | // Error blocks and blocks dominated by them have been assumed to never be | |||
2062 | // executed. Representing them in the Scop does not add any value. In fact, | |||
2063 | // it is likely to cause issues during construction of the ScopStmts. The | |||
2064 | // contents of error blocks have not been verfied to be expressible and | |||
2065 | // will cause problems when building up a ScopStmt for them. | |||
2066 | // Furthermore, basic blocks dominated by error blocks may reference | |||
2067 | // instructions in the error block which, if the error block is not modeled, | |||
2068 | // can themselves not be constructed properly. | |||
2069 | removeErrorBlockDomains(); | |||
2070 | } | |||
2071 | ||||
2072 | void Scop::buildDomainsWithBranchConstraints(Region *R) { | |||
2073 | RegionInfo &RI = *R->getRegionInfo(); | |||
2074 | ||||
2075 | // To create the domain for each block in R we iterate over all blocks and | |||
2076 | // subregions in R and propagate the conditions under which the current region | |||
2077 | // element is executed. To this end we iterate in reverse post order over R as | |||
2078 | // it ensures that we first visit all predecessors of a region node (either a | |||
2079 | // basic block or a subregion) before we visit the region node itself. | |||
2080 | // Initially, only the domain for the SCoP region entry block is set and from | |||
2081 | // there we propagate the current domain to all successors, however we add the | |||
2082 | // condition that the successor is actually executed next. | |||
2083 | // As we are only interested in non-loop carried constraints here we can | |||
2084 | // simply skip loop back edges. | |||
2085 | ||||
2086 | ReversePostOrderTraversal<Region *> RTraversal(R); | |||
2087 | for (auto *RN : RTraversal) { | |||
2088 | ||||
2089 | // Recurse for affine subregions but go on for basic blocks and non-affine | |||
2090 | // subregions. | |||
2091 | if (RN->isSubRegion()) { | |||
2092 | Region *SubRegion = RN->getNodeAs<Region>(); | |||
2093 | if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) { | |||
2094 | buildDomainsWithBranchConstraints(SubRegion); | |||
2095 | continue; | |||
2096 | } | |||
2097 | } | |||
2098 | ||||
2099 | if (containsErrorBlock(RN, getRegion(), LI, DT)) | |||
2100 | HasErrorBlock = true; | |||
2101 | ||||
2102 | BasicBlock *BB = getRegionNodeBasicBlock(RN); | |||
2103 | TerminatorInst *TI = BB->getTerminator(); | |||
2104 | ||||
2105 | if (isa<UnreachableInst>(TI)) | |||
2106 | continue; | |||
2107 | ||||
2108 | isl_set *Domain = DomainMap.lookup(BB); | |||
2109 | if (!Domain) { | |||
2110 | DEBUG(dbgs() << "\tSkip: " << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tSkip: " << BB-> getName() << ", it is only reachable from error blocks.\n" ; } } while (0) | |||
2111 | << ", it is only reachable from error blocks.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tSkip: " << BB-> getName() << ", it is only reachable from error blocks.\n" ; } } while (0); | |||
2112 | continue; | |||
2113 | } | |||
2114 | ||||
2115 | DEBUG(dbgs() << "\tVisit: " << BB->getName() << " : " << Domain << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tVisit: " << BB-> getName() << " : " << Domain << "\n"; } } while (0); | |||
2116 | ||||
2117 | Loop *BBLoop = getRegionNodeLoop(RN, LI); | |||
2118 | int BBLoopDepth = getRelativeLoopDepth(BBLoop); | |||
2119 | ||||
2120 | // Build the condition sets for the successor nodes of the current region | |||
2121 | // node. If it is a non-affine subregion we will always execute the single | |||
2122 | // exit node, hence the single entry node domain is the condition set. For | |||
2123 | // basic blocks we use the helper function buildConditionSets. | |||
2124 | SmallVector<isl_set *, 8> ConditionSets; | |||
2125 | if (RN->isSubRegion()) | |||
2126 | ConditionSets.push_back(isl_set_copy(Domain)); | |||
2127 | else | |||
2128 | buildConditionSets(*this, TI, BBLoop, Domain, ConditionSets); | |||
2129 | ||||
2130 | // Now iterate over the successors and set their initial domain based on | |||
2131 | // their condition set. We skip back edges here and have to be careful when | |||
2132 | // we leave a loop not to keep constraints over a dimension that doesn't | |||
2133 | // exist anymore. | |||
2134 | assert(RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size())((RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets .size()) ? static_cast<void> (0) : __assert_fail ("RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size()" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2134, __PRETTY_FUNCTION__)); | |||
2135 | for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) { | |||
2136 | isl_set *CondSet = ConditionSets[u]; | |||
2137 | BasicBlock *SuccBB = getRegionNodeSuccessor(RN, TI, u); | |||
2138 | ||||
2139 | // Skip back edges. | |||
2140 | if (DT.dominates(SuccBB, BB)) { | |||
2141 | isl_set_free(CondSet); | |||
2142 | continue; | |||
2143 | } | |||
2144 | ||||
2145 | // Do not adjust the number of dimensions if we enter a boxed loop or are | |||
2146 | // in a non-affine subregion or if the surrounding loop stays the same. | |||
2147 | Loop *SuccBBLoop = LI.getLoopFor(SuccBB); | |||
2148 | Region *SuccRegion = RI.getRegionFor(SuccBB); | |||
2149 | if (SD.isNonAffineSubRegion(SuccRegion, &getRegion())) | |||
2150 | while (SuccBBLoop && SuccRegion->contains(SuccBBLoop)) | |||
2151 | SuccBBLoop = SuccBBLoop->getParentLoop(); | |||
2152 | ||||
2153 | if (BBLoop != SuccBBLoop) { | |||
2154 | ||||
2155 | // Check if the edge to SuccBB is a loop entry or exit edge. If so | |||
2156 | // adjust the dimensionality accordingly. Lastly, if we leave a loop | |||
2157 | // and enter a new one we need to drop the old constraints. | |||
2158 | int SuccBBLoopDepth = getRelativeLoopDepth(SuccBBLoop); | |||
2159 | unsigned LoopDepthDiff = std::abs(BBLoopDepth - SuccBBLoopDepth); | |||
2160 | if (BBLoopDepth > SuccBBLoopDepth) { | |||
2161 | CondSet = isl_set_project_out(CondSet, isl_dim_set, | |||
2162 | isl_set_n_dim(CondSet) - LoopDepthDiff, | |||
2163 | LoopDepthDiff); | |||
2164 | } else if (SuccBBLoopDepth > BBLoopDepth) { | |||
2165 | assert(LoopDepthDiff == 1)((LoopDepthDiff == 1) ? static_cast<void> (0) : __assert_fail ("LoopDepthDiff == 1", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2165, __PRETTY_FUNCTION__)); | |||
2166 | CondSet = isl_set_add_dims(CondSet, isl_dim_set, 1); | |||
2167 | CondSet = addDomainDimId(CondSet, SuccBBLoopDepth, SuccBBLoop); | |||
2168 | } else if (BBLoopDepth >= 0) { | |||
2169 | assert(LoopDepthDiff <= 1)((LoopDepthDiff <= 1) ? static_cast<void> (0) : __assert_fail ("LoopDepthDiff <= 1", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2169, __PRETTY_FUNCTION__)); | |||
2170 | CondSet = isl_set_project_out(CondSet, isl_dim_set, BBLoopDepth, 1); | |||
2171 | CondSet = isl_set_add_dims(CondSet, isl_dim_set, 1); | |||
2172 | CondSet = addDomainDimId(CondSet, SuccBBLoopDepth, SuccBBLoop); | |||
2173 | } | |||
2174 | } | |||
2175 | ||||
2176 | // Set the domain for the successor or merge it with an existing domain in | |||
2177 | // case there are multiple paths (without loop back edges) to the | |||
2178 | // successor block. | |||
2179 | isl_set *&SuccDomain = DomainMap[SuccBB]; | |||
2180 | if (!SuccDomain) | |||
2181 | SuccDomain = CondSet; | |||
2182 | else | |||
2183 | SuccDomain = isl_set_union(SuccDomain, CondSet); | |||
2184 | ||||
2185 | SuccDomain = isl_set_coalesce(SuccDomain); | |||
2186 | if (isl_set_n_basic_set(SuccDomain) > MaxConjunctsInDomain) { | |||
2187 | auto *Empty = isl_set_empty(isl_set_get_space(SuccDomain)); | |||
2188 | isl_set_free(SuccDomain); | |||
2189 | SuccDomain = Empty; | |||
2190 | invalidate(ERROR_DOMAINCONJUNCTS, DebugLoc()); | |||
2191 | } | |||
2192 | DEBUG(dbgs() << "\tSet SuccBB: " << SuccBB->getName() << " : "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tSet SuccBB: " << SuccBB ->getName() << " : " << SuccDomain << "\n" ; } } while (0) | |||
2193 | << SuccDomain << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tSet SuccBB: " << SuccBB ->getName() << " : " << SuccDomain << "\n" ; } } while (0); | |||
2194 | } | |||
2195 | } | |||
2196 | } | |||
2197 | ||||
2198 | /// @brief Return the domain for @p BB wrt @p DomainMap. | |||
2199 | /// | |||
2200 | /// This helper function will lookup @p BB in @p DomainMap but also handle the | |||
2201 | /// case where @p BB is contained in a non-affine subregion using the region | |||
2202 | /// tree obtained by @p RI. | |||
2203 | static __isl_give isl_set * | |||
2204 | getDomainForBlock(BasicBlock *BB, DenseMap<BasicBlock *, isl_set *> &DomainMap, | |||
2205 | RegionInfo &RI) { | |||
2206 | auto DIt = DomainMap.find(BB); | |||
2207 | if (DIt != DomainMap.end()) | |||
2208 | return isl_set_copy(DIt->getSecond()); | |||
2209 | ||||
2210 | Region *R = RI.getRegionFor(BB); | |||
2211 | while (R->getEntry() == BB) | |||
2212 | R = R->getParent(); | |||
2213 | return getDomainForBlock(R->getEntry(), DomainMap, RI); | |||
2214 | } | |||
2215 | ||||
2216 | void Scop::propagateDomainConstraints(Region *R) { | |||
2217 | // Iterate over the region R and propagate the domain constrains from the | |||
2218 | // predecessors to the current node. In contrast to the | |||
2219 | // buildDomainsWithBranchConstraints function, this one will pull the domain | |||
2220 | // information from the predecessors instead of pushing it to the successors. | |||
2221 | // Additionally, we assume the domains to be already present in the domain | |||
2222 | // map here. However, we iterate again in reverse post order so we know all | |||
2223 | // predecessors have been visited before a block or non-affine subregion is | |||
2224 | // visited. | |||
2225 | ||||
2226 | // The set of boxed loops (loops in non-affine subregions) for this SCoP. | |||
2227 | auto &BoxedLoops = *SD.getBoxedLoops(&getRegion()); | |||
2228 | ||||
2229 | ReversePostOrderTraversal<Region *> RTraversal(R); | |||
2230 | for (auto *RN : RTraversal) { | |||
2231 | ||||
2232 | // Recurse for affine subregions but go on for basic blocks and non-affine | |||
2233 | // subregions. | |||
2234 | if (RN->isSubRegion()) { | |||
2235 | Region *SubRegion = RN->getNodeAs<Region>(); | |||
2236 | if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) { | |||
2237 | propagateDomainConstraints(SubRegion); | |||
2238 | continue; | |||
2239 | } | |||
2240 | } | |||
2241 | ||||
2242 | // Get the domain for the current block and check if it was initialized or | |||
2243 | // not. The only way it was not is if this block is only reachable via error | |||
2244 | // blocks, thus will not be executed under the assumptions we make. Such | |||
2245 | // blocks have to be skipped as their predecessors might not have domains | |||
2246 | // either. It would not benefit us to compute the domain anyway, only the | |||
2247 | // domains of the error blocks that are reachable from non-error blocks | |||
2248 | // are needed to generate assumptions. | |||
2249 | BasicBlock *BB = getRegionNodeBasicBlock(RN); | |||
2250 | isl_set *&Domain = DomainMap[BB]; | |||
2251 | if (!Domain) { | |||
2252 | DEBUG(dbgs() << "\tSkip: " << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tSkip: " << BB-> getName() << ", it is only reachable from error blocks.\n" ; } } while (0) | |||
2253 | << ", it is only reachable from error blocks.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tSkip: " << BB-> getName() << ", it is only reachable from error blocks.\n" ; } } while (0); | |||
2254 | DomainMap.erase(BB); | |||
2255 | continue; | |||
2256 | } | |||
2257 | DEBUG(dbgs() << "\tVisit: " << BB->getName() << " : " << Domain << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\tVisit: " << BB-> getName() << " : " << Domain << "\n"; } } while (0); | |||
2258 | ||||
2259 | Loop *BBLoop = getRegionNodeLoop(RN, LI); | |||
2260 | int BBLoopDepth = getRelativeLoopDepth(BBLoop); | |||
2261 | ||||
2262 | isl_set *PredDom = isl_set_empty(isl_set_get_space(Domain)); | |||
2263 | for (auto *PredBB : predecessors(BB)) { | |||
2264 | ||||
2265 | // Skip backedges | |||
2266 | if (DT.dominates(BB, PredBB)) | |||
2267 | continue; | |||
2268 | ||||
2269 | isl_set *PredBBDom = nullptr; | |||
2270 | ||||
2271 | // Handle the SCoP entry block with its outside predecessors. | |||
2272 | if (!getRegion().contains(PredBB)) | |||
2273 | PredBBDom = isl_set_universe(isl_set_get_space(PredDom)); | |||
2274 | ||||
2275 | if (!PredBBDom) { | |||
2276 | // Determine the loop depth of the predecessor and adjust its domain to | |||
2277 | // the domain of the current block. This can mean we have to: | |||
2278 | // o) Drop a dimension if this block is the exit of a loop, not the | |||
2279 | // header of a new loop and the predecessor was part of the loop. | |||
2280 | // o) Add an unconstrainted new dimension if this block is the header | |||
2281 | // of a loop and the predecessor is not part of it. | |||
2282 | // o) Drop the information about the innermost loop dimension when the | |||
2283 | // predecessor and the current block are surrounded by different | |||
2284 | // loops in the same depth. | |||
2285 | PredBBDom = getDomainForBlock(PredBB, DomainMap, *R->getRegionInfo()); | |||
2286 | Loop *PredBBLoop = LI.getLoopFor(PredBB); | |||
2287 | while (BoxedLoops.count(PredBBLoop)) | |||
2288 | PredBBLoop = PredBBLoop->getParentLoop(); | |||
2289 | ||||
2290 | int PredBBLoopDepth = getRelativeLoopDepth(PredBBLoop); | |||
2291 | unsigned LoopDepthDiff = std::abs(BBLoopDepth - PredBBLoopDepth); | |||
2292 | if (BBLoopDepth < PredBBLoopDepth) | |||
2293 | PredBBDom = isl_set_project_out( | |||
2294 | PredBBDom, isl_dim_set, isl_set_n_dim(PredBBDom) - LoopDepthDiff, | |||
2295 | LoopDepthDiff); | |||
2296 | else if (PredBBLoopDepth < BBLoopDepth) { | |||
2297 | assert(LoopDepthDiff == 1)((LoopDepthDiff == 1) ? static_cast<void> (0) : __assert_fail ("LoopDepthDiff == 1", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2297, __PRETTY_FUNCTION__)); | |||
2298 | PredBBDom = isl_set_add_dims(PredBBDom, isl_dim_set, 1); | |||
2299 | } else if (BBLoop != PredBBLoop && BBLoopDepth >= 0) { | |||
2300 | assert(LoopDepthDiff <= 1)((LoopDepthDiff <= 1) ? static_cast<void> (0) : __assert_fail ("LoopDepthDiff <= 1", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2300, __PRETTY_FUNCTION__)); | |||
2301 | PredBBDom = isl_set_drop_constraints_involving_dims( | |||
2302 | PredBBDom, isl_dim_set, BBLoopDepth, 1); | |||
2303 | } | |||
2304 | } | |||
2305 | ||||
2306 | PredDom = isl_set_union(PredDom, PredBBDom); | |||
2307 | } | |||
2308 | ||||
2309 | // Under the union of all predecessor conditions we can reach this block. | |||
2310 | Domain = isl_set_coalesce(isl_set_intersect(Domain, PredDom)); | |||
2311 | ||||
2312 | if (BBLoop && BBLoop->getHeader() == BB && getRegion().contains(BBLoop)) | |||
2313 | addLoopBoundsToHeaderDomain(BBLoop); | |||
2314 | ||||
2315 | // Add assumptions for error blocks. | |||
2316 | if (containsErrorBlock(RN, getRegion(), LI, DT)) { | |||
2317 | IsOptimized = true; | |||
2318 | isl_set *DomPar = isl_set_params(isl_set_copy(Domain)); | |||
2319 | addAssumption(ERRORBLOCK, isl_set_complement(DomPar), | |||
2320 | BB->getTerminator()->getDebugLoc()); | |||
2321 | } | |||
2322 | } | |||
2323 | } | |||
2324 | ||||
2325 | /// @brief Create a map from SetSpace -> SetSpace where the dimensions @p Dim | |||
2326 | /// is incremented by one and all other dimensions are equal, e.g., | |||
2327 | /// [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3] | |||
2328 | /// if @p Dim is 2 and @p SetSpace has 4 dimensions. | |||
2329 | static __isl_give isl_map * | |||
2330 | createNextIterationMap(__isl_take isl_space *SetSpace, unsigned Dim) { | |||
2331 | auto *MapSpace = isl_space_map_from_set(SetSpace); | |||
2332 | auto *NextIterationMap = isl_map_universe(isl_space_copy(MapSpace)); | |||
2333 | for (unsigned u = 0; u < isl_map_n_in(NextIterationMap); u++) | |||
2334 | if (u != Dim) | |||
2335 | NextIterationMap = | |||
2336 | isl_map_equate(NextIterationMap, isl_dim_in, u, isl_dim_out, u); | |||
2337 | auto *C = isl_constraint_alloc_equality(isl_local_space_from_space(MapSpace)); | |||
2338 | C = isl_constraint_set_constant_si(C, 1); | |||
2339 | C = isl_constraint_set_coefficient_si(C, isl_dim_in, Dim, 1); | |||
2340 | C = isl_constraint_set_coefficient_si(C, isl_dim_out, Dim, -1); | |||
2341 | NextIterationMap = isl_map_add_constraint(NextIterationMap, C); | |||
2342 | return NextIterationMap; | |||
2343 | } | |||
2344 | ||||
2345 | void Scop::addLoopBoundsToHeaderDomain(Loop *L) { | |||
2346 | int LoopDepth = getRelativeLoopDepth(L); | |||
2347 | assert(LoopDepth >= 0 && "Loop in region should have at least depth one")((LoopDepth >= 0 && "Loop in region should have at least depth one" ) ? static_cast<void> (0) : __assert_fail ("LoopDepth >= 0 && \"Loop in region should have at least depth one\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2347, __PRETTY_FUNCTION__)); | |||
2348 | ||||
2349 | BasicBlock *HeaderBB = L->getHeader(); | |||
2350 | assert(DomainMap.count(HeaderBB))((DomainMap.count(HeaderBB)) ? static_cast<void> (0) : __assert_fail ("DomainMap.count(HeaderBB)", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2350, __PRETTY_FUNCTION__)); | |||
2351 | isl_set *&HeaderBBDom = DomainMap[HeaderBB]; | |||
| ||||
2352 | ||||
2353 | isl_map *NextIterationMap = | |||
2354 | createNextIterationMap(isl_set_get_space(HeaderBBDom), LoopDepth); | |||
2355 | ||||
2356 | isl_set *UnionBackedgeCondition = | |||
2357 | isl_set_empty(isl_set_get_space(HeaderBBDom)); | |||
2358 | ||||
2359 | SmallVector<llvm::BasicBlock *, 4> LatchBlocks; | |||
2360 | L->getLoopLatches(LatchBlocks); | |||
2361 | ||||
2362 | for (BasicBlock *LatchBB : LatchBlocks) { | |||
2363 | ||||
2364 | // If the latch is only reachable via error statements we skip it. | |||
2365 | isl_set *LatchBBDom = DomainMap.lookup(LatchBB); | |||
2366 | if (!LatchBBDom) | |||
2367 | continue; | |||
2368 | ||||
2369 | isl_set *BackedgeCondition = nullptr; | |||
2370 | ||||
2371 | TerminatorInst *TI = LatchBB->getTerminator(); | |||
2372 | BranchInst *BI = dyn_cast<BranchInst>(TI); | |||
2373 | if (BI && BI->isUnconditional()) | |||
2374 | BackedgeCondition = isl_set_copy(LatchBBDom); | |||
2375 | else { | |||
2376 | SmallVector<isl_set *, 8> ConditionSets; | |||
2377 | int idx = BI->getSuccessor(0) != HeaderBB; | |||
2378 | buildConditionSets(*this, TI, L, LatchBBDom, ConditionSets); | |||
2379 | ||||
2380 | // Free the non back edge condition set as we do not need it. | |||
2381 | isl_set_free(ConditionSets[1 - idx]); | |||
2382 | ||||
2383 | BackedgeCondition = ConditionSets[idx]; | |||
2384 | } | |||
2385 | ||||
2386 | int LatchLoopDepth = getRelativeLoopDepth(LI.getLoopFor(LatchBB)); | |||
2387 | assert(LatchLoopDepth >= LoopDepth)((LatchLoopDepth >= LoopDepth) ? static_cast<void> ( 0) : __assert_fail ("LatchLoopDepth >= LoopDepth", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2387, __PRETTY_FUNCTION__)); | |||
2388 | BackedgeCondition = | |||
2389 | isl_set_project_out(BackedgeCondition, isl_dim_set, LoopDepth + 1, | |||
2390 | LatchLoopDepth - LoopDepth); | |||
2391 | UnionBackedgeCondition = | |||
2392 | isl_set_union(UnionBackedgeCondition, BackedgeCondition); | |||
2393 | } | |||
2394 | ||||
2395 | isl_map *ForwardMap = isl_map_lex_le(isl_set_get_space(HeaderBBDom)); | |||
2396 | for (int i = 0; i < LoopDepth; i++) | |||
2397 | ForwardMap = isl_map_equate(ForwardMap, isl_dim_in, i, isl_dim_out, i); | |||
2398 | ||||
2399 | isl_set *UnionBackedgeConditionComplement = | |||
2400 | isl_set_complement(UnionBackedgeCondition); | |||
2401 | UnionBackedgeConditionComplement = isl_set_lower_bound_si( | |||
2402 | UnionBackedgeConditionComplement, isl_dim_set, LoopDepth, 0); | |||
2403 | UnionBackedgeConditionComplement = | |||
2404 | isl_set_apply(UnionBackedgeConditionComplement, ForwardMap); | |||
2405 | HeaderBBDom = isl_set_subtract(HeaderBBDom, UnionBackedgeConditionComplement); | |||
2406 | HeaderBBDom = isl_set_apply(HeaderBBDom, NextIterationMap); | |||
2407 | ||||
2408 | auto Parts = partitionSetParts(HeaderBBDom, LoopDepth); | |||
2409 | HeaderBBDom = Parts.second; | |||
2410 | ||||
2411 | // Check if there is a <nsw> tagged AddRec for this loop and if so do not add | |||
2412 | // the bounded assumptions to the context as they are already implied by the | |||
2413 | // <nsw> tag. | |||
2414 | if (Affinator.hasNSWAddRecForLoop(L)) { | |||
2415 | isl_set_free(Parts.first); | |||
2416 | return; | |||
2417 | } | |||
2418 | ||||
2419 | isl_set *UnboundedCtx = isl_set_params(Parts.first); | |||
2420 | isl_set *BoundedCtx = isl_set_complement(UnboundedCtx); | |||
2421 | addAssumption(INFINITELOOP, BoundedCtx, | |||
2422 | HeaderBB->getTerminator()->getDebugLoc()); | |||
| ||||
2423 | } | |||
2424 | ||||
2425 | void Scop::buildAliasChecks(AliasAnalysis &AA) { | |||
2426 | if (!PollyUseRuntimeAliasChecks) | |||
2427 | return; | |||
2428 | ||||
2429 | if (buildAliasGroups(AA)) | |||
2430 | return; | |||
2431 | ||||
2432 | // If a problem occurs while building the alias groups we need to delete | |||
2433 | // this SCoP and pretend it wasn't valid in the first place. To this end | |||
2434 | // we make the assumed context infeasible. | |||
2435 | invalidate(ALIASING, DebugLoc()); | |||
2436 | ||||
2437 | DEBUG(dbgs() << "\n\nNOTE: Run time checks for " << getNameStr()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for " << getNameStr() << " could not be created as the number of parameters involved " "is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust " "the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n" ; } } while (0) | |||
2438 | << " could not be created as the number of parameters involved "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for " << getNameStr() << " could not be created as the number of parameters involved " "is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust " "the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n" ; } } while (0) | |||
2439 | "is too high. The SCoP will be "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for " << getNameStr() << " could not be created as the number of parameters involved " "is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust " "the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n" ; } } while (0) | |||
2440 | "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for " << getNameStr() << " could not be created as the number of parameters involved " "is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust " "the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n" ; } } while (0) | |||
2441 | "the maximal number of parameters but be advised that the "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for " << getNameStr() << " could not be created as the number of parameters involved " "is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust " "the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n" ; } } while (0) | |||
2442 | "compile time might increase exponentially.\n\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { dbgs() << "\n\nNOTE: Run time checks for " << getNameStr() << " could not be created as the number of parameters involved " "is too high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust " "the maximal number of parameters but be advised that the " "compile time might increase exponentially.\n\n" ; } } while (0); | |||
2443 | } | |||
2444 | ||||
2445 | bool Scop::buildAliasGroups(AliasAnalysis &AA) { | |||
2446 | // To create sound alias checks we perform the following steps: | |||
2447 | // o) Use the alias analysis and an alias set tracker to build alias sets | |||
2448 | // for all memory accesses inside the SCoP. | |||
2449 | // o) For each alias set we then map the aliasing pointers back to the | |||
2450 | // memory accesses we know, thus obtain groups of memory accesses which | |||
2451 | // might alias. | |||
2452 | // o) We divide each group based on the domains of the minimal/maximal | |||
2453 | // accesses. That means two minimal/maximal accesses are only in a group | |||
2454 | // if their access domains intersect, otherwise they are in different | |||
2455 | // ones. | |||
2456 | // o) We partition each group into read only and non read only accesses. | |||
2457 | // o) For each group with more than one base pointer we then compute minimal | |||
2458 | // and maximal accesses to each array of a group in read only and non | |||
2459 | // read only partitions separately. | |||
2460 | using AliasGroupTy = SmallVector<MemoryAccess *, 4>; | |||
2461 | ||||
2462 | AliasSetTracker AST(AA); | |||
2463 | ||||
2464 | DenseMap<Value *, MemoryAccess *> PtrToAcc; | |||
2465 | DenseSet<Value *> HasWriteAccess; | |||
2466 | for (ScopStmt &Stmt : *this) { | |||
2467 | ||||
2468 | // Skip statements with an empty domain as they will never be executed. | |||
2469 | isl_set *StmtDomain = Stmt.getDomain(); | |||
2470 | bool StmtDomainEmpty = isl_set_is_empty(StmtDomain); | |||
2471 | isl_set_free(StmtDomain); | |||
2472 | if (StmtDomainEmpty) | |||
2473 | continue; | |||
2474 | ||||
2475 | for (MemoryAccess *MA : Stmt) { | |||
2476 | if (MA->isScalarKind()) | |||
2477 | continue; | |||
2478 | if (!MA->isRead()) | |||
2479 | HasWriteAccess.insert(MA->getBaseAddr()); | |||
2480 | Instruction *Acc = MA->getAccessInstruction(); | |||
2481 | PtrToAcc[getPointerOperand(*Acc)] = MA; | |||
2482 | AST.add(Acc); | |||
2483 | } | |||
2484 | } | |||
2485 | ||||
2486 | SmallVector<AliasGroupTy, 4> AliasGroups; | |||
2487 | for (AliasSet &AS : AST) { | |||
2488 | if (AS.isMustAlias() || AS.isForwardingAliasSet()) | |||
2489 | continue; | |||
2490 | AliasGroupTy AG; | |||
2491 | for (auto PR : AS) | |||
2492 | AG.push_back(PtrToAcc[PR.getValue()]); | |||
2493 | assert(AG.size() > 1 &&((AG.size() > 1 && "Alias groups should contain at least two accesses" ) ? static_cast<void> (0) : __assert_fail ("AG.size() > 1 && \"Alias groups should contain at least two accesses\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2494, __PRETTY_FUNCTION__)) | |||
2494 | "Alias groups should contain at least two accesses")((AG.size() > 1 && "Alias groups should contain at least two accesses" ) ? static_cast<void> (0) : __assert_fail ("AG.size() > 1 && \"Alias groups should contain at least two accesses\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2494, __PRETTY_FUNCTION__)); | |||
2495 | AliasGroups.push_back(std::move(AG)); | |||
2496 | } | |||
2497 | ||||
2498 | // Split the alias groups based on their domain. | |||
2499 | for (unsigned u = 0; u < AliasGroups.size(); u++) { | |||
2500 | AliasGroupTy NewAG; | |||
2501 | AliasGroupTy &AG = AliasGroups[u]; | |||
2502 | AliasGroupTy::iterator AGI = AG.begin(); | |||
2503 | isl_set *AGDomain = getAccessDomain(*AGI); | |||
2504 | while (AGI != AG.end()) { | |||
2505 | MemoryAccess *MA = *AGI; | |||
2506 | isl_set *MADomain = getAccessDomain(MA); | |||
2507 | if (isl_set_is_disjoint(AGDomain, MADomain)) { | |||
2508 | NewAG.push_back(MA); | |||
2509 | AGI = AG.erase(AGI); | |||
2510 | isl_set_free(MADomain); | |||
2511 | } else { | |||
2512 | AGDomain = isl_set_union(AGDomain, MADomain); | |||
2513 | AGI++; | |||
2514 | } | |||
2515 | } | |||
2516 | if (NewAG.size() > 1) | |||
2517 | AliasGroups.push_back(std::move(NewAG)); | |||
2518 | isl_set_free(AGDomain); | |||
2519 | } | |||
2520 | ||||
2521 | auto &F = *getRegion().getEntry()->getParent(); | |||
2522 | MapVector<const Value *, SmallPtrSet<MemoryAccess *, 8>> ReadOnlyPairs; | |||
2523 | SmallPtrSet<const Value *, 4> NonReadOnlyBaseValues; | |||
2524 | for (AliasGroupTy &AG : AliasGroups) { | |||
2525 | NonReadOnlyBaseValues.clear(); | |||
2526 | ReadOnlyPairs.clear(); | |||
2527 | ||||
2528 | if (AG.size() < 2) { | |||
2529 | AG.clear(); | |||
2530 | continue; | |||
2531 | } | |||
2532 | ||||
2533 | for (auto II = AG.begin(); II != AG.end();) { | |||
2534 | emitOptimizationRemarkAnalysis( | |||
2535 | F.getContext(), DEBUG_TYPE"polly-scops", F, | |||
2536 | (*II)->getAccessInstruction()->getDebugLoc(), | |||
2537 | "Possibly aliasing pointer, use restrict keyword."); | |||
2538 | ||||
2539 | Value *BaseAddr = (*II)->getBaseAddr(); | |||
2540 | if (HasWriteAccess.count(BaseAddr)) { | |||
2541 | NonReadOnlyBaseValues.insert(BaseAddr); | |||
2542 | II++; | |||
2543 | } else { | |||
2544 | ReadOnlyPairs[BaseAddr].insert(*II); | |||
2545 | II = AG.erase(II); | |||
2546 | } | |||
2547 | } | |||
2548 | ||||
2549 | // If we don't have read only pointers check if there are at least two | |||
2550 | // non read only pointers, otherwise clear the alias group. | |||
2551 | if (ReadOnlyPairs.empty() && NonReadOnlyBaseValues.size() <= 1) { | |||
2552 | AG.clear(); | |||
2553 | continue; | |||
2554 | } | |||
2555 | ||||
2556 | // If we don't have non read only pointers clear the alias group. | |||
2557 | if (NonReadOnlyBaseValues.empty()) { | |||
2558 | AG.clear(); | |||
2559 | continue; | |||
2560 | } | |||
2561 | ||||
2562 | // Calculate minimal and maximal accesses for non read only accesses. | |||
2563 | MinMaxAliasGroups.emplace_back(); | |||
2564 | MinMaxVectorPairTy &pair = MinMaxAliasGroups.back(); | |||
2565 | MinMaxVectorTy &MinMaxAccessesNonReadOnly = pair.first; | |||
2566 | MinMaxVectorTy &MinMaxAccessesReadOnly = pair.second; | |||
2567 | MinMaxAccessesNonReadOnly.reserve(AG.size()); | |||
2568 | ||||
2569 | isl_union_map *Accesses = isl_union_map_empty(getParamSpace()); | |||
2570 | ||||
2571 | // AG contains only non read only accesses. | |||
2572 | for (MemoryAccess *MA : AG) | |||
2573 | Accesses = isl_union_map_add_map(Accesses, MA->getAccessRelation()); | |||
2574 | ||||
2575 | bool Valid = calculateMinMaxAccess(Accesses, getDomains(), | |||
2576 | MinMaxAccessesNonReadOnly); | |||
2577 | ||||
2578 | // Bail out if the number of values we need to compare is too large. | |||
2579 | // This is important as the number of comparisions grows quadratically with | |||
2580 | // the number of values we need to compare. | |||
2581 | if (!Valid || (MinMaxAccessesNonReadOnly.size() + !ReadOnlyPairs.empty() > | |||
2582 | RunTimeChecksMaxArraysPerGroup)) | |||
2583 | return false; | |||
2584 | ||||
2585 | // Calculate minimal and maximal accesses for read only accesses. | |||
2586 | MinMaxAccessesReadOnly.reserve(ReadOnlyPairs.size()); | |||
2587 | Accesses = isl_union_map_empty(getParamSpace()); | |||
2588 | ||||
2589 | for (const auto &ReadOnlyPair : ReadOnlyPairs) | |||
2590 | for (MemoryAccess *MA : ReadOnlyPair.second) | |||
2591 | Accesses = isl_union_map_add_map(Accesses, MA->getAccessRelation()); | |||
2592 | ||||
2593 | Valid = | |||
2594 | calculateMinMaxAccess(Accesses, getDomains(), MinMaxAccessesReadOnly); | |||
2595 | ||||
2596 | if (!Valid) | |||
2597 | return false; | |||
2598 | } | |||
2599 | ||||
2600 | return true; | |||
2601 | } | |||
2602 | ||||
2603 | /// @brief Get the smallest loop that contains @p R but is not in @p R. | |||
2604 | static Loop *getLoopSurroundingRegion(Region &R, LoopInfo &LI) { | |||
2605 | // Start with the smallest loop containing the entry and expand that | |||
2606 | // loop until it contains all blocks in the region. If there is a loop | |||
2607 | // containing all blocks in the region check if it is itself contained | |||
2608 | // and if so take the parent loop as it will be the smallest containing | |||
2609 | // the region but not contained by it. | |||
2610 | Loop *L = LI.getLoopFor(R.getEntry()); | |||
2611 | while (L) { | |||
2612 | bool AllContained = true; | |||
2613 | for (auto *BB : R.blocks()) | |||
2614 | AllContained &= L->contains(BB); | |||
2615 | if (AllContained) | |||
2616 | break; | |||
2617 | L = L->getParentLoop(); | |||
2618 | } | |||
2619 | ||||
2620 | return L ? (R.contains(L) ? L->getParentLoop() : L) : nullptr; | |||
2621 | } | |||
2622 | ||||
2623 | static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI, | |||
2624 | ScopDetection &SD) { | |||
2625 | ||||
2626 | const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD.getBoxedLoops(&R); | |||
2627 | ||||
2628 | unsigned MinLD = INT_MAX2147483647, MaxLD = 0; | |||
2629 | for (BasicBlock *BB : R.blocks()) { | |||
2630 | if (Loop *L = LI.getLoopFor(BB)) { | |||
2631 | if (!R.contains(L)) | |||
2632 | continue; | |||
2633 | if (BoxedLoops && BoxedLoops->count(L)) | |||
2634 | continue; | |||
2635 | unsigned LD = L->getLoopDepth(); | |||
2636 | MinLD = std::min(MinLD, LD); | |||
2637 | MaxLD = std::max(MaxLD, LD); | |||
2638 | } | |||
2639 | } | |||
2640 | ||||
2641 | // Handle the case that there is no loop in the SCoP first. | |||
2642 | if (MaxLD == 0) | |||
2643 | return 1; | |||
2644 | ||||
2645 | assert(MinLD >= 1 && "Minimal loop depth should be at least one")((MinLD >= 1 && "Minimal loop depth should be at least one" ) ? static_cast<void> (0) : __assert_fail ("MinLD >= 1 && \"Minimal loop depth should be at least one\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2645, __PRETTY_FUNCTION__)); | |||
2646 | assert(MaxLD >= MinLD &&((MaxLD >= MinLD && "Maximal loop depth was smaller than mininaml loop depth?" ) ? static_cast<void> (0) : __assert_fail ("MaxLD >= MinLD && \"Maximal loop depth was smaller than mininaml loop depth?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2647, __PRETTY_FUNCTION__)) | |||
2647 | "Maximal loop depth was smaller than mininaml loop depth?")((MaxLD >= MinLD && "Maximal loop depth was smaller than mininaml loop depth?" ) ? static_cast<void> (0) : __assert_fail ("MaxLD >= MinLD && \"Maximal loop depth was smaller than mininaml loop depth?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2647, __PRETTY_FUNCTION__)); | |||
2648 | return MaxLD - MinLD + 1; | |||
2649 | } | |||
2650 | ||||
2651 | Scop::Scop(Region &R, AccFuncMapType &AccFuncMap, ScopDetection &SD, | |||
2652 | ScalarEvolution &ScalarEvolution, DominatorTree &DT, LoopInfo &LI, | |||
2653 | isl_ctx *Context, unsigned MaxLoopDepth) | |||
2654 | : LI(LI), DT(DT), SE(&ScalarEvolution), SD(SD), R(R), | |||
2655 | AccFuncMap(AccFuncMap), IsOptimized(false), | |||
2656 | HasSingleExitEdge(R.getExitingBlock()), HasErrorBlock(false), | |||
2657 | MaxLoopDepth(MaxLoopDepth), IslCtx(Context), Context(nullptr), | |||
2658 | Affinator(this), AssumedContext(nullptr), BoundaryContext(nullptr), | |||
2659 | Schedule(nullptr) {} | |||
2660 | ||||
2661 | void Scop::init(AliasAnalysis &AA, AssumptionCache &AC) { | |||
2662 | buildContext(); | |||
2663 | addUserAssumptions(AC); | |||
2664 | buildInvariantEquivalenceClasses(); | |||
2665 | ||||
2666 | buildDomains(&R); | |||
2667 | ||||
2668 | // Remove empty and ignored statements. | |||
2669 | // Exit early in case there are no executable statements left in this scop. | |||
2670 | simplifySCoP(true); | |||
2671 | if (Stmts.empty()) | |||
2672 | return; | |||
2673 | ||||
2674 | // The ScopStmts now have enough information to initialize themselves. | |||
2675 | for (ScopStmt &Stmt : Stmts) | |||
2676 | Stmt.init(); | |||
2677 | ||||
2678 | buildSchedule(); | |||
2679 | ||||
2680 | if (isl_set_is_empty(AssumedContext)) | |||
2681 | return; | |||
2682 | ||||
2683 | updateAccessDimensionality(); | |||
2684 | realignParams(); | |||
2685 | addParameterBounds(); | |||
2686 | addUserContext(); | |||
2687 | buildBoundaryContext(); | |||
2688 | simplifyContexts(); | |||
2689 | buildAliasChecks(AA); | |||
2690 | ||||
2691 | hoistInvariantLoads(); | |||
2692 | simplifySCoP(false); | |||
2693 | } | |||
2694 | ||||
2695 | Scop::~Scop() { | |||
2696 | isl_set_free(Context); | |||
2697 | isl_set_free(AssumedContext); | |||
2698 | isl_set_free(BoundaryContext); | |||
2699 | isl_schedule_free(Schedule); | |||
2700 | ||||
2701 | for (auto It : DomainMap) | |||
2702 | isl_set_free(It.second); | |||
2703 | ||||
2704 | // Free the alias groups | |||
2705 | for (MinMaxVectorPairTy &MinMaxAccessPair : MinMaxAliasGroups) { | |||
2706 | for (MinMaxAccessTy &MMA : MinMaxAccessPair.first) { | |||
2707 | isl_pw_multi_aff_free(MMA.first); | |||
2708 | isl_pw_multi_aff_free(MMA.second); | |||
2709 | } | |||
2710 | for (MinMaxAccessTy &MMA : MinMaxAccessPair.second) { | |||
2711 | isl_pw_multi_aff_free(MMA.first); | |||
2712 | isl_pw_multi_aff_free(MMA.second); | |||
2713 | } | |||
2714 | } | |||
2715 | ||||
2716 | for (const auto &IAClass : InvariantEquivClasses) | |||
2717 | isl_set_free(std::get<2>(IAClass)); | |||
2718 | } | |||
2719 | ||||
2720 | void Scop::updateAccessDimensionality() { | |||
2721 | for (auto &Stmt : *this) | |||
2722 | for (auto &Access : Stmt) | |||
2723 | Access->updateDimensionality(); | |||
2724 | } | |||
2725 | ||||
2726 | void Scop::simplifySCoP(bool RemoveIgnoredStmts) { | |||
2727 | for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) { | |||
2728 | ScopStmt &Stmt = *StmtIt; | |||
2729 | RegionNode *RN = Stmt.isRegionStmt() | |||
2730 | ? Stmt.getRegion()->getNode() | |||
2731 | : getRegion().getBBNode(Stmt.getBasicBlock()); | |||
2732 | ||||
2733 | bool RemoveStmt = StmtIt->isEmpty(); | |||
2734 | if (!RemoveStmt) | |||
2735 | RemoveStmt = isl_set_is_empty(DomainMap[getRegionNodeBasicBlock(RN)]); | |||
2736 | if (!RemoveStmt) | |||
2737 | RemoveStmt = (RemoveIgnoredStmts && isIgnored(RN)); | |||
2738 | ||||
2739 | // Remove read only statements only after invariant loop hoisting. | |||
2740 | if (!RemoveStmt && !RemoveIgnoredStmts) { | |||
2741 | bool OnlyRead = true; | |||
2742 | for (MemoryAccess *MA : Stmt) { | |||
2743 | if (MA->isRead()) | |||
2744 | continue; | |||
2745 | ||||
2746 | OnlyRead = false; | |||
2747 | break; | |||
2748 | } | |||
2749 | ||||
2750 | RemoveStmt = OnlyRead; | |||
2751 | } | |||
2752 | ||||
2753 | if (RemoveStmt) { | |||
2754 | // Remove the statement because it is unnecessary. | |||
2755 | if (Stmt.isRegionStmt()) | |||
2756 | for (BasicBlock *BB : Stmt.getRegion()->blocks()) | |||
2757 | StmtMap.erase(BB); | |||
2758 | else | |||
2759 | StmtMap.erase(Stmt.getBasicBlock()); | |||
2760 | ||||
2761 | StmtIt = Stmts.erase(StmtIt); | |||
2762 | continue; | |||
2763 | } | |||
2764 | ||||
2765 | StmtIt++; | |||
2766 | } | |||
2767 | } | |||
2768 | ||||
2769 | const InvariantEquivClassTy *Scop::lookupInvariantEquivClass(Value *Val) const { | |||
2770 | LoadInst *LInst = dyn_cast<LoadInst>(Val); | |||
2771 | if (!LInst) | |||
2772 | return nullptr; | |||
2773 | ||||
2774 | if (Value *Rep = InvEquivClassVMap.lookup(LInst)) | |||
2775 | LInst = cast<LoadInst>(Rep); | |||
2776 | ||||
2777 | const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand()); | |||
2778 | for (auto &IAClass : InvariantEquivClasses) | |||
2779 | if (PointerSCEV == std::get<0>(IAClass)) | |||
2780 | return &IAClass; | |||
2781 | ||||
2782 | return nullptr; | |||
2783 | } | |||
2784 | ||||
2785 | void Scop::addInvariantLoads(ScopStmt &Stmt, MemoryAccessList &InvMAs) { | |||
2786 | ||||
2787 | // Get the context under which the statement is executed. | |||
2788 | isl_set *DomainCtx = isl_set_params(Stmt.getDomain()); | |||
2789 | DomainCtx = isl_set_remove_redundancies(DomainCtx); | |||
2790 | DomainCtx = isl_set_detect_equalities(DomainCtx); | |||
2791 | DomainCtx = isl_set_coalesce(DomainCtx); | |||
2792 | ||||
2793 | // Project out all parameters that relate to loads in the statement. Otherwise | |||
2794 | // we could have cyclic dependences on the constraints under which the | |||
2795 | // hoisted loads are executed and we could not determine an order in which to | |||
2796 | // pre-load them. This happens because not only lower bounds are part of the | |||
2797 | // domain but also upper bounds. | |||
2798 | for (MemoryAccess *MA : InvMAs) { | |||
2799 | Instruction *AccInst = MA->getAccessInstruction(); | |||
2800 | if (SE->isSCEVable(AccInst->getType())) { | |||
2801 | SetVector<Value *> Values; | |||
2802 | for (const SCEV *Parameter : Parameters) { | |||
2803 | Values.clear(); | |||
2804 | findValues(Parameter, Values); | |||
2805 | if (!Values.count(AccInst)) | |||
2806 | continue; | |||
2807 | ||||
2808 | if (isl_id *ParamId = getIdForParam(Parameter)) { | |||
2809 | int Dim = isl_set_find_dim_by_id(DomainCtx, isl_dim_param, ParamId); | |||
2810 | DomainCtx = isl_set_eliminate(DomainCtx, isl_dim_param, Dim, 1); | |||
2811 | isl_id_free(ParamId); | |||
2812 | } | |||
2813 | } | |||
2814 | } | |||
2815 | } | |||
2816 | ||||
2817 | for (MemoryAccess *MA : InvMAs) { | |||
2818 | // Check for another invariant access that accesses the same location as | |||
2819 | // MA and if found consolidate them. Otherwise create a new equivalence | |||
2820 | // class at the end of InvariantEquivClasses. | |||
2821 | LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction()); | |||
2822 | const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand()); | |||
2823 | ||||
2824 | bool Consolidated = false; | |||
2825 | for (auto &IAClass : InvariantEquivClasses) { | |||
2826 | if (PointerSCEV != std::get<0>(IAClass)) | |||
2827 | continue; | |||
2828 | ||||
2829 | Consolidated = true; | |||
2830 | ||||
2831 | // Add MA to the list of accesses that are in this class. | |||
2832 | auto &MAs = std::get<1>(IAClass); | |||
2833 | MAs.push_front(MA); | |||
2834 | ||||
2835 | // Unify the execution context of the class and this statement. | |||
2836 | isl_set *&IAClassDomainCtx = std::get<2>(IAClass); | |||
2837 | if (IAClassDomainCtx) | |||
2838 | IAClassDomainCtx = isl_set_coalesce( | |||
2839 | isl_set_union(IAClassDomainCtx, isl_set_copy(DomainCtx))); | |||
2840 | else | |||
2841 | IAClassDomainCtx = isl_set_copy(DomainCtx); | |||
2842 | break; | |||
2843 | } | |||
2844 | ||||
2845 | if (Consolidated) | |||
2846 | continue; | |||
2847 | ||||
2848 | // If we did not consolidate MA, thus did not find an equivalence class | |||
2849 | // for it, we create a new one. | |||
2850 | InvariantEquivClasses.emplace_back(PointerSCEV, MemoryAccessList{MA}, | |||
2851 | isl_set_copy(DomainCtx)); | |||
2852 | } | |||
2853 | ||||
2854 | isl_set_free(DomainCtx); | |||
2855 | } | |||
2856 | ||||
2857 | bool Scop::isHoistableAccess(MemoryAccess *Access, | |||
2858 | __isl_keep isl_union_map *Writes) { | |||
2859 | // TODO: Loads that are not loop carried, hence are in a statement with | |||
2860 | // zero iterators, are by construction invariant, though we | |||
2861 | // currently "hoist" them anyway. This is necessary because we allow | |||
2862 | // them to be treated as parameters (e.g., in conditions) and our code | |||
2863 | // generation would otherwise use the old value. | |||
2864 | ||||
2865 | auto &Stmt = *Access->getStatement(); | |||
2866 | BasicBlock *BB = | |||
2867 | Stmt.isBlockStmt() ? Stmt.getBasicBlock() : Stmt.getRegion()->getEntry(); | |||
2868 | ||||
2869 | if (Access->isScalarKind() || Access->isWrite() || !Access->isAffine()) | |||
2870 | return false; | |||
2871 | ||||
2872 | // Skip accesses that have an invariant base pointer which is defined but | |||
2873 | // not loaded inside the SCoP. This can happened e.g., if a readnone call | |||
2874 | // returns a pointer that is used as a base address. However, as we want | |||
2875 | // to hoist indirect pointers, we allow the base pointer to be defined in | |||
2876 | // the region if it is also a memory access. Each ScopArrayInfo object | |||
2877 | // that has a base pointer origin has a base pointer that is loaded and | |||
2878 | // that it is invariant, thus it will be hoisted too. However, if there is | |||
2879 | // no base pointer origin we check that the base pointer is defined | |||
2880 | // outside the region. | |||
2881 | const ScopArrayInfo *SAI = Access->getScopArrayInfo(); | |||
2882 | while (auto *BasePtrOriginSAI = SAI->getBasePtrOriginSAI()) | |||
2883 | SAI = BasePtrOriginSAI; | |||
2884 | ||||
2885 | if (auto *BasePtrInst = dyn_cast<Instruction>(SAI->getBasePtr())) | |||
2886 | if (R.contains(BasePtrInst)) | |||
2887 | return false; | |||
2888 | ||||
2889 | // Skip accesses in non-affine subregions as they might not be executed | |||
2890 | // under the same condition as the entry of the non-affine subregion. | |||
2891 | if (BB != Access->getAccessInstruction()->getParent()) | |||
2892 | return false; | |||
2893 | ||||
2894 | isl_map *AccessRelation = Access->getAccessRelation(); | |||
2895 | ||||
2896 | // Skip accesses that have an empty access relation. These can be caused | |||
2897 | // by multiple offsets with a type cast in-between that cause the overall | |||
2898 | // byte offset to be not divisible by the new types sizes. | |||
2899 | if (isl_map_is_empty(AccessRelation)) { | |||
2900 | isl_map_free(AccessRelation); | |||
2901 | return false; | |||
2902 | } | |||
2903 | ||||
2904 | if (isl_map_involves_dims(AccessRelation, isl_dim_in, 0, | |||
2905 | Stmt.getNumIterators())) { | |||
2906 | isl_map_free(AccessRelation); | |||
2907 | return false; | |||
2908 | } | |||
2909 | ||||
2910 | AccessRelation = isl_map_intersect_domain(AccessRelation, Stmt.getDomain()); | |||
2911 | isl_set *AccessRange = isl_map_range(AccessRelation); | |||
2912 | ||||
2913 | isl_union_map *Written = isl_union_map_intersect_range( | |||
2914 | isl_union_map_copy(Writes), isl_union_set_from_set(AccessRange)); | |||
2915 | bool IsWritten = !isl_union_map_is_empty(Written); | |||
2916 | isl_union_map_free(Written); | |||
2917 | ||||
2918 | if (IsWritten) | |||
2919 | return false; | |||
2920 | ||||
2921 | return true; | |||
2922 | } | |||
2923 | ||||
2924 | void Scop::verifyInvariantLoads() { | |||
2925 | auto &RIL = *SD.getRequiredInvariantLoads(&getRegion()); | |||
2926 | for (LoadInst *LI : RIL) { | |||
2927 | assert(LI && getRegion().contains(LI))((LI && getRegion().contains(LI)) ? static_cast<void > (0) : __assert_fail ("LI && getRegion().contains(LI)" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2927, __PRETTY_FUNCTION__)); | |||
2928 | ScopStmt *Stmt = getStmtForBasicBlock(LI->getParent()); | |||
2929 | if (Stmt && Stmt->getArrayAccessOrNULLFor(LI)) { | |||
2930 | invalidate(INVARIANTLOAD, LI->getDebugLoc()); | |||
2931 | return; | |||
2932 | } | |||
2933 | } | |||
2934 | } | |||
2935 | ||||
2936 | void Scop::hoistInvariantLoads() { | |||
2937 | isl_union_map *Writes = getWrites(); | |||
2938 | for (ScopStmt &Stmt : *this) { | |||
2939 | ||||
2940 | MemoryAccessList InvariantAccesses; | |||
2941 | ||||
2942 | for (MemoryAccess *Access : Stmt) | |||
2943 | if (isHoistableAccess(Access, Writes)) | |||
2944 | InvariantAccesses.push_front(Access); | |||
2945 | ||||
2946 | // We inserted invariant accesses always in the front but need them to be | |||
2947 | // sorted in a "natural order". The statements are already sorted in reverse | |||
2948 | // post order and that suffices for the accesses too. The reason we require | |||
2949 | // an order in the first place is the dependences between invariant loads | |||
2950 | // that can be caused by indirect loads. | |||
2951 | InvariantAccesses.reverse(); | |||
2952 | ||||
2953 | // Transfer the memory access from the statement to the SCoP. | |||
2954 | Stmt.removeMemoryAccesses(InvariantAccesses); | |||
2955 | addInvariantLoads(Stmt, InvariantAccesses); | |||
2956 | } | |||
2957 | isl_union_map_free(Writes); | |||
2958 | ||||
2959 | verifyInvariantLoads(); | |||
2960 | } | |||
2961 | ||||
2962 | const ScopArrayInfo * | |||
2963 | Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *AccessType, | |||
2964 | ArrayRef<const SCEV *> Sizes, | |||
2965 | ScopArrayInfo::MemoryKind Kind) { | |||
2966 | auto &SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)]; | |||
2967 | if (!SAI) { | |||
2968 | auto &DL = getRegion().getEntry()->getModule()->getDataLayout(); | |||
2969 | SAI.reset(new ScopArrayInfo(BasePtr, AccessType, getIslCtx(), Sizes, Kind, | |||
2970 | DL, this)); | |||
2971 | } else { | |||
2972 | // In case of mismatching array sizes, we bail out by setting the run-time | |||
2973 | // context to false. | |||
2974 | if (!SAI->updateSizes(Sizes)) | |||
2975 | invalidate(DELINEARIZATION, DebugLoc()); | |||
2976 | } | |||
2977 | return SAI.get(); | |||
2978 | } | |||
2979 | ||||
2980 | const ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr, | |||
2981 | ScopArrayInfo::MemoryKind Kind) { | |||
2982 | auto *SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)].get(); | |||
2983 | assert(SAI && "No ScopArrayInfo available for this base pointer")((SAI && "No ScopArrayInfo available for this base pointer" ) ? static_cast<void> (0) : __assert_fail ("SAI && \"No ScopArrayInfo available for this base pointer\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 2983, __PRETTY_FUNCTION__)); | |||
2984 | return SAI; | |||
2985 | } | |||
2986 | ||||
2987 | std::string Scop::getContextStr() const { return stringFromIslObj(Context); } | |||
2988 | std::string Scop::getAssumedContextStr() const { | |||
2989 | return stringFromIslObj(AssumedContext); | |||
2990 | } | |||
2991 | std::string Scop::getBoundaryContextStr() const { | |||
2992 | return stringFromIslObj(BoundaryContext); | |||
2993 | } | |||
2994 | ||||
2995 | std::string Scop::getNameStr() const { | |||
2996 | std::string ExitName, EntryName; | |||
2997 | raw_string_ostream ExitStr(ExitName); | |||
2998 | raw_string_ostream EntryStr(EntryName); | |||
2999 | ||||
3000 | R.getEntry()->printAsOperand(EntryStr, false); | |||
3001 | EntryStr.str(); | |||
3002 | ||||
3003 | if (R.getExit()) { | |||
3004 | R.getExit()->printAsOperand(ExitStr, false); | |||
3005 | ExitStr.str(); | |||
3006 | } else | |||
3007 | ExitName = "FunctionExit"; | |||
3008 | ||||
3009 | return EntryName + "---" + ExitName; | |||
3010 | } | |||
3011 | ||||
3012 | __isl_give isl_set *Scop::getContext() const { return isl_set_copy(Context); } | |||
3013 | __isl_give isl_space *Scop::getParamSpace() const { | |||
3014 | return isl_set_get_space(Context); | |||
3015 | } | |||
3016 | ||||
3017 | __isl_give isl_set *Scop::getAssumedContext() const { | |||
3018 | return isl_set_copy(AssumedContext); | |||
3019 | } | |||
3020 | ||||
3021 | __isl_give isl_set *Scop::getRuntimeCheckContext() const { | |||
3022 | isl_set *RuntimeCheckContext = getAssumedContext(); | |||
3023 | RuntimeCheckContext = | |||
3024 | isl_set_intersect(RuntimeCheckContext, getBoundaryContext()); | |||
3025 | RuntimeCheckContext = simplifyAssumptionContext(RuntimeCheckContext, *this); | |||
3026 | return RuntimeCheckContext; | |||
3027 | } | |||
3028 | ||||
3029 | bool Scop::hasFeasibleRuntimeContext() const { | |||
3030 | isl_set *RuntimeCheckContext = getRuntimeCheckContext(); | |||
3031 | RuntimeCheckContext = addNonEmptyDomainConstraints(RuntimeCheckContext); | |||
3032 | bool IsFeasible = !isl_set_is_empty(RuntimeCheckContext); | |||
3033 | isl_set_free(RuntimeCheckContext); | |||
3034 | return IsFeasible; | |||
3035 | } | |||
3036 | ||||
3037 | static std::string toString(AssumptionKind Kind) { | |||
3038 | switch (Kind) { | |||
3039 | case ALIASING: | |||
3040 | return "No-aliasing"; | |||
3041 | case INBOUNDS: | |||
3042 | return "Inbounds"; | |||
3043 | case WRAPPING: | |||
3044 | return "No-overflows"; | |||
3045 | case ALIGNMENT: | |||
3046 | return "Alignment"; | |||
3047 | case ERRORBLOCK: | |||
3048 | return "No-error"; | |||
3049 | case INFINITELOOP: | |||
3050 | return "Finite loop"; | |||
3051 | case INVARIANTLOAD: | |||
3052 | return "Invariant load"; | |||
3053 | case DELINEARIZATION: | |||
3054 | return "Delinearization"; | |||
3055 | case ERROR_DOMAINCONJUNCTS: | |||
3056 | return "Low number of domain conjuncts"; | |||
3057 | } | |||
3058 | llvm_unreachable("Unknown AssumptionKind!")::llvm::llvm_unreachable_internal("Unknown AssumptionKind!", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3058); | |||
3059 | } | |||
3060 | ||||
3061 | void Scop::trackAssumption(AssumptionKind Kind, __isl_keep isl_set *Set, | |||
3062 | DebugLoc Loc) { | |||
3063 | if (isl_set_is_subset(Context, Set)) | |||
3064 | return; | |||
3065 | ||||
3066 | if (isl_set_is_subset(AssumedContext, Set)) | |||
3067 | return; | |||
3068 | ||||
3069 | auto &F = *getRegion().getEntry()->getParent(); | |||
3070 | std::string Msg = toString(Kind) + " assumption:\t" + stringFromIslObj(Set); | |||
3071 | emitOptimizationRemarkAnalysis(F.getContext(), DEBUG_TYPE"polly-scops", F, Loc, Msg); | |||
3072 | } | |||
3073 | ||||
3074 | void Scop::addAssumption(AssumptionKind Kind, __isl_take isl_set *Set, | |||
3075 | DebugLoc Loc) { | |||
3076 | trackAssumption(Kind, Set, Loc); | |||
3077 | AssumedContext = isl_set_intersect(AssumedContext, Set); | |||
3078 | ||||
3079 | int NSets = isl_set_n_basic_set(AssumedContext); | |||
3080 | if (NSets >= MaxDisjunctsAssumed) { | |||
3081 | isl_space *Space = isl_set_get_space(AssumedContext); | |||
3082 | isl_set_free(AssumedContext); | |||
3083 | AssumedContext = isl_set_empty(Space); | |||
3084 | } | |||
3085 | ||||
3086 | AssumedContext = isl_set_coalesce(AssumedContext); | |||
3087 | } | |||
3088 | ||||
3089 | void Scop::invalidate(AssumptionKind Kind, DebugLoc Loc) { | |||
3090 | addAssumption(Kind, isl_set_empty(getParamSpace()), Loc); | |||
3091 | } | |||
3092 | ||||
3093 | __isl_give isl_set *Scop::getBoundaryContext() const { | |||
3094 | return isl_set_copy(BoundaryContext); | |||
3095 | } | |||
3096 | ||||
3097 | void Scop::printContext(raw_ostream &OS) const { | |||
3098 | OS << "Context:\n"; | |||
3099 | ||||
3100 | if (!Context) { | |||
3101 | OS.indent(4) << "n/a\n\n"; | |||
3102 | return; | |||
3103 | } | |||
3104 | ||||
3105 | OS.indent(4) << getContextStr() << "\n"; | |||
3106 | ||||
3107 | OS.indent(4) << "Assumed Context:\n"; | |||
3108 | if (!AssumedContext) { | |||
3109 | OS.indent(4) << "n/a\n\n"; | |||
3110 | return; | |||
3111 | } | |||
3112 | ||||
3113 | OS.indent(4) << getAssumedContextStr() << "\n"; | |||
3114 | ||||
3115 | OS.indent(4) << "Boundary Context:\n"; | |||
3116 | if (!BoundaryContext) { | |||
3117 | OS.indent(4) << "n/a\n\n"; | |||
3118 | return; | |||
3119 | } | |||
3120 | ||||
3121 | OS.indent(4) << getBoundaryContextStr() << "\n"; | |||
3122 | ||||
3123 | for (const SCEV *Parameter : Parameters) { | |||
3124 | int Dim = ParameterIds.find(Parameter)->second; | |||
3125 | OS.indent(4) << "p" << Dim << ": " << *Parameter << "\n"; | |||
3126 | } | |||
3127 | } | |||
3128 | ||||
3129 | void Scop::printAliasAssumptions(raw_ostream &OS) const { | |||
3130 | int noOfGroups = 0; | |||
3131 | for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups) { | |||
3132 | if (Pair.second.size() == 0) | |||
3133 | noOfGroups += 1; | |||
3134 | else | |||
3135 | noOfGroups += Pair.second.size(); | |||
3136 | } | |||
3137 | ||||
3138 | OS.indent(4) << "Alias Groups (" << noOfGroups << "):\n"; | |||
3139 | if (MinMaxAliasGroups.empty()) { | |||
3140 | OS.indent(8) << "n/a\n"; | |||
3141 | return; | |||
3142 | } | |||
3143 | ||||
3144 | for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups) { | |||
3145 | ||||
3146 | // If the group has no read only accesses print the write accesses. | |||
3147 | if (Pair.second.empty()) { | |||
3148 | OS.indent(8) << "[["; | |||
3149 | for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) { | |||
3150 | OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second | |||
3151 | << ">"; | |||
3152 | } | |||
3153 | OS << " ]]\n"; | |||
3154 | } | |||
3155 | ||||
3156 | for (const MinMaxAccessTy &MMAReadOnly : Pair.second) { | |||
3157 | OS.indent(8) << "[["; | |||
3158 | OS << " <" << MMAReadOnly.first << ", " << MMAReadOnly.second << ">"; | |||
3159 | for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) { | |||
3160 | OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second | |||
3161 | << ">"; | |||
3162 | } | |||
3163 | OS << " ]]\n"; | |||
3164 | } | |||
3165 | } | |||
3166 | } | |||
3167 | ||||
3168 | void Scop::printStatements(raw_ostream &OS) const { | |||
3169 | OS << "Statements {\n"; | |||
3170 | ||||
3171 | for (const ScopStmt &Stmt : *this) | |||
3172 | OS.indent(4) << Stmt; | |||
3173 | ||||
3174 | OS.indent(4) << "}\n"; | |||
3175 | } | |||
3176 | ||||
3177 | void Scop::printArrayInfo(raw_ostream &OS) const { | |||
3178 | OS << "Arrays {\n"; | |||
3179 | ||||
3180 | for (auto &Array : arrays()) | |||
3181 | Array.second->print(OS); | |||
3182 | ||||
3183 | OS.indent(4) << "}\n"; | |||
3184 | ||||
3185 | OS.indent(4) << "Arrays (Bounds as pw_affs) {\n"; | |||
3186 | ||||
3187 | for (auto &Array : arrays()) | |||
3188 | Array.second->print(OS, /* SizeAsPwAff */ true); | |||
3189 | ||||
3190 | OS.indent(4) << "}\n"; | |||
3191 | } | |||
3192 | ||||
3193 | void Scop::print(raw_ostream &OS) const { | |||
3194 | OS.indent(4) << "Function: " << getRegion().getEntry()->getParent()->getName() | |||
3195 | << "\n"; | |||
3196 | OS.indent(4) << "Region: " << getNameStr() << "\n"; | |||
3197 | OS.indent(4) << "Max Loop Depth: " << getMaxLoopDepth() << "\n"; | |||
3198 | OS.indent(4) << "Invariant Accesses: {\n"; | |||
3199 | for (const auto &IAClass : InvariantEquivClasses) { | |||
3200 | const auto &MAs = std::get<1>(IAClass); | |||
3201 | if (MAs.empty()) { | |||
3202 | OS.indent(12) << "Class Pointer: " << *std::get<0>(IAClass) << "\n"; | |||
3203 | } else { | |||
3204 | MAs.front()->print(OS); | |||
3205 | OS.indent(12) << "Execution Context: " << std::get<2>(IAClass) << "\n"; | |||
3206 | } | |||
3207 | } | |||
3208 | OS.indent(4) << "}\n"; | |||
3209 | printContext(OS.indent(4)); | |||
3210 | printArrayInfo(OS.indent(4)); | |||
3211 | printAliasAssumptions(OS); | |||
3212 | printStatements(OS.indent(4)); | |||
3213 | } | |||
3214 | ||||
3215 | void Scop::dump() const { print(dbgs()); } | |||
3216 | ||||
3217 | isl_ctx *Scop::getIslCtx() const { return IslCtx; } | |||
3218 | ||||
3219 | __isl_give isl_pw_aff *Scop::getPwAff(const SCEV *E, BasicBlock *BB) { | |||
3220 | return Affinator.getPwAff(E, BB); | |||
3221 | } | |||
3222 | ||||
3223 | __isl_give isl_union_set *Scop::getDomains() const { | |||
3224 | isl_union_set *Domain = isl_union_set_empty(getParamSpace()); | |||
3225 | ||||
3226 | for (const ScopStmt &Stmt : *this) | |||
3227 | Domain = isl_union_set_add_set(Domain, Stmt.getDomain()); | |||
3228 | ||||
3229 | return Domain; | |||
3230 | } | |||
3231 | ||||
3232 | __isl_give isl_union_map * | |||
3233 | Scop::getAccessesOfType(std::function<bool(MemoryAccess &)> Predicate) { | |||
3234 | isl_union_map *Accesses = isl_union_map_empty(getParamSpace()); | |||
3235 | ||||
3236 | for (ScopStmt &Stmt : *this) { | |||
3237 | for (MemoryAccess *MA : Stmt) { | |||
3238 | if (!Predicate(*MA)) | |||
3239 | continue; | |||
3240 | ||||
3241 | isl_set *Domain = Stmt.getDomain(); | |||
3242 | isl_map *AccessDomain = MA->getAccessRelation(); | |||
3243 | AccessDomain = isl_map_intersect_domain(AccessDomain, Domain); | |||
3244 | Accesses = isl_union_map_add_map(Accesses, AccessDomain); | |||
3245 | } | |||
3246 | } | |||
3247 | return isl_union_map_coalesce(Accesses); | |||
3248 | } | |||
3249 | ||||
3250 | __isl_give isl_union_map *Scop::getMustWrites() { | |||
3251 | return getAccessesOfType([](MemoryAccess &MA) { return MA.isMustWrite(); }); | |||
3252 | } | |||
3253 | ||||
3254 | __isl_give isl_union_map *Scop::getMayWrites() { | |||
3255 | return getAccessesOfType([](MemoryAccess &MA) { return MA.isMayWrite(); }); | |||
3256 | } | |||
3257 | ||||
3258 | __isl_give isl_union_map *Scop::getWrites() { | |||
3259 | return getAccessesOfType([](MemoryAccess &MA) { return MA.isWrite(); }); | |||
3260 | } | |||
3261 | ||||
3262 | __isl_give isl_union_map *Scop::getReads() { | |||
3263 | return getAccessesOfType([](MemoryAccess &MA) { return MA.isRead(); }); | |||
3264 | } | |||
3265 | ||||
3266 | __isl_give isl_union_map *Scop::getAccesses() { | |||
3267 | return getAccessesOfType([](MemoryAccess &MA) { return true; }); | |||
3268 | } | |||
3269 | ||||
3270 | __isl_give isl_union_map *Scop::getSchedule() const { | |||
3271 | auto Tree = getScheduleTree(); | |||
3272 | auto S = isl_schedule_get_map(Tree); | |||
3273 | isl_schedule_free(Tree); | |||
3274 | return S; | |||
3275 | } | |||
3276 | ||||
3277 | __isl_give isl_schedule *Scop::getScheduleTree() const { | |||
3278 | return isl_schedule_intersect_domain(isl_schedule_copy(Schedule), | |||
3279 | getDomains()); | |||
3280 | } | |||
3281 | ||||
3282 | void Scop::setSchedule(__isl_take isl_union_map *NewSchedule) { | |||
3283 | auto *S = isl_schedule_from_domain(getDomains()); | |||
3284 | S = isl_schedule_insert_partial_schedule( | |||
3285 | S, isl_multi_union_pw_aff_from_union_map(NewSchedule)); | |||
3286 | isl_schedule_free(Schedule); | |||
3287 | Schedule = S; | |||
3288 | } | |||
3289 | ||||
3290 | void Scop::setScheduleTree(__isl_take isl_schedule *NewSchedule) { | |||
3291 | isl_schedule_free(Schedule); | |||
3292 | Schedule = NewSchedule; | |||
3293 | } | |||
3294 | ||||
3295 | bool Scop::restrictDomains(__isl_take isl_union_set *Domain) { | |||
3296 | bool Changed = false; | |||
3297 | for (ScopStmt &Stmt : *this) { | |||
3298 | isl_union_set *StmtDomain = isl_union_set_from_set(Stmt.getDomain()); | |||
3299 | isl_union_set *NewStmtDomain = isl_union_set_intersect( | |||
3300 | isl_union_set_copy(StmtDomain), isl_union_set_copy(Domain)); | |||
3301 | ||||
3302 | if (isl_union_set_is_subset(StmtDomain, NewStmtDomain)) { | |||
3303 | isl_union_set_free(StmtDomain); | |||
3304 | isl_union_set_free(NewStmtDomain); | |||
3305 | continue; | |||
3306 | } | |||
3307 | ||||
3308 | Changed = true; | |||
3309 | ||||
3310 | isl_union_set_free(StmtDomain); | |||
3311 | NewStmtDomain = isl_union_set_coalesce(NewStmtDomain); | |||
3312 | ||||
3313 | if (isl_union_set_is_empty(NewStmtDomain)) { | |||
3314 | Stmt.restrictDomain(isl_set_empty(Stmt.getDomainSpace())); | |||
3315 | isl_union_set_free(NewStmtDomain); | |||
3316 | } else | |||
3317 | Stmt.restrictDomain(isl_set_from_union_set(NewStmtDomain)); | |||
3318 | } | |||
3319 | isl_union_set_free(Domain); | |||
3320 | return Changed; | |||
3321 | } | |||
3322 | ||||
3323 | ScalarEvolution *Scop::getSE() const { return SE; } | |||
3324 | ||||
3325 | bool Scop::isIgnored(RegionNode *RN) { | |||
3326 | BasicBlock *BB = getRegionNodeBasicBlock(RN); | |||
3327 | ScopStmt *Stmt = getStmtForRegionNode(RN); | |||
3328 | ||||
3329 | // If there is no stmt, then it already has been removed. | |||
3330 | if (!Stmt) | |||
3331 | return true; | |||
3332 | ||||
3333 | // Check if there are accesses contained. | |||
3334 | if (Stmt->isEmpty()) | |||
3335 | return true; | |||
3336 | ||||
3337 | // Check for reachability via non-error blocks. | |||
3338 | if (!DomainMap.count(BB)) | |||
3339 | return true; | |||
3340 | ||||
3341 | // Check if error blocks are contained. | |||
3342 | if (containsErrorBlock(RN, getRegion(), LI, DT)) | |||
3343 | return true; | |||
3344 | ||||
3345 | return false; | |||
3346 | } | |||
3347 | ||||
3348 | struct MapToDimensionDataTy { | |||
3349 | int N; | |||
3350 | isl_union_pw_multi_aff *Res; | |||
3351 | }; | |||
3352 | ||||
3353 | // @brief Create a function that maps the elements of 'Set' to its N-th | |||
3354 | // dimension and add it to User->Res. | |||
3355 | // | |||
3356 | // @param Set The input set. | |||
3357 | // @param User->N The dimension to map to. | |||
3358 | // @param User->Res The isl_union_pw_multi_aff to which to add the result. | |||
3359 | // | |||
3360 | // @returns isl_stat_ok if no error occured, othewise isl_stat_error. | |||
3361 | static isl_stat mapToDimension_AddSet(__isl_take isl_set *Set, void *User) { | |||
3362 | struct MapToDimensionDataTy *Data = (struct MapToDimensionDataTy *)User; | |||
3363 | int Dim; | |||
3364 | isl_space *Space; | |||
3365 | isl_pw_multi_aff *PMA; | |||
3366 | ||||
3367 | Dim = isl_set_dim(Set, isl_dim_set); | |||
3368 | Space = isl_set_get_space(Set); | |||
3369 | PMA = isl_pw_multi_aff_project_out_map(Space, isl_dim_set, Data->N, | |||
3370 | Dim - Data->N); | |||
3371 | if (Data->N > 1) | |||
3372 | PMA = isl_pw_multi_aff_drop_dims(PMA, isl_dim_out, 0, Data->N - 1); | |||
3373 | Data->Res = isl_union_pw_multi_aff_add_pw_multi_aff(Data->Res, PMA); | |||
3374 | ||||
3375 | isl_set_free(Set); | |||
3376 | ||||
3377 | return isl_stat_ok; | |||
3378 | } | |||
3379 | ||||
3380 | // @brief Create an isl_multi_union_aff that defines an identity mapping | |||
3381 | // from the elements of USet to their N-th dimension. | |||
3382 | // | |||
3383 | // # Example: | |||
3384 | // | |||
3385 | // Domain: { A[i,j]; B[i,j,k] } | |||
3386 | // N: 1 | |||
3387 | // | |||
3388 | // Resulting Mapping: { {A[i,j] -> [(j)]; B[i,j,k] -> [(j)] } | |||
3389 | // | |||
3390 | // @param USet A union set describing the elements for which to generate a | |||
3391 | // mapping. | |||
3392 | // @param N The dimension to map to. | |||
3393 | // @returns A mapping from USet to its N-th dimension. | |||
3394 | static __isl_give isl_multi_union_pw_aff * | |||
3395 | mapToDimension(__isl_take isl_union_set *USet, int N) { | |||
3396 | assert(N >= 0)((N >= 0) ? static_cast<void> (0) : __assert_fail ("N >= 0" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3396, __PRETTY_FUNCTION__)); | |||
3397 | assert(USet)((USet) ? static_cast<void> (0) : __assert_fail ("USet" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3397, __PRETTY_FUNCTION__)); | |||
3398 | assert(!isl_union_set_is_empty(USet))((!isl_union_set_is_empty(USet)) ? static_cast<void> (0 ) : __assert_fail ("!isl_union_set_is_empty(USet)", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3398, __PRETTY_FUNCTION__)); | |||
3399 | ||||
3400 | struct MapToDimensionDataTy Data; | |||
3401 | ||||
3402 | auto *Space = isl_union_set_get_space(USet); | |||
3403 | auto *PwAff = isl_union_pw_multi_aff_empty(Space); | |||
3404 | ||||
3405 | Data = {N, PwAff}; | |||
3406 | ||||
3407 | auto Res = isl_union_set_foreach_set(USet, &mapToDimension_AddSet, &Data); | |||
3408 | ||||
3409 | assert(Res == isl_stat_ok)((Res == isl_stat_ok) ? static_cast<void> (0) : __assert_fail ("Res == isl_stat_ok", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3409, __PRETTY_FUNCTION__)); | |||
3410 | ||||
3411 | isl_union_set_free(USet); | |||
3412 | return isl_multi_union_pw_aff_from_union_pw_multi_aff(Data.Res); | |||
3413 | } | |||
3414 | ||||
3415 | void Scop::addScopStmt(BasicBlock *BB, Region *R) { | |||
3416 | if (BB) { | |||
3417 | Stmts.emplace_back(*this, *BB); | |||
3418 | auto Stmt = &Stmts.back(); | |||
3419 | StmtMap[BB] = Stmt; | |||
3420 | } else { | |||
3421 | assert(R && "Either basic block or a region expected.")((R && "Either basic block or a region expected.") ? static_cast <void> (0) : __assert_fail ("R && \"Either basic block or a region expected.\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3421, __PRETTY_FUNCTION__)); | |||
3422 | Stmts.emplace_back(*this, *R); | |||
3423 | auto Stmt = &Stmts.back(); | |||
3424 | for (BasicBlock *BB : R->blocks()) | |||
3425 | StmtMap[BB] = Stmt; | |||
3426 | } | |||
3427 | } | |||
3428 | ||||
3429 | void Scop::buildSchedule() { | |||
3430 | DenseMap<Loop *, std::pair<isl_schedule *, unsigned>> LoopSchedules; | |||
3431 | Loop *L = getLoopSurroundingRegion(getRegion(), LI); | |||
3432 | LoopSchedules[L]; | |||
3433 | buildSchedule(getRegion().getNode(), LoopSchedules); | |||
3434 | Schedule = LoopSchedules[L].first; | |||
3435 | } | |||
3436 | ||||
3437 | void Scop::buildSchedule( | |||
3438 | RegionNode *RN, | |||
3439 | DenseMap<Loop *, std::pair<isl_schedule *, unsigned>> &LoopSchedules) { | |||
3440 | ||||
3441 | if (RN->isSubRegion()) { | |||
3442 | auto *LocalRegion = RN->getNodeAs<Region>(); | |||
3443 | if (!SD.isNonAffineSubRegion(LocalRegion, &getRegion())) { | |||
3444 | ReversePostOrderTraversal<Region *> RTraversal(LocalRegion); | |||
3445 | for (auto *Child : RTraversal) | |||
3446 | buildSchedule(Child, LoopSchedules); | |||
3447 | return; | |||
3448 | } | |||
3449 | } | |||
3450 | ||||
3451 | Loop *L = getRegionNodeLoop(RN, LI); | |||
3452 | if (!getRegion().contains(L)) | |||
3453 | L = getLoopSurroundingRegion(getRegion(), LI); | |||
3454 | ||||
3455 | int LD = getRelativeLoopDepth(L); | |||
3456 | auto &LSchedulePair = LoopSchedules[L]; | |||
3457 | LSchedulePair.second += getNumBlocksInRegionNode(RN); | |||
3458 | ||||
3459 | ScopStmt *Stmt = getStmtForRegionNode(RN); | |||
3460 | if (Stmt) { | |||
3461 | auto *UDomain = isl_union_set_from_set(Stmt->getDomain()); | |||
3462 | auto *StmtSchedule = isl_schedule_from_domain(UDomain); | |||
3463 | LSchedulePair.first = combineInSequence(LSchedulePair.first, StmtSchedule); | |||
3464 | } | |||
3465 | ||||
3466 | isl_schedule *LSchedule = LSchedulePair.first; | |||
3467 | unsigned NumVisited = LSchedulePair.second; | |||
3468 | while (L && NumVisited == L->getNumBlocks()) { | |||
3469 | auto *PL = L->getParentLoop(); | |||
3470 | ||||
3471 | // Either we have a proper loop and we also build a schedule for the | |||
3472 | // parent loop or we have a infinite loop that does not have a proper | |||
3473 | // parent loop. In the former case this conditional will be skipped, in | |||
3474 | // the latter case however we will break here as we do not build a domain | |||
3475 | // nor a schedule for a infinite loop. | |||
3476 | assert(LoopSchedules.count(PL) || LSchedule == nullptr)((LoopSchedules.count(PL) || LSchedule == nullptr) ? static_cast <void> (0) : __assert_fail ("LoopSchedules.count(PL) || LSchedule == nullptr" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3476, __PRETTY_FUNCTION__)); | |||
3477 | if (!LoopSchedules.count(PL)) | |||
3478 | break; | |||
3479 | ||||
3480 | auto &PSchedulePair = LoopSchedules[PL]; | |||
3481 | ||||
3482 | if (LSchedule) { | |||
3483 | auto *LDomain = isl_schedule_get_domain(LSchedule); | |||
3484 | auto *MUPA = mapToDimension(LDomain, LD + 1); | |||
3485 | LSchedule = isl_schedule_insert_partial_schedule(LSchedule, MUPA); | |||
3486 | PSchedulePair.first = combineInSequence(PSchedulePair.first, LSchedule); | |||
3487 | } | |||
3488 | ||||
3489 | PSchedulePair.second += NumVisited; | |||
3490 | ||||
3491 | L = PL; | |||
3492 | LD--; | |||
3493 | NumVisited = PSchedulePair.second; | |||
3494 | LSchedule = PSchedulePair.first; | |||
3495 | } | |||
3496 | } | |||
3497 | ||||
3498 | ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const { | |||
3499 | auto StmtMapIt = StmtMap.find(BB); | |||
3500 | if (StmtMapIt == StmtMap.end()) | |||
3501 | return nullptr; | |||
3502 | return StmtMapIt->second; | |||
3503 | } | |||
3504 | ||||
3505 | ScopStmt *Scop::getStmtForRegionNode(RegionNode *RN) const { | |||
3506 | return getStmtForBasicBlock(getRegionNodeBasicBlock(RN)); | |||
3507 | } | |||
3508 | ||||
3509 | int Scop::getRelativeLoopDepth(const Loop *L) const { | |||
3510 | Loop *OuterLoop = | |||
3511 | L ? R.outermostLoopInRegion(const_cast<Loop *>(L)) : nullptr; | |||
3512 | if (!OuterLoop) | |||
3513 | return -1; | |||
3514 | return L->getLoopDepth() - OuterLoop->getLoopDepth(); | |||
3515 | } | |||
3516 | ||||
3517 | void ScopInfo::buildPHIAccesses(PHINode *PHI, Region &R, | |||
3518 | Region *NonAffineSubRegion, bool IsExitBlock) { | |||
3519 | ||||
3520 | // PHI nodes that are in the exit block of the region, hence if IsExitBlock is | |||
3521 | // true, are not modeled as ordinary PHI nodes as they are not part of the | |||
3522 | // region. However, we model the operands in the predecessor blocks that are | |||
3523 | // part of the region as regular scalar accesses. | |||
3524 | ||||
3525 | // If we can synthesize a PHI we can skip it, however only if it is in | |||
3526 | // the region. If it is not it can only be in the exit block of the region. | |||
3527 | // In this case we model the operands but not the PHI itself. | |||
3528 | if (!IsExitBlock && canSynthesize(PHI, LI, SE, &R)) | |||
3529 | return; | |||
3530 | ||||
3531 | // PHI nodes are modeled as if they had been demoted prior to the SCoP | |||
3532 | // detection. Hence, the PHI is a load of a new memory location in which the | |||
3533 | // incoming value was written at the end of the incoming basic block. | |||
3534 | bool OnlyNonAffineSubRegionOperands = true; | |||
3535 | for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) { | |||
3536 | Value *Op = PHI->getIncomingValue(u); | |||
3537 | BasicBlock *OpBB = PHI->getIncomingBlock(u); | |||
3538 | ||||
3539 | // Do not build scalar dependences inside a non-affine subregion. | |||
3540 | if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB)) | |||
3541 | continue; | |||
3542 | ||||
3543 | OnlyNonAffineSubRegionOperands = false; | |||
3544 | ||||
3545 | if (!R.contains(OpBB)) | |||
3546 | continue; | |||
3547 | ||||
3548 | Instruction *OpI = dyn_cast<Instruction>(Op); | |||
3549 | if (OpI) { | |||
3550 | BasicBlock *OpIBB = OpI->getParent(); | |||
3551 | // As we pretend there is a use (or more precise a write) of OpI in OpBB | |||
3552 | // we have to insert a scalar dependence from the definition of OpI to | |||
3553 | // OpBB if the definition is not in OpBB. | |||
3554 | if (scop->getStmtForBasicBlock(OpIBB) != | |||
3555 | scop->getStmtForBasicBlock(OpBB)) { | |||
3556 | addValueReadAccess(OpI, PHI, OpBB); | |||
3557 | addValueWriteAccess(OpI); | |||
3558 | } | |||
3559 | } else if (ModelReadOnlyScalars && !isa<Constant>(Op)) { | |||
3560 | addValueReadAccess(Op, PHI, OpBB); | |||
3561 | } | |||
3562 | ||||
3563 | addPHIWriteAccess(PHI, OpBB, Op, IsExitBlock); | |||
3564 | } | |||
3565 | ||||
3566 | if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) { | |||
3567 | addPHIReadAccess(PHI); | |||
3568 | } | |||
3569 | } | |||
3570 | ||||
3571 | bool ScopInfo::buildScalarDependences(Instruction *Inst, Region *R, | |||
3572 | Region *NonAffineSubRegion) { | |||
3573 | bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R); | |||
3574 | if (isIgnoredIntrinsic(Inst)) | |||
3575 | return false; | |||
3576 | ||||
3577 | bool AnyCrossStmtUse = false; | |||
3578 | BasicBlock *ParentBB = Inst->getParent(); | |||
3579 | ||||
3580 | for (User *U : Inst->users()) { | |||
3581 | Instruction *UI = dyn_cast<Instruction>(U); | |||
3582 | ||||
3583 | // Ignore the strange user | |||
3584 | if (UI == 0) | |||
3585 | continue; | |||
3586 | ||||
3587 | BasicBlock *UseParent = UI->getParent(); | |||
3588 | ||||
3589 | // Ignore basic block local uses. A value that is defined in a scop, but | |||
3590 | // used in a PHI node in the same basic block does not count as basic block | |||
3591 | // local, as for such cases a control flow edge is passed between definition | |||
3592 | // and use. | |||
3593 | if (UseParent == ParentBB && !isa<PHINode>(UI)) | |||
3594 | continue; | |||
3595 | ||||
3596 | // Uses by PHI nodes in the entry node count as external uses in case the | |||
3597 | // use is through an incoming block that is itself not contained in the | |||
3598 | // region. | |||
3599 | if (R->getEntry() == UseParent) { | |||
3600 | if (auto *PHI = dyn_cast<PHINode>(UI)) { | |||
3601 | bool ExternalUse = false; | |||
3602 | for (unsigned i = 0; i < PHI->getNumIncomingValues(); i++) { | |||
3603 | if (PHI->getIncomingValue(i) == Inst && | |||
3604 | !R->contains(PHI->getIncomingBlock(i))) { | |||
3605 | ExternalUse = true; | |||
3606 | break; | |||
3607 | } | |||
3608 | } | |||
3609 | ||||
3610 | if (ExternalUse) { | |||
3611 | AnyCrossStmtUse = true; | |||
3612 | continue; | |||
3613 | } | |||
3614 | } | |||
3615 | } | |||
3616 | ||||
3617 | // Do not build scalar dependences inside a non-affine subregion. | |||
3618 | if (NonAffineSubRegion && NonAffineSubRegion->contains(UseParent)) | |||
3619 | continue; | |||
3620 | ||||
3621 | // Check for PHI nodes in the region exit and skip them, if they will be | |||
3622 | // modeled as PHI nodes. | |||
3623 | // | |||
3624 | // PHI nodes in the region exit that have more than two incoming edges need | |||
3625 | // to be modeled as PHI-Nodes to correctly model the fact that depending on | |||
3626 | // the control flow a different value will be assigned to the PHI node. In | |||
3627 | // case this is the case, there is no need to create an additional normal | |||
3628 | // scalar dependence. Hence, bail out before we register an "out-of-region" | |||
3629 | // use for this definition. | |||
3630 | if (isa<PHINode>(UI) && UI->getParent() == R->getExit() && | |||
3631 | !R->getExitingBlock()) | |||
3632 | continue; | |||
3633 | ||||
3634 | // Check whether or not the use is in the SCoP. | |||
3635 | if (!R->contains(UseParent)) { | |||
3636 | AnyCrossStmtUse = true; | |||
3637 | continue; | |||
3638 | } | |||
3639 | ||||
3640 | // If the instruction can be synthesized and the user is in the region | |||
3641 | // we do not need to add scalar dependences. | |||
3642 | if (canSynthesizeInst) | |||
3643 | continue; | |||
3644 | ||||
3645 | // No need to translate these scalar dependences into polyhedral form, | |||
3646 | // because synthesizable scalars can be generated by the code generator. | |||
3647 | if (canSynthesize(UI, LI, SE, R)) | |||
3648 | continue; | |||
3649 | ||||
3650 | // Skip PHI nodes in the region as they handle their operands on their own. | |||
3651 | if (isa<PHINode>(UI)) | |||
3652 | continue; | |||
3653 | ||||
3654 | // Now U is used in another statement. | |||
3655 | AnyCrossStmtUse = true; | |||
3656 | ||||
3657 | // Do not build a read access that is not in the current SCoP | |||
3658 | // Use the def instruction as base address of the MemoryAccess, so that it | |||
3659 | // will become the name of the scalar access in the polyhedral form. | |||
3660 | addValueReadAccess(Inst, UI); | |||
3661 | } | |||
3662 | ||||
3663 | if (ModelReadOnlyScalars && !isa<PHINode>(Inst)) { | |||
3664 | for (Value *Op : Inst->operands()) { | |||
3665 | if (canSynthesize(Op, LI, SE, R)) | |||
3666 | continue; | |||
3667 | ||||
3668 | if (Instruction *OpInst = dyn_cast<Instruction>(Op)) | |||
3669 | if (R->contains(OpInst)) | |||
3670 | continue; | |||
3671 | ||||
3672 | if (isa<Constant>(Op)) | |||
3673 | continue; | |||
3674 | ||||
3675 | addValueReadAccess(Op, Inst); | |||
3676 | } | |||
3677 | } | |||
3678 | ||||
3679 | return AnyCrossStmtUse; | |||
3680 | } | |||
3681 | ||||
3682 | extern MapInsnToMemAcc InsnToMemAcc; | |||
3683 | ||||
3684 | void ScopInfo::buildMemoryAccess( | |||
3685 | Instruction *Inst, Loop *L, Region *R, | |||
3686 | const ScopDetection::BoxedLoopsSetTy *BoxedLoops, | |||
3687 | const InvariantLoadsSetTy &ScopRIL) { | |||
3688 | unsigned Size; | |||
3689 | Type *SizeType; | |||
3690 | Value *Val; | |||
3691 | enum MemoryAccess::AccessType Type; | |||
3692 | ||||
3693 | if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) { | |||
3694 | SizeType = Load->getType(); | |||
3695 | Size = TD->getTypeAllocSize(SizeType); | |||
3696 | Type = MemoryAccess::READ; | |||
3697 | Val = Load; | |||
3698 | } else { | |||
3699 | StoreInst *Store = cast<StoreInst>(Inst); | |||
3700 | SizeType = Store->getValueOperand()->getType(); | |||
3701 | Size = TD->getTypeAllocSize(SizeType); | |||
3702 | Type = MemoryAccess::MUST_WRITE; | |||
3703 | Val = Store->getValueOperand(); | |||
3704 | } | |||
3705 | ||||
3706 | auto Address = getPointerOperand(*Inst); | |||
3707 | ||||
3708 | const SCEV *AccessFunction = SE->getSCEVAtScope(Address, L); | |||
3709 | const SCEVUnknown *BasePointer = | |||
3710 | dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction)); | |||
3711 | ||||
3712 | assert(BasePointer && "Could not find base pointer")((BasePointer && "Could not find base pointer") ? static_cast <void> (0) : __assert_fail ("BasePointer && \"Could not find base pointer\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3712, __PRETTY_FUNCTION__)); | |||
3713 | AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer); | |||
3714 | ||||
3715 | if (isa<GetElementPtrInst>(Address) || isa<BitCastInst>(Address)) { | |||
3716 | auto NewAddress = Address; | |||
3717 | if (auto *BitCast = dyn_cast<BitCastInst>(Address)) { | |||
3718 | auto Src = BitCast->getOperand(0); | |||
3719 | auto SrcTy = Src->getType(); | |||
3720 | auto DstTy = BitCast->getType(); | |||
3721 | if (SrcTy->getPrimitiveSizeInBits() == DstTy->getPrimitiveSizeInBits()) | |||
3722 | NewAddress = Src; | |||
3723 | } | |||
3724 | ||||
3725 | if (auto *GEP = dyn_cast<GetElementPtrInst>(NewAddress)) { | |||
3726 | std::vector<const SCEV *> Subscripts; | |||
3727 | std::vector<int> Sizes; | |||
3728 | std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, *SE); | |||
3729 | auto BasePtr = GEP->getOperand(0); | |||
3730 | ||||
3731 | std::vector<const SCEV *> SizesSCEV; | |||
3732 | ||||
3733 | bool AllAffineSubcripts = true; | |||
3734 | for (auto Subscript : Subscripts) { | |||
3735 | InvariantLoadsSetTy AccessILS; | |||
3736 | AllAffineSubcripts = | |||
3737 | isAffineExpr(R, Subscript, *SE, nullptr, &AccessILS); | |||
3738 | ||||
3739 | for (LoadInst *LInst : AccessILS) | |||
3740 | if (!ScopRIL.count(LInst)) | |||
3741 | AllAffineSubcripts = false; | |||
3742 | ||||
3743 | if (!AllAffineSubcripts) | |||
3744 | break; | |||
3745 | } | |||
3746 | ||||
3747 | if (AllAffineSubcripts && Sizes.size() > 0) { | |||
3748 | for (auto V : Sizes) | |||
3749 | SizesSCEV.push_back(SE->getSCEV(ConstantInt::get( | |||
3750 | IntegerType::getInt64Ty(BasePtr->getContext()), V))); | |||
3751 | SizesSCEV.push_back(SE->getSCEV(ConstantInt::get( | |||
3752 | IntegerType::getInt64Ty(BasePtr->getContext()), Size))); | |||
3753 | ||||
3754 | addArrayAccess(Inst, Type, BasePointer->getValue(), Size, true, | |||
3755 | Subscripts, SizesSCEV, Val); | |||
3756 | return; | |||
3757 | } | |||
3758 | } | |||
3759 | } | |||
3760 | ||||
3761 | auto AccItr = InsnToMemAcc.find(Inst); | |||
3762 | if (PollyDelinearize && AccItr != InsnToMemAcc.end()) { | |||
3763 | addArrayAccess(Inst, Type, BasePointer->getValue(), Size, true, | |||
3764 | AccItr->second.DelinearizedSubscripts, | |||
3765 | AccItr->second.Shape->DelinearizedSizes, Val); | |||
3766 | return; | |||
3767 | } | |||
3768 | ||||
3769 | // Check if the access depends on a loop contained in a non-affine subregion. | |||
3770 | bool isVariantInNonAffineLoop = false; | |||
3771 | if (BoxedLoops) { | |||
3772 | SetVector<const Loop *> Loops; | |||
3773 | findLoops(AccessFunction, Loops); | |||
3774 | for (const Loop *L : Loops) | |||
3775 | if (BoxedLoops->count(L)) | |||
3776 | isVariantInNonAffineLoop = true; | |||
3777 | } | |||
3778 | ||||
3779 | InvariantLoadsSetTy AccessILS; | |||
3780 | bool IsAffine = | |||
3781 | !isVariantInNonAffineLoop && | |||
3782 | isAffineExpr(R, AccessFunction, *SE, BasePointer->getValue(), &AccessILS); | |||
3783 | ||||
3784 | for (LoadInst *LInst : AccessILS) | |||
3785 | if (!ScopRIL.count(LInst)) | |||
3786 | IsAffine = false; | |||
3787 | ||||
3788 | // FIXME: Size of the number of bytes of an array element, not the number of | |||
3789 | // elements as probably intended here. | |||
3790 | const SCEV *SizeSCEV = | |||
3791 | SE->getConstant(TD->getIntPtrType(Inst->getContext()), Size); | |||
3792 | ||||
3793 | if (!IsAffine && Type == MemoryAccess::MUST_WRITE) | |||
3794 | Type = MemoryAccess::MAY_WRITE; | |||
3795 | ||||
3796 | addArrayAccess(Inst, Type, BasePointer->getValue(), Size, IsAffine, | |||
3797 | ArrayRef<const SCEV *>(AccessFunction), | |||
3798 | ArrayRef<const SCEV *>(SizeSCEV), Val); | |||
3799 | } | |||
3800 | ||||
3801 | void ScopInfo::buildAccessFunctions(Region &R, Region &SR) { | |||
3802 | ||||
3803 | if (SD->isNonAffineSubRegion(&SR, &R)) { | |||
3804 | for (BasicBlock *BB : SR.blocks()) | |||
3805 | buildAccessFunctions(R, *BB, &SR); | |||
3806 | return; | |||
3807 | } | |||
3808 | ||||
3809 | for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I) | |||
3810 | if (I->isSubRegion()) | |||
3811 | buildAccessFunctions(R, *I->getNodeAs<Region>()); | |||
3812 | else | |||
3813 | buildAccessFunctions(R, *I->getNodeAs<BasicBlock>()); | |||
3814 | } | |||
3815 | ||||
3816 | void ScopInfo::buildStmts(Region &SR) { | |||
3817 | Region *R = getRegion(); | |||
3818 | ||||
3819 | if (SD->isNonAffineSubRegion(&SR, R)) { | |||
3820 | scop->addScopStmt(nullptr, &SR); | |||
3821 | return; | |||
3822 | } | |||
3823 | ||||
3824 | for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I) | |||
3825 | if (I->isSubRegion()) | |||
3826 | buildStmts(*I->getNodeAs<Region>()); | |||
3827 | else | |||
3828 | scop->addScopStmt(I->getNodeAs<BasicBlock>(), nullptr); | |||
3829 | } | |||
3830 | ||||
3831 | void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB, | |||
3832 | Region *NonAffineSubRegion, | |||
3833 | bool IsExitBlock) { | |||
3834 | // We do not build access functions for error blocks, as they may contain | |||
3835 | // instructions we can not model. | |||
3836 | DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); | |||
3837 | if (isErrorBlock(BB, R, *LI, DT) && !IsExitBlock) | |||
3838 | return; | |||
3839 | ||||
3840 | Loop *L = LI->getLoopFor(&BB); | |||
3841 | ||||
3842 | // The set of loops contained in non-affine subregions that are part of R. | |||
3843 | const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R); | |||
3844 | ||||
3845 | // The set of loads that are required to be invariant. | |||
3846 | auto &ScopRIL = *SD->getRequiredInvariantLoads(&R); | |||
3847 | ||||
3848 | for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) { | |||
3849 | Instruction *Inst = &*I; | |||
3850 | ||||
3851 | PHINode *PHI = dyn_cast<PHINode>(Inst); | |||
3852 | if (PHI) | |||
3853 | buildPHIAccesses(PHI, R, NonAffineSubRegion, IsExitBlock); | |||
3854 | ||||
3855 | // For the exit block we stop modeling after the last PHI node. | |||
3856 | if (!PHI && IsExitBlock) | |||
3857 | break; | |||
3858 | ||||
3859 | // TODO: At this point we only know that elements of ScopRIL have to be | |||
3860 | // invariant and will be hoisted for the SCoP to be processed. Though, | |||
3861 | // there might be other invariant accesses that will be hoisted and | |||
3862 | // that would allow to make a non-affine access affine. | |||
3863 | if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst)) | |||
3864 | buildMemoryAccess(Inst, L, &R, BoxedLoops, ScopRIL); | |||
3865 | ||||
3866 | if (isIgnoredIntrinsic(Inst)) | |||
3867 | continue; | |||
3868 | ||||
3869 | // Do not build scalar dependences for required invariant loads as we will | |||
3870 | // hoist them later on anyway or drop the SCoP if we cannot. | |||
3871 | if (ScopRIL.count(dyn_cast<LoadInst>(Inst))) | |||
3872 | continue; | |||
3873 | ||||
3874 | if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) { | |||
3875 | if (!isa<StoreInst>(Inst)) | |||
3876 | addValueWriteAccess(Inst); | |||
3877 | } | |||
3878 | } | |||
3879 | } | |||
3880 | ||||
3881 | void ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst, | |||
3882 | MemoryAccess::AccessType Type, | |||
3883 | Value *BaseAddress, unsigned ElemBytes, | |||
3884 | bool Affine, Value *AccessValue, | |||
3885 | ArrayRef<const SCEV *> Subscripts, | |||
3886 | ArrayRef<const SCEV *> Sizes, | |||
3887 | ScopArrayInfo::MemoryKind Kind) { | |||
3888 | ScopStmt *Stmt = scop->getStmtForBasicBlock(BB); | |||
3889 | ||||
3890 | // Do not create a memory access for anything not in the SCoP. It would be | |||
3891 | // ignored anyway. | |||
3892 | if (!Stmt) | |||
3893 | return; | |||
3894 | ||||
3895 | AccFuncSetType &AccList = AccFuncMap[BB]; | |||
3896 | Value *BaseAddr = BaseAddress; | |||
3897 | std::string BaseName = getIslCompatibleName("MemRef_", BaseAddr, ""); | |||
3898 | ||||
3899 | bool isKnownMustAccess = false; | |||
3900 | ||||
3901 | // Accesses in single-basic block statements are always excuted. | |||
3902 | if (Stmt->isBlockStmt()) | |||
3903 | isKnownMustAccess = true; | |||
3904 | ||||
3905 | if (Stmt->isRegionStmt()) { | |||
3906 | // Accesses that dominate the exit block of a non-affine region are always | |||
3907 | // executed. In non-affine regions there may exist MK_Values that do not | |||
3908 | // dominate the exit. MK_Values will always dominate the exit and MK_PHIs | |||
3909 | // only if there is at most one PHI_WRITE in the non-affine region. | |||
3910 | if (DT->dominates(BB, Stmt->getRegion()->getExit())) | |||
3911 | isKnownMustAccess = true; | |||
3912 | } | |||
3913 | ||||
3914 | if (!isKnownMustAccess && Type == MemoryAccess::MUST_WRITE) | |||
3915 | Type = MemoryAccess::MAY_WRITE; | |||
3916 | ||||
3917 | AccList.emplace_back(Stmt, Inst, Type, BaseAddress, ElemBytes, Affine, | |||
3918 | Subscripts, Sizes, AccessValue, Kind, BaseName); | |||
3919 | Stmt->addAccess(&AccList.back()); | |||
3920 | } | |||
3921 | ||||
3922 | void ScopInfo::addArrayAccess(Instruction *MemAccInst, | |||
3923 | MemoryAccess::AccessType Type, Value *BaseAddress, | |||
3924 | unsigned ElemBytes, bool IsAffine, | |||
3925 | ArrayRef<const SCEV *> Subscripts, | |||
3926 | ArrayRef<const SCEV *> Sizes, | |||
3927 | Value *AccessValue) { | |||
3928 | assert(isa<LoadInst>(MemAccInst) || isa<StoreInst>(MemAccInst))((isa<LoadInst>(MemAccInst) || isa<StoreInst>(MemAccInst )) ? static_cast<void> (0) : __assert_fail ("isa<LoadInst>(MemAccInst) || isa<StoreInst>(MemAccInst)" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3928, __PRETTY_FUNCTION__)); | |||
3929 | assert(isa<LoadInst>(MemAccInst) == (Type == MemoryAccess::READ))((isa<LoadInst>(MemAccInst) == (Type == MemoryAccess::READ )) ? static_cast<void> (0) : __assert_fail ("isa<LoadInst>(MemAccInst) == (Type == MemoryAccess::READ)" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3929, __PRETTY_FUNCTION__)); | |||
3930 | addMemoryAccess(MemAccInst->getParent(), MemAccInst, Type, BaseAddress, | |||
3931 | ElemBytes, IsAffine, AccessValue, Subscripts, Sizes, | |||
3932 | ScopArrayInfo::MK_Array); | |||
3933 | } | |||
3934 | void ScopInfo::addValueWriteAccess(Instruction *Value) { | |||
3935 | addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value, 1, | |||
3936 | true, Value, ArrayRef<const SCEV *>(), | |||
3937 | ArrayRef<const SCEV *>(), ScopArrayInfo::MK_Value); | |||
3938 | } | |||
3939 | void ScopInfo::addValueReadAccess(Value *Value, Instruction *User) { | |||
3940 | assert(!isa<PHINode>(User))((!isa<PHINode>(User)) ? static_cast<void> (0) : __assert_fail ("!isa<PHINode>(User)", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/Analysis/ScopInfo.cpp" , 3940, __PRETTY_FUNCTION__)); | |||
3941 | addMemoryAccess(User->getParent(), User, MemoryAccess::READ, Value, 1, true, | |||
3942 | Value, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(), | |||
3943 | ScopArrayInfo::MK_Value); | |||
3944 | } | |||
3945 | void ScopInfo::addValueReadAccess(Value *Value, PHINode *User, | |||
3946 | BasicBlock *UserBB) { | |||
3947 | addMemoryAccess(UserBB, User, MemoryAccess::READ, Value, 1, true, Value, | |||
3948 | ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(), | |||
3949 | ScopArrayInfo::MK_Value); | |||
3950 | } | |||
3951 | void ScopInfo::addPHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock, | |||
3952 | Value *IncomingValue, bool IsExitBlock) { | |||
3953 | addMemoryAccess(IncomingBlock, IncomingBlock->getTerminator(), | |||
3954 | MemoryAccess::MUST_WRITE, PHI, 1, true, IncomingValue, | |||
3955 | ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(), | |||
3956 | IsExitBlock ? ScopArrayInfo::MK_ExitPHI | |||
3957 | : ScopArrayInfo::MK_PHI); | |||
3958 | } | |||
3959 | void ScopInfo::addPHIReadAccess(PHINode *PHI) { | |||
3960 | addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI, | |||
3961 | ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(), | |||
3962 | ScopArrayInfo::MK_PHI); | |||
3963 | } | |||
3964 | ||||
3965 | void ScopInfo::buildScop(Region &R, AssumptionCache &AC) { | |||
3966 | unsigned MaxLoopDepth = getMaxLoopDepthInRegion(R, *LI, *SD); | |||
3967 | scop = new Scop(R, AccFuncMap, *SD, *SE, *DT, *LI, ctx, MaxLoopDepth); | |||
3968 | ||||
3969 | buildStmts(R); | |||
3970 | buildAccessFunctions(R, R); | |||
3971 | ||||
3972 | // In case the region does not have an exiting block we will later (during | |||
3973 | // code generation) split the exit block. This will move potential PHI nodes | |||
3974 | // from the current exit block into the new region exiting block. Hence, PHI | |||
3975 | // nodes that are at this point not part of the region will be. | |||
3976 | // To handle these PHI nodes later we will now model their operands as scalar | |||
3977 | // accesses. Note that we do not model anything in the exit block if we have | |||
3978 | // an exiting block in the region, as there will not be any splitting later. | |||
3979 | if (!R.getExitingBlock()) | |||
3980 | buildAccessFunctions(R, *R.getExit(), nullptr, /* IsExitBlock */ true); | |||
3981 | ||||
3982 | scop->init(*AA, AC); | |||
3983 | } | |||
3984 | ||||
3985 | void ScopInfo::print(raw_ostream &OS, const Module *) const { | |||
3986 | if (!scop) { | |||
3987 | OS << "Invalid Scop!\n"; | |||
3988 | return; | |||
3989 | } | |||
3990 | ||||
3991 | scop->print(OS); | |||
3992 | } | |||
3993 | ||||
3994 | void ScopInfo::clear() { | |||
3995 | AccFuncMap.clear(); | |||
3996 | if (scop) { | |||
3997 | delete scop; | |||
3998 | scop = 0; | |||
3999 | } | |||
4000 | } | |||
4001 | ||||
4002 | //===----------------------------------------------------------------------===// | |||
4003 | ScopInfo::ScopInfo() : RegionPass(ID), scop(0) { | |||
4004 | ctx = isl_ctx_alloc(); | |||
4005 | isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT2); | |||
4006 | } | |||
4007 | ||||
4008 | ScopInfo::~ScopInfo() { | |||
4009 | clear(); | |||
4010 | isl_ctx_free(ctx); | |||
4011 | } | |||
4012 | ||||
4013 | void ScopInfo::getAnalysisUsage(AnalysisUsage &AU) const { | |||
4014 | AU.addRequired<LoopInfoWrapperPass>(); | |||
4015 | AU.addRequired<RegionInfoPass>(); | |||
4016 | AU.addRequired<DominatorTreeWrapperPass>(); | |||
4017 | AU.addRequiredTransitive<ScalarEvolutionWrapperPass>(); | |||
4018 | AU.addRequiredTransitive<ScopDetection>(); | |||
4019 | AU.addRequired<AAResultsWrapperPass>(); | |||
4020 | AU.addRequired<AssumptionCacheTracker>(); | |||
4021 | AU.setPreservesAll(); | |||
4022 | } | |||
4023 | ||||
4024 | bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) { | |||
4025 | SD = &getAnalysis<ScopDetection>(); | |||
4026 | ||||
4027 | if (!SD->isMaxRegionInScop(*R)) | |||
4028 | return false; | |||
4029 | ||||
4030 | Function *F = R->getEntry()->getParent(); | |||
4031 | SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); | |||
4032 | LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); | |||
4033 | AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); | |||
4034 | TD = &F->getParent()->getDataLayout(); | |||
4035 | DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); | |||
4036 | auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(*F); | |||
4037 | ||||
4038 | DebugLoc Beg, End; | |||
4039 | getDebugLocations(R, Beg, End); | |||
4040 | std::string Msg = "SCoP begins here."; | |||
4041 | emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE"polly-scops", *F, Beg, Msg); | |||
4042 | ||||
4043 | buildScop(*R, AC); | |||
4044 | ||||
4045 | DEBUG(scop->print(dbgs()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("polly-scops")) { scop->print(dbgs()); } } while (0); | |||
4046 | ||||
4047 | if (scop->isEmpty() || !scop->hasFeasibleRuntimeContext()) { | |||
4048 | Msg = "SCoP ends here but was dismissed."; | |||
4049 | delete scop; | |||
4050 | scop = nullptr; | |||
4051 | } else { | |||
4052 | Msg = "SCoP ends here."; | |||
4053 | ++ScopFound; | |||
4054 | if (scop->getMaxLoopDepth() > 0) | |||
4055 | ++RichScopFound; | |||
4056 | } | |||
4057 | ||||
4058 | emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE"polly-scops", *F, End, Msg); | |||
4059 | ||||
4060 | return false; | |||
4061 | } | |||
4062 | ||||
4063 | char ScopInfo::ID = 0; | |||
4064 | ||||
4065 | Pass *polly::createScopInfoPass() { return new ScopInfo(); } | |||
4066 | ||||
4067 | INITIALIZE_PASS_BEGIN(ScopInfo, "polly-scops",static void* initializeScopInfoPassOnce(PassRegistry &Registry ) { | |||
4068 | "Polly - Create polyhedral description of Scops", false,static void* initializeScopInfoPassOnce(PassRegistry &Registry ) { | |||
4069 | false)static void* initializeScopInfoPassOnce(PassRegistry &Registry ) {; | |||
4070 | INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);; | |||
4071 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry);; | |||
4072 | INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)initializeLoopInfoWrapperPassPass(Registry);; | |||
4073 | INITIALIZE_PASS_DEPENDENCY(RegionInfoPass)initializeRegionInfoPassPass(Registry);; | |||
4074 | INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)initializeScalarEvolutionWrapperPassPass(Registry);; | |||
4075 | INITIALIZE_PASS_DEPENDENCY(ScopDetection)initializeScopDetectionPass(Registry);; | |||
4076 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);; | |||
4077 | INITIALIZE_PASS_END(ScopInfo, "polly-scops",PassInfo *PI = new PassInfo("Polly - Create polyhedral description of Scops" , "polly-scops", & ScopInfo ::ID, PassInfo::NormalCtor_t( callDefaultCtor< ScopInfo >), false, false); Registry.registerPass (*PI, true); return PI; } void llvm::initializeScopInfoPass(PassRegistry &Registry) { static volatile sys::cas_flag initialized = 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized , 1, 0); if (old_val == 0) { initializeScopInfoPassOnce(Registry ); sys::MemoryFence(); ; ; initialized = 2; ; } else { sys::cas_flag tmp = initialized; sys::MemoryFence(); while (tmp != 2) { tmp = initialized; sys::MemoryFence(); } } ; } | |||
4078 | "Polly - Create polyhedral description of Scops", false,PassInfo *PI = new PassInfo("Polly - Create polyhedral description of Scops" , "polly-scops", & ScopInfo ::ID, PassInfo::NormalCtor_t( callDefaultCtor< ScopInfo >), false, false); Registry.registerPass (*PI, true); return PI; } void llvm::initializeScopInfoPass(PassRegistry &Registry) { static volatile sys::cas_flag initialized = 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized , 1, 0); if (old_val == 0) { initializeScopInfoPassOnce(Registry ); sys::MemoryFence(); ; ; initialized = 2; ; } else { sys::cas_flag tmp = initialized; sys::MemoryFence(); while (tmp != 2) { tmp = initialized; sys::MemoryFence(); } } ; } | |||
4079 | false)PassInfo *PI = new PassInfo("Polly - Create polyhedral description of Scops" , "polly-scops", & ScopInfo ::ID, PassInfo::NormalCtor_t( callDefaultCtor< ScopInfo >), false, false); Registry.registerPass (*PI, true); return PI; } void llvm::initializeScopInfoPass(PassRegistry &Registry) { static volatile sys::cas_flag initialized = 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized , 1, 0); if (old_val == 0) { initializeScopInfoPassOnce(Registry ); sys::MemoryFence(); ; ; initialized = 2; ; } else { sys::cas_flag tmp = initialized; sys::MemoryFence(); while (tmp != 2) { tmp = initialized; sys::MemoryFence(); } } ; } |