Bug Summary

File:tools/polly/lib/CodeGen/IslNodeBuilder.cpp
Warning:line 1066, column 10
Value stored to 'size' during its initialization is never read

Annotated Source Code

1//===------ IslNodeBuilder.cpp - Translate an isl AST into a LLVM-IR AST---===//
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// This file contains the IslNodeBuilder, a class to translate an isl AST into
11// a LLVM-IR AST.
12//
13//===----------------------------------------------------------------------===//
14
15#include "polly/CodeGen/IslNodeBuilder.h"
16#include "polly/CodeGen/BlockGenerators.h"
17#include "polly/CodeGen/CodeGeneration.h"
18#include "polly/CodeGen/IslAst.h"
19#include "polly/CodeGen/IslExprBuilder.h"
20#include "polly/CodeGen/LoopGenerators.h"
21#include "polly/CodeGen/RuntimeDebugBuilder.h"
22#include "polly/CodeGen/Utils.h"
23#include "polly/Config/config.h"
24#include "polly/DependenceInfo.h"
25#include "polly/LinkAllPasses.h"
26#include "polly/Options.h"
27#include "polly/ScopInfo.h"
28#include "polly/Support/GICHelper.h"
29#include "polly/Support/SCEVValidator.h"
30#include "polly/Support/ScopHelper.h"
31#include "llvm/ADT/PostOrderIterator.h"
32#include "llvm/ADT/SmallPtrSet.h"
33#include "llvm/Analysis/LoopInfo.h"
34#include "llvm/IR/DataLayout.h"
35#include "llvm/IR/Module.h"
36#include "llvm/IR/Verifier.h"
37#include "llvm/Support/CommandLine.h"
38#include "llvm/Support/Debug.h"
39#include "llvm/Transforms/Utils/BasicBlockUtils.h"
40#include "isl/aff.h"
41#include "isl/ast.h"
42#include "isl/ast_build.h"
43#include "isl/list.h"
44#include "isl/map.h"
45#include "isl/set.h"
46#include "isl/union_map.h"
47#include "isl/union_set.h"
48
49using namespace polly;
50using namespace llvm;
51
52#define DEBUG_TYPE"polly-codegen" "polly-codegen"
53
54STATISTIC(VersionedScops, "Number of SCoPs that required versioning.")static llvm::Statistic VersionedScops = {"polly-codegen", "VersionedScops"
, "Number of SCoPs that required versioning.", {0}, false}
;
55
56// The maximal number of dimensions we allow during invariant load construction.
57// More complex access ranges will result in very high compile time and are also
58// unlikely to result in good code. This value is very high and should only
59// trigger for corner cases (e.g., the "dct_luma" function in h264, SPEC2006).
60static int const MaxDimensionsInAccessRange = 9;
61
62static cl::opt<bool> PollyGenerateRTCPrint(
63 "polly-codegen-emit-rtc-print",
64 cl::desc("Emit code that prints the runtime check result dynamically."),
65 cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
66
67// If this option is set we always use the isl AST generator to regenerate
68// memory accesses. Without this option set we regenerate expressions using the
69// original SCEV expressions and only generate new expressions in case the
70// access relation has been changed and consequently must be regenerated.
71static cl::opt<bool> PollyGenerateExpressions(
72 "polly-codegen-generate-expressions",
73 cl::desc("Generate AST expressions for unmodified and modified accesses"),
74 cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
75
76static cl::opt<int> PollyTargetFirstLevelCacheLineSize(
77 "polly-target-first-level-cache-line-size",
78 cl::desc("The size of the first level cache line size specified in bytes."),
79 cl::Hidden, cl::init(64), cl::ZeroOrMore, cl::cat(PollyCategory));
80
81__isl_give isl_ast_expr *
82IslNodeBuilder::getUpperBound(__isl_keep isl_ast_node *For,
83 ICmpInst::Predicate &Predicate) {
84 isl_id *UBID, *IteratorID;
85 isl_ast_expr *Cond, *Iterator, *UB, *Arg0;
86 isl_ast_op_type Type;
87
88 Cond = isl_ast_node_for_get_cond(For);
89 Iterator = isl_ast_node_for_get_iterator(For);
90 isl_ast_expr_get_type(Cond);
91 assert(isl_ast_expr_get_type(Cond) == isl_ast_expr_op &&((isl_ast_expr_get_type(Cond) == isl_ast_expr_op && "conditional expression is not an atomic upper bound"
) ? static_cast<void> (0) : __assert_fail ("isl_ast_expr_get_type(Cond) == isl_ast_expr_op && \"conditional expression is not an atomic upper bound\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 92, __PRETTY_FUNCTION__))
92 "conditional expression is not an atomic upper bound")((isl_ast_expr_get_type(Cond) == isl_ast_expr_op && "conditional expression is not an atomic upper bound"
) ? static_cast<void> (0) : __assert_fail ("isl_ast_expr_get_type(Cond) == isl_ast_expr_op && \"conditional expression is not an atomic upper bound\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 92, __PRETTY_FUNCTION__))
;
93
94 Type = isl_ast_expr_get_op_type(Cond);
95
96 switch (Type) {
97 case isl_ast_op_le:
98 Predicate = ICmpInst::ICMP_SLE;
99 break;
100 case isl_ast_op_lt:
101 Predicate = ICmpInst::ICMP_SLT;
102 break;
103 default:
104 llvm_unreachable("Unexpected comparison type in loop condition")::llvm::llvm_unreachable_internal("Unexpected comparison type in loop condition"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 104)
;
105 }
106
107 Arg0 = isl_ast_expr_get_op_arg(Cond, 0);
108
109 assert(isl_ast_expr_get_type(Arg0) == isl_ast_expr_id &&((isl_ast_expr_get_type(Arg0) == isl_ast_expr_id && "conditional expression is not an atomic upper bound"
) ? static_cast<void> (0) : __assert_fail ("isl_ast_expr_get_type(Arg0) == isl_ast_expr_id && \"conditional expression is not an atomic upper bound\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 110, __PRETTY_FUNCTION__))
110 "conditional expression is not an atomic upper bound")((isl_ast_expr_get_type(Arg0) == isl_ast_expr_id && "conditional expression is not an atomic upper bound"
) ? static_cast<void> (0) : __assert_fail ("isl_ast_expr_get_type(Arg0) == isl_ast_expr_id && \"conditional expression is not an atomic upper bound\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 110, __PRETTY_FUNCTION__))
;
111
112 UBID = isl_ast_expr_get_id(Arg0);
113
114 assert(isl_ast_expr_get_type(Iterator) == isl_ast_expr_id &&((isl_ast_expr_get_type(Iterator) == isl_ast_expr_id &&
"Could not get the iterator") ? static_cast<void> (0) :
__assert_fail ("isl_ast_expr_get_type(Iterator) == isl_ast_expr_id && \"Could not get the iterator\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 115, __PRETTY_FUNCTION__))
115 "Could not get the iterator")((isl_ast_expr_get_type(Iterator) == isl_ast_expr_id &&
"Could not get the iterator") ? static_cast<void> (0) :
__assert_fail ("isl_ast_expr_get_type(Iterator) == isl_ast_expr_id && \"Could not get the iterator\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 115, __PRETTY_FUNCTION__))
;
116
117 IteratorID = isl_ast_expr_get_id(Iterator);
118
119 assert(UBID == IteratorID &&((UBID == IteratorID && "conditional expression is not an atomic upper bound"
) ? static_cast<void> (0) : __assert_fail ("UBID == IteratorID && \"conditional expression is not an atomic upper bound\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 120, __PRETTY_FUNCTION__))
120 "conditional expression is not an atomic upper bound")((UBID == IteratorID && "conditional expression is not an atomic upper bound"
) ? static_cast<void> (0) : __assert_fail ("UBID == IteratorID && \"conditional expression is not an atomic upper bound\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 120, __PRETTY_FUNCTION__))
;
121
122 UB = isl_ast_expr_get_op_arg(Cond, 1);
123
124 isl_ast_expr_free(Cond);
125 isl_ast_expr_free(Iterator);
126 isl_ast_expr_free(Arg0);
127 isl_id_free(IteratorID);
128 isl_id_free(UBID);
129
130 return UB;
131}
132
133/// Return true if a return value of Predicate is true for the value represented
134/// by passed isl_ast_expr_int.
135static bool checkIslAstExprInt(__isl_take isl_ast_expr *Expr,
136 isl_bool (*Predicate)(__isl_keep isl_val *)) {
137 if (isl_ast_expr_get_type(Expr) != isl_ast_expr_int) {
138 isl_ast_expr_free(Expr);
139 return false;
140 }
141 auto ExprVal = isl_ast_expr_get_val(Expr);
142 isl_ast_expr_free(Expr);
143 if (Predicate(ExprVal) != true) {
144 isl_val_free(ExprVal);
145 return false;
146 }
147 isl_val_free(ExprVal);
148 return true;
149}
150
151int IslNodeBuilder::getNumberOfIterations(__isl_keep isl_ast_node *For) {
152 assert(isl_ast_node_get_type(For) == isl_ast_node_for)((isl_ast_node_get_type(For) == isl_ast_node_for) ? static_cast
<void> (0) : __assert_fail ("isl_ast_node_get_type(For) == isl_ast_node_for"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 152, __PRETTY_FUNCTION__))
;
153 auto Body = isl_ast_node_for_get_body(For);
154
155 // First, check if we can actually handle this code.
156 switch (isl_ast_node_get_type(Body)) {
157 case isl_ast_node_user:
158 break;
159 case isl_ast_node_block: {
160 isl_ast_node_list *List = isl_ast_node_block_get_children(Body);
161 for (int i = 0; i < isl_ast_node_list_n_ast_node(List); ++i) {
162 isl_ast_node *Node = isl_ast_node_list_get_ast_node(List, i);
163 int Type = isl_ast_node_get_type(Node);
164 isl_ast_node_free(Node);
165 if (Type != isl_ast_node_user) {
166 isl_ast_node_list_free(List);
167 isl_ast_node_free(Body);
168 return -1;
169 }
170 }
171 isl_ast_node_list_free(List);
172 break;
173 }
174 default:
175 isl_ast_node_free(Body);
176 return -1;
177 }
178 isl_ast_node_free(Body);
179
180 auto Init = isl_ast_node_for_get_init(For);
181 if (!checkIslAstExprInt(Init, isl_val_is_zero))
182 return -1;
183 auto Inc = isl_ast_node_for_get_inc(For);
184 if (!checkIslAstExprInt(Inc, isl_val_is_one))
185 return -1;
186 CmpInst::Predicate Predicate;
187 auto UB = getUpperBound(For, Predicate);
188 if (isl_ast_expr_get_type(UB) != isl_ast_expr_int) {
189 isl_ast_expr_free(UB);
190 return -1;
191 }
192 auto UpVal = isl_ast_expr_get_val(UB);
193 isl_ast_expr_free(UB);
194 int NumberIterations = isl_val_get_num_si(UpVal);
195 isl_val_free(UpVal);
196 if (NumberIterations < 0)
197 return -1;
198 if (Predicate == CmpInst::ICMP_SLT)
199 return NumberIterations;
200 else
201 return NumberIterations + 1;
202}
203
204/// Extract the values and SCEVs needed to generate code for a block.
205static int findReferencesInBlock(struct SubtreeReferences &References,
206 const ScopStmt *Stmt, const BasicBlock *BB) {
207 for (const Instruction &Inst : *BB)
208 for (Value *SrcVal : Inst.operands()) {
209 auto *Scope = References.LI.getLoopFor(BB);
210 if (canSynthesize(SrcVal, References.S, &References.SE, Scope)) {
211 References.SCEVs.insert(References.SE.getSCEVAtScope(SrcVal, Scope));
212 continue;
213 } else if (Value *NewVal = References.GlobalMap.lookup(SrcVal))
214 References.Values.insert(NewVal);
215 }
216 return 0;
217}
218
219isl_stat addReferencesFromStmt(const ScopStmt *Stmt, void *UserPtr,
220 bool CreateScalarRefs) {
221 auto &References = *static_cast<struct SubtreeReferences *>(UserPtr);
222
223 if (Stmt->isBlockStmt())
224 findReferencesInBlock(References, Stmt, Stmt->getBasicBlock());
225 else {
226 assert(Stmt->isRegionStmt() &&((Stmt->isRegionStmt() && "Stmt was neither block nor region statement"
) ? static_cast<void> (0) : __assert_fail ("Stmt->isRegionStmt() && \"Stmt was neither block nor region statement\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 227, __PRETTY_FUNCTION__))
227 "Stmt was neither block nor region statement")((Stmt->isRegionStmt() && "Stmt was neither block nor region statement"
) ? static_cast<void> (0) : __assert_fail ("Stmt->isRegionStmt() && \"Stmt was neither block nor region statement\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 227, __PRETTY_FUNCTION__))
;
228 for (const BasicBlock *BB : Stmt->getRegion()->blocks())
229 findReferencesInBlock(References, Stmt, BB);
230 }
231
232 for (auto &Access : *Stmt) {
233 if (Access->isArrayKind()) {
234 auto *BasePtr = Access->getScopArrayInfo()->getBasePtr();
235 if (Instruction *OpInst = dyn_cast<Instruction>(BasePtr))
236 if (Stmt->getParent()->contains(OpInst))
237 continue;
238
239 References.Values.insert(BasePtr);
240 continue;
241 }
242
243 if (CreateScalarRefs)
244 References.Values.insert(References.BlockGen.getOrCreateAlloca(*Access));
245 }
246
247 return isl_stat_ok;
248}
249
250/// Extract the out-of-scop values and SCEVs referenced from a set describing
251/// a ScopStmt.
252///
253/// This includes the SCEVUnknowns referenced by the SCEVs used in the
254/// statement and the base pointers of the memory accesses. For scalar
255/// statements we force the generation of alloca memory locations and list
256/// these locations in the set of out-of-scop values as well.
257///
258/// @param Set A set which references the ScopStmt we are interested in.
259/// @param UserPtr A void pointer that can be casted to a SubtreeReferences
260/// structure.
261static isl_stat addReferencesFromStmtSet(__isl_take isl_set *Set,
262 void *UserPtr) {
263 isl_id *Id = isl_set_get_tuple_id(Set);
264 auto *Stmt = static_cast<const ScopStmt *>(isl_id_get_user(Id));
265 isl_id_free(Id);
266 isl_set_free(Set);
267 return addReferencesFromStmt(Stmt, UserPtr);
268}
269
270/// Extract the out-of-scop values and SCEVs referenced from a union set
271/// referencing multiple ScopStmts.
272///
273/// This includes the SCEVUnknowns referenced by the SCEVs used in the
274/// statement and the base pointers of the memory accesses. For scalar
275/// statements we force the generation of alloca memory locations and list
276/// these locations in the set of out-of-scop values as well.
277///
278/// @param USet A union set referencing the ScopStmts we are interested
279/// in.
280/// @param References The SubtreeReferences data structure through which
281/// results are returned and further information is
282/// provided.
283static void
284addReferencesFromStmtUnionSet(isl_union_set *USet,
285 struct SubtreeReferences &References) {
286 isl_union_set_foreach_set(USet, addReferencesFromStmtSet, &References);
287 isl_union_set_free(USet);
288}
289
290__isl_give isl_union_map *
291IslNodeBuilder::getScheduleForAstNode(__isl_keep isl_ast_node *For) {
292 return IslAstInfo::getSchedule(For);
293}
294
295void IslNodeBuilder::getReferencesInSubtree(__isl_keep isl_ast_node *For,
296 SetVector<Value *> &Values,
297 SetVector<const Loop *> &Loops) {
298
299 SetVector<const SCEV *> SCEVs;
300 struct SubtreeReferences References = {
301 LI, SE, S, ValueMap, Values, SCEVs, getBlockGenerator()};
302
303 for (const auto &I : IDToValue)
304 Values.insert(I.second);
305
306 for (const auto &I : OutsideLoopIterations)
307 Values.insert(cast<SCEVUnknown>(I.second)->getValue());
308
309 isl_union_set *Schedule = isl_union_map_domain(getScheduleForAstNode(For));
310 addReferencesFromStmtUnionSet(Schedule, References);
311
312 for (const SCEV *Expr : SCEVs) {
313 findValues(Expr, SE, Values);
314 findLoops(Expr, Loops);
315 }
316
317 Values.remove_if([](const Value *V) { return isa<GlobalValue>(V); });
318
319 /// Remove loops that contain the scop or that are part of the scop, as they
320 /// are considered local. This leaves only loops that are before the scop, but
321 /// do not contain the scop itself.
322 Loops.remove_if([this](const Loop *L) {
323 return S.contains(L) || L->contains(S.getEntry());
324 });
325}
326
327void IslNodeBuilder::updateValues(ValueMapT &NewValues) {
328 SmallPtrSet<Value *, 5> Inserted;
329
330 for (const auto &I : IDToValue) {
331 IDToValue[I.first] = NewValues[I.second];
332 Inserted.insert(I.second);
333 }
334
335 for (const auto &I : NewValues) {
336 if (Inserted.count(I.first))
337 continue;
338
339 ValueMap[I.first] = I.second;
340 }
341}
342
343void IslNodeBuilder::createUserVector(__isl_take isl_ast_node *User,
344 std::vector<Value *> &IVS,
345 __isl_take isl_id *IteratorID,
346 __isl_take isl_union_map *Schedule) {
347 isl_ast_expr *Expr = isl_ast_node_user_get_expr(User);
348 isl_ast_expr *StmtExpr = isl_ast_expr_get_op_arg(Expr, 0);
349 isl_id *Id = isl_ast_expr_get_id(StmtExpr);
350 isl_ast_expr_free(StmtExpr);
351 ScopStmt *Stmt = (ScopStmt *)isl_id_get_user(Id);
352 std::vector<LoopToScevMapT> VLTS(IVS.size());
353
354 isl_union_set *Domain = isl_union_set_from_set(Stmt->getDomain());
355 Schedule = isl_union_map_intersect_domain(Schedule, Domain);
356 isl_map *S = isl_map_from_union_map(Schedule);
357
358 auto *NewAccesses = createNewAccesses(Stmt, User);
359 createSubstitutionsVector(Expr, Stmt, VLTS, IVS, IteratorID);
360 VectorBlockGenerator::generate(BlockGen, *Stmt, VLTS, S, NewAccesses);
361 isl_id_to_ast_expr_free(NewAccesses);
362 isl_map_free(S);
363 isl_id_free(Id);
364 isl_ast_node_free(User);
365}
366
367void IslNodeBuilder::createMark(__isl_take isl_ast_node *Node) {
368 auto *Id = isl_ast_node_mark_get_id(Node);
369 auto Child = isl_ast_node_mark_get_node(Node);
370 isl_ast_node_free(Node);
371 // If a child node of a 'SIMD mark' is a loop that has a single iteration,
372 // it will be optimized away and we should skip it.
373 if (!strcmp(isl_id_get_name(Id), "SIMD") &&
374 isl_ast_node_get_type(Child) == isl_ast_node_for) {
375 bool Vector = PollyVectorizerChoice == VECTORIZER_POLLY;
376 int VectorWidth = getNumberOfIterations(Child);
377 if (Vector && 1 < VectorWidth && VectorWidth <= 16)
378 createForVector(Child, VectorWidth);
379 else
380 createForSequential(Child, true);
381 isl_id_free(Id);
382 return;
383 }
384 if (!strcmp(isl_id_get_name(Id), "Inter iteration alias-free")) {
385 auto *BasePtr = static_cast<Value *>(isl_id_get_user(Id));
386 Annotator.addInterIterationAliasFreeBasePtr(BasePtr);
387 }
388 create(Child);
389 isl_id_free(Id);
390}
391
392void IslNodeBuilder::createForVector(__isl_take isl_ast_node *For,
393 int VectorWidth) {
394 isl_ast_node *Body = isl_ast_node_for_get_body(For);
395 isl_ast_expr *Init = isl_ast_node_for_get_init(For);
396 isl_ast_expr *Inc = isl_ast_node_for_get_inc(For);
397 isl_ast_expr *Iterator = isl_ast_node_for_get_iterator(For);
398 isl_id *IteratorID = isl_ast_expr_get_id(Iterator);
399
400 Value *ValueLB = ExprBuilder.create(Init);
401 Value *ValueInc = ExprBuilder.create(Inc);
402
403 Type *MaxType = ExprBuilder.getType(Iterator);
404 MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
405 MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
406
407 if (MaxType != ValueLB->getType())
408 ValueLB = Builder.CreateSExt(ValueLB, MaxType);
409 if (MaxType != ValueInc->getType())
410 ValueInc = Builder.CreateSExt(ValueInc, MaxType);
411
412 std::vector<Value *> IVS(VectorWidth);
413 IVS[0] = ValueLB;
414
415 for (int i = 1; i < VectorWidth; i++)
416 IVS[i] = Builder.CreateAdd(IVS[i - 1], ValueInc, "p_vector_iv");
417
418 isl_union_map *Schedule = getScheduleForAstNode(For);
419 assert(Schedule && "For statement annotation does not contain its schedule")((Schedule && "For statement annotation does not contain its schedule"
) ? static_cast<void> (0) : __assert_fail ("Schedule && \"For statement annotation does not contain its schedule\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 419, __PRETTY_FUNCTION__))
;
420
421 IDToValue[IteratorID] = ValueLB;
422
423 switch (isl_ast_node_get_type(Body)) {
424 case isl_ast_node_user:
425 createUserVector(Body, IVS, isl_id_copy(IteratorID),
426 isl_union_map_copy(Schedule));
427 break;
428 case isl_ast_node_block: {
429 isl_ast_node_list *List = isl_ast_node_block_get_children(Body);
430
431 for (int i = 0; i < isl_ast_node_list_n_ast_node(List); ++i)
432 createUserVector(isl_ast_node_list_get_ast_node(List, i), IVS,
433 isl_id_copy(IteratorID), isl_union_map_copy(Schedule));
434
435 isl_ast_node_free(Body);
436 isl_ast_node_list_free(List);
437 break;
438 }
439 default:
440 isl_ast_node_dump(Body);
441 llvm_unreachable("Unhandled isl_ast_node in vectorizer")::llvm::llvm_unreachable_internal("Unhandled isl_ast_node in vectorizer"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 441)
;
442 }
443
444 IDToValue.erase(IDToValue.find(IteratorID));
445 isl_id_free(IteratorID);
446 isl_union_map_free(Schedule);
447
448 isl_ast_node_free(For);
449 isl_ast_expr_free(Iterator);
450}
451
452void IslNodeBuilder::createForSequential(__isl_take isl_ast_node *For,
453 bool KnownParallel) {
454 isl_ast_node *Body;
455 isl_ast_expr *Init, *Inc, *Iterator, *UB;
456 isl_id *IteratorID;
457 Value *ValueLB, *ValueUB, *ValueInc;
458 Type *MaxType;
459 BasicBlock *ExitBlock;
460 Value *IV;
461 CmpInst::Predicate Predicate;
462 bool Parallel;
463
464 Parallel = KnownParallel || (IslAstInfo::isParallel(For) &&
465 !IslAstInfo::isReductionParallel(For));
466
467 Body = isl_ast_node_for_get_body(For);
468
469 // isl_ast_node_for_is_degenerate(For)
470 //
471 // TODO: For degenerated loops we could generate a plain assignment.
472 // However, for now we just reuse the logic for normal loops, which will
473 // create a loop with a single iteration.
474
475 Init = isl_ast_node_for_get_init(For);
476 Inc = isl_ast_node_for_get_inc(For);
477 Iterator = isl_ast_node_for_get_iterator(For);
478 IteratorID = isl_ast_expr_get_id(Iterator);
479 UB = getUpperBound(For, Predicate);
480
481 ValueLB = ExprBuilder.create(Init);
482 ValueUB = ExprBuilder.create(UB);
483 ValueInc = ExprBuilder.create(Inc);
484
485 MaxType = ExprBuilder.getType(Iterator);
486 MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
487 MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType());
488 MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
489
490 if (MaxType != ValueLB->getType())
491 ValueLB = Builder.CreateSExt(ValueLB, MaxType);
492 if (MaxType != ValueUB->getType())
493 ValueUB = Builder.CreateSExt(ValueUB, MaxType);
494 if (MaxType != ValueInc->getType())
495 ValueInc = Builder.CreateSExt(ValueInc, MaxType);
496
497 // If we can show that LB <Predicate> UB holds at least once, we can
498 // omit the GuardBB in front of the loop.
499 bool UseGuardBB =
500 !SE.isKnownPredicate(Predicate, SE.getSCEV(ValueLB), SE.getSCEV(ValueUB));
501 IV = createLoop(ValueLB, ValueUB, ValueInc, Builder, LI, DT, ExitBlock,
502 Predicate, &Annotator, Parallel, UseGuardBB);
503 IDToValue[IteratorID] = IV;
504
505 create(Body);
506
507 Annotator.popLoop(Parallel);
508
509 IDToValue.erase(IDToValue.find(IteratorID));
510
511 Builder.SetInsertPoint(&ExitBlock->front());
512
513 isl_ast_node_free(For);
514 isl_ast_expr_free(Iterator);
515 isl_id_free(IteratorID);
516}
517
518/// Remove the BBs contained in a (sub)function from the dominator tree.
519///
520/// This function removes the basic blocks that are part of a subfunction from
521/// the dominator tree. Specifically, when generating code it may happen that at
522/// some point the code generation continues in a new sub-function (e.g., when
523/// generating OpenMP code). The basic blocks that are created in this
524/// sub-function are then still part of the dominator tree of the original
525/// function, such that the dominator tree reaches over function boundaries.
526/// This is not only incorrect, but also causes crashes. This function now
527/// removes from the dominator tree all basic blocks that are dominated (and
528/// consequently reachable) from the entry block of this (sub)function.
529///
530/// FIXME: A LLVM (function or region) pass should not touch anything outside of
531/// the function/region it runs on. Hence, the pure need for this function shows
532/// that we do not comply to this rule. At the moment, this does not cause any
533/// issues, but we should be aware that such issues may appear. Unfortunately
534/// the current LLVM pass infrastructure does not allow to make Polly a module
535/// or call-graph pass to solve this issue, as such a pass would not have access
536/// to the per-function analyses passes needed by Polly. A future pass manager
537/// infrastructure is supposed to enable such kind of access possibly allowing
538/// us to create a cleaner solution here.
539///
540/// FIXME: Instead of adding the dominance information and then dropping it
541/// later on, we should try to just not add it in the first place. This requires
542/// some careful testing to make sure this does not break in interaction with
543/// the SCEVBuilder and SplitBlock which may rely on the dominator tree or
544/// which may try to update it.
545///
546/// @param F The function which contains the BBs to removed.
547/// @param DT The dominator tree from which to remove the BBs.
548static void removeSubFuncFromDomTree(Function *F, DominatorTree &DT) {
549 DomTreeNode *N = DT.getNode(&F->getEntryBlock());
550 std::vector<BasicBlock *> Nodes;
551
552 // We can only remove an element from the dominator tree, if all its children
553 // have been removed. To ensure this we obtain the list of nodes to remove
554 // using a post-order tree traversal.
555 for (po_iterator<DomTreeNode *> I = po_begin(N), E = po_end(N); I != E; ++I)
556 Nodes.push_back(I->getBlock());
557
558 for (BasicBlock *BB : Nodes)
559 DT.eraseNode(BB);
560}
561
562void IslNodeBuilder::createForParallel(__isl_take isl_ast_node *For) {
563 isl_ast_node *Body;
564 isl_ast_expr *Init, *Inc, *Iterator, *UB;
565 isl_id *IteratorID;
566 Value *ValueLB, *ValueUB, *ValueInc;
567 Type *MaxType;
568 Value *IV;
569 CmpInst::Predicate Predicate;
570
571 // The preamble of parallel code interacts different than normal code with
572 // e.g., scalar initialization. Therefore, we ensure the parallel code is
573 // separated from the last basic block.
574 BasicBlock *ParBB = SplitBlock(Builder.GetInsertBlock(),
575 &*Builder.GetInsertPoint(), &DT, &LI);
576 ParBB->setName("polly.parallel.for");
577 Builder.SetInsertPoint(&ParBB->front());
578
579 Body = isl_ast_node_for_get_body(For);
580 Init = isl_ast_node_for_get_init(For);
581 Inc = isl_ast_node_for_get_inc(For);
582 Iterator = isl_ast_node_for_get_iterator(For);
583 IteratorID = isl_ast_expr_get_id(Iterator);
584 UB = getUpperBound(For, Predicate);
585
586 ValueLB = ExprBuilder.create(Init);
587 ValueUB = ExprBuilder.create(UB);
588 ValueInc = ExprBuilder.create(Inc);
589
590 // OpenMP always uses SLE. In case the isl generated AST uses a SLT
591 // expression, we need to adjust the loop bound by one.
592 if (Predicate == CmpInst::ICMP_SLT)
593 ValueUB = Builder.CreateAdd(
594 ValueUB, Builder.CreateSExt(Builder.getTrue(), ValueUB->getType()));
595
596 MaxType = ExprBuilder.getType(Iterator);
597 MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
598 MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType());
599 MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
600
601 if (MaxType != ValueLB->getType())
602 ValueLB = Builder.CreateSExt(ValueLB, MaxType);
603 if (MaxType != ValueUB->getType())
604 ValueUB = Builder.CreateSExt(ValueUB, MaxType);
605 if (MaxType != ValueInc->getType())
606 ValueInc = Builder.CreateSExt(ValueInc, MaxType);
607
608 BasicBlock::iterator LoopBody;
609
610 SetVector<Value *> SubtreeValues;
611 SetVector<const Loop *> Loops;
612
613 getReferencesInSubtree(For, SubtreeValues, Loops);
614
615 // Create for all loops we depend on values that contain the current loop
616 // iteration. These values are necessary to generate code for SCEVs that
617 // depend on such loops. As a result we need to pass them to the subfunction.
618 for (const Loop *L : Loops) {
619 const SCEV *OuterLIV = SE.getAddRecExpr(SE.getUnknown(Builder.getInt64(0)),
620 SE.getUnknown(Builder.getInt64(1)),
621 L, SCEV::FlagAnyWrap);
622 Value *V = generateSCEV(OuterLIV);
623 OutsideLoopIterations[L] = SE.getUnknown(V);
624 SubtreeValues.insert(V);
625 }
626
627 ValueMapT NewValues;
628 ParallelLoopGenerator ParallelLoopGen(Builder, LI, DT, DL);
629
630 IV = ParallelLoopGen.createParallelLoop(ValueLB, ValueUB, ValueInc,
631 SubtreeValues, NewValues, &LoopBody);
632 BasicBlock::iterator AfterLoop = Builder.GetInsertPoint();
633 Builder.SetInsertPoint(&*LoopBody);
634
635 // Remember the parallel subfunction
636 ParallelSubfunctions.push_back(LoopBody->getFunction());
637
638 // Save the current values.
639 auto ValueMapCopy = ValueMap;
640 IslExprBuilder::IDToValueTy IDToValueCopy = IDToValue;
641
642 updateValues(NewValues);
643 IDToValue[IteratorID] = IV;
644
645 ValueMapT NewValuesReverse;
646
647 for (auto P : NewValues)
648 NewValuesReverse[P.second] = P.first;
649
650 Annotator.addAlternativeAliasBases(NewValuesReverse);
651
652 create(Body);
653
654 Annotator.resetAlternativeAliasBases();
655 // Restore the original values.
656 ValueMap = ValueMapCopy;
657 IDToValue = IDToValueCopy;
658
659 Builder.SetInsertPoint(&*AfterLoop);
660 removeSubFuncFromDomTree((*LoopBody).getParent()->getParent(), DT);
661
662 for (const Loop *L : Loops)
663 OutsideLoopIterations.erase(L);
664
665 isl_ast_node_free(For);
666 isl_ast_expr_free(Iterator);
667 isl_id_free(IteratorID);
668}
669
670/// Return whether any of @p Node's statements contain partial accesses.
671///
672/// Partial accesses are not supported by Polly's vector code generator.
673static bool hasPartialAccesses(__isl_take isl_ast_node *Node) {
674 return isl_ast_node_foreach_descendant_top_down(
675 Node,
676 [](isl_ast_node *Node, void *User) -> isl_bool {
677 if (isl_ast_node_get_type(Node) != isl_ast_node_user)
678 return isl_bool_true;
679
680 isl::ast_expr Expr = give(isl_ast_node_user_get_expr(Node));
681 isl::ast_expr StmtExpr =
682 give(isl_ast_expr_get_op_arg(Expr.keep(), 0));
683 isl::id Id = give(isl_ast_expr_get_id(StmtExpr.keep()));
684
685 ScopStmt *Stmt =
686 static_cast<ScopStmt *>(isl_id_get_user(Id.keep()));
687 isl::set StmtDom = give(Stmt->getDomain());
688 for (auto *MA : *Stmt) {
689 if (MA->isLatestPartialAccess())
690 return isl_bool_error;
691 }
692 return isl_bool_true;
693 },
694 nullptr) == isl_stat_error;
695}
696
697void IslNodeBuilder::createFor(__isl_take isl_ast_node *For) {
698 bool Vector = PollyVectorizerChoice == VECTORIZER_POLLY;
699
700 if (Vector && IslAstInfo::isInnermostParallel(For) &&
701 !IslAstInfo::isReductionParallel(For)) {
702 int VectorWidth = getNumberOfIterations(For);
703 if (1 < VectorWidth && VectorWidth <= 16 && !hasPartialAccesses(For)) {
704 createForVector(For, VectorWidth);
705 return;
706 }
707 }
708
709 if (IslAstInfo::isExecutedInParallel(For)) {
710 createForParallel(For);
711 return;
712 }
713 createForSequential(For, false);
714}
715
716void IslNodeBuilder::createIf(__isl_take isl_ast_node *If) {
717 isl_ast_expr *Cond = isl_ast_node_if_get_cond(If);
718
719 Function *F = Builder.GetInsertBlock()->getParent();
720 LLVMContext &Context = F->getContext();
721
722 BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(),
723 &*Builder.GetInsertPoint(), &DT, &LI);
724 CondBB->setName("polly.cond");
725 BasicBlock *MergeBB = SplitBlock(CondBB, &CondBB->front(), &DT, &LI);
726 MergeBB->setName("polly.merge");
727 BasicBlock *ThenBB = BasicBlock::Create(Context, "polly.then", F);
728 BasicBlock *ElseBB = BasicBlock::Create(Context, "polly.else", F);
729
730 DT.addNewBlock(ThenBB, CondBB);
731 DT.addNewBlock(ElseBB, CondBB);
732 DT.changeImmediateDominator(MergeBB, CondBB);
733
734 Loop *L = LI.getLoopFor(CondBB);
735 if (L) {
736 L->addBasicBlockToLoop(ThenBB, LI);
737 L->addBasicBlockToLoop(ElseBB, LI);
738 }
739
740 CondBB->getTerminator()->eraseFromParent();
741
742 Builder.SetInsertPoint(CondBB);
743 Value *Predicate = ExprBuilder.create(Cond);
744 Builder.CreateCondBr(Predicate, ThenBB, ElseBB);
745 Builder.SetInsertPoint(ThenBB);
746 Builder.CreateBr(MergeBB);
747 Builder.SetInsertPoint(ElseBB);
748 Builder.CreateBr(MergeBB);
749 Builder.SetInsertPoint(&ThenBB->front());
750
751 create(isl_ast_node_if_get_then(If));
752
753 Builder.SetInsertPoint(&ElseBB->front());
754
755 if (isl_ast_node_if_has_else(If))
756 create(isl_ast_node_if_get_else(If));
757
758 Builder.SetInsertPoint(&MergeBB->front());
759
760 isl_ast_node_free(If);
761}
762
763__isl_give isl_id_to_ast_expr *
764IslNodeBuilder::createNewAccesses(ScopStmt *Stmt,
765 __isl_keep isl_ast_node *Node) {
766 isl_id_to_ast_expr *NewAccesses =
767 isl_id_to_ast_expr_alloc(Stmt->getParent()->getIslCtx(), 0);
768
769 auto *Build = IslAstInfo::getBuild(Node);
770 assert(Build && "Could not obtain isl_ast_build from user node")((Build && "Could not obtain isl_ast_build from user node"
) ? static_cast<void> (0) : __assert_fail ("Build && \"Could not obtain isl_ast_build from user node\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 770, __PRETTY_FUNCTION__))
;
771 Stmt->setAstBuild(Build);
772
773 for (auto *MA : *Stmt) {
774 if (!MA->hasNewAccessRelation()) {
775 if (PollyGenerateExpressions) {
776 if (!MA->isAffine())
777 continue;
778 if (MA->getLatestScopArrayInfo()->getBasePtrOriginSAI())
779 continue;
780
781 auto *BasePtr =
782 dyn_cast<Instruction>(MA->getLatestScopArrayInfo()->getBasePtr());
783 if (BasePtr && Stmt->getParent()->getRegion().contains(BasePtr))
784 continue;
785 } else {
786 continue;
787 }
788 }
789 assert(MA->isAffine() &&((MA->isAffine() && "Only affine memory accesses can be code generated"
) ? static_cast<void> (0) : __assert_fail ("MA->isAffine() && \"Only affine memory accesses can be code generated\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 790, __PRETTY_FUNCTION__))
790 "Only affine memory accesses can be code generated")((MA->isAffine() && "Only affine memory accesses can be code generated"
) ? static_cast<void> (0) : __assert_fail ("MA->isAffine() && \"Only affine memory accesses can be code generated\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 790, __PRETTY_FUNCTION__))
;
791
792 auto Schedule = isl_ast_build_get_schedule(Build);
793
794#ifndef NDEBUG
795 if (MA->isRead()) {
796 auto Dom = Stmt->getDomain();
797 auto SchedDom = isl_set_from_union_set(
798 isl_union_map_domain(isl_union_map_copy(Schedule)));
799 auto AccDom = isl_map_domain(MA->getAccessRelation());
800 Dom = isl_set_intersect_params(Dom, Stmt->getParent()->getContext());
801 SchedDom =
802 isl_set_intersect_params(SchedDom, Stmt->getParent()->getContext());
803 assert(isl_set_is_subset(SchedDom, AccDom) &&((isl_set_is_subset(SchedDom, AccDom) && "Access relation not defined on full schedule domain"
) ? static_cast<void> (0) : __assert_fail ("isl_set_is_subset(SchedDom, AccDom) && \"Access relation not defined on full schedule domain\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 804, __PRETTY_FUNCTION__))
804 "Access relation not defined on full schedule domain")((isl_set_is_subset(SchedDom, AccDom) && "Access relation not defined on full schedule domain"
) ? static_cast<void> (0) : __assert_fail ("isl_set_is_subset(SchedDom, AccDom) && \"Access relation not defined on full schedule domain\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 804, __PRETTY_FUNCTION__))
;
805 assert(isl_set_is_subset(Dom, AccDom) &&((isl_set_is_subset(Dom, AccDom) && "Access relation not defined on full domain"
) ? static_cast<void> (0) : __assert_fail ("isl_set_is_subset(Dom, AccDom) && \"Access relation not defined on full domain\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 806, __PRETTY_FUNCTION__))
806 "Access relation not defined on full domain")((isl_set_is_subset(Dom, AccDom) && "Access relation not defined on full domain"
) ? static_cast<void> (0) : __assert_fail ("isl_set_is_subset(Dom, AccDom) && \"Access relation not defined on full domain\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 806, __PRETTY_FUNCTION__))
;
807 isl_set_free(AccDom);
808 isl_set_free(SchedDom);
809 isl_set_free(Dom);
810 }
811#endif
812
813 auto PWAccRel = MA->applyScheduleToAccessRelation(Schedule);
814
815 // isl cannot generate an index expression for access-nothing accesses.
816 isl::set AccDomain =
817 give(isl_pw_multi_aff_domain(isl_pw_multi_aff_copy(PWAccRel)));
818 if (isl_set_is_empty(AccDomain.keep()) == isl_bool_true) {
819 isl_pw_multi_aff_free(PWAccRel);
820 continue;
821 }
822
823 auto AccessExpr = isl_ast_build_access_from_pw_multi_aff(Build, PWAccRel);
824 NewAccesses = isl_id_to_ast_expr_set(NewAccesses, MA->getId(), AccessExpr);
825 }
826
827 return NewAccesses;
828}
829
830void IslNodeBuilder::createSubstitutions(__isl_take isl_ast_expr *Expr,
831 ScopStmt *Stmt, LoopToScevMapT &LTS) {
832 assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&((isl_ast_expr_get_type(Expr) == isl_ast_expr_op && "Expression of type 'op' expected"
) ? static_cast<void> (0) : __assert_fail ("isl_ast_expr_get_type(Expr) == isl_ast_expr_op && \"Expression of type 'op' expected\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 833, __PRETTY_FUNCTION__))
833 "Expression of type 'op' expected")((isl_ast_expr_get_type(Expr) == isl_ast_expr_op && "Expression of type 'op' expected"
) ? static_cast<void> (0) : __assert_fail ("isl_ast_expr_get_type(Expr) == isl_ast_expr_op && \"Expression of type 'op' expected\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 833, __PRETTY_FUNCTION__))
;
834 assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_call &&((isl_ast_expr_get_op_type(Expr) == isl_ast_op_call &&
"Operation of type 'call' expected") ? static_cast<void>
(0) : __assert_fail ("isl_ast_expr_get_op_type(Expr) == isl_ast_op_call && \"Operation of type 'call' expected\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 835, __PRETTY_FUNCTION__))
835 "Operation of type 'call' expected")((isl_ast_expr_get_op_type(Expr) == isl_ast_op_call &&
"Operation of type 'call' expected") ? static_cast<void>
(0) : __assert_fail ("isl_ast_expr_get_op_type(Expr) == isl_ast_op_call && \"Operation of type 'call' expected\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 835, __PRETTY_FUNCTION__))
;
836 for (int i = 0; i < isl_ast_expr_get_op_n_arg(Expr) - 1; ++i) {
837 isl_ast_expr *SubExpr;
838 Value *V;
839
840 SubExpr = isl_ast_expr_get_op_arg(Expr, i + 1);
841 V = ExprBuilder.create(SubExpr);
842 ScalarEvolution *SE = Stmt->getParent()->getSE();
843 LTS[Stmt->getLoopForDimension(i)] = SE->getUnknown(V);
844 }
845
846 isl_ast_expr_free(Expr);
847}
848
849void IslNodeBuilder::createSubstitutionsVector(
850 __isl_take isl_ast_expr *Expr, ScopStmt *Stmt,
851 std::vector<LoopToScevMapT> &VLTS, std::vector<Value *> &IVS,
852 __isl_take isl_id *IteratorID) {
853 int i = 0;
854
855 Value *OldValue = IDToValue[IteratorID];
856 for (Value *IV : IVS) {
857 IDToValue[IteratorID] = IV;
858 createSubstitutions(isl_ast_expr_copy(Expr), Stmt, VLTS[i]);
859 i++;
860 }
861
862 IDToValue[IteratorID] = OldValue;
863 isl_id_free(IteratorID);
864 isl_ast_expr_free(Expr);
865}
866
867void IslNodeBuilder::generateCopyStmt(
868 ScopStmt *Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) {
869 assert(Stmt->size() == 2)((Stmt->size() == 2) ? static_cast<void> (0) : __assert_fail
("Stmt->size() == 2", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 869, __PRETTY_FUNCTION__))
;
870 auto ReadAccess = Stmt->begin();
871 auto WriteAccess = ReadAccess++;
872 assert((*ReadAccess)->isRead() && (*WriteAccess)->isMustWrite())(((*ReadAccess)->isRead() && (*WriteAccess)->isMustWrite
()) ? static_cast<void> (0) : __assert_fail ("(*ReadAccess)->isRead() && (*WriteAccess)->isMustWrite()"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 872, __PRETTY_FUNCTION__))
;
873 assert((*ReadAccess)->getElementType() == (*WriteAccess)->getElementType() &&(((*ReadAccess)->getElementType() == (*WriteAccess)->getElementType
() && "Accesses use the same data type") ? static_cast
<void> (0) : __assert_fail ("(*ReadAccess)->getElementType() == (*WriteAccess)->getElementType() && \"Accesses use the same data type\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 874, __PRETTY_FUNCTION__))
874 "Accesses use the same data type")(((*ReadAccess)->getElementType() == (*WriteAccess)->getElementType
() && "Accesses use the same data type") ? static_cast
<void> (0) : __assert_fail ("(*ReadAccess)->getElementType() == (*WriteAccess)->getElementType() && \"Accesses use the same data type\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 874, __PRETTY_FUNCTION__))
;
875 assert((*ReadAccess)->isArrayKind() && (*WriteAccess)->isArrayKind())(((*ReadAccess)->isArrayKind() && (*WriteAccess)->
isArrayKind()) ? static_cast<void> (0) : __assert_fail (
"(*ReadAccess)->isArrayKind() && (*WriteAccess)->isArrayKind()"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 875, __PRETTY_FUNCTION__))
;
876 auto *AccessExpr =
877 isl_id_to_ast_expr_get(NewAccesses, (*ReadAccess)->getId());
878 auto *LoadValue = ExprBuilder.create(AccessExpr);
879 AccessExpr = isl_id_to_ast_expr_get(NewAccesses, (*WriteAccess)->getId());
880 auto *StoreAddr = ExprBuilder.createAccessAddress(AccessExpr);
881 Builder.CreateStore(LoadValue, StoreAddr);
882}
883
884void IslNodeBuilder::createUser(__isl_take isl_ast_node *User) {
885 LoopToScevMapT LTS;
886 isl_id *Id;
887 ScopStmt *Stmt;
888
889 isl_ast_expr *Expr = isl_ast_node_user_get_expr(User);
890 isl_ast_expr *StmtExpr = isl_ast_expr_get_op_arg(Expr, 0);
891 Id = isl_ast_expr_get_id(StmtExpr);
892 isl_ast_expr_free(StmtExpr);
893
894 LTS.insert(OutsideLoopIterations.begin(), OutsideLoopIterations.end());
895
896 Stmt = (ScopStmt *)isl_id_get_user(Id);
897 auto *NewAccesses = createNewAccesses(Stmt, User);
898 if (Stmt->isCopyStmt()) {
899 generateCopyStmt(Stmt, NewAccesses);
900 isl_ast_expr_free(Expr);
901 } else {
902 createSubstitutions(Expr, Stmt, LTS);
903
904 if (Stmt->isBlockStmt())
905 BlockGen.copyStmt(*Stmt, LTS, NewAccesses);
906 else
907 RegionGen.copyStmt(*Stmt, LTS, NewAccesses);
908 }
909
910 isl_id_to_ast_expr_free(NewAccesses);
911 isl_ast_node_free(User);
912 isl_id_free(Id);
913}
914
915void IslNodeBuilder::createBlock(__isl_take isl_ast_node *Block) {
916 isl_ast_node_list *List = isl_ast_node_block_get_children(Block);
917
918 for (int i = 0; i < isl_ast_node_list_n_ast_node(List); ++i)
919 create(isl_ast_node_list_get_ast_node(List, i));
920
921 isl_ast_node_free(Block);
922 isl_ast_node_list_free(List);
923}
924
925void IslNodeBuilder::create(__isl_take isl_ast_node *Node) {
926 switch (isl_ast_node_get_type(Node)) {
927 case isl_ast_node_error:
928 llvm_unreachable("code generation error")::llvm::llvm_unreachable_internal("code generation error", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 928)
;
929 case isl_ast_node_mark:
930 createMark(Node);
931 return;
932 case isl_ast_node_for:
933 createFor(Node);
934 return;
935 case isl_ast_node_if:
936 createIf(Node);
937 return;
938 case isl_ast_node_user:
939 createUser(Node);
940 return;
941 case isl_ast_node_block:
942 createBlock(Node);
943 return;
944 }
945
946 llvm_unreachable("Unknown isl_ast_node type")::llvm::llvm_unreachable_internal("Unknown isl_ast_node type"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 946)
;
947}
948
949bool IslNodeBuilder::materializeValue(isl_id *Id) {
950 // If the Id is already mapped, skip it.
951 if (!IDToValue.count(Id)) {
952 auto *ParamSCEV = (const SCEV *)isl_id_get_user(Id);
953 Value *V = nullptr;
954
955 // Parameters could refer to invariant loads that need to be
956 // preloaded before we can generate code for the parameter. Thus,
957 // check if any value referred to in ParamSCEV is an invariant load
958 // and if so make sure its equivalence class is preloaded.
959 SetVector<Value *> Values;
960 findValues(ParamSCEV, SE, Values);
961 for (auto *Val : Values) {
962
963 // Check if the value is an instruction in a dead block within the SCoP
964 // and if so do not code generate it.
965 if (auto *Inst = dyn_cast<Instruction>(Val)) {
966 if (S.contains(Inst)) {
967 bool IsDead = true;
968
969 // Check for "undef" loads first, then if there is a statement for
970 // the parent of Inst and lastly if the parent of Inst has an empty
971 // domain. In the first and last case the instruction is dead but if
972 // there is a statement or the domain is not empty Inst is not dead.
973 auto MemInst = MemAccInst::dyn_cast(Inst);
974 auto Address = MemInst ? MemInst.getPointerOperand() : nullptr;
975 if (Address && SE.getUnknown(UndefValue::get(Address->getType())) ==
976 SE.getPointerBase(SE.getSCEV(Address))) {
977 } else if (S.getStmtFor(Inst)) {
978 IsDead = false;
979 } else {
980 auto *Domain = S.getDomainConditions(Inst->getParent());
981 IsDead = isl_set_is_empty(Domain);
982 isl_set_free(Domain);
983 }
984
985 if (IsDead) {
986 V = UndefValue::get(ParamSCEV->getType());
987 break;
988 }
989 }
990 }
991
992 if (auto *IAClass = S.lookupInvariantEquivClass(Val)) {
993
994 // Check if this invariant access class is empty, hence if we never
995 // actually added a loads instruction to it. In that case it has no
996 // (meaningful) users and we should not try to code generate it.
997 if (IAClass->InvariantAccesses.empty())
998 V = UndefValue::get(ParamSCEV->getType());
999
1000 if (!preloadInvariantEquivClass(*IAClass)) {
1001 isl_id_free(Id);
1002 return false;
1003 }
1004 }
1005 }
1006
1007 V = V ? V : generateSCEV(ParamSCEV);
1008 IDToValue[Id] = V;
1009 }
1010
1011 isl_id_free(Id);
1012 return true;
1013}
1014
1015bool IslNodeBuilder::materializeParameters(isl_set *Set) {
1016 for (unsigned i = 0, e = isl_set_dim(Set, isl_dim_param); i < e; ++i) {
1017 if (!isl_set_involves_dims(Set, isl_dim_param, i, 1))
1018 continue;
1019 isl_id *Id = isl_set_get_dim_id(Set, isl_dim_param, i);
1020 if (!materializeValue(Id))
1021 return false;
1022 }
1023 return true;
1024}
1025
1026bool IslNodeBuilder::materializeParameters() {
1027 for (const SCEV *Param : S.parameters()) {
1028 isl_id *Id = S.getIdForParam(Param);
1029 if (!materializeValue(Id))
1030 return false;
1031 }
1032 return true;
1033}
1034
1035/// Generate the computation of the size of the outermost dimension from the
1036/// Fortran array descriptor (in this case, `@g_arr`). The final `%size`
1037/// contains the size of the array.
1038///
1039/// %arrty = type { i8*, i64, i64, [3 x %desc.dimensionty] }
1040/// %desc.dimensionty = type { i64, i64, i64 }
1041/// @g_arr = global %arrty zeroinitializer, align 32
1042/// ...
1043/// %0 = load i64, i64* getelementptr inbounds
1044/// (%arrty, %arrty* @g_arr, i64 0, i32 3, i64 0, i32 2)
1045/// %1 = load i64, i64* getelementptr inbounds
1046/// (%arrty, %arrty* @g_arr, i64 0, i32 3, i64 0, i32 1)
1047/// %2 = sub nsw i64 %0, %1
1048/// %size = add nsw i64 %2, 1
1049static Value *buildFADOutermostDimensionLoad(Value *GlobalDescriptor,
1050 PollyIRBuilder &Builder,
1051 std::string ArrayName) {
1052 assert(GlobalDescriptor && "invalid global descriptor given")((GlobalDescriptor && "invalid global descriptor given"
) ? static_cast<void> (0) : __assert_fail ("GlobalDescriptor && \"invalid global descriptor given\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1052, __PRETTY_FUNCTION__))
;
1053
1054 Value *endIdx[4] = {Builder.getInt64(0), Builder.getInt32(3),
1055 Builder.getInt64(0), Builder.getInt32(2)};
1056 Value *endPtr = Builder.CreateInBoundsGEP(GlobalDescriptor, endIdx,
1057 ArrayName + "_end_ptr");
1058 Value *end = Builder.CreateLoad(endPtr, ArrayName + "_end");
1059
1060 Value *beginIdx[4] = {Builder.getInt64(0), Builder.getInt32(3),
1061 Builder.getInt64(0), Builder.getInt32(1)};
1062 Value *beginPtr = Builder.CreateInBoundsGEP(GlobalDescriptor, beginIdx,
1063 ArrayName + "_begin_ptr");
1064 Value *begin = Builder.CreateLoad(beginPtr, ArrayName + "_begin");
1065
1066 Value *size =
Value stored to 'size' during its initialization is never read
1067 Builder.CreateNSWSub(end, begin, ArrayName + "_end_begin_delta");
1068 Type *endType = dyn_cast<IntegerType>(end->getType());
1069 assert(endType && "expected type of end to be integral")((endType && "expected type of end to be integral") ?
static_cast<void> (0) : __assert_fail ("endType && \"expected type of end to be integral\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1069, __PRETTY_FUNCTION__))
;
1070
1071 size = Builder.CreateNSWAdd(end,
1072 ConstantInt::get(endType, 1, /* signed = */ true),
1073 ArrayName + "_size");
1074
1075 return size;
1076}
1077
1078bool IslNodeBuilder::materializeFortranArrayOutermostDimension() {
1079 for (const ScopStmt &Stmt : S) {
1080 for (const MemoryAccess *Access : Stmt) {
1081 if (!Access->isArrayKind())
1082 continue;
1083
1084 const ScopArrayInfo *Array = Access->getScopArrayInfo();
1085 if (!Array)
1086 continue;
1087
1088 if (Array->getNumberOfDimensions() == 0)
1089 continue;
1090
1091 Value *FAD = Access->getFortranArrayDescriptor();
1092 if (!FAD)
1093 continue;
1094
1095 isl_pw_aff *ParametricPwAff = Array->getDimensionSizePw(0);
1096 assert(ParametricPwAff && "parametric pw_aff corresponding "((ParametricPwAff && "parametric pw_aff corresponding "
"to outermost dimension does not " "exist") ? static_cast<
void> (0) : __assert_fail ("ParametricPwAff && \"parametric pw_aff corresponding \" \"to outermost dimension does not \" \"exist\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1098, __PRETTY_FUNCTION__))
1097 "to outermost dimension does not "((ParametricPwAff && "parametric pw_aff corresponding "
"to outermost dimension does not " "exist") ? static_cast<
void> (0) : __assert_fail ("ParametricPwAff && \"parametric pw_aff corresponding \" \"to outermost dimension does not \" \"exist\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1098, __PRETTY_FUNCTION__))
1098 "exist")((ParametricPwAff && "parametric pw_aff corresponding "
"to outermost dimension does not " "exist") ? static_cast<
void> (0) : __assert_fail ("ParametricPwAff && \"parametric pw_aff corresponding \" \"to outermost dimension does not \" \"exist\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1098, __PRETTY_FUNCTION__))
;
1099
1100 isl_id *Id = isl_pw_aff_get_dim_id(ParametricPwAff, isl_dim_param, 0);
1101 isl_pw_aff_free(ParametricPwAff);
1102
1103 assert(Id && "pw_aff is not parametric")((Id && "pw_aff is not parametric") ? static_cast<
void> (0) : __assert_fail ("Id && \"pw_aff is not parametric\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1103, __PRETTY_FUNCTION__))
;
1104
1105 if (IDToValue.count(Id)) {
1106 isl_id_free(Id);
1107 continue;
1108 }
1109
1110 Value *FinalValue =
1111 buildFADOutermostDimensionLoad(FAD, Builder, Array->getName());
1112 assert(FinalValue && "unable to build Fortran array "((FinalValue && "unable to build Fortran array " "descriptor load of outermost dimension"
) ? static_cast<void> (0) : __assert_fail ("FinalValue && \"unable to build Fortran array \" \"descriptor load of outermost dimension\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1113, __PRETTY_FUNCTION__))
1113 "descriptor load of outermost dimension")((FinalValue && "unable to build Fortran array " "descriptor load of outermost dimension"
) ? static_cast<void> (0) : __assert_fail ("FinalValue && \"unable to build Fortran array \" \"descriptor load of outermost dimension\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1113, __PRETTY_FUNCTION__))
;
1114 IDToValue[Id] = FinalValue;
1115 isl_id_free(Id);
1116 }
1117 }
1118 return true;
1119}
1120
1121/// Add the number of dimensions in @p BS to @p U.
1122static isl_stat countTotalDims(__isl_take isl_basic_set *BS, void *U) {
1123 unsigned *NumTotalDim = static_cast<unsigned *>(U);
1124 *NumTotalDim += isl_basic_set_total_dim(BS);
1125 isl_basic_set_free(BS);
1126 return isl_stat_ok;
1127}
1128
1129Value *IslNodeBuilder::preloadUnconditionally(isl_set *AccessRange,
1130 isl_ast_build *Build,
1131 Instruction *AccInst) {
1132
1133 // TODO: This check could be performed in the ScopInfo already.
1134 unsigned NumTotalDim = 0;
1135 isl_set_foreach_basic_set(AccessRange, countTotalDims, &NumTotalDim);
1136 if (NumTotalDim > MaxDimensionsInAccessRange) {
1137 isl_set_free(AccessRange);
1138 return nullptr;
1139 }
1140
1141 isl_pw_multi_aff *PWAccRel = isl_pw_multi_aff_from_set(AccessRange);
1142 isl_ast_expr *Access =
1143 isl_ast_build_access_from_pw_multi_aff(Build, PWAccRel);
1144 auto *Address = isl_ast_expr_address_of(Access);
1145 auto *AddressValue = ExprBuilder.create(Address);
1146 Value *PreloadVal;
1147
1148 // Correct the type as the SAI might have a different type than the user
1149 // expects, especially if the base pointer is a struct.
1150 Type *Ty = AccInst->getType();
1151
1152 auto *Ptr = AddressValue;
1153 auto Name = Ptr->getName();
1154 auto AS = Ptr->getType()->getPointerAddressSpace();
1155 Ptr = Builder.CreatePointerCast(Ptr, Ty->getPointerTo(AS), Name + ".cast");
1156 PreloadVal = Builder.CreateLoad(Ptr, Name + ".load");
1157 if (LoadInst *PreloadInst = dyn_cast<LoadInst>(PreloadVal))
1158 PreloadInst->setAlignment(dyn_cast<LoadInst>(AccInst)->getAlignment());
1159
1160 // TODO: This is only a hot fix for SCoP sequences that use the same load
1161 // instruction contained and hoisted by one of the SCoPs.
1162 if (SE.isSCEVable(Ty))
1163 SE.forgetValue(AccInst);
1164
1165 return PreloadVal;
1166}
1167
1168Value *IslNodeBuilder::preloadInvariantLoad(const MemoryAccess &MA,
1169 isl_set *Domain) {
1170
1171 isl_set *AccessRange = isl_map_range(MA.getAddressFunction());
1172 AccessRange = isl_set_gist_params(AccessRange, S.getContext());
1173
1174 if (!materializeParameters(AccessRange)) {
1175 isl_set_free(AccessRange);
1176 isl_set_free(Domain);
1177 return nullptr;
1178 }
1179
1180 auto *Build = isl_ast_build_from_context(isl_set_universe(S.getParamSpace()));
1181 isl_set *Universe = isl_set_universe(isl_set_get_space(Domain));
1182 bool AlwaysExecuted = isl_set_is_equal(Domain, Universe);
1183 isl_set_free(Universe);
1184
1185 Instruction *AccInst = MA.getAccessInstruction();
1186 Type *AccInstTy = AccInst->getType();
1187
1188 Value *PreloadVal = nullptr;
1189 if (AlwaysExecuted) {
1190 PreloadVal = preloadUnconditionally(AccessRange, Build, AccInst);
1191 isl_ast_build_free(Build);
1192 isl_set_free(Domain);
1193 return PreloadVal;
1194 }
1195
1196 if (!materializeParameters(Domain)) {
1197 isl_ast_build_free(Build);
1198 isl_set_free(AccessRange);
1199 isl_set_free(Domain);
1200 return nullptr;
1201 }
1202
1203 isl_ast_expr *DomainCond = isl_ast_build_expr_from_set(Build, Domain);
1204 Domain = nullptr;
1205
1206 ExprBuilder.setTrackOverflow(true);
1207 Value *Cond = ExprBuilder.create(DomainCond);
1208 Value *OverflowHappened = Builder.CreateNot(ExprBuilder.getOverflowState(),
1209 "polly.preload.cond.overflown");
1210 Cond = Builder.CreateAnd(Cond, OverflowHappened, "polly.preload.cond.result");
1211 ExprBuilder.setTrackOverflow(false);
1212
1213 if (!Cond->getType()->isIntegerTy(1))
1214 Cond = Builder.CreateIsNotNull(Cond);
1215
1216 BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(),
1217 &*Builder.GetInsertPoint(), &DT, &LI);
1218 CondBB->setName("polly.preload.cond");
1219
1220 BasicBlock *MergeBB = SplitBlock(CondBB, &CondBB->front(), &DT, &LI);
1221 MergeBB->setName("polly.preload.merge");
1222
1223 Function *F = Builder.GetInsertBlock()->getParent();
1224 LLVMContext &Context = F->getContext();
1225 BasicBlock *ExecBB = BasicBlock::Create(Context, "polly.preload.exec", F);
1226
1227 DT.addNewBlock(ExecBB, CondBB);
1228 if (Loop *L = LI.getLoopFor(CondBB))
1229 L->addBasicBlockToLoop(ExecBB, LI);
1230
1231 auto *CondBBTerminator = CondBB->getTerminator();
1232 Builder.SetInsertPoint(CondBBTerminator);
1233 Builder.CreateCondBr(Cond, ExecBB, MergeBB);
1234 CondBBTerminator->eraseFromParent();
1235
1236 Builder.SetInsertPoint(ExecBB);
1237 Builder.CreateBr(MergeBB);
1238
1239 Builder.SetInsertPoint(ExecBB->getTerminator());
1240 Value *PreAccInst = preloadUnconditionally(AccessRange, Build, AccInst);
1241 Builder.SetInsertPoint(MergeBB->getTerminator());
1242 auto *MergePHI = Builder.CreatePHI(
1243 AccInstTy, 2, "polly.preload." + AccInst->getName() + ".merge");
1244 PreloadVal = MergePHI;
1245
1246 if (!PreAccInst) {
1247 PreloadVal = nullptr;
1248 PreAccInst = UndefValue::get(AccInstTy);
1249 }
1250
1251 MergePHI->addIncoming(PreAccInst, ExecBB);
1252 MergePHI->addIncoming(Constant::getNullValue(AccInstTy), CondBB);
1253
1254 isl_ast_build_free(Build);
1255 return PreloadVal;
1256}
1257
1258bool IslNodeBuilder::preloadInvariantEquivClass(
1259 InvariantEquivClassTy &IAClass) {
1260 // For an equivalence class of invariant loads we pre-load the representing
1261 // element with the unified execution context. However, we have to map all
1262 // elements of the class to the one preloaded load as they are referenced
1263 // during the code generation and therefor need to be mapped.
1264 const MemoryAccessList &MAs = IAClass.InvariantAccesses;
1265 if (MAs.empty())
1266 return true;
1267
1268 MemoryAccess *MA = MAs.front();
1269 assert(MA->isArrayKind() && MA->isRead())((MA->isArrayKind() && MA->isRead()) ? static_cast
<void> (0) : __assert_fail ("MA->isArrayKind() && MA->isRead()"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1269, __PRETTY_FUNCTION__))
;
1270
1271 // If the access function was already mapped, the preload of this equivalence
1272 // class was triggered earlier already and doesn't need to be done again.
1273 if (ValueMap.count(MA->getAccessInstruction()))
1274 return true;
1275
1276 // Check for recursion which can be caused by additional constraints, e.g.,
1277 // non-finite loop constraints. In such a case we have to bail out and insert
1278 // a "false" runtime check that will cause the original code to be executed.
1279 auto PtrId = std::make_pair(IAClass.IdentifyingPointer, IAClass.AccessType);
1280 if (!PreloadedPtrs.insert(PtrId).second)
1281 return false;
1282
1283 // The execution context of the IAClass.
1284 isl_set *&ExecutionCtx = IAClass.ExecutionContext;
1285
1286 // If the base pointer of this class is dependent on another one we have to
1287 // make sure it was preloaded already.
1288 auto *SAI = MA->getScopArrayInfo();
1289 if (auto *BaseIAClass = S.lookupInvariantEquivClass(SAI->getBasePtr())) {
1290 if (!preloadInvariantEquivClass(*BaseIAClass))
1291 return false;
1292
1293 // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx and
1294 // we need to refine the ExecutionCtx.
1295 isl_set *BaseExecutionCtx = isl_set_copy(BaseIAClass->ExecutionContext);
1296 ExecutionCtx = isl_set_intersect(ExecutionCtx, BaseExecutionCtx);
1297 }
1298
1299 // If the size of a dimension is dependent on another class, make sure it is
1300 // preloaded.
1301 for (unsigned i = 1, e = SAI->getNumberOfDimensions(); i < e; ++i) {
1302 const SCEV *Dim = SAI->getDimensionSize(i);
1303 SetVector<Value *> Values;
1304 findValues(Dim, SE, Values);
1305 for (auto *Val : Values) {
1306 if (auto *BaseIAClass = S.lookupInvariantEquivClass(Val)) {
1307 if (!preloadInvariantEquivClass(*BaseIAClass))
1308 return false;
1309
1310 // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx
1311 // and we need to refine the ExecutionCtx.
1312 isl_set *BaseExecutionCtx = isl_set_copy(BaseIAClass->ExecutionContext);
1313 ExecutionCtx = isl_set_intersect(ExecutionCtx, BaseExecutionCtx);
1314 }
1315 }
1316 }
1317
1318 Instruction *AccInst = MA->getAccessInstruction();
1319 Type *AccInstTy = AccInst->getType();
1320
1321 Value *PreloadVal = preloadInvariantLoad(*MA, isl_set_copy(ExecutionCtx));
1322 if (!PreloadVal)
1323 return false;
1324
1325 for (const MemoryAccess *MA : MAs) {
1326 Instruction *MAAccInst = MA->getAccessInstruction();
1327 assert(PreloadVal->getType() == MAAccInst->getType())((PreloadVal->getType() == MAAccInst->getType()) ? static_cast
<void> (0) : __assert_fail ("PreloadVal->getType() == MAAccInst->getType()"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1327, __PRETTY_FUNCTION__))
;
1328 ValueMap[MAAccInst] = PreloadVal;
1329 }
1330
1331 if (SE.isSCEVable(AccInstTy)) {
1332 isl_id *ParamId = S.getIdForParam(SE.getSCEV(AccInst));
1333 if (ParamId)
1334 IDToValue[ParamId] = PreloadVal;
1335 isl_id_free(ParamId);
1336 }
1337
1338 BasicBlock *EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
1339 auto *Alloca = new AllocaInst(AccInstTy, DL.getAllocaAddrSpace(),
1340 AccInst->getName() + ".preload.s2a");
1341 Alloca->insertBefore(&*EntryBB->getFirstInsertionPt());
1342 Builder.CreateStore(PreloadVal, Alloca);
1343 ValueMapT PreloadedPointer;
1344 PreloadedPointer[PreloadVal] = AccInst;
1345 Annotator.addAlternativeAliasBases(PreloadedPointer);
1346
1347 for (auto *DerivedSAI : SAI->getDerivedSAIs()) {
1348 Value *BasePtr = DerivedSAI->getBasePtr();
1349
1350 for (const MemoryAccess *MA : MAs) {
1351 // As the derived SAI information is quite coarse, any load from the
1352 // current SAI could be the base pointer of the derived SAI, however we
1353 // should only change the base pointer of the derived SAI if we actually
1354 // preloaded it.
1355 if (BasePtr == MA->getOriginalBaseAddr()) {
1356 assert(BasePtr->getType() == PreloadVal->getType())((BasePtr->getType() == PreloadVal->getType()) ? static_cast
<void> (0) : __assert_fail ("BasePtr->getType() == PreloadVal->getType()"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1356, __PRETTY_FUNCTION__))
;
1357 DerivedSAI->setBasePtr(PreloadVal);
1358 }
1359
1360 // For scalar derived SAIs we remap the alloca used for the derived value.
1361 if (BasePtr == MA->getAccessInstruction())
1362 ScalarMap[DerivedSAI] = Alloca;
1363 }
1364 }
1365
1366 for (const MemoryAccess *MA : MAs) {
1367
1368 Instruction *MAAccInst = MA->getAccessInstruction();
1369 // Use the escape system to get the correct value to users outside the SCoP.
1370 BlockGenerator::EscapeUserVectorTy EscapeUsers;
1371 for (auto *U : MAAccInst->users())
1372 if (Instruction *UI = dyn_cast<Instruction>(U))
1373 if (!S.contains(UI))
1374 EscapeUsers.push_back(UI);
1375
1376 if (EscapeUsers.empty())
1377 continue;
1378
1379 EscapeMap[MA->getAccessInstruction()] =
1380 std::make_pair(Alloca, std::move(EscapeUsers));
1381 }
1382
1383 return true;
1384}
1385
1386void IslNodeBuilder::allocateNewArrays() {
1387 for (auto &SAI : S.arrays()) {
1388 if (SAI->getBasePtr())
1389 continue;
1390
1391 assert(SAI->getNumberOfDimensions() > 0 && SAI->getDimensionSize(0) &&((SAI->getNumberOfDimensions() > 0 && SAI->getDimensionSize
(0) && "The size of the outermost dimension is used to declare newly "
"created arrays that require memory allocation.") ? static_cast
<void> (0) : __assert_fail ("SAI->getNumberOfDimensions() > 0 && SAI->getDimensionSize(0) && \"The size of the outermost dimension is used to declare newly \" \"created arrays that require memory allocation.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1393, __PRETTY_FUNCTION__))
1392 "The size of the outermost dimension is used to declare newly "((SAI->getNumberOfDimensions() > 0 && SAI->getDimensionSize
(0) && "The size of the outermost dimension is used to declare newly "
"created arrays that require memory allocation.") ? static_cast
<void> (0) : __assert_fail ("SAI->getNumberOfDimensions() > 0 && SAI->getDimensionSize(0) && \"The size of the outermost dimension is used to declare newly \" \"created arrays that require memory allocation.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1393, __PRETTY_FUNCTION__))
1393 "created arrays that require memory allocation.")((SAI->getNumberOfDimensions() > 0 && SAI->getDimensionSize
(0) && "The size of the outermost dimension is used to declare newly "
"created arrays that require memory allocation.") ? static_cast
<void> (0) : __assert_fail ("SAI->getNumberOfDimensions() > 0 && SAI->getDimensionSize(0) && \"The size of the outermost dimension is used to declare newly \" \"created arrays that require memory allocation.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1393, __PRETTY_FUNCTION__))
;
1394
1395 Type *NewArrayType = nullptr;
1396 for (int i = SAI->getNumberOfDimensions() - 1; i >= 0; i--) {
1397 auto *DimSize = SAI->getDimensionSize(i);
1398 unsigned UnsignedDimSize = static_cast<const SCEVConstant *>(DimSize)
1399 ->getAPInt()
1400 .getLimitedValue();
1401
1402 if (!NewArrayType)
1403 NewArrayType = SAI->getElementType();
1404
1405 NewArrayType = ArrayType::get(NewArrayType, UnsignedDimSize);
1406 }
1407
1408 auto InstIt =
1409 Builder.GetInsertBlock()->getParent()->getEntryBlock().getTerminator();
1410 auto *CreatedArray = new AllocaInst(NewArrayType, DL.getAllocaAddrSpace(),
1411 SAI->getName(), &*InstIt);
1412 CreatedArray->setAlignment(PollyTargetFirstLevelCacheLineSize);
1413 SAI->setBasePtr(CreatedArray);
1414 }
1415}
1416
1417bool IslNodeBuilder::preloadInvariantLoads() {
1418
1419 auto &InvariantEquivClasses = S.getInvariantAccesses();
1420 if (InvariantEquivClasses.empty())
1421 return true;
1422
1423 BasicBlock *PreLoadBB = SplitBlock(Builder.GetInsertBlock(),
1424 &*Builder.GetInsertPoint(), &DT, &LI);
1425 PreLoadBB->setName("polly.preload.begin");
1426 Builder.SetInsertPoint(&PreLoadBB->front());
1427
1428 for (auto &IAClass : InvariantEquivClasses)
1429 if (!preloadInvariantEquivClass(IAClass))
1430 return false;
1431
1432 return true;
1433}
1434
1435void IslNodeBuilder::addParameters(__isl_take isl_set *Context) {
1436 // Materialize values for the parameters of the SCoP.
1437 materializeParameters();
1438
1439 // materialize the outermost dimension parameters for a Fortran array.
1440 // NOTE: materializeParameters() does not work since it looks through
1441 // the SCEVs. We don't have a corresponding SCEV for the array size
1442 // parameter
1443 materializeFortranArrayOutermostDimension();
1444
1445 // Generate values for the current loop iteration for all surrounding loops.
1446 //
1447 // We may also reference loops outside of the scop which do not contain the
1448 // scop itself, but as the number of such scops may be arbitrarily large we do
1449 // not generate code for them here, but only at the point of code generation
1450 // where these values are needed.
1451 Loop *L = LI.getLoopFor(S.getEntry());
1452
1453 while (L != nullptr && S.contains(L))
1454 L = L->getParentLoop();
1455
1456 while (L != nullptr) {
1457 const SCEV *OuterLIV = SE.getAddRecExpr(SE.getUnknown(Builder.getInt64(0)),
1458 SE.getUnknown(Builder.getInt64(1)),
1459 L, SCEV::FlagAnyWrap);
1460 Value *V = generateSCEV(OuterLIV);
1461 OutsideLoopIterations[L] = SE.getUnknown(V);
1462 L = L->getParentLoop();
1463 }
1464
1465 isl_set_free(Context);
1466}
1467
1468Value *IslNodeBuilder::generateSCEV(const SCEV *Expr) {
1469 /// We pass the insert location of our Builder, as Polly ensures during IR
1470 /// generation that there is always a valid CFG into which instructions are
1471 /// inserted. As a result, the insertpoint is known to be always followed by a
1472 /// terminator instruction. This means the insert point may be specified by a
1473 /// terminator instruction, but it can never point to an ->end() iterator
1474 /// which does not have a corresponding instruction. Hence, dereferencing
1475 /// the insertpoint to obtain an instruction is known to be save.
1476 ///
1477 /// We also do not need to update the Builder here, as new instructions are
1478 /// always inserted _before_ the given InsertLocation. As a result, the
1479 /// insert location remains valid.
1480 assert(Builder.GetInsertBlock()->end() != Builder.GetInsertPoint() &&((Builder.GetInsertBlock()->end() != Builder.GetInsertPoint
() && "Insert location points after last valid instruction"
) ? static_cast<void> (0) : __assert_fail ("Builder.GetInsertBlock()->end() != Builder.GetInsertPoint() && \"Insert location points after last valid instruction\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1481, __PRETTY_FUNCTION__))
1481 "Insert location points after last valid instruction")((Builder.GetInsertBlock()->end() != Builder.GetInsertPoint
() && "Insert location points after last valid instruction"
) ? static_cast<void> (0) : __assert_fail ("Builder.GetInsertBlock()->end() != Builder.GetInsertPoint() && \"Insert location points after last valid instruction\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn306458/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1481, __PRETTY_FUNCTION__))
;
1482 Instruction *InsertLocation = &*Builder.GetInsertPoint();
1483 return expandCodeFor(S, SE, DL, "polly", Expr, Expr->getType(),
1484 InsertLocation, &ValueMap,
1485 StartBlock->getSinglePredecessor());
1486}
1487
1488/// The AST expression we generate to perform the run-time check assumes
1489/// computations on integer types of infinite size. As we only use 64-bit
1490/// arithmetic we check for overflows, in case of which we set the result
1491/// of this run-time check to false to be conservatively correct,
1492Value *IslNodeBuilder::createRTC(isl_ast_expr *Condition) {
1493 auto ExprBuilder = getExprBuilder();
1494 ExprBuilder.setTrackOverflow(true);
1495 Value *RTC = ExprBuilder.create(Condition);
1496 if (!RTC->getType()->isIntegerTy(1))
1497 RTC = Builder.CreateIsNotNull(RTC);
1498 Value *OverflowHappened =
1499 Builder.CreateNot(ExprBuilder.getOverflowState(), "polly.rtc.overflown");
1500
1501 if (PollyGenerateRTCPrint) {
1502 auto *F = Builder.GetInsertBlock()->getParent();
1503 RuntimeDebugBuilder::createCPUPrinter(
1504 Builder,
1505 "F: " + F->getName().str() + " R: " + S.getRegion().getNameStr() +
1506 " __RTC: ",
1507 RTC, " Overflow: ", OverflowHappened, "\n");
1508 }
1509
1510 RTC = Builder.CreateAnd(RTC, OverflowHappened, "polly.rtc.result");
1511 ExprBuilder.setTrackOverflow(false);
1512
1513 if (!isa<ConstantInt>(RTC))
1514 VersionedScops++;
1515
1516 return RTC;
1517}