blob: 79d6d0b8464d7f88705586f18056cff8b79504ac [file] [log] [blame]
Hongbin Zheng3b11a162012-04-25 13:16:49 +00001//===--- 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
Hongbin Zheng8a846612012-04-25 13:18:28 +000016#include "polly/CodeGen/BlockGenerators.h"
Tobias Grosser83628182013-05-07 08:11:54 +000017#include "polly/CodeGen/CodeGeneration.h"
Johannes Doerferta63b2572014-08-03 01:51:59 +000018#include "polly/CodeGen/IslExprBuilder.h"
Tobias Grosser86bc93a2015-09-06 08:47:57 +000019#include "polly/CodeGen/RuntimeDebugBuilder.h"
Tobias Grosser637bd632013-05-07 07:31:10 +000020#include "polly/Options.h"
Tobias Grosser5624d3c2015-12-21 12:38:56 +000021#include "polly/ScopInfo.h"
Hongbin Zheng3b11a162012-04-25 13:16:49 +000022#include "polly/Support/GICHelper.h"
Sebastian Pop97cb8132013-03-18 20:21:13 +000023#include "polly/Support/SCEVValidator.h"
Tobias Grosserecfe21b2013-03-20 18:03:18 +000024#include "polly/Support/ScopHelper.h"
Tobias Grossere71c6ab2012-04-27 16:36:14 +000025#include "llvm/Analysis/LoopInfo.h"
Johannes Doerfertf32d6512015-03-01 18:45:58 +000026#include "llvm/Analysis/RegionInfo.h"
Tobias Grossere71c6ab2012-04-27 16:36:14 +000027#include "llvm/Analysis/ScalarEvolution.h"
Tobias Grosser030237d2014-02-21 15:06:05 +000028#include "llvm/IR/IntrinsicInst.h"
Tobias Grosserc9895062015-03-10 15:24:33 +000029#include "llvm/IR/Module.h"
Hongbin Zheng3b11a162012-04-25 13:16:49 +000030#include "llvm/Transforms/Utils/BasicBlockUtils.h"
Tobias Grosser1b9d25a2015-09-27 11:17:22 +000031#include "llvm/Transforms/Utils/Local.h"
Johannes Doerfertf32d6512015-03-01 18:45:58 +000032#include "isl/aff.h"
33#include "isl/ast.h"
Johannes Doerfertf32d6512015-03-01 18:45:58 +000034#include "isl/ast_build.h"
Tobias Grosserba0d0922015-05-09 09:13:42 +000035#include "isl/set.h"
Johannes Doerfertf32d6512015-03-01 18:45:58 +000036#include <deque>
37
Hongbin Zheng3b11a162012-04-25 13:16:49 +000038using namespace llvm;
39using namespace polly;
40
Tobias Grosser878aba42014-10-22 23:22:41 +000041static 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));
Hongbin Zheng3b11a162012-04-25 13:16:49 +000045
Tobias Grosser86bc93a2015-09-06 08:47:57 +000046static 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
Johannes Doerfertb4f08eb2015-02-23 13:51:35 +000051BlockGenerator::BlockGenerator(PollyIRBuilder &B, LoopInfo &LI,
52 ScalarEvolution &SE, DominatorTree &DT,
Johannes Doerfertecff11d2015-05-22 23:43:58 +000053 ScalarAllocaMapTy &ScalarMap,
54 ScalarAllocaMapTy &PHIOpMap,
55 EscapeUsersAllocaMapTy &EscapeMap,
Tobias Grosserf4bb7a62015-10-04 10:18:32 +000056 ValueMapT &GlobalMap,
Johannes Doerfertb4f08eb2015-02-23 13:51:35 +000057 IslExprBuilder *ExprBuilder)
Johannes Doerfertecff11d2015-05-22 23:43:58 +000058 : Builder(B), LI(LI), SE(SE), ExprBuilder(ExprBuilder), DT(DT),
59 EntryBB(nullptr), PHIOpMap(PHIOpMap), ScalarMap(ScalarMap),
Tobias Grosserbc132602015-09-05 09:56:54 +000060 EscapeMap(EscapeMap), GlobalMap(GlobalMap) {}
Tobias Grossere71c6ab2012-04-27 16:36:14 +000061
Tobias Grosser2f1acac2015-10-04 10:18:45 +000062Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old,
Tobias Grosser33cb9f92015-09-30 11:56:19 +000063 ValueMapT &BBMap,
64 LoopToScevMapT &LTS,
65 Loop *L) const {
Johannes Doerfert42df8d12015-12-22 19:08:01 +000066 if (!SE.isSCEVable(Old->getType()))
67 return nullptr;
Johannes Doerferte69e1142015-08-18 11:56:00 +000068
Johannes Doerfert42df8d12015-12-22 19:08:01 +000069 const SCEV *Scev = SE.getSCEVAtScope(Old, L);
70 if (!Scev)
71 return nullptr;
Johannes Doerferte69e1142015-08-18 11:56:00 +000072
Johannes Doerfert42df8d12015-12-22 19:08:01 +000073 if (isa<SCEVCouldNotCompute>(Scev))
74 return nullptr;
Tobias Grossere71c6ab2012-04-27 16:36:14 +000075
Johannes Doerfert42df8d12015-12-22 19:08:01 +000076 const SCEV *NewScev = apply(Scev, LTS, SE);
77 ValueMapT VTV;
78 VTV.insert(BBMap.begin(), BBMap.end());
79 VTV.insert(GlobalMap.begin(), GlobalMap.end());
Tobias Grossere71c6ab2012-04-27 16:36:14 +000080
Johannes Doerfert42df8d12015-12-22 19:08:01 +000081 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() &&
87 "Only instructions can be insert points for SCEVExpander");
88 Value *Expanded =
89 expandCodeFor(S, SE, DL, "polly", NewScev, Old->getType(), &*IP, &VTV);
90
91 BBMap[Old] = Expanded;
92 return Expanded;
Tobias Grosser33cb9f92015-09-30 11:56:19 +000093}
94
Tobias Grosser2f1acac2015-10-04 10:18:45 +000095Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
96 LoopToScevMapT &LTS, Loop *L) const {
Tobias Grosser9bd0dad2015-12-14 16:19:59 +000097 // Constants that do not reference any named value can always remain
Michael Kruse5bbc0e12015-12-14 23:41:32 +000098 // unchanged. Handle them early to avoid expensive map lookups. We do not take
Tobias Grosser9bd0dad2015-12-14 16:19:59 +000099 // 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))
Tobias Grosser6f764bb2015-12-14 16:19:54 +0000103 return Old;
Tobias Grosser33cb9f92015-09-30 11:56:19 +0000104
Johannes Doerfert28f8ac12015-12-22 19:08:24 +0000105 // Inline asm is like a constant to us.
106 if (isa<InlineAsm>(Old))
107 return Old;
108
Tobias Grosser33cb9f92015-09-30 11:56:19 +0000109 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
Tobias Grosser16371ac2014-11-05 20:48:56 +0000125 // A scop-constant value defined by a global or a function parameter.
126 if (isa<GlobalValue>(Old) || isa<Argument>(Old))
Tobias Grosser6f764bb2015-12-14 16:19:54 +0000127 return Old;
Tobias Grosser16371ac2014-11-05 20:48:56 +0000128
129 // A scop-constant value defined by an instruction executed outside the scop.
130 if (const Instruction *Inst = dyn_cast<Instruction>(Old))
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000131 if (!Stmt.getParent()->getRegion().contains(Inst->getParent()))
Tobias Grosser6f764bb2015-12-14 16:19:54 +0000132 return Old;
Tobias Grosser16371ac2014-11-05 20:48:56 +0000133
134 // The scalar dependence is neither available nor SCEVCodegenable.
Hongbin Zheng5b463ce2013-07-25 09:12:07 +0000135 llvm_unreachable("Unexpected scalar dependence in region!");
Tobias Grosser5a56cbf2014-04-16 07:33:47 +0000136 return nullptr;
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000137}
138
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000139void BlockGenerator::copyInstScalar(ScopStmt &Stmt, Instruction *Inst,
Tobias Grosserbc132602015-09-05 09:56:54 +0000140 ValueMapT &BBMap, LoopToScevMapT &LTS) {
Tobias Grosser030237d2014-02-21 15:06:05 +0000141 // 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
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000147 Instruction *NewInst = Inst->clone();
148
149 // Replace old operands with the new ones.
Tobias Grosser91f5b262014-06-04 08:06:40 +0000150 for (Value *OldOperand : Inst->operands()) {
Tobias Grosserbc132602015-09-05 09:56:54 +0000151 Value *NewOperand =
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000152 getNewValue(Stmt, OldOperand, BBMap, LTS, getLoopForStmt(Stmt));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000153
154 if (!NewOperand) {
Tobias Grosserc14582f2013-02-05 18:01:29 +0000155 assert(!isa<StoreInst>(NewInst) &&
156 "Store instructions are always needed!");
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000157 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
Michael Kruse70131d32016-01-27 17:09:17 +0000171Value *
172BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,
173 ValueMapT &BBMap, LoopToScevMapT &LTS,
174 isl_id_to_ast_expr *NewAccesses) {
Tobias Grosser09214772015-12-15 23:49:53 +0000175 const MemoryAccess &MA = Stmt.getArrayAccessFor(Inst);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000176
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000177 isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(NewAccesses, MA.getId());
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000178
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000179 if (AccessExpr) {
180 AccessExpr = isl_ast_expr_address_of(AccessExpr);
Tobias Grosser98b3ee52015-09-29 06:44:38 +0000181 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
Tobias Grosserd840fc72016-02-04 13:18:42 +0000191 if (OldPtrTy != NewPtrTy)
Tobias Grosser98b3ee52015-09-29 06:44:38 +0000192 Address = Builder.CreateBitOrPointerCast(Address, OldPtrTy);
Tobias Grosser98b3ee52015-09-29 06:44:38 +0000193 return Address;
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000194 }
195
Michael Kruse70131d32016-01-27 17:09:17 +0000196 return getNewValue(Stmt, Inst.getPointerOperand(), BBMap, LTS,
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000197 getLoopForStmt(Stmt));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000198}
199
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000200Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const {
Michael Kruse375cb5f2016-02-24 22:08:24 +0000201 auto *StmtBB = Stmt.getEntryBlock();
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000202 return LI.getLoopFor(StmtBB);
Tobias Grosser369430f2013-03-22 23:42:53 +0000203}
204
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000205Value *BlockGenerator::generateScalarLoad(ScopStmt &Stmt, LoadInst *Load,
Tobias Grosserbc132602015-09-05 09:56:54 +0000206 ValueMapT &BBMap, LoopToScevMapT &LTS,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000207 isl_id_to_ast_expr *NewAccesses) {
Johannes Doerfertc1db67e2015-09-29 23:47:21 +0000208 if (Value *PreloadLoad = GlobalMap.lookup(Load))
209 return PreloadLoad;
210
Tobias Grosserbc132602015-09-05 09:56:54 +0000211 Value *NewPointer =
Michael Kruse70131d32016-01-27 17:09:17 +0000212 generateLocationAccessed(Stmt, Load, BBMap, LTS, NewAccesses);
Johannes Doerfert87901452014-10-02 16:22:19 +0000213 Value *ScalarLoad = Builder.CreateAlignedLoad(
214 NewPointer, Load->getAlignment(), Load->getName() + "_p_scalar_");
Tobias Grosser86bc93a2015-09-06 08:47:57 +0000215
216 if (DebugPrinting)
217 RuntimeDebugBuilder::createCPUPrinter(Builder, "Load from ", NewPointer,
218 ": ", ScalarLoad, "\n");
219
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000220 return ScalarLoad;
221}
222
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000223void BlockGenerator::generateScalarStore(ScopStmt &Stmt, StoreInst *Store,
Tobias Grosserbc132602015-09-05 09:56:54 +0000224 ValueMapT &BBMap, LoopToScevMapT &LTS,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000225 isl_id_to_ast_expr *NewAccesses) {
Tobias Grosserbc132602015-09-05 09:56:54 +0000226 Value *NewPointer =
Michael Kruse70131d32016-01-27 17:09:17 +0000227 generateLocationAccessed(Stmt, Store, BBMap, LTS, NewAccesses);
Tobias Grosserbc132602015-09-05 09:56:54 +0000228 Value *ValueOperand = getNewValue(Stmt, Store->getValueOperand(), BBMap, LTS,
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000229 getLoopForStmt(Stmt));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000230
Tobias Grosser86bc93a2015-09-06 08:47:57 +0000231 if (DebugPrinting)
232 RuntimeDebugBuilder::createCPUPrinter(Builder, "Store to ", NewPointer,
233 ": ", ValueOperand, "\n");
234
Tobias Grosserc186ac72015-08-11 08:13:15 +0000235 Builder.CreateAlignedStore(ValueOperand, NewPointer, Store->getAlignment());
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000236}
237
Johannes Doerfert5dced262015-12-22 19:08:49 +0000238bool BlockGenerator::canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst) {
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000239 Loop *L = getLoopForStmt(Stmt);
Johannes Doerfert5dced262015-12-22 19:08:49 +0000240 return (Stmt.isBlockStmt() || !Stmt.getRegion()->contains(L)) &&
Michael Krusec7e0d9c2016-03-01 21:44:06 +0000241 canSynthesize(Inst, &LI, &SE, &Stmt.getParent()->getRegion(), L);
Johannes Doerfert5dced262015-12-22 19:08:49 +0000242}
243
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000244void BlockGenerator::copyInstruction(ScopStmt &Stmt, Instruction *Inst,
Tobias Grosserbc132602015-09-05 09:56:54 +0000245 ValueMapT &BBMap, LoopToScevMapT &LTS,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000246 isl_id_to_ast_expr *NewAccesses) {
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000247 // 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
Johannes Doerfert5dced262015-12-22 19:08:49 +0000252 // Synthesizable statements will be generated on-demand.
253 if (canSyntheziseInStmt(Stmt, Inst))
Tobias Grossere71c6ab2012-04-27 16:36:14 +0000254 return;
255
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000256 if (auto *Load = dyn_cast<LoadInst>(Inst)) {
Tobias Grosserbc132602015-09-05 09:56:54 +0000257 Value *NewLoad = generateScalarLoad(Stmt, Load, BBMap, LTS, NewAccesses);
Sebastian Pop3d94fed2013-05-24 18:46:02 +0000258 // Compute NewLoad before its insertion in BBMap to make the insertion
259 // deterministic.
Sebastian Pop753d43f2013-05-24 17:16:02 +0000260 BBMap[Load] = NewLoad;
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000261 return;
262 }
263
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000264 if (auto *Store = dyn_cast<StoreInst>(Inst)) {
Tobias Grosserbc132602015-09-05 09:56:54 +0000265 generateScalarStore(Stmt, Store, BBMap, LTS, NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000266 return;
267 }
268
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000269 if (auto *PHI = dyn_cast<PHINode>(Inst)) {
Tobias Grosserbc132602015-09-05 09:56:54 +0000270 copyPHIInstruction(Stmt, PHI, BBMap, LTS);
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000271 return;
272 }
273
Johannes Doerfert3f500fa2015-01-25 18:07:30 +0000274 // 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.
Tobias Grosser9c0ffe32015-08-30 16:57:15 +0000276 if (isIgnoredIntrinsic(Inst))
277 return;
Johannes Doerfert3f500fa2015-01-25 18:07:30 +0000278
Tobias Grosserbc132602015-09-05 09:56:54 +0000279 copyInstScalar(Stmt, Inst, BBMap, LTS);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000280}
281
Tobias Grosserbc132602015-09-05 09:56:54 +0000282void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000283 isl_id_to_ast_expr *NewAccesses) {
Johannes Doerfert275a1752015-02-24 16:16:32 +0000284 assert(Stmt.isBlockStmt() &&
285 "Only block statements can be copied by the block generator");
286
287 ValueMapT BBMap;
288
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000289 BasicBlock *BB = Stmt.getBasicBlock();
Tobias Grosserbc132602015-09-05 09:56:54 +0000290 copyBB(Stmt, BB, BBMap, LTS, NewAccesses);
Johannes Doerfert275a1752015-02-24 16:16:32 +0000291}
292
Johannes Doerfert514f6ef2015-02-27 18:29:04 +0000293BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) {
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +0000294 BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(),
295 &*Builder.GetInsertPoint(), &DT, &LI);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000296 CopyBB->setName("polly.stmt." + BB->getName());
Johannes Doerfert514f6ef2015-02-27 18:29:04 +0000297 return CopyBB;
298}
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000299
Johannes Doerfert514f6ef2015-02-27 18:29:04 +0000300BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,
Tobias Grosserbc132602015-09-05 09:56:54 +0000301 ValueMapT &BBMap, LoopToScevMapT &LTS,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000302 isl_id_to_ast_expr *NewAccesses) {
Johannes Doerfert514f6ef2015-02-27 18:29:04 +0000303 BasicBlock *CopyBB = splitBB(BB);
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +0000304 Builder.SetInsertPoint(&CopyBB->front());
Michael Kruse225f0d12015-10-17 21:36:00 +0000305 generateScalarLoads(Stmt, BBMap);
306
Tobias Grosserbc132602015-09-05 09:56:54 +0000307 copyBB(Stmt, BB, CopyBB, BBMap, LTS, NewAccesses);
Michael Kruse225f0d12015-10-17 21:36:00 +0000308
309 // After a basic block was copied store all scalars that escape this block in
310 // their alloca.
311 generateScalarStores(Stmt, LTS, BBMap);
Johannes Doerfert514f6ef2015-02-27 18:29:04 +0000312 return CopyBB;
313}
314
315void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,
Tobias Grosserbc132602015-09-05 09:56:54 +0000316 ValueMapT &BBMap, LoopToScevMapT &LTS,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000317 isl_id_to_ast_expr *NewAccesses) {
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000318 EntryBB = &CopyBB->getParent()->getEntryBlock();
319
Tobias Grosser91f5b262014-06-04 08:06:40 +0000320 for (Instruction &Inst : *BB)
Tobias Grosserbc132602015-09-05 09:56:54 +0000321 copyInstruction(Stmt, &Inst, BBMap, LTS, NewAccesses);
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000322}
323
Tobias Grosser64c0ff42015-08-31 05:52:24 +0000324Value *BlockGenerator::getOrCreateAlloca(Value *ScalarBase,
325 ScalarAllocaMapTy &Map,
Tobias Grosser64c0ff42015-08-31 05:52:24 +0000326 const char *NameExt) {
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000327 // If no alloca was found create one and insert it in the entry block.
Tobias Grossere9cb5a02015-10-03 17:19:49 +0000328 if (!Map.count(ScalarBase)) {
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000329 auto *Ty = ScalarBase->getType();
Tobias Grosserb09455d2015-09-18 06:01:11 +0000330 auto NewAddr = new AllocaInst(Ty, ScalarBase->getName() + NameExt);
Tobias Grosser64c0ff42015-08-31 05:52:24 +0000331 EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +0000332 NewAddr->insertBefore(&*EntryBB->getFirstInsertionPt());
Tobias Grossere9cb5a02015-10-03 17:19:49 +0000333 Map[ScalarBase] = NewAddr;
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000334 }
335
Tobias Grossere9cb5a02015-10-03 17:19:49 +0000336 auto Addr = Map[ScalarBase];
337
Tobias Grosser5c7f16b2016-01-24 14:16:59 +0000338 if (auto NewAddr = GlobalMap.lookup(Addr))
339 return NewAddr;
Tobias Grosser64c0ff42015-08-31 05:52:24 +0000340
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000341 return Addr;
342}
343
Johannes Doerfert800e17a2016-02-02 14:16:01 +0000344Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) {
Tobias Grossera535dff2015-12-13 19:59:01 +0000345 if (Access.isPHIKind())
Tobias Grosserb8d27aa2015-10-18 00:51:13 +0000346 return getOrCreatePHIAlloca(Access.getBaseAddr());
347 else
348 return getOrCreateScalarAlloca(Access.getBaseAddr());
Tobias Grossera4f09882015-10-17 22:16:00 +0000349}
350
351Value *BlockGenerator::getOrCreateAlloca(const ScopArrayInfo *Array) {
Tobias Grossera535dff2015-12-13 19:59:01 +0000352 if (Array->isPHIKind())
Tobias Grossera4f09882015-10-17 22:16:00 +0000353 return getOrCreatePHIAlloca(Array->getBasePtr());
Tobias Grosserf8d55f72015-08-29 18:12:03 +0000354 else
Tobias Grossera4f09882015-10-17 22:16:00 +0000355 return getOrCreateScalarAlloca(Array->getBasePtr());
Tobias Grosserf8d55f72015-08-29 18:12:03 +0000356}
357
Tobias Grosserbc132602015-09-05 09:56:54 +0000358Value *BlockGenerator::getOrCreateScalarAlloca(Value *ScalarBase) {
359 return getOrCreateAlloca(ScalarBase, ScalarMap, ".s2a");
Tobias Grosserb79a67d2015-08-28 08:23:35 +0000360}
361
Tobias Grosserbc132602015-09-05 09:56:54 +0000362Value *BlockGenerator::getOrCreatePHIAlloca(Value *ScalarBase) {
363 return getOrCreateAlloca(ScalarBase, PHIOpMap, ".phiops");
Tobias Grosserb79a67d2015-08-28 08:23:35 +0000364}
365
Johannes Doerfert38a012c2016-05-23 09:14:07 +0000366void BlockGenerator::handleOutsideUsers(const Scop &S, Instruction *Inst) {
Tobias Grosser29854002015-08-30 15:03:59 +0000367 // 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.
Michael Kruseacb6ade2015-08-18 17:25:48 +0000370 if (EscapeMap.count(Inst))
371 return;
Johannes Doerferte69e1142015-08-18 11:56:00 +0000372
Johannes Doerfert38a012c2016-05-23 09:14:07 +0000373 const auto &R = S.getRegion();
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000374 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
Johannes Doerfertddb83d02015-08-16 08:35:40 +0000382 if (R.contains(UI))
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000383 continue;
384
385 EscapeUsers.push_back(UI);
386 }
387
388 // Exit if no escape uses were found.
389 if (EscapeUsers.empty())
390 return;
391
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000392 // Get or create an escape alloca for this instruction.
Johannes Doerfert38a012c2016-05-23 09:14:07 +0000393 auto *ScalarAddr = getOrCreateScalarAlloca(Inst);
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000394
395 // Remember that this instruction has escape uses and the escape alloca.
396 EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers));
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000397}
398
Michael Kruse225f0d12015-10-17 21:36:00 +0000399void BlockGenerator::generateScalarLoads(ScopStmt &Stmt, ValueMapT &BBMap) {
400 for (MemoryAccess *MA : Stmt) {
Tobias Grossera535dff2015-12-13 19:59:01 +0000401 if (MA->isArrayKind() || MA->isWrite())
Tobias Grosserd4dd6ec2015-07-27 17:57:58 +0000402 continue;
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000403
Michael Krusee2bccbb2015-09-18 19:59:43 +0000404 auto *Address = getOrCreateAlloca(*MA);
Michael Kruseeac97262016-02-24 22:08:14 +0000405 assert((!isa<Instruction>(Address) ||
406 DT.dominates(cast<Instruction>(Address)->getParent(),
407 Builder.GetInsertBlock())) &&
408 "Domination violation");
Michael Krusee2bccbb2015-09-18 19:59:43 +0000409 BBMap[MA->getBaseAddr()] =
Tobias Grosser2fc50df2015-08-30 19:51:01 +0000410 Builder.CreateLoad(Address, Address->getName() + ".reload");
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000411 }
412}
413
Michael Kruse225f0d12015-10-17 21:36:00 +0000414void BlockGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
Tobias Grosserbc132602015-09-05 09:56:54 +0000415 ValueMapT &BBMap) {
Tobias Grosserf2cdd142016-01-26 10:01:35 +0000416 Loop *L = LI.getLoopFor(Stmt.getBasicBlock());
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000417
Michael Kruse225f0d12015-10-17 21:36:00 +0000418 assert(Stmt.isBlockStmt() && "Region statements need to use the "
419 "generateScalarStores() function in the "
420 "RegionGenerator");
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000421
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000422 for (MemoryAccess *MA : Stmt) {
Tobias Grossera535dff2015-12-13 19:59:01 +0000423 if (MA->isArrayKind() || MA->isRead())
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000424 continue;
425
Johannes Doerfertd86f2152015-08-17 10:58:17 +0000426 Value *Val = MA->getAccessValue();
Michael Kruseee6a4fc2016-01-26 13:33:27 +0000427 if (MA->isAnyPHIKind()) {
428 assert(MA->getIncoming().size() >= 1 &&
429 "Block statements have exactly one exiting block, or multiple but "
430 "with same incoming block and value");
431 assert(std::all_of(MA->getIncoming().begin(), MA->getIncoming().end(),
432 [&](std::pair<BasicBlock *, Value *> p) -> bool {
433 return p.first == Stmt.getBasicBlock();
434 }) &&
435 "Incoming block must be statement's block");
436 Val = MA->getIncoming()[0].second;
437 }
Tobias Grosserbc132602015-09-05 09:56:54 +0000438 auto *Address = getOrCreateAlloca(*MA);
Johannes Doerfertd86f2152015-08-17 10:58:17 +0000439
Tobias Grosserf2cdd142016-01-26 10:01:35 +0000440 Val = getNewValue(Stmt, Val, BBMap, LTS, L);
Michael Kruseeac97262016-02-24 22:08:14 +0000441 assert((!isa<Instruction>(Val) ||
442 DT.dominates(cast<Instruction>(Val)->getParent(),
443 Builder.GetInsertBlock())) &&
444 "Domination violation");
445 assert((!isa<Instruction>(Address) ||
446 DT.dominates(cast<Instruction>(Address)->getParent(),
447 Builder.GetInsertBlock())) &&
448 "Domination violation");
Tobias Grosser92245222015-07-28 14:53:44 +0000449 Builder.CreateStore(Val, Address);
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000450 }
451}
452
Tobias Grosserc0091a72015-08-30 19:19:34 +0000453void BlockGenerator::createScalarInitialization(Scop &S) {
454 Region &R = S.getRegion();
Johannes Doerfert188542f2015-11-09 00:21:21 +0000455 BasicBlock *ExitBB = R.getExit();
456
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000457 // 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!");
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
Johannes Doerfertfb19dd62015-09-26 20:57:59 +0000467 Builder.SetInsertPoint(StartBB->getTerminator());
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000468
Tobias Grosserc0091a72015-08-30 19:19:34 +0000469 for (auto &Pair : S.arrays()) {
470 auto &Array = Pair.second;
471 if (Array->getNumberOfDimensions() != 0)
472 continue;
Tobias Grossera535dff2015-12-13 19:59:01 +0000473 if (Array->isPHIKind()) {
Tobias Grosserc0091a72015-08-30 19:19:34 +0000474 // 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());
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000479
Tobias Grosserc0091a72015-08-30 19:19:34 +0000480 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 "
483 "come from SplitBB");
484
485 int Idx = PHI->getBasicBlockIndex(SplitBB);
486 if (Idx < 0)
487 continue;
488
489 Value *ScalarValue = PHI->getIncomingValue(Idx);
490
Tobias Grosserbc132602015-09-05 09:56:54 +0000491 Builder.CreateStore(ScalarValue, getOrCreatePHIAlloca(PHI));
Tobias Grosserc0091a72015-08-30 19:19:34 +0000492 continue;
493 }
494
495 auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());
496
497 if (Inst && R.contains(Inst))
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000498 continue;
499
Johannes Doerfert188542f2015-11-09 00:21:21 +0000500 // 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;
Johannes Doerfert717b8662015-09-08 21:44:27 +0000507
Tobias Grosserc0091a72015-08-30 19:19:34 +0000508 Builder.CreateStore(Array->getBasePtr(),
Tobias Grosserbc132602015-09-05 09:56:54 +0000509 getOrCreateScalarAlloca(Array->getBasePtr()));
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000510 }
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;
Tobias Grosser64c0ff42015-08-31 05:52:24 +0000531 Value *ScalarAddr = EscapeMappingValue.first;
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000532
533 // Reload the demoted instruction in the optimized version of the SCoP.
Johannes Doerfertd8b6ad22015-10-18 12:36:42 +0000534 Value *EscapeInstReload =
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000535 Builder.CreateLoad(ScalarAddr, EscapeInst->getName() + ".final_reload");
Johannes Doerfertd8b6ad22015-10-18 12:36:42 +0000536 EscapeInstReload =
537 Builder.CreateBitOrPointerCast(EscapeInstReload, EscapeInst->getType());
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000538
539 // Create the merge PHI that merges the optimized and unoptimized version.
540 PHINode *MergePHI = PHINode::Create(EscapeInst->getType(), 2,
541 EscapeInst->getName() + ".merge");
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +0000542 MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000543
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
Tobias Grosserffa24462015-10-17 08:54:13 +0000559void BlockGenerator::findOutsideUsers(Scop &S) {
560 auto &R = S.getRegion();
Tobias Grosserffa24462015-10-17 08:54:13 +0000561 for (auto &Pair : S.arrays()) {
562 auto &Array = Pair.second;
563
564 if (Array->getNumberOfDimensions() != 0)
565 continue;
566
Tobias Grossera535dff2015-12-13 19:59:01 +0000567 if (Array->isPHIKind())
Tobias Grosserffa24462015-10-17 08:54:13 +0000568 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
Johannes Doerfert38a012c2016-05-23 09:14:07 +0000581 handleOutsideUsers(S, Inst);
Tobias Grosserffa24462015-10-17 08:54:13 +0000582 }
583}
584
Tobias Grosser27d742d2015-10-24 17:41:29 +0000585void 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
Michael Krusefaedfcb2016-03-03 17:20:43 +0000604 // 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
Tobias Grosser27d742d2015-10-24 17:41:29 +0000611 PHINode *PHI = dyn_cast<PHINode>(Val);
612 if (!PHI)
613 continue;
614
Tobias Grossera3f6eda2015-10-24 19:01:09 +0000615 if (PHI->getParent() != AfterMergeBB)
Tobias Grosser27d742d2015-10-24 17:41:29 +0000616 continue;
Tobias Grosser27d742d2015-10-24 17:41:29 +0000617
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);
Michael Krusefaedfcb2016-03-03 17:20:43 +0000623 assert((!isa<Instruction>(OriginalValue) ||
624 cast<Instruction>(OriginalValue)->getParent() != MergeBB) &&
625 "Original value must no be one we just generated.");
Tobias Grosser27d742d2015-10-24 17:41:29 +0000626 auto *MergePHI = PHINode::Create(PHI->getType(), 2, Name + ".ph.merge");
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +0000627 MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());
Tobias Grosser27d742d2015-10-24 17:41:29 +0000628 MergePHI->addIncoming(Reload, OptExitBB);
629 MergePHI->addIncoming(OriginalValue, ExitBB);
630 int Idx = PHI->getBasicBlockIndex(MergeBB);
631 PHI->setIncomingValue(Idx, MergePHI);
632 }
633}
634
Tobias Grosserffa24462015-10-17 08:54:13 +0000635void BlockGenerator::finalizeSCoP(Scop &S) {
636 findOutsideUsers(S);
Tobias Grosserc0091a72015-08-30 19:19:34 +0000637 createScalarInitialization(S);
Tobias Grosser27d742d2015-10-24 17:41:29 +0000638 createExitPHINodeMerges(S);
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000639 createScalarFinalization(S.getRegion());
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000640}
641
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000642VectorBlockGenerator::VectorBlockGenerator(BlockGenerator &BlockGen,
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000643 std::vector<LoopToScevMapT> &VLTS,
644 isl_map *Schedule)
Tobias Grosserbc132602015-09-05 09:56:54 +0000645 : BlockGenerator(BlockGen), VLTS(VLTS), Schedule(Schedule) {
Sebastian Popa00a0292012-12-18 07:46:06 +0000646 assert(Schedule && "No statement domain provided");
647}
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000648
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000649Value *VectorBlockGenerator::getVectorValue(ScopStmt &Stmt, Value *Old,
Tobias Grossere602a072013-05-07 07:30:56 +0000650 ValueMapT &VectorMap,
651 VectorValueMapT &ScalarMaps,
652 Loop *L) {
Hongbin Zhengfe11e282013-06-29 13:22:15 +0000653 if (Value *NewValue = VectorMap.lookup(Old))
654 return NewValue;
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000655
656 int Width = getVectorWidth();
657
658 Value *Vector = UndefValue::get(VectorType::get(Old->getType(), Width));
659
660 for (int Lane = 0; Lane < Width; Lane++)
Tobias Grosserc14582f2013-02-05 18:01:29 +0000661 Vector = Builder.CreateInsertElement(
Tobias Grosserbc132602015-09-05 09:56:54 +0000662 Vector, getNewValue(Stmt, Old, ScalarMaps[Lane], VLTS[Lane], L),
Tobias Grosser7242ad92013-02-22 08:07:06 +0000663 Builder.getInt32(Lane));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000664
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");
673
674 Type *ScalarType = PointerTy->getElementType();
675 VectorType *VectorType = VectorType::get(ScalarType, Width);
676
677 return PointerType::getUnqual(VectorType);
678}
679
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000680Value *VectorBlockGenerator::generateStrideOneLoad(
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000681 ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000682 __isl_keep isl_id_to_ast_expr *NewAccesses, bool NegativeStride = false) {
Tobias Grosser0dd463f2014-03-19 19:27:24 +0000683 unsigned VectorWidth = getVectorWidth();
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000684 auto *Pointer = Load->getPointerOperand();
Tobias Grosser0dd463f2014-03-19 19:27:24 +0000685 Type *VectorPtrType = getVectorPtrTy(Pointer, VectorWidth);
686 unsigned Offset = NegativeStride ? VectorWidth - 1 : 0;
687
Michael Kruse8f25b0c2016-02-25 15:52:43 +0000688 Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[Offset],
689 VLTS[Offset], NewAccesses);
Tobias Grosserc14582f2013-02-05 18:01:29 +0000690 Value *VectorPtr =
691 Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr");
692 LoadInst *VecLoad =
693 Builder.CreateLoad(VectorPtr, Load->getName() + "_p_vec_full");
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000694 if (!Aligned)
695 VecLoad->setAlignment(8);
696
Tobias Grosser0dd463f2014-03-19 19:27:24 +0000697 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
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000707 return VecLoad;
708}
709
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000710Value *VectorBlockGenerator::generateStrideZeroLoad(
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000711 ScopStmt &Stmt, LoadInst *Load, ValueMapT &BBMap,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000712 __isl_keep isl_id_to_ast_expr *NewAccesses) {
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000713 auto *Pointer = Load->getPointerOperand();
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000714 Type *VectorPtrType = getVectorPtrTy(Pointer, 1);
Michael Kruse70131d32016-01-27 17:09:17 +0000715 Value *NewPointer =
716 generateLocationAccessed(Stmt, Load, BBMap, VLTS[0], NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000717 Value *VectorPtr = Builder.CreateBitCast(NewPointer, VectorPtrType,
718 Load->getName() + "_p_vec_p");
Tobias Grosserc14582f2013-02-05 18:01:29 +0000719 LoadInst *ScalarLoad =
720 Builder.CreateLoad(VectorPtr, Load->getName() + "_p_splat_one");
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000721
722 if (!Aligned)
723 ScalarLoad->setAlignment(8);
724
Tobias Grosserc14582f2013-02-05 18:01:29 +0000725 Constant *SplatVector = Constant::getNullValue(
726 VectorType::get(Builder.getInt32Ty(), getVectorWidth()));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000727
Tobias Grosserc14582f2013-02-05 18:01:29 +0000728 Value *VectorLoad = Builder.CreateShuffleVector(
729 ScalarLoad, ScalarLoad, SplatVector, Load->getName() + "_p_splat");
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000730 return VectorLoad;
731}
732
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000733Value *VectorBlockGenerator::generateUnknownStrideLoad(
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000734 ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps,
Johannes Doerfert09e36972015-10-07 20:17:36 +0000735 __isl_keep isl_id_to_ast_expr *NewAccesses) {
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000736 int VectorWidth = getVectorWidth();
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000737 auto *Pointer = Load->getPointerOperand();
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000738 VectorType *VectorType = VectorType::get(
Tobias Grosserc14582f2013-02-05 18:01:29 +0000739 dyn_cast<PointerType>(Pointer->getType())->getElementType(), VectorWidth);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000740
741 Value *Vector = UndefValue::get(VectorType);
742
743 for (int i = 0; i < VectorWidth; i++) {
Michael Kruse70131d32016-01-27 17:09:17 +0000744 Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[i],
745 VLTS[i], NewAccesses);
Tobias Grosserc14582f2013-02-05 18:01:29 +0000746 Value *ScalarLoad =
747 Builder.CreateLoad(NewPointer, Load->getName() + "_p_scalar_");
748 Vector = Builder.CreateInsertElement(
749 Vector, ScalarLoad, Builder.getInt32(i), Load->getName() + "_p_vec_");
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000750 }
751
752 return Vector;
753}
754
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000755void VectorBlockGenerator::generateLoad(
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000756 ScopStmt &Stmt, LoadInst *Load, ValueMapT &VectorMap,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000757 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
Johannes Doerfertc1db67e2015-09-29 23:47:21 +0000758 if (Value *PreloadLoad = GlobalMap.lookup(Load)) {
759 VectorMap[Load] = Builder.CreateVectorSplat(getVectorWidth(), PreloadLoad,
760 Load->getName() + "_p");
761 return;
762 }
763
Tobias Grosser28736452015-03-23 07:00:36 +0000764 if (!VectorType::isValidElementType(Load->getType())) {
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000765 for (int i = 0; i < getVectorWidth(); i++)
Tobias Grosserbc132602015-09-05 09:56:54 +0000766 ScalarMaps[i][Load] =
767 generateScalarLoad(Stmt, Load, ScalarMaps[i], VLTS[i], NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000768 return;
769 }
770
Tobias Grosser184a4922015-12-15 23:50:01 +0000771 const MemoryAccess &Access = Stmt.getArrayAccessFor(Load);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000772
Tobias Grosser95493982014-04-18 09:46:35 +0000773 // Make sure we have scalar values available to access the pointer to
774 // the data location.
775 extractScalarValues(Load, VectorMap, ScalarMaps);
776
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000777 Value *NewLoad;
Sebastian Popa00a0292012-12-18 07:46:06 +0000778 if (Access.isStrideZero(isl_map_copy(Schedule)))
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000779 NewLoad = generateStrideZeroLoad(Stmt, Load, ScalarMaps[0], NewAccesses);
Sebastian Popa00a0292012-12-18 07:46:06 +0000780 else if (Access.isStrideOne(isl_map_copy(Schedule)))
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000781 NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses);
Tobias Grosser0dd463f2014-03-19 19:27:24 +0000782 else if (Access.isStrideX(isl_map_copy(Schedule), -1))
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000783 NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses, true);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000784 else
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000785 NewLoad = generateUnknownStrideLoad(Stmt, Load, ScalarMaps, NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000786
787 VectorMap[Load] = NewLoad;
788}
789
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000790void VectorBlockGenerator::copyUnaryInst(ScopStmt &Stmt, UnaryInstruction *Inst,
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000791 ValueMapT &VectorMap,
792 VectorValueMapT &ScalarMaps) {
793 int VectorWidth = getVectorWidth();
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000794 Value *NewOperand = getVectorValue(Stmt, Inst->getOperand(0), VectorMap,
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000795 ScalarMaps, getLoopForStmt(Stmt));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000796
797 assert(isa<CastInst>(Inst) && "Can not generate vector code for instruction");
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
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000804void VectorBlockGenerator::copyBinaryInst(ScopStmt &Stmt, BinaryOperator *Inst,
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000805 ValueMapT &VectorMap,
806 VectorValueMapT &ScalarMaps) {
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000807 Loop *L = getLoopForStmt(Stmt);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000808 Value *OpZero = Inst->getOperand(0);
809 Value *OpOne = Inst->getOperand(1);
810
811 Value *NewOpZero, *NewOpOne;
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000812 NewOpZero = getVectorValue(Stmt, OpZero, VectorMap, ScalarMaps, L);
813 NewOpOne = getVectorValue(Stmt, OpOne, VectorMap, ScalarMaps, L);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000814
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000815 Value *NewInst = Builder.CreateBinOp(Inst->getOpcode(), NewOpZero, NewOpOne,
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000816 Inst->getName() + "p_vec");
817 VectorMap[Inst] = NewInst;
818}
819
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000820void VectorBlockGenerator::copyStore(
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000821 ScopStmt &Stmt, StoreInst *Store, ValueMapT &VectorMap,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000822 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
Tobias Grosser184a4922015-12-15 23:50:01 +0000823 const MemoryAccess &Access = Stmt.getArrayAccessFor(Store);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000824
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000825 auto *Pointer = Store->getPointerOperand();
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000826 Value *Vector = getVectorValue(Stmt, Store->getValueOperand(), VectorMap,
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000827 ScalarMaps, getLoopForStmt(Stmt));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000828
Tobias Grosser50fd7012014-04-17 23:13:49 +0000829 // Make sure we have scalar values available to access the pointer to
830 // the data location.
831 extractScalarValues(Store, VectorMap, ScalarMaps);
832
Sebastian Popa00a0292012-12-18 07:46:06 +0000833 if (Access.isStrideOne(isl_map_copy(Schedule))) {
Johannes Doerfert1947f862014-10-08 20:18:32 +0000834 Type *VectorPtrType = getVectorPtrTy(Pointer, getVectorWidth());
Michael Kruse70131d32016-01-27 17:09:17 +0000835 Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[0],
836 VLTS[0], NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000837
Tobias Grosserc14582f2013-02-05 18:01:29 +0000838 Value *VectorPtr =
839 Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr");
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000840 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++) {
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000846 Value *Scalar = Builder.CreateExtractElement(Vector, Builder.getInt32(i));
Michael Kruse70131d32016-01-27 17:09:17 +0000847 Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[i],
848 VLTS[i], NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000849 Builder.CreateStore(Scalar, NewPointer);
850 }
851 }
852}
853
854bool VectorBlockGenerator::hasVectorOperands(const Instruction *Inst,
855 ValueMapT &VectorMap) {
Tobias Grosser91f5b262014-06-04 08:06:40 +0000856 for (Value *Operand : Inst->operands())
857 if (VectorMap.count(Operand))
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000858 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
Tobias Grosser91f5b262014-06-04 08:06:40 +0000868 for (Value *Operand : Inst->operands()) {
869 ValueMapT::iterator VecOp = VectorMap.find(Operand);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000870
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.
Tobias Grosser91f5b262014-06-04 08:06:40 +0000883 if (SM.count(Operand))
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000884 break;
885
Tobias Grosser91f5b262014-06-04 08:06:40 +0000886 SM[Operand] =
887 Builder.CreateExtractElement(NewVector, Builder.getInt32(i));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000888 }
889 }
890
891 return HasVectorOperand;
892}
893
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000894void VectorBlockGenerator::copyInstScalarized(
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000895 ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000896 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000897 bool HasVectorOperand;
898 int VectorWidth = getVectorWidth();
899
900 HasVectorOperand = extractScalarValues(Inst, VectorMap, ScalarMaps);
901
902 for (int VectorLane = 0; VectorLane < getVectorWidth(); VectorLane++)
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000903 BlockGenerator::copyInstruction(Stmt, Inst, ScalarMaps[VectorLane],
Tobias Grosserbc132602015-09-05 09:56:54 +0000904 VLTS[VectorLane], NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000905
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
Tobias Grosserbc132602015-09-05 09:56:54 +0000920int VectorBlockGenerator::getVectorWidth() { return VLTS.size(); }
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000921
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000922void VectorBlockGenerator::copyInstruction(
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000923 ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000924 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000925 // 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
Johannes Doerfert5dced262015-12-22 19:08:49 +0000930 if (canSyntheziseInStmt(Stmt, Inst))
Tobias Grossere71c6ab2012-04-27 16:36:14 +0000931 return;
932
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000933 if (auto *Load = dyn_cast<LoadInst>(Inst)) {
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000934 generateLoad(Stmt, Load, VectorMap, ScalarMaps, NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000935 return;
936 }
937
938 if (hasVectorOperands(Inst, VectorMap)) {
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000939 if (auto *Store = dyn_cast<StoreInst>(Inst)) {
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000940 copyStore(Stmt, Store, VectorMap, ScalarMaps, NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000941 return;
942 }
943
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000944 if (auto *Unary = dyn_cast<UnaryInstruction>(Inst)) {
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000945 copyUnaryInst(Stmt, Unary, VectorMap, ScalarMaps);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000946 return;
947 }
948
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000949 if (auto *Binary = dyn_cast<BinaryOperator>(Inst)) {
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000950 copyBinaryInst(Stmt, Binary, VectorMap, ScalarMaps);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000951 return;
952 }
953
954 // Falltrough: We generate scalar instructions, if we don't know how to
955 // generate vector code.
956 }
957
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000958 copyInstScalarized(Stmt, Inst, VectorMap, ScalarMaps, NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000959}
960
Tobias Grossera69d4f02015-12-15 23:49:58 +0000961void 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;
Tobias Grossera69d4f02015-12-15 23:49:58 +0000978 }
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");
987 }
988}
989
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000990void VectorBlockGenerator::copyStmt(
991 ScopStmt &Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) {
Johannes Doerfert275a1752015-02-24 16:16:32 +0000992 assert(Stmt.isBlockStmt() && "TODO: Only block statements can be copied by "
993 "the vector block generator");
994
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000995 BasicBlock *BB = Stmt.getBasicBlock();
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +0000996 BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(),
997 &*Builder.GetInsertPoint(), &DT, &LI);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000998 CopyBB->setName("polly.stmt." + BB->getName());
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +0000999 Builder.SetInsertPoint(&CopyBB->front());
Hongbin Zheng3b11a162012-04-25 13:16:49 +00001000
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
Tobias Grossera69d4f02015-12-15 23:49:58 +00001018 generateScalarVectorLoads(Stmt, VectorBlockMap);
1019
Tobias Grosser91f5b262014-06-04 08:06:40 +00001020 for (Instruction &Inst : *BB)
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +00001021 copyInstruction(Stmt, &Inst, VectorBlockMap, ScalarBlockMap, NewAccesses);
Tobias Grossera69d4f02015-12-15 23:49:58 +00001022
1023 verifyNoScalarStores(Stmt);
Hongbin Zheng3b11a162012-04-25 13:16:49 +00001024}
Johannes Doerfert275a1752015-02-24 16:16:32 +00001025
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001026BasicBlock *RegionGenerator::repairDominance(BasicBlock *BB,
1027 BasicBlock *BBCopy) {
Johannes Doerfert514f6ef2015-02-27 18:29:04 +00001028
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
Michael Krusef33c1252016-02-25 14:08:48 +00001038// 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));
1079 return Common;
1080}
1081
Tobias Grosserbc132602015-09-05 09:56:54 +00001082void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +00001083 isl_id_to_ast_expr *IdToAstExp) {
Johannes Doerfert275a1752015-02-24 16:16:32 +00001084 assert(Stmt.isRegionStmt() &&
Tobias Grosserd3f21832015-08-01 06:26:51 +00001085 "Only region statements can be copied by the region generator");
Johannes Doerfert275a1752015-02-24 16:16:32 +00001086
Michael Krused6fb6f12015-11-09 23:07:38 +00001087 Scop *S = Stmt.getParent();
1088
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001089 // Forget all old mappings.
1090 BlockMap.clear();
1091 RegionMaps.clear();
1092 IncompletePHINodeMap.clear();
1093
Michael Kruse225f0d12015-10-17 21:36:00 +00001094 // Collection of all values related to this subregion.
1095 ValueMapT ValueMap;
1096
Johannes Doerfert275a1752015-02-24 16:16:32 +00001097 // The region represented by the statement.
1098 Region *R = Stmt.getRegion();
1099
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001100 // Create a dedicated entry for the region where we can reload all demoted
1101 // inputs.
1102 BasicBlock *EntryBB = R->getEntry();
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +00001103 BasicBlock *EntryBBCopy = SplitBlock(Builder.GetInsertBlock(),
1104 &*Builder.GetInsertPoint(), &DT, &LI);
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001105 EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry");
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +00001106 Builder.SetInsertPoint(&EntryBBCopy->front());
Johannes Doerfert514f6ef2015-02-27 18:29:04 +00001107
Michael Krusec9937392015-11-09 23:33:40 +00001108 ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy];
1109 generateScalarLoads(Stmt, EntryBBMap);
Michael Kruse225f0d12015-10-17 21:36:00 +00001110
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001111 for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI)
1112 if (!R->contains(*PI))
1113 BlockMap[*PI] = EntryBBCopy;
Johannes Doerfert275a1752015-02-24 16:16:32 +00001114
Michael Krused6fb6f12015-11-09 23:07:38 +00001115 // 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));
1125
Johannes Doerfert275a1752015-02-24 16:16:32 +00001126 // Iterate over all blocks in the region in a breadth-first search.
1127 std::deque<BasicBlock *> Blocks;
1128 SmallPtrSet<BasicBlock *, 8> SeenBlocks;
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001129 Blocks.push_back(EntryBB);
1130 SeenBlocks.insert(EntryBB);
Johannes Doerfert275a1752015-02-24 16:16:32 +00001131
1132 while (!Blocks.empty()) {
1133 BasicBlock *BB = Blocks.front();
1134 Blocks.pop_front();
1135
Johannes Doerfert514f6ef2015-02-27 18:29:04 +00001136 // First split the block and update dominance information.
1137 BasicBlock *BBCopy = splitBB(BB);
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001138 BasicBlock *BBCopyIDom = repairDominance(BB, BBCopy);
1139
Michael Krusec9937392015-11-09 23:33:40 +00001140 // 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));
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;
Johannes Doerfert514f6ef2015-02-27 18:29:04 +00001152
Johannes Doerfert275a1752015-02-24 16:16:32 +00001153 // Copy the block with the BlockGenerator.
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +00001154 Builder.SetInsertPoint(&BBCopy->front());
Tobias Grosserbc132602015-09-05 09:56:54 +00001155 copyBB(Stmt, BB, BBCopy, RegionMap, LTS, IdToAstExp);
Johannes Doerfert275a1752015-02-24 16:16:32 +00001156
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001157 // 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])
Tobias Grosserbc132602015-09-05 09:56:54 +00001162 addOperandToPHI(Stmt, PHINodePair.first, PHINodePair.second, BB, LTS);
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001163 IncompletePHINodeMap[BB].clear();
1164
Johannes Doerfert275a1752015-02-24 16:16:32 +00001165 // 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);
Michael Kruseebffcbe2015-11-09 22:37:29 +00001169
1170 // Remember value in case it is visible after this subregion.
Michael Krusef33c1252016-02-25 14:08:48 +00001171 if (isDominatingSubregionExit(DT, R, BB))
Michael Kruseebffcbe2015-11-09 22:37:29 +00001172 ValueMap.insert(RegionMap.begin(), RegionMap.end());
Johannes Doerfert275a1752015-02-24 16:16:32 +00001173 }
1174
1175 // Now create a new dedicated region exit block and add it to the region map.
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +00001176 BasicBlock *ExitBBCopy = SplitBlock(Builder.GetInsertBlock(),
1177 &*Builder.GetInsertPoint(), &DT, &LI);
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001178 ExitBBCopy->setName("polly.stmt." + R->getExit()->getName() + ".exit");
Johannes Doerfert514f6ef2015-02-27 18:29:04 +00001179 BlockMap[R->getExit()] = ExitBBCopy;
1180
Michael Krusef33c1252016-02-25 14:08:48 +00001181 BasicBlock *ExitDomBBCopy = BlockMap.lookup(findExitDominator(DT, R));
1182 assert(ExitDomBBCopy && "Common exit dominator must be within region; at "
1183 "least the entry node must match");
1184 DT.changeImmediateDominator(ExitBBCopy, ExitDomBBCopy);
Johannes Doerfert275a1752015-02-24 16:16:32 +00001185
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
Johannes Doerfert514f6ef2015-02-27 18:29:04 +00001190 BasicBlock *BBCopy = BlockMap[BB];
Johannes Doerferte114dc02015-09-14 11:15:58 +00001191 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
Johannes Doerfert275a1752015-02-24 16:16:32 +00001199 Instruction *BICopy = BBCopy->getTerminator();
1200
Johannes Doerfert514f6ef2015-02-27 18:29:04 +00001201 ValueMapT &RegionMap = RegionMaps[BBCopy];
1202 RegionMap.insert(BlockMap.begin(), BlockMap.end());
1203
Tobias Grosser45e79442015-08-01 09:07:57 +00001204 Builder.SetInsertPoint(BICopy);
Johannes Doerfert9a132f32015-09-28 09:33:22 +00001205 copyInstScalar(Stmt, TI, RegionMap, LTS);
Johannes Doerfert275a1752015-02-24 16:16:32 +00001206 BICopy->eraseFromParent();
1207 }
1208
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001209 // 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);
Tobias Grosserbc29e0b2015-11-12 07:34:09 +00001213 if (L == nullptr || L->getHeader() != BB || !R->contains(L))
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001214 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");
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +00001222 LoopPHI->insertBefore(&BBCopy->front());
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001223 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
Michael Kruse225f0d12015-10-17 21:36:00 +00001241 // Continue generating code in the exit block.
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +00001242 Builder.SetInsertPoint(&*ExitBBCopy->getFirstInsertionPt());
Michael Kruse225f0d12015-10-17 21:36:00 +00001243
1244 // Write values visible to other statements.
1245 generateScalarStores(Stmt, LTS, ValueMap);
Tobias Grosser3e956022015-10-26 20:41:53 +00001246 BlockMap.clear();
1247 RegionMaps.clear();
1248 IncompletePHINodeMap.clear();
Johannes Doerfert275a1752015-02-24 16:16:32 +00001249}
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001250
Michael Kruseee6a4fc2016-01-26 13:33:27 +00001251PHINode *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));
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() &&
1300 "PHI WRITEs must have originate from at least one incoming block");
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
Michael Kruse225f0d12015-10-17 21:36:00 +00001317void RegionGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
Tobias Grosserbc132602015-09-05 09:56:54 +00001318 ValueMapT &BBMap) {
Tobias Grosser75296902015-08-21 19:23:21 +00001319 assert(Stmt.getRegion() &&
1320 "Block statements need to use the generateScalarStores() "
1321 "function in the BlockGenerator");
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001322
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001323 for (MemoryAccess *MA : Stmt) {
Tobias Grossera535dff2015-12-13 19:59:01 +00001324 if (MA->isArrayKind() || MA->isRead())
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001325 continue;
1326
Michael Kruseee6a4fc2016-01-26 13:33:27 +00001327 Value *NewVal = getExitScalar(MA, LTS, BBMap);
1328 Value *Address = getOrCreateAlloca(*MA);
Michael Kruseeac97262016-02-24 22:08:14 +00001329 assert((!isa<Instruction>(NewVal) ||
1330 DT.dominates(cast<Instruction>(NewVal)->getParent(),
1331 Builder.GetInsertBlock())) &&
1332 "Domination violation");
1333 assert((!isa<Instruction>(Address) ||
1334 DT.dominates(cast<Instruction>(Address)->getParent(),
1335 Builder.GetInsertBlock())) &&
1336 "Domination violation");
Michael Kruseee6a4fc2016-01-26 13:33:27 +00001337 Builder.CreateStore(NewVal, Address);
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001338 }
1339}
1340
1341void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, const PHINode *PHI,
1342 PHINode *PHICopy, BasicBlock *IncomingBB,
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001343 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) &&
1351 "Bad incoming block for PHI in non-affine region");
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) &&
1359 "Incoming PHI block did not have a BBMap");
1360 ValueMapT &BBCopyMap = RegionMaps[BBCopy];
1361
1362 Value *Op = PHI->getIncomingValueForBlock(IncomingBB);
Michael Krusedc122222015-10-19 09:19:25 +00001363
Johannes Doerfert6ba92712016-04-01 11:25:47 +00001364 // 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());
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +00001369 OpCopy = getNewValue(Stmt, Op, BBCopyMap, LTS, getLoopForStmt(Stmt));
Johannes Doerfert6ba92712016-04-01 11:25:47 +00001370 if (IP->getParent() != BBCopy)
1371 Builder.SetInsertPoint(&*IP);
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001372 } else {
1373
1374 if (PHICopy->getBasicBlockIndex(BBCopy) >= 0)
1375 return;
1376
Tobias Grosserbc132602015-09-05 09:56:54 +00001377 Value *PHIOpAddr = getOrCreatePHIAlloca(const_cast<PHINode *>(PHI));
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001378 OpCopy = new LoadInst(PHIOpAddr, PHIOpAddr->getName() + ".reload",
1379 BlockMap[IncomingBB]->getTerminator());
1380 }
1381
1382 assert(OpCopy && "Incoming PHI value was not copied properly");
1383 assert(BBCopy && "Incoming PHI block was not copied properly");
1384 PHICopy->addIncoming(OpCopy, BBCopy);
1385}
1386
Tobias Grosser2b809d12016-02-21 15:44:34 +00001387void RegionGenerator::copyPHIInstruction(ScopStmt &Stmt, PHINode *PHI,
1388 ValueMapT &BBMap,
1389 LoopToScevMapT &LTS) {
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001390 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++)
Tobias Grosserbc132602015-09-05 09:56:54 +00001397 addOperandToPHI(Stmt, PHI, PHICopy, PHI->getIncomingBlock(u), LTS);
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001398}