Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

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