LLVM  mainline
NVPTXLowerAggrCopies.cpp
Go to the documentation of this file.
00001 //===- NVPTXLowerAggrCopies.cpp - ------------------------------*- C++ -*--===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // \file
00011 // Lower aggregate copies, memset, memcpy, memmov intrinsics into loops when
00012 // the size is large or is not a compile-time constant.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "NVPTXLowerAggrCopies.h"
00017 #include "llvm/CodeGen/MachineFunctionAnalysis.h"
00018 #include "llvm/CodeGen/StackProtector.h"
00019 #include "llvm/IR/Constants.h"
00020 #include "llvm/IR/DataLayout.h"
00021 #include "llvm/IR/Function.h"
00022 #include "llvm/IR/IRBuilder.h"
00023 #include "llvm/IR/Instructions.h"
00024 #include "llvm/IR/IntrinsicInst.h"
00025 #include "llvm/IR/Intrinsics.h"
00026 #include "llvm/IR/LLVMContext.h"
00027 #include "llvm/IR/Module.h"
00028 #include "llvm/Support/Debug.h"
00029 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00030 
00031 #define DEBUG_TYPE "nvptx"
00032 
00033 using namespace llvm;
00034 
00035 namespace {
00036 
00037 // actual analysis class, which is a functionpass
00038 struct NVPTXLowerAggrCopies : public FunctionPass {
00039   static char ID;
00040 
00041   NVPTXLowerAggrCopies() : FunctionPass(ID) {}
00042 
00043   void getAnalysisUsage(AnalysisUsage &AU) const override {
00044     AU.addPreserved<MachineFunctionAnalysis>();
00045     AU.addPreserved<StackProtector>();
00046   }
00047 
00048   bool runOnFunction(Function &F) override;
00049 
00050   static const unsigned MaxAggrCopySize = 128;
00051 
00052   const char *getPassName() const override {
00053     return "Lower aggregate copies/intrinsics into loops";
00054   }
00055 };
00056 
00057 char NVPTXLowerAggrCopies::ID = 0;
00058 
00059 // Lower memcpy to loop.
00060 void convertMemCpyToLoop(Instruction *ConvertedInst, Value *SrcAddr,
00061                          Value *DstAddr, Value *CopyLen, bool SrcIsVolatile,
00062                          bool DstIsVolatile, LLVMContext &Context,
00063                          Function &F) {
00064   Type *TypeOfCopyLen = CopyLen->getType();
00065 
00066   BasicBlock *OrigBB = ConvertedInst->getParent();
00067   BasicBlock *NewBB =
00068       ConvertedInst->getParent()->splitBasicBlock(ConvertedInst, "split");
00069   BasicBlock *LoopBB = BasicBlock::Create(Context, "loadstoreloop", &F, NewBB);
00070 
00071   OrigBB->getTerminator()->setSuccessor(0, LoopBB);
00072   IRBuilder<> Builder(OrigBB->getTerminator());
00073 
00074   // SrcAddr and DstAddr are expected to be pointer types,
00075   // so no check is made here.
00076   unsigned SrcAS = cast<PointerType>(SrcAddr->getType())->getAddressSpace();
00077   unsigned DstAS = cast<PointerType>(DstAddr->getType())->getAddressSpace();
00078 
00079   // Cast pointers to (char *)
00080   SrcAddr = Builder.CreateBitCast(SrcAddr, Builder.getInt8PtrTy(SrcAS));
00081   DstAddr = Builder.CreateBitCast(DstAddr, Builder.getInt8PtrTy(DstAS));
00082 
00083   IRBuilder<> LoopBuilder(LoopBB);
00084   PHINode *LoopIndex = LoopBuilder.CreatePHI(TypeOfCopyLen, 0);
00085   LoopIndex->addIncoming(ConstantInt::get(TypeOfCopyLen, 0), OrigBB);
00086 
00087   // load from SrcAddr+LoopIndex
00088   // TODO: we can leverage the align parameter of llvm.memcpy for more efficient
00089   // word-sized loads and stores.
00090   Value *Element =
00091       LoopBuilder.CreateLoad(LoopBuilder.CreateInBoundsGEP(
00092                                  LoopBuilder.getInt8Ty(), SrcAddr, LoopIndex),
00093                              SrcIsVolatile);
00094   // store at DstAddr+LoopIndex
00095   LoopBuilder.CreateStore(Element,
00096                           LoopBuilder.CreateInBoundsGEP(LoopBuilder.getInt8Ty(),
00097                                                         DstAddr, LoopIndex),
00098                           DstIsVolatile);
00099 
00100   // The value for LoopIndex coming from backedge is (LoopIndex + 1)
00101   Value *NewIndex =
00102       LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(TypeOfCopyLen, 1));
00103   LoopIndex->addIncoming(NewIndex, LoopBB);
00104 
00105   LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpULT(NewIndex, CopyLen), LoopBB,
00106                            NewBB);
00107 }
00108 
00109 // Lower memmove to IR. memmove is required to correctly copy overlapping memory
00110 // regions; therefore, it has to check the relative positions of the source and
00111 // destination pointers and choose the copy direction accordingly.
00112 //
00113 // The code below is an IR rendition of this C function:
00114 //
00115 // void* memmove(void* dst, const void* src, size_t n) {
00116 //   unsigned char* d = dst;
00117 //   const unsigned char* s = src;
00118 //   if (s < d) {
00119 //     // copy backwards
00120 //     while (n--) {
00121 //       d[n] = s[n];
00122 //     }
00123 //   } else {
00124 //     // copy forward
00125 //     for (size_t i = 0; i < n; ++i) {
00126 //       d[i] = s[i];
00127 //     }
00128 //   }
00129 //   return dst;
00130 // }
00131 void convertMemMoveToLoop(Instruction *ConvertedInst, Value *SrcAddr,
00132                           Value *DstAddr, Value *CopyLen, bool SrcIsVolatile,
00133                           bool DstIsVolatile, LLVMContext &Context,
00134                           Function &F) {
00135   Type *TypeOfCopyLen = CopyLen->getType();
00136   BasicBlock *OrigBB = ConvertedInst->getParent();
00137 
00138   // Create the a comparison of src and dst, based on which we jump to either
00139   // the forward-copy part of the function (if src >= dst) or the backwards-copy
00140   // part (if src < dst).
00141   // SplitBlockAndInsertIfThenElse conveniently creates the basic if-then-else
00142   // structure. Its block terminators (unconditional branches) are replaced by
00143   // the appropriate conditional branches when the loop is built.
00144   ICmpInst *PtrCompare = new ICmpInst(ConvertedInst, ICmpInst::ICMP_ULT,
00145                                       SrcAddr, DstAddr, "compare_src_dst");
00146   TerminatorInst *ThenTerm, *ElseTerm;
00147   SplitBlockAndInsertIfThenElse(PtrCompare, ConvertedInst, &ThenTerm,
00148                                 &ElseTerm);
00149 
00150   // Each part of the function consists of two blocks:
00151   //   copy_backwards:        used to skip the loop when n == 0
00152   //   copy_backwards_loop:   the actual backwards loop BB
00153   //   copy_forward:          used to skip the loop when n == 0
00154   //   copy_forward_loop:     the actual forward loop BB
00155   BasicBlock *CopyBackwardsBB = ThenTerm->getParent();
00156   CopyBackwardsBB->setName("copy_backwards");
00157   BasicBlock *CopyForwardBB = ElseTerm->getParent();
00158   CopyForwardBB->setName("copy_forward");
00159   BasicBlock *ExitBB = ConvertedInst->getParent();
00160   ExitBB->setName("memmove_done");
00161 
00162   // Initial comparison of n == 0 that lets us skip the loops altogether. Shared
00163   // between both backwards and forward copy clauses.
00164   ICmpInst *CompareN =
00165       new ICmpInst(OrigBB->getTerminator(), ICmpInst::ICMP_EQ, CopyLen,
00166                    ConstantInt::get(TypeOfCopyLen, 0), "compare_n_to_0");
00167 
00168   // Copying backwards.
00169   BasicBlock *LoopBB =
00170       BasicBlock::Create(Context, "copy_backwards_loop", &F, CopyForwardBB);
00171   IRBuilder<> LoopBuilder(LoopBB);
00172   PHINode *LoopPhi = LoopBuilder.CreatePHI(TypeOfCopyLen, 0);
00173   Value *IndexPtr = LoopBuilder.CreateSub(
00174       LoopPhi, ConstantInt::get(TypeOfCopyLen, 1), "index_ptr");
00175   Value *Element = LoopBuilder.CreateLoad(
00176       LoopBuilder.CreateInBoundsGEP(SrcAddr, IndexPtr), "element");
00177   LoopBuilder.CreateStore(Element,
00178                           LoopBuilder.CreateInBoundsGEP(DstAddr, IndexPtr));
00179   LoopBuilder.CreateCondBr(
00180       LoopBuilder.CreateICmpEQ(IndexPtr, ConstantInt::get(TypeOfCopyLen, 0)),
00181       ExitBB, LoopBB);
00182   LoopPhi->addIncoming(IndexPtr, LoopBB);
00183   LoopPhi->addIncoming(CopyLen, CopyBackwardsBB);
00184   BranchInst::Create(ExitBB, LoopBB, CompareN, ThenTerm);
00185   ThenTerm->eraseFromParent();
00186 
00187   // Copying forward.
00188   BasicBlock *FwdLoopBB =
00189       BasicBlock::Create(Context, "copy_forward_loop", &F, ExitBB);
00190   IRBuilder<> FwdLoopBuilder(FwdLoopBB);
00191   PHINode *FwdCopyPhi = FwdLoopBuilder.CreatePHI(TypeOfCopyLen, 0, "index_ptr");
00192   Value *FwdElement = FwdLoopBuilder.CreateLoad(
00193       FwdLoopBuilder.CreateInBoundsGEP(SrcAddr, FwdCopyPhi), "element");
00194   FwdLoopBuilder.CreateStore(
00195       FwdElement, FwdLoopBuilder.CreateInBoundsGEP(DstAddr, FwdCopyPhi));
00196   Value *FwdIndexPtr = FwdLoopBuilder.CreateAdd(
00197       FwdCopyPhi, ConstantInt::get(TypeOfCopyLen, 1), "index_increment");
00198   FwdLoopBuilder.CreateCondBr(FwdLoopBuilder.CreateICmpEQ(FwdIndexPtr, CopyLen),
00199                               ExitBB, FwdLoopBB);
00200   FwdCopyPhi->addIncoming(FwdIndexPtr, FwdLoopBB);
00201   FwdCopyPhi->addIncoming(ConstantInt::get(TypeOfCopyLen, 0), CopyForwardBB);
00202 
00203   BranchInst::Create(ExitBB, FwdLoopBB, CompareN, ElseTerm);
00204   ElseTerm->eraseFromParent();
00205 }
00206 
00207 // Lower memset to loop.
00208 void convertMemSetToLoop(Instruction *ConvertedInst, Value *DstAddr,
00209                          Value *CopyLen, Value *SetValue, LLVMContext &Context,
00210                          Function &F) {
00211   BasicBlock *OrigBB = ConvertedInst->getParent();
00212   BasicBlock *NewBB =
00213       ConvertedInst->getParent()->splitBasicBlock(ConvertedInst, "split");
00214   BasicBlock *LoopBB = BasicBlock::Create(Context, "loadstoreloop", &F, NewBB);
00215 
00216   OrigBB->getTerminator()->setSuccessor(0, LoopBB);
00217   IRBuilder<> Builder(OrigBB->getTerminator());
00218 
00219   // Cast pointer to the type of value getting stored
00220   unsigned dstAS = cast<PointerType>(DstAddr->getType())->getAddressSpace();
00221   DstAddr = Builder.CreateBitCast(DstAddr,
00222                                   PointerType::get(SetValue->getType(), dstAS));
00223 
00224   IRBuilder<> LoopBuilder(LoopBB);
00225   PHINode *LoopIndex = LoopBuilder.CreatePHI(CopyLen->getType(), 0);
00226   LoopIndex->addIncoming(ConstantInt::get(CopyLen->getType(), 0), OrigBB);
00227 
00228   LoopBuilder.CreateStore(
00229       SetValue,
00230       LoopBuilder.CreateInBoundsGEP(SetValue->getType(), DstAddr, LoopIndex),
00231       false);
00232 
00233   Value *NewIndex =
00234       LoopBuilder.CreateAdd(LoopIndex, ConstantInt::get(CopyLen->getType(), 1));
00235   LoopIndex->addIncoming(NewIndex, LoopBB);
00236 
00237   LoopBuilder.CreateCondBr(LoopBuilder.CreateICmpULT(NewIndex, CopyLen), LoopBB,
00238                            NewBB);
00239 }
00240 
00241 bool NVPTXLowerAggrCopies::runOnFunction(Function &F) {
00242   SmallVector<LoadInst *, 4> AggrLoads;
00243   SmallVector<MemIntrinsic *, 4> MemCalls;
00244 
00245   const DataLayout &DL = F.getParent()->getDataLayout();
00246   LLVMContext &Context = F.getParent()->getContext();
00247 
00248   // Collect all aggregate loads and mem* calls.
00249   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
00250     for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;
00251          ++II) {
00252       if (LoadInst *LI = dyn_cast<LoadInst>(II)) {
00253         if (!LI->hasOneUse())
00254           continue;
00255 
00256         if (DL.getTypeStoreSize(LI->getType()) < MaxAggrCopySize)
00257           continue;
00258 
00259         if (StoreInst *SI = dyn_cast<StoreInst>(LI->user_back())) {
00260           if (SI->getOperand(0) != LI)
00261             continue;
00262           AggrLoads.push_back(LI);
00263         }
00264       } else if (MemIntrinsic *IntrCall = dyn_cast<MemIntrinsic>(II)) {
00265         // Convert intrinsic calls with variable size or with constant size
00266         // larger than the MaxAggrCopySize threshold.
00267         if (ConstantInt *LenCI = dyn_cast<ConstantInt>(IntrCall->getLength())) {
00268           if (LenCI->getZExtValue() >= MaxAggrCopySize) {
00269             MemCalls.push_back(IntrCall);
00270           }
00271         } else {
00272           MemCalls.push_back(IntrCall);
00273         }
00274       }
00275     }
00276   }
00277 
00278   if (AggrLoads.size() == 0 && MemCalls.size() == 0) {
00279     return false;
00280   }
00281 
00282   //
00283   // Do the transformation of an aggr load/copy/set to a loop
00284   //
00285   for (LoadInst *LI : AggrLoads) {
00286     StoreInst *SI = dyn_cast<StoreInst>(*LI->user_begin());
00287     Value *SrcAddr = LI->getOperand(0);
00288     Value *DstAddr = SI->getOperand(1);
00289     unsigned NumLoads = DL.getTypeStoreSize(LI->getType());
00290     Value *CopyLen = ConstantInt::get(Type::getInt32Ty(Context), NumLoads);
00291 
00292     convertMemCpyToLoop(/* ConvertedInst */ SI,
00293                         /* SrcAddr */ SrcAddr, /* DstAddr */ DstAddr,
00294                         /* CopyLen */ CopyLen,
00295                         /* SrcIsVolatile */ LI->isVolatile(),
00296                         /* DstIsVolatile */ SI->isVolatile(),
00297                         /* Context */ Context,
00298                         /* Function F */ F);
00299 
00300     SI->eraseFromParent();
00301     LI->eraseFromParent();
00302   }
00303 
00304   // Transform mem* intrinsic calls.
00305   for (MemIntrinsic *MemCall : MemCalls) {
00306     if (MemCpyInst *Memcpy = dyn_cast<MemCpyInst>(MemCall)) {
00307       convertMemCpyToLoop(/* ConvertedInst */ Memcpy,
00308                           /* SrcAddr */ Memcpy->getRawSource(),
00309                           /* DstAddr */ Memcpy->getRawDest(),
00310                           /* CopyLen */ Memcpy->getLength(),
00311                           /* SrcIsVolatile */ Memcpy->isVolatile(),
00312                           /* DstIsVolatile */ Memcpy->isVolatile(),
00313                           /* Context */ Context,
00314                           /* Function F */ F);
00315     } else if (MemMoveInst *Memmove = dyn_cast<MemMoveInst>(MemCall)) {
00316       convertMemMoveToLoop(/* ConvertedInst */ Memmove,
00317                            /* SrcAddr */ Memmove->getRawSource(),
00318                            /* DstAddr */ Memmove->getRawDest(),
00319                            /* CopyLen */ Memmove->getLength(),
00320                            /* SrcIsVolatile */ Memmove->isVolatile(),
00321                            /* DstIsVolatile */ Memmove->isVolatile(),
00322                            /* Context */ Context,
00323                            /* Function F */ F);
00324 
00325     } else if (MemSetInst *Memset = dyn_cast<MemSetInst>(MemCall)) {
00326       convertMemSetToLoop(/* ConvertedInst */ Memset,
00327                           /* DstAddr */ Memset->getRawDest(),
00328                           /* CopyLen */ Memset->getLength(),
00329                           /* SetValue */ Memset->getValue(),
00330                           /* Context */ Context,
00331                           /* Function F */ F);
00332     }
00333     MemCall->eraseFromParent();
00334   }
00335 
00336   return true;
00337 }
00338 
00339 } // namespace
00340 
00341 namespace llvm {
00342 void initializeNVPTXLowerAggrCopiesPass(PassRegistry &);
00343 }
00344 
00345 INITIALIZE_PASS(NVPTXLowerAggrCopies, "nvptx-lower-aggr-copies",
00346                 "Lower aggregate copies, and llvm.mem* intrinsics into loops",
00347                 false, false)
00348 
00349 FunctionPass *llvm::createLowerAggrCopies() {
00350   return new NVPTXLowerAggrCopies();
00351 }