File: | polly/lib/CodeGen/BlockGenerators.cpp |
Warning: | line 1170, column 40 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===--- BlockGenerators.cpp - Generate code for statements -----*- C++ -*-===// | |||
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 implements the BlockGenerator and VectorBlockGenerator classes, | |||
10 | // which generate sequential code and vectorized code for a polyhedral | |||
11 | // statement, respectively. | |||
12 | // | |||
13 | //===----------------------------------------------------------------------===// | |||
14 | ||||
15 | #include "polly/CodeGen/BlockGenerators.h" | |||
16 | #include "polly/CodeGen/IslExprBuilder.h" | |||
17 | #include "polly/CodeGen/RuntimeDebugBuilder.h" | |||
18 | #include "polly/Options.h" | |||
19 | #include "polly/ScopInfo.h" | |||
20 | #include "polly/Support/ScopHelper.h" | |||
21 | #include "polly/Support/VirtualInstruction.h" | |||
22 | #include "llvm/Analysis/LoopInfo.h" | |||
23 | #include "llvm/Analysis/RegionInfo.h" | |||
24 | #include "llvm/Analysis/ScalarEvolution.h" | |||
25 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" | |||
26 | #include "llvm/Transforms/Utils/Local.h" | |||
27 | #include "isl/ast.h" | |||
28 | #include <deque> | |||
29 | ||||
30 | using namespace llvm; | |||
31 | using namespace polly; | |||
32 | ||||
33 | static cl::opt<bool> Aligned("enable-polly-aligned", | |||
34 | cl::desc("Assumed aligned memory accesses."), | |||
35 | cl::Hidden, cl::init(false), cl::ZeroOrMore, | |||
36 | cl::cat(PollyCategory)); | |||
37 | ||||
38 | bool PollyDebugPrinting; | |||
39 | static cl::opt<bool, true> DebugPrintingX( | |||
40 | "polly-codegen-add-debug-printing", | |||
41 | cl::desc("Add printf calls that show the values loaded/stored."), | |||
42 | cl::location(PollyDebugPrinting), cl::Hidden, cl::init(false), | |||
43 | cl::ZeroOrMore, cl::cat(PollyCategory)); | |||
44 | ||||
45 | static cl::opt<bool> TraceStmts( | |||
46 | "polly-codegen-trace-stmts", | |||
47 | cl::desc("Add printf calls that print the statement being executed"), | |||
48 | cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory)); | |||
49 | ||||
50 | static cl::opt<bool> TraceScalars( | |||
51 | "polly-codegen-trace-scalars", | |||
52 | cl::desc("Add printf calls that print the values of all scalar values " | |||
53 | "used in a statement. Requires -polly-codegen-trace-stmts."), | |||
54 | cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory)); | |||
55 | ||||
56 | BlockGenerator::BlockGenerator( | |||
57 | PollyIRBuilder &B, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, | |||
58 | AllocaMapTy &ScalarMap, EscapeUsersAllocaMapTy &EscapeMap, | |||
59 | ValueMapT &GlobalMap, IslExprBuilder *ExprBuilder, BasicBlock *StartBlock) | |||
60 | : Builder(B), LI(LI), SE(SE), ExprBuilder(ExprBuilder), DT(DT), | |||
61 | EntryBB(nullptr), ScalarMap(ScalarMap), EscapeMap(EscapeMap), | |||
62 | GlobalMap(GlobalMap), StartBlock(StartBlock) {} | |||
63 | ||||
64 | Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old, | |||
65 | ValueMapT &BBMap, | |||
66 | LoopToScevMapT <S, | |||
67 | Loop *L) const { | |||
68 | if (!SE.isSCEVable(Old->getType())) | |||
69 | return nullptr; | |||
70 | ||||
71 | const SCEV *Scev = SE.getSCEVAtScope(Old, L); | |||
72 | if (!Scev) | |||
73 | return nullptr; | |||
74 | ||||
75 | if (isa<SCEVCouldNotCompute>(Scev)) | |||
76 | return nullptr; | |||
77 | ||||
78 | const SCEV *NewScev = SCEVLoopAddRecRewriter::rewrite(Scev, LTS, SE); | |||
79 | ValueMapT VTV; | |||
80 | VTV.insert(BBMap.begin(), BBMap.end()); | |||
81 | VTV.insert(GlobalMap.begin(), GlobalMap.end()); | |||
82 | ||||
83 | Scop &S = *Stmt.getParent(); | |||
84 | const DataLayout &DL = S.getFunction().getParent()->getDataLayout(); | |||
85 | auto IP = Builder.GetInsertPoint(); | |||
86 | ||||
87 | assert(IP != Builder.GetInsertBlock()->end() &&((IP != Builder.GetInsertBlock()->end() && "Only instructions can be insert points for SCEVExpander" ) ? static_cast<void> (0) : __assert_fail ("IP != Builder.GetInsertBlock()->end() && \"Only instructions can be insert points for SCEVExpander\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 88, __PRETTY_FUNCTION__)) | |||
88 | "Only instructions can be insert points for SCEVExpander")((IP != Builder.GetInsertBlock()->end() && "Only instructions can be insert points for SCEVExpander" ) ? static_cast<void> (0) : __assert_fail ("IP != Builder.GetInsertBlock()->end() && \"Only instructions can be insert points for SCEVExpander\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 88, __PRETTY_FUNCTION__)); | |||
89 | Value *Expanded = | |||
90 | expandCodeFor(S, SE, DL, "polly", NewScev, Old->getType(), &*IP, &VTV, | |||
91 | StartBlock->getSinglePredecessor()); | |||
92 | ||||
93 | BBMap[Old] = Expanded; | |||
94 | return Expanded; | |||
95 | } | |||
96 | ||||
97 | Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap, | |||
98 | LoopToScevMapT <S, Loop *L) const { | |||
99 | ||||
100 | auto lookupGlobally = [this](Value *Old) -> Value * { | |||
101 | Value *New = GlobalMap.lookup(Old); | |||
102 | if (!New) | |||
103 | return nullptr; | |||
104 | ||||
105 | // Required by: | |||
106 | // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded.ll | |||
107 | // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_different_bb.ll | |||
108 | // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_pass_only_needed.ll | |||
109 | // * Isl/CodeGen/OpenMP/invariant_base_pointers_preloaded.ll | |||
110 | // * Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll | |||
111 | // * Isl/CodeGen/OpenMP/single_loop_with_loop_invariant_baseptr.ll | |||
112 | // GlobalMap should be a mapping from (value in original SCoP) to (copied | |||
113 | // value in generated SCoP), without intermediate mappings, which might | |||
114 | // easily require transitiveness as well. | |||
115 | if (Value *NewRemapped = GlobalMap.lookup(New)) | |||
116 | New = NewRemapped; | |||
117 | ||||
118 | // No test case for this code. | |||
119 | if (Old->getType()->getScalarSizeInBits() < | |||
120 | New->getType()->getScalarSizeInBits()) | |||
121 | New = Builder.CreateTruncOrBitCast(New, Old->getType()); | |||
122 | ||||
123 | return New; | |||
124 | }; | |||
125 | ||||
126 | Value *New = nullptr; | |||
127 | auto VUse = VirtualUse::create(&Stmt, L, Old, true); | |||
128 | switch (VUse.getKind()) { | |||
129 | case VirtualUse::Block: | |||
130 | // BasicBlock are constants, but the BlockGenerator copies them. | |||
131 | New = BBMap.lookup(Old); | |||
132 | break; | |||
133 | ||||
134 | case VirtualUse::Constant: | |||
135 | // Used by: | |||
136 | // * Isl/CodeGen/OpenMP/reference-argument-from-non-affine-region.ll | |||
137 | // Constants should not be redefined. In this case, the GlobalMap just | |||
138 | // contains a mapping to the same constant, which is unnecessary, but | |||
139 | // harmless. | |||
140 | if ((New = lookupGlobally(Old))) | |||
141 | break; | |||
142 | ||||
143 | assert(!BBMap.count(Old))((!BBMap.count(Old)) ? static_cast<void> (0) : __assert_fail ("!BBMap.count(Old)", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 143, __PRETTY_FUNCTION__)); | |||
144 | New = Old; | |||
145 | break; | |||
146 | ||||
147 | case VirtualUse::ReadOnly: | |||
148 | assert(!GlobalMap.count(Old))((!GlobalMap.count(Old)) ? static_cast<void> (0) : __assert_fail ("!GlobalMap.count(Old)", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 148, __PRETTY_FUNCTION__)); | |||
149 | ||||
150 | // Required for: | |||
151 | // * Isl/CodeGen/MemAccess/create_arrays.ll | |||
152 | // * Isl/CodeGen/read-only-scalars.ll | |||
153 | // * ScheduleOptimizer/pattern-matching-based-opts_10.ll | |||
154 | // For some reason these reload a read-only value. The reloaded value ends | |||
155 | // up in BBMap, buts its value should be identical. | |||
156 | // | |||
157 | // Required for: | |||
158 | // * Isl/CodeGen/OpenMP/single_loop_with_param.ll | |||
159 | // The parallel subfunctions need to reference the read-only value from the | |||
160 | // parent function, this is done by reloading them locally. | |||
161 | if ((New = BBMap.lookup(Old))) | |||
162 | break; | |||
163 | ||||
164 | New = Old; | |||
165 | break; | |||
166 | ||||
167 | case VirtualUse::Synthesizable: | |||
168 | // Used by: | |||
169 | // * Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll | |||
170 | // * Isl/CodeGen/OpenMP/recomputed-srem.ll | |||
171 | // * Isl/CodeGen/OpenMP/reference-other-bb.ll | |||
172 | // * Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll | |||
173 | // For some reason synthesizable values end up in GlobalMap. Their values | |||
174 | // are the same as trySynthesizeNewValue would return. The legacy | |||
175 | // implementation prioritized GlobalMap, so this is what we do here as well. | |||
176 | // Ideally, synthesizable values should not end up in GlobalMap. | |||
177 | if ((New = lookupGlobally(Old))) | |||
178 | break; | |||
179 | ||||
180 | // Required for: | |||
181 | // * Isl/CodeGen/RuntimeDebugBuilder/combine_different_values.ll | |||
182 | // * Isl/CodeGen/getNumberOfIterations.ll | |||
183 | // * Isl/CodeGen/non_affine_float_compare.ll | |||
184 | // * ScheduleOptimizer/pattern-matching-based-opts_10.ll | |||
185 | // Ideally, synthesizable values are synthesized by trySynthesizeNewValue, | |||
186 | // not precomputed (SCEVExpander has its own caching mechanism). | |||
187 | // These tests fail without this, but I think trySynthesizeNewValue would | |||
188 | // just re-synthesize the same instructions. | |||
189 | if ((New = BBMap.lookup(Old))) | |||
190 | break; | |||
191 | ||||
192 | New = trySynthesizeNewValue(Stmt, Old, BBMap, LTS, L); | |||
193 | break; | |||
194 | ||||
195 | case VirtualUse::Hoisted: | |||
196 | // TODO: Hoisted invariant loads should be found in GlobalMap only, but not | |||
197 | // redefined locally (which will be ignored anyway). That is, the following | |||
198 | // assertion should apply: assert(!BBMap.count(Old)) | |||
199 | ||||
200 | New = lookupGlobally(Old); | |||
201 | break; | |||
202 | ||||
203 | case VirtualUse::Intra: | |||
204 | case VirtualUse::Inter: | |||
205 | assert(!GlobalMap.count(Old) &&((!GlobalMap.count(Old) && "Intra and inter-stmt values are never global" ) ? static_cast<void> (0) : __assert_fail ("!GlobalMap.count(Old) && \"Intra and inter-stmt values are never global\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 206, __PRETTY_FUNCTION__)) | |||
206 | "Intra and inter-stmt values are never global")((!GlobalMap.count(Old) && "Intra and inter-stmt values are never global" ) ? static_cast<void> (0) : __assert_fail ("!GlobalMap.count(Old) && \"Intra and inter-stmt values are never global\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 206, __PRETTY_FUNCTION__)); | |||
207 | New = BBMap.lookup(Old); | |||
208 | break; | |||
209 | } | |||
210 | assert(New && "Unexpected scalar dependence in region!")((New && "Unexpected scalar dependence in region!") ? static_cast<void> (0) : __assert_fail ("New && \"Unexpected scalar dependence in region!\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 210, __PRETTY_FUNCTION__)); | |||
211 | return New; | |||
212 | } | |||
213 | ||||
214 | void BlockGenerator::copyInstScalar(ScopStmt &Stmt, Instruction *Inst, | |||
215 | ValueMapT &BBMap, LoopToScevMapT <S) { | |||
216 | // We do not generate debug intrinsics as we did not investigate how to | |||
217 | // copy them correctly. At the current state, they just crash the code | |||
218 | // generation as the meta-data operands are not correctly copied. | |||
219 | if (isa<DbgInfoIntrinsic>(Inst)) | |||
220 | return; | |||
221 | ||||
222 | Instruction *NewInst = Inst->clone(); | |||
223 | ||||
224 | // Replace old operands with the new ones. | |||
225 | for (Value *OldOperand : Inst->operands()) { | |||
226 | Value *NewOperand = | |||
227 | getNewValue(Stmt, OldOperand, BBMap, LTS, getLoopForStmt(Stmt)); | |||
228 | ||||
229 | if (!NewOperand) { | |||
230 | assert(!isa<StoreInst>(NewInst) &&((!isa<StoreInst>(NewInst) && "Store instructions are always needed!" ) ? static_cast<void> (0) : __assert_fail ("!isa<StoreInst>(NewInst) && \"Store instructions are always needed!\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 231, __PRETTY_FUNCTION__)) | |||
231 | "Store instructions are always needed!")((!isa<StoreInst>(NewInst) && "Store instructions are always needed!" ) ? static_cast<void> (0) : __assert_fail ("!isa<StoreInst>(NewInst) && \"Store instructions are always needed!\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 231, __PRETTY_FUNCTION__)); | |||
232 | NewInst->deleteValue(); | |||
233 | return; | |||
234 | } | |||
235 | ||||
236 | NewInst->replaceUsesOfWith(OldOperand, NewOperand); | |||
237 | } | |||
238 | ||||
239 | Builder.Insert(NewInst); | |||
240 | BBMap[Inst] = NewInst; | |||
241 | ||||
242 | // When copying the instruction onto the Module meant for the GPU, | |||
243 | // debug metadata attached to an instruction causes all related | |||
244 | // metadata to be pulled into the Module. This includes the DICompileUnit, | |||
245 | // which will not be listed in llvm.dbg.cu of the Module since the Module | |||
246 | // doesn't contain one. This fails the verification of the Module and the | |||
247 | // subsequent generation of the ASM string. | |||
248 | if (NewInst->getModule() != Inst->getModule()) | |||
249 | NewInst->setDebugLoc(llvm::DebugLoc()); | |||
250 | ||||
251 | if (!NewInst->getType()->isVoidTy()) | |||
252 | NewInst->setName("p_" + Inst->getName()); | |||
253 | } | |||
254 | ||||
255 | Value * | |||
256 | BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst, | |||
257 | ValueMapT &BBMap, LoopToScevMapT <S, | |||
258 | isl_id_to_ast_expr *NewAccesses) { | |||
259 | const MemoryAccess &MA = Stmt.getArrayAccessFor(Inst); | |||
260 | return generateLocationAccessed( | |||
261 | Stmt, getLoopForStmt(Stmt), | |||
262 | Inst.isNull() ? nullptr : Inst.getPointerOperand(), BBMap, LTS, | |||
263 | NewAccesses, MA.getId().release(), MA.getAccessValue()->getType()); | |||
264 | } | |||
265 | ||||
266 | Value *BlockGenerator::generateLocationAccessed( | |||
267 | ScopStmt &Stmt, Loop *L, Value *Pointer, ValueMapT &BBMap, | |||
268 | LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses, __isl_take isl_id *Id, | |||
269 | Type *ExpectedType) { | |||
270 | isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(NewAccesses, Id); | |||
271 | ||||
272 | if (AccessExpr) { | |||
273 | AccessExpr = isl_ast_expr_address_of(AccessExpr); | |||
274 | auto Address = ExprBuilder->create(AccessExpr); | |||
275 | ||||
276 | // Cast the address of this memory access to a pointer type that has the | |||
277 | // same element type as the original access, but uses the address space of | |||
278 | // the newly generated pointer. | |||
279 | auto OldPtrTy = ExpectedType->getPointerTo(); | |||
280 | auto NewPtrTy = Address->getType(); | |||
281 | OldPtrTy = PointerType::get(OldPtrTy->getElementType(), | |||
282 | NewPtrTy->getPointerAddressSpace()); | |||
283 | ||||
284 | if (OldPtrTy != NewPtrTy) | |||
285 | Address = Builder.CreateBitOrPointerCast(Address, OldPtrTy); | |||
286 | return Address; | |||
287 | } | |||
288 | assert(((Pointer && "If expression was not generated, must use the original pointer value" ) ? static_cast<void> (0) : __assert_fail ("Pointer && \"If expression was not generated, must use the original pointer value\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 290, __PRETTY_FUNCTION__)) | |||
289 | Pointer &&((Pointer && "If expression was not generated, must use the original pointer value" ) ? static_cast<void> (0) : __assert_fail ("Pointer && \"If expression was not generated, must use the original pointer value\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 290, __PRETTY_FUNCTION__)) | |||
290 | "If expression was not generated, must use the original pointer value")((Pointer && "If expression was not generated, must use the original pointer value" ) ? static_cast<void> (0) : __assert_fail ("Pointer && \"If expression was not generated, must use the original pointer value\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 290, __PRETTY_FUNCTION__)); | |||
291 | return getNewValue(Stmt, Pointer, BBMap, LTS, L); | |||
292 | } | |||
293 | ||||
294 | Value * | |||
295 | BlockGenerator::getImplicitAddress(MemoryAccess &Access, Loop *L, | |||
296 | LoopToScevMapT <S, ValueMapT &BBMap, | |||
297 | __isl_keep isl_id_to_ast_expr *NewAccesses) { | |||
298 | if (Access.isLatestArrayKind()) | |||
299 | return generateLocationAccessed(*Access.getStatement(), L, nullptr, BBMap, | |||
300 | LTS, NewAccesses, Access.getId().release(), | |||
301 | Access.getAccessValue()->getType()); | |||
302 | ||||
303 | return getOrCreateAlloca(Access); | |||
304 | } | |||
305 | ||||
306 | Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const { | |||
307 | auto *StmtBB = Stmt.getEntryBlock(); | |||
308 | return LI.getLoopFor(StmtBB); | |||
309 | } | |||
310 | ||||
311 | Value *BlockGenerator::generateArrayLoad(ScopStmt &Stmt, LoadInst *Load, | |||
312 | ValueMapT &BBMap, LoopToScevMapT <S, | |||
313 | isl_id_to_ast_expr *NewAccesses) { | |||
314 | if (Value *PreloadLoad = GlobalMap.lookup(Load)) | |||
315 | return PreloadLoad; | |||
316 | ||||
317 | Value *NewPointer = | |||
318 | generateLocationAccessed(Stmt, Load, BBMap, LTS, NewAccesses); | |||
319 | Value *ScalarLoad = Builder.CreateAlignedLoad(NewPointer, Load->getAlign(), | |||
320 | Load->getName() + "_p_scalar_"); | |||
321 | ||||
322 | if (PollyDebugPrinting) | |||
323 | RuntimeDebugBuilder::createCPUPrinter(Builder, "Load from ", NewPointer, | |||
324 | ": ", ScalarLoad, "\n"); | |||
325 | ||||
326 | return ScalarLoad; | |||
327 | } | |||
328 | ||||
329 | void BlockGenerator::generateArrayStore(ScopStmt &Stmt, StoreInst *Store, | |||
330 | ValueMapT &BBMap, LoopToScevMapT <S, | |||
331 | isl_id_to_ast_expr *NewAccesses) { | |||
332 | MemoryAccess &MA = Stmt.getArrayAccessFor(Store); | |||
333 | isl::set AccDom = MA.getAccessRelation().domain(); | |||
334 | std::string Subject = MA.getId().get_name(); | |||
335 | ||||
336 | generateConditionalExecution(Stmt, AccDom, Subject.c_str(), [&, this]() { | |||
337 | Value *NewPointer = | |||
338 | generateLocationAccessed(Stmt, Store, BBMap, LTS, NewAccesses); | |||
339 | Value *ValueOperand = getNewValue(Stmt, Store->getValueOperand(), BBMap, | |||
340 | LTS, getLoopForStmt(Stmt)); | |||
341 | ||||
342 | if (PollyDebugPrinting) | |||
343 | RuntimeDebugBuilder::createCPUPrinter(Builder, "Store to ", NewPointer, | |||
344 | ": ", ValueOperand, "\n"); | |||
345 | ||||
346 | Builder.CreateAlignedStore(ValueOperand, NewPointer, Store->getAlign()); | |||
347 | }); | |||
348 | } | |||
349 | ||||
350 | bool BlockGenerator::canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst) { | |||
351 | Loop *L = getLoopForStmt(Stmt); | |||
352 | return (Stmt.isBlockStmt() || !Stmt.getRegion()->contains(L)) && | |||
353 | canSynthesize(Inst, *Stmt.getParent(), &SE, L); | |||
354 | } | |||
355 | ||||
356 | void BlockGenerator::copyInstruction(ScopStmt &Stmt, Instruction *Inst, | |||
357 | ValueMapT &BBMap, LoopToScevMapT <S, | |||
358 | isl_id_to_ast_expr *NewAccesses) { | |||
359 | // Terminator instructions control the control flow. They are explicitly | |||
360 | // expressed in the clast and do not need to be copied. | |||
361 | if (Inst->isTerminator()) | |||
362 | return; | |||
363 | ||||
364 | // Synthesizable statements will be generated on-demand. | |||
365 | if (canSyntheziseInStmt(Stmt, Inst)) | |||
366 | return; | |||
367 | ||||
368 | if (auto *Load = dyn_cast<LoadInst>(Inst)) { | |||
369 | Value *NewLoad = generateArrayLoad(Stmt, Load, BBMap, LTS, NewAccesses); | |||
370 | // Compute NewLoad before its insertion in BBMap to make the insertion | |||
371 | // deterministic. | |||
372 | BBMap[Load] = NewLoad; | |||
373 | return; | |||
374 | } | |||
375 | ||||
376 | if (auto *Store = dyn_cast<StoreInst>(Inst)) { | |||
377 | // Identified as redundant by -polly-simplify. | |||
378 | if (!Stmt.getArrayAccessOrNULLFor(Store)) | |||
379 | return; | |||
380 | ||||
381 | generateArrayStore(Stmt, Store, BBMap, LTS, NewAccesses); | |||
382 | return; | |||
383 | } | |||
384 | ||||
385 | if (auto *PHI = dyn_cast<PHINode>(Inst)) { | |||
386 | copyPHIInstruction(Stmt, PHI, BBMap, LTS); | |||
387 | return; | |||
388 | } | |||
389 | ||||
390 | // Skip some special intrinsics for which we do not adjust the semantics to | |||
391 | // the new schedule. All others are handled like every other instruction. | |||
392 | if (isIgnoredIntrinsic(Inst)) | |||
393 | return; | |||
394 | ||||
395 | copyInstScalar(Stmt, Inst, BBMap, LTS); | |||
396 | } | |||
397 | ||||
398 | void BlockGenerator::removeDeadInstructions(BasicBlock *BB, ValueMapT &BBMap) { | |||
399 | auto NewBB = Builder.GetInsertBlock(); | |||
400 | for (auto I = NewBB->rbegin(); I != NewBB->rend(); I++) { | |||
401 | Instruction *NewInst = &*I; | |||
402 | ||||
403 | if (!isInstructionTriviallyDead(NewInst)) | |||
404 | continue; | |||
405 | ||||
406 | for (auto Pair : BBMap) | |||
407 | if (Pair.second == NewInst) { | |||
408 | BBMap.erase(Pair.first); | |||
409 | } | |||
410 | ||||
411 | NewInst->eraseFromParent(); | |||
412 | I = NewBB->rbegin(); | |||
413 | } | |||
414 | } | |||
415 | ||||
416 | void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT <S, | |||
417 | isl_id_to_ast_expr *NewAccesses) { | |||
418 | assert(Stmt.isBlockStmt() &&((Stmt.isBlockStmt() && "Only block statements can be copied by the block generator" ) ? static_cast<void> (0) : __assert_fail ("Stmt.isBlockStmt() && \"Only block statements can be copied by the block generator\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 419, __PRETTY_FUNCTION__)) | |||
419 | "Only block statements can be copied by the block generator")((Stmt.isBlockStmt() && "Only block statements can be copied by the block generator" ) ? static_cast<void> (0) : __assert_fail ("Stmt.isBlockStmt() && \"Only block statements can be copied by the block generator\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 419, __PRETTY_FUNCTION__)); | |||
420 | ||||
421 | ValueMapT BBMap; | |||
422 | ||||
423 | BasicBlock *BB = Stmt.getBasicBlock(); | |||
424 | copyBB(Stmt, BB, BBMap, LTS, NewAccesses); | |||
425 | removeDeadInstructions(BB, BBMap); | |||
426 | } | |||
427 | ||||
428 | BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) { | |||
429 | BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(), | |||
430 | &*Builder.GetInsertPoint(), &DT, &LI); | |||
431 | CopyBB->setName("polly.stmt." + BB->getName()); | |||
432 | return CopyBB; | |||
433 | } | |||
434 | ||||
435 | BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, | |||
436 | ValueMapT &BBMap, LoopToScevMapT <S, | |||
437 | isl_id_to_ast_expr *NewAccesses) { | |||
438 | BasicBlock *CopyBB = splitBB(BB); | |||
439 | Builder.SetInsertPoint(&CopyBB->front()); | |||
440 | generateScalarLoads(Stmt, LTS, BBMap, NewAccesses); | |||
441 | generateBeginStmtTrace(Stmt, LTS, BBMap); | |||
442 | ||||
443 | copyBB(Stmt, BB, CopyBB, BBMap, LTS, NewAccesses); | |||
444 | ||||
445 | // After a basic block was copied store all scalars that escape this block in | |||
446 | // their alloca. | |||
447 | generateScalarStores(Stmt, LTS, BBMap, NewAccesses); | |||
448 | return CopyBB; | |||
449 | } | |||
450 | ||||
451 | void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB, | |||
452 | ValueMapT &BBMap, LoopToScevMapT <S, | |||
453 | isl_id_to_ast_expr *NewAccesses) { | |||
454 | EntryBB = &CopyBB->getParent()->getEntryBlock(); | |||
455 | ||||
456 | // Block statements and the entry blocks of region statement are code | |||
457 | // generated from instruction lists. This allow us to optimize the | |||
458 | // instructions that belong to a certain scop statement. As the code | |||
459 | // structure of region statements might be arbitrary complex, optimizing the | |||
460 | // instruction list is not yet supported. | |||
461 | if (Stmt.isBlockStmt() || (Stmt.isRegionStmt() && Stmt.getEntryBlock() == BB)) | |||
462 | for (Instruction *Inst : Stmt.getInstructions()) | |||
463 | copyInstruction(Stmt, Inst, BBMap, LTS, NewAccesses); | |||
464 | else | |||
465 | for (Instruction &Inst : *BB) | |||
466 | copyInstruction(Stmt, &Inst, BBMap, LTS, NewAccesses); | |||
467 | } | |||
468 | ||||
469 | Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) { | |||
470 | assert(!Access.isLatestArrayKind() && "Trying to get alloca for array kind")((!Access.isLatestArrayKind() && "Trying to get alloca for array kind" ) ? static_cast<void> (0) : __assert_fail ("!Access.isLatestArrayKind() && \"Trying to get alloca for array kind\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 470, __PRETTY_FUNCTION__)); | |||
471 | ||||
472 | return getOrCreateAlloca(Access.getLatestScopArrayInfo()); | |||
473 | } | |||
474 | ||||
475 | Value *BlockGenerator::getOrCreateAlloca(const ScopArrayInfo *Array) { | |||
476 | assert(!Array->isArrayKind() && "Trying to get alloca for array kind")((!Array->isArrayKind() && "Trying to get alloca for array kind" ) ? static_cast<void> (0) : __assert_fail ("!Array->isArrayKind() && \"Trying to get alloca for array kind\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 476, __PRETTY_FUNCTION__)); | |||
477 | ||||
478 | auto &Addr = ScalarMap[Array]; | |||
479 | ||||
480 | if (Addr) { | |||
481 | // Allow allocas to be (temporarily) redirected once by adding a new | |||
482 | // old-alloca-addr to new-addr mapping to GlobalMap. This functionality | |||
483 | // is used for example by the OpenMP code generation where a first use | |||
484 | // of a scalar while still in the host code allocates a normal alloca with | |||
485 | // getOrCreateAlloca. When the values of this scalar are accessed during | |||
486 | // the generation of the parallel subfunction, these values are copied over | |||
487 | // to the parallel subfunction and each request for a scalar alloca slot | |||
488 | // must be forwarded to the temporary in-subfunction slot. This mapping is | |||
489 | // removed when the subfunction has been generated and again normal host | |||
490 | // code is generated. Due to the following reasons it is not possible to | |||
491 | // perform the GlobalMap lookup right after creating the alloca below, but | |||
492 | // instead we need to check GlobalMap at each call to getOrCreateAlloca: | |||
493 | // | |||
494 | // 1) GlobalMap may be changed multiple times (for each parallel loop), | |||
495 | // 2) The temporary mapping is commonly only known after the initial | |||
496 | // alloca has already been generated, and | |||
497 | // 3) The original alloca value must be restored after leaving the | |||
498 | // sub-function. | |||
499 | if (Value *NewAddr = GlobalMap.lookup(&*Addr)) | |||
500 | return NewAddr; | |||
501 | return Addr; | |||
502 | } | |||
503 | ||||
504 | Type *Ty = Array->getElementType(); | |||
505 | Value *ScalarBase = Array->getBasePtr(); | |||
506 | std::string NameExt; | |||
507 | if (Array->isPHIKind()) | |||
508 | NameExt = ".phiops"; | |||
509 | else | |||
510 | NameExt = ".s2a"; | |||
511 | ||||
512 | const DataLayout &DL = Builder.GetInsertBlock()->getModule()->getDataLayout(); | |||
513 | ||||
514 | Addr = new AllocaInst(Ty, DL.getAllocaAddrSpace(), | |||
515 | ScalarBase->getName() + NameExt); | |||
516 | EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock(); | |||
517 | Addr->insertBefore(&*EntryBB->getFirstInsertionPt()); | |||
518 | ||||
519 | return Addr; | |||
520 | } | |||
521 | ||||
522 | void BlockGenerator::handleOutsideUsers(const Scop &S, ScopArrayInfo *Array) { | |||
523 | Instruction *Inst = cast<Instruction>(Array->getBasePtr()); | |||
524 | ||||
525 | // If there are escape users we get the alloca for this instruction and put it | |||
526 | // in the EscapeMap for later finalization. Lastly, if the instruction was | |||
527 | // copied multiple times we already did this and can exit. | |||
528 | if (EscapeMap.count(Inst)) | |||
529 | return; | |||
530 | ||||
531 | EscapeUserVectorTy EscapeUsers; | |||
532 | for (User *U : Inst->users()) { | |||
533 | ||||
534 | // Non-instruction user will never escape. | |||
535 | Instruction *UI = dyn_cast<Instruction>(U); | |||
536 | if (!UI) | |||
537 | continue; | |||
538 | ||||
539 | if (S.contains(UI)) | |||
540 | continue; | |||
541 | ||||
542 | EscapeUsers.push_back(UI); | |||
543 | } | |||
544 | ||||
545 | // Exit if no escape uses were found. | |||
546 | if (EscapeUsers.empty()) | |||
547 | return; | |||
548 | ||||
549 | // Get or create an escape alloca for this instruction. | |||
550 | auto *ScalarAddr = getOrCreateAlloca(Array); | |||
551 | ||||
552 | // Remember that this instruction has escape uses and the escape alloca. | |||
553 | EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers)); | |||
554 | } | |||
555 | ||||
556 | void BlockGenerator::generateScalarLoads( | |||
557 | ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMap, | |||
558 | __isl_keep isl_id_to_ast_expr *NewAccesses) { | |||
559 | for (MemoryAccess *MA : Stmt) { | |||
560 | if (MA->isOriginalArrayKind() || MA->isWrite()) | |||
561 | continue; | |||
562 | ||||
563 | #ifndef NDEBUG | |||
564 | auto StmtDom = | |||
565 | Stmt.getDomain().intersect_params(Stmt.getParent()->getContext()); | |||
566 | auto AccDom = MA->getAccessRelation().domain(); | |||
567 | assert(!StmtDom.is_subset(AccDom).is_false() &&((!StmtDom.is_subset(AccDom).is_false() && "Scalar must be loaded in all statement instances" ) ? static_cast<void> (0) : __assert_fail ("!StmtDom.is_subset(AccDom).is_false() && \"Scalar must be loaded in all statement instances\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 568, __PRETTY_FUNCTION__)) | |||
568 | "Scalar must be loaded in all statement instances")((!StmtDom.is_subset(AccDom).is_false() && "Scalar must be loaded in all statement instances" ) ? static_cast<void> (0) : __assert_fail ("!StmtDom.is_subset(AccDom).is_false() && \"Scalar must be loaded in all statement instances\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 568, __PRETTY_FUNCTION__)); | |||
569 | #endif | |||
570 | ||||
571 | auto *Address = | |||
572 | getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, BBMap, NewAccesses); | |||
573 | assert((!isa<Instruction>(Address) ||(((!isa<Instruction>(Address) || DT.dominates(cast<Instruction >(Address)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Address) || DT.dominates(cast<Instruction>(Address)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 576, __PRETTY_FUNCTION__)) | |||
574 | DT.dominates(cast<Instruction>(Address)->getParent(),(((!isa<Instruction>(Address) || DT.dominates(cast<Instruction >(Address)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Address) || DT.dominates(cast<Instruction>(Address)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 576, __PRETTY_FUNCTION__)) | |||
575 | Builder.GetInsertBlock())) &&(((!isa<Instruction>(Address) || DT.dominates(cast<Instruction >(Address)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Address) || DT.dominates(cast<Instruction>(Address)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 576, __PRETTY_FUNCTION__)) | |||
576 | "Domination violation")(((!isa<Instruction>(Address) || DT.dominates(cast<Instruction >(Address)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Address) || DT.dominates(cast<Instruction>(Address)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 576, __PRETTY_FUNCTION__)); | |||
577 | BBMap[MA->getAccessValue()] = | |||
578 | Builder.CreateLoad(Address, Address->getName() + ".reload"); | |||
579 | } | |||
580 | } | |||
581 | ||||
582 | Value *BlockGenerator::buildContainsCondition(ScopStmt &Stmt, | |||
583 | const isl::set &Subdomain) { | |||
584 | isl::ast_build AstBuild = Stmt.getAstBuild(); | |||
585 | isl::set Domain = Stmt.getDomain(); | |||
586 | ||||
587 | isl::union_map USchedule = AstBuild.get_schedule(); | |||
588 | USchedule = USchedule.intersect_domain(Domain); | |||
589 | ||||
590 | assert(!USchedule.is_empty())((!USchedule.is_empty()) ? static_cast<void> (0) : __assert_fail ("!USchedule.is_empty()", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 590, __PRETTY_FUNCTION__)); | |||
591 | isl::map Schedule = isl::map::from_union_map(USchedule); | |||
592 | ||||
593 | isl::set ScheduledDomain = Schedule.range(); | |||
594 | isl::set ScheduledSet = Subdomain.apply(Schedule); | |||
595 | ||||
596 | isl::ast_build RestrictedBuild = AstBuild.restrict(ScheduledDomain); | |||
597 | ||||
598 | isl::ast_expr IsInSet = RestrictedBuild.expr_from(ScheduledSet); | |||
599 | Value *IsInSetExpr = ExprBuilder->create(IsInSet.copy()); | |||
600 | IsInSetExpr = Builder.CreateICmpNE( | |||
601 | IsInSetExpr, ConstantInt::get(IsInSetExpr->getType(), 0)); | |||
602 | ||||
603 | return IsInSetExpr; | |||
604 | } | |||
605 | ||||
606 | void BlockGenerator::generateConditionalExecution( | |||
607 | ScopStmt &Stmt, const isl::set &Subdomain, StringRef Subject, | |||
608 | const std::function<void()> &GenThenFunc) { | |||
609 | isl::set StmtDom = Stmt.getDomain(); | |||
610 | ||||
611 | // If the condition is a tautology, don't generate a condition around the | |||
612 | // code. | |||
613 | bool IsPartialWrite = | |||
614 | !StmtDom.intersect_params(Stmt.getParent()->getContext()) | |||
615 | .is_subset(Subdomain); | |||
616 | if (!IsPartialWrite) { | |||
617 | GenThenFunc(); | |||
618 | return; | |||
619 | } | |||
620 | ||||
621 | // Generate the condition. | |||
622 | Value *Cond = buildContainsCondition(Stmt, Subdomain); | |||
623 | ||||
624 | // Don't call GenThenFunc if it is never executed. An ast index expression | |||
625 | // might not be defined in this case. | |||
626 | if (auto *Const = dyn_cast<ConstantInt>(Cond)) | |||
627 | if (Const->isZero()) | |||
628 | return; | |||
629 | ||||
630 | BasicBlock *HeadBlock = Builder.GetInsertBlock(); | |||
631 | StringRef BlockName = HeadBlock->getName(); | |||
632 | ||||
633 | // Generate the conditional block. | |||
634 | SplitBlockAndInsertIfThen(Cond, &*Builder.GetInsertPoint(), false, nullptr, | |||
635 | &DT, &LI); | |||
636 | BranchInst *Branch = cast<BranchInst>(HeadBlock->getTerminator()); | |||
637 | BasicBlock *ThenBlock = Branch->getSuccessor(0); | |||
638 | BasicBlock *TailBlock = Branch->getSuccessor(1); | |||
639 | ||||
640 | // Assign descriptive names. | |||
641 | if (auto *CondInst = dyn_cast<Instruction>(Cond)) | |||
642 | CondInst->setName("polly." + Subject + ".cond"); | |||
643 | ThenBlock->setName(BlockName + "." + Subject + ".partial"); | |||
644 | TailBlock->setName(BlockName + ".cont"); | |||
645 | ||||
646 | // Put the client code into the conditional block and continue in the merge | |||
647 | // block afterwards. | |||
648 | Builder.SetInsertPoint(ThenBlock, ThenBlock->getFirstInsertionPt()); | |||
649 | GenThenFunc(); | |||
650 | Builder.SetInsertPoint(TailBlock, TailBlock->getFirstInsertionPt()); | |||
651 | } | |||
652 | ||||
653 | static std::string getInstName(Value *Val) { | |||
654 | std::string Result; | |||
655 | raw_string_ostream OS(Result); | |||
656 | Val->printAsOperand(OS, false); | |||
657 | return OS.str(); | |||
658 | } | |||
659 | ||||
660 | void BlockGenerator::generateBeginStmtTrace(ScopStmt &Stmt, LoopToScevMapT <S, | |||
661 | ValueMapT &BBMap) { | |||
662 | if (!TraceStmts) | |||
663 | return; | |||
664 | ||||
665 | Scop *S = Stmt.getParent(); | |||
666 | const char *BaseName = Stmt.getBaseName(); | |||
667 | ||||
668 | isl::ast_build AstBuild = Stmt.getAstBuild(); | |||
669 | isl::set Domain = Stmt.getDomain(); | |||
670 | ||||
671 | isl::union_map USchedule = AstBuild.get_schedule().intersect_domain(Domain); | |||
672 | isl::map Schedule = isl::map::from_union_map(USchedule); | |||
673 | assert(Schedule.is_empty().is_false() &&((Schedule.is_empty().is_false() && "The stmt must have a valid instance" ) ? static_cast<void> (0) : __assert_fail ("Schedule.is_empty().is_false() && \"The stmt must have a valid instance\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 674, __PRETTY_FUNCTION__)) | |||
674 | "The stmt must have a valid instance")((Schedule.is_empty().is_false() && "The stmt must have a valid instance" ) ? static_cast<void> (0) : __assert_fail ("Schedule.is_empty().is_false() && \"The stmt must have a valid instance\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 674, __PRETTY_FUNCTION__)); | |||
675 | ||||
676 | isl::multi_pw_aff ScheduleMultiPwAff = | |||
677 | isl::pw_multi_aff::from_map(Schedule.reverse()); | |||
678 | isl::ast_build RestrictedBuild = AstBuild.restrict(Schedule.range()); | |||
679 | ||||
680 | // Sequence of strings to print. | |||
681 | SmallVector<llvm::Value *, 8> Values; | |||
682 | ||||
683 | // Print the name of the statement. | |||
684 | // TODO: Indent by the depth of the statement instance in the schedule tree. | |||
685 | Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, BaseName)); | |||
686 | Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "(")); | |||
687 | ||||
688 | // Add the coordinate of the statement instance. | |||
689 | int DomDims = ScheduleMultiPwAff.dim(isl::dim::out); | |||
690 | for (int i = 0; i < DomDims; i += 1) { | |||
691 | if (i > 0) | |||
692 | Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ",")); | |||
693 | ||||
694 | isl::ast_expr IsInSet = | |||
695 | RestrictedBuild.expr_from(ScheduleMultiPwAff.get_pw_aff(i)); | |||
696 | Values.push_back(ExprBuilder->create(IsInSet.copy())); | |||
697 | } | |||
698 | ||||
699 | if (TraceScalars) { | |||
700 | Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ")")); | |||
701 | DenseSet<Instruction *> Encountered; | |||
702 | ||||
703 | // Add the value of each scalar (and the result of PHIs) used in the | |||
704 | // statement. | |||
705 | // TODO: Values used in region-statements. | |||
706 | for (Instruction *Inst : Stmt.insts()) { | |||
707 | if (!RuntimeDebugBuilder::isPrintable(Inst->getType())) | |||
708 | continue; | |||
709 | ||||
710 | if (isa<PHINode>(Inst)) { | |||
711 | Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, " ")); | |||
712 | Values.push_back(RuntimeDebugBuilder::getPrintableString( | |||
713 | Builder, getInstName(Inst))); | |||
714 | Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "=")); | |||
715 | Values.push_back(getNewValue(Stmt, Inst, BBMap, LTS, | |||
716 | LI.getLoopFor(Inst->getParent()))); | |||
717 | } else { | |||
718 | for (Value *Op : Inst->operand_values()) { | |||
719 | // Do not print values that cannot change during the execution of the | |||
720 | // SCoP. | |||
721 | auto *OpInst = dyn_cast<Instruction>(Op); | |||
722 | if (!OpInst) | |||
723 | continue; | |||
724 | if (!S->contains(OpInst)) | |||
725 | continue; | |||
726 | ||||
727 | // Print each scalar at most once, and exclude values defined in the | |||
728 | // statement itself. | |||
729 | if (Encountered.count(OpInst)) | |||
730 | continue; | |||
731 | ||||
732 | Values.push_back( | |||
733 | RuntimeDebugBuilder::getPrintableString(Builder, " ")); | |||
734 | Values.push_back(RuntimeDebugBuilder::getPrintableString( | |||
735 | Builder, getInstName(OpInst))); | |||
736 | Values.push_back( | |||
737 | RuntimeDebugBuilder::getPrintableString(Builder, "=")); | |||
738 | Values.push_back(getNewValue(Stmt, OpInst, BBMap, LTS, | |||
739 | LI.getLoopFor(Inst->getParent()))); | |||
740 | Encountered.insert(OpInst); | |||
741 | } | |||
742 | } | |||
743 | ||||
744 | Encountered.insert(Inst); | |||
745 | } | |||
746 | ||||
747 | Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "\n")); | |||
748 | } else { | |||
749 | Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ")\n")); | |||
750 | } | |||
751 | ||||
752 | RuntimeDebugBuilder::createCPUPrinter(Builder, ArrayRef<Value *>(Values)); | |||
753 | } | |||
754 | ||||
755 | void BlockGenerator::generateScalarStores( | |||
756 | ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMap, | |||
757 | __isl_keep isl_id_to_ast_expr *NewAccesses) { | |||
758 | Loop *L = LI.getLoopFor(Stmt.getBasicBlock()); | |||
759 | ||||
760 | assert(Stmt.isBlockStmt() &&((Stmt.isBlockStmt() && "Region statements need to use the generateScalarStores() function in " "the RegionGenerator") ? static_cast<void> (0) : __assert_fail ("Stmt.isBlockStmt() && \"Region statements need to use the generateScalarStores() function in \" \"the RegionGenerator\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 762, __PRETTY_FUNCTION__)) | |||
761 | "Region statements need to use the generateScalarStores() function in "((Stmt.isBlockStmt() && "Region statements need to use the generateScalarStores() function in " "the RegionGenerator") ? static_cast<void> (0) : __assert_fail ("Stmt.isBlockStmt() && \"Region statements need to use the generateScalarStores() function in \" \"the RegionGenerator\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 762, __PRETTY_FUNCTION__)) | |||
762 | "the RegionGenerator")((Stmt.isBlockStmt() && "Region statements need to use the generateScalarStores() function in " "the RegionGenerator") ? static_cast<void> (0) : __assert_fail ("Stmt.isBlockStmt() && \"Region statements need to use the generateScalarStores() function in \" \"the RegionGenerator\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 762, __PRETTY_FUNCTION__)); | |||
763 | ||||
764 | for (MemoryAccess *MA : Stmt) { | |||
765 | if (MA->isOriginalArrayKind() || MA->isRead()) | |||
766 | continue; | |||
767 | ||||
768 | isl::set AccDom = MA->getAccessRelation().domain(); | |||
769 | std::string Subject = MA->getId().get_name(); | |||
770 | ||||
771 | generateConditionalExecution( | |||
772 | Stmt, AccDom, Subject.c_str(), [&, this, MA]() { | |||
773 | Value *Val = MA->getAccessValue(); | |||
774 | if (MA->isAnyPHIKind()) { | |||
775 | assert(MA->getIncoming().size() >= 1 &&((MA->getIncoming().size() >= 1 && "Block statements have exactly one exiting block, or " "multiple but " "with same incoming block and value") ? static_cast <void> (0) : __assert_fail ("MA->getIncoming().size() >= 1 && \"Block statements have exactly one exiting block, or \" \"multiple but \" \"with same incoming block and value\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 778, __PRETTY_FUNCTION__)) | |||
776 | "Block statements have exactly one exiting block, or "((MA->getIncoming().size() >= 1 && "Block statements have exactly one exiting block, or " "multiple but " "with same incoming block and value") ? static_cast <void> (0) : __assert_fail ("MA->getIncoming().size() >= 1 && \"Block statements have exactly one exiting block, or \" \"multiple but \" \"with same incoming block and value\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 778, __PRETTY_FUNCTION__)) | |||
777 | "multiple but "((MA->getIncoming().size() >= 1 && "Block statements have exactly one exiting block, or " "multiple but " "with same incoming block and value") ? static_cast <void> (0) : __assert_fail ("MA->getIncoming().size() >= 1 && \"Block statements have exactly one exiting block, or \" \"multiple but \" \"with same incoming block and value\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 778, __PRETTY_FUNCTION__)) | |||
778 | "with same incoming block and value")((MA->getIncoming().size() >= 1 && "Block statements have exactly one exiting block, or " "multiple but " "with same incoming block and value") ? static_cast <void> (0) : __assert_fail ("MA->getIncoming().size() >= 1 && \"Block statements have exactly one exiting block, or \" \"multiple but \" \"with same incoming block and value\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 778, __PRETTY_FUNCTION__)); | |||
779 | assert(std::all_of(MA->getIncoming().begin(),((std::all_of(MA->getIncoming().begin(), MA->getIncoming ().end(), [&](std::pair<BasicBlock *, Value *> p) -> bool { return p.first == Stmt.getBasicBlock(); }) && "Incoming block must be statement's block") ? static_cast< void> (0) : __assert_fail ("std::all_of(MA->getIncoming().begin(), MA->getIncoming().end(), [&](std::pair<BasicBlock *, Value *> p) -> bool { return p.first == Stmt.getBasicBlock(); }) && \"Incoming block must be statement's block\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 784, __PRETTY_FUNCTION__)) | |||
780 | MA->getIncoming().end(),((std::all_of(MA->getIncoming().begin(), MA->getIncoming ().end(), [&](std::pair<BasicBlock *, Value *> p) -> bool { return p.first == Stmt.getBasicBlock(); }) && "Incoming block must be statement's block") ? static_cast< void> (0) : __assert_fail ("std::all_of(MA->getIncoming().begin(), MA->getIncoming().end(), [&](std::pair<BasicBlock *, Value *> p) -> bool { return p.first == Stmt.getBasicBlock(); }) && \"Incoming block must be statement's block\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 784, __PRETTY_FUNCTION__)) | |||
781 | [&](std::pair<BasicBlock *, Value *> p) -> bool {((std::all_of(MA->getIncoming().begin(), MA->getIncoming ().end(), [&](std::pair<BasicBlock *, Value *> p) -> bool { return p.first == Stmt.getBasicBlock(); }) && "Incoming block must be statement's block") ? static_cast< void> (0) : __assert_fail ("std::all_of(MA->getIncoming().begin(), MA->getIncoming().end(), [&](std::pair<BasicBlock *, Value *> p) -> bool { return p.first == Stmt.getBasicBlock(); }) && \"Incoming block must be statement's block\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 784, __PRETTY_FUNCTION__)) | |||
782 | return p.first == Stmt.getBasicBlock();((std::all_of(MA->getIncoming().begin(), MA->getIncoming ().end(), [&](std::pair<BasicBlock *, Value *> p) -> bool { return p.first == Stmt.getBasicBlock(); }) && "Incoming block must be statement's block") ? static_cast< void> (0) : __assert_fail ("std::all_of(MA->getIncoming().begin(), MA->getIncoming().end(), [&](std::pair<BasicBlock *, Value *> p) -> bool { return p.first == Stmt.getBasicBlock(); }) && \"Incoming block must be statement's block\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 784, __PRETTY_FUNCTION__)) | |||
783 | }) &&((std::all_of(MA->getIncoming().begin(), MA->getIncoming ().end(), [&](std::pair<BasicBlock *, Value *> p) -> bool { return p.first == Stmt.getBasicBlock(); }) && "Incoming block must be statement's block") ? static_cast< void> (0) : __assert_fail ("std::all_of(MA->getIncoming().begin(), MA->getIncoming().end(), [&](std::pair<BasicBlock *, Value *> p) -> bool { return p.first == Stmt.getBasicBlock(); }) && \"Incoming block must be statement's block\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 784, __PRETTY_FUNCTION__)) | |||
784 | "Incoming block must be statement's block")((std::all_of(MA->getIncoming().begin(), MA->getIncoming ().end(), [&](std::pair<BasicBlock *, Value *> p) -> bool { return p.first == Stmt.getBasicBlock(); }) && "Incoming block must be statement's block") ? static_cast< void> (0) : __assert_fail ("std::all_of(MA->getIncoming().begin(), MA->getIncoming().end(), [&](std::pair<BasicBlock *, Value *> p) -> bool { return p.first == Stmt.getBasicBlock(); }) && \"Incoming block must be statement's block\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 784, __PRETTY_FUNCTION__)); | |||
785 | Val = MA->getIncoming()[0].second; | |||
786 | } | |||
787 | auto Address = getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, | |||
788 | BBMap, NewAccesses); | |||
789 | ||||
790 | Val = getNewValue(Stmt, Val, BBMap, LTS, L); | |||
791 | assert((!isa<Instruction>(Val) ||(((!isa<Instruction>(Val) || DT.dominates(cast<Instruction >(Val)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Val) || DT.dominates(cast<Instruction>(Val)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 794, __PRETTY_FUNCTION__)) | |||
792 | DT.dominates(cast<Instruction>(Val)->getParent(),(((!isa<Instruction>(Val) || DT.dominates(cast<Instruction >(Val)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Val) || DT.dominates(cast<Instruction>(Val)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 794, __PRETTY_FUNCTION__)) | |||
793 | Builder.GetInsertBlock())) &&(((!isa<Instruction>(Val) || DT.dominates(cast<Instruction >(Val)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Val) || DT.dominates(cast<Instruction>(Val)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 794, __PRETTY_FUNCTION__)) | |||
794 | "Domination violation")(((!isa<Instruction>(Val) || DT.dominates(cast<Instruction >(Val)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Val) || DT.dominates(cast<Instruction>(Val)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 794, __PRETTY_FUNCTION__)); | |||
795 | assert((!isa<Instruction>(Address) ||(((!isa<Instruction>(Address) || DT.dominates(cast<Instruction >(Address)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Address) || DT.dominates(cast<Instruction>(Address)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 798, __PRETTY_FUNCTION__)) | |||
796 | DT.dominates(cast<Instruction>(Address)->getParent(),(((!isa<Instruction>(Address) || DT.dominates(cast<Instruction >(Address)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Address) || DT.dominates(cast<Instruction>(Address)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 798, __PRETTY_FUNCTION__)) | |||
797 | Builder.GetInsertBlock())) &&(((!isa<Instruction>(Address) || DT.dominates(cast<Instruction >(Address)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Address) || DT.dominates(cast<Instruction>(Address)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 798, __PRETTY_FUNCTION__)) | |||
798 | "Domination violation")(((!isa<Instruction>(Address) || DT.dominates(cast<Instruction >(Address)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Address) || DT.dominates(cast<Instruction>(Address)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 798, __PRETTY_FUNCTION__)); | |||
799 | ||||
800 | // The new Val might have a different type than the old Val due to | |||
801 | // ScalarEvolution looking through bitcasts. | |||
802 | if (Val->getType() != Address->getType()->getPointerElementType()) | |||
803 | Address = Builder.CreateBitOrPointerCast( | |||
804 | Address, Val->getType()->getPointerTo()); | |||
805 | ||||
806 | Builder.CreateStore(Val, Address); | |||
807 | }); | |||
808 | } | |||
809 | } | |||
810 | ||||
811 | void BlockGenerator::createScalarInitialization(Scop &S) { | |||
812 | BasicBlock *ExitBB = S.getExit(); | |||
813 | BasicBlock *PreEntryBB = S.getEnteringBlock(); | |||
814 | ||||
815 | Builder.SetInsertPoint(&*StartBlock->begin()); | |||
816 | ||||
817 | for (auto &Array : S.arrays()) { | |||
818 | if (Array->getNumberOfDimensions() != 0) | |||
819 | continue; | |||
820 | if (Array->isPHIKind()) { | |||
821 | // For PHI nodes, the only values we need to store are the ones that | |||
822 | // reach the PHI node from outside the region. In general there should | |||
823 | // only be one such incoming edge and this edge should enter through | |||
824 | // 'PreEntryBB'. | |||
825 | auto PHI = cast<PHINode>(Array->getBasePtr()); | |||
826 | ||||
827 | for (auto BI = PHI->block_begin(), BE = PHI->block_end(); BI != BE; BI++) | |||
828 | if (!S.contains(*BI) && *BI != PreEntryBB) | |||
829 | llvm_unreachable("Incoming edges from outside the scop should always "::llvm::llvm_unreachable_internal("Incoming edges from outside the scop should always " "come from PreEntryBB", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 830) | |||
830 | "come from PreEntryBB")::llvm::llvm_unreachable_internal("Incoming edges from outside the scop should always " "come from PreEntryBB", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 830); | |||
831 | ||||
832 | int Idx = PHI->getBasicBlockIndex(PreEntryBB); | |||
833 | if (Idx < 0) | |||
834 | continue; | |||
835 | ||||
836 | Value *ScalarValue = PHI->getIncomingValue(Idx); | |||
837 | ||||
838 | Builder.CreateStore(ScalarValue, getOrCreateAlloca(Array)); | |||
839 | continue; | |||
840 | } | |||
841 | ||||
842 | auto *Inst = dyn_cast<Instruction>(Array->getBasePtr()); | |||
843 | ||||
844 | if (Inst && S.contains(Inst)) | |||
845 | continue; | |||
846 | ||||
847 | // PHI nodes that are not marked as such in their SAI object are either exit | |||
848 | // PHI nodes we model as common scalars but without initialization, or | |||
849 | // incoming phi nodes that need to be initialized. Check if the first is the | |||
850 | // case for Inst and do not create and initialize memory if so. | |||
851 | if (auto *PHI = dyn_cast_or_null<PHINode>(Inst)) | |||
852 | if (!S.hasSingleExitEdge() && PHI->getBasicBlockIndex(ExitBB) >= 0) | |||
853 | continue; | |||
854 | ||||
855 | Builder.CreateStore(Array->getBasePtr(), getOrCreateAlloca(Array)); | |||
856 | } | |||
857 | } | |||
858 | ||||
859 | void BlockGenerator::createScalarFinalization(Scop &S) { | |||
860 | // The exit block of the __unoptimized__ region. | |||
861 | BasicBlock *ExitBB = S.getExitingBlock(); | |||
862 | // The merge block __just after__ the region and the optimized region. | |||
863 | BasicBlock *MergeBB = S.getExit(); | |||
864 | ||||
865 | // The exit block of the __optimized__ region. | |||
866 | BasicBlock *OptExitBB = *(pred_begin(MergeBB)); | |||
867 | if (OptExitBB == ExitBB) | |||
868 | OptExitBB = *(++pred_begin(MergeBB)); | |||
869 | ||||
870 | Builder.SetInsertPoint(OptExitBB->getTerminator()); | |||
871 | for (const auto &EscapeMapping : EscapeMap) { | |||
872 | // Extract the escaping instruction and the escaping users as well as the | |||
873 | // alloca the instruction was demoted to. | |||
874 | Instruction *EscapeInst = EscapeMapping.first; | |||
875 | const auto &EscapeMappingValue = EscapeMapping.second; | |||
876 | const EscapeUserVectorTy &EscapeUsers = EscapeMappingValue.second; | |||
877 | Value *ScalarAddr = EscapeMappingValue.first; | |||
878 | ||||
879 | // Reload the demoted instruction in the optimized version of the SCoP. | |||
880 | Value *EscapeInstReload = | |||
881 | Builder.CreateLoad(ScalarAddr, EscapeInst->getName() + ".final_reload"); | |||
882 | EscapeInstReload = | |||
883 | Builder.CreateBitOrPointerCast(EscapeInstReload, EscapeInst->getType()); | |||
884 | ||||
885 | // Create the merge PHI that merges the optimized and unoptimized version. | |||
886 | PHINode *MergePHI = PHINode::Create(EscapeInst->getType(), 2, | |||
887 | EscapeInst->getName() + ".merge"); | |||
888 | MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt()); | |||
889 | ||||
890 | // Add the respective values to the merge PHI. | |||
891 | MergePHI->addIncoming(EscapeInstReload, OptExitBB); | |||
892 | MergePHI->addIncoming(EscapeInst, ExitBB); | |||
893 | ||||
894 | // The information of scalar evolution about the escaping instruction needs | |||
895 | // to be revoked so the new merged instruction will be used. | |||
896 | if (SE.isSCEVable(EscapeInst->getType())) | |||
897 | SE.forgetValue(EscapeInst); | |||
898 | ||||
899 | // Replace all uses of the demoted instruction with the merge PHI. | |||
900 | for (Instruction *EUser : EscapeUsers) | |||
901 | EUser->replaceUsesOfWith(EscapeInst, MergePHI); | |||
902 | } | |||
903 | } | |||
904 | ||||
905 | void BlockGenerator::findOutsideUsers(Scop &S) { | |||
906 | for (auto &Array : S.arrays()) { | |||
907 | ||||
908 | if (Array->getNumberOfDimensions() != 0) | |||
909 | continue; | |||
910 | ||||
911 | if (Array->isPHIKind()) | |||
912 | continue; | |||
913 | ||||
914 | auto *Inst = dyn_cast<Instruction>(Array->getBasePtr()); | |||
915 | ||||
916 | if (!Inst) | |||
917 | continue; | |||
918 | ||||
919 | // Scop invariant hoisting moves some of the base pointers out of the scop. | |||
920 | // We can ignore these, as the invariant load hoisting already registers the | |||
921 | // relevant outside users. | |||
922 | if (!S.contains(Inst)) | |||
923 | continue; | |||
924 | ||||
925 | handleOutsideUsers(S, Array); | |||
926 | } | |||
927 | } | |||
928 | ||||
929 | void BlockGenerator::createExitPHINodeMerges(Scop &S) { | |||
930 | if (S.hasSingleExitEdge()) | |||
931 | return; | |||
932 | ||||
933 | auto *ExitBB = S.getExitingBlock(); | |||
934 | auto *MergeBB = S.getExit(); | |||
935 | auto *AfterMergeBB = MergeBB->getSingleSuccessor(); | |||
936 | BasicBlock *OptExitBB = *(pred_begin(MergeBB)); | |||
937 | if (OptExitBB == ExitBB) | |||
938 | OptExitBB = *(++pred_begin(MergeBB)); | |||
939 | ||||
940 | Builder.SetInsertPoint(OptExitBB->getTerminator()); | |||
941 | ||||
942 | for (auto &SAI : S.arrays()) { | |||
943 | auto *Val = SAI->getBasePtr(); | |||
944 | ||||
945 | // Only Value-like scalars need a merge PHI. Exit block PHIs receive either | |||
946 | // the original PHI's value or the reloaded incoming values from the | |||
947 | // generated code. An llvm::Value is merged between the original code's | |||
948 | // value or the generated one. | |||
949 | if (!SAI->isExitPHIKind()) | |||
950 | continue; | |||
951 | ||||
952 | PHINode *PHI = dyn_cast<PHINode>(Val); | |||
953 | if (!PHI) | |||
954 | continue; | |||
955 | ||||
956 | if (PHI->getParent() != AfterMergeBB) | |||
957 | continue; | |||
958 | ||||
959 | std::string Name = PHI->getName().str(); | |||
960 | Value *ScalarAddr = getOrCreateAlloca(SAI); | |||
961 | Value *Reload = Builder.CreateLoad(ScalarAddr, Name + ".ph.final_reload"); | |||
962 | Reload = Builder.CreateBitOrPointerCast(Reload, PHI->getType()); | |||
963 | Value *OriginalValue = PHI->getIncomingValueForBlock(MergeBB); | |||
964 | assert((!isa<Instruction>(OriginalValue) ||(((!isa<Instruction>(OriginalValue) || cast<Instruction >(OriginalValue)->getParent() != MergeBB) && "Original value must no be one we just generated." ) ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(OriginalValue) || cast<Instruction>(OriginalValue)->getParent() != MergeBB) && \"Original value must no be one we just generated.\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 966, __PRETTY_FUNCTION__)) | |||
965 | cast<Instruction>(OriginalValue)->getParent() != MergeBB) &&(((!isa<Instruction>(OriginalValue) || cast<Instruction >(OriginalValue)->getParent() != MergeBB) && "Original value must no be one we just generated." ) ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(OriginalValue) || cast<Instruction>(OriginalValue)->getParent() != MergeBB) && \"Original value must no be one we just generated.\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 966, __PRETTY_FUNCTION__)) | |||
966 | "Original value must no be one we just generated.")(((!isa<Instruction>(OriginalValue) || cast<Instruction >(OriginalValue)->getParent() != MergeBB) && "Original value must no be one we just generated." ) ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(OriginalValue) || cast<Instruction>(OriginalValue)->getParent() != MergeBB) && \"Original value must no be one we just generated.\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 966, __PRETTY_FUNCTION__)); | |||
967 | auto *MergePHI = PHINode::Create(PHI->getType(), 2, Name + ".ph.merge"); | |||
968 | MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt()); | |||
969 | MergePHI->addIncoming(Reload, OptExitBB); | |||
970 | MergePHI->addIncoming(OriginalValue, ExitBB); | |||
971 | int Idx = PHI->getBasicBlockIndex(MergeBB); | |||
972 | PHI->setIncomingValue(Idx, MergePHI); | |||
973 | } | |||
974 | } | |||
975 | ||||
976 | void BlockGenerator::invalidateScalarEvolution(Scop &S) { | |||
977 | for (auto &Stmt : S) | |||
978 | if (Stmt.isCopyStmt()) | |||
979 | continue; | |||
980 | else if (Stmt.isBlockStmt()) | |||
981 | for (auto &Inst : *Stmt.getBasicBlock()) | |||
982 | SE.forgetValue(&Inst); | |||
983 | else if (Stmt.isRegionStmt()) | |||
984 | for (auto *BB : Stmt.getRegion()->blocks()) | |||
985 | for (auto &Inst : *BB) | |||
986 | SE.forgetValue(&Inst); | |||
987 | else | |||
988 | llvm_unreachable("Unexpected statement type found")::llvm::llvm_unreachable_internal("Unexpected statement type found" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 988); | |||
989 | ||||
990 | // Invalidate SCEV of loops surrounding the EscapeUsers. | |||
991 | for (const auto &EscapeMapping : EscapeMap) { | |||
992 | const EscapeUserVectorTy &EscapeUsers = EscapeMapping.second.second; | |||
993 | for (Instruction *EUser : EscapeUsers) { | |||
994 | if (Loop *L = LI.getLoopFor(EUser->getParent())) | |||
995 | while (L) { | |||
996 | SE.forgetLoop(L); | |||
997 | L = L->getParentLoop(); | |||
998 | } | |||
999 | } | |||
1000 | } | |||
1001 | } | |||
1002 | ||||
1003 | void BlockGenerator::finalizeSCoP(Scop &S) { | |||
1004 | findOutsideUsers(S); | |||
1005 | createScalarInitialization(S); | |||
1006 | createExitPHINodeMerges(S); | |||
1007 | createScalarFinalization(S); | |||
1008 | invalidateScalarEvolution(S); | |||
1009 | } | |||
1010 | ||||
1011 | VectorBlockGenerator::VectorBlockGenerator(BlockGenerator &BlockGen, | |||
1012 | std::vector<LoopToScevMapT> &VLTS, | |||
1013 | isl_map *Schedule) | |||
1014 | : BlockGenerator(BlockGen), VLTS(VLTS), Schedule(Schedule) { | |||
1015 | assert(Schedule && "No statement domain provided")((Schedule && "No statement domain provided") ? static_cast <void> (0) : __assert_fail ("Schedule && \"No statement domain provided\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1015, __PRETTY_FUNCTION__)); | |||
1016 | } | |||
1017 | ||||
1018 | Value *VectorBlockGenerator::getVectorValue(ScopStmt &Stmt, Value *Old, | |||
1019 | ValueMapT &VectorMap, | |||
1020 | VectorValueMapT &ScalarMaps, | |||
1021 | Loop *L) { | |||
1022 | if (Value *NewValue = VectorMap.lookup(Old)) | |||
1023 | return NewValue; | |||
1024 | ||||
1025 | int Width = getVectorWidth(); | |||
1026 | ||||
1027 | Value *Vector = UndefValue::get(VectorType::get(Old->getType(), Width)); | |||
1028 | ||||
1029 | for (int Lane = 0; Lane < Width; Lane++) | |||
1030 | Vector = Builder.CreateInsertElement( | |||
1031 | Vector, getNewValue(Stmt, Old, ScalarMaps[Lane], VLTS[Lane], L), | |||
1032 | Builder.getInt32(Lane)); | |||
1033 | ||||
1034 | VectorMap[Old] = Vector; | |||
1035 | ||||
1036 | return Vector; | |||
1037 | } | |||
1038 | ||||
1039 | Type *VectorBlockGenerator::getVectorPtrTy(const Value *Val, int Width) { | |||
1040 | PointerType *PointerTy = dyn_cast<PointerType>(Val->getType()); | |||
1041 | assert(PointerTy && "PointerType expected")((PointerTy && "PointerType expected") ? static_cast< void> (0) : __assert_fail ("PointerTy && \"PointerType expected\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1041, __PRETTY_FUNCTION__)); | |||
1042 | ||||
1043 | Type *ScalarType = PointerTy->getElementType(); | |||
1044 | VectorType *VectorType = VectorType::get(ScalarType, Width); | |||
1045 | ||||
1046 | return PointerType::getUnqual(VectorType); | |||
1047 | } | |||
1048 | ||||
1049 | Value *VectorBlockGenerator::generateStrideOneLoad( | |||
1050 | ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps, | |||
1051 | __isl_keep isl_id_to_ast_expr *NewAccesses, bool NegativeStride = false) { | |||
1052 | unsigned VectorWidth = getVectorWidth(); | |||
1053 | auto *Pointer = Load->getPointerOperand(); | |||
1054 | Type *VectorPtrType = getVectorPtrTy(Pointer, VectorWidth); | |||
1055 | unsigned Offset = NegativeStride ? VectorWidth - 1 : 0; | |||
1056 | ||||
1057 | Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[Offset], | |||
1058 | VLTS[Offset], NewAccesses); | |||
1059 | Value *VectorPtr = | |||
1060 | Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr"); | |||
1061 | LoadInst *VecLoad = | |||
1062 | Builder.CreateLoad(VectorPtr, Load->getName() + "_p_vec_full"); | |||
1063 | if (!Aligned) | |||
1064 | VecLoad->setAlignment(Align(8)); | |||
1065 | ||||
1066 | if (NegativeStride) { | |||
1067 | SmallVector<Constant *, 16> Indices; | |||
1068 | for (int i = VectorWidth - 1; i >= 0; i--) | |||
1069 | Indices.push_back(ConstantInt::get(Builder.getInt32Ty(), i)); | |||
1070 | Constant *SV = llvm::ConstantVector::get(Indices); | |||
1071 | Value *RevVecLoad = Builder.CreateShuffleVector( | |||
1072 | VecLoad, VecLoad, SV, Load->getName() + "_reverse"); | |||
1073 | return RevVecLoad; | |||
1074 | } | |||
1075 | ||||
1076 | return VecLoad; | |||
1077 | } | |||
1078 | ||||
1079 | Value *VectorBlockGenerator::generateStrideZeroLoad( | |||
1080 | ScopStmt &Stmt, LoadInst *Load, ValueMapT &BBMap, | |||
1081 | __isl_keep isl_id_to_ast_expr *NewAccesses) { | |||
1082 | auto *Pointer = Load->getPointerOperand(); | |||
1083 | Type *VectorPtrType = getVectorPtrTy(Pointer, 1); | |||
1084 | Value *NewPointer = | |||
1085 | generateLocationAccessed(Stmt, Load, BBMap, VLTS[0], NewAccesses); | |||
1086 | Value *VectorPtr = Builder.CreateBitCast(NewPointer, VectorPtrType, | |||
1087 | Load->getName() + "_p_vec_p"); | |||
1088 | LoadInst *ScalarLoad = | |||
1089 | Builder.CreateLoad(VectorPtr, Load->getName() + "_p_splat_one"); | |||
1090 | ||||
1091 | if (!Aligned) | |||
1092 | ScalarLoad->setAlignment(Align(8)); | |||
1093 | ||||
1094 | Constant *SplatVector = Constant::getNullValue( | |||
1095 | VectorType::get(Builder.getInt32Ty(), getVectorWidth())); | |||
1096 | ||||
1097 | Value *VectorLoad = Builder.CreateShuffleVector( | |||
1098 | ScalarLoad, ScalarLoad, SplatVector, Load->getName() + "_p_splat"); | |||
1099 | return VectorLoad; | |||
1100 | } | |||
1101 | ||||
1102 | Value *VectorBlockGenerator::generateUnknownStrideLoad( | |||
1103 | ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps, | |||
1104 | __isl_keep isl_id_to_ast_expr *NewAccesses) { | |||
1105 | int VectorWidth = getVectorWidth(); | |||
1106 | auto *Pointer = Load->getPointerOperand(); | |||
1107 | VectorType *VectorType = VectorType::get( | |||
1108 | dyn_cast<PointerType>(Pointer->getType())->getElementType(), VectorWidth); | |||
1109 | ||||
1110 | Value *Vector = UndefValue::get(VectorType); | |||
1111 | ||||
1112 | for (int i = 0; i < VectorWidth; i++) { | |||
1113 | Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[i], | |||
1114 | VLTS[i], NewAccesses); | |||
1115 | Value *ScalarLoad = | |||
1116 | Builder.CreateLoad(NewPointer, Load->getName() + "_p_scalar_"); | |||
1117 | Vector = Builder.CreateInsertElement( | |||
1118 | Vector, ScalarLoad, Builder.getInt32(i), Load->getName() + "_p_vec_"); | |||
1119 | } | |||
1120 | ||||
1121 | return Vector; | |||
1122 | } | |||
1123 | ||||
1124 | void VectorBlockGenerator::generateLoad( | |||
1125 | ScopStmt &Stmt, LoadInst *Load, ValueMapT &VectorMap, | |||
1126 | VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) { | |||
1127 | if (Value *PreloadLoad = GlobalMap.lookup(Load)) { | |||
1128 | VectorMap[Load] = Builder.CreateVectorSplat(getVectorWidth(), PreloadLoad, | |||
1129 | Load->getName() + "_p"); | |||
1130 | return; | |||
1131 | } | |||
1132 | ||||
1133 | if (!VectorType::isValidElementType(Load->getType())) { | |||
1134 | for (int i = 0; i < getVectorWidth(); i++) | |||
1135 | ScalarMaps[i][Load] = | |||
1136 | generateArrayLoad(Stmt, Load, ScalarMaps[i], VLTS[i], NewAccesses); | |||
1137 | return; | |||
1138 | } | |||
1139 | ||||
1140 | const MemoryAccess &Access = Stmt.getArrayAccessFor(Load); | |||
1141 | ||||
1142 | // Make sure we have scalar values available to access the pointer to | |||
1143 | // the data location. | |||
1144 | extractScalarValues(Load, VectorMap, ScalarMaps); | |||
1145 | ||||
1146 | Value *NewLoad; | |||
1147 | if (Access.isStrideZero(isl::manage_copy(Schedule))) | |||
1148 | NewLoad = generateStrideZeroLoad(Stmt, Load, ScalarMaps[0], NewAccesses); | |||
1149 | else if (Access.isStrideOne(isl::manage_copy(Schedule))) | |||
1150 | NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses); | |||
1151 | else if (Access.isStrideX(isl::manage_copy(Schedule), -1)) | |||
1152 | NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses, true); | |||
1153 | else | |||
1154 | NewLoad = generateUnknownStrideLoad(Stmt, Load, ScalarMaps, NewAccesses); | |||
1155 | ||||
1156 | VectorMap[Load] = NewLoad; | |||
1157 | } | |||
1158 | ||||
1159 | void VectorBlockGenerator::copyUnaryInst(ScopStmt &Stmt, UnaryInstruction *Inst, | |||
1160 | ValueMapT &VectorMap, | |||
1161 | VectorValueMapT &ScalarMaps) { | |||
1162 | int VectorWidth = getVectorWidth(); | |||
1163 | Value *NewOperand = getVectorValue(Stmt, Inst->getOperand(0), VectorMap, | |||
1164 | ScalarMaps, getLoopForStmt(Stmt)); | |||
1165 | ||||
1166 | assert(isa<CastInst>(Inst) && "Can not generate vector code for instruction")((isa<CastInst>(Inst) && "Can not generate vector code for instruction" ) ? static_cast<void> (0) : __assert_fail ("isa<CastInst>(Inst) && \"Can not generate vector code for instruction\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1166, __PRETTY_FUNCTION__)); | |||
1167 | ||||
1168 | const CastInst *Cast = dyn_cast<CastInst>(Inst); | |||
1169 | VectorType *DestType = VectorType::get(Inst->getType(), VectorWidth); | |||
1170 | VectorMap[Inst] = Builder.CreateCast(Cast->getOpcode(), NewOperand, DestType); | |||
| ||||
1171 | } | |||
1172 | ||||
1173 | void VectorBlockGenerator::copyBinaryInst(ScopStmt &Stmt, BinaryOperator *Inst, | |||
1174 | ValueMapT &VectorMap, | |||
1175 | VectorValueMapT &ScalarMaps) { | |||
1176 | Loop *L = getLoopForStmt(Stmt); | |||
1177 | Value *OpZero = Inst->getOperand(0); | |||
1178 | Value *OpOne = Inst->getOperand(1); | |||
1179 | ||||
1180 | Value *NewOpZero, *NewOpOne; | |||
1181 | NewOpZero = getVectorValue(Stmt, OpZero, VectorMap, ScalarMaps, L); | |||
1182 | NewOpOne = getVectorValue(Stmt, OpOne, VectorMap, ScalarMaps, L); | |||
1183 | ||||
1184 | Value *NewInst = Builder.CreateBinOp(Inst->getOpcode(), NewOpZero, NewOpOne, | |||
1185 | Inst->getName() + "p_vec"); | |||
1186 | VectorMap[Inst] = NewInst; | |||
1187 | } | |||
1188 | ||||
1189 | void VectorBlockGenerator::copyStore( | |||
1190 | ScopStmt &Stmt, StoreInst *Store, ValueMapT &VectorMap, | |||
1191 | VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) { | |||
1192 | const MemoryAccess &Access = Stmt.getArrayAccessFor(Store); | |||
1193 | ||||
1194 | auto *Pointer = Store->getPointerOperand(); | |||
1195 | Value *Vector = getVectorValue(Stmt, Store->getValueOperand(), VectorMap, | |||
1196 | ScalarMaps, getLoopForStmt(Stmt)); | |||
1197 | ||||
1198 | // Make sure we have scalar values available to access the pointer to | |||
1199 | // the data location. | |||
1200 | extractScalarValues(Store, VectorMap, ScalarMaps); | |||
1201 | ||||
1202 | if (Access.isStrideOne(isl::manage_copy(Schedule))) { | |||
1203 | Type *VectorPtrType = getVectorPtrTy(Pointer, getVectorWidth()); | |||
1204 | Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[0], | |||
1205 | VLTS[0], NewAccesses); | |||
1206 | ||||
1207 | Value *VectorPtr = | |||
1208 | Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr"); | |||
1209 | StoreInst *Store = Builder.CreateStore(Vector, VectorPtr); | |||
1210 | ||||
1211 | if (!Aligned) | |||
1212 | Store->setAlignment(Align(8)); | |||
1213 | } else { | |||
1214 | for (unsigned i = 0; i < ScalarMaps.size(); i++) { | |||
1215 | Value *Scalar = Builder.CreateExtractElement(Vector, Builder.getInt32(i)); | |||
1216 | Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[i], | |||
1217 | VLTS[i], NewAccesses); | |||
1218 | Builder.CreateStore(Scalar, NewPointer); | |||
1219 | } | |||
1220 | } | |||
1221 | } | |||
1222 | ||||
1223 | bool VectorBlockGenerator::hasVectorOperands(const Instruction *Inst, | |||
1224 | ValueMapT &VectorMap) { | |||
1225 | for (Value *Operand : Inst->operands()) | |||
1226 | if (VectorMap.count(Operand)) | |||
1227 | return true; | |||
1228 | return false; | |||
1229 | } | |||
1230 | ||||
1231 | bool VectorBlockGenerator::extractScalarValues(const Instruction *Inst, | |||
1232 | ValueMapT &VectorMap, | |||
1233 | VectorValueMapT &ScalarMaps) { | |||
1234 | bool HasVectorOperand = false; | |||
1235 | int VectorWidth = getVectorWidth(); | |||
1236 | ||||
1237 | for (Value *Operand : Inst->operands()) { | |||
1238 | ValueMapT::iterator VecOp = VectorMap.find(Operand); | |||
1239 | ||||
1240 | if (VecOp == VectorMap.end()) | |||
1241 | continue; | |||
1242 | ||||
1243 | HasVectorOperand = true; | |||
1244 | Value *NewVector = VecOp->second; | |||
1245 | ||||
1246 | for (int i = 0; i < VectorWidth; ++i) { | |||
1247 | ValueMapT &SM = ScalarMaps[i]; | |||
1248 | ||||
1249 | // If there is one scalar extracted, all scalar elements should have | |||
1250 | // already been extracted by the code here. So no need to check for the | |||
1251 | // existence of all of them. | |||
1252 | if (SM.count(Operand)) | |||
1253 | break; | |||
1254 | ||||
1255 | SM[Operand] = | |||
1256 | Builder.CreateExtractElement(NewVector, Builder.getInt32(i)); | |||
1257 | } | |||
1258 | } | |||
1259 | ||||
1260 | return HasVectorOperand; | |||
1261 | } | |||
1262 | ||||
1263 | void VectorBlockGenerator::copyInstScalarized( | |||
1264 | ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap, | |||
1265 | VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) { | |||
1266 | bool HasVectorOperand; | |||
1267 | int VectorWidth = getVectorWidth(); | |||
1268 | ||||
1269 | HasVectorOperand = extractScalarValues(Inst, VectorMap, ScalarMaps); | |||
1270 | ||||
1271 | for (int VectorLane = 0; VectorLane < getVectorWidth(); VectorLane++) | |||
1272 | BlockGenerator::copyInstruction(Stmt, Inst, ScalarMaps[VectorLane], | |||
1273 | VLTS[VectorLane], NewAccesses); | |||
1274 | ||||
1275 | if (!VectorType::isValidElementType(Inst->getType()) || !HasVectorOperand) | |||
1276 | return; | |||
1277 | ||||
1278 | // Make the result available as vector value. | |||
1279 | VectorType *VectorType = VectorType::get(Inst->getType(), VectorWidth); | |||
1280 | Value *Vector = UndefValue::get(VectorType); | |||
1281 | ||||
1282 | for (int i = 0; i < VectorWidth; i++) | |||
1283 | Vector = Builder.CreateInsertElement(Vector, ScalarMaps[i][Inst], | |||
1284 | Builder.getInt32(i)); | |||
1285 | ||||
1286 | VectorMap[Inst] = Vector; | |||
1287 | } | |||
1288 | ||||
1289 | int VectorBlockGenerator::getVectorWidth() { return VLTS.size(); } | |||
1290 | ||||
1291 | void VectorBlockGenerator::copyInstruction( | |||
1292 | ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap, | |||
1293 | VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) { | |||
1294 | // Terminator instructions control the control flow. They are explicitly | |||
1295 | // expressed in the clast and do not need to be copied. | |||
1296 | if (Inst->isTerminator()) | |||
1297 | return; | |||
1298 | ||||
1299 | if (canSyntheziseInStmt(Stmt, Inst)) | |||
1300 | return; | |||
1301 | ||||
1302 | if (auto *Load
| |||
1303 | generateLoad(Stmt, Load, VectorMap, ScalarMaps, NewAccesses); | |||
1304 | return; | |||
1305 | } | |||
1306 | ||||
1307 | if (hasVectorOperands(Inst, VectorMap)) { | |||
1308 | if (auto *Store
| |||
1309 | // Identified as redundant by -polly-simplify. | |||
1310 | if (!Stmt.getArrayAccessOrNULLFor(Store)) | |||
1311 | return; | |||
1312 | ||||
1313 | copyStore(Stmt, Store, VectorMap, ScalarMaps, NewAccesses); | |||
1314 | return; | |||
1315 | } | |||
1316 | ||||
1317 | if (auto *Unary
| |||
1318 | copyUnaryInst(Stmt, Unary, VectorMap, ScalarMaps); | |||
1319 | return; | |||
1320 | } | |||
1321 | ||||
1322 | if (auto *Binary = dyn_cast<BinaryOperator>(Inst)) { | |||
1323 | copyBinaryInst(Stmt, Binary, VectorMap, ScalarMaps); | |||
1324 | return; | |||
1325 | } | |||
1326 | ||||
1327 | // Fallthrough: We generate scalar instructions, if we don't know how to | |||
1328 | // generate vector code. | |||
1329 | } | |||
1330 | ||||
1331 | copyInstScalarized(Stmt, Inst, VectorMap, ScalarMaps, NewAccesses); | |||
1332 | } | |||
1333 | ||||
1334 | void VectorBlockGenerator::generateScalarVectorLoads( | |||
1335 | ScopStmt &Stmt, ValueMapT &VectorBlockMap) { | |||
1336 | for (MemoryAccess *MA : Stmt) { | |||
1337 | if (MA->isArrayKind() || MA->isWrite()) | |||
1338 | continue; | |||
1339 | ||||
1340 | auto *Address = getOrCreateAlloca(*MA); | |||
1341 | Type *VectorPtrType = getVectorPtrTy(Address, 1); | |||
1342 | Value *VectorPtr = Builder.CreateBitCast(Address, VectorPtrType, | |||
1343 | Address->getName() + "_p_vec_p"); | |||
1344 | auto *Val = Builder.CreateLoad(VectorPtr, Address->getName() + ".reload"); | |||
1345 | Constant *SplatVector = Constant::getNullValue( | |||
1346 | VectorType::get(Builder.getInt32Ty(), getVectorWidth())); | |||
1347 | ||||
1348 | Value *VectorVal = Builder.CreateShuffleVector( | |||
1349 | Val, Val, SplatVector, Address->getName() + "_p_splat"); | |||
1350 | VectorBlockMap[MA->getAccessValue()] = VectorVal; | |||
1351 | } | |||
1352 | } | |||
1353 | ||||
1354 | void VectorBlockGenerator::verifyNoScalarStores(ScopStmt &Stmt) { | |||
1355 | for (MemoryAccess *MA : Stmt) { | |||
1356 | if (MA->isArrayKind() || MA->isRead()) | |||
1357 | continue; | |||
1358 | ||||
1359 | llvm_unreachable("Scalar stores not expected in vector loop")::llvm::llvm_unreachable_internal("Scalar stores not expected in vector loop" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1359); | |||
1360 | } | |||
1361 | } | |||
1362 | ||||
1363 | void VectorBlockGenerator::copyStmt( | |||
1364 | ScopStmt &Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) { | |||
1365 | assert(Stmt.isBlockStmt() &&((Stmt.isBlockStmt() && "TODO: Only block statements can be copied by the vector block " "generator") ? static_cast<void> (0) : __assert_fail ( "Stmt.isBlockStmt() && \"TODO: Only block statements can be copied by the vector block \" \"generator\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1367, __PRETTY_FUNCTION__)) | |||
| ||||
1366 | "TODO: Only block statements can be copied by the vector block "((Stmt.isBlockStmt() && "TODO: Only block statements can be copied by the vector block " "generator") ? static_cast<void> (0) : __assert_fail ( "Stmt.isBlockStmt() && \"TODO: Only block statements can be copied by the vector block \" \"generator\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1367, __PRETTY_FUNCTION__)) | |||
1367 | "generator")((Stmt.isBlockStmt() && "TODO: Only block statements can be copied by the vector block " "generator") ? static_cast<void> (0) : __assert_fail ( "Stmt.isBlockStmt() && \"TODO: Only block statements can be copied by the vector block \" \"generator\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1367, __PRETTY_FUNCTION__)); | |||
1368 | ||||
1369 | BasicBlock *BB = Stmt.getBasicBlock(); | |||
1370 | BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(), | |||
1371 | &*Builder.GetInsertPoint(), &DT, &LI); | |||
1372 | CopyBB->setName("polly.stmt." + BB->getName()); | |||
1373 | Builder.SetInsertPoint(&CopyBB->front()); | |||
1374 | ||||
1375 | // Create two maps that store the mapping from the original instructions of | |||
1376 | // the old basic block to their copies in the new basic block. Those maps | |||
1377 | // are basic block local. | |||
1378 | // | |||
1379 | // As vector code generation is supported there is one map for scalar values | |||
1380 | // and one for vector values. | |||
1381 | // | |||
1382 | // In case we just do scalar code generation, the vectorMap is not used and | |||
1383 | // the scalarMap has just one dimension, which contains the mapping. | |||
1384 | // | |||
1385 | // In case vector code generation is done, an instruction may either appear | |||
1386 | // in the vector map once (as it is calculating >vectorwidth< values at a | |||
1387 | // time. Or (if the values are calculated using scalar operations), it | |||
1388 | // appears once in every dimension of the scalarMap. | |||
1389 | VectorValueMapT ScalarBlockMap(getVectorWidth()); | |||
1390 | ValueMapT VectorBlockMap; | |||
1391 | ||||
1392 | generateScalarVectorLoads(Stmt, VectorBlockMap); | |||
1393 | ||||
1394 | for (Instruction *Inst : Stmt.getInstructions()) | |||
1395 | copyInstruction(Stmt, Inst, VectorBlockMap, ScalarBlockMap, NewAccesses); | |||
1396 | ||||
1397 | verifyNoScalarStores(Stmt); | |||
1398 | } | |||
1399 | ||||
1400 | BasicBlock *RegionGenerator::repairDominance(BasicBlock *BB, | |||
1401 | BasicBlock *BBCopy) { | |||
1402 | ||||
1403 | BasicBlock *BBIDom = DT.getNode(BB)->getIDom()->getBlock(); | |||
1404 | BasicBlock *BBCopyIDom = EndBlockMap.lookup(BBIDom); | |||
1405 | ||||
1406 | if (BBCopyIDom) | |||
1407 | DT.changeImmediateDominator(BBCopy, BBCopyIDom); | |||
1408 | ||||
1409 | return StartBlockMap.lookup(BBIDom); | |||
1410 | } | |||
1411 | ||||
1412 | // This is to determine whether an llvm::Value (defined in @p BB) is usable when | |||
1413 | // leaving a subregion. The straight-forward DT.dominates(BB, R->getExitBlock()) | |||
1414 | // does not work in cases where the exit block has edges from outside the | |||
1415 | // region. In that case the llvm::Value would never be usable in in the exit | |||
1416 | // block. The RegionGenerator however creates an new exit block ('ExitBBCopy') | |||
1417 | // for the subregion's exiting edges only. We need to determine whether an | |||
1418 | // llvm::Value is usable in there. We do this by checking whether it dominates | |||
1419 | // all exiting blocks individually. | |||
1420 | static bool isDominatingSubregionExit(const DominatorTree &DT, Region *R, | |||
1421 | BasicBlock *BB) { | |||
1422 | for (auto ExitingBB : predecessors(R->getExit())) { | |||
1423 | // Check for non-subregion incoming edges. | |||
1424 | if (!R->contains(ExitingBB)) | |||
1425 | continue; | |||
1426 | ||||
1427 | if (!DT.dominates(BB, ExitingBB)) | |||
1428 | return false; | |||
1429 | } | |||
1430 | ||||
1431 | return true; | |||
1432 | } | |||
1433 | ||||
1434 | // Find the direct dominator of the subregion's exit block if the subregion was | |||
1435 | // simplified. | |||
1436 | static BasicBlock *findExitDominator(DominatorTree &DT, Region *R) { | |||
1437 | BasicBlock *Common = nullptr; | |||
1438 | for (auto ExitingBB : predecessors(R->getExit())) { | |||
1439 | // Check for non-subregion incoming edges. | |||
1440 | if (!R->contains(ExitingBB)) | |||
1441 | continue; | |||
1442 | ||||
1443 | // First exiting edge. | |||
1444 | if (!Common) { | |||
1445 | Common = ExitingBB; | |||
1446 | continue; | |||
1447 | } | |||
1448 | ||||
1449 | Common = DT.findNearestCommonDominator(Common, ExitingBB); | |||
1450 | } | |||
1451 | ||||
1452 | assert(Common && R->contains(Common))((Common && R->contains(Common)) ? static_cast< void> (0) : __assert_fail ("Common && R->contains(Common)" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1452, __PRETTY_FUNCTION__)); | |||
1453 | return Common; | |||
1454 | } | |||
1455 | ||||
1456 | void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT <S, | |||
1457 | isl_id_to_ast_expr *IdToAstExp) { | |||
1458 | assert(Stmt.isRegionStmt() &&((Stmt.isRegionStmt() && "Only region statements can be copied by the region generator" ) ? static_cast<void> (0) : __assert_fail ("Stmt.isRegionStmt() && \"Only region statements can be copied by the region generator\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1459, __PRETTY_FUNCTION__)) | |||
1459 | "Only region statements can be copied by the region generator")((Stmt.isRegionStmt() && "Only region statements can be copied by the region generator" ) ? static_cast<void> (0) : __assert_fail ("Stmt.isRegionStmt() && \"Only region statements can be copied by the region generator\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1459, __PRETTY_FUNCTION__)); | |||
1460 | ||||
1461 | // Forget all old mappings. | |||
1462 | StartBlockMap.clear(); | |||
1463 | EndBlockMap.clear(); | |||
1464 | RegionMaps.clear(); | |||
1465 | IncompletePHINodeMap.clear(); | |||
1466 | ||||
1467 | // Collection of all values related to this subregion. | |||
1468 | ValueMapT ValueMap; | |||
1469 | ||||
1470 | // The region represented by the statement. | |||
1471 | Region *R = Stmt.getRegion(); | |||
1472 | ||||
1473 | // Create a dedicated entry for the region where we can reload all demoted | |||
1474 | // inputs. | |||
1475 | BasicBlock *EntryBB = R->getEntry(); | |||
1476 | BasicBlock *EntryBBCopy = SplitBlock(Builder.GetInsertBlock(), | |||
1477 | &*Builder.GetInsertPoint(), &DT, &LI); | |||
1478 | EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry"); | |||
1479 | Builder.SetInsertPoint(&EntryBBCopy->front()); | |||
1480 | ||||
1481 | ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy]; | |||
1482 | generateScalarLoads(Stmt, LTS, EntryBBMap, IdToAstExp); | |||
1483 | generateBeginStmtTrace(Stmt, LTS, EntryBBMap); | |||
1484 | ||||
1485 | for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI) | |||
1486 | if (!R->contains(*PI)) { | |||
1487 | StartBlockMap[*PI] = EntryBBCopy; | |||
1488 | EndBlockMap[*PI] = EntryBBCopy; | |||
1489 | } | |||
1490 | ||||
1491 | // Iterate over all blocks in the region in a breadth-first search. | |||
1492 | std::deque<BasicBlock *> Blocks; | |||
1493 | SmallSetVector<BasicBlock *, 8> SeenBlocks; | |||
1494 | Blocks.push_back(EntryBB); | |||
1495 | SeenBlocks.insert(EntryBB); | |||
1496 | ||||
1497 | while (!Blocks.empty()) { | |||
1498 | BasicBlock *BB = Blocks.front(); | |||
1499 | Blocks.pop_front(); | |||
1500 | ||||
1501 | // First split the block and update dominance information. | |||
1502 | BasicBlock *BBCopy = splitBB(BB); | |||
1503 | BasicBlock *BBCopyIDom = repairDominance(BB, BBCopy); | |||
1504 | ||||
1505 | // Get the mapping for this block and initialize it with either the scalar | |||
1506 | // loads from the generated entering block (which dominates all blocks of | |||
1507 | // this subregion) or the maps of the immediate dominator, if part of the | |||
1508 | // subregion. The latter necessarily includes the former. | |||
1509 | ValueMapT *InitBBMap; | |||
1510 | if (BBCopyIDom) { | |||
1511 | assert(RegionMaps.count(BBCopyIDom))((RegionMaps.count(BBCopyIDom)) ? static_cast<void> (0) : __assert_fail ("RegionMaps.count(BBCopyIDom)", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1511, __PRETTY_FUNCTION__)); | |||
1512 | InitBBMap = &RegionMaps[BBCopyIDom]; | |||
1513 | } else | |||
1514 | InitBBMap = &EntryBBMap; | |||
1515 | auto Inserted = RegionMaps.insert(std::make_pair(BBCopy, *InitBBMap)); | |||
1516 | ValueMapT &RegionMap = Inserted.first->second; | |||
1517 | ||||
1518 | // Copy the block with the BlockGenerator. | |||
1519 | Builder.SetInsertPoint(&BBCopy->front()); | |||
1520 | copyBB(Stmt, BB, BBCopy, RegionMap, LTS, IdToAstExp); | |||
1521 | ||||
1522 | // In order to remap PHI nodes we store also basic block mappings. | |||
1523 | StartBlockMap[BB] = BBCopy; | |||
1524 | EndBlockMap[BB] = Builder.GetInsertBlock(); | |||
1525 | ||||
1526 | // Add values to incomplete PHI nodes waiting for this block to be copied. | |||
1527 | for (const PHINodePairTy &PHINodePair : IncompletePHINodeMap[BB]) | |||
1528 | addOperandToPHI(Stmt, PHINodePair.first, PHINodePair.second, BB, LTS); | |||
1529 | IncompletePHINodeMap[BB].clear(); | |||
1530 | ||||
1531 | // And continue with new successors inside the region. | |||
1532 | for (auto SI = succ_begin(BB), SE = succ_end(BB); SI != SE; SI++) | |||
1533 | if (R->contains(*SI) && SeenBlocks.insert(*SI)) | |||
1534 | Blocks.push_back(*SI); | |||
1535 | ||||
1536 | // Remember value in case it is visible after this subregion. | |||
1537 | if (isDominatingSubregionExit(DT, R, BB)) | |||
1538 | ValueMap.insert(RegionMap.begin(), RegionMap.end()); | |||
1539 | } | |||
1540 | ||||
1541 | // Now create a new dedicated region exit block and add it to the region map. | |||
1542 | BasicBlock *ExitBBCopy = SplitBlock(Builder.GetInsertBlock(), | |||
1543 | &*Builder.GetInsertPoint(), &DT, &LI); | |||
1544 | ExitBBCopy->setName("polly.stmt." + R->getExit()->getName() + ".exit"); | |||
1545 | StartBlockMap[R->getExit()] = ExitBBCopy; | |||
1546 | EndBlockMap[R->getExit()] = ExitBBCopy; | |||
1547 | ||||
1548 | BasicBlock *ExitDomBBCopy = EndBlockMap.lookup(findExitDominator(DT, R)); | |||
1549 | assert(ExitDomBBCopy &&((ExitDomBBCopy && "Common exit dominator must be within region; at least the entry node " "must match") ? static_cast<void> (0) : __assert_fail ( "ExitDomBBCopy && \"Common exit dominator must be within region; at least the entry node \" \"must match\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1551, __PRETTY_FUNCTION__)) | |||
1550 | "Common exit dominator must be within region; at least the entry node "((ExitDomBBCopy && "Common exit dominator must be within region; at least the entry node " "must match") ? static_cast<void> (0) : __assert_fail ( "ExitDomBBCopy && \"Common exit dominator must be within region; at least the entry node \" \"must match\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1551, __PRETTY_FUNCTION__)) | |||
1551 | "must match")((ExitDomBBCopy && "Common exit dominator must be within region; at least the entry node " "must match") ? static_cast<void> (0) : __assert_fail ( "ExitDomBBCopy && \"Common exit dominator must be within region; at least the entry node \" \"must match\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1551, __PRETTY_FUNCTION__)); | |||
1552 | DT.changeImmediateDominator(ExitBBCopy, ExitDomBBCopy); | |||
1553 | ||||
1554 | // As the block generator doesn't handle control flow we need to add the | |||
1555 | // region control flow by hand after all blocks have been copied. | |||
1556 | for (BasicBlock *BB : SeenBlocks) { | |||
1557 | ||||
1558 | BasicBlock *BBCopyStart = StartBlockMap[BB]; | |||
1559 | BasicBlock *BBCopyEnd = EndBlockMap[BB]; | |||
1560 | Instruction *TI = BB->getTerminator(); | |||
1561 | if (isa<UnreachableInst>(TI)) { | |||
1562 | while (!BBCopyEnd->empty()) | |||
1563 | BBCopyEnd->begin()->eraseFromParent(); | |||
1564 | new UnreachableInst(BBCopyEnd->getContext(), BBCopyEnd); | |||
1565 | continue; | |||
1566 | } | |||
1567 | ||||
1568 | Instruction *BICopy = BBCopyEnd->getTerminator(); | |||
1569 | ||||
1570 | ValueMapT &RegionMap = RegionMaps[BBCopyStart]; | |||
1571 | RegionMap.insert(StartBlockMap.begin(), StartBlockMap.end()); | |||
1572 | ||||
1573 | Builder.SetInsertPoint(BICopy); | |||
1574 | copyInstScalar(Stmt, TI, RegionMap, LTS); | |||
1575 | BICopy->eraseFromParent(); | |||
1576 | } | |||
1577 | ||||
1578 | // Add counting PHI nodes to all loops in the region that can be used as | |||
1579 | // replacement for SCEVs referring to the old loop. | |||
1580 | for (BasicBlock *BB : SeenBlocks) { | |||
1581 | Loop *L = LI.getLoopFor(BB); | |||
1582 | if (L == nullptr || L->getHeader() != BB || !R->contains(L)) | |||
1583 | continue; | |||
1584 | ||||
1585 | BasicBlock *BBCopy = StartBlockMap[BB]; | |||
1586 | Value *NullVal = Builder.getInt32(0); | |||
1587 | PHINode *LoopPHI = | |||
1588 | PHINode::Create(Builder.getInt32Ty(), 2, "polly.subregion.iv"); | |||
1589 | Instruction *LoopPHIInc = BinaryOperator::CreateAdd( | |||
1590 | LoopPHI, Builder.getInt32(1), "polly.subregion.iv.inc"); | |||
1591 | LoopPHI->insertBefore(&BBCopy->front()); | |||
1592 | LoopPHIInc->insertBefore(BBCopy->getTerminator()); | |||
1593 | ||||
1594 | for (auto *PredBB : make_range(pred_begin(BB), pred_end(BB))) { | |||
1595 | if (!R->contains(PredBB)) | |||
1596 | continue; | |||
1597 | if (L->contains(PredBB)) | |||
1598 | LoopPHI->addIncoming(LoopPHIInc, EndBlockMap[PredBB]); | |||
1599 | else | |||
1600 | LoopPHI->addIncoming(NullVal, EndBlockMap[PredBB]); | |||
1601 | } | |||
1602 | ||||
1603 | for (auto *PredBBCopy : make_range(pred_begin(BBCopy), pred_end(BBCopy))) | |||
1604 | if (LoopPHI->getBasicBlockIndex(PredBBCopy) < 0) | |||
1605 | LoopPHI->addIncoming(NullVal, PredBBCopy); | |||
1606 | ||||
1607 | LTS[L] = SE.getUnknown(LoopPHI); | |||
1608 | } | |||
1609 | ||||
1610 | // Continue generating code in the exit block. | |||
1611 | Builder.SetInsertPoint(&*ExitBBCopy->getFirstInsertionPt()); | |||
1612 | ||||
1613 | // Write values visible to other statements. | |||
1614 | generateScalarStores(Stmt, LTS, ValueMap, IdToAstExp); | |||
1615 | StartBlockMap.clear(); | |||
1616 | EndBlockMap.clear(); | |||
1617 | RegionMaps.clear(); | |||
1618 | IncompletePHINodeMap.clear(); | |||
1619 | } | |||
1620 | ||||
1621 | PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT <S, | |||
1622 | ValueMapT &BBMap, Loop *L) { | |||
1623 | ScopStmt *Stmt = MA->getStatement(); | |||
1624 | Region *SubR = Stmt->getRegion(); | |||
1625 | auto Incoming = MA->getIncoming(); | |||
1626 | ||||
1627 | PollyIRBuilder::InsertPointGuard IPGuard(Builder); | |||
1628 | PHINode *OrigPHI = cast<PHINode>(MA->getAccessInstruction()); | |||
1629 | BasicBlock *NewSubregionExit = Builder.GetInsertBlock(); | |||
1630 | ||||
1631 | // This can happen if the subregion is simplified after the ScopStmts | |||
1632 | // have been created; simplification happens as part of CodeGeneration. | |||
1633 | if (OrigPHI->getParent() != SubR->getExit()) { | |||
1634 | BasicBlock *FormerExit = SubR->getExitingBlock(); | |||
1635 | if (FormerExit) | |||
1636 | NewSubregionExit = StartBlockMap.lookup(FormerExit); | |||
1637 | } | |||
1638 | ||||
1639 | PHINode *NewPHI = PHINode::Create(OrigPHI->getType(), Incoming.size(), | |||
1640 | "polly." + OrigPHI->getName(), | |||
1641 | NewSubregionExit->getFirstNonPHI()); | |||
1642 | ||||
1643 | // Add the incoming values to the PHI. | |||
1644 | for (auto &Pair : Incoming) { | |||
1645 | BasicBlock *OrigIncomingBlock = Pair.first; | |||
1646 | BasicBlock *NewIncomingBlockStart = StartBlockMap.lookup(OrigIncomingBlock); | |||
1647 | BasicBlock *NewIncomingBlockEnd = EndBlockMap.lookup(OrigIncomingBlock); | |||
1648 | Builder.SetInsertPoint(NewIncomingBlockEnd->getTerminator()); | |||
1649 | assert(RegionMaps.count(NewIncomingBlockStart))((RegionMaps.count(NewIncomingBlockStart)) ? static_cast<void > (0) : __assert_fail ("RegionMaps.count(NewIncomingBlockStart)" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1649, __PRETTY_FUNCTION__)); | |||
1650 | assert(RegionMaps.count(NewIncomingBlockEnd))((RegionMaps.count(NewIncomingBlockEnd)) ? static_cast<void > (0) : __assert_fail ("RegionMaps.count(NewIncomingBlockEnd)" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1650, __PRETTY_FUNCTION__)); | |||
1651 | ValueMapT *LocalBBMap = &RegionMaps[NewIncomingBlockStart]; | |||
1652 | ||||
1653 | Value *OrigIncomingValue = Pair.second; | |||
1654 | Value *NewIncomingValue = | |||
1655 | getNewValue(*Stmt, OrigIncomingValue, *LocalBBMap, LTS, L); | |||
1656 | NewPHI->addIncoming(NewIncomingValue, NewIncomingBlockEnd); | |||
1657 | } | |||
1658 | ||||
1659 | return NewPHI; | |||
1660 | } | |||
1661 | ||||
1662 | Value *RegionGenerator::getExitScalar(MemoryAccess *MA, LoopToScevMapT <S, | |||
1663 | ValueMapT &BBMap) { | |||
1664 | ScopStmt *Stmt = MA->getStatement(); | |||
1665 | ||||
1666 | // TODO: Add some test cases that ensure this is really the right choice. | |||
1667 | Loop *L = LI.getLoopFor(Stmt->getRegion()->getExit()); | |||
1668 | ||||
1669 | if (MA->isAnyPHIKind()) { | |||
1670 | auto Incoming = MA->getIncoming(); | |||
1671 | assert(!Incoming.empty() &&((!Incoming.empty() && "PHI WRITEs must have originate from at least one incoming block" ) ? static_cast<void> (0) : __assert_fail ("!Incoming.empty() && \"PHI WRITEs must have originate from at least one incoming block\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1672, __PRETTY_FUNCTION__)) | |||
1672 | "PHI WRITEs must have originate from at least one incoming block")((!Incoming.empty() && "PHI WRITEs must have originate from at least one incoming block" ) ? static_cast<void> (0) : __assert_fail ("!Incoming.empty() && \"PHI WRITEs must have originate from at least one incoming block\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1672, __PRETTY_FUNCTION__)); | |||
1673 | ||||
1674 | // If there is only one incoming value, we do not need to create a PHI. | |||
1675 | if (Incoming.size() == 1) { | |||
1676 | Value *OldVal = Incoming[0].second; | |||
1677 | return getNewValue(*Stmt, OldVal, BBMap, LTS, L); | |||
1678 | } | |||
1679 | ||||
1680 | return buildExitPHI(MA, LTS, BBMap, L); | |||
1681 | } | |||
1682 | ||||
1683 | // MemoryKind::Value accesses leaving the subregion must dominate the exit | |||
1684 | // block; just pass the copied value. | |||
1685 | Value *OldVal = MA->getAccessValue(); | |||
1686 | return getNewValue(*Stmt, OldVal, BBMap, LTS, L); | |||
1687 | } | |||
1688 | ||||
1689 | void RegionGenerator::generateScalarStores( | |||
1690 | ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMap, | |||
1691 | __isl_keep isl_id_to_ast_expr *NewAccesses) { | |||
1692 | assert(Stmt.getRegion() &&((Stmt.getRegion() && "Block statements need to use the generateScalarStores() " "function in the BlockGenerator") ? static_cast<void> ( 0) : __assert_fail ("Stmt.getRegion() && \"Block statements need to use the generateScalarStores() \" \"function in the BlockGenerator\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1694, __PRETTY_FUNCTION__)) | |||
1693 | "Block statements need to use the generateScalarStores() "((Stmt.getRegion() && "Block statements need to use the generateScalarStores() " "function in the BlockGenerator") ? static_cast<void> ( 0) : __assert_fail ("Stmt.getRegion() && \"Block statements need to use the generateScalarStores() \" \"function in the BlockGenerator\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1694, __PRETTY_FUNCTION__)) | |||
1694 | "function in the BlockGenerator")((Stmt.getRegion() && "Block statements need to use the generateScalarStores() " "function in the BlockGenerator") ? static_cast<void> ( 0) : __assert_fail ("Stmt.getRegion() && \"Block statements need to use the generateScalarStores() \" \"function in the BlockGenerator\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1694, __PRETTY_FUNCTION__)); | |||
1695 | ||||
1696 | // Get the exit scalar values before generating the writes. | |||
1697 | // This is necessary because RegionGenerator::getExitScalar may insert | |||
1698 | // PHINodes that depend on the region's exiting blocks. But | |||
1699 | // BlockGenerator::generateConditionalExecution may insert a new basic block | |||
1700 | // such that the current basic block is not a direct successor of the exiting | |||
1701 | // blocks anymore. Hence, build the PHINodes while the current block is still | |||
1702 | // the direct successor. | |||
1703 | SmallDenseMap<MemoryAccess *, Value *> NewExitScalars; | |||
1704 | for (MemoryAccess *MA : Stmt) { | |||
1705 | if (MA->isOriginalArrayKind() || MA->isRead()) | |||
1706 | continue; | |||
1707 | ||||
1708 | Value *NewVal = getExitScalar(MA, LTS, BBMap); | |||
1709 | NewExitScalars[MA] = NewVal; | |||
1710 | } | |||
1711 | ||||
1712 | for (MemoryAccess *MA : Stmt) { | |||
1713 | if (MA->isOriginalArrayKind() || MA->isRead()) | |||
1714 | continue; | |||
1715 | ||||
1716 | isl::set AccDom = MA->getAccessRelation().domain(); | |||
1717 | std::string Subject = MA->getId().get_name(); | |||
1718 | generateConditionalExecution( | |||
1719 | Stmt, AccDom, Subject.c_str(), [&, this, MA]() { | |||
1720 | Value *NewVal = NewExitScalars.lookup(MA); | |||
1721 | assert(NewVal && "The exit scalar must be determined before")((NewVal && "The exit scalar must be determined before" ) ? static_cast<void> (0) : __assert_fail ("NewVal && \"The exit scalar must be determined before\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1721, __PRETTY_FUNCTION__)); | |||
1722 | Value *Address = getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, | |||
1723 | BBMap, NewAccesses); | |||
1724 | assert((!isa<Instruction>(NewVal) ||(((!isa<Instruction>(NewVal) || DT.dominates(cast<Instruction >(NewVal)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(NewVal) || DT.dominates(cast<Instruction>(NewVal)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1727, __PRETTY_FUNCTION__)) | |||
1725 | DT.dominates(cast<Instruction>(NewVal)->getParent(),(((!isa<Instruction>(NewVal) || DT.dominates(cast<Instruction >(NewVal)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(NewVal) || DT.dominates(cast<Instruction>(NewVal)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1727, __PRETTY_FUNCTION__)) | |||
1726 | Builder.GetInsertBlock())) &&(((!isa<Instruction>(NewVal) || DT.dominates(cast<Instruction >(NewVal)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(NewVal) || DT.dominates(cast<Instruction>(NewVal)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1727, __PRETTY_FUNCTION__)) | |||
1727 | "Domination violation")(((!isa<Instruction>(NewVal) || DT.dominates(cast<Instruction >(NewVal)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(NewVal) || DT.dominates(cast<Instruction>(NewVal)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1727, __PRETTY_FUNCTION__)); | |||
1728 | assert((!isa<Instruction>(Address) ||(((!isa<Instruction>(Address) || DT.dominates(cast<Instruction >(Address)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Address) || DT.dominates(cast<Instruction>(Address)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1731, __PRETTY_FUNCTION__)) | |||
1729 | DT.dominates(cast<Instruction>(Address)->getParent(),(((!isa<Instruction>(Address) || DT.dominates(cast<Instruction >(Address)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Address) || DT.dominates(cast<Instruction>(Address)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1731, __PRETTY_FUNCTION__)) | |||
1730 | Builder.GetInsertBlock())) &&(((!isa<Instruction>(Address) || DT.dominates(cast<Instruction >(Address)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Address) || DT.dominates(cast<Instruction>(Address)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1731, __PRETTY_FUNCTION__)) | |||
1731 | "Domination violation")(((!isa<Instruction>(Address) || DT.dominates(cast<Instruction >(Address)->getParent(), Builder.GetInsertBlock())) && "Domination violation") ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Address) || DT.dominates(cast<Instruction>(Address)->getParent(), Builder.GetInsertBlock())) && \"Domination violation\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1731, __PRETTY_FUNCTION__)); | |||
1732 | Builder.CreateStore(NewVal, Address); | |||
1733 | }); | |||
1734 | } | |||
1735 | } | |||
1736 | ||||
1737 | void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, PHINode *PHI, | |||
1738 | PHINode *PHICopy, BasicBlock *IncomingBB, | |||
1739 | LoopToScevMapT <S) { | |||
1740 | // If the incoming block was not yet copied mark this PHI as incomplete. | |||
1741 | // Once the block will be copied the incoming value will be added. | |||
1742 | BasicBlock *BBCopyStart = StartBlockMap[IncomingBB]; | |||
1743 | BasicBlock *BBCopyEnd = EndBlockMap[IncomingBB]; | |||
1744 | if (!BBCopyStart) { | |||
1745 | assert(!BBCopyEnd)((!BBCopyEnd) ? static_cast<void> (0) : __assert_fail ( "!BBCopyEnd", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1745, __PRETTY_FUNCTION__)); | |||
1746 | assert(Stmt.represents(IncomingBB) &&((Stmt.represents(IncomingBB) && "Bad incoming block for PHI in non-affine region" ) ? static_cast<void> (0) : __assert_fail ("Stmt.represents(IncomingBB) && \"Bad incoming block for PHI in non-affine region\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1747, __PRETTY_FUNCTION__)) | |||
1747 | "Bad incoming block for PHI in non-affine region")((Stmt.represents(IncomingBB) && "Bad incoming block for PHI in non-affine region" ) ? static_cast<void> (0) : __assert_fail ("Stmt.represents(IncomingBB) && \"Bad incoming block for PHI in non-affine region\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1747, __PRETTY_FUNCTION__)); | |||
1748 | IncompletePHINodeMap[IncomingBB].push_back(std::make_pair(PHI, PHICopy)); | |||
1749 | return; | |||
1750 | } | |||
1751 | ||||
1752 | assert(RegionMaps.count(BBCopyStart) &&((RegionMaps.count(BBCopyStart) && "Incoming PHI block did not have a BBMap" ) ? static_cast<void> (0) : __assert_fail ("RegionMaps.count(BBCopyStart) && \"Incoming PHI block did not have a BBMap\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1753, __PRETTY_FUNCTION__)) | |||
1753 | "Incoming PHI block did not have a BBMap")((RegionMaps.count(BBCopyStart) && "Incoming PHI block did not have a BBMap" ) ? static_cast<void> (0) : __assert_fail ("RegionMaps.count(BBCopyStart) && \"Incoming PHI block did not have a BBMap\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1753, __PRETTY_FUNCTION__)); | |||
1754 | ValueMapT &BBCopyMap = RegionMaps[BBCopyStart]; | |||
1755 | ||||
1756 | Value *OpCopy = nullptr; | |||
1757 | ||||
1758 | if (Stmt.represents(IncomingBB)) { | |||
1759 | Value *Op = PHI->getIncomingValueForBlock(IncomingBB); | |||
1760 | ||||
1761 | // If the current insert block is different from the PHIs incoming block | |||
1762 | // change it, otherwise do not. | |||
1763 | auto IP = Builder.GetInsertPoint(); | |||
1764 | if (IP->getParent() != BBCopyEnd) | |||
1765 | Builder.SetInsertPoint(BBCopyEnd->getTerminator()); | |||
1766 | OpCopy = getNewValue(Stmt, Op, BBCopyMap, LTS, getLoopForStmt(Stmt)); | |||
1767 | if (IP->getParent() != BBCopyEnd) | |||
1768 | Builder.SetInsertPoint(&*IP); | |||
1769 | } else { | |||
1770 | // All edges from outside the non-affine region become a single edge | |||
1771 | // in the new copy of the non-affine region. Make sure to only add the | |||
1772 | // corresponding edge the first time we encounter a basic block from | |||
1773 | // outside the non-affine region. | |||
1774 | if (PHICopy->getBasicBlockIndex(BBCopyEnd) >= 0) | |||
1775 | return; | |||
1776 | ||||
1777 | // Get the reloaded value. | |||
1778 | OpCopy = getNewValue(Stmt, PHI, BBCopyMap, LTS, getLoopForStmt(Stmt)); | |||
1779 | } | |||
1780 | ||||
1781 | assert(OpCopy && "Incoming PHI value was not copied properly")((OpCopy && "Incoming PHI value was not copied properly" ) ? static_cast<void> (0) : __assert_fail ("OpCopy && \"Incoming PHI value was not copied properly\"" , "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/polly/lib/CodeGen/BlockGenerators.cpp" , 1781, __PRETTY_FUNCTION__)); | |||
1782 | PHICopy->addIncoming(OpCopy, BBCopyEnd); | |||
1783 | } | |||
1784 | ||||
1785 | void RegionGenerator::copyPHIInstruction(ScopStmt &Stmt, PHINode *PHI, | |||
1786 | ValueMapT &BBMap, | |||
1787 | LoopToScevMapT <S) { | |||
1788 | unsigned NumIncoming = PHI->getNumIncomingValues(); | |||
1789 | PHINode *PHICopy = | |||
1790 | Builder.CreatePHI(PHI->getType(), NumIncoming, "polly." + PHI->getName()); | |||
1791 | PHICopy->moveBefore(PHICopy->getParent()->getFirstNonPHI()); | |||
1792 | BBMap[PHI] = PHICopy; | |||
1793 | ||||
1794 | for (BasicBlock *IncomingBB : PHI->blocks()) | |||
1795 | addOperandToPHI(Stmt, PHI, PHICopy, IncomingBB, LTS); | |||
1796 | } |