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 41 NVPTXLowerAggrCopies() : FunctionPass(ID) {} 42 43 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 52 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. 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 // } 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. 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 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 349 FunctionPass *llvm::createLowerAggrCopies() { 350 return new NVPTXLowerAggrCopies(); 351 } 352
