1 //===- NVPTXLowerAggrCopies.cpp - ------------------------------*- 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 // \file
11 // Lower aggregate copies, memset, memcpy, memmov intrinsics into loops when
12 // the size is large or is not a compile-time constant.
13 //
14 //===----------------------------------------------------------------------===//
15
16 #include "NVPTXLowerAggrCopies.h"
17 #include "llvm/CodeGen/MachineFunctionAnalysis.h"
18 #include "llvm/CodeGen/StackProtector.h"
19 #include "llvm/IR/Constants.h"
20 #include "llvm/IR/DataLayout.h"
21 #include "llvm/IR/Function.h"
22 #include "llvm/IR/IRBuilder.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/IR/IntrinsicInst.h"
25 #include "llvm/IR/Intrinsics.h"
26 #include "llvm/IR/LLVMContext.h"
27 #include "llvm/IR/Module.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
30
31 #define DEBUG_TYPE "nvptx"
32
33 using namespace llvm;
34
35 namespace {
36
37 // actual analysis class, which is a functionpass
38 struct NVPTXLowerAggrCopies : public FunctionPass {
39 static char ID;
40
NVPTXLowerAggrCopies__anon92aa2acf0111::NVPTXLowerAggrCopies41 NVPTXLowerAggrCopies() : FunctionPass(ID) {}
42
getAnalysisUsage__anon92aa2acf0111::NVPTXLowerAggrCopies43 void getAnalysisUsage(AnalysisUsage &AU) const override {
44 AU.addPreserved<MachineFunctionAnalysis>();
45 AU.addPreserved<StackProtector>();
46 }
47
48 bool runOnFunction(Function &F) override;
49
50 static const unsigned MaxAggrCopySize = 128;
51
getPassName__anon92aa2acf0111::NVPTXLowerAggrCopies52 const char *getPassName() const override {
53 return "Lower aggregate copies/intrinsics into loops";
54 }
55 };
56
57 char NVPTXLowerAggrCopies::ID = 0;
58
59 // Lower memcpy to loop.
convertMemCpyToLoop(Instruction * ConvertedInst,Value * SrcAddr,Value * DstAddr,Value * CopyLen,bool SrcIsVolatile,bool DstIsVolatile,LLVMContext & Context,Function & F)60 void convertMemCpyToLoop(Instruction *ConvertedInst, Value *SrcAddr,
61 Value *DstAddr, Value *CopyLen, bool SrcIsVolatile,
62 bool DstIsVolatile, LLVMContext &Context,
63 Function &F) {
64 Type *TypeOfCopyLen = CopyLen->getType();
65
66 BasicBlock *OrigBB = ConvertedInst->getParent();
67 BasicBlock *NewBB =
68 ConvertedInst->getParent()->splitBasicBlock(ConvertedInst, "split");
69 BasicBlock *LoopBB = BasicBlock::Create(Context, "loadstoreloop", &F, NewBB);
70
71 OrigBB->getTerminator()->setSuccessor(0, LoopBB);
72 IRBuilder<> Builder(OrigBB->getTerminator());
73
74 // SrcAddr and DstAddr are expected to be pointer types,
75 // so no check is made here.
76 unsigned SrcAS = cast<PointerType>(SrcAddr->getType())->getAddressSpace();
77 unsigned DstAS = cast<PointerType>(DstAddr->getType())->getAddressSpace();
78
79 // Cast pointers to (char *)
80 SrcAddr = Builder.CreateBitCast(SrcAddr, Builder.getInt8PtrTy(SrcAS));
81 DstAddr = Builder.CreateBitCast(DstAddr, Builder.getInt8PtrTy(DstAS));
82
83 IRBuilder<> LoopBuilder(LoopBB);
84 PHINode *LoopIndex = LoopBuilder.CreatePHI(TypeOfCopyLen, 0);
85 LoopIndex->addIncoming(ConstantInt::get(TypeOfCopyLen, 0), OrigBB);
86
87 // load from SrcAddr+LoopIndex
88 // TODO: we can leverage the align parameter of llvm.memcpy for more efficient
89 // word-sized loads and stores.
90 Value *Element =
91 LoopBuilder.CreateLoad(LoopBuilder.CreateInBoundsGEP(
92 LoopBuilder.getInt8Ty(), SrcAddr, LoopIndex),
93 SrcIsVolatile);
94 // store at DstAddr+LoopIndex
95 LoopBuilder.CreateStore(Element,
96 LoopBuilder.CreateInBoundsGEP(LoopBuilder.getInt8Ty(),
97 DstAddr, LoopIndex),
98 DstIsVolatile);
99
100 // The value for LoopIndex coming from backedge is (LoopIndex + 1)
101 Value *NewIndex =
102 LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(TypeOfCopyLen, 1));
103 LoopIndex->addIncoming(NewIndex, LoopBB);
104
105 LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpULT(NewIndex, CopyLen), LoopBB,
106 NewBB);
107 }
108
109 // Lower memmove to IR. memmove is required to correctly copy overlapping memory
110 // regions; therefore, it has to check the relative positions of the source and
111 // destination pointers and choose the copy direction accordingly.
112 //
113 // The code below is an IR rendition of this C function:
114 //
115 // void* memmove(void* dst, const void* src, size_t n) {
116 // unsigned char* d = dst;
117 // const unsigned char* s = src;
118 // if (s < d) {
119 // // copy backwards
120 // while (n--) {
121 // d[n] = s[n];
122 // }
123 // } else {
124 // // copy forward
125 // for (size_t i = 0; i < n; ++i) {
126 // d[i] = s[i];
127 // }
128 // }
129 // return dst;
130 // }
convertMemMoveToLoop(Instruction * ConvertedInst,Value * SrcAddr,Value * DstAddr,Value * CopyLen,bool SrcIsVolatile,bool DstIsVolatile,LLVMContext & Context,Function & F)131 void convertMemMoveToLoop(Instruction *ConvertedInst, Value *SrcAddr,
132 Value *DstAddr, Value *CopyLen, bool SrcIsVolatile,
133 bool DstIsVolatile, LLVMContext &Context,
134 Function &F) {
135 Type *TypeOfCopyLen = CopyLen->getType();
136 BasicBlock *OrigBB = ConvertedInst->getParent();
137
138 // Create the a comparison of src and dst, based on which we jump to either
139 // the forward-copy part of the function (if src >= dst) or the backwards-copy
140 // part (if src < dst).
141 // SplitBlockAndInsertIfThenElse conveniently creates the basic if-then-else
142 // structure. Its block terminators (unconditional branches) are replaced by
143 // the appropriate conditional branches when the loop is built.
144 ICmpInst *PtrCompare = new ICmpInst(ConvertedInst, ICmpInst::ICMP_ULT,
145 SrcAddr, DstAddr, "compare_src_dst");
146 TerminatorInst *ThenTerm, *ElseTerm;
147 SplitBlockAndInsertIfThenElse(PtrCompare, ConvertedInst, &ThenTerm,
148 &ElseTerm);
149
150 // Each part of the function consists of two blocks:
151 // copy_backwards: used to skip the loop when n == 0
152 // copy_backwards_loop: the actual backwards loop BB
153 // copy_forward: used to skip the loop when n == 0
154 // copy_forward_loop: the actual forward loop BB
155 BasicBlock *CopyBackwardsBB = ThenTerm->getParent();
156 CopyBackwardsBB->setName("copy_backwards");
157 BasicBlock *CopyForwardBB = ElseTerm->getParent();
158 CopyForwardBB->setName("copy_forward");
159 BasicBlock *ExitBB = ConvertedInst->getParent();
160 ExitBB->setName("memmove_done");
161
162 // Initial comparison of n == 0 that lets us skip the loops altogether. Shared
163 // between both backwards and forward copy clauses.
164 ICmpInst *CompareN =
165 new ICmpInst(OrigBB->getTerminator(), ICmpInst::ICMP_EQ, CopyLen,
166 ConstantInt::get(TypeOfCopyLen, 0), "compare_n_to_0");
167
168 // Copying backwards.
169 BasicBlock *LoopBB =
170 BasicBlock::Create(Context, "copy_backwards_loop", &F, CopyForwardBB);
171 IRBuilder<> LoopBuilder(LoopBB);
172 PHINode *LoopPhi = LoopBuilder.CreatePHI(TypeOfCopyLen, 0);
173 Value *IndexPtr = LoopBuilder.CreateSub(
174 LoopPhi, ConstantInt::get(TypeOfCopyLen, 1), "index_ptr");
175 Value *Element = LoopBuilder.CreateLoad(
176 LoopBuilder.CreateInBoundsGEP(SrcAddr, IndexPtr), "element");
177 LoopBuilder.CreateStore(Element,
178 LoopBuilder.CreateInBoundsGEP(DstAddr, IndexPtr));
179 LoopBuilder.CreateCondBr(
180 LoopBuilder.CreateICmpEQ(IndexPtr, ConstantInt::get(TypeOfCopyLen, 0)),
181 ExitBB, LoopBB);
182 LoopPhi->addIncoming(IndexPtr, LoopBB);
183 LoopPhi->addIncoming(CopyLen, CopyBackwardsBB);
184 BranchInst::Create(ExitBB, LoopBB, CompareN, ThenTerm);
185 ThenTerm->eraseFromParent();
186
187 // Copying forward.
188 BasicBlock *FwdLoopBB =
189 BasicBlock::Create(Context, "copy_forward_loop", &F, ExitBB);
190 IRBuilder<> FwdLoopBuilder(FwdLoopBB);
191 PHINode *FwdCopyPhi = FwdLoopBuilder.CreatePHI(TypeOfCopyLen, 0, "index_ptr");
192 Value *FwdElement = FwdLoopBuilder.CreateLoad(
193 FwdLoopBuilder.CreateInBoundsGEP(SrcAddr, FwdCopyPhi), "element");
194 FwdLoopBuilder.CreateStore(
195 FwdElement, FwdLoopBuilder.CreateInBoundsGEP(DstAddr, FwdCopyPhi));
196 Value *FwdIndexPtr = FwdLoopBuilder.CreateAdd(
197 FwdCopyPhi, ConstantInt::get(TypeOfCopyLen, 1), "index_increment");
198 FwdLoopBuilder.CreateCondBr(FwdLoopBuilder.CreateICmpEQ(FwdIndexPtr, CopyLen),
199 ExitBB, FwdLoopBB);
200 FwdCopyPhi->addIncoming(FwdIndexPtr, FwdLoopBB);
201 FwdCopyPhi->addIncoming(ConstantInt::get(TypeOfCopyLen, 0), CopyForwardBB);
202
203 BranchInst::Create(ExitBB, FwdLoopBB, CompareN, ElseTerm);
204 ElseTerm->eraseFromParent();
205 }
206
207 // Lower memset to loop.
convertMemSetToLoop(Instruction * ConvertedInst,Value * DstAddr,Value * CopyLen,Value * SetValue,LLVMContext & Context,Function & F)208 void convertMemSetToLoop(Instruction *ConvertedInst, Value *DstAddr,
209 Value *CopyLen, Value *SetValue, LLVMContext &Context,
210 Function &F) {
211 BasicBlock *OrigBB = ConvertedInst->getParent();
212 BasicBlock *NewBB =
213 ConvertedInst->getParent()->splitBasicBlock(ConvertedInst, "split");
214 BasicBlock *LoopBB = BasicBlock::Create(Context, "loadstoreloop", &F, NewBB);
215
216 OrigBB->getTerminator()->setSuccessor(0, LoopBB);
217 IRBuilder<> Builder(OrigBB->getTerminator());
218
219 // Cast pointer to the type of value getting stored
220 unsigned dstAS = cast<PointerType>(DstAddr->getType())->getAddressSpace();
221 DstAddr = Builder.CreateBitCast(DstAddr,
222 PointerType::get(SetValue->getType(), dstAS));
223
224 IRBuilder<> LoopBuilder(LoopBB);
225 PHINode *LoopIndex = LoopBuilder.CreatePHI(CopyLen->getType(), 0);
226 LoopIndex->addIncoming(ConstantInt::get(CopyLen->getType(), 0), OrigBB);
227
228 LoopBuilder.CreateStore(
229 SetValue,
230 LoopBuilder.CreateInBoundsGEP(SetValue->getType(), DstAddr, LoopIndex),
231 false);
232
233 Value *NewIndex =
234 LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(CopyLen->getType(), 1));
235 LoopIndex->addIncoming(NewIndex, LoopBB);
236
237 LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpULT(NewIndex, CopyLen), LoopBB,
238 NewBB);
239 }
240
runOnFunction(Function & F)241 bool NVPTXLowerAggrCopies::runOnFunction(Function &F) {
242 SmallVector<LoadInst *, 4> AggrLoads;
243 SmallVector<MemIntrinsic *, 4> MemCalls;
244
245 const DataLayout &DL = F.getParent()->getDataLayout();
246 LLVMContext &Context = F.getParent()->getContext();
247
248 // Collect all aggregate loads and mem* calls.
249 for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
250 for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;
251 ++II) {
252 if (LoadInst *LI = dyn_cast<LoadInst>(II)) {
253 if (!LI->hasOneUse())
254 continue;
255
256 if (DL.getTypeStoreSize(LI->getType()) < MaxAggrCopySize)
257 continue;
258
259 if (StoreInst *SI = dyn_cast<StoreInst>(LI->user_back())) {
260 if (SI->getOperand(0) != LI)
261 continue;
262 AggrLoads.push_back(LI);
263 }
264 } else if (MemIntrinsic *IntrCall = dyn_cast<MemIntrinsic>(II)) {
265 // Convert intrinsic calls with variable size or with constant size
266 // larger than the MaxAggrCopySize threshold.
267 if (ConstantInt *LenCI = dyn_cast<ConstantInt>(IntrCall->getLength())) {
268 if (LenCI->getZExtValue() >= MaxAggrCopySize) {
269 MemCalls.push_back(IntrCall);
270 }
271 } else {
272 MemCalls.push_back(IntrCall);
273 }
274 }
275 }
276 }
277
278 if (AggrLoads.size() == 0 && MemCalls.size() == 0) {
279 return false;
280 }
281
282 //
283 // Do the transformation of an aggr load/copy/set to a loop
284 //
285 for (LoadInst *LI : AggrLoads) {
286 StoreInst *SI = dyn_cast<StoreInst>(*LI->user_begin());
287 Value *SrcAddr = LI->getOperand(0);
288 Value *DstAddr = SI->getOperand(1);
289 unsigned NumLoads = DL.getTypeStoreSize(LI->getType());
290 Value *CopyLen = ConstantInt::get(Type::getInt32Ty(Context), NumLoads);
291
292 convertMemCpyToLoop(/* ConvertedInst */ SI,
293 /* SrcAddr */ SrcAddr, /* DstAddr */ DstAddr,
294 /* CopyLen */ CopyLen,
295 /* SrcIsVolatile */ LI->isVolatile(),
296 /* DstIsVolatile */ SI->isVolatile(),
297 /* Context */ Context,
298 /* Function F */ F);
299
300 SI->eraseFromParent();
301 LI->eraseFromParent();
302 }
303
304 // Transform mem* intrinsic calls.
305 for (MemIntrinsic *MemCall : MemCalls) {
306 if (MemCpyInst *Memcpy = dyn_cast<MemCpyInst>(MemCall)) {
307 convertMemCpyToLoop(/* ConvertedInst */ Memcpy,
308 /* SrcAddr */ Memcpy->getRawSource(),
309 /* DstAddr */ Memcpy->getRawDest(),
310 /* CopyLen */ Memcpy->getLength(),
311 /* SrcIsVolatile */ Memcpy->isVolatile(),
312 /* DstIsVolatile */ Memcpy->isVolatile(),
313 /* Context */ Context,
314 /* Function F */ F);
315 } else if (MemMoveInst *Memmove = dyn_cast<MemMoveInst>(MemCall)) {
316 convertMemMoveToLoop(/* ConvertedInst */ Memmove,
317 /* SrcAddr */ Memmove->getRawSource(),
318 /* DstAddr */ Memmove->getRawDest(),
319 /* CopyLen */ Memmove->getLength(),
320 /* SrcIsVolatile */ Memmove->isVolatile(),
321 /* DstIsVolatile */ Memmove->isVolatile(),
322 /* Context */ Context,
323 /* Function F */ F);
324
325 } else if (MemSetInst *Memset = dyn_cast<MemSetInst>(MemCall)) {
326 convertMemSetToLoop(/* ConvertedInst */ Memset,
327 /* DstAddr */ Memset->getRawDest(),
328 /* CopyLen */ Memset->getLength(),
329 /* SetValue */ Memset->getValue(),
330 /* Context */ Context,
331 /* Function F */ F);
332 }
333 MemCall->eraseFromParent();
334 }
335
336 return true;
337 }
338
339 } // namespace
340
341 namespace llvm {
342 void initializeNVPTXLowerAggrCopiesPass(PassRegistry &);
343 }
344
345 INITIALIZE_PASS(NVPTXLowerAggrCopies, "nvptx-lower-aggr-copies",
346 "Lower aggregate copies, and llvm.mem* intrinsics into loops",
347 false, false)
348
createLowerAggrCopies()349 FunctionPass *llvm::createLowerAggrCopies() {
350 return new NVPTXLowerAggrCopies();
351 }
352