Bug Summary

File:tools/polly/lib/CodeGen/IslNodeBuilder.cpp
Warning:line 1217, column 20
Called C++ object pointer is null

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