Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name IslNodeBuilder.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/lib -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/include -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/pet/include -I /usr/include/jsoncpp -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/include -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn329677/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -Wno-long-long -Wno-unused-parameter -Wwrite-strings -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/lib -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fno-rtti -fobjc-runtime=gcc -fno-common -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-04-11-031539-24776-1 -x c++ /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp
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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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 = IsLoopVectorizerDisabled(isl::manage_copy(For));
544
545 Body = isl_ast_node_for_get_body(For);
546
547 // isl_ast_node_for_is_degenerate(For)
548 //
549 // TODO: For degenerated loops we could generate a plain assignment.
550 // However, for now we just reuse the logic for normal loops, which will
551 // create a loop with a single iteration.
552
553 Init = isl_ast_node_for_get_init(For);
554 Inc = isl_ast_node_for_get_inc(For);
555 Iterator = isl_ast_node_for_get_iterator(For);
556 IteratorID = isl_ast_expr_get_id(Iterator);
557 UB = getUpperBound(For, Predicate);
558
559 ValueLB = ExprBuilder.create(Init);
560 ValueUB = ExprBuilder.create(UB);
561 ValueInc = ExprBuilder.create(Inc);
562
563 MaxType = ExprBuilder.getType(Iterator);
564 MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
565 MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType());
566 MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
567
568 if (MaxType != ValueLB->getType())
569 ValueLB = Builder.CreateSExt(ValueLB, MaxType);
570 if (MaxType != ValueUB->getType())
571 ValueUB = Builder.CreateSExt(ValueUB, MaxType);
572 if (MaxType != ValueInc->getType())
573 ValueInc = Builder.CreateSExt(ValueInc, MaxType);
574
575 // If we can show that LB <Predicate> UB holds at least once, we can
576 // omit the GuardBB in front of the loop.
577 bool UseGuardBB =
578 !SE.isKnownPredicate(Predicate, SE.getSCEV(ValueLB), SE.getSCEV(ValueUB));
579 IV = createLoop(ValueLB, ValueUB, ValueInc, Builder, LI, DT, ExitBlock,
580 Predicate, &Annotator, MarkParallel, UseGuardBB,
581 LoopVectorizerDisabled);
582 IDToValue[IteratorID] = IV;
583
584 create(Body);
585
586 Annotator.popLoop(MarkParallel);
587
588 IDToValue.erase(IDToValue.find(IteratorID));
589
590 Builder.SetInsertPoint(&ExitBlock->front());
591
592 isl_ast_node_free(For);
593 isl_ast_expr_free(Iterator);
594 isl_id_free(IteratorID);
595
596 SequentialLoops++;
597}
598
599/// Remove the BBs contained in a (sub)function from the dominator tree.
600///
601/// This function removes the basic blocks that are part of a subfunction from
602/// the dominator tree. Specifically, when generating code it may happen that at
603/// some point the code generation continues in a new sub-function (e.g., when
604/// generating OpenMP code). The basic blocks that are created in this
605/// sub-function are then still part of the dominator tree of the original
606/// function, such that the dominator tree reaches over function boundaries.
607/// This is not only incorrect, but also causes crashes. This function now
608/// removes from the dominator tree all basic blocks that are dominated (and
609/// consequently reachable) from the entry block of this (sub)function.
610///
611/// FIXME: A LLVM (function or region) pass should not touch anything outside of
612/// the function/region it runs on. Hence, the pure need for this function shows
613/// that we do not comply to this rule. At the moment, this does not cause any
614/// issues, but we should be aware that such issues may appear. Unfortunately
615/// the current LLVM pass infrastructure does not allow to make Polly a module
616/// or call-graph pass to solve this issue, as such a pass would not have access
617/// to the per-function analyses passes needed by Polly. A future pass manager
618/// infrastructure is supposed to enable such kind of access possibly allowing
619/// us to create a cleaner solution here.
620///
621/// FIXME: Instead of adding the dominance information and then dropping it
622/// later on, we should try to just not add it in the first place. This requires
623/// some careful testing to make sure this does not break in interaction with
624/// the SCEVBuilder and SplitBlock which may rely on the dominator tree or
625/// which may try to update it.
626///
627/// @param F The function which contains the BBs to removed.
628/// @param DT The dominator tree from which to remove the BBs.
629static void removeSubFuncFromDomTree(Function *F, DominatorTree &DT) {
630 DomTreeNode *N = DT.getNode(&F->getEntryBlock());
631 std::vector<BasicBlock *> Nodes;
632
633 // We can only remove an element from the dominator tree, if all its children
634 // have been removed. To ensure this we obtain the list of nodes to remove
635 // using a post-order tree traversal.
636 for (po_iterator<DomTreeNode *> I = po_begin(N), E = po_end(N); I != E; ++I)
637 Nodes.push_back(I->getBlock());
638
639 for (BasicBlock *BB : Nodes)
640 DT.eraseNode(BB);
641}
642
643void IslNodeBuilder::createForParallel(__isl_take isl_ast_node *For) {
644 isl_ast_node *Body;
645 isl_ast_expr *Init, *Inc, *Iterator, *UB;
646 isl_id *IteratorID;
647 Value *ValueLB, *ValueUB, *ValueInc;
648 Type *MaxType;
649 Value *IV;
650 CmpInst::Predicate Predicate;
651
652 // The preamble of parallel code interacts different than normal code with
653 // e.g., scalar initialization. Therefore, we ensure the parallel code is
654 // separated from the last basic block.
655 BasicBlock *ParBB = SplitBlock(Builder.GetInsertBlock(),
656 &*Builder.GetInsertPoint(), &DT, &LI);
657 ParBB->setName("polly.parallel.for");
658 Builder.SetInsertPoint(&ParBB->front());
659
660 Body = isl_ast_node_for_get_body(For);
661 Init = isl_ast_node_for_get_init(For);
662 Inc = isl_ast_node_for_get_inc(For);
663 Iterator = isl_ast_node_for_get_iterator(For);
664 IteratorID = isl_ast_expr_get_id(Iterator);
665 UB = getUpperBound(For, Predicate);
666
667 ValueLB = ExprBuilder.create(Init);
668 ValueUB = ExprBuilder.create(UB);
669 ValueInc = ExprBuilder.create(Inc);
670
671 // OpenMP always uses SLE. In case the isl generated AST uses a SLT
672 // expression, we need to adjust the loop bound by one.
673 if (Predicate == CmpInst::ICMP_SLT)
674 ValueUB = Builder.CreateAdd(
675 ValueUB, Builder.CreateSExt(Builder.getTrue(), ValueUB->getType()));
676
677 MaxType = ExprBuilder.getType(Iterator);
678 MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
679 MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType());
680 MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
681
682 if (MaxType != ValueLB->getType())
683 ValueLB = Builder.CreateSExt(ValueLB, MaxType);
684 if (MaxType != ValueUB->getType())
685 ValueUB = Builder.CreateSExt(ValueUB, MaxType);
686 if (MaxType != ValueInc->getType())
687 ValueInc = Builder.CreateSExt(ValueInc, MaxType);
688
689 BasicBlock::iterator LoopBody;
690
691 SetVector<Value *> SubtreeValues;
692 SetVector<const Loop *> Loops;
693
694 getReferencesInSubtree(For, SubtreeValues, Loops);
695
696 // Create for all loops we depend on values that contain the current loop
697 // iteration. These values are necessary to generate code for SCEVs that
698 // depend on such loops. As a result we need to pass them to the subfunction.
699 // See [Code generation of induction variables of loops outside Scops]
700 for (const Loop *L : Loops) {
701 Value *LoopInductionVar = materializeNonScopLoopInductionVariable(L);
702 SubtreeValues.insert(LoopInductionVar);
703 }
704
705 ValueMapT NewValues;
706 ParallelLoopGenerator ParallelLoopGen(Builder, LI, DT, DL);
707
708 IV = ParallelLoopGen.createParallelLoop(ValueLB, ValueUB, ValueInc,
709 SubtreeValues, NewValues, &LoopBody);
710 BasicBlock::iterator AfterLoop = Builder.GetInsertPoint();
711 Builder.SetInsertPoint(&*LoopBody);
712
713 // Remember the parallel subfunction
714 ParallelSubfunctions.push_back(LoopBody->getFunction());
715
716 // Save the current values.
717 auto ValueMapCopy = ValueMap;
718 IslExprBuilder::IDToValueTy IDToValueCopy = IDToValue;
719
720 updateValues(NewValues);
721 IDToValue[IteratorID] = IV;
722
723 ValueMapT NewValuesReverse;
724
725 for (auto P : NewValues)
726 NewValuesReverse[P.second] = P.first;
727
728 Annotator.addAlternativeAliasBases(NewValuesReverse);
729
730 create(Body);
731
732 Annotator.resetAlternativeAliasBases();
733 // Restore the original values.
734 ValueMap = ValueMapCopy;
735 IDToValue = IDToValueCopy;
736
737 Builder.SetInsertPoint(&*AfterLoop);
738 removeSubFuncFromDomTree((*LoopBody).getParent()->getParent(), DT);
739
740 for (const Loop *L : Loops)
741 OutsideLoopIterations.erase(L);
742
743 isl_ast_node_free(For);
744 isl_ast_expr_free(Iterator);
745 isl_id_free(IteratorID);
746
747 ParallelLoops++;
748}
749
750/// Return whether any of @p Node's statements contain partial accesses.
751///
752/// Partial accesses are not supported by Polly's vector code generator.
753static bool hasPartialAccesses(__isl_take isl_ast_node *Node) {
754 return isl_ast_node_foreach_descendant_top_down(
755 Node,
756 [](isl_ast_node *Node, void *User) -> isl_bool {
757 if (isl_ast_node_get_type(Node) != isl_ast_node_user)
758 return isl_bool_true;
759
760 isl::ast_expr Expr = give(isl_ast_node_user_get_expr(Node));
761 isl::ast_expr StmtExpr =
762 give(isl_ast_expr_get_op_arg(Expr.keep(), 0));
763 isl::id Id = give(isl_ast_expr_get_id(StmtExpr.keep()));
764
765 ScopStmt *Stmt =
766 static_cast<ScopStmt *>(isl_id_get_user(Id.keep()));
767 isl::set StmtDom = Stmt->getDomain();
768 for (auto *MA : *Stmt) {
769 if (MA->isLatestPartialAccess())
770 return isl_bool_error;
771 }
772 return isl_bool_true;
773 },
774 nullptr) == isl_stat_error;
775}
776
777void IslNodeBuilder::createFor(__isl_take isl_ast_node *For) {
778 bool Vector = PollyVectorizerChoice == VECTORIZER_POLLY;
779
780 if (Vector && IslAstInfo::isInnermostParallel(For) &&
781 !IslAstInfo::isReductionParallel(For)) {
782 int VectorWidth = getNumberOfIterations(For);
783 if (1 < VectorWidth && VectorWidth <= 16 && !hasPartialAccesses(For)) {
784 createForVector(For, VectorWidth);
785 return;
786 }
787 }
788
789 if (IslAstInfo::isExecutedInParallel(For)) {
790 createForParallel(For);
791 return;
792 }
793 bool Parallel =
794 (IslAstInfo::isParallel(For) && !IslAstInfo::isReductionParallel(For));
795 createForSequential(For, Parallel);
796}
797
798void IslNodeBuilder::createIf(__isl_take isl_ast_node *If) {
799 isl_ast_expr *Cond = isl_ast_node_if_get_cond(If);
800
801 Function *F = Builder.GetInsertBlock()->getParent();
802 LLVMContext &Context = F->getContext();
803
804 BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(),
805 &*Builder.GetInsertPoint(), &DT, &LI);
806 CondBB->setName("polly.cond");
807 BasicBlock *MergeBB = SplitBlock(CondBB, &CondBB->front(), &DT, &LI);
808 MergeBB->setName("polly.merge");
809 BasicBlock *ThenBB = BasicBlock::Create(Context, "polly.then", F);
810 BasicBlock *ElseBB = BasicBlock::Create(Context, "polly.else", F);
811
812 DT.addNewBlock(ThenBB, CondBB);
813 DT.addNewBlock(ElseBB, CondBB);
814 DT.changeImmediateDominator(MergeBB, CondBB);
815
816 Loop *L = LI.getLoopFor(CondBB);
817 if (L) {
818 L->addBasicBlockToLoop(ThenBB, LI);
819 L->addBasicBlockToLoop(ElseBB, LI);
820 }
821
822 CondBB->getTerminator()->eraseFromParent();
823
824 Builder.SetInsertPoint(CondBB);
825 Value *Predicate = ExprBuilder.create(Cond);
826 Builder.CreateCondBr(Predicate, ThenBB, ElseBB);
827 Builder.SetInsertPoint(ThenBB);
828 Builder.CreateBr(MergeBB);
829 Builder.SetInsertPoint(ElseBB);
830 Builder.CreateBr(MergeBB);
831 Builder.SetInsertPoint(&ThenBB->front());
832
833 create(isl_ast_node_if_get_then(If));
834
835 Builder.SetInsertPoint(&ElseBB->front());
836
837 if (isl_ast_node_if_has_else(If))
838 create(isl_ast_node_if_get_else(If));
839
840 Builder.SetInsertPoint(&MergeBB->front());
841
842 isl_ast_node_free(If);
843
844 IfConditions++;
845}
846
847__isl_give isl_id_to_ast_expr *
848IslNodeBuilder::createNewAccesses(ScopStmt *Stmt,
849 __isl_keep isl_ast_node *Node) {
850 isl_id_to_ast_expr *NewAccesses =
851 isl_id_to_ast_expr_alloc(Stmt->getParent()->getIslCtx().get(), 0);
852
853 auto *Build = IslAstInfo::getBuild(Node);
854 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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 854, __extension__ __PRETTY_FUNCTION__))
;
855 Stmt->setAstBuild(isl::manage_copy(Build));
856
857 for (auto *MA : *Stmt) {
858 if (!MA->hasNewAccessRelation()) {
859 if (PollyGenerateExpressions) {
860 if (!MA->isAffine())
861 continue;
862 if (MA->getLatestScopArrayInfo()->getBasePtrOriginSAI())
863 continue;
864
865 auto *BasePtr =
866 dyn_cast<Instruction>(MA->getLatestScopArrayInfo()->getBasePtr());
867 if (BasePtr && Stmt->getParent()->getRegion().contains(BasePtr))
868 continue;
869 } else {
870 continue;
871 }
872 }
873 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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 874, __extension__ __PRETTY_FUNCTION__))
874 "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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 874, __extension__ __PRETTY_FUNCTION__))
;
875
876 auto Schedule = isl_ast_build_get_schedule(Build);
877
878#ifndef NDEBUG
879 if (MA->isRead()) {
880 auto Dom = Stmt->getDomain().release();
881 auto SchedDom = isl_set_from_union_set(
882 isl_union_map_domain(isl_union_map_copy(Schedule)));
883 auto AccDom = isl_map_domain(MA->getAccessRelation().release());
884 Dom = isl_set_intersect_params(Dom,
885 Stmt->getParent()->getContext().release());
886 SchedDom = isl_set_intersect_params(
887 SchedDom, Stmt->getParent()->getContext().release());
888 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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 889, __extension__ __PRETTY_FUNCTION__))
889 "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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 889, __extension__ __PRETTY_FUNCTION__))
;
890 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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 891, __extension__ __PRETTY_FUNCTION__))
891 "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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 891, __extension__ __PRETTY_FUNCTION__))
;
892 isl_set_free(AccDom);
893 isl_set_free(SchedDom);
894 isl_set_free(Dom);
895 }
896#endif
897
898 auto PWAccRel =
899 MA->applyScheduleToAccessRelation(isl::manage(Schedule)).release();
900
901 // isl cannot generate an index expression for access-nothing accesses.
902 isl::set AccDomain =
903 give(isl_pw_multi_aff_domain(isl_pw_multi_aff_copy(PWAccRel)));
904 isl::set Context = S.getContext();
905 AccDomain = AccDomain.intersect_params(Context);
906 if (isl_set_is_empty(AccDomain.keep()) == isl_bool_true) {
907 isl_pw_multi_aff_free(PWAccRel);
908 continue;
909 }
910
911 auto AccessExpr = isl_ast_build_access_from_pw_multi_aff(Build, PWAccRel);
912 NewAccesses =
913 isl_id_to_ast_expr_set(NewAccesses, MA->getId().release(), AccessExpr);
914 }
915
916 return NewAccesses;
917}
918
919void IslNodeBuilder::createSubstitutions(__isl_take isl_ast_expr *Expr,
920 ScopStmt *Stmt, LoopToScevMapT &LTS) {
921 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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 922, __extension__ __PRETTY_FUNCTION__))
922 "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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 922, __extension__ __PRETTY_FUNCTION__))
;
923 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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 924, __extension__ __PRETTY_FUNCTION__))
924 "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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 924, __extension__ __PRETTY_FUNCTION__))
;
925 for (int i = 0; i < isl_ast_expr_get_op_n_arg(Expr) - 1; ++i) {
926 isl_ast_expr *SubExpr;
927 Value *V;
928
929 SubExpr = isl_ast_expr_get_op_arg(Expr, i + 1);
930 V = ExprBuilder.create(SubExpr);
931 ScalarEvolution *SE = Stmt->getParent()->getSE();
932 LTS[Stmt->getLoopForDimension(i)] = SE->getUnknown(V);
933 }
934
935 isl_ast_expr_free(Expr);
936}
937
938void IslNodeBuilder::createSubstitutionsVector(
939 __isl_take isl_ast_expr *Expr, ScopStmt *Stmt,
940 std::vector<LoopToScevMapT> &VLTS, std::vector<Value *> &IVS,
941 __isl_take isl_id *IteratorID) {
942 int i = 0;
943
944 Value *OldValue = IDToValue[IteratorID];
945 for (Value *IV : IVS) {
946 IDToValue[IteratorID] = IV;
947 createSubstitutions(isl_ast_expr_copy(Expr), Stmt, VLTS[i]);
948 i++;
949 }
950
951 IDToValue[IteratorID] = OldValue;
952 isl_id_free(IteratorID);
953 isl_ast_expr_free(Expr);
954}
955
956void IslNodeBuilder::generateCopyStmt(
957 ScopStmt *Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) {
958 assert(Stmt->size() == 2)(static_cast <bool> (Stmt->size() == 2) ? void (0) :
__assert_fail ("Stmt->size() == 2", "/build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 958, __extension__ __PRETTY_FUNCTION__))
;
959 auto ReadAccess = Stmt->begin();
960 auto WriteAccess = ReadAccess++;
961 assert((*ReadAccess)->isRead() && (*WriteAccess)->isMustWrite())(static_cast <bool> ((*ReadAccess)->isRead() &&
(*WriteAccess)->isMustWrite()) ? void (0) : __assert_fail
("(*ReadAccess)->isRead() && (*WriteAccess)->isMustWrite()"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 961, __extension__ __PRETTY_FUNCTION__))
;
962 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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 963, __extension__ __PRETTY_FUNCTION__))
963 "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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 963, __extension__ __PRETTY_FUNCTION__))
;
964 assert((*ReadAccess)->isArrayKind() && (*WriteAccess)->isArrayKind())(static_cast <bool> ((*ReadAccess)->isArrayKind() &&
(*WriteAccess)->isArrayKind()) ? void (0) : __assert_fail
("(*ReadAccess)->isArrayKind() && (*WriteAccess)->isArrayKind()"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 964, __extension__ __PRETTY_FUNCTION__))
;
965 auto *AccessExpr =
966 isl_id_to_ast_expr_get(NewAccesses, (*ReadAccess)->getId().release());
967 auto *LoadValue = ExprBuilder.create(AccessExpr);
968 AccessExpr =
969 isl_id_to_ast_expr_get(NewAccesses, (*WriteAccess)->getId().release());
970 auto *StoreAddr = ExprBuilder.createAccessAddress(AccessExpr);
971 Builder.CreateStore(LoadValue, StoreAddr);
972}
973
974Value *IslNodeBuilder::materializeNonScopLoopInductionVariable(const Loop *L) {
975 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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 976, __extension__ __PRETTY_FUNCTION__))
976 "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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 976, __extension__ __PRETTY_FUNCTION__))
;
977 const SCEV *OuterLIV = SE.getAddRecExpr(SE.getUnknown(Builder.getInt64(0)),
978 SE.getUnknown(Builder.getInt64(1)), L,
979 SCEV::FlagAnyWrap);
980 Value *V = generateSCEV(OuterLIV);
981 OutsideLoopIterations[L] = SE.getUnknown(V);
982 return V;
983}
984
985void IslNodeBuilder::createUser(__isl_take isl_ast_node *User) {
986 LoopToScevMapT LTS;
987 isl_id *Id;
988 ScopStmt *Stmt;
989
990 isl_ast_expr *Expr = isl_ast_node_user_get_expr(User);
991 isl_ast_expr *StmtExpr = isl_ast_expr_get_op_arg(Expr, 0);
992 Id = isl_ast_expr_get_id(StmtExpr);
993 isl_ast_expr_free(StmtExpr);
994
995 LTS.insert(OutsideLoopIterations.begin(), OutsideLoopIterations.end());
996
997 Stmt = (ScopStmt *)isl_id_get_user(Id);
998 auto *NewAccesses = createNewAccesses(Stmt, User);
999 if (Stmt->isCopyStmt()) {
1000 generateCopyStmt(Stmt, NewAccesses);
1001 isl_ast_expr_free(Expr);
1002 } else {
1003 createSubstitutions(Expr, Stmt, LTS);
1004
1005 if (Stmt->isBlockStmt())
1006 BlockGen.copyStmt(*Stmt, LTS, NewAccesses);
1007 else
1008 RegionGen.copyStmt(*Stmt, LTS, NewAccesses);
1009 }
1010
1011 isl_id_to_ast_expr_free(NewAccesses);
1012 isl_ast_node_free(User);
1013 isl_id_free(Id);
1014}
1015
1016void IslNodeBuilder::createBlock(__isl_take isl_ast_node *Block) {
1017 isl_ast_node_list *List = isl_ast_node_block_get_children(Block);
1018
1019 for (int i = 0; i < isl_ast_node_list_n_ast_node(List); ++i)
1020 create(isl_ast_node_list_get_ast_node(List, i));
1021
1022 isl_ast_node_free(Block);
1023 isl_ast_node_list_free(List);
1024}
1025
1026void IslNodeBuilder::create(__isl_take isl_ast_node *Node) {
1027 switch (isl_ast_node_get_type(Node)) {
1028 case isl_ast_node_error:
1029 llvm_unreachable("code generation error")::llvm::llvm_unreachable_internal("code generation error", "/build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1029)
;
1030 case isl_ast_node_mark:
1031 createMark(Node);
1032 return;
1033 case isl_ast_node_for:
1034 createFor(Node);
1035 return;
1036 case isl_ast_node_if:
1037 createIf(Node);
1038 return;
1039 case isl_ast_node_user:
1040 createUser(Node);
1041 return;
1042 case isl_ast_node_block:
1043 createBlock(Node);
1044 return;
1045 }
1046
1047 llvm_unreachable("Unknown isl_ast_node type")::llvm::llvm_unreachable_internal("Unknown isl_ast_node type"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1047)
;
1048}
1049
1050bool IslNodeBuilder::materializeValue(isl_id *Id) {
1051 // If the Id is already mapped, skip it.
1052 if (!IDToValue.count(Id)) {
1053 auto *ParamSCEV = (const SCEV *)isl_id_get_user(Id);
1054 Value *V = nullptr;
1055
1056 // Parameters could refer to invariant loads that need to be
1057 // preloaded before we can generate code for the parameter. Thus,
1058 // check if any value referred to in ParamSCEV is an invariant load
1059 // and if so make sure its equivalence class is preloaded.
1060 SetVector<Value *> Values;
1061 findValues(ParamSCEV, SE, Values);
1062 for (auto *Val : Values) {
1063 // Check if the value is an instruction in a dead block within the SCoP
1064 // and if so do not code generate it.
1065 if (auto *Inst = dyn_cast<Instruction>(Val)) {
1066 if (S.contains(Inst)) {
1067 bool IsDead = true;
1068
1069 // Check for "undef" loads first, then if there is a statement for
1070 // the parent of Inst and lastly if the parent of Inst has an empty
1071 // domain. In the first and last case the instruction is dead but if
1072 // there is a statement or the domain is not empty Inst is not dead.
1073 auto MemInst = MemAccInst::dyn_cast(Inst);
1074 auto Address = MemInst ? MemInst.getPointerOperand() : nullptr;
1075 if (Address && SE.getUnknown(UndefValue::get(Address->getType())) ==
1076 SE.getPointerBase(SE.getSCEV(Address))) {
1077 } else if (S.getStmtFor(Inst)) {
1078 IsDead = false;
1079 } else {
1080 auto *Domain = S.getDomainConditions(Inst->getParent()).release();
1081 IsDead = isl_set_is_empty(Domain);
1082 isl_set_free(Domain);
1083 }
1084
1085 if (IsDead) {
1086 V = UndefValue::get(ParamSCEV->getType());
1087 break;
1088 }
1089 }
1090 }
1091
1092 if (auto *IAClass = S.lookupInvariantEquivClass(Val)) {
1093 // Check if this invariant access class is empty, hence if we never
1094 // actually added a loads instruction to it. In that case it has no
1095 // (meaningful) users and we should not try to code generate it.
1096 if (IAClass->InvariantAccesses.empty())
1097 V = UndefValue::get(ParamSCEV->getType());
1098
1099 if (!preloadInvariantEquivClass(*IAClass)) {
1100 isl_id_free(Id);
1101 return false;
1102 }
1103 }
1104 }
1105
1106 V = V ? V : generateSCEV(ParamSCEV);
1107 IDToValue[Id] = V;
1108 }
1109
1110 isl_id_free(Id);
1111 return true;
1112}
1113
1114bool IslNodeBuilder::materializeParameters(isl_set *Set) {
1115 for (unsigned i = 0, e = isl_set_dim(Set, isl_dim_param); i < e; ++i) {
1116 if (!isl_set_involves_dims(Set, isl_dim_param, i, 1))
1117 continue;
1118 isl_id *Id = isl_set_get_dim_id(Set, isl_dim_param, i);
1119 if (!materializeValue(Id))
1120 return false;
1121 }
1122 return true;
1123}
1124
1125bool IslNodeBuilder::materializeParameters() {
1126 for (const SCEV *Param : S.parameters()) {
1127 isl_id *Id = S.getIdForParam(Param).release();
1128 if (!materializeValue(Id))
1129 return false;
1130 }
1131 return true;
1132}
1133
1134/// Generate the computation of the size of the outermost dimension from the
1135/// Fortran array descriptor (in this case, `@g_arr`). The final `%size`
1136/// contains the size of the array.
1137///
1138/// %arrty = type { i8*, i64, i64, [3 x %desc.dimensionty] }
1139/// %desc.dimensionty = type { i64, i64, i64 }
1140/// @g_arr = global %arrty zeroinitializer, align 32
1141/// ...
1142/// %0 = load i64, i64* getelementptr inbounds
1143/// (%arrty, %arrty* @g_arr, i64 0, i32 3, i64 0, i32 2)
1144/// %1 = load i64, i64* getelementptr inbounds
1145/// (%arrty, %arrty* @g_arr, i64 0, i32 3, i64 0, i32 1)
1146/// %2 = sub nsw i64 %0, %1
1147/// %size = add nsw i64 %2, 1
1148static Value *buildFADOutermostDimensionLoad(Value *GlobalDescriptor,
1149 PollyIRBuilder &Builder,
1150 std::string ArrayName) {
1151 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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1151, __extension__ __PRETTY_FUNCTION__))
;
1152
1153 Value *endIdx[4] = {Builder.getInt64(0), Builder.getInt32(3),
1154 Builder.getInt64(0), Builder.getInt32(2)};
1155 Value *endPtr = Builder.CreateInBoundsGEP(GlobalDescriptor, endIdx,
1156 ArrayName + "_end_ptr");
1157 Value *end = Builder.CreateLoad(endPtr, ArrayName + "_end");
1158
1159 Value *beginIdx[4] = {Builder.getInt64(0), Builder.getInt32(3),
1160 Builder.getInt64(0), Builder.getInt32(1)};
1161 Value *beginPtr = Builder.CreateInBoundsGEP(GlobalDescriptor, beginIdx,
1162 ArrayName + "_begin_ptr");
1163 Value *begin = Builder.CreateLoad(beginPtr, ArrayName + "_begin");
1164
1165 Value *size =
Value stored to 'size' during its initialization is never read
1166 Builder.CreateNSWSub(end, begin, ArrayName + "_end_begin_delta");
1167 Type *endType = dyn_cast<IntegerType>(end->getType());
1168 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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1168, __extension__ __PRETTY_FUNCTION__))
;
1169
1170 size = Builder.CreateNSWAdd(end,
1171 ConstantInt::get(endType, 1, /* signed = */ true),
1172 ArrayName + "_size");
1173
1174 return size;
1175}
1176
1177bool IslNodeBuilder::materializeFortranArrayOutermostDimension() {
1178 for (ScopArrayInfo *Array : S.arrays()) {
1179 if (Array->getNumberOfDimensions() == 0)
1180 continue;
1181
1182 Value *FAD = Array->getFortranArrayDescriptor();
1183 if (!FAD)
1184 continue;
1185
1186 isl_pw_aff *ParametricPwAff = Array->getDimensionSizePw(0).release();
1187 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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1189, __extension__ __PRETTY_FUNCTION__))
1188 "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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1189, __extension__ __PRETTY_FUNCTION__))
1189 "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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1189, __extension__ __PRETTY_FUNCTION__))
;
1190
1191 isl_id *Id = isl_pw_aff_get_dim_id(ParametricPwAff, isl_dim_param, 0);
1192 isl_pw_aff_free(ParametricPwAff);
1193
1194 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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1194, __extension__ __PRETTY_FUNCTION__))
;
1195
1196 if (IDToValue.count(Id)) {
1197 isl_id_free(Id);
1198 continue;
1199 }
1200
1201 Value *FinalValue =
1202 buildFADOutermostDimensionLoad(FAD, Builder, Array->getName());
1203 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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1204, __extension__ __PRETTY_FUNCTION__))
1204 "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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1204, __extension__ __PRETTY_FUNCTION__))
;
1205 IDToValue[Id] = FinalValue;
1206 isl_id_free(Id);
1207 }
1208 return true;
1209}
1210
1211Value *IslNodeBuilder::preloadUnconditionally(isl_set *AccessRange,
1212 isl_ast_build *Build,
1213 Instruction *AccInst) {
1214 isl_pw_multi_aff *PWAccRel = isl_pw_multi_aff_from_set(AccessRange);
1215 isl_ast_expr *Access =
1216 isl_ast_build_access_from_pw_multi_aff(Build, PWAccRel);
1217 auto *Address = isl_ast_expr_address_of(Access);
1218 auto *AddressValue = ExprBuilder.create(Address);
1219 Value *PreloadVal;
1220
1221 // Correct the type as the SAI might have a different type than the user
1222 // expects, especially if the base pointer is a struct.
1223 Type *Ty = AccInst->getType();
1224
1225 auto *Ptr = AddressValue;
1226 auto Name = Ptr->getName();
1227 auto AS = Ptr->getType()->getPointerAddressSpace();
1228 Ptr = Builder.CreatePointerCast(Ptr, Ty->getPointerTo(AS), Name + ".cast");
1229 PreloadVal = Builder.CreateLoad(Ptr, Name + ".load");
1230 if (LoadInst *PreloadInst = dyn_cast<LoadInst>(PreloadVal))
1231 PreloadInst->setAlignment(dyn_cast<LoadInst>(AccInst)->getAlignment());
1232
1233 // TODO: This is only a hot fix for SCoP sequences that use the same load
1234 // instruction contained and hoisted by one of the SCoPs.
1235 if (SE.isSCEVable(Ty))
1236 SE.forgetValue(AccInst);
1237
1238 return PreloadVal;
1239}
1240
1241Value *IslNodeBuilder::preloadInvariantLoad(const MemoryAccess &MA,
1242 isl_set *Domain) {
1243 isl_set *AccessRange = isl_map_range(MA.getAddressFunction().release());
1244 AccessRange = isl_set_gist_params(AccessRange, S.getContext().release());
1245
1246 if (!materializeParameters(AccessRange)) {
1247 isl_set_free(AccessRange);
1248 isl_set_free(Domain);
1249 return nullptr;
1250 }
1251
1252 auto *Build =
1253 isl_ast_build_from_context(isl_set_universe(S.getParamSpace().release()));
1254 isl_set *Universe = isl_set_universe(isl_set_get_space(Domain));
1255 bool AlwaysExecuted = isl_set_is_equal(Domain, Universe);
1256 isl_set_free(Universe);
1257
1258 Instruction *AccInst = MA.getAccessInstruction();
1259 Type *AccInstTy = AccInst->getType();
1260
1261 Value *PreloadVal = nullptr;
1262 if (AlwaysExecuted) {
1263 PreloadVal = preloadUnconditionally(AccessRange, Build, AccInst);
1264 isl_ast_build_free(Build);
1265 isl_set_free(Domain);
1266 return PreloadVal;
1267 }
1268
1269 if (!materializeParameters(Domain)) {
1270 isl_ast_build_free(Build);
1271 isl_set_free(AccessRange);
1272 isl_set_free(Domain);
1273 return nullptr;
1274 }
1275
1276 isl_ast_expr *DomainCond = isl_ast_build_expr_from_set(Build, Domain);
1277 Domain = nullptr;
1278
1279 ExprBuilder.setTrackOverflow(true);
1280 Value *Cond = ExprBuilder.create(DomainCond);
1281 Value *OverflowHappened = Builder.CreateNot(ExprBuilder.getOverflowState(),
1282 "polly.preload.cond.overflown");
1283 Cond = Builder.CreateAnd(Cond, OverflowHappened, "polly.preload.cond.result");
1284 ExprBuilder.setTrackOverflow(false);
1285
1286 if (!Cond->getType()->isIntegerTy(1))
1287 Cond = Builder.CreateIsNotNull(Cond);
1288
1289 BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(),
1290 &*Builder.GetInsertPoint(), &DT, &LI);
1291 CondBB->setName("polly.preload.cond");
1292
1293 BasicBlock *MergeBB = SplitBlock(CondBB, &CondBB->front(), &DT, &LI);
1294 MergeBB->setName("polly.preload.merge");
1295
1296 Function *F = Builder.GetInsertBlock()->getParent();
1297 LLVMContext &Context = F->getContext();
1298 BasicBlock *ExecBB = BasicBlock::Create(Context, "polly.preload.exec", F);
1299
1300 DT.addNewBlock(ExecBB, CondBB);
1301 if (Loop *L = LI.getLoopFor(CondBB))
1302 L->addBasicBlockToLoop(ExecBB, LI);
1303
1304 auto *CondBBTerminator = CondBB->getTerminator();
1305 Builder.SetInsertPoint(CondBBTerminator);
1306 Builder.CreateCondBr(Cond, ExecBB, MergeBB);
1307 CondBBTerminator->eraseFromParent();
1308
1309 Builder.SetInsertPoint(ExecBB);
1310 Builder.CreateBr(MergeBB);
1311
1312 Builder.SetInsertPoint(ExecBB->getTerminator());
1313 Value *PreAccInst = preloadUnconditionally(AccessRange, Build, AccInst);
1314 Builder.SetInsertPoint(MergeBB->getTerminator());
1315 auto *MergePHI = Builder.CreatePHI(
1316 AccInstTy, 2, "polly.preload." + AccInst->getName() + ".merge");
1317 PreloadVal = MergePHI;
1318
1319 if (!PreAccInst) {
1320 PreloadVal = nullptr;
1321 PreAccInst = UndefValue::get(AccInstTy);
1322 }
1323
1324 MergePHI->addIncoming(PreAccInst, ExecBB);
1325 MergePHI->addIncoming(Constant::getNullValue(AccInstTy), CondBB);
1326
1327 isl_ast_build_free(Build);
1328 return PreloadVal;
1329}
1330
1331bool IslNodeBuilder::preloadInvariantEquivClass(
1332 InvariantEquivClassTy &IAClass) {
1333 // For an equivalence class of invariant loads we pre-load the representing
1334 // element with the unified execution context. However, we have to map all
1335 // elements of the class to the one preloaded load as they are referenced
1336 // during the code generation and therefor need to be mapped.
1337 const MemoryAccessList &MAs = IAClass.InvariantAccesses;
1338 if (MAs.empty())
1339 return true;
1340
1341 MemoryAccess *MA = MAs.front();
1342 assert(MA->isArrayKind() && MA->isRead())(static_cast <bool> (MA->isArrayKind() && MA
->isRead()) ? void (0) : __assert_fail ("MA->isArrayKind() && MA->isRead()"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1342, __extension__ __PRETTY_FUNCTION__))
;
1343
1344 // If the access function was already mapped, the preload of this equivalence
1345 // class was triggered earlier already and doesn't need to be done again.
1346 if (ValueMap.count(MA->getAccessInstruction()))
1347 return true;
1348
1349 // Check for recursion which can be caused by additional constraints, e.g.,
1350 // non-finite loop constraints. In such a case we have to bail out and insert
1351 // a "false" runtime check that will cause the original code to be executed.
1352 auto PtrId = std::make_pair(IAClass.IdentifyingPointer, IAClass.AccessType);
1353 if (!PreloadedPtrs.insert(PtrId).second)
1354 return false;
1355
1356 // The execution context of the IAClass.
1357 isl::set &ExecutionCtx = IAClass.ExecutionContext;
1358
1359 // If the base pointer of this class is dependent on another one we have to
1360 // make sure it was preloaded already.
1361 auto *SAI = MA->getScopArrayInfo();
1362 if (auto *BaseIAClass = S.lookupInvariantEquivClass(SAI->getBasePtr())) {
1363 if (!preloadInvariantEquivClass(*BaseIAClass))
1364 return false;
1365
1366 // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx and
1367 // we need to refine the ExecutionCtx.
1368 isl::set BaseExecutionCtx = BaseIAClass->ExecutionContext;
1369 ExecutionCtx = ExecutionCtx.intersect(BaseExecutionCtx);
1370 }
1371
1372 // If the size of a dimension is dependent on another class, make sure it is
1373 // preloaded.
1374 for (unsigned i = 1, e = SAI->getNumberOfDimensions(); i < e; ++i) {
1375 const SCEV *Dim = SAI->getDimensionSize(i);
1376 SetVector<Value *> Values;
1377 findValues(Dim, SE, Values);
1378 for (auto *Val : Values) {
1379 if (auto *BaseIAClass = S.lookupInvariantEquivClass(Val)) {
1380 if (!preloadInvariantEquivClass(*BaseIAClass))
1381 return false;
1382
1383 // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx
1384 // and we need to refine the ExecutionCtx.
1385 isl::set BaseExecutionCtx = BaseIAClass->ExecutionContext;
1386 ExecutionCtx = ExecutionCtx.intersect(BaseExecutionCtx);
1387 }
1388 }
1389 }
1390
1391 Instruction *AccInst = MA->getAccessInstruction();
1392 Type *AccInstTy = AccInst->getType();
1393
1394 Value *PreloadVal = preloadInvariantLoad(*MA, ExecutionCtx.copy());
1395 if (!PreloadVal)
1396 return false;
1397
1398 for (const MemoryAccess *MA : MAs) {
1399 Instruction *MAAccInst = MA->getAccessInstruction();
1400 assert(PreloadVal->getType() == MAAccInst->getType())(static_cast <bool> (PreloadVal->getType() == MAAccInst
->getType()) ? void (0) : __assert_fail ("PreloadVal->getType() == MAAccInst->getType()"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1400, __extension__ __PRETTY_FUNCTION__))
;
1401 ValueMap[MAAccInst] = PreloadVal;
1402 }
1403
1404 if (SE.isSCEVable(AccInstTy)) {
1405 isl_id *ParamId = S.getIdForParam(SE.getSCEV(AccInst)).release();
1406 if (ParamId)
1407 IDToValue[ParamId] = PreloadVal;
1408 isl_id_free(ParamId);
1409 }
1410
1411 BasicBlock *EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
1412 auto *Alloca = new AllocaInst(AccInstTy, DL.getAllocaAddrSpace(),
1413 AccInst->getName() + ".preload.s2a");
1414 Alloca->insertBefore(&*EntryBB->getFirstInsertionPt());
1415 Builder.CreateStore(PreloadVal, Alloca);
1416 ValueMapT PreloadedPointer;
1417 PreloadedPointer[PreloadVal] = AccInst;
1418 Annotator.addAlternativeAliasBases(PreloadedPointer);
1419
1420 for (auto *DerivedSAI : SAI->getDerivedSAIs()) {
1421 Value *BasePtr = DerivedSAI->getBasePtr();
1422
1423 for (const MemoryAccess *MA : MAs) {
1424 // As the derived SAI information is quite coarse, any load from the
1425 // current SAI could be the base pointer of the derived SAI, however we
1426 // should only change the base pointer of the derived SAI if we actually
1427 // preloaded it.
1428 if (BasePtr == MA->getOriginalBaseAddr()) {
1429 assert(BasePtr->getType() == PreloadVal->getType())(static_cast <bool> (BasePtr->getType() == PreloadVal
->getType()) ? void (0) : __assert_fail ("BasePtr->getType() == PreloadVal->getType()"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1429, __extension__ __PRETTY_FUNCTION__))
;
1430 DerivedSAI->setBasePtr(PreloadVal);
1431 }
1432
1433 // For scalar derived SAIs we remap the alloca used for the derived value.
1434 if (BasePtr == MA->getAccessInstruction())
1435 ScalarMap[DerivedSAI] = Alloca;
1436 }
1437 }
1438
1439 for (const MemoryAccess *MA : MAs) {
1440 Instruction *MAAccInst = MA->getAccessInstruction();
1441 // Use the escape system to get the correct value to users outside the SCoP.
1442 BlockGenerator::EscapeUserVectorTy EscapeUsers;
1443 for (auto *U : MAAccInst->users())
1444 if (Instruction *UI = dyn_cast<Instruction>(U))
1445 if (!S.contains(UI))
1446 EscapeUsers.push_back(UI);
1447
1448 if (EscapeUsers.empty())
1449 continue;
1450
1451 EscapeMap[MA->getAccessInstruction()] =
1452 std::make_pair(Alloca, std::move(EscapeUsers));
1453 }
1454
1455 return true;
1456}
1457
1458void IslNodeBuilder::allocateNewArrays(BBPair StartExitBlocks) {
1459 for (auto &SAI : S.arrays()) {
1460 if (SAI->getBasePtr())
1461 continue;
1462
1463 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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1465, __extension__ __PRETTY_FUNCTION__))
1464 "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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1465, __extension__ __PRETTY_FUNCTION__))
1465 "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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1465, __extension__ __PRETTY_FUNCTION__))
;
1466
1467 Type *NewArrayType = nullptr;
1468
1469 // Get the size of the array = size(dim_1)*...*size(dim_n)
1470 uint64_t ArraySizeInt = 1;
1471 for (int i = SAI->getNumberOfDimensions() - 1; i >= 0; i--) {
1472 auto *DimSize = SAI->getDimensionSize(i);
1473 unsigned UnsignedDimSize = static_cast<const SCEVConstant *>(DimSize)
1474 ->getAPInt()
1475 .getLimitedValue();
1476
1477 if (!NewArrayType)
1478 NewArrayType = SAI->getElementType();
1479
1480 NewArrayType = ArrayType::get(NewArrayType, UnsignedDimSize);
1481 ArraySizeInt *= UnsignedDimSize;
1482 }
1483
1484 if (SAI->isOnHeap()) {
1485 LLVMContext &Ctx = NewArrayType->getContext();
1486
1487 // Get the IntPtrTy from the Datalayout
1488 auto IntPtrTy = DL.getIntPtrType(Ctx);
1489
1490 // Get the size of the element type in bits
1491 unsigned Size = SAI->getElemSizeInBytes();
1492
1493 // Insert the malloc call at polly.start
1494 auto InstIt = std::get<0>(StartExitBlocks)->getTerminator();
1495 auto *CreatedArray = CallInst::CreateMalloc(
1496 &*InstIt, IntPtrTy, SAI->getElementType(),
1497 ConstantInt::get(Type::getInt64Ty(Ctx), Size),
1498 ConstantInt::get(Type::getInt64Ty(Ctx), ArraySizeInt), nullptr,
1499 SAI->getName());
1500
1501 SAI->setBasePtr(CreatedArray);
1502
1503 // Insert the free call at polly.exiting
1504 CallInst::CreateFree(CreatedArray,
1505 std::get<1>(StartExitBlocks)->getTerminator());
1506 } else {
1507 auto InstIt = Builder.GetInsertBlock()
1508 ->getParent()
1509 ->getEntryBlock()
1510 .getTerminator();
1511
1512 auto *CreatedArray = new AllocaInst(NewArrayType, DL.getAllocaAddrSpace(),
1513 SAI->getName(), &*InstIt);
1514 CreatedArray->setAlignment(PollyTargetFirstLevelCacheLineSize);
1515 SAI->setBasePtr(CreatedArray);
1516 }
1517 }
1518}
1519
1520bool IslNodeBuilder::preloadInvariantLoads() {
1521 auto &InvariantEquivClasses = S.getInvariantAccesses();
1522 if (InvariantEquivClasses.empty())
1523 return true;
1524
1525 BasicBlock *PreLoadBB = SplitBlock(Builder.GetInsertBlock(),
1526 &*Builder.GetInsertPoint(), &DT, &LI);
1527 PreLoadBB->setName("polly.preload.begin");
1528 Builder.SetInsertPoint(&PreLoadBB->front());
1529
1530 for (auto &IAClass : InvariantEquivClasses)
1531 if (!preloadInvariantEquivClass(IAClass))
1532 return false;
1533
1534 return true;
1535}
1536
1537void IslNodeBuilder::addParameters(__isl_take isl_set *Context) {
1538 // Materialize values for the parameters of the SCoP.
1539 materializeParameters();
1540
1541 // materialize the outermost dimension parameters for a Fortran array.
1542 // NOTE: materializeParameters() does not work since it looks through
1543 // the SCEVs. We don't have a corresponding SCEV for the array size
1544 // parameter
1545 materializeFortranArrayOutermostDimension();
1546
1547 // Generate values for the current loop iteration for all surrounding loops.
1548 //
1549 // We may also reference loops outside of the scop which do not contain the
1550 // scop itself, but as the number of such scops may be arbitrarily large we do
1551 // not generate code for them here, but only at the point of code generation
1552 // where these values are needed.
1553 Loop *L = LI.getLoopFor(S.getEntry());
1554
1555 while (L != nullptr && S.contains(L))
1556 L = L->getParentLoop();
1557
1558 while (L != nullptr) {
1559 materializeNonScopLoopInductionVariable(L);
1560 L = L->getParentLoop();
1561 }
1562
1563 isl_set_free(Context);
1564}
1565
1566Value *IslNodeBuilder::generateSCEV(const SCEV *Expr) {
1567 /// We pass the insert location of our Builder, as Polly ensures during IR
1568 /// generation that there is always a valid CFG into which instructions are
1569 /// inserted. As a result, the insertpoint is known to be always followed by a
1570 /// terminator instruction. This means the insert point may be specified by a
1571 /// terminator instruction, but it can never point to an ->end() iterator
1572 /// which does not have a corresponding instruction. Hence, dereferencing
1573 /// the insertpoint to obtain an instruction is known to be save.
1574 ///
1575 /// We also do not need to update the Builder here, as new instructions are
1576 /// always inserted _before_ the given InsertLocation. As a result, the
1577 /// insert location remains valid.
1578 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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1579, __extension__ __PRETTY_FUNCTION__))
1579 "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-7~svn329677/tools/polly/lib/CodeGen/IslNodeBuilder.cpp"
, 1579, __extension__ __PRETTY_FUNCTION__))
;
1580 Instruction *InsertLocation = &*Builder.GetInsertPoint();
1581 return expandCodeFor(S, SE, DL, "polly", Expr, Expr->getType(),
1582 InsertLocation, &ValueMap,
1583 StartBlock->getSinglePredecessor());
1584}
1585
1586/// The AST expression we generate to perform the run-time check assumes
1587/// computations on integer types of infinite size. As we only use 64-bit
1588/// arithmetic we check for overflows, in case of which we set the result
1589/// of this run-time check to false to be conservatively correct,
1590Value *IslNodeBuilder::createRTC(isl_ast_expr *Condition) {
1591 auto ExprBuilder = getExprBuilder();
1592
1593 // In case the AST expression has integers larger than 64 bit, bail out. The
1594 // resulting LLVM-IR will contain operations on types that use more than 64
1595 // bits. These are -- in case wrapping intrinsics are used -- translated to
1596 // runtime library calls that are not available on all systems (e.g., Android)
1597 // and consequently will result in linker errors.
1598 if (ExprBuilder.hasLargeInts(isl::manage_copy(Condition))) {
1599 isl_ast_expr_free(Condition);
1600 return Builder.getFalse();
1601 }
1602
1603 ExprBuilder.setTrackOverflow(true);
1604 Value *RTC = ExprBuilder.create(Condition);
1605 if (!RTC->getType()->isIntegerTy(1))
1606 RTC = Builder.CreateIsNotNull(RTC);
1607 Value *OverflowHappened =
1608 Builder.CreateNot(ExprBuilder.getOverflowState(), "polly.rtc.overflown");
1609
1610 if (PollyGenerateRTCPrint) {
1611 auto *F = Builder.GetInsertBlock()->getParent();
1612 RuntimeDebugBuilder::createCPUPrinter(
1613 Builder,
1614 "F: " + F->getName().str() + " R: " + S.getRegion().getNameStr() +
1615 "RTC: ",
1616 RTC, " Overflow: ", OverflowHappened,
1617 "\n"
1618 " (0 failed, -1 succeeded)\n"
1619 " (if one or both are 0 falling back to original code, if both are -1 "
1620 "executing Polly code)\n");
1621 }
1622
1623 RTC = Builder.CreateAnd(RTC, OverflowHappened, "polly.rtc.result");
1624 ExprBuilder.setTrackOverflow(false);
1625
1626 if (!isa<ConstantInt>(RTC))
1627 VersionedScops++;
1628
1629 return RTC;
1630}