Bug Summary

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