blob: 3904e85784ec2caf8b147e7f43cc2d667a3ccbe4 [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
Sanjoy Das03bcb912016-05-29 07:33:16 +000076 const SCEV *NewScev = SCEVLoopAddRecRewriter::rewrite(Scev, LTS, SE);
Johannes Doerfert42df8d12015-12-22 19:08:01 +000077 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();
Johannes Doerfert3f52e352016-05-23 12:38:05 +000082 const DataLayout &DL = S.getFunction().getParent()->getDataLayout();
Johannes Doerfert42df8d12015-12-22 19:08:01 +000083 auto IP = Builder.GetInsertPoint();
84
85 assert(IP != Builder.GetInsertBlock()->end() &&
86 "Only instructions can be insert points for SCEVExpander");
87 Value *Expanded =
88 expandCodeFor(S, SE, DL, "polly", NewScev, Old->getType(), &*IP, &VTV);
89
90 BBMap[Old] = Expanded;
91 return Expanded;
Tobias Grosser33cb9f92015-09-30 11:56:19 +000092}
93
Tobias Grosser2f1acac2015-10-04 10:18:45 +000094Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
95 LoopToScevMapT &LTS, Loop *L) const {
Tobias Grosser9bd0dad2015-12-14 16:19:59 +000096 // Constants that do not reference any named value can always remain
Michael Kruse5bbc0e12015-12-14 23:41:32 +000097 // unchanged. Handle them early to avoid expensive map lookups. We do not take
Tobias Grosser9bd0dad2015-12-14 16:19:59 +000098 // the fast-path for external constants which are referenced through globals
99 // as these may need to be rewritten when distributing code accross different
100 // LLVM modules.
101 if (isa<Constant>(Old) && !isa<GlobalValue>(Old))
Tobias Grosser6f764bb2015-12-14 16:19:54 +0000102 return Old;
Tobias Grosser33cb9f92015-09-30 11:56:19 +0000103
Johannes Doerfert28f8ac12015-12-22 19:08:24 +0000104 // Inline asm is like a constant to us.
105 if (isa<InlineAsm>(Old))
106 return Old;
107
Tobias Grosser33cb9f92015-09-30 11:56:19 +0000108 if (Value *New = GlobalMap.lookup(Old)) {
109 if (Value *NewRemapped = GlobalMap.lookup(New))
110 New = NewRemapped;
111 if (Old->getType()->getScalarSizeInBits() <
112 New->getType()->getScalarSizeInBits())
113 New = Builder.CreateTruncOrBitCast(New, Old->getType());
114
115 return New;
116 }
117
118 if (Value *New = BBMap.lookup(Old))
119 return New;
120
121 if (Value *New = trySynthesizeNewValue(Stmt, Old, BBMap, LTS, L))
122 return New;
123
Tobias Grosser16371ac2014-11-05 20:48:56 +0000124 // A scop-constant value defined by a global or a function parameter.
125 if (isa<GlobalValue>(Old) || isa<Argument>(Old))
Tobias Grosser6f764bb2015-12-14 16:19:54 +0000126 return Old;
Tobias Grosser16371ac2014-11-05 20:48:56 +0000127
128 // A scop-constant value defined by an instruction executed outside the scop.
129 if (const Instruction *Inst = dyn_cast<Instruction>(Old))
Johannes Doerfert952b5302016-05-23 12:40:48 +0000130 if (!Stmt.getParent()->contains(Inst->getParent()))
Tobias Grosser6f764bb2015-12-14 16:19:54 +0000131 return Old;
Tobias Grosser16371ac2014-11-05 20:48:56 +0000132
133 // The scalar dependence is neither available nor SCEVCodegenable.
Hongbin Zheng5b463ce2013-07-25 09:12:07 +0000134 llvm_unreachable("Unexpected scalar dependence in region!");
Tobias Grosser5a56cbf2014-04-16 07:33:47 +0000135 return nullptr;
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000136}
137
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000138void BlockGenerator::copyInstScalar(ScopStmt &Stmt, Instruction *Inst,
Tobias Grosserbc132602015-09-05 09:56:54 +0000139 ValueMapT &BBMap, LoopToScevMapT &LTS) {
Tobias Grosser030237d2014-02-21 15:06:05 +0000140 // We do not generate debug intrinsics as we did not investigate how to
141 // copy them correctly. At the current state, they just crash the code
142 // generation as the meta-data operands are not correctly copied.
143 if (isa<DbgInfoIntrinsic>(Inst))
144 return;
145
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000146 Instruction *NewInst = Inst->clone();
147
148 // Replace old operands with the new ones.
Tobias Grosser91f5b262014-06-04 08:06:40 +0000149 for (Value *OldOperand : Inst->operands()) {
Tobias Grosserbc132602015-09-05 09:56:54 +0000150 Value *NewOperand =
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000151 getNewValue(Stmt, OldOperand, BBMap, LTS, getLoopForStmt(Stmt));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000152
153 if (!NewOperand) {
Tobias Grosserc14582f2013-02-05 18:01:29 +0000154 assert(!isa<StoreInst>(NewInst) &&
155 "Store instructions are always needed!");
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000156 delete NewInst;
157 return;
158 }
159
160 NewInst->replaceUsesOfWith(OldOperand, NewOperand);
161 }
162
163 Builder.Insert(NewInst);
164 BBMap[Inst] = NewInst;
165
166 if (!NewInst->getType()->isVoidTy())
167 NewInst->setName("p_" + Inst->getName());
168}
169
Michael Kruse70131d32016-01-27 17:09:17 +0000170Value *
171BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,
172 ValueMapT &BBMap, LoopToScevMapT &LTS,
173 isl_id_to_ast_expr *NewAccesses) {
Tobias Grosser09214772015-12-15 23:49:53 +0000174 const MemoryAccess &MA = Stmt.getArrayAccessFor(Inst);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000175
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000176 isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(NewAccesses, MA.getId());
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000177
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000178 if (AccessExpr) {
179 AccessExpr = isl_ast_expr_address_of(AccessExpr);
Tobias Grosser98b3ee52015-09-29 06:44:38 +0000180 auto Address = ExprBuilder->create(AccessExpr);
181
182 // Cast the address of this memory access to a pointer type that has the
183 // same element type as the original access, but uses the address space of
184 // the newly generated pointer.
185 auto OldPtrTy = MA.getAccessValue()->getType()->getPointerTo();
186 auto NewPtrTy = Address->getType();
187 OldPtrTy = PointerType::get(OldPtrTy->getElementType(),
188 NewPtrTy->getPointerAddressSpace());
189
Tobias Grosserd840fc72016-02-04 13:18:42 +0000190 if (OldPtrTy != NewPtrTy)
Tobias Grosser98b3ee52015-09-29 06:44:38 +0000191 Address = Builder.CreateBitOrPointerCast(Address, OldPtrTy);
Tobias Grosser98b3ee52015-09-29 06:44:38 +0000192 return Address;
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000193 }
194
Michael Kruse70131d32016-01-27 17:09:17 +0000195 return getNewValue(Stmt, Inst.getPointerOperand(), BBMap, LTS,
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000196 getLoopForStmt(Stmt));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000197}
198
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000199Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const {
Michael Kruse375cb5f2016-02-24 22:08:24 +0000200 auto *StmtBB = Stmt.getEntryBlock();
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000201 return LI.getLoopFor(StmtBB);
Tobias Grosser369430f2013-03-22 23:42:53 +0000202}
203
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000204Value *BlockGenerator::generateScalarLoad(ScopStmt &Stmt, LoadInst *Load,
Tobias Grosserbc132602015-09-05 09:56:54 +0000205 ValueMapT &BBMap, LoopToScevMapT &LTS,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000206 isl_id_to_ast_expr *NewAccesses) {
Johannes Doerfertc1db67e2015-09-29 23:47:21 +0000207 if (Value *PreloadLoad = GlobalMap.lookup(Load))
208 return PreloadLoad;
209
Tobias Grosserbc132602015-09-05 09:56:54 +0000210 Value *NewPointer =
Michael Kruse70131d32016-01-27 17:09:17 +0000211 generateLocationAccessed(Stmt, Load, BBMap, LTS, NewAccesses);
Johannes Doerfert87901452014-10-02 16:22:19 +0000212 Value *ScalarLoad = Builder.CreateAlignedLoad(
213 NewPointer, Load->getAlignment(), Load->getName() + "_p_scalar_");
Tobias Grosser86bc93a2015-09-06 08:47:57 +0000214
215 if (DebugPrinting)
216 RuntimeDebugBuilder::createCPUPrinter(Builder, "Load from ", NewPointer,
217 ": ", ScalarLoad, "\n");
218
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000219 return ScalarLoad;
220}
221
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000222void BlockGenerator::generateScalarStore(ScopStmt &Stmt, StoreInst *Store,
Tobias Grosserbc132602015-09-05 09:56:54 +0000223 ValueMapT &BBMap, LoopToScevMapT &LTS,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000224 isl_id_to_ast_expr *NewAccesses) {
Tobias Grosserbc132602015-09-05 09:56:54 +0000225 Value *NewPointer =
Michael Kruse70131d32016-01-27 17:09:17 +0000226 generateLocationAccessed(Stmt, Store, BBMap, LTS, NewAccesses);
Tobias Grosserbc132602015-09-05 09:56:54 +0000227 Value *ValueOperand = getNewValue(Stmt, Store->getValueOperand(), BBMap, LTS,
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000228 getLoopForStmt(Stmt));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000229
Tobias Grosser86bc93a2015-09-06 08:47:57 +0000230 if (DebugPrinting)
231 RuntimeDebugBuilder::createCPUPrinter(Builder, "Store to ", NewPointer,
232 ": ", ValueOperand, "\n");
233
Tobias Grosserc186ac72015-08-11 08:13:15 +0000234 Builder.CreateAlignedStore(ValueOperand, NewPointer, Store->getAlignment());
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000235}
236
Johannes Doerfert5dced262015-12-22 19:08:49 +0000237bool BlockGenerator::canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst) {
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000238 Loop *L = getLoopForStmt(Stmt);
Johannes Doerfert5dced262015-12-22 19:08:49 +0000239 return (Stmt.isBlockStmt() || !Stmt.getRegion()->contains(L)) &&
Johannes Doerfert0f0d209b2016-05-23 12:47:09 +0000240 canSynthesize(Inst, *Stmt.getParent(), &LI, &SE, L);
Johannes Doerfert5dced262015-12-22 19:08:49 +0000241}
242
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000243void BlockGenerator::copyInstruction(ScopStmt &Stmt, Instruction *Inst,
Tobias Grosserbc132602015-09-05 09:56:54 +0000244 ValueMapT &BBMap, LoopToScevMapT &LTS,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000245 isl_id_to_ast_expr *NewAccesses) {
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000246 // Terminator instructions control the control flow. They are explicitly
247 // expressed in the clast and do not need to be copied.
248 if (Inst->isTerminator())
249 return;
250
Johannes Doerfert5dced262015-12-22 19:08:49 +0000251 // Synthesizable statements will be generated on-demand.
252 if (canSyntheziseInStmt(Stmt, Inst))
Tobias Grossere71c6ab2012-04-27 16:36:14 +0000253 return;
254
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000255 if (auto *Load = dyn_cast<LoadInst>(Inst)) {
Tobias Grosserbc132602015-09-05 09:56:54 +0000256 Value *NewLoad = generateScalarLoad(Stmt, Load, BBMap, LTS, NewAccesses);
Sebastian Pop3d94fed2013-05-24 18:46:02 +0000257 // Compute NewLoad before its insertion in BBMap to make the insertion
258 // deterministic.
Sebastian Pop753d43f2013-05-24 17:16:02 +0000259 BBMap[Load] = NewLoad;
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000260 return;
261 }
262
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000263 if (auto *Store = dyn_cast<StoreInst>(Inst)) {
Tobias Grosserbc132602015-09-05 09:56:54 +0000264 generateScalarStore(Stmt, Store, BBMap, LTS, NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000265 return;
266 }
267
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000268 if (auto *PHI = dyn_cast<PHINode>(Inst)) {
Tobias Grosserbc132602015-09-05 09:56:54 +0000269 copyPHIInstruction(Stmt, PHI, BBMap, LTS);
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000270 return;
271 }
272
Johannes Doerfert3f500fa2015-01-25 18:07:30 +0000273 // Skip some special intrinsics for which we do not adjust the semantics to
274 // the new schedule. All others are handled like every other instruction.
Tobias Grosser9c0ffe32015-08-30 16:57:15 +0000275 if (isIgnoredIntrinsic(Inst))
276 return;
Johannes Doerfert3f500fa2015-01-25 18:07:30 +0000277
Tobias Grosserbc132602015-09-05 09:56:54 +0000278 copyInstScalar(Stmt, Inst, BBMap, LTS);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000279}
280
Tobias Grosserbc132602015-09-05 09:56:54 +0000281void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000282 isl_id_to_ast_expr *NewAccesses) {
Johannes Doerfert275a1752015-02-24 16:16:32 +0000283 assert(Stmt.isBlockStmt() &&
284 "Only block statements can be copied by the block generator");
285
286 ValueMapT BBMap;
287
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000288 BasicBlock *BB = Stmt.getBasicBlock();
Tobias Grosserbc132602015-09-05 09:56:54 +0000289 copyBB(Stmt, BB, BBMap, LTS, NewAccesses);
Johannes Doerfert275a1752015-02-24 16:16:32 +0000290}
291
Johannes Doerfert514f6ef2015-02-27 18:29:04 +0000292BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) {
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +0000293 BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(),
294 &*Builder.GetInsertPoint(), &DT, &LI);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000295 CopyBB->setName("polly.stmt." + BB->getName());
Johannes Doerfert514f6ef2015-02-27 18:29:04 +0000296 return CopyBB;
297}
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000298
Johannes Doerfert514f6ef2015-02-27 18:29:04 +0000299BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,
Tobias Grosserbc132602015-09-05 09:56:54 +0000300 ValueMapT &BBMap, LoopToScevMapT &LTS,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000301 isl_id_to_ast_expr *NewAccesses) {
Johannes Doerfert514f6ef2015-02-27 18:29:04 +0000302 BasicBlock *CopyBB = splitBB(BB);
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +0000303 Builder.SetInsertPoint(&CopyBB->front());
Michael Kruse225f0d12015-10-17 21:36:00 +0000304 generateScalarLoads(Stmt, BBMap);
305
Tobias Grosserbc132602015-09-05 09:56:54 +0000306 copyBB(Stmt, BB, CopyBB, BBMap, LTS, NewAccesses);
Michael Kruse225f0d12015-10-17 21:36:00 +0000307
308 // After a basic block was copied store all scalars that escape this block in
309 // their alloca.
310 generateScalarStores(Stmt, LTS, BBMap);
Johannes Doerfert514f6ef2015-02-27 18:29:04 +0000311 return CopyBB;
312}
313
314void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,
Tobias Grosserbc132602015-09-05 09:56:54 +0000315 ValueMapT &BBMap, LoopToScevMapT &LTS,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000316 isl_id_to_ast_expr *NewAccesses) {
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000317 EntryBB = &CopyBB->getParent()->getEntryBlock();
318
Tobias Grosser91f5b262014-06-04 08:06:40 +0000319 for (Instruction &Inst : *BB)
Tobias Grosserbc132602015-09-05 09:56:54 +0000320 copyInstruction(Stmt, &Inst, BBMap, LTS, NewAccesses);
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000321}
322
Tobias Grosser64c0ff42015-08-31 05:52:24 +0000323Value *BlockGenerator::getOrCreateAlloca(Value *ScalarBase,
324 ScalarAllocaMapTy &Map,
Tobias Grosser64c0ff42015-08-31 05:52:24 +0000325 const char *NameExt) {
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000326 // If no alloca was found create one and insert it in the entry block.
Tobias Grossere9cb5a02015-10-03 17:19:49 +0000327 if (!Map.count(ScalarBase)) {
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000328 auto *Ty = ScalarBase->getType();
Tobias Grosserb09455d2015-09-18 06:01:11 +0000329 auto NewAddr = new AllocaInst(Ty, ScalarBase->getName() + NameExt);
Tobias Grosser64c0ff42015-08-31 05:52:24 +0000330 EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +0000331 NewAddr->insertBefore(&*EntryBB->getFirstInsertionPt());
Tobias Grossere9cb5a02015-10-03 17:19:49 +0000332 Map[ScalarBase] = NewAddr;
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000333 }
334
Tobias Grossere9cb5a02015-10-03 17:19:49 +0000335 auto Addr = Map[ScalarBase];
336
Tobias Grosser5c7f16b2016-01-24 14:16:59 +0000337 if (auto NewAddr = GlobalMap.lookup(Addr))
338 return NewAddr;
Tobias Grosser64c0ff42015-08-31 05:52:24 +0000339
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000340 return Addr;
341}
342
Johannes Doerfert800e17a2016-02-02 14:16:01 +0000343Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) {
Tobias Grossera535dff2015-12-13 19:59:01 +0000344 if (Access.isPHIKind())
Tobias Grosserb8d27aa2015-10-18 00:51:13 +0000345 return getOrCreatePHIAlloca(Access.getBaseAddr());
346 else
347 return getOrCreateScalarAlloca(Access.getBaseAddr());
Tobias Grossera4f09882015-10-17 22:16:00 +0000348}
349
350Value *BlockGenerator::getOrCreateAlloca(const ScopArrayInfo *Array) {
Tobias Grossera535dff2015-12-13 19:59:01 +0000351 if (Array->isPHIKind())
Tobias Grossera4f09882015-10-17 22:16:00 +0000352 return getOrCreatePHIAlloca(Array->getBasePtr());
Tobias Grosserf8d55f72015-08-29 18:12:03 +0000353 else
Tobias Grossera4f09882015-10-17 22:16:00 +0000354 return getOrCreateScalarAlloca(Array->getBasePtr());
Tobias Grosserf8d55f72015-08-29 18:12:03 +0000355}
356
Tobias Grosserbc132602015-09-05 09:56:54 +0000357Value *BlockGenerator::getOrCreateScalarAlloca(Value *ScalarBase) {
358 return getOrCreateAlloca(ScalarBase, ScalarMap, ".s2a");
Tobias Grosserb79a67d2015-08-28 08:23:35 +0000359}
360
Tobias Grosserbc132602015-09-05 09:56:54 +0000361Value *BlockGenerator::getOrCreatePHIAlloca(Value *ScalarBase) {
362 return getOrCreateAlloca(ScalarBase, PHIOpMap, ".phiops");
Tobias Grosserb79a67d2015-08-28 08:23:35 +0000363}
364
Johannes Doerfert38a012c2016-05-23 09:14:07 +0000365void BlockGenerator::handleOutsideUsers(const Scop &S, Instruction *Inst) {
Tobias Grosser29854002015-08-30 15:03:59 +0000366 // If there are escape users we get the alloca for this instruction and put it
367 // in the EscapeMap for later finalization. Lastly, if the instruction was
368 // copied multiple times we already did this and can exit.
Michael Kruseacb6ade2015-08-18 17:25:48 +0000369 if (EscapeMap.count(Inst))
370 return;
Johannes Doerferte69e1142015-08-18 11:56:00 +0000371
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000372 EscapeUserVectorTy EscapeUsers;
373 for (User *U : Inst->users()) {
374
375 // Non-instruction user will never escape.
376 Instruction *UI = dyn_cast<Instruction>(U);
377 if (!UI)
378 continue;
379
Johannes Doerfert952b5302016-05-23 12:40:48 +0000380 if (S.contains(UI))
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000381 continue;
382
383 EscapeUsers.push_back(UI);
384 }
385
386 // Exit if no escape uses were found.
387 if (EscapeUsers.empty())
388 return;
389
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000390 // Get or create an escape alloca for this instruction.
Johannes Doerfert38a012c2016-05-23 09:14:07 +0000391 auto *ScalarAddr = getOrCreateScalarAlloca(Inst);
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000392
393 // Remember that this instruction has escape uses and the escape alloca.
394 EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers));
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000395}
396
Michael Kruse225f0d12015-10-17 21:36:00 +0000397void BlockGenerator::generateScalarLoads(ScopStmt &Stmt, ValueMapT &BBMap) {
398 for (MemoryAccess *MA : Stmt) {
Tobias Grossera535dff2015-12-13 19:59:01 +0000399 if (MA->isArrayKind() || MA->isWrite())
Tobias Grosserd4dd6ec2015-07-27 17:57:58 +0000400 continue;
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000401
Michael Krusee2bccbb2015-09-18 19:59:43 +0000402 auto *Address = getOrCreateAlloca(*MA);
Michael Kruseeac97262016-02-24 22:08:14 +0000403 assert((!isa<Instruction>(Address) ||
404 DT.dominates(cast<Instruction>(Address)->getParent(),
405 Builder.GetInsertBlock())) &&
406 "Domination violation");
Michael Krusee2bccbb2015-09-18 19:59:43 +0000407 BBMap[MA->getBaseAddr()] =
Tobias Grosser2fc50df2015-08-30 19:51:01 +0000408 Builder.CreateLoad(Address, Address->getName() + ".reload");
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000409 }
410}
411
Michael Kruse225f0d12015-10-17 21:36:00 +0000412void BlockGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
Tobias Grosserbc132602015-09-05 09:56:54 +0000413 ValueMapT &BBMap) {
Tobias Grosserf2cdd142016-01-26 10:01:35 +0000414 Loop *L = LI.getLoopFor(Stmt.getBasicBlock());
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000415
Michael Kruse225f0d12015-10-17 21:36:00 +0000416 assert(Stmt.isBlockStmt() && "Region statements need to use the "
417 "generateScalarStores() function in the "
418 "RegionGenerator");
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000419
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000420 for (MemoryAccess *MA : Stmt) {
Tobias Grossera535dff2015-12-13 19:59:01 +0000421 if (MA->isArrayKind() || MA->isRead())
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000422 continue;
423
Johannes Doerfertd86f2152015-08-17 10:58:17 +0000424 Value *Val = MA->getAccessValue();
Michael Kruseee6a4fc2016-01-26 13:33:27 +0000425 if (MA->isAnyPHIKind()) {
426 assert(MA->getIncoming().size() >= 1 &&
427 "Block statements have exactly one exiting block, or multiple but "
428 "with same incoming block and value");
429 assert(std::all_of(MA->getIncoming().begin(), MA->getIncoming().end(),
430 [&](std::pair<BasicBlock *, Value *> p) -> bool {
431 return p.first == Stmt.getBasicBlock();
432 }) &&
433 "Incoming block must be statement's block");
434 Val = MA->getIncoming()[0].second;
435 }
Tobias Grosserbc132602015-09-05 09:56:54 +0000436 auto *Address = getOrCreateAlloca(*MA);
Johannes Doerfertd86f2152015-08-17 10:58:17 +0000437
Tobias Grosserf2cdd142016-01-26 10:01:35 +0000438 Val = getNewValue(Stmt, Val, BBMap, LTS, L);
Michael Kruseeac97262016-02-24 22:08:14 +0000439 assert((!isa<Instruction>(Val) ||
440 DT.dominates(cast<Instruction>(Val)->getParent(),
441 Builder.GetInsertBlock())) &&
442 "Domination violation");
443 assert((!isa<Instruction>(Address) ||
444 DT.dominates(cast<Instruction>(Address)->getParent(),
445 Builder.GetInsertBlock())) &&
446 "Domination violation");
Tobias Grosser92245222015-07-28 14:53:44 +0000447 Builder.CreateStore(Val, Address);
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000448 }
449}
450
Tobias Grosserc0091a72015-08-30 19:19:34 +0000451void BlockGenerator::createScalarInitialization(Scop &S) {
Johannes Doerfertef744432016-05-23 12:42:38 +0000452 BasicBlock *ExitBB = S.getExit();
Johannes Doerfert188542f2015-11-09 00:21:21 +0000453
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000454 // The split block __just before__ the region and optimized region.
Johannes Doerfertef744432016-05-23 12:42:38 +0000455 BasicBlock *SplitBB = S.getEnteringBlock();
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000456 BranchInst *SplitBBTerm = cast<BranchInst>(SplitBB->getTerminator());
457 assert(SplitBBTerm->getNumSuccessors() == 2 && "Bad region entering block!");
458
459 // Get the start block of the __optimized__ region.
460 BasicBlock *StartBB = SplitBBTerm->getSuccessor(0);
Johannes Doerfertef744432016-05-23 12:42:38 +0000461 if (StartBB == S.getEntry())
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000462 StartBB = SplitBBTerm->getSuccessor(1);
463
Johannes Doerfertfb19dd62015-09-26 20:57:59 +0000464 Builder.SetInsertPoint(StartBB->getTerminator());
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000465
Tobias Grosserc0091a72015-08-30 19:19:34 +0000466 for (auto &Pair : S.arrays()) {
467 auto &Array = Pair.second;
468 if (Array->getNumberOfDimensions() != 0)
469 continue;
Tobias Grossera535dff2015-12-13 19:59:01 +0000470 if (Array->isPHIKind()) {
Tobias Grosserc0091a72015-08-30 19:19:34 +0000471 // For PHI nodes, the only values we need to store are the ones that
472 // reach the PHI node from outside the region. In general there should
473 // only be one such incoming edge and this edge should enter through
474 // 'SplitBB'.
475 auto PHI = cast<PHINode>(Array->getBasePtr());
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000476
Tobias Grosserc0091a72015-08-30 19:19:34 +0000477 for (auto BI = PHI->block_begin(), BE = PHI->block_end(); BI != BE; BI++)
Johannes Doerfert952b5302016-05-23 12:40:48 +0000478 if (!S.contains(*BI) && *BI != SplitBB)
Tobias Grosserc0091a72015-08-30 19:19:34 +0000479 llvm_unreachable("Incoming edges from outside the scop should always "
480 "come from SplitBB");
481
482 int Idx = PHI->getBasicBlockIndex(SplitBB);
483 if (Idx < 0)
484 continue;
485
486 Value *ScalarValue = PHI->getIncomingValue(Idx);
487
Tobias Grosserbc132602015-09-05 09:56:54 +0000488 Builder.CreateStore(ScalarValue, getOrCreatePHIAlloca(PHI));
Tobias Grosserc0091a72015-08-30 19:19:34 +0000489 continue;
490 }
491
492 auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());
493
Johannes Doerfert952b5302016-05-23 12:40:48 +0000494 if (Inst && S.contains(Inst))
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000495 continue;
496
Johannes Doerfert188542f2015-11-09 00:21:21 +0000497 // PHI nodes that are not marked as such in their SAI object are either exit
498 // PHI nodes we model as common scalars but without initialization, or
499 // incoming phi nodes that need to be initialized. Check if the first is the
500 // case for Inst and do not create and initialize memory if so.
501 if (auto *PHI = dyn_cast_or_null<PHINode>(Inst))
502 if (!S.hasSingleExitEdge() && PHI->getBasicBlockIndex(ExitBB) >= 0)
503 continue;
Johannes Doerfert717b8662015-09-08 21:44:27 +0000504
Tobias Grosserc0091a72015-08-30 19:19:34 +0000505 Builder.CreateStore(Array->getBasePtr(),
Tobias Grosserbc132602015-09-05 09:56:54 +0000506 getOrCreateScalarAlloca(Array->getBasePtr()));
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000507 }
508}
509
Johannes Doerfertef744432016-05-23 12:42:38 +0000510void BlockGenerator::createScalarFinalization(Scop &S) {
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000511 // The exit block of the __unoptimized__ region.
Johannes Doerfertef744432016-05-23 12:42:38 +0000512 BasicBlock *ExitBB = S.getExitingBlock();
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000513 // The merge block __just after__ the region and the optimized region.
Johannes Doerfertef744432016-05-23 12:42:38 +0000514 BasicBlock *MergeBB = S.getExit();
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000515
516 // The exit block of the __optimized__ region.
517 BasicBlock *OptExitBB = *(pred_begin(MergeBB));
518 if (OptExitBB == ExitBB)
519 OptExitBB = *(++pred_begin(MergeBB));
520
521 Builder.SetInsertPoint(OptExitBB->getTerminator());
522 for (const auto &EscapeMapping : EscapeMap) {
523 // Extract the escaping instruction and the escaping users as well as the
524 // alloca the instruction was demoted to.
525 Instruction *EscapeInst = EscapeMapping.getFirst();
526 const auto &EscapeMappingValue = EscapeMapping.getSecond();
527 const EscapeUserVectorTy &EscapeUsers = EscapeMappingValue.second;
Tobias Grosser64c0ff42015-08-31 05:52:24 +0000528 Value *ScalarAddr = EscapeMappingValue.first;
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000529
530 // Reload the demoted instruction in the optimized version of the SCoP.
Johannes Doerfertd8b6ad22015-10-18 12:36:42 +0000531 Value *EscapeInstReload =
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000532 Builder.CreateLoad(ScalarAddr, EscapeInst->getName() + ".final_reload");
Johannes Doerfertd8b6ad22015-10-18 12:36:42 +0000533 EscapeInstReload =
534 Builder.CreateBitOrPointerCast(EscapeInstReload, EscapeInst->getType());
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000535
536 // Create the merge PHI that merges the optimized and unoptimized version.
537 PHINode *MergePHI = PHINode::Create(EscapeInst->getType(), 2,
538 EscapeInst->getName() + ".merge");
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +0000539 MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());
Johannes Doerfertecff11d2015-05-22 23:43:58 +0000540
541 // Add the respective values to the merge PHI.
542 MergePHI->addIncoming(EscapeInstReload, OptExitBB);
543 MergePHI->addIncoming(EscapeInst, ExitBB);
544
545 // The information of scalar evolution about the escaping instruction needs
546 // to be revoked so the new merged instruction will be used.
547 if (SE.isSCEVable(EscapeInst->getType()))
548 SE.forgetValue(EscapeInst);
549
550 // Replace all uses of the demoted instruction with the merge PHI.
551 for (Instruction *EUser : EscapeUsers)
552 EUser->replaceUsesOfWith(EscapeInst, MergePHI);
553 }
554}
555
Tobias Grosserffa24462015-10-17 08:54:13 +0000556void BlockGenerator::findOutsideUsers(Scop &S) {
Tobias Grosserffa24462015-10-17 08:54:13 +0000557 for (auto &Pair : S.arrays()) {
558 auto &Array = Pair.second;
559
560 if (Array->getNumberOfDimensions() != 0)
561 continue;
562
Tobias Grossera535dff2015-12-13 19:59:01 +0000563 if (Array->isPHIKind())
Tobias Grosserffa24462015-10-17 08:54:13 +0000564 continue;
565
566 auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());
567
568 if (!Inst)
569 continue;
570
571 // Scop invariant hoisting moves some of the base pointers out of the scop.
572 // We can ignore these, as the invariant load hoisting already registers the
573 // relevant outside users.
Johannes Doerfert952b5302016-05-23 12:40:48 +0000574 if (!S.contains(Inst))
Tobias Grosserffa24462015-10-17 08:54:13 +0000575 continue;
576
Johannes Doerfert38a012c2016-05-23 09:14:07 +0000577 handleOutsideUsers(S, Inst);
Tobias Grosserffa24462015-10-17 08:54:13 +0000578 }
579}
580
Tobias Grosser27d742d2015-10-24 17:41:29 +0000581void BlockGenerator::createExitPHINodeMerges(Scop &S) {
582 if (S.hasSingleExitEdge())
583 return;
584
Johannes Doerfertef744432016-05-23 12:42:38 +0000585 auto *ExitBB = S.getExitingBlock();
586 auto *MergeBB = S.getExit();
Tobias Grosser27d742d2015-10-24 17:41:29 +0000587 auto *AfterMergeBB = MergeBB->getSingleSuccessor();
588 BasicBlock *OptExitBB = *(pred_begin(MergeBB));
589 if (OptExitBB == ExitBB)
590 OptExitBB = *(++pred_begin(MergeBB));
591
592 Builder.SetInsertPoint(OptExitBB->getTerminator());
593
594 for (auto &Pair : S.arrays()) {
595 auto &SAI = Pair.second;
596 auto *Val = SAI->getBasePtr();
597
Michael Krusefaedfcb2016-03-03 17:20:43 +0000598 // Only Value-like scalars need a merge PHI. Exit block PHIs receive either
599 // the original PHI's value or the reloaded incoming values from the
600 // generated code. An llvm::Value is merged between the original code's
601 // value or the generated one.
602 if (!SAI->isValueKind() && !SAI->isExitPHIKind())
603 continue;
604
Tobias Grosser27d742d2015-10-24 17:41:29 +0000605 PHINode *PHI = dyn_cast<PHINode>(Val);
606 if (!PHI)
607 continue;
608
Tobias Grossera3f6eda2015-10-24 19:01:09 +0000609 if (PHI->getParent() != AfterMergeBB)
Tobias Grosser27d742d2015-10-24 17:41:29 +0000610 continue;
Tobias Grosser27d742d2015-10-24 17:41:29 +0000611
612 std::string Name = PHI->getName();
613 Value *ScalarAddr = getOrCreateScalarAlloca(PHI);
614 Value *Reload = Builder.CreateLoad(ScalarAddr, Name + ".ph.final_reload");
615 Reload = Builder.CreateBitOrPointerCast(Reload, PHI->getType());
616 Value *OriginalValue = PHI->getIncomingValueForBlock(MergeBB);
Michael Krusefaedfcb2016-03-03 17:20:43 +0000617 assert((!isa<Instruction>(OriginalValue) ||
618 cast<Instruction>(OriginalValue)->getParent() != MergeBB) &&
619 "Original value must no be one we just generated.");
Tobias Grosser27d742d2015-10-24 17:41:29 +0000620 auto *MergePHI = PHINode::Create(PHI->getType(), 2, Name + ".ph.merge");
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +0000621 MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());
Tobias Grosser27d742d2015-10-24 17:41:29 +0000622 MergePHI->addIncoming(Reload, OptExitBB);
623 MergePHI->addIncoming(OriginalValue, ExitBB);
624 int Idx = PHI->getBasicBlockIndex(MergeBB);
625 PHI->setIncomingValue(Idx, MergePHI);
626 }
627}
628
Tobias Grosserffa24462015-10-17 08:54:13 +0000629void BlockGenerator::finalizeSCoP(Scop &S) {
630 findOutsideUsers(S);
Tobias Grosserc0091a72015-08-30 19:19:34 +0000631 createScalarInitialization(S);
Tobias Grosser27d742d2015-10-24 17:41:29 +0000632 createExitPHINodeMerges(S);
Johannes Doerfertef744432016-05-23 12:42:38 +0000633 createScalarFinalization(S);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000634}
635
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000636VectorBlockGenerator::VectorBlockGenerator(BlockGenerator &BlockGen,
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000637 std::vector<LoopToScevMapT> &VLTS,
638 isl_map *Schedule)
Tobias Grosserbc132602015-09-05 09:56:54 +0000639 : BlockGenerator(BlockGen), VLTS(VLTS), Schedule(Schedule) {
Sebastian Popa00a0292012-12-18 07:46:06 +0000640 assert(Schedule && "No statement domain provided");
641}
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000642
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000643Value *VectorBlockGenerator::getVectorValue(ScopStmt &Stmt, Value *Old,
Tobias Grossere602a072013-05-07 07:30:56 +0000644 ValueMapT &VectorMap,
645 VectorValueMapT &ScalarMaps,
646 Loop *L) {
Hongbin Zhengfe11e282013-06-29 13:22:15 +0000647 if (Value *NewValue = VectorMap.lookup(Old))
648 return NewValue;
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000649
650 int Width = getVectorWidth();
651
652 Value *Vector = UndefValue::get(VectorType::get(Old->getType(), Width));
653
654 for (int Lane = 0; Lane < Width; Lane++)
Tobias Grosserc14582f2013-02-05 18:01:29 +0000655 Vector = Builder.CreateInsertElement(
Tobias Grosserbc132602015-09-05 09:56:54 +0000656 Vector, getNewValue(Stmt, Old, ScalarMaps[Lane], VLTS[Lane], L),
Tobias Grosser7242ad92013-02-22 08:07:06 +0000657 Builder.getInt32(Lane));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000658
659 VectorMap[Old] = Vector;
660
661 return Vector;
662}
663
664Type *VectorBlockGenerator::getVectorPtrTy(const Value *Val, int Width) {
665 PointerType *PointerTy = dyn_cast<PointerType>(Val->getType());
666 assert(PointerTy && "PointerType expected");
667
668 Type *ScalarType = PointerTy->getElementType();
669 VectorType *VectorType = VectorType::get(ScalarType, Width);
670
671 return PointerType::getUnqual(VectorType);
672}
673
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000674Value *VectorBlockGenerator::generateStrideOneLoad(
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000675 ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000676 __isl_keep isl_id_to_ast_expr *NewAccesses, bool NegativeStride = false) {
Tobias Grosser0dd463f2014-03-19 19:27:24 +0000677 unsigned VectorWidth = getVectorWidth();
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000678 auto *Pointer = Load->getPointerOperand();
Tobias Grosser0dd463f2014-03-19 19:27:24 +0000679 Type *VectorPtrType = getVectorPtrTy(Pointer, VectorWidth);
680 unsigned Offset = NegativeStride ? VectorWidth - 1 : 0;
681
Michael Kruse8f25b0c2016-02-25 15:52:43 +0000682 Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[Offset],
683 VLTS[Offset], NewAccesses);
Tobias Grosserc14582f2013-02-05 18:01:29 +0000684 Value *VectorPtr =
685 Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr");
686 LoadInst *VecLoad =
687 Builder.CreateLoad(VectorPtr, Load->getName() + "_p_vec_full");
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000688 if (!Aligned)
689 VecLoad->setAlignment(8);
690
Tobias Grosser0dd463f2014-03-19 19:27:24 +0000691 if (NegativeStride) {
692 SmallVector<Constant *, 16> Indices;
693 for (int i = VectorWidth - 1; i >= 0; i--)
694 Indices.push_back(ConstantInt::get(Builder.getInt32Ty(), i));
695 Constant *SV = llvm::ConstantVector::get(Indices);
696 Value *RevVecLoad = Builder.CreateShuffleVector(
697 VecLoad, VecLoad, SV, Load->getName() + "_reverse");
698 return RevVecLoad;
699 }
700
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000701 return VecLoad;
702}
703
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000704Value *VectorBlockGenerator::generateStrideZeroLoad(
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000705 ScopStmt &Stmt, LoadInst *Load, ValueMapT &BBMap,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000706 __isl_keep isl_id_to_ast_expr *NewAccesses) {
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000707 auto *Pointer = Load->getPointerOperand();
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000708 Type *VectorPtrType = getVectorPtrTy(Pointer, 1);
Michael Kruse70131d32016-01-27 17:09:17 +0000709 Value *NewPointer =
710 generateLocationAccessed(Stmt, Load, BBMap, VLTS[0], NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000711 Value *VectorPtr = Builder.CreateBitCast(NewPointer, VectorPtrType,
712 Load->getName() + "_p_vec_p");
Tobias Grosserc14582f2013-02-05 18:01:29 +0000713 LoadInst *ScalarLoad =
714 Builder.CreateLoad(VectorPtr, Load->getName() + "_p_splat_one");
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000715
716 if (!Aligned)
717 ScalarLoad->setAlignment(8);
718
Tobias Grosserc14582f2013-02-05 18:01:29 +0000719 Constant *SplatVector = Constant::getNullValue(
720 VectorType::get(Builder.getInt32Ty(), getVectorWidth()));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000721
Tobias Grosserc14582f2013-02-05 18:01:29 +0000722 Value *VectorLoad = Builder.CreateShuffleVector(
723 ScalarLoad, ScalarLoad, SplatVector, Load->getName() + "_p_splat");
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000724 return VectorLoad;
725}
726
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000727Value *VectorBlockGenerator::generateUnknownStrideLoad(
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000728 ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps,
Johannes Doerfert09e36972015-10-07 20:17:36 +0000729 __isl_keep isl_id_to_ast_expr *NewAccesses) {
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000730 int VectorWidth = getVectorWidth();
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000731 auto *Pointer = Load->getPointerOperand();
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000732 VectorType *VectorType = VectorType::get(
Tobias Grosserc14582f2013-02-05 18:01:29 +0000733 dyn_cast<PointerType>(Pointer->getType())->getElementType(), VectorWidth);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000734
735 Value *Vector = UndefValue::get(VectorType);
736
737 for (int i = 0; i < VectorWidth; i++) {
Michael Kruse70131d32016-01-27 17:09:17 +0000738 Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[i],
739 VLTS[i], NewAccesses);
Tobias Grosserc14582f2013-02-05 18:01:29 +0000740 Value *ScalarLoad =
741 Builder.CreateLoad(NewPointer, Load->getName() + "_p_scalar_");
742 Vector = Builder.CreateInsertElement(
743 Vector, ScalarLoad, Builder.getInt32(i), Load->getName() + "_p_vec_");
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000744 }
745
746 return Vector;
747}
748
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000749void VectorBlockGenerator::generateLoad(
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000750 ScopStmt &Stmt, LoadInst *Load, ValueMapT &VectorMap,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000751 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
Johannes Doerfertc1db67e2015-09-29 23:47:21 +0000752 if (Value *PreloadLoad = GlobalMap.lookup(Load)) {
753 VectorMap[Load] = Builder.CreateVectorSplat(getVectorWidth(), PreloadLoad,
754 Load->getName() + "_p");
755 return;
756 }
757
Tobias Grosser28736452015-03-23 07:00:36 +0000758 if (!VectorType::isValidElementType(Load->getType())) {
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000759 for (int i = 0; i < getVectorWidth(); i++)
Tobias Grosserbc132602015-09-05 09:56:54 +0000760 ScalarMaps[i][Load] =
761 generateScalarLoad(Stmt, Load, ScalarMaps[i], VLTS[i], NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000762 return;
763 }
764
Tobias Grosser184a4922015-12-15 23:50:01 +0000765 const MemoryAccess &Access = Stmt.getArrayAccessFor(Load);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000766
Tobias Grosser95493982014-04-18 09:46:35 +0000767 // Make sure we have scalar values available to access the pointer to
768 // the data location.
769 extractScalarValues(Load, VectorMap, ScalarMaps);
770
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000771 Value *NewLoad;
Sebastian Popa00a0292012-12-18 07:46:06 +0000772 if (Access.isStrideZero(isl_map_copy(Schedule)))
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000773 NewLoad = generateStrideZeroLoad(Stmt, Load, ScalarMaps[0], NewAccesses);
Sebastian Popa00a0292012-12-18 07:46:06 +0000774 else if (Access.isStrideOne(isl_map_copy(Schedule)))
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000775 NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses);
Tobias Grosser0dd463f2014-03-19 19:27:24 +0000776 else if (Access.isStrideX(isl_map_copy(Schedule), -1))
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000777 NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses, true);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000778 else
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000779 NewLoad = generateUnknownStrideLoad(Stmt, Load, ScalarMaps, NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000780
781 VectorMap[Load] = NewLoad;
782}
783
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000784void VectorBlockGenerator::copyUnaryInst(ScopStmt &Stmt, UnaryInstruction *Inst,
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000785 ValueMapT &VectorMap,
786 VectorValueMapT &ScalarMaps) {
787 int VectorWidth = getVectorWidth();
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000788 Value *NewOperand = getVectorValue(Stmt, Inst->getOperand(0), VectorMap,
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000789 ScalarMaps, getLoopForStmt(Stmt));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000790
791 assert(isa<CastInst>(Inst) && "Can not generate vector code for instruction");
792
793 const CastInst *Cast = dyn_cast<CastInst>(Inst);
794 VectorType *DestType = VectorType::get(Inst->getType(), VectorWidth);
795 VectorMap[Inst] = Builder.CreateCast(Cast->getOpcode(), NewOperand, DestType);
796}
797
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000798void VectorBlockGenerator::copyBinaryInst(ScopStmt &Stmt, BinaryOperator *Inst,
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000799 ValueMapT &VectorMap,
800 VectorValueMapT &ScalarMaps) {
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000801 Loop *L = getLoopForStmt(Stmt);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000802 Value *OpZero = Inst->getOperand(0);
803 Value *OpOne = Inst->getOperand(1);
804
805 Value *NewOpZero, *NewOpOne;
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000806 NewOpZero = getVectorValue(Stmt, OpZero, VectorMap, ScalarMaps, L);
807 NewOpOne = getVectorValue(Stmt, OpOne, VectorMap, ScalarMaps, L);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000808
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000809 Value *NewInst = Builder.CreateBinOp(Inst->getOpcode(), NewOpZero, NewOpOne,
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000810 Inst->getName() + "p_vec");
811 VectorMap[Inst] = NewInst;
812}
813
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000814void VectorBlockGenerator::copyStore(
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000815 ScopStmt &Stmt, StoreInst *Store, ValueMapT &VectorMap,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000816 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
Tobias Grosser184a4922015-12-15 23:50:01 +0000817 const MemoryAccess &Access = Stmt.getArrayAccessFor(Store);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000818
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000819 auto *Pointer = Store->getPointerOperand();
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000820 Value *Vector = getVectorValue(Stmt, Store->getValueOperand(), VectorMap,
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +0000821 ScalarMaps, getLoopForStmt(Stmt));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000822
Tobias Grosser50fd7012014-04-17 23:13:49 +0000823 // Make sure we have scalar values available to access the pointer to
824 // the data location.
825 extractScalarValues(Store, VectorMap, ScalarMaps);
826
Sebastian Popa00a0292012-12-18 07:46:06 +0000827 if (Access.isStrideOne(isl_map_copy(Schedule))) {
Johannes Doerfert1947f862014-10-08 20:18:32 +0000828 Type *VectorPtrType = getVectorPtrTy(Pointer, getVectorWidth());
Michael Kruse70131d32016-01-27 17:09:17 +0000829 Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[0],
830 VLTS[0], NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000831
Tobias Grosserc14582f2013-02-05 18:01:29 +0000832 Value *VectorPtr =
833 Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr");
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000834 StoreInst *Store = Builder.CreateStore(Vector, VectorPtr);
835
836 if (!Aligned)
837 Store->setAlignment(8);
838 } else {
839 for (unsigned i = 0; i < ScalarMaps.size(); i++) {
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000840 Value *Scalar = Builder.CreateExtractElement(Vector, Builder.getInt32(i));
Michael Kruse70131d32016-01-27 17:09:17 +0000841 Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[i],
842 VLTS[i], NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000843 Builder.CreateStore(Scalar, NewPointer);
844 }
845 }
846}
847
848bool VectorBlockGenerator::hasVectorOperands(const Instruction *Inst,
849 ValueMapT &VectorMap) {
Tobias Grosser91f5b262014-06-04 08:06:40 +0000850 for (Value *Operand : Inst->operands())
851 if (VectorMap.count(Operand))
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000852 return true;
853 return false;
854}
855
856bool VectorBlockGenerator::extractScalarValues(const Instruction *Inst,
857 ValueMapT &VectorMap,
858 VectorValueMapT &ScalarMaps) {
859 bool HasVectorOperand = false;
860 int VectorWidth = getVectorWidth();
861
Tobias Grosser91f5b262014-06-04 08:06:40 +0000862 for (Value *Operand : Inst->operands()) {
863 ValueMapT::iterator VecOp = VectorMap.find(Operand);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000864
865 if (VecOp == VectorMap.end())
866 continue;
867
868 HasVectorOperand = true;
869 Value *NewVector = VecOp->second;
870
871 for (int i = 0; i < VectorWidth; ++i) {
872 ValueMapT &SM = ScalarMaps[i];
873
874 // If there is one scalar extracted, all scalar elements should have
875 // already been extracted by the code here. So no need to check for the
876 // existance of all of them.
Tobias Grosser91f5b262014-06-04 08:06:40 +0000877 if (SM.count(Operand))
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000878 break;
879
Tobias Grosser91f5b262014-06-04 08:06:40 +0000880 SM[Operand] =
881 Builder.CreateExtractElement(NewVector, Builder.getInt32(i));
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000882 }
883 }
884
885 return HasVectorOperand;
886}
887
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000888void VectorBlockGenerator::copyInstScalarized(
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000889 ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000890 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000891 bool HasVectorOperand;
892 int VectorWidth = getVectorWidth();
893
894 HasVectorOperand = extractScalarValues(Inst, VectorMap, ScalarMaps);
895
896 for (int VectorLane = 0; VectorLane < getVectorWidth(); VectorLane++)
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000897 BlockGenerator::copyInstruction(Stmt, Inst, ScalarMaps[VectorLane],
Tobias Grosserbc132602015-09-05 09:56:54 +0000898 VLTS[VectorLane], NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000899
900 if (!VectorType::isValidElementType(Inst->getType()) || !HasVectorOperand)
901 return;
902
903 // Make the result available as vector value.
904 VectorType *VectorType = VectorType::get(Inst->getType(), VectorWidth);
905 Value *Vector = UndefValue::get(VectorType);
906
907 for (int i = 0; i < VectorWidth; i++)
908 Vector = Builder.CreateInsertElement(Vector, ScalarMaps[i][Inst],
909 Builder.getInt32(i));
910
911 VectorMap[Inst] = Vector;
912}
913
Tobias Grosserbc132602015-09-05 09:56:54 +0000914int VectorBlockGenerator::getVectorWidth() { return VLTS.size(); }
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000915
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000916void VectorBlockGenerator::copyInstruction(
Tobias Grosser2f1acac2015-10-04 10:18:45 +0000917 ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000918 VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000919 // Terminator instructions control the control flow. They are explicitly
920 // expressed in the clast and do not need to be copied.
921 if (Inst->isTerminator())
922 return;
923
Johannes Doerfert5dced262015-12-22 19:08:49 +0000924 if (canSyntheziseInStmt(Stmt, Inst))
Tobias Grossere71c6ab2012-04-27 16:36:14 +0000925 return;
926
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000927 if (auto *Load = dyn_cast<LoadInst>(Inst)) {
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000928 generateLoad(Stmt, Load, VectorMap, ScalarMaps, NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000929 return;
930 }
931
932 if (hasVectorOperands(Inst, VectorMap)) {
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000933 if (auto *Store = dyn_cast<StoreInst>(Inst)) {
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000934 copyStore(Stmt, Store, VectorMap, ScalarMaps, NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000935 return;
936 }
937
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000938 if (auto *Unary = dyn_cast<UnaryInstruction>(Inst)) {
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000939 copyUnaryInst(Stmt, Unary, VectorMap, ScalarMaps);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000940 return;
941 }
942
Tobias Grosser9646e3f2015-10-04 10:18:39 +0000943 if (auto *Binary = dyn_cast<BinaryOperator>(Inst)) {
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000944 copyBinaryInst(Stmt, Binary, VectorMap, ScalarMaps);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000945 return;
946 }
947
948 // Falltrough: We generate scalar instructions, if we don't know how to
949 // generate vector code.
950 }
951
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000952 copyInstScalarized(Stmt, Inst, VectorMap, ScalarMaps, NewAccesses);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000953}
954
Tobias Grossera69d4f02015-12-15 23:49:58 +0000955void VectorBlockGenerator::generateScalarVectorLoads(
956 ScopStmt &Stmt, ValueMapT &VectorBlockMap) {
957 for (MemoryAccess *MA : Stmt) {
958 if (MA->isArrayKind() || MA->isWrite())
959 continue;
960
961 auto *Address = getOrCreateAlloca(*MA);
962 Type *VectorPtrType = getVectorPtrTy(Address, 1);
963 Value *VectorPtr = Builder.CreateBitCast(Address, VectorPtrType,
964 Address->getName() + "_p_vec_p");
965 auto *Val = Builder.CreateLoad(VectorPtr, Address->getName() + ".reload");
966 Constant *SplatVector = Constant::getNullValue(
967 VectorType::get(Builder.getInt32Ty(), getVectorWidth()));
968
969 Value *VectorVal = Builder.CreateShuffleVector(
970 Val, Val, SplatVector, Address->getName() + "_p_splat");
971 VectorBlockMap[MA->getBaseAddr()] = VectorVal;
Tobias Grossera69d4f02015-12-15 23:49:58 +0000972 }
973}
974
975void VectorBlockGenerator::verifyNoScalarStores(ScopStmt &Stmt) {
976 for (MemoryAccess *MA : Stmt) {
977 if (MA->isArrayKind() || MA->isRead())
978 continue;
979
980 llvm_unreachable("Scalar stores not expected in vector loop");
981 }
982}
983
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +0000984void VectorBlockGenerator::copyStmt(
985 ScopStmt &Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) {
Johannes Doerfert275a1752015-02-24 16:16:32 +0000986 assert(Stmt.isBlockStmt() && "TODO: Only block statements can be copied by "
987 "the vector block generator");
988
Johannes Doerfertbe9c9112015-02-06 21:39:31 +0000989 BasicBlock *BB = Stmt.getBasicBlock();
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +0000990 BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(),
991 &*Builder.GetInsertPoint(), &DT, &LI);
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000992 CopyBB->setName("polly.stmt." + BB->getName());
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +0000993 Builder.SetInsertPoint(&CopyBB->front());
Hongbin Zheng3b11a162012-04-25 13:16:49 +0000994
995 // Create two maps that store the mapping from the original instructions of
996 // the old basic block to their copies in the new basic block. Those maps
997 // are basic block local.
998 //
999 // As vector code generation is supported there is one map for scalar values
1000 // and one for vector values.
1001 //
1002 // In case we just do scalar code generation, the vectorMap is not used and
1003 // the scalarMap has just one dimension, which contains the mapping.
1004 //
1005 // In case vector code generation is done, an instruction may either appear
1006 // in the vector map once (as it is calculating >vectorwidth< values at a
1007 // time. Or (if the values are calculated using scalar operations), it
1008 // appears once in every dimension of the scalarMap.
1009 VectorValueMapT ScalarBlockMap(getVectorWidth());
1010 ValueMapT VectorBlockMap;
1011
Tobias Grossera69d4f02015-12-15 23:49:58 +00001012 generateScalarVectorLoads(Stmt, VectorBlockMap);
1013
Tobias Grosser91f5b262014-06-04 08:06:40 +00001014 for (Instruction &Inst : *BB)
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +00001015 copyInstruction(Stmt, &Inst, VectorBlockMap, ScalarBlockMap, NewAccesses);
Tobias Grossera69d4f02015-12-15 23:49:58 +00001016
1017 verifyNoScalarStores(Stmt);
Hongbin Zheng3b11a162012-04-25 13:16:49 +00001018}
Johannes Doerfert275a1752015-02-24 16:16:32 +00001019
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001020BasicBlock *RegionGenerator::repairDominance(BasicBlock *BB,
1021 BasicBlock *BBCopy) {
Johannes Doerfert514f6ef2015-02-27 18:29:04 +00001022
1023 BasicBlock *BBIDom = DT.getNode(BB)->getIDom()->getBlock();
1024 BasicBlock *BBCopyIDom = BlockMap.lookup(BBIDom);
1025
1026 if (BBCopyIDom)
1027 DT.changeImmediateDominator(BBCopy, BBCopyIDom);
1028
1029 return BBCopyIDom;
1030}
1031
Michael Krusef33c1252016-02-25 14:08:48 +00001032// This is to determine whether an llvm::Value (defined in @p BB) is usable when
1033// leaving a subregion. The straight-forward DT.dominates(BB, R->getExitBlock())
1034// does not work in cases where the exit block has edges from outside the
1035// region. In that case the llvm::Value would never be usable in in the exit
1036// block. The RegionGenerator however creates an new exit block ('ExitBBCopy')
1037// for the subregion's exiting edges only. We need to determine whether an
1038// llvm::Value is usable in there. We do this by checking whether it dominates
1039// all exiting blocks individually.
1040static bool isDominatingSubregionExit(const DominatorTree &DT, Region *R,
1041 BasicBlock *BB) {
1042 for (auto ExitingBB : predecessors(R->getExit())) {
1043 // Check for non-subregion incoming edges.
1044 if (!R->contains(ExitingBB))
1045 continue;
1046
1047 if (!DT.dominates(BB, ExitingBB))
1048 return false;
1049 }
1050
1051 return true;
1052}
1053
1054// Find the direct dominator of the subregion's exit block if the subregion was
1055// simplified.
1056static BasicBlock *findExitDominator(DominatorTree &DT, Region *R) {
1057 BasicBlock *Common = nullptr;
1058 for (auto ExitingBB : predecessors(R->getExit())) {
1059 // Check for non-subregion incoming edges.
1060 if (!R->contains(ExitingBB))
1061 continue;
1062
1063 // First exiting edge.
1064 if (!Common) {
1065 Common = ExitingBB;
1066 continue;
1067 }
1068
1069 Common = DT.findNearestCommonDominator(Common, ExitingBB);
1070 }
1071
1072 assert(Common && R->contains(Common));
1073 return Common;
1074}
1075
Tobias Grosserbc132602015-09-05 09:56:54 +00001076void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
Tobias Grosser2d1ed0b2015-08-27 07:28:16 +00001077 isl_id_to_ast_expr *IdToAstExp) {
Johannes Doerfert275a1752015-02-24 16:16:32 +00001078 assert(Stmt.isRegionStmt() &&
Tobias Grosserd3f21832015-08-01 06:26:51 +00001079 "Only region statements can be copied by the region generator");
Johannes Doerfert275a1752015-02-24 16:16:32 +00001080
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001081 // Forget all old mappings.
1082 BlockMap.clear();
1083 RegionMaps.clear();
1084 IncompletePHINodeMap.clear();
1085
Michael Kruse225f0d12015-10-17 21:36:00 +00001086 // Collection of all values related to this subregion.
1087 ValueMapT ValueMap;
1088
Johannes Doerfert275a1752015-02-24 16:16:32 +00001089 // The region represented by the statement.
1090 Region *R = Stmt.getRegion();
1091
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001092 // Create a dedicated entry for the region where we can reload all demoted
1093 // inputs.
1094 BasicBlock *EntryBB = R->getEntry();
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +00001095 BasicBlock *EntryBBCopy = SplitBlock(Builder.GetInsertBlock(),
1096 &*Builder.GetInsertPoint(), &DT, &LI);
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001097 EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry");
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +00001098 Builder.SetInsertPoint(&EntryBBCopy->front());
Johannes Doerfert514f6ef2015-02-27 18:29:04 +00001099
Michael Krusec9937392015-11-09 23:33:40 +00001100 ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy];
1101 generateScalarLoads(Stmt, EntryBBMap);
Michael Kruse225f0d12015-10-17 21:36:00 +00001102
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001103 for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI)
1104 if (!R->contains(*PI))
1105 BlockMap[*PI] = EntryBBCopy;
Johannes Doerfert275a1752015-02-24 16:16:32 +00001106
1107 // Iterate over all blocks in the region in a breadth-first search.
1108 std::deque<BasicBlock *> Blocks;
1109 SmallPtrSet<BasicBlock *, 8> SeenBlocks;
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001110 Blocks.push_back(EntryBB);
1111 SeenBlocks.insert(EntryBB);
Johannes Doerfert275a1752015-02-24 16:16:32 +00001112
1113 while (!Blocks.empty()) {
1114 BasicBlock *BB = Blocks.front();
1115 Blocks.pop_front();
1116
Johannes Doerfert514f6ef2015-02-27 18:29:04 +00001117 // First split the block and update dominance information.
1118 BasicBlock *BBCopy = splitBB(BB);
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001119 BasicBlock *BBCopyIDom = repairDominance(BB, BBCopy);
1120
Michael Krusec9937392015-11-09 23:33:40 +00001121 // Get the mapping for this block and initialize it with either the scalar
1122 // loads from the generated entering block (which dominates all blocks of
1123 // this subregion) or the maps of the immediate dominator, if part of the
1124 // subregion. The latter necessarily includes the former.
1125 ValueMapT *InitBBMap;
1126 if (BBCopyIDom) {
1127 assert(RegionMaps.count(BBCopyIDom));
1128 InitBBMap = &RegionMaps[BBCopyIDom];
1129 } else
1130 InitBBMap = &EntryBBMap;
1131 auto Inserted = RegionMaps.insert(std::make_pair(BBCopy, *InitBBMap));
1132 ValueMapT &RegionMap = Inserted.first->second;
Johannes Doerfert514f6ef2015-02-27 18:29:04 +00001133
Johannes Doerfert275a1752015-02-24 16:16:32 +00001134 // Copy the block with the BlockGenerator.
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +00001135 Builder.SetInsertPoint(&BBCopy->front());
Tobias Grosserbc132602015-09-05 09:56:54 +00001136 copyBB(Stmt, BB, BBCopy, RegionMap, LTS, IdToAstExp);
Johannes Doerfert275a1752015-02-24 16:16:32 +00001137
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001138 // In order to remap PHI nodes we store also basic block mappings.
1139 BlockMap[BB] = BBCopy;
1140
1141 // Add values to incomplete PHI nodes waiting for this block to be copied.
1142 for (const PHINodePairTy &PHINodePair : IncompletePHINodeMap[BB])
Tobias Grosserbc132602015-09-05 09:56:54 +00001143 addOperandToPHI(Stmt, PHINodePair.first, PHINodePair.second, BB, LTS);
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001144 IncompletePHINodeMap[BB].clear();
1145
Johannes Doerfert275a1752015-02-24 16:16:32 +00001146 // And continue with new successors inside the region.
1147 for (auto SI = succ_begin(BB), SE = succ_end(BB); SI != SE; SI++)
1148 if (R->contains(*SI) && SeenBlocks.insert(*SI).second)
1149 Blocks.push_back(*SI);
Michael Kruseebffcbe2015-11-09 22:37:29 +00001150
1151 // Remember value in case it is visible after this subregion.
Michael Krusef33c1252016-02-25 14:08:48 +00001152 if (isDominatingSubregionExit(DT, R, BB))
Michael Kruseebffcbe2015-11-09 22:37:29 +00001153 ValueMap.insert(RegionMap.begin(), RegionMap.end());
Johannes Doerfert275a1752015-02-24 16:16:32 +00001154 }
1155
1156 // 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 +00001157 BasicBlock *ExitBBCopy = SplitBlock(Builder.GetInsertBlock(),
1158 &*Builder.GetInsertPoint(), &DT, &LI);
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001159 ExitBBCopy->setName("polly.stmt." + R->getExit()->getName() + ".exit");
Johannes Doerfert514f6ef2015-02-27 18:29:04 +00001160 BlockMap[R->getExit()] = ExitBBCopy;
1161
Michael Krusef33c1252016-02-25 14:08:48 +00001162 BasicBlock *ExitDomBBCopy = BlockMap.lookup(findExitDominator(DT, R));
1163 assert(ExitDomBBCopy && "Common exit dominator must be within region; at "
1164 "least the entry node must match");
1165 DT.changeImmediateDominator(ExitBBCopy, ExitDomBBCopy);
Johannes Doerfert275a1752015-02-24 16:16:32 +00001166
1167 // As the block generator doesn't handle control flow we need to add the
1168 // region control flow by hand after all blocks have been copied.
1169 for (BasicBlock *BB : SeenBlocks) {
1170
Johannes Doerfert514f6ef2015-02-27 18:29:04 +00001171 BasicBlock *BBCopy = BlockMap[BB];
Johannes Doerferte114dc02015-09-14 11:15:58 +00001172 TerminatorInst *TI = BB->getTerminator();
1173 if (isa<UnreachableInst>(TI)) {
1174 while (!BBCopy->empty())
1175 BBCopy->begin()->eraseFromParent();
1176 new UnreachableInst(BBCopy->getContext(), BBCopy);
1177 continue;
1178 }
1179
Johannes Doerfert275a1752015-02-24 16:16:32 +00001180 Instruction *BICopy = BBCopy->getTerminator();
1181
Johannes Doerfert514f6ef2015-02-27 18:29:04 +00001182 ValueMapT &RegionMap = RegionMaps[BBCopy];
1183 RegionMap.insert(BlockMap.begin(), BlockMap.end());
1184
Tobias Grosser45e79442015-08-01 09:07:57 +00001185 Builder.SetInsertPoint(BICopy);
Johannes Doerfert9a132f32015-09-28 09:33:22 +00001186 copyInstScalar(Stmt, TI, RegionMap, LTS);
Johannes Doerfert275a1752015-02-24 16:16:32 +00001187 BICopy->eraseFromParent();
1188 }
1189
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001190 // Add counting PHI nodes to all loops in the region that can be used as
1191 // replacement for SCEVs refering to the old loop.
1192 for (BasicBlock *BB : SeenBlocks) {
1193 Loop *L = LI.getLoopFor(BB);
Tobias Grosserbc29e0b2015-11-12 07:34:09 +00001194 if (L == nullptr || L->getHeader() != BB || !R->contains(L))
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001195 continue;
1196
1197 BasicBlock *BBCopy = BlockMap[BB];
1198 Value *NullVal = Builder.getInt32(0);
1199 PHINode *LoopPHI =
1200 PHINode::Create(Builder.getInt32Ty(), 2, "polly.subregion.iv");
1201 Instruction *LoopPHIInc = BinaryOperator::CreateAdd(
1202 LoopPHI, Builder.getInt32(1), "polly.subregion.iv.inc");
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +00001203 LoopPHI->insertBefore(&BBCopy->front());
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001204 LoopPHIInc->insertBefore(BBCopy->getTerminator());
1205
1206 for (auto *PredBB : make_range(pred_begin(BB), pred_end(BB))) {
1207 if (!R->contains(PredBB))
1208 continue;
1209 if (L->contains(PredBB))
1210 LoopPHI->addIncoming(LoopPHIInc, BlockMap[PredBB]);
1211 else
1212 LoopPHI->addIncoming(NullVal, BlockMap[PredBB]);
1213 }
1214
1215 for (auto *PredBBCopy : make_range(pred_begin(BBCopy), pred_end(BBCopy)))
1216 if (LoopPHI->getBasicBlockIndex(PredBBCopy) < 0)
1217 LoopPHI->addIncoming(NullVal, PredBBCopy);
1218
1219 LTS[L] = SE.getUnknown(LoopPHI);
1220 }
1221
Michael Kruse225f0d12015-10-17 21:36:00 +00001222 // Continue generating code in the exit block.
Duncan P. N. Exon Smithb8f58b52015-11-06 22:56:54 +00001223 Builder.SetInsertPoint(&*ExitBBCopy->getFirstInsertionPt());
Michael Kruse225f0d12015-10-17 21:36:00 +00001224
1225 // Write values visible to other statements.
1226 generateScalarStores(Stmt, LTS, ValueMap);
Tobias Grosser3e956022015-10-26 20:41:53 +00001227 BlockMap.clear();
1228 RegionMaps.clear();
1229 IncompletePHINodeMap.clear();
Johannes Doerfert275a1752015-02-24 16:16:32 +00001230}
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001231
Michael Kruseee6a4fc2016-01-26 13:33:27 +00001232PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT &LTS,
1233 ValueMapT &BBMap, Loop *L) {
1234 ScopStmt *Stmt = MA->getStatement();
1235 Region *SubR = Stmt->getRegion();
1236 auto Incoming = MA->getIncoming();
1237
1238 PollyIRBuilder::InsertPointGuard IPGuard(Builder);
1239 PHINode *OrigPHI = cast<PHINode>(MA->getAccessInstruction());
1240 BasicBlock *NewSubregionExit = Builder.GetInsertBlock();
1241
1242 // This can happen if the subregion is simplified after the ScopStmts
1243 // have been created; simplification happens as part of CodeGeneration.
1244 if (OrigPHI->getParent() != SubR->getExit()) {
1245 BasicBlock *FormerExit = SubR->getExitingBlock();
1246 if (FormerExit)
1247 NewSubregionExit = BlockMap.lookup(FormerExit);
1248 }
1249
1250 PHINode *NewPHI = PHINode::Create(OrigPHI->getType(), Incoming.size(),
1251 "polly." + OrigPHI->getName(),
1252 NewSubregionExit->getFirstNonPHI());
1253
1254 // Add the incoming values to the PHI.
1255 for (auto &Pair : Incoming) {
1256 BasicBlock *OrigIncomingBlock = Pair.first;
1257 BasicBlock *NewIncomingBlock = BlockMap.lookup(OrigIncomingBlock);
1258 Builder.SetInsertPoint(NewIncomingBlock->getTerminator());
1259 assert(RegionMaps.count(NewIncomingBlock));
1260 ValueMapT *LocalBBMap = &RegionMaps[NewIncomingBlock];
1261
1262 Value *OrigIncomingValue = Pair.second;
1263 Value *NewIncomingValue =
1264 getNewValue(*Stmt, OrigIncomingValue, *LocalBBMap, LTS, L);
1265 NewPHI->addIncoming(NewIncomingValue, NewIncomingBlock);
1266 }
1267
1268 return NewPHI;
1269}
1270
1271Value *RegionGenerator::getExitScalar(MemoryAccess *MA, LoopToScevMapT &LTS,
1272 ValueMapT &BBMap) {
1273 ScopStmt *Stmt = MA->getStatement();
1274
1275 // TODO: Add some test cases that ensure this is really the right choice.
1276 Loop *L = LI.getLoopFor(Stmt->getRegion()->getExit());
1277
1278 if (MA->isAnyPHIKind()) {
1279 auto Incoming = MA->getIncoming();
1280 assert(!Incoming.empty() &&
1281 "PHI WRITEs must have originate from at least one incoming block");
1282
1283 // If there is only one incoming value, we do not need to create a PHI.
1284 if (Incoming.size() == 1) {
1285 Value *OldVal = Incoming[0].second;
1286 return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
1287 }
1288
1289 return buildExitPHI(MA, LTS, BBMap, L);
1290 }
1291
1292 // MK_Value accesses leaving the subregion must dominate the exit block; just
1293 // pass the copied value
1294 Value *OldVal = MA->getAccessValue();
1295 return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
1296}
1297
Michael Kruse225f0d12015-10-17 21:36:00 +00001298void RegionGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
Tobias Grosserbc132602015-09-05 09:56:54 +00001299 ValueMapT &BBMap) {
Tobias Grosser75296902015-08-21 19:23:21 +00001300 assert(Stmt.getRegion() &&
1301 "Block statements need to use the generateScalarStores() "
1302 "function in the BlockGenerator");
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001303
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001304 for (MemoryAccess *MA : Stmt) {
Tobias Grossera535dff2015-12-13 19:59:01 +00001305 if (MA->isArrayKind() || MA->isRead())
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001306 continue;
1307
Michael Kruseee6a4fc2016-01-26 13:33:27 +00001308 Value *NewVal = getExitScalar(MA, LTS, BBMap);
1309 Value *Address = getOrCreateAlloca(*MA);
Michael Kruseeac97262016-02-24 22:08:14 +00001310 assert((!isa<Instruction>(NewVal) ||
1311 DT.dominates(cast<Instruction>(NewVal)->getParent(),
1312 Builder.GetInsertBlock())) &&
1313 "Domination violation");
1314 assert((!isa<Instruction>(Address) ||
1315 DT.dominates(cast<Instruction>(Address)->getParent(),
1316 Builder.GetInsertBlock())) &&
1317 "Domination violation");
Michael Kruseee6a4fc2016-01-26 13:33:27 +00001318 Builder.CreateStore(NewVal, Address);
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001319 }
1320}
1321
1322void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, const PHINode *PHI,
1323 PHINode *PHICopy, BasicBlock *IncomingBB,
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001324 LoopToScevMapT &LTS) {
1325 Region *StmtR = Stmt.getRegion();
1326
1327 // If the incoming block was not yet copied mark this PHI as incomplete.
1328 // Once the block will be copied the incoming value will be added.
1329 BasicBlock *BBCopy = BlockMap[IncomingBB];
1330 if (!BBCopy) {
1331 assert(StmtR->contains(IncomingBB) &&
1332 "Bad incoming block for PHI in non-affine region");
1333 IncompletePHINodeMap[IncomingBB].push_back(std::make_pair(PHI, PHICopy));
1334 return;
1335 }
1336
1337 Value *OpCopy = nullptr;
1338 if (StmtR->contains(IncomingBB)) {
1339 assert(RegionMaps.count(BBCopy) &&
1340 "Incoming PHI block did not have a BBMap");
1341 ValueMapT &BBCopyMap = RegionMaps[BBCopy];
1342
1343 Value *Op = PHI->getIncomingValueForBlock(IncomingBB);
Michael Krusedc122222015-10-19 09:19:25 +00001344
Johannes Doerfert6ba92712016-04-01 11:25:47 +00001345 // If the current insert block is different from the PHIs incoming block
1346 // change it, otherwise do not.
1347 auto IP = Builder.GetInsertPoint();
1348 if (IP->getParent() != BBCopy)
1349 Builder.SetInsertPoint(BBCopy->getTerminator());
Johannes Doerfert2c3ffc02016-02-16 12:36:14 +00001350 OpCopy = getNewValue(Stmt, Op, BBCopyMap, LTS, getLoopForStmt(Stmt));
Johannes Doerfert6ba92712016-04-01 11:25:47 +00001351 if (IP->getParent() != BBCopy)
1352 Builder.SetInsertPoint(&*IP);
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001353 } else {
1354
1355 if (PHICopy->getBasicBlockIndex(BBCopy) >= 0)
1356 return;
1357
Tobias Grosserbc132602015-09-05 09:56:54 +00001358 Value *PHIOpAddr = getOrCreatePHIAlloca(const_cast<PHINode *>(PHI));
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001359 OpCopy = new LoadInst(PHIOpAddr, PHIOpAddr->getName() + ".reload",
1360 BlockMap[IncomingBB]->getTerminator());
1361 }
1362
1363 assert(OpCopy && "Incoming PHI value was not copied properly");
1364 assert(BBCopy && "Incoming PHI block was not copied properly");
1365 PHICopy->addIncoming(OpCopy, BBCopy);
1366}
1367
Tobias Grosser2b809d12016-02-21 15:44:34 +00001368void RegionGenerator::copyPHIInstruction(ScopStmt &Stmt, PHINode *PHI,
1369 ValueMapT &BBMap,
1370 LoopToScevMapT &LTS) {
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001371 unsigned NumIncoming = PHI->getNumIncomingValues();
1372 PHINode *PHICopy =
1373 Builder.CreatePHI(PHI->getType(), NumIncoming, "polly." + PHI->getName());
1374 PHICopy->moveBefore(PHICopy->getParent()->getFirstNonPHI());
1375 BBMap[PHI] = PHICopy;
1376
1377 for (unsigned u = 0; u < NumIncoming; u++)
Tobias Grosserbc132602015-09-05 09:56:54 +00001378 addOperandToPHI(Stmt, PHI, PHICopy, PHI->getIncomingBlock(u), LTS);
Johannes Doerfertecff11d2015-05-22 23:43:58 +00001379}