Bug Summary

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