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/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"
29 
30 #define DEBUG_TYPE "nvptx"
31 
32 using namespace llvm;
33 
34 namespace {
35 
36 // actual analysis class, which is a functionpass
37 struct NVPTXLowerAggrCopies : public FunctionPass {
38   static char ID;
39 
40   NVPTXLowerAggrCopies() : FunctionPass(ID) {}
41 
42   void getAnalysisUsage(AnalysisUsage &AU) const override {
43     AU.addPreserved<StackProtector>();
44   }
45 
46   bool runOnFunction(Function &F) override;
47 
48   static const unsigned MaxAggrCopySize = 128;
49 
50   StringRef getPassName() const override {
51     return "Lower aggregate copies/intrinsics into loops";
52   }
53 };
54 
55 char NVPTXLowerAggrCopies::ID = 0;
56 
57 // Lower memcpy to loop.
58 void convertMemCpyToLoop(Instruction *ConvertedInst, Value *SrcAddr,
59                          Value *DstAddr, Value *CopyLen, bool SrcIsVolatile,
60                          bool DstIsVolatile, LLVMContext &Context,
61                          Function &F) {
62   Type *TypeOfCopyLen = CopyLen->getType();
63 
64   BasicBlock *OrigBB = ConvertedInst->getParent();
65   BasicBlock *NewBB =
66       ConvertedInst->getParent()->splitBasicBlock(ConvertedInst, "split");
67   BasicBlock *LoopBB = BasicBlock::Create(Context, "loadstoreloop", &F, NewBB);
68 
69   OrigBB->getTerminator()->setSuccessor(0, LoopBB);
70   IRBuilder<> Builder(OrigBB->getTerminator());
71 
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();
76 
77   // Cast pointers to (char *)
78   SrcAddr = Builder.CreateBitCast(SrcAddr, Builder.getInt8PtrTy(SrcAS));
79   DstAddr = Builder.CreateBitCast(DstAddr, Builder.getInt8PtrTy(DstAS));
80 
81   IRBuilder<> LoopBuilder(LoopBB);
82   PHINode *LoopIndex = LoopBuilder.CreatePHI(TypeOfCopyLen, 0);
83   LoopIndex->addIncoming(ConstantInt::get(TypeOfCopyLen, 0), OrigBB);
84 
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.
88   Value *Element =
89       LoopBuilder.CreateLoad(LoopBuilder.CreateInBoundsGEP(
90                                  LoopBuilder.getInt8Ty(), SrcAddr, LoopIndex),
91                              SrcIsVolatile);
92   // store at DstAddr+LoopIndex
93   LoopBuilder.CreateStore(Element,
94                           LoopBuilder.CreateInBoundsGEP(LoopBuilder.getInt8Ty(),
95                                                         DstAddr, LoopIndex),
96                           DstIsVolatile);
97 
98   // The value for LoopIndex coming from backedge is (LoopIndex + 1)
99   Value *NewIndex =
100       LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(TypeOfCopyLen, 1));
101   LoopIndex->addIncoming(NewIndex, LoopBB);
102 
103   LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpULT(NewIndex, CopyLen), LoopBB,
104                            NewBB);
105 }
106 
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.
110 //
111 // The code below is an IR rendition of this C function:
112 //
113 // void* memmove(void* dst, const void* src, size_t n) {
114 //   unsigned char* d = dst;
115 //   const unsigned char* s = src;
116 //   if (s < d) {
117 //     // copy backwards
118 //     while (n--) {
119 //       d[n] = s[n];
120 //     }
121 //   } else {
122 //     // copy forward
123 //     for (size_t i = 0; i < n; ++i) {
124 //       d[i] = s[i];
125 //     }
126 //   }
127 //   return dst;
128 // }
129 void convertMemMoveToLoop(Instruction *ConvertedInst, Value *SrcAddr,
130                           Value *DstAddr, Value *CopyLen, bool SrcIsVolatile,
131                           bool DstIsVolatile, LLVMContext &Context,
132                           Function &F) {
133   Type *TypeOfCopyLen = CopyLen->getType();
134   BasicBlock *OrigBB = ConvertedInst->getParent();
135 
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,
146                                 &ElseTerm);
147 
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");
159 
160   // Initial comparison of n == 0 that lets us skip the loops altogether. Shared
161   // between both backwards and forward copy clauses.
162   ICmpInst *CompareN =
163       new ICmpInst(OrigBB->getTerminator(), ICmpInst::ICMP_EQ, CopyLen,
164                    ConstantInt::get(TypeOfCopyLen, 0), "compare_n_to_0");
165 
166   // Copying backwards.
167   BasicBlock *LoopBB =
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)),
179       ExitBB, LoopBB);
180   LoopPhi->addIncoming(IndexPtr, LoopBB);
181   LoopPhi->addIncoming(CopyLen, CopyBackwardsBB);
182   BranchInst::Create(ExitBB, LoopBB, CompareN, ThenTerm);
183   ThenTerm->eraseFromParent();
184 
185   // Copying forward.
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),
197                               ExitBB, FwdLoopBB);
198   FwdCopyPhi->addIncoming(FwdIndexPtr, FwdLoopBB);
199   FwdCopyPhi->addIncoming(ConstantInt::get(TypeOfCopyLen, 0), CopyForwardBB);
200 
201   BranchInst::Create(ExitBB, FwdLoopBB, CompareN, ElseTerm);
202   ElseTerm->eraseFromParent();
203 }
204 
205 // Lower memset to loop.
206 void convertMemSetToLoop(Instruction *ConvertedInst, Value *DstAddr,
207                          Value *CopyLen, Value *SetValue, LLVMContext &Context,
208                          Function &F) {
209   BasicBlock *OrigBB = ConvertedInst->getParent();
210   BasicBlock *NewBB =
211       ConvertedInst->getParent()->splitBasicBlock(ConvertedInst, "split");
212   BasicBlock *LoopBB = BasicBlock::Create(Context, "loadstoreloop", &F, NewBB);
213 
214   OrigBB->getTerminator()->setSuccessor(0, LoopBB);
215   IRBuilder<> Builder(OrigBB->getTerminator());
216 
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));
221 
222   IRBuilder<> LoopBuilder(LoopBB);
223   PHINode *LoopIndex = LoopBuilder.CreatePHI(CopyLen->getType(), 0);
224   LoopIndex->addIncoming(ConstantInt::get(CopyLen->getType(), 0), OrigBB);
225 
226   LoopBuilder.CreateStore(
227       SetValue,
228       LoopBuilder.CreateInBoundsGEP(SetValue->getType(), DstAddr, LoopIndex),
229       false);
230 
231   Value *NewIndex =
232       LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(CopyLen->getType(), 1));
233   LoopIndex->addIncoming(NewIndex, LoopBB);
234 
235   LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpULT(NewIndex, CopyLen), LoopBB,
236                            NewBB);
237 }
238 
239 bool NVPTXLowerAggrCopies::runOnFunction(Function &F) {
240   SmallVector<LoadInst *, 4> AggrLoads;
241   SmallVector<MemIntrinsic *, 4> MemCalls;
242 
243   const DataLayout &DL = F.getParent()->getDataLayout();
244   LLVMContext &Context = F.getParent()->getContext();
245 
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;
249          ++II) {
250       if (LoadInst *LI = dyn_cast<LoadInst>(II)) {
251         if (!LI->hasOneUse())
252           continue;
253 
254         if (DL.getTypeStoreSize(LI->getType()) < MaxAggrCopySize)
255           continue;
256 
257         if (StoreInst *SI = dyn_cast<StoreInst>(LI->user_back())) {
258           if (SI->getOperand(0) != LI)
259             continue;
260           AggrLoads.push_back(LI);
261         }
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);
268           }
269         } else {
270           MemCalls.push_back(IntrCall);
271         }
272       }
273     }
274   }
275 
276   if (AggrLoads.size() == 0 && MemCalls.size() == 0) {
277     return false;
278   }
279 
280   //
281   // Do the transformation of an aggr load/copy/set to a loop
282   //
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);
289 
290     convertMemCpyToLoop(/* ConvertedInst */ SI,
291                         /* SrcAddr */ SrcAddr, /* DstAddr */ DstAddr,
292                         /* CopyLen */ CopyLen,
293                         /* SrcIsVolatile */ LI->isVolatile(),
294                         /* DstIsVolatile */ SI->isVolatile(),
295                         /* Context */ Context,
296                         /* Function F */ F);
297 
298     SI->eraseFromParent();
299     LI->eraseFromParent();
300   }
301 
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,
312                           /* Function F */ F);
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,
321                            /* Function F */ F);
322 
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,
329                           /* Function F */ F);
330     }
331     MemCall->eraseFromParent();
332   }
333 
334   return true;
335 }
336 
337 } // namespace
338 
339 namespace llvm {
340 void initializeNVPTXLowerAggrCopiesPass(PassRegistry &);
341 }
342 
343 INITIALIZE_PASS(NVPTXLowerAggrCopies, "nvptx-lower-aggr-copies",
344                 "Lower aggregate copies, and llvm.mem* intrinsics into loops",
345                 false, false)
346 
347 FunctionPass *llvm::createLowerAggrCopies() {
348   return new NVPTXLowerAggrCopies();
349 }
350