File: | polly/lib/CodeGen/IslNodeBuilder.cpp |
Warning: | line 1217, column 20 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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 | ||||
70 | using namespace llvm; | |||
71 | using namespace polly; | |||
72 | ||||
73 | #define DEBUG_TYPE"polly-codegen" "polly-codegen" | |||
74 | ||||
75 | STATISTIC(VersionedScops, "Number of SCoPs that required versioning.")static llvm::Statistic VersionedScops = {"polly-codegen", "VersionedScops" , "Number of SCoPs that required versioning."}; | |||
76 | ||||
77 | STATISTIC(SequentialLoops, "Number of generated sequential for-loops")static llvm::Statistic SequentialLoops = {"polly-codegen", "SequentialLoops" , "Number of generated sequential for-loops"}; | |||
78 | STATISTIC(ParallelLoops, "Number of generated parallel for-loops")static llvm::Statistic ParallelLoops = {"polly-codegen", "ParallelLoops" , "Number of generated parallel for-loops"}; | |||
79 | STATISTIC(VectorLoops, "Number of generated vector for-loops")static llvm::Statistic VectorLoops = {"polly-codegen", "VectorLoops" , "Number of generated vector for-loops"}; | |||
80 | STATISTIC(IfConditions, "Number of generated if-conditions")static llvm::Statistic IfConditions = {"polly-codegen", "IfConditions" , "Number of generated if-conditions"}; | |||
81 | ||||
82 | /// OpenMP backend options | |||
83 | enum class OpenMPBackend { GNU, LLVM }; | |||
84 | ||||
85 | static 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. | |||
94 | static 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 | ||||
99 | static 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 | ||||
104 | static 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 | ||||
110 | isl::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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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. | |||
150 | static 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 | ||||
166 | int 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-11~++20200309111110+2c36c23f347/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. | |||
208 | static 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 | ||||
228 | void 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-11~++20200309111110+2c36c23f347/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. | |||
275 | static 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. | |||
295 | static void | |||
296 | addReferencesFromStmtUnionSet(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 * | |||
304 | IslNodeBuilder::getScheduleForAstNode(__isl_keep isl_ast_node *For) { | |||
305 | return IslAstInfo::getSchedule(For); | |||
306 | } | |||
307 | ||||
308 | void 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 | ||||
361 | void 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 | ||||
377 | Value *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 | ||||
384 | void 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 | ||||
408 | void 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 | ||||
433 | void 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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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. | |||
503 | static 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-11~++20200309111110+2c36c23f347/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 | ||||
514 | void 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. | |||
603 | static 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 | ||||
617 | void 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. | |||
738 | static 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 | ||||
762 | void 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 | ||||
783 | void 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 * | |||
833 | IslNodeBuilder::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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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 | ||||
904 | void IslNodeBuilder::createSubstitutions(__isl_take isl_ast_expr *Expr, | |||
905 | ScopStmt *Stmt, LoopToScevMapT <S) { | |||
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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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_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-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/IslNodeBuilder.cpp" , 909, __PRETTY_FUNCTION__)) | |||
909 | "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-11~++20200309111110+2c36c23f347/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 | ||||
923 | void 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 | ||||
941 | void 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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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 | ||||
959 | Value *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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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 | ||||
970 | void 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 | ||||
1001 | void 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 | ||||
1011 | void 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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/IslNodeBuilder.cpp" , 1032); | |||
1033 | } | |||
1034 | ||||
1035 | bool 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 | ||||
1099 | bool 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 | ||||
1110 | bool 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 | |||
1133 | static 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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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 | ||||
1162 | bool 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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/IslNodeBuilder.cpp" , 1189, __PRETTY_FUNCTION__)); | |||
1190 | IDToValue[Id] = FinalValue; | |||
1191 | isl_id_free(Id); | |||
1192 | } | |||
1193 | return true; | |||
1194 | } | |||
1195 | ||||
1196 | Value *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
| |||
| ||||
1216 | PreloadInst->setAlignment( | |||
1217 | MaybeAlign(dyn_cast<LoadInst>(AccInst)->getAlignment())); | |||
| ||||
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 | ||||
1227 | Value *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 | ||||
1317 | bool 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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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 | ||||
1444 | void 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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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 | ||||
1507 | bool 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 | ||||
1524 | void 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 | ||||
1553 | Value *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-11~++20200309111110+2c36c23f347/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-11~++20200309111110+2c36c23f347/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, | |||
1577 | Value *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 | } |