Bug Summary

File:tools/polly/lib/CodeGen/BlockGenerators.cpp
Location:line 1124, column 5
Description:Value stored to 'ExitBB' is never read

Annotated Source Code

1//===--- BlockGenerators.cpp - Generate code for statements -----*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the BlockGenerator and VectorBlockGenerator classes,
11// which generate sequential code and vectorized code for a polyhedral
12// statement, respectively.
13//
14//===----------------------------------------------------------------------===//
15
16#include "polly/CodeGen/BlockGenerators.h"
17#include "polly/CodeGen/CodeGeneration.h"
18#include "polly/CodeGen/IslExprBuilder.h"
19#include "polly/CodeGen/RuntimeDebugBuilder.h"
20#include "polly/Options.h"
21#include "polly/ScopInfo.h"
22#include "polly/Support/GICHelper.h"
23#include "polly/Support/SCEVValidator.h"
24#include "polly/Support/ScopHelper.h"
25#include "llvm/Analysis/LoopInfo.h"
26#include "llvm/Analysis/RegionInfo.h"
27#include "llvm/Analysis/ScalarEvolution.h"
28#include "llvm/IR/IntrinsicInst.h"
29#include "llvm/IR/Module.h"
30#include "llvm/Transforms/Utils/BasicBlockUtils.h"
31#include "llvm/Transforms/Utils/Local.h"
32#include "isl/aff.h"
33#include "isl/ast.h"
34#include "isl/ast_build.h"
35#include "isl/set.h"
36#include <deque>
37
38using namespace llvm;
39using namespace polly;
40
41static cl::opt<bool> Aligned("enable-polly-aligned",
42 cl::desc("Assumed aligned memory accesses."),
43 cl::Hidden, cl::init(false), cl::ZeroOrMore,
44 cl::cat(PollyCategory));
45
46static cl::opt<bool> DebugPrinting(
47 "polly-codegen-add-debug-printing",
48 cl::desc("Add printf calls that show the values loaded/stored."),
49 cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
50
51BlockGenerator::BlockGenerator(PollyIRBuilder &B, LoopInfo &LI,
52 ScalarEvolution &SE, DominatorTree &DT,
53 ScalarAllocaMapTy &ScalarMap,
54 ScalarAllocaMapTy &PHIOpMap,
55 EscapeUsersAllocaMapTy &EscapeMap,
56 ValueMapT &GlobalMap,
57 IslExprBuilder *ExprBuilder)
58 : Builder(B), LI(LI), SE(SE), ExprBuilder(ExprBuilder), DT(DT),
59 EntryBB(nullptr), PHIOpMap(PHIOpMap), ScalarMap(ScalarMap),
60 EscapeMap(EscapeMap), GlobalMap(GlobalMap) {}
61
62Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old,
63 ValueMapT &BBMap,
64 LoopToScevMapT &LTS,
65 Loop *L) const {
66 if (!SE.isSCEVable(Old->getType()))
67 return nullptr;
68
69 const SCEV *Scev = SE.getSCEVAtScope(Old, L);
70 if (!Scev)
71 return nullptr;
72
73 if (isa<SCEVCouldNotCompute>(Scev))
74 return nullptr;
75
76 const SCEV *NewScev = apply(Scev, LTS, SE);
77 ValueMapT VTV;
78 VTV.insert(BBMap.begin(), BBMap.end());
79 VTV.insert(GlobalMap.begin(), GlobalMap.end());
80
81 Scop &S = *Stmt.getParent();
82 const DataLayout &DL =
83 S.getRegion().getEntry()->getParent()->getParent()->getDataLayout();
84 auto IP = Builder.GetInsertPoint();
85
86 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 87, __PRETTY_FUNCTION__))
87 "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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 87, __PRETTY_FUNCTION__));
88 Value *Expanded =
89 expandCodeFor(S, SE, DL, "polly", NewScev, Old->getType(), &*IP, &VTV);
90
91 BBMap[Old] = Expanded;
92 return Expanded;
93}
94
95Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
96 LoopToScevMapT &LTS, Loop *L) const {
97 // Constants that do not reference any named value can always remain
98 // unchanged. Handle them early to avoid expensive map lookups. We do not take
99 // the fast-path for external constants which are referenced through globals
100 // as these may need to be rewritten when distributing code accross different
101 // LLVM modules.
102 if (isa<Constant>(Old) && !isa<GlobalValue>(Old))
103 return Old;
104
105 // Inline asm is like a constant to us.
106 if (isa<InlineAsm>(Old))
107 return Old;
108
109 if (Value *New = GlobalMap.lookup(Old)) {
110 if (Value *NewRemapped = GlobalMap.lookup(New))
111 New = NewRemapped;
112 if (Old->getType()->getScalarSizeInBits() <
113 New->getType()->getScalarSizeInBits())
114 New = Builder.CreateTruncOrBitCast(New, Old->getType());
115
116 return New;
117 }
118
119 if (Value *New = BBMap.lookup(Old))
120 return New;
121
122 if (Value *New = trySynthesizeNewValue(Stmt, Old, BBMap, LTS, L))
123 return New;
124
125 // A scop-constant value defined by a global or a function parameter.
126 if (isa<GlobalValue>(Old) || isa<Argument>(Old))
127 return Old;
128
129 // A scop-constant value defined by an instruction executed outside the scop.
130 if (const Instruction *Inst = dyn_cast<Instruction>(Old))
131 if (!Stmt.getParent()->getRegion().contains(Inst->getParent()))
132 return Old;
133
134 // The scalar dependence is neither available nor SCEVCodegenable.
135 llvm_unreachable("Unexpected scalar dependence in region!")::llvm::llvm_unreachable_internal("Unexpected scalar dependence in region!"
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 135);
136 return nullptr;
137}
138
139void BlockGenerator::copyInstScalar(ScopStmt &Stmt, Instruction *Inst,
140 ValueMapT &BBMap, LoopToScevMapT &LTS) {
141 // We do not generate debug intrinsics as we did not investigate how to
142 // copy them correctly. At the current state, they just crash the code
143 // generation as the meta-data operands are not correctly copied.
144 if (isa<DbgInfoIntrinsic>(Inst))
145 return;
146
147 Instruction *NewInst = Inst->clone();
148
149 // Replace old operands with the new ones.
150 for (Value *OldOperand : Inst->operands()) {
151 Value *NewOperand =
152 getNewValue(Stmt, OldOperand, BBMap, LTS, getLoopForStmt(Stmt));
153
154 if (!NewOperand) {
155 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!\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 156, __PRETTY_FUNCTION__))
156 "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!\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 156, __PRETTY_FUNCTION__));
157 delete NewInst;
158 return;
159 }
160
161 NewInst->replaceUsesOfWith(OldOperand, NewOperand);
162 }
163
164 Builder.Insert(NewInst);
165 BBMap[Inst] = NewInst;
166
167 if (!NewInst->getType()->isVoidTy())
168 NewInst->setName("p_" + Inst->getName());
169}
170
171Value *
172BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,
173 ValueMapT &BBMap, LoopToScevMapT &LTS,
174 isl_id_to_ast_expr *NewAccesses) {
175 const MemoryAccess &MA = Stmt.getArrayAccessFor(Inst);
176
177 isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(NewAccesses, MA.getId());
178
179 if (AccessExpr) {
180 AccessExpr = isl_ast_expr_address_of(AccessExpr);
181 auto Address = ExprBuilder->create(AccessExpr);
182
183 // Cast the address of this memory access to a pointer type that has the
184 // same element type as the original access, but uses the address space of
185 // the newly generated pointer.
186 auto OldPtrTy = MA.getAccessValue()->getType()->getPointerTo();
187 auto NewPtrTy = Address->getType();
188 OldPtrTy = PointerType::get(OldPtrTy->getElementType(),
189 NewPtrTy->getPointerAddressSpace());
190
191 if (OldPtrTy != NewPtrTy)
192 Address = Builder.CreateBitOrPointerCast(Address, OldPtrTy);
193 return Address;
194 }
195
196 return getNewValue(Stmt, Inst.getPointerOperand(), BBMap, LTS,
197 getLoopForStmt(Stmt));
198}
199
200Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const {
201 auto *StmtBB = Stmt.getEntryBlock();
202 return LI.getLoopFor(StmtBB);
203}
204
205Value *BlockGenerator::generateScalarLoad(ScopStmt &Stmt, LoadInst *Load,
206 ValueMapT &BBMap, LoopToScevMapT &LTS,
207 isl_id_to_ast_expr *NewAccesses) {
208 if (Value *PreloadLoad = GlobalMap.lookup(Load))
209 return PreloadLoad;
210
211 Value *NewPointer =
212 generateLocationAccessed(Stmt, Load, BBMap, LTS, NewAccesses);
213 Value *ScalarLoad = Builder.CreateAlignedLoad(
214 NewPointer, Load->getAlignment(), Load->getName() + "_p_scalar_");
215
216 if (DebugPrinting)
217 RuntimeDebugBuilder::createCPUPrinter(Builder, "Load from ", NewPointer,
218 ": ", ScalarLoad, "\n");
219
220 return ScalarLoad;
221}
222
223void BlockGenerator::generateScalarStore(ScopStmt &Stmt, StoreInst *Store,
224 ValueMapT &BBMap, LoopToScevMapT &LTS,
225 isl_id_to_ast_expr *NewAccesses) {
226 Value *NewPointer =
227 generateLocationAccessed(Stmt, Store, BBMap, LTS, NewAccesses);
228 Value *ValueOperand = getNewValue(Stmt, Store->getValueOperand(), BBMap, LTS,
229 getLoopForStmt(Stmt));
230
231 if (DebugPrinting)
232 RuntimeDebugBuilder::createCPUPrinter(Builder, "Store to ", NewPointer,
233 ": ", ValueOperand, "\n");
234
235 Builder.CreateAlignedStore(ValueOperand, NewPointer, Store->getAlignment());
236}
237
238bool BlockGenerator::canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst) {
239 Loop *L = getLoopForStmt(Stmt);
240 return (Stmt.isBlockStmt() || !Stmt.getRegion()->contains(L)) &&
241 canSynthesize(Inst, &LI, &SE, &Stmt.getParent()->getRegion(), L);
242}
243
244void BlockGenerator::copyInstruction(ScopStmt &Stmt, Instruction *Inst,
245 ValueMapT &BBMap, LoopToScevMapT &LTS,
246 isl_id_to_ast_expr *NewAccesses) {
247 // Terminator instructions control the control flow. They are explicitly
248 // expressed in the clast and do not need to be copied.
249 if (Inst->isTerminator())
250 return;
251
252 // Synthesizable statements will be generated on-demand.
253 if (canSyntheziseInStmt(Stmt, Inst))
254 return;
255
256 if (auto *Load = dyn_cast<LoadInst>(Inst)) {
257 Value *NewLoad = generateScalarLoad(Stmt, Load, BBMap, LTS, NewAccesses);
258 // Compute NewLoad before its insertion in BBMap to make the insertion
259 // deterministic.
260 BBMap[Load] = NewLoad;
261 return;
262 }
263
264 if (auto *Store = dyn_cast<StoreInst>(Inst)) {
265 generateScalarStore(Stmt, Store, BBMap, LTS, NewAccesses);
266 return;
267 }
268
269 if (auto *PHI = dyn_cast<PHINode>(Inst)) {
270 copyPHIInstruction(Stmt, PHI, BBMap, LTS);
271 return;
272 }
273
274 // Skip some special intrinsics for which we do not adjust the semantics to
275 // the new schedule. All others are handled like every other instruction.
276 if (isIgnoredIntrinsic(Inst))
277 return;
278
279 copyInstScalar(Stmt, Inst, BBMap, LTS);
280}
281
282void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
283 isl_id_to_ast_expr *NewAccesses) {
284 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 285, __PRETTY_FUNCTION__))
285 "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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 285, __PRETTY_FUNCTION__));
286
287 ValueMapT BBMap;
288
289 BasicBlock *BB = Stmt.getBasicBlock();
290 copyBB(Stmt, BB, BBMap, LTS, NewAccesses);
291}
292
293BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) {
294 BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(),
295 &*Builder.GetInsertPoint(), &DT, &LI);
296 CopyBB->setName("polly.stmt." + BB->getName());
297 return CopyBB;
298}
299
300BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,
301 ValueMapT &BBMap, LoopToScevMapT &LTS,
302 isl_id_to_ast_expr *NewAccesses) {
303 BasicBlock *CopyBB = splitBB(BB);
304 Builder.SetInsertPoint(&CopyBB->front());
305 generateScalarLoads(Stmt, BBMap);
306
307 copyBB(Stmt, BB, CopyBB, BBMap, LTS, NewAccesses);
308
309 // After a basic block was copied store all scalars that escape this block in
310 // their alloca.
311 generateScalarStores(Stmt, LTS, BBMap);
312 return CopyBB;
313}
314
315void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,
316 ValueMapT &BBMap, LoopToScevMapT &LTS,
317 isl_id_to_ast_expr *NewAccesses) {
318 EntryBB = &CopyBB->getParent()->getEntryBlock();
319
320 for (Instruction &Inst : *BB)
321 copyInstruction(Stmt, &Inst, BBMap, LTS, NewAccesses);
322}
323
324Value *BlockGenerator::getOrCreateAlloca(Value *ScalarBase,
325 ScalarAllocaMapTy &Map,
326 const char *NameExt) {
327 // If no alloca was found create one and insert it in the entry block.
328 if (!Map.count(ScalarBase)) {
329 auto *Ty = ScalarBase->getType();
330 auto NewAddr = new AllocaInst(Ty, ScalarBase->getName() + NameExt);
331 EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
332 NewAddr->insertBefore(&*EntryBB->getFirstInsertionPt());
333 Map[ScalarBase] = NewAddr;
334 }
335
336 auto Addr = Map[ScalarBase];
337
338 if (auto NewAddr = GlobalMap.lookup(Addr))
339 return NewAddr;
340
341 return Addr;
342}
343
344Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) {
345 if (Access.isPHIKind())
346 return getOrCreatePHIAlloca(Access.getBaseAddr());
347 else
348 return getOrCreateScalarAlloca(Access.getBaseAddr());
349}
350
351Value *BlockGenerator::getOrCreateAlloca(const ScopArrayInfo *Array) {
352 if (Array->isPHIKind())
353 return getOrCreatePHIAlloca(Array->getBasePtr());
354 else
355 return getOrCreateScalarAlloca(Array->getBasePtr());
356}
357
358Value *BlockGenerator::getOrCreateScalarAlloca(Value *ScalarBase) {
359 return getOrCreateAlloca(ScalarBase, ScalarMap, ".s2a");
360}
361
362Value *BlockGenerator::getOrCreatePHIAlloca(Value *ScalarBase) {
363 return getOrCreateAlloca(ScalarBase, PHIOpMap, ".phiops");
364}
365
366void BlockGenerator::handleOutsideUsers(const Scop &S, Instruction *Inst) {
367 // If there are escape users we get the alloca for this instruction and put it
368 // in the EscapeMap for later finalization. Lastly, if the instruction was
369 // copied multiple times we already did this and can exit.
370 if (EscapeMap.count(Inst))
371 return;
372
373 const auto &R = S.getRegion();
374 EscapeUserVectorTy EscapeUsers;
375 for (User *U : Inst->users()) {
376
377 // Non-instruction user will never escape.
378 Instruction *UI = dyn_cast<Instruction>(U);
379 if (!UI)
380 continue;
381
382 if (R.contains(UI))
383 continue;
384
385 EscapeUsers.push_back(UI);
386 }
387
388 // Exit if no escape uses were found.
389 if (EscapeUsers.empty())
390 return;
391
392 // Get or create an escape alloca for this instruction.
393 auto *ScalarAddr = getOrCreateScalarAlloca(Inst);
394
395 // Remember that this instruction has escape uses and the escape alloca.
396 EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers));
397}
398
399void BlockGenerator::generateScalarLoads(ScopStmt &Stmt, ValueMapT &BBMap) {
400 for (MemoryAccess *MA : Stmt) {
401 if (MA->isArrayKind() || MA->isWrite())
402 continue;
403
404 auto *Address = getOrCreateAlloca(*MA);
405 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 408, __PRETTY_FUNCTION__))
406 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 408, __PRETTY_FUNCTION__))
407 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 408, __PRETTY_FUNCTION__))
408 "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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 408, __PRETTY_FUNCTION__));
409 BBMap[MA->getBaseAddr()] =
410 Builder.CreateLoad(Address, Address->getName() + ".reload");
411 }
412}
413
414void BlockGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
415 ValueMapT &BBMap) {
416 Loop *L = LI.getLoopFor(Stmt.getBasicBlock());
417
418 assert(Stmt.isBlockStmt() && "Region statements need to use the "((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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 420, __PRETTY_FUNCTION__))
419 "generateScalarStores() function in the "((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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 420, __PRETTY_FUNCTION__))
420 "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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 420, __PRETTY_FUNCTION__));
421
422 for (MemoryAccess *MA : Stmt) {
423 if (MA->isArrayKind() || MA->isRead())
424 continue;
425
426 Value *Val = MA->getAccessValue();
427 if (MA->isAnyPHIKind()) {
428 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 430, __PRETTY_FUNCTION__))
429 "Block statements have exactly one exiting block, or 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 430, __PRETTY_FUNCTION__))
430 "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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 430, __PRETTY_FUNCTION__));
431 assert(std::all_of(MA->getIncoming().begin(), 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 435, __PRETTY_FUNCTION__))
432 [&](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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 435, __PRETTY_FUNCTION__))
433 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 435, __PRETTY_FUNCTION__))
434 }) &&((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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 435, __PRETTY_FUNCTION__))
435 "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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 435, __PRETTY_FUNCTION__));
436 Val = MA->getIncoming()[0].second;
437 }
438 auto *Address = getOrCreateAlloca(*MA);
439
440 Val = getNewValue(Stmt, Val, BBMap, LTS, L);
441 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 444, __PRETTY_FUNCTION__))
442 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 444, __PRETTY_FUNCTION__))
443 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 444, __PRETTY_FUNCTION__))
444 "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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 444, __PRETTY_FUNCTION__));
445 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 448, __PRETTY_FUNCTION__))
446 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 448, __PRETTY_FUNCTION__))
447 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 448, __PRETTY_FUNCTION__))
448 "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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 448, __PRETTY_FUNCTION__));
449 Builder.CreateStore(Val, Address);
450 }
451}
452
453void BlockGenerator::createScalarInitialization(Scop &S) {
454 Region &R = S.getRegion();
455 BasicBlock *ExitBB = R.getExit();
456
457 // The split block __just before__ the region and optimized region.
458 BasicBlock *SplitBB = R.getEnteringBlock();
459 BranchInst *SplitBBTerm = cast<BranchInst>(SplitBB->getTerminator());
460 assert(SplitBBTerm->getNumSuccessors() == 2 && "Bad region entering block!")((SplitBBTerm->getNumSuccessors() == 2 && "Bad region entering block!"
) ? static_cast<void> (0) : __assert_fail ("SplitBBTerm->getNumSuccessors() == 2 && \"Bad region entering block!\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 460, __PRETTY_FUNCTION__));
461
462 // Get the start block of the __optimized__ region.
463 BasicBlock *StartBB = SplitBBTerm->getSuccessor(0);
464 if (StartBB == R.getEntry())
465 StartBB = SplitBBTerm->getSuccessor(1);
466
467 Builder.SetInsertPoint(StartBB->getTerminator());
468
469 for (auto &Pair : S.arrays()) {
470 auto &Array = Pair.second;
471 if (Array->getNumberOfDimensions() != 0)
472 continue;
473 if (Array->isPHIKind()) {
474 // For PHI nodes, the only values we need to store are the ones that
475 // reach the PHI node from outside the region. In general there should
476 // only be one such incoming edge and this edge should enter through
477 // 'SplitBB'.
478 auto PHI = cast<PHINode>(Array->getBasePtr());
479
480 for (auto BI = PHI->block_begin(), BE = PHI->block_end(); BI != BE; BI++)
481 if (!R.contains(*BI) && *BI != SplitBB)
482 llvm_unreachable("Incoming edges from outside the scop should always "::llvm::llvm_unreachable_internal("Incoming edges from outside the scop should always "
"come from SplitBB", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 483)
483 "come from SplitBB")::llvm::llvm_unreachable_internal("Incoming edges from outside the scop should always "
"come from SplitBB", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 483);
484
485 int Idx = PHI->getBasicBlockIndex(SplitBB);
486 if (Idx < 0)
487 continue;
488
489 Value *ScalarValue = PHI->getIncomingValue(Idx);
490
491 Builder.CreateStore(ScalarValue, getOrCreatePHIAlloca(PHI));
492 continue;
493 }
494
495 auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());
496
497 if (Inst && R.contains(Inst))
498 continue;
499
500 // PHI nodes that are not marked as such in their SAI object are either exit
501 // PHI nodes we model as common scalars but without initialization, or
502 // incoming phi nodes that need to be initialized. Check if the first is the
503 // case for Inst and do not create and initialize memory if so.
504 if (auto *PHI = dyn_cast_or_null<PHINode>(Inst))
505 if (!S.hasSingleExitEdge() && PHI->getBasicBlockIndex(ExitBB) >= 0)
506 continue;
507
508 Builder.CreateStore(Array->getBasePtr(),
509 getOrCreateScalarAlloca(Array->getBasePtr()));
510 }
511}
512
513void BlockGenerator::createScalarFinalization(Region &R) {
514 // The exit block of the __unoptimized__ region.
515 BasicBlock *ExitBB = R.getExitingBlock();
516 // The merge block __just after__ the region and the optimized region.
517 BasicBlock *MergeBB = R.getExit();
518
519 // The exit block of the __optimized__ region.
520 BasicBlock *OptExitBB = *(pred_begin(MergeBB));
521 if (OptExitBB == ExitBB)
522 OptExitBB = *(++pred_begin(MergeBB));
523
524 Builder.SetInsertPoint(OptExitBB->getTerminator());
525 for (const auto &EscapeMapping : EscapeMap) {
526 // Extract the escaping instruction and the escaping users as well as the
527 // alloca the instruction was demoted to.
528 Instruction *EscapeInst = EscapeMapping.getFirst();
529 const auto &EscapeMappingValue = EscapeMapping.getSecond();
530 const EscapeUserVectorTy &EscapeUsers = EscapeMappingValue.second;
531 Value *ScalarAddr = EscapeMappingValue.first;
532
533 // Reload the demoted instruction in the optimized version of the SCoP.
534 Value *EscapeInstReload =
535 Builder.CreateLoad(ScalarAddr, EscapeInst->getName() + ".final_reload");
536 EscapeInstReload =
537 Builder.CreateBitOrPointerCast(EscapeInstReload, EscapeInst->getType());
538
539 // Create the merge PHI that merges the optimized and unoptimized version.
540 PHINode *MergePHI = PHINode::Create(EscapeInst->getType(), 2,
541 EscapeInst->getName() + ".merge");
542 MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());
543
544 // Add the respective values to the merge PHI.
545 MergePHI->addIncoming(EscapeInstReload, OptExitBB);
546 MergePHI->addIncoming(EscapeInst, ExitBB);
547
548 // The information of scalar evolution about the escaping instruction needs
549 // to be revoked so the new merged instruction will be used.
550 if (SE.isSCEVable(EscapeInst->getType()))
551 SE.forgetValue(EscapeInst);
552
553 // Replace all uses of the demoted instruction with the merge PHI.
554 for (Instruction *EUser : EscapeUsers)
555 EUser->replaceUsesOfWith(EscapeInst, MergePHI);
556 }
557}
558
559void BlockGenerator::findOutsideUsers(Scop &S) {
560 auto &R = S.getRegion();
561 for (auto &Pair : S.arrays()) {
562 auto &Array = Pair.second;
563
564 if (Array->getNumberOfDimensions() != 0)
565 continue;
566
567 if (Array->isPHIKind())
568 continue;
569
570 auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());
571
572 if (!Inst)
573 continue;
574
575 // Scop invariant hoisting moves some of the base pointers out of the scop.
576 // We can ignore these, as the invariant load hoisting already registers the
577 // relevant outside users.
578 if (!R.contains(Inst))
579 continue;
580
581 handleOutsideUsers(S, Inst);
582 }
583}
584
585void BlockGenerator::createExitPHINodeMerges(Scop &S) {
586 if (S.hasSingleExitEdge())
587 return;
588
589 Region &R = S.getRegion();
590
591 auto *ExitBB = R.getExitingBlock();
592 auto *MergeBB = R.getExit();
593 auto *AfterMergeBB = MergeBB->getSingleSuccessor();
594 BasicBlock *OptExitBB = *(pred_begin(MergeBB));
595 if (OptExitBB == ExitBB)
596 OptExitBB = *(++pred_begin(MergeBB));
597
598 Builder.SetInsertPoint(OptExitBB->getTerminator());
599
600 for (auto &Pair : S.arrays()) {
601 auto &SAI = Pair.second;
602 auto *Val = SAI->getBasePtr();
603
604 // Only Value-like scalars need a merge PHI. Exit block PHIs receive either
605 // the original PHI's value or the reloaded incoming values from the
606 // generated code. An llvm::Value is merged between the original code's
607 // value or the generated one.
608 if (!SAI->isValueKind() && !SAI->isExitPHIKind())
609 continue;
610
611 PHINode *PHI = dyn_cast<PHINode>(Val);
612 if (!PHI)
613 continue;
614
615 if (PHI->getParent() != AfterMergeBB)
616 continue;
617
618 std::string Name = PHI->getName();
619 Value *ScalarAddr = getOrCreateScalarAlloca(PHI);
620 Value *Reload = Builder.CreateLoad(ScalarAddr, Name + ".ph.final_reload");
621 Reload = Builder.CreateBitOrPointerCast(Reload, PHI->getType());
622 Value *OriginalValue = PHI->getIncomingValueForBlock(MergeBB);
623 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.\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 625, __PRETTY_FUNCTION__))
624 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.\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 625, __PRETTY_FUNCTION__))
625 "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.\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 625, __PRETTY_FUNCTION__));
626 auto *MergePHI = PHINode::Create(PHI->getType(), 2, Name + ".ph.merge");
627 MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());
628 MergePHI->addIncoming(Reload, OptExitBB);
629 MergePHI->addIncoming(OriginalValue, ExitBB);
630 int Idx = PHI->getBasicBlockIndex(MergeBB);
631 PHI->setIncomingValue(Idx, MergePHI);
632 }
633}
634
635void BlockGenerator::finalizeSCoP(Scop &S) {
636 findOutsideUsers(S);
637 createScalarInitialization(S);
638 createExitPHINodeMerges(S);
639 createScalarFinalization(S.getRegion());
640}
641
642VectorBlockGenerator::VectorBlockGenerator(BlockGenerator &BlockGen,
643 std::vector<LoopToScevMapT> &VLTS,
644 isl_map *Schedule)
645 : BlockGenerator(BlockGen), VLTS(VLTS), Schedule(Schedule) {
646 assert(Schedule && "No statement domain provided")((Schedule && "No statement domain provided") ? static_cast
<void> (0) : __assert_fail ("Schedule && \"No statement domain provided\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 646, __PRETTY_FUNCTION__));
647}
648
649Value *VectorBlockGenerator::getVectorValue(ScopStmt &Stmt, Value *Old,
650 ValueMapT &VectorMap,
651 VectorValueMapT &ScalarMaps,
652 Loop *L) {
653 if (Value *NewValue = VectorMap.lookup(Old))
654 return NewValue;
655
656 int Width = getVectorWidth();
657
658 Value *Vector = UndefValue::get(VectorType::get(Old->getType(), Width));
659
660 for (int Lane = 0; Lane < Width; Lane++)
661 Vector = Builder.CreateInsertElement(
662 Vector, getNewValue(Stmt, Old, ScalarMaps[Lane], VLTS[Lane], L),
663 Builder.getInt32(Lane));
664
665 VectorMap[Old] = Vector;
666
667 return Vector;
668}
669
670Type *VectorBlockGenerator::getVectorPtrTy(const Value *Val, int Width) {
671 PointerType *PointerTy = dyn_cast<PointerType>(Val->getType());
672 assert(PointerTy && "PointerType expected")((PointerTy && "PointerType expected") ? static_cast<
void> (0) : __assert_fail ("PointerTy && \"PointerType expected\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 672, __PRETTY_FUNCTION__));
673
674 Type *ScalarType = PointerTy->getElementType();
675 VectorType *VectorType = VectorType::get(ScalarType, Width);
676
677 return PointerType::getUnqual(VectorType);
678}
679
680Value *VectorBlockGenerator::generateStrideOneLoad(
681 ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps,
682 __isl_keep isl_id_to_ast_expr *NewAccesses, bool NegativeStride = false) {
683 unsigned VectorWidth = getVectorWidth();
684 auto *Pointer = Load->getPointerOperand();
685 Type *VectorPtrType = getVectorPtrTy(Pointer, VectorWidth);
686 unsigned Offset = NegativeStride ? VectorWidth - 1 : 0;
687
688 Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[Offset],
689 VLTS[Offset], NewAccesses);
690 Value *VectorPtr =
691 Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr");
692 LoadInst *VecLoad =
693 Builder.CreateLoad(VectorPtr, Load->getName() + "_p_vec_full");
694 if (!Aligned)
695 VecLoad->setAlignment(8);
696
697 if (NegativeStride) {
698 SmallVector<Constant *, 16> Indices;
699 for (int i = VectorWidth - 1; i >= 0; i--)
700 Indices.push_back(ConstantInt::get(Builder.getInt32Ty(), i));
701 Constant *SV = llvm::ConstantVector::get(Indices);
702 Value *RevVecLoad = Builder.CreateShuffleVector(
703 VecLoad, VecLoad, SV, Load->getName() + "_reverse");
704 return RevVecLoad;
705 }
706
707 return VecLoad;
708}
709
710Value *VectorBlockGenerator::generateStrideZeroLoad(
711 ScopStmt &Stmt, LoadInst *Load, ValueMapT &BBMap,
712 __isl_keep isl_id_to_ast_expr *NewAccesses) {
713 auto *Pointer = Load->getPointerOperand();
714 Type *VectorPtrType = getVectorPtrTy(Pointer, 1);
715 Value *NewPointer =
716 generateLocationAccessed(Stmt, Load, BBMap, VLTS[0], NewAccesses);
717 Value *VectorPtr = Builder.CreateBitCast(NewPointer, VectorPtrType,
718 Load->getName() + "_p_vec_p");
719 LoadInst *ScalarLoad =
720 Builder.CreateLoad(VectorPtr, Load->getName() + "_p_splat_one");
721
722 if (!Aligned)
723 ScalarLoad->setAlignment(8);
724
725 Constant *SplatVector = Constant::getNullValue(
726 VectorType::get(Builder.getInt32Ty(), getVectorWidth()));
727
728 Value *VectorLoad = Builder.CreateShuffleVector(
729 ScalarLoad, ScalarLoad, SplatVector, Load->getName() + "_p_splat");
730 return VectorLoad;
731}
732
733Value *VectorBlockGenerator::generateUnknownStrideLoad(
734 ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps,
735 __isl_keep isl_id_to_ast_expr *NewAccesses) {
736 int VectorWidth = getVectorWidth();
737 auto *Pointer = Load->getPointerOperand();
738 VectorType *VectorType = VectorType::get(
739 dyn_cast<PointerType>(Pointer->getType())->getElementType(), VectorWidth);
740
741 Value *Vector = UndefValue::get(VectorType);
742
743 for (int i = 0; i < VectorWidth; i++) {
744 Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[i],
745 VLTS[i], NewAccesses);
746 Value *ScalarLoad =
747 Builder.CreateLoad(NewPointer, Load->getName() + "_p_scalar_");
748 Vector = Builder.CreateInsertElement(
749 Vector, ScalarLoad, Builder.getInt32(i), Load->getName() + "_p_vec_");
750 }
751
752 return Vector;
753}
754
755void VectorBlockGenerator::generateLoad(
756 ScopStmt &Stmt, LoadInst *Load, ValueMapT &VectorMap,
757 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
758 if (Value *PreloadLoad = GlobalMap.lookup(Load)) {
759 VectorMap[Load] = Builder.CreateVectorSplat(getVectorWidth(), PreloadLoad,
760 Load->getName() + "_p");
761 return;
762 }
763
764 if (!VectorType::isValidElementType(Load->getType())) {
765 for (int i = 0; i < getVectorWidth(); i++)
766 ScalarMaps[i][Load] =
767 generateScalarLoad(Stmt, Load, ScalarMaps[i], VLTS[i], NewAccesses);
768 return;
769 }
770
771 const MemoryAccess &Access = Stmt.getArrayAccessFor(Load);
772
773 // Make sure we have scalar values available to access the pointer to
774 // the data location.
775 extractScalarValues(Load, VectorMap, ScalarMaps);
776
777 Value *NewLoad;
778 if (Access.isStrideZero(isl_map_copy(Schedule)))
779 NewLoad = generateStrideZeroLoad(Stmt, Load, ScalarMaps[0], NewAccesses);
780 else if (Access.isStrideOne(isl_map_copy(Schedule)))
781 NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses);
782 else if (Access.isStrideX(isl_map_copy(Schedule), -1))
783 NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses, true);
784 else
785 NewLoad = generateUnknownStrideLoad(Stmt, Load, ScalarMaps, NewAccesses);
786
787 VectorMap[Load] = NewLoad;
788}
789
790void VectorBlockGenerator::copyUnaryInst(ScopStmt &Stmt, UnaryInstruction *Inst,
791 ValueMapT &VectorMap,
792 VectorValueMapT &ScalarMaps) {
793 int VectorWidth = getVectorWidth();
794 Value *NewOperand = getVectorValue(Stmt, Inst->getOperand(0), VectorMap,
795 ScalarMaps, getLoopForStmt(Stmt));
796
797 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 797, __PRETTY_FUNCTION__));
798
799 const CastInst *Cast = dyn_cast<CastInst>(Inst);
800 VectorType *DestType = VectorType::get(Inst->getType(), VectorWidth);
801 VectorMap[Inst] = Builder.CreateCast(Cast->getOpcode(), NewOperand, DestType);
802}
803
804void VectorBlockGenerator::copyBinaryInst(ScopStmt &Stmt, BinaryOperator *Inst,
805 ValueMapT &VectorMap,
806 VectorValueMapT &ScalarMaps) {
807 Loop *L = getLoopForStmt(Stmt);
808 Value *OpZero = Inst->getOperand(0);
809 Value *OpOne = Inst->getOperand(1);
810
811 Value *NewOpZero, *NewOpOne;
812 NewOpZero = getVectorValue(Stmt, OpZero, VectorMap, ScalarMaps, L);
813 NewOpOne = getVectorValue(Stmt, OpOne, VectorMap, ScalarMaps, L);
814
815 Value *NewInst = Builder.CreateBinOp(Inst->getOpcode(), NewOpZero, NewOpOne,
816 Inst->getName() + "p_vec");
817 VectorMap[Inst] = NewInst;
818}
819
820void VectorBlockGenerator::copyStore(
821 ScopStmt &Stmt, StoreInst *Store, ValueMapT &VectorMap,
822 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
823 const MemoryAccess &Access = Stmt.getArrayAccessFor(Store);
824
825 auto *Pointer = Store->getPointerOperand();
826 Value *Vector = getVectorValue(Stmt, Store->getValueOperand(), VectorMap,
827 ScalarMaps, getLoopForStmt(Stmt));
828
829 // Make sure we have scalar values available to access the pointer to
830 // the data location.
831 extractScalarValues(Store, VectorMap, ScalarMaps);
832
833 if (Access.isStrideOne(isl_map_copy(Schedule))) {
834 Type *VectorPtrType = getVectorPtrTy(Pointer, getVectorWidth());
835 Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[0],
836 VLTS[0], NewAccesses);
837
838 Value *VectorPtr =
839 Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr");
840 StoreInst *Store = Builder.CreateStore(Vector, VectorPtr);
841
842 if (!Aligned)
843 Store->setAlignment(8);
844 } else {
845 for (unsigned i = 0; i < ScalarMaps.size(); i++) {
846 Value *Scalar = Builder.CreateExtractElement(Vector, Builder.getInt32(i));
847 Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[i],
848 VLTS[i], NewAccesses);
849 Builder.CreateStore(Scalar, NewPointer);
850 }
851 }
852}
853
854bool VectorBlockGenerator::hasVectorOperands(const Instruction *Inst,
855 ValueMapT &VectorMap) {
856 for (Value *Operand : Inst->operands())
857 if (VectorMap.count(Operand))
858 return true;
859 return false;
860}
861
862bool VectorBlockGenerator::extractScalarValues(const Instruction *Inst,
863 ValueMapT &VectorMap,
864 VectorValueMapT &ScalarMaps) {
865 bool HasVectorOperand = false;
866 int VectorWidth = getVectorWidth();
867
868 for (Value *Operand : Inst->operands()) {
869 ValueMapT::iterator VecOp = VectorMap.find(Operand);
870
871 if (VecOp == VectorMap.end())
872 continue;
873
874 HasVectorOperand = true;
875 Value *NewVector = VecOp->second;
876
877 for (int i = 0; i < VectorWidth; ++i) {
878 ValueMapT &SM = ScalarMaps[i];
879
880 // If there is one scalar extracted, all scalar elements should have
881 // already been extracted by the code here. So no need to check for the
882 // existance of all of them.
883 if (SM.count(Operand))
884 break;
885
886 SM[Operand] =
887 Builder.CreateExtractElement(NewVector, Builder.getInt32(i));
888 }
889 }
890
891 return HasVectorOperand;
892}
893
894void VectorBlockGenerator::copyInstScalarized(
895 ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap,
896 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
897 bool HasVectorOperand;
898 int VectorWidth = getVectorWidth();
899
900 HasVectorOperand = extractScalarValues(Inst, VectorMap, ScalarMaps);
901
902 for (int VectorLane = 0; VectorLane < getVectorWidth(); VectorLane++)
903 BlockGenerator::copyInstruction(Stmt, Inst, ScalarMaps[VectorLane],
904 VLTS[VectorLane], NewAccesses);
905
906 if (!VectorType::isValidElementType(Inst->getType()) || !HasVectorOperand)
907 return;
908
909 // Make the result available as vector value.
910 VectorType *VectorType = VectorType::get(Inst->getType(), VectorWidth);
911 Value *Vector = UndefValue::get(VectorType);
912
913 for (int i = 0; i < VectorWidth; i++)
914 Vector = Builder.CreateInsertElement(Vector, ScalarMaps[i][Inst],
915 Builder.getInt32(i));
916
917 VectorMap[Inst] = Vector;
918}
919
920int VectorBlockGenerator::getVectorWidth() { return VLTS.size(); }
921
922void VectorBlockGenerator::copyInstruction(
923 ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap,
924 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
925 // Terminator instructions control the control flow. They are explicitly
926 // expressed in the clast and do not need to be copied.
927 if (Inst->isTerminator())
928 return;
929
930 if (canSyntheziseInStmt(Stmt, Inst))
931 return;
932
933 if (auto *Load = dyn_cast<LoadInst>(Inst)) {
934 generateLoad(Stmt, Load, VectorMap, ScalarMaps, NewAccesses);
935 return;
936 }
937
938 if (hasVectorOperands(Inst, VectorMap)) {
939 if (auto *Store = dyn_cast<StoreInst>(Inst)) {
940 copyStore(Stmt, Store, VectorMap, ScalarMaps, NewAccesses);
941 return;
942 }
943
944 if (auto *Unary = dyn_cast<UnaryInstruction>(Inst)) {
945 copyUnaryInst(Stmt, Unary, VectorMap, ScalarMaps);
946 return;
947 }
948
949 if (auto *Binary = dyn_cast<BinaryOperator>(Inst)) {
950 copyBinaryInst(Stmt, Binary, VectorMap, ScalarMaps);
951 return;
952 }
953
954 // Falltrough: We generate scalar instructions, if we don't know how to
955 // generate vector code.
956 }
957
958 copyInstScalarized(Stmt, Inst, VectorMap, ScalarMaps, NewAccesses);
959}
960
961void VectorBlockGenerator::generateScalarVectorLoads(
962 ScopStmt &Stmt, ValueMapT &VectorBlockMap) {
963 for (MemoryAccess *MA : Stmt) {
964 if (MA->isArrayKind() || MA->isWrite())
965 continue;
966
967 auto *Address = getOrCreateAlloca(*MA);
968 Type *VectorPtrType = getVectorPtrTy(Address, 1);
969 Value *VectorPtr = Builder.CreateBitCast(Address, VectorPtrType,
970 Address->getName() + "_p_vec_p");
971 auto *Val = Builder.CreateLoad(VectorPtr, Address->getName() + ".reload");
972 Constant *SplatVector = Constant::getNullValue(
973 VectorType::get(Builder.getInt32Ty(), getVectorWidth()));
974
975 Value *VectorVal = Builder.CreateShuffleVector(
976 Val, Val, SplatVector, Address->getName() + "_p_splat");
977 VectorBlockMap[MA->getBaseAddr()] = VectorVal;
978 }
979}
980
981void VectorBlockGenerator::verifyNoScalarStores(ScopStmt &Stmt) {
982 for (MemoryAccess *MA : Stmt) {
983 if (MA->isArrayKind() || MA->isRead())
984 continue;
985
986 llvm_unreachable("Scalar stores not expected in vector loop")::llvm::llvm_unreachable_internal("Scalar stores not expected in vector loop"
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 986);
987 }
988}
989
990void VectorBlockGenerator::copyStmt(
991 ScopStmt &Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) {
992 assert(Stmt.isBlockStmt() && "TODO: Only block statements can be copied by "((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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 993, __PRETTY_FUNCTION__))
993 "the vector block 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 993, __PRETTY_FUNCTION__));
994
995 BasicBlock *BB = Stmt.getBasicBlock();
996 BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(),
997 &*Builder.GetInsertPoint(), &DT, &LI);
998 CopyBB->setName("polly.stmt." + BB->getName());
999 Builder.SetInsertPoint(&CopyBB->front());
1000
1001 // Create two maps that store the mapping from the original instructions of
1002 // the old basic block to their copies in the new basic block. Those maps
1003 // are basic block local.
1004 //
1005 // As vector code generation is supported there is one map for scalar values
1006 // and one for vector values.
1007 //
1008 // In case we just do scalar code generation, the vectorMap is not used and
1009 // the scalarMap has just one dimension, which contains the mapping.
1010 //
1011 // In case vector code generation is done, an instruction may either appear
1012 // in the vector map once (as it is calculating >vectorwidth< values at a
1013 // time. Or (if the values are calculated using scalar operations), it
1014 // appears once in every dimension of the scalarMap.
1015 VectorValueMapT ScalarBlockMap(getVectorWidth());
1016 ValueMapT VectorBlockMap;
1017
1018 generateScalarVectorLoads(Stmt, VectorBlockMap);
1019
1020 for (Instruction &Inst : *BB)
1021 copyInstruction(Stmt, &Inst, VectorBlockMap, ScalarBlockMap, NewAccesses);
1022
1023 verifyNoScalarStores(Stmt);
1024}
1025
1026BasicBlock *RegionGenerator::repairDominance(BasicBlock *BB,
1027 BasicBlock *BBCopy) {
1028
1029 BasicBlock *BBIDom = DT.getNode(BB)->getIDom()->getBlock();
1030 BasicBlock *BBCopyIDom = BlockMap.lookup(BBIDom);
1031
1032 if (BBCopyIDom)
1033 DT.changeImmediateDominator(BBCopy, BBCopyIDom);
1034
1035 return BBCopyIDom;
1036}
1037
1038// This is to determine whether an llvm::Value (defined in @p BB) is usable when
1039// leaving a subregion. The straight-forward DT.dominates(BB, R->getExitBlock())
1040// does not work in cases where the exit block has edges from outside the
1041// region. In that case the llvm::Value would never be usable in in the exit
1042// block. The RegionGenerator however creates an new exit block ('ExitBBCopy')
1043// for the subregion's exiting edges only. We need to determine whether an
1044// llvm::Value is usable in there. We do this by checking whether it dominates
1045// all exiting blocks individually.
1046static bool isDominatingSubregionExit(const DominatorTree &DT, Region *R,
1047 BasicBlock *BB) {
1048 for (auto ExitingBB : predecessors(R->getExit())) {
1049 // Check for non-subregion incoming edges.
1050 if (!R->contains(ExitingBB))
1051 continue;
1052
1053 if (!DT.dominates(BB, ExitingBB))
1054 return false;
1055 }
1056
1057 return true;
1058}
1059
1060// Find the direct dominator of the subregion's exit block if the subregion was
1061// simplified.
1062static BasicBlock *findExitDominator(DominatorTree &DT, Region *R) {
1063 BasicBlock *Common = nullptr;
1064 for (auto ExitingBB : predecessors(R->getExit())) {
1065 // Check for non-subregion incoming edges.
1066 if (!R->contains(ExitingBB))
1067 continue;
1068
1069 // First exiting edge.
1070 if (!Common) {
1071 Common = ExitingBB;
1072 continue;
1073 }
1074
1075 Common = DT.findNearestCommonDominator(Common, ExitingBB);
1076 }
1077
1078 assert(Common && R->contains(Common))((Common && R->contains(Common)) ? static_cast<
void> (0) : __assert_fail ("Common && R->contains(Common)"
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1078, __PRETTY_FUNCTION__));
1079 return Common;
1080}
1081
1082void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
1083 isl_id_to_ast_expr *IdToAstExp) {
1084 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1085, __PRETTY_FUNCTION__))
1085 "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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1085, __PRETTY_FUNCTION__));
1086
1087 Scop *S = Stmt.getParent();
1088
1089 // Forget all old mappings.
1090 BlockMap.clear();
1091 RegionMaps.clear();
1092 IncompletePHINodeMap.clear();
1093
1094 // Collection of all values related to this subregion.
1095 ValueMapT ValueMap;
1096
1097 // The region represented by the statement.
1098 Region *R = Stmt.getRegion();
1099
1100 // Create a dedicated entry for the region where we can reload all demoted
1101 // inputs.
1102 BasicBlock *EntryBB = R->getEntry();
1103 BasicBlock *EntryBBCopy = SplitBlock(Builder.GetInsertBlock(),
1104 &*Builder.GetInsertPoint(), &DT, &LI);
1105 EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry");
1106 Builder.SetInsertPoint(&EntryBBCopy->front());
1107
1108 ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy];
1109 generateScalarLoads(Stmt, EntryBBMap);
1110
1111 for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI)
1112 if (!R->contains(*PI))
1113 BlockMap[*PI] = EntryBBCopy;
1114
1115 // Determine the original exit block of this subregion. If it the exit block
1116 // is also the scop's exit, it it has been changed to polly.merge_new_and_old.
1117 // We move one block back to find the original block. This only happens if the
1118 // scop required simplification.
1119 // If the whole scop consists of only this non-affine region, then they share
1120 // the same Region object, such that we cannot change the exit of one and not
1121 // the other.
1122 BasicBlock *ExitBB = R->getExit();
1123 if (!S->hasSingleExitEdge() && ExitBB == S->getRegion().getExit())
1124 ExitBB = *(++pred_begin(ExitBB));
Value stored to 'ExitBB' is never read
1125
1126 // Iterate over all blocks in the region in a breadth-first search.
1127 std::deque<BasicBlock *> Blocks;
1128 SmallPtrSet<BasicBlock *, 8> SeenBlocks;
1129 Blocks.push_back(EntryBB);
1130 SeenBlocks.insert(EntryBB);
1131
1132 while (!Blocks.empty()) {
1133 BasicBlock *BB = Blocks.front();
1134 Blocks.pop_front();
1135
1136 // First split the block and update dominance information.
1137 BasicBlock *BBCopy = splitBB(BB);
1138 BasicBlock *BBCopyIDom = repairDominance(BB, BBCopy);
1139
1140 // Get the mapping for this block and initialize it with either the scalar
1141 // loads from the generated entering block (which dominates all blocks of
1142 // this subregion) or the maps of the immediate dominator, if part of the
1143 // subregion. The latter necessarily includes the former.
1144 ValueMapT *InitBBMap;
1145 if (BBCopyIDom) {
1146 assert(RegionMaps.count(BBCopyIDom))((RegionMaps.count(BBCopyIDom)) ? static_cast<void> (0)
: __assert_fail ("RegionMaps.count(BBCopyIDom)", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1146, __PRETTY_FUNCTION__));
1147 InitBBMap = &RegionMaps[BBCopyIDom];
1148 } else
1149 InitBBMap = &EntryBBMap;
1150 auto Inserted = RegionMaps.insert(std::make_pair(BBCopy, *InitBBMap));
1151 ValueMapT &RegionMap = Inserted.first->second;
1152
1153 // Copy the block with the BlockGenerator.
1154 Builder.SetInsertPoint(&BBCopy->front());
1155 copyBB(Stmt, BB, BBCopy, RegionMap, LTS, IdToAstExp);
1156
1157 // In order to remap PHI nodes we store also basic block mappings.
1158 BlockMap[BB] = BBCopy;
1159
1160 // Add values to incomplete PHI nodes waiting for this block to be copied.
1161 for (const PHINodePairTy &PHINodePair : IncompletePHINodeMap[BB])
1162 addOperandToPHI(Stmt, PHINodePair.first, PHINodePair.second, BB, LTS);
1163 IncompletePHINodeMap[BB].clear();
1164
1165 // And continue with new successors inside the region.
1166 for (auto SI = succ_begin(BB), SE = succ_end(BB); SI != SE; SI++)
1167 if (R->contains(*SI) && SeenBlocks.insert(*SI).second)
1168 Blocks.push_back(*SI);
1169
1170 // Remember value in case it is visible after this subregion.
1171 if (isDominatingSubregionExit(DT, R, BB))
1172 ValueMap.insert(RegionMap.begin(), RegionMap.end());
1173 }
1174
1175 // Now create a new dedicated region exit block and add it to the region map.
1176 BasicBlock *ExitBBCopy = SplitBlock(Builder.GetInsertBlock(),
1177 &*Builder.GetInsertPoint(), &DT, &LI);
1178 ExitBBCopy->setName("polly.stmt." + R->getExit()->getName() + ".exit");
1179 BlockMap[R->getExit()] = ExitBBCopy;
1180
1181 BasicBlock *ExitDomBBCopy = BlockMap.lookup(findExitDominator(DT, R));
1182 assert(ExitDomBBCopy && "Common exit dominator must be within region; at "((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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1183, __PRETTY_FUNCTION__))
1183 "least the entry node 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1183, __PRETTY_FUNCTION__));
1184 DT.changeImmediateDominator(ExitBBCopy, ExitDomBBCopy);
1185
1186 // As the block generator doesn't handle control flow we need to add the
1187 // region control flow by hand after all blocks have been copied.
1188 for (BasicBlock *BB : SeenBlocks) {
1189
1190 BasicBlock *BBCopy = BlockMap[BB];
1191 TerminatorInst *TI = BB->getTerminator();
1192 if (isa<UnreachableInst>(TI)) {
1193 while (!BBCopy->empty())
1194 BBCopy->begin()->eraseFromParent();
1195 new UnreachableInst(BBCopy->getContext(), BBCopy);
1196 continue;
1197 }
1198
1199 Instruction *BICopy = BBCopy->getTerminator();
1200
1201 ValueMapT &RegionMap = RegionMaps[BBCopy];
1202 RegionMap.insert(BlockMap.begin(), BlockMap.end());
1203
1204 Builder.SetInsertPoint(BICopy);
1205 copyInstScalar(Stmt, TI, RegionMap, LTS);
1206 BICopy->eraseFromParent();
1207 }
1208
1209 // Add counting PHI nodes to all loops in the region that can be used as
1210 // replacement for SCEVs refering to the old loop.
1211 for (BasicBlock *BB : SeenBlocks) {
1212 Loop *L = LI.getLoopFor(BB);
1213 if (L == nullptr || L->getHeader() != BB || !R->contains(L))
1214 continue;
1215
1216 BasicBlock *BBCopy = BlockMap[BB];
1217 Value *NullVal = Builder.getInt32(0);
1218 PHINode *LoopPHI =
1219 PHINode::Create(Builder.getInt32Ty(), 2, "polly.subregion.iv");
1220 Instruction *LoopPHIInc = BinaryOperator::CreateAdd(
1221 LoopPHI, Builder.getInt32(1), "polly.subregion.iv.inc");
1222 LoopPHI->insertBefore(&BBCopy->front());
1223 LoopPHIInc->insertBefore(BBCopy->getTerminator());
1224
1225 for (auto *PredBB : make_range(pred_begin(BB), pred_end(BB))) {
1226 if (!R->contains(PredBB))
1227 continue;
1228 if (L->contains(PredBB))
1229 LoopPHI->addIncoming(LoopPHIInc, BlockMap[PredBB]);
1230 else
1231 LoopPHI->addIncoming(NullVal, BlockMap[PredBB]);
1232 }
1233
1234 for (auto *PredBBCopy : make_range(pred_begin(BBCopy), pred_end(BBCopy)))
1235 if (LoopPHI->getBasicBlockIndex(PredBBCopy) < 0)
1236 LoopPHI->addIncoming(NullVal, PredBBCopy);
1237
1238 LTS[L] = SE.getUnknown(LoopPHI);
1239 }
1240
1241 // Continue generating code in the exit block.
1242 Builder.SetInsertPoint(&*ExitBBCopy->getFirstInsertionPt());
1243
1244 // Write values visible to other statements.
1245 generateScalarStores(Stmt, LTS, ValueMap);
1246 BlockMap.clear();
1247 RegionMaps.clear();
1248 IncompletePHINodeMap.clear();
1249}
1250
1251PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT &LTS,
1252 ValueMapT &BBMap, Loop *L) {
1253 ScopStmt *Stmt = MA->getStatement();
1254 Region *SubR = Stmt->getRegion();
1255 auto Incoming = MA->getIncoming();
1256
1257 PollyIRBuilder::InsertPointGuard IPGuard(Builder);
1258 PHINode *OrigPHI = cast<PHINode>(MA->getAccessInstruction());
1259 BasicBlock *NewSubregionExit = Builder.GetInsertBlock();
1260
1261 // This can happen if the subregion is simplified after the ScopStmts
1262 // have been created; simplification happens as part of CodeGeneration.
1263 if (OrigPHI->getParent() != SubR->getExit()) {
1264 BasicBlock *FormerExit = SubR->getExitingBlock();
1265 if (FormerExit)
1266 NewSubregionExit = BlockMap.lookup(FormerExit);
1267 }
1268
1269 PHINode *NewPHI = PHINode::Create(OrigPHI->getType(), Incoming.size(),
1270 "polly." + OrigPHI->getName(),
1271 NewSubregionExit->getFirstNonPHI());
1272
1273 // Add the incoming values to the PHI.
1274 for (auto &Pair : Incoming) {
1275 BasicBlock *OrigIncomingBlock = Pair.first;
1276 BasicBlock *NewIncomingBlock = BlockMap.lookup(OrigIncomingBlock);
1277 Builder.SetInsertPoint(NewIncomingBlock->getTerminator());
1278 assert(RegionMaps.count(NewIncomingBlock))((RegionMaps.count(NewIncomingBlock)) ? static_cast<void>
(0) : __assert_fail ("RegionMaps.count(NewIncomingBlock)", "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1278, __PRETTY_FUNCTION__));
1279 ValueMapT *LocalBBMap = &RegionMaps[NewIncomingBlock];
1280
1281 Value *OrigIncomingValue = Pair.second;
1282 Value *NewIncomingValue =
1283 getNewValue(*Stmt, OrigIncomingValue, *LocalBBMap, LTS, L);
1284 NewPHI->addIncoming(NewIncomingValue, NewIncomingBlock);
1285 }
1286
1287 return NewPHI;
1288}
1289
1290Value *RegionGenerator::getExitScalar(MemoryAccess *MA, LoopToScevMapT &LTS,
1291 ValueMapT &BBMap) {
1292 ScopStmt *Stmt = MA->getStatement();
1293
1294 // TODO: Add some test cases that ensure this is really the right choice.
1295 Loop *L = LI.getLoopFor(Stmt->getRegion()->getExit());
1296
1297 if (MA->isAnyPHIKind()) {
1298 auto Incoming = MA->getIncoming();
1299 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1300, __PRETTY_FUNCTION__))
1300 "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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1300, __PRETTY_FUNCTION__));
1301
1302 // If there is only one incoming value, we do not need to create a PHI.
1303 if (Incoming.size() == 1) {
1304 Value *OldVal = Incoming[0].second;
1305 return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
1306 }
1307
1308 return buildExitPHI(MA, LTS, BBMap, L);
1309 }
1310
1311 // MK_Value accesses leaving the subregion must dominate the exit block; just
1312 // pass the copied value
1313 Value *OldVal = MA->getAccessValue();
1314 return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
1315}
1316
1317void RegionGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
1318 ValueMapT &BBMap) {
1319 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1321, __PRETTY_FUNCTION__))
1320 "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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1321, __PRETTY_FUNCTION__))
1321 "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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1321, __PRETTY_FUNCTION__));
1322
1323 for (MemoryAccess *MA : Stmt) {
1324 if (MA->isArrayKind() || MA->isRead())
1325 continue;
1326
1327 Value *NewVal = getExitScalar(MA, LTS, BBMap);
1328 Value *Address = getOrCreateAlloca(*MA);
1329 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1332, __PRETTY_FUNCTION__))
1330 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1332, __PRETTY_FUNCTION__))
1331 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1332, __PRETTY_FUNCTION__))
1332 "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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1332, __PRETTY_FUNCTION__));
1333 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1336, __PRETTY_FUNCTION__))
1334 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1336, __PRETTY_FUNCTION__))
1335 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1336, __PRETTY_FUNCTION__))
1336 "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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1336, __PRETTY_FUNCTION__));
1337 Builder.CreateStore(NewVal, Address);
1338 }
1339}
1340
1341void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, const PHINode *PHI,
1342 PHINode *PHICopy, BasicBlock *IncomingBB,
1343 LoopToScevMapT &LTS) {
1344 Region *StmtR = Stmt.getRegion();
1345
1346 // If the incoming block was not yet copied mark this PHI as incomplete.
1347 // Once the block will be copied the incoming value will be added.
1348 BasicBlock *BBCopy = BlockMap[IncomingBB];
1349 if (!BBCopy) {
1350 assert(StmtR->contains(IncomingBB) &&((StmtR->contains(IncomingBB) && "Bad incoming block for PHI in non-affine region"
) ? static_cast<void> (0) : __assert_fail ("StmtR->contains(IncomingBB) && \"Bad incoming block for PHI in non-affine region\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1351, __PRETTY_FUNCTION__))
1351 "Bad incoming block for PHI in non-affine region")((StmtR->contains(IncomingBB) && "Bad incoming block for PHI in non-affine region"
) ? static_cast<void> (0) : __assert_fail ("StmtR->contains(IncomingBB) && \"Bad incoming block for PHI in non-affine region\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1351, __PRETTY_FUNCTION__));
1352 IncompletePHINodeMap[IncomingBB].push_back(std::make_pair(PHI, PHICopy));
1353 return;
1354 }
1355
1356 Value *OpCopy = nullptr;
1357 if (StmtR->contains(IncomingBB)) {
1358 assert(RegionMaps.count(BBCopy) &&((RegionMaps.count(BBCopy) && "Incoming PHI block did not have a BBMap"
) ? static_cast<void> (0) : __assert_fail ("RegionMaps.count(BBCopy) && \"Incoming PHI block did not have a BBMap\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1359, __PRETTY_FUNCTION__))
1359 "Incoming PHI block did not have a BBMap")((RegionMaps.count(BBCopy) && "Incoming PHI block did not have a BBMap"
) ? static_cast<void> (0) : __assert_fail ("RegionMaps.count(BBCopy) && \"Incoming PHI block did not have a BBMap\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1359, __PRETTY_FUNCTION__));
1360 ValueMapT &BBCopyMap = RegionMaps[BBCopy];
1361
1362 Value *Op = PHI->getIncomingValueForBlock(IncomingBB);
1363
1364 // If the current insert block is different from the PHIs incoming block
1365 // change it, otherwise do not.
1366 auto IP = Builder.GetInsertPoint();
1367 if (IP->getParent() != BBCopy)
1368 Builder.SetInsertPoint(BBCopy->getTerminator());
1369 OpCopy = getNewValue(Stmt, Op, BBCopyMap, LTS, getLoopForStmt(Stmt));
1370 if (IP->getParent() != BBCopy)
1371 Builder.SetInsertPoint(&*IP);
1372 } else {
1373
1374 if (PHICopy->getBasicBlockIndex(BBCopy) >= 0)
1375 return;
1376
1377 Value *PHIOpAddr = getOrCreatePHIAlloca(const_cast<PHINode *>(PHI));
1378 OpCopy = new LoadInst(PHIOpAddr, PHIOpAddr->getName() + ".reload",
1379 BlockMap[IncomingBB]->getTerminator());
1380 }
1381
1382 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\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1382, __PRETTY_FUNCTION__));
1383 assert(BBCopy && "Incoming PHI block was not copied properly")((BBCopy && "Incoming PHI block was not copied properly"
) ? static_cast<void> (0) : __assert_fail ("BBCopy && \"Incoming PHI block was not copied properly\""
, "/tmp/buildd/llvm-toolchain-snapshot-3.9~svn270412/tools/polly/lib/CodeGen/BlockGenerators.cpp"
, 1383, __PRETTY_FUNCTION__));
1384 PHICopy->addIncoming(OpCopy, BBCopy);
1385}
1386
1387void RegionGenerator::copyPHIInstruction(ScopStmt &Stmt, PHINode *PHI,
1388 ValueMapT &BBMap,
1389 LoopToScevMapT &LTS) {
1390 unsigned NumIncoming = PHI->getNumIncomingValues();
1391 PHINode *PHICopy =
1392 Builder.CreatePHI(PHI->getType(), NumIncoming, "polly." + PHI->getName());
1393 PHICopy->moveBefore(PHICopy->getParent()->getFirstNonPHI());
1394 BBMap[PHI] = PHICopy;
1395
1396 for (unsigned u = 0; u < NumIncoming; u++)
1397 addOperandToPHI(Stmt, PHI, PHICopy, PHI->getIncomingBlock(u), LTS);
1398}