1 //===- NVPTXLowerAggrCopies.cpp - ------------------------------*- C++ -*--===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 // Lower aggregate copies, memset, memcpy, memmov intrinsics into loops when
12 // the size is large or is not a compile-time constant.
14 //===----------------------------------------------------------------------===//
16 #include "NVPTXLowerAggrCopies.h"
17 #include "llvm/CodeGen/StackProtector.h"
18 #include "llvm/IR/Constants.h"
19 #include "llvm/IR/DataLayout.h"
20 #include "llvm/IR/Function.h"
21 #include "llvm/IR/IRBuilder.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/IR/IntrinsicInst.h"
24 #include "llvm/IR/Intrinsics.h"
25 #include "llvm/IR/LLVMContext.h"
26 #include "llvm/IR/Module.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
30 #define DEBUG_TYPE "nvptx"
36 // actual analysis class, which is a functionpass
37 struct NVPTXLowerAggrCopies : public FunctionPass {
40 NVPTXLowerAggrCopies() : FunctionPass(ID) {}
42 void getAnalysisUsage(AnalysisUsage &AU) const override {
43 AU.addPreserved<StackProtector>();
46 bool runOnFunction(Function &F) override;
48 static const unsigned MaxAggrCopySize = 128;
50 StringRef getPassName() const override {
51 return "Lower aggregate copies/intrinsics into loops";
55 char NVPTXLowerAggrCopies::ID = 0;
57 // Lower memcpy to loop.
58 void convertMemCpyToLoop(Instruction *ConvertedInst, Value *SrcAddr,
59 Value *DstAddr, Value *CopyLen, bool SrcIsVolatile,
60 bool DstIsVolatile, LLVMContext &Context,
62 Type *TypeOfCopyLen = CopyLen->getType();
64 BasicBlock *OrigBB = ConvertedInst->getParent();
66 ConvertedInst->getParent()->splitBasicBlock(ConvertedInst, "split");
67 BasicBlock *LoopBB = BasicBlock::Create(Context, "loadstoreloop", &F, NewBB);
69 OrigBB->getTerminator()->setSuccessor(0, LoopBB);
70 IRBuilder<> Builder(OrigBB->getTerminator());
72 // SrcAddr and DstAddr are expected to be pointer types,
73 // so no check is made here.
74 unsigned SrcAS = cast<PointerType>(SrcAddr->getType())->getAddressSpace();
75 unsigned DstAS = cast<PointerType>(DstAddr->getType())->getAddressSpace();
77 // Cast pointers to (char *)
78 SrcAddr = Builder.CreateBitCast(SrcAddr, Builder.getInt8PtrTy(SrcAS));
79 DstAddr = Builder.CreateBitCast(DstAddr, Builder.getInt8PtrTy(DstAS));
81 IRBuilder<> LoopBuilder(LoopBB);
82 PHINode *LoopIndex = LoopBuilder.CreatePHI(TypeOfCopyLen, 0);
83 LoopIndex->addIncoming(ConstantInt::get(TypeOfCopyLen, 0), OrigBB);
85 // load from SrcAddr+LoopIndex
86 // TODO: we can leverage the align parameter of llvm.memcpy for more efficient
87 // word-sized loads and stores.
89 LoopBuilder.CreateLoad(LoopBuilder.CreateInBoundsGEP(
90 LoopBuilder.getInt8Ty(), SrcAddr, LoopIndex),
92 // store at DstAddr+LoopIndex
93 LoopBuilder.CreateStore(Element,
94 LoopBuilder.CreateInBoundsGEP(LoopBuilder.getInt8Ty(),
98 // The value for LoopIndex coming from backedge is (LoopIndex + 1)
100 LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(TypeOfCopyLen, 1));
101 LoopIndex->addIncoming(NewIndex, LoopBB);
103 LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpULT(NewIndex, CopyLen), LoopBB,
107 // Lower memmove to IR. memmove is required to correctly copy overlapping memory
108 // regions; therefore, it has to check the relative positions of the source and
109 // destination pointers and choose the copy direction accordingly.
111 // The code below is an IR rendition of this C function:
113 // void* memmove(void* dst, const void* src, size_t n) {
114 // unsigned char* d = dst;
115 // const unsigned char* s = src;
123 // for (size_t i = 0; i < n; ++i) {
129 void convertMemMoveToLoop(Instruction *ConvertedInst, Value *SrcAddr,
130 Value *DstAddr, Value *CopyLen, bool SrcIsVolatile,
131 bool DstIsVolatile, LLVMContext &Context,
133 Type *TypeOfCopyLen = CopyLen->getType();
134 BasicBlock *OrigBB = ConvertedInst->getParent();
136 // Create the a comparison of src and dst, based on which we jump to either
137 // the forward-copy part of the function (if src >= dst) or the backwards-copy
138 // part (if src < dst).
139 // SplitBlockAndInsertIfThenElse conveniently creates the basic if-then-else
140 // structure. Its block terminators (unconditional branches) are replaced by
141 // the appropriate conditional branches when the loop is built.
142 ICmpInst *PtrCompare = new ICmpInst(ConvertedInst, ICmpInst::ICMP_ULT,
143 SrcAddr, DstAddr, "compare_src_dst");
144 TerminatorInst *ThenTerm, *ElseTerm;
145 SplitBlockAndInsertIfThenElse(PtrCompare, ConvertedInst, &ThenTerm,
148 // Each part of the function consists of two blocks:
149 // copy_backwards: used to skip the loop when n == 0
150 // copy_backwards_loop: the actual backwards loop BB
151 // copy_forward: used to skip the loop when n == 0
152 // copy_forward_loop: the actual forward loop BB
153 BasicBlock *CopyBackwardsBB = ThenTerm->getParent();
154 CopyBackwardsBB->setName("copy_backwards");
155 BasicBlock *CopyForwardBB = ElseTerm->getParent();
156 CopyForwardBB->setName("copy_forward");
157 BasicBlock *ExitBB = ConvertedInst->getParent();
158 ExitBB->setName("memmove_done");
160 // Initial comparison of n == 0 that lets us skip the loops altogether. Shared
161 // between both backwards and forward copy clauses.
163 new ICmpInst(OrigBB->getTerminator(), ICmpInst::ICMP_EQ, CopyLen,
164 ConstantInt::get(TypeOfCopyLen, 0), "compare_n_to_0");
166 // Copying backwards.
168 BasicBlock::Create(Context, "copy_backwards_loop", &F, CopyForwardBB);
169 IRBuilder<> LoopBuilder(LoopBB);
170 PHINode *LoopPhi = LoopBuilder.CreatePHI(TypeOfCopyLen, 0);
171 Value *IndexPtr = LoopBuilder.CreateSub(
172 LoopPhi, ConstantInt::get(TypeOfCopyLen, 1), "index_ptr");
173 Value *Element = LoopBuilder.CreateLoad(
174 LoopBuilder.CreateInBoundsGEP(SrcAddr, IndexPtr), "element");
175 LoopBuilder.CreateStore(Element,
176 LoopBuilder.CreateInBoundsGEP(DstAddr, IndexPtr));
177 LoopBuilder.CreateCondBr(
178 LoopBuilder.CreateICmpEQ(IndexPtr, ConstantInt::get(TypeOfCopyLen, 0)),
180 LoopPhi->addIncoming(IndexPtr, LoopBB);
181 LoopPhi->addIncoming(CopyLen, CopyBackwardsBB);
182 BranchInst::Create(ExitBB, LoopBB, CompareN, ThenTerm);
183 ThenTerm->eraseFromParent();
186 BasicBlock *FwdLoopBB =
187 BasicBlock::Create(Context, "copy_forward_loop", &F, ExitBB);
188 IRBuilder<> FwdLoopBuilder(FwdLoopBB);
189 PHINode *FwdCopyPhi = FwdLoopBuilder.CreatePHI(TypeOfCopyLen, 0, "index_ptr");
190 Value *FwdElement = FwdLoopBuilder.CreateLoad(
191 FwdLoopBuilder.CreateInBoundsGEP(SrcAddr, FwdCopyPhi), "element");
192 FwdLoopBuilder.CreateStore(
193 FwdElement, FwdLoopBuilder.CreateInBoundsGEP(DstAddr, FwdCopyPhi));
194 Value *FwdIndexPtr = FwdLoopBuilder.CreateAdd(
195 FwdCopyPhi, ConstantInt::get(TypeOfCopyLen, 1), "index_increment");
196 FwdLoopBuilder.CreateCondBr(FwdLoopBuilder.CreateICmpEQ(FwdIndexPtr, CopyLen),
198 FwdCopyPhi->addIncoming(FwdIndexPtr, FwdLoopBB);
199 FwdCopyPhi->addIncoming(ConstantInt::get(TypeOfCopyLen, 0), CopyForwardBB);
201 BranchInst::Create(ExitBB, FwdLoopBB, CompareN, ElseTerm);
202 ElseTerm->eraseFromParent();
205 // Lower memset to loop.
206 void convertMemSetToLoop(Instruction *ConvertedInst, Value *DstAddr,
207 Value *CopyLen, Value *SetValue, LLVMContext &Context,
209 BasicBlock *OrigBB = ConvertedInst->getParent();
211 ConvertedInst->getParent()->splitBasicBlock(ConvertedInst, "split");
212 BasicBlock *LoopBB = BasicBlock::Create(Context, "loadstoreloop", &F, NewBB);
214 OrigBB->getTerminator()->setSuccessor(0, LoopBB);
215 IRBuilder<> Builder(OrigBB->getTerminator());
217 // Cast pointer to the type of value getting stored
218 unsigned dstAS = cast<PointerType>(DstAddr->getType())->getAddressSpace();
219 DstAddr = Builder.CreateBitCast(DstAddr,
220 PointerType::get(SetValue->getType(), dstAS));
222 IRBuilder<> LoopBuilder(LoopBB);
223 PHINode *LoopIndex = LoopBuilder.CreatePHI(CopyLen->getType(), 0);
224 LoopIndex->addIncoming(ConstantInt::get(CopyLen->getType(), 0), OrigBB);
226 LoopBuilder.CreateStore(
228 LoopBuilder.CreateInBoundsGEP(SetValue->getType(), DstAddr, LoopIndex),
232 LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(CopyLen->getType(), 1));
233 LoopIndex->addIncoming(NewIndex, LoopBB);
235 LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpULT(NewIndex, CopyLen), LoopBB,
239 bool NVPTXLowerAggrCopies::runOnFunction(Function &F) {
240 SmallVector<LoadInst *, 4> AggrLoads;
241 SmallVector<MemIntrinsic *, 4> MemCalls;
243 const DataLayout &DL = F.getParent()->getDataLayout();
244 LLVMContext &Context = F.getParent()->getContext();
246 // Collect all aggregate loads and mem* calls.
247 for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
248 for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;
250 if (LoadInst *LI = dyn_cast<LoadInst>(II)) {
251 if (!LI->hasOneUse())
254 if (DL.getTypeStoreSize(LI->getType()) < MaxAggrCopySize)
257 if (StoreInst *SI = dyn_cast<StoreInst>(LI->user_back())) {
258 if (SI->getOperand(0) != LI)
260 AggrLoads.push_back(LI);
262 } else if (MemIntrinsic *IntrCall = dyn_cast<MemIntrinsic>(II)) {
263 // Convert intrinsic calls with variable size or with constant size
264 // larger than the MaxAggrCopySize threshold.
265 if (ConstantInt *LenCI = dyn_cast<ConstantInt>(IntrCall->getLength())) {
266 if (LenCI->getZExtValue() >= MaxAggrCopySize) {
267 MemCalls.push_back(IntrCall);
270 MemCalls.push_back(IntrCall);
276 if (AggrLoads.size() == 0 && MemCalls.size() == 0) {
281 // Do the transformation of an aggr load/copy/set to a loop
283 for (LoadInst *LI : AggrLoads) {
284 StoreInst *SI = dyn_cast<StoreInst>(*LI->user_begin());
285 Value *SrcAddr = LI->getOperand(0);
286 Value *DstAddr = SI->getOperand(1);
287 unsigned NumLoads = DL.getTypeStoreSize(LI->getType());
288 Value *CopyLen = ConstantInt::get(Type::getInt32Ty(Context), NumLoads);
290 convertMemCpyToLoop(/* ConvertedInst */ SI,
291 /* SrcAddr */ SrcAddr, /* DstAddr */ DstAddr,
292 /* CopyLen */ CopyLen,
293 /* SrcIsVolatile */ LI->isVolatile(),
294 /* DstIsVolatile */ SI->isVolatile(),
295 /* Context */ Context,
298 SI->eraseFromParent();
299 LI->eraseFromParent();
302 // Transform mem* intrinsic calls.
303 for (MemIntrinsic *MemCall : MemCalls) {
304 if (MemCpyInst *Memcpy = dyn_cast<MemCpyInst>(MemCall)) {
305 convertMemCpyToLoop(/* ConvertedInst */ Memcpy,
306 /* SrcAddr */ Memcpy->getRawSource(),
307 /* DstAddr */ Memcpy->getRawDest(),
308 /* CopyLen */ Memcpy->getLength(),
309 /* SrcIsVolatile */ Memcpy->isVolatile(),
310 /* DstIsVolatile */ Memcpy->isVolatile(),
311 /* Context */ Context,
313 } else if (MemMoveInst *Memmove = dyn_cast<MemMoveInst>(MemCall)) {
314 convertMemMoveToLoop(/* ConvertedInst */ Memmove,
315 /* SrcAddr */ Memmove->getRawSource(),
316 /* DstAddr */ Memmove->getRawDest(),
317 /* CopyLen */ Memmove->getLength(),
318 /* SrcIsVolatile */ Memmove->isVolatile(),
319 /* DstIsVolatile */ Memmove->isVolatile(),
320 /* Context */ Context,
323 } else if (MemSetInst *Memset = dyn_cast<MemSetInst>(MemCall)) {
324 convertMemSetToLoop(/* ConvertedInst */ Memset,
325 /* DstAddr */ Memset->getRawDest(),
326 /* CopyLen */ Memset->getLength(),
327 /* SetValue */ Memset->getValue(),
328 /* Context */ Context,
331 MemCall->eraseFromParent();
340 void initializeNVPTXLowerAggrCopiesPass(PassRegistry &);
343 INITIALIZE_PASS(NVPTXLowerAggrCopies, "nvptx-lower-aggr-copies",
344 "Lower aggregate copies, and llvm.mem* intrinsics into loops",
347 FunctionPass *llvm::createLowerAggrCopies() {
348 return new NVPTXLowerAggrCopies();