1 //===- MemCpyOptimizer.cpp - Optimize use of memcpy and friends -----------===// 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 // This pass performs various transformations related to eliminating memcpy 11 // calls, or transforming sets of stores into memset's. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #define DEBUG_TYPE "memcpyopt" 16 #include "llvm/Transforms/Scalar.h" 17 #include "llvm/ADT/SmallVector.h" 18 #include "llvm/ADT/Statistic.h" 19 #include "llvm/Analysis/AliasAnalysis.h" 20 #include "llvm/Analysis/Dominators.h" 21 #include "llvm/Analysis/MemoryDependenceAnalysis.h" 22 #include "llvm/Analysis/ValueTracking.h" 23 #include "llvm/IR/DataLayout.h" 24 #include "llvm/IR/GlobalVariable.h" 25 #include "llvm/IR/IRBuilder.h" 26 #include "llvm/IR/Instructions.h" 27 #include "llvm/IR/IntrinsicInst.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Support/GetElementPtrTypeIterator.h" 30 #include "llvm/Support/raw_ostream.h" 31 #include "llvm/Target/TargetLibraryInfo.h" 32 #include "llvm/Transforms/Utils/Local.h" 33 #include <list> 34 using namespace llvm; 35 36 STATISTIC(NumMemCpyInstr, "Number of memcpy instructions deleted"); 37 STATISTIC(NumMemSetInfer, "Number of memsets inferred"); 38 STATISTIC(NumMoveToCpy, "Number of memmoves converted to memcpy"); 39 STATISTIC(NumCpyToSet, "Number of memcpys converted to memset"); 40 41 static int64_t GetOffsetFromIndex(const GEPOperator *GEP, unsigned Idx, 42 bool &VariableIdxFound, const DataLayout &TD){ 43 // Skip over the first indices. 44 gep_type_iterator GTI = gep_type_begin(GEP); 45 for (unsigned i = 1; i != Idx; ++i, ++GTI) 46 /*skip along*/; 47 48 // Compute the offset implied by the rest of the indices. 49 int64_t Offset = 0; 50 for (unsigned i = Idx, e = GEP->getNumOperands(); i != e; ++i, ++GTI) { 51 ConstantInt *OpC = dyn_cast<ConstantInt>(GEP->getOperand(i)); 52 if (OpC == 0) 53 return VariableIdxFound = true; 54 if (OpC->isZero()) continue; // No offset. 55 56 // Handle struct indices, which add their field offset to the pointer. 57 if (StructType *STy = dyn_cast<StructType>(*GTI)) { 58 Offset += TD.getStructLayout(STy)->getElementOffset(OpC->getZExtValue()); 59 continue; 60 } 61 62 // Otherwise, we have a sequential type like an array or vector. Multiply 63 // the index by the ElementSize. 64 uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()); 65 Offset += Size*OpC->getSExtValue(); 66 } 67 68 return Offset; 69 } 70 71 /// IsPointerOffset - Return true if Ptr1 is provably equal to Ptr2 plus a 72 /// constant offset, and return that constant offset. For example, Ptr1 might 73 /// be &A[42], and Ptr2 might be &A[40]. In this case offset would be -8. 74 static bool IsPointerOffset(Value *Ptr1, Value *Ptr2, int64_t &Offset, 75 const DataLayout &TD) { 76 Ptr1 = Ptr1->stripPointerCasts(); 77 Ptr2 = Ptr2->stripPointerCasts(); 78 GEPOperator *GEP1 = dyn_cast<GEPOperator>(Ptr1); 79 GEPOperator *GEP2 = dyn_cast<GEPOperator>(Ptr2); 80 81 bool VariableIdxFound = false; 82 83 // If one pointer is a GEP and the other isn't, then see if the GEP is a 84 // constant offset from the base, as in "P" and "gep P, 1". 85 if (GEP1 && GEP2 == 0 && GEP1->getOperand(0)->stripPointerCasts() == Ptr2) { 86 Offset = -GetOffsetFromIndex(GEP1, 1, VariableIdxFound, TD); 87 return !VariableIdxFound; 88 } 89 90 if (GEP2 && GEP1 == 0 && GEP2->getOperand(0)->stripPointerCasts() == Ptr1) { 91 Offset = GetOffsetFromIndex(GEP2, 1, VariableIdxFound, TD); 92 return !VariableIdxFound; 93 } 94 95 // Right now we handle the case when Ptr1/Ptr2 are both GEPs with an identical 96 // base. After that base, they may have some number of common (and 97 // potentially variable) indices. After that they handle some constant 98 // offset, which determines their offset from each other. At this point, we 99 // handle no other case. 100 if (!GEP1 || !GEP2 || GEP1->getOperand(0) != GEP2->getOperand(0)) 101 return false; 102 103 // Skip any common indices and track the GEP types. 104 unsigned Idx = 1; 105 for (; Idx != GEP1->getNumOperands() && Idx != GEP2->getNumOperands(); ++Idx) 106 if (GEP1->getOperand(Idx) != GEP2->getOperand(Idx)) 107 break; 108 109 int64_t Offset1 = GetOffsetFromIndex(GEP1, Idx, VariableIdxFound, TD); 110 int64_t Offset2 = GetOffsetFromIndex(GEP2, Idx, VariableIdxFound, TD); 111 if (VariableIdxFound) return false; 112 113 Offset = Offset2-Offset1; 114 return true; 115 } 116 117 118 /// MemsetRange - Represents a range of memset'd bytes with the ByteVal value. 119 /// This allows us to analyze stores like: 120 /// store 0 -> P+1 121 /// store 0 -> P+0 122 /// store 0 -> P+3 123 /// store 0 -> P+2 124 /// which sometimes happens with stores to arrays of structs etc. When we see 125 /// the first store, we make a range [1, 2). The second store extends the range 126 /// to [0, 2). The third makes a new range [2, 3). The fourth store joins the 127 /// two ranges into [0, 3) which is memset'able. 128 namespace { 129 struct MemsetRange { 130 // Start/End - A semi range that describes the span that this range covers. 131 // The range is closed at the start and open at the end: [Start, End). 132 int64_t Start, End; 133 134 /// StartPtr - The getelementptr instruction that points to the start of the 135 /// range. 136 Value *StartPtr; 137 138 /// Alignment - The known alignment of the first store. 139 unsigned Alignment; 140 141 /// TheStores - The actual stores that make up this range. 142 SmallVector<Instruction*, 16> TheStores; 143 144 bool isProfitableToUseMemset(const DataLayout &TD) const; 145 146 }; 147 } // end anon namespace 148 149 bool MemsetRange::isProfitableToUseMemset(const DataLayout &TD) const { 150 // If we found more than 4 stores to merge or 16 bytes, use memset. 151 if (TheStores.size() >= 4 || End-Start >= 16) return true; 152 153 // If there is nothing to merge, don't do anything. 154 if (TheStores.size() < 2) return false; 155 156 // If any of the stores are a memset, then it is always good to extend the 157 // memset. 158 for (unsigned i = 0, e = TheStores.size(); i != e; ++i) 159 if (!isa<StoreInst>(TheStores[i])) 160 return true; 161 162 // Assume that the code generator is capable of merging pairs of stores 163 // together if it wants to. 164 if (TheStores.size() == 2) return false; 165 166 // If we have fewer than 8 stores, it can still be worthwhile to do this. 167 // For example, merging 4 i8 stores into an i32 store is useful almost always. 168 // However, merging 2 32-bit stores isn't useful on a 32-bit architecture (the 169 // memset will be split into 2 32-bit stores anyway) and doing so can 170 // pessimize the llvm optimizer. 171 // 172 // Since we don't have perfect knowledge here, make some assumptions: assume 173 // the maximum GPR width is the same size as the largest legal integer 174 // size. If so, check to see whether we will end up actually reducing the 175 // number of stores used. 176 unsigned Bytes = unsigned(End-Start); 177 unsigned MaxIntSize = TD.getLargestLegalIntTypeSize(); 178 if (MaxIntSize == 0) 179 MaxIntSize = 1; 180 unsigned NumPointerStores = Bytes / MaxIntSize; 181 182 // Assume the remaining bytes if any are done a byte at a time. 183 unsigned NumByteStores = Bytes - NumPointerStores * MaxIntSize; 184 185 // If we will reduce the # stores (according to this heuristic), do the 186 // transformation. This encourages merging 4 x i8 -> i32 and 2 x i16 -> i32 187 // etc. 188 return TheStores.size() > NumPointerStores+NumByteStores; 189 } 190 191 192 namespace { 193 class MemsetRanges { 194 /// Ranges - A sorted list of the memset ranges. We use std::list here 195 /// because each element is relatively large and expensive to copy. 196 std::list<MemsetRange> Ranges; 197 typedef std::list<MemsetRange>::iterator range_iterator; 198 const DataLayout &TD; 199 public: 200 MemsetRanges(const DataLayout &td) : TD(td) {} 201 202 typedef std::list<MemsetRange>::const_iterator const_iterator; 203 const_iterator begin() const { return Ranges.begin(); } 204 const_iterator end() const { return Ranges.end(); } 205 bool empty() const { return Ranges.empty(); } 206 207 void addInst(int64_t OffsetFromFirst, Instruction *Inst) { 208 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) 209 addStore(OffsetFromFirst, SI); 210 else 211 addMemSet(OffsetFromFirst, cast<MemSetInst>(Inst)); 212 } 213 214 void addStore(int64_t OffsetFromFirst, StoreInst *SI) { 215 int64_t StoreSize = TD.getTypeStoreSize(SI->getOperand(0)->getType()); 216 217 addRange(OffsetFromFirst, StoreSize, 218 SI->getPointerOperand(), SI->getAlignment(), SI); 219 } 220 221 void addMemSet(int64_t OffsetFromFirst, MemSetInst *MSI) { 222 int64_t Size = cast<ConstantInt>(MSI->getLength())->getZExtValue(); 223 addRange(OffsetFromFirst, Size, MSI->getDest(), MSI->getAlignment(), MSI); 224 } 225 226 void addRange(int64_t Start, int64_t Size, Value *Ptr, 227 unsigned Alignment, Instruction *Inst); 228 229 }; 230 231 } // end anon namespace 232 233 234 /// addRange - Add a new store to the MemsetRanges data structure. This adds a 235 /// new range for the specified store at the specified offset, merging into 236 /// existing ranges as appropriate. 237 /// 238 /// Do a linear search of the ranges to see if this can be joined and/or to 239 /// find the insertion point in the list. We keep the ranges sorted for 240 /// simplicity here. This is a linear search of a linked list, which is ugly, 241 /// however the number of ranges is limited, so this won't get crazy slow. 242 void MemsetRanges::addRange(int64_t Start, int64_t Size, Value *Ptr, 243 unsigned Alignment, Instruction *Inst) { 244 int64_t End = Start+Size; 245 range_iterator I = Ranges.begin(), E = Ranges.end(); 246 247 while (I != E && Start > I->End) 248 ++I; 249 250 // We now know that I == E, in which case we didn't find anything to merge 251 // with, or that Start <= I->End. If End < I->Start or I == E, then we need 252 // to insert a new range. Handle this now. 253 if (I == E || End < I->Start) { 254 MemsetRange &R = *Ranges.insert(I, MemsetRange()); 255 R.Start = Start; 256 R.End = End; 257 R.StartPtr = Ptr; 258 R.Alignment = Alignment; 259 R.TheStores.push_back(Inst); 260 return; 261 } 262 263 // This store overlaps with I, add it. 264 I->TheStores.push_back(Inst); 265 266 // At this point, we may have an interval that completely contains our store. 267 // If so, just add it to the interval and return. 268 if (I->Start <= Start && I->End >= End) 269 return; 270 271 // Now we know that Start <= I->End and End >= I->Start so the range overlaps 272 // but is not entirely contained within the range. 273 274 // See if the range extends the start of the range. In this case, it couldn't 275 // possibly cause it to join the prior range, because otherwise we would have 276 // stopped on *it*. 277 if (Start < I->Start) { 278 I->Start = Start; 279 I->StartPtr = Ptr; 280 I->Alignment = Alignment; 281 } 282 283 // Now we know that Start <= I->End and Start >= I->Start (so the startpoint 284 // is in or right at the end of I), and that End >= I->Start. Extend I out to 285 // End. 286 if (End > I->End) { 287 I->End = End; 288 range_iterator NextI = I; 289 while (++NextI != E && End >= NextI->Start) { 290 // Merge the range in. 291 I->TheStores.append(NextI->TheStores.begin(), NextI->TheStores.end()); 292 if (NextI->End > I->End) 293 I->End = NextI->End; 294 Ranges.erase(NextI); 295 NextI = I; 296 } 297 } 298 } 299 300 //===----------------------------------------------------------------------===// 301 // MemCpyOpt Pass 302 //===----------------------------------------------------------------------===// 303 304 namespace { 305 class MemCpyOpt : public FunctionPass { 306 MemoryDependenceAnalysis *MD; 307 TargetLibraryInfo *TLI; 308 const DataLayout *TD; 309 public: 310 static char ID; // Pass identification, replacement for typeid 311 MemCpyOpt() : FunctionPass(ID) { 312 initializeMemCpyOptPass(*PassRegistry::getPassRegistry()); 313 MD = 0; 314 TLI = 0; 315 TD = 0; 316 } 317 318 bool runOnFunction(Function &F); 319 320 private: 321 // This transformation requires dominator postdominator info 322 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 323 AU.setPreservesCFG(); 324 AU.addRequired<DominatorTree>(); 325 AU.addRequired<MemoryDependenceAnalysis>(); 326 AU.addRequired<AliasAnalysis>(); 327 AU.addRequired<TargetLibraryInfo>(); 328 AU.addPreserved<AliasAnalysis>(); 329 AU.addPreserved<MemoryDependenceAnalysis>(); 330 } 331 332 // Helper fuctions 333 bool processStore(StoreInst *SI, BasicBlock::iterator &BBI); 334 bool processMemSet(MemSetInst *SI, BasicBlock::iterator &BBI); 335 bool processMemCpy(MemCpyInst *M); 336 bool processMemMove(MemMoveInst *M); 337 bool performCallSlotOptzn(Instruction *cpy, Value *cpyDst, Value *cpySrc, 338 uint64_t cpyLen, unsigned cpyAlign, CallInst *C); 339 bool processMemCpyMemCpyDependence(MemCpyInst *M, MemCpyInst *MDep, 340 uint64_t MSize); 341 bool processByValArgument(CallSite CS, unsigned ArgNo); 342 Instruction *tryMergingIntoMemset(Instruction *I, Value *StartPtr, 343 Value *ByteVal); 344 345 bool iterateOnFunction(Function &F); 346 }; 347 348 char MemCpyOpt::ID = 0; 349 } 350 351 // createMemCpyOptPass - The public interface to this file... 352 FunctionPass *llvm::createMemCpyOptPass() { return new MemCpyOpt(); } 353 354 INITIALIZE_PASS_BEGIN(MemCpyOpt, "memcpyopt", "MemCpy Optimization", 355 false, false) 356 INITIALIZE_PASS_DEPENDENCY(DominatorTree) 357 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) 358 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 359 INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 360 INITIALIZE_PASS_END(MemCpyOpt, "memcpyopt", "MemCpy Optimization", 361 false, false) 362 363 /// tryMergingIntoMemset - When scanning forward over instructions, we look for 364 /// some other patterns to fold away. In particular, this looks for stores to 365 /// neighboring locations of memory. If it sees enough consecutive ones, it 366 /// attempts to merge them together into a memcpy/memset. 367 Instruction *MemCpyOpt::tryMergingIntoMemset(Instruction *StartInst, 368 Value *StartPtr, Value *ByteVal) { 369 if (TD == 0) return 0; 370 371 // Okay, so we now have a single store that can be splatable. Scan to find 372 // all subsequent stores of the same value to offset from the same pointer. 373 // Join these together into ranges, so we can decide whether contiguous blocks 374 // are stored. 375 MemsetRanges Ranges(*TD); 376 377 BasicBlock::iterator BI = StartInst; 378 for (++BI; !isa<TerminatorInst>(BI); ++BI) { 379 if (!isa<StoreInst>(BI) && !isa<MemSetInst>(BI)) { 380 // If the instruction is readnone, ignore it, otherwise bail out. We 381 // don't even allow readonly here because we don't want something like: 382 // A[1] = 2; strlen(A); A[2] = 2; -> memcpy(A, ...); strlen(A). 383 if (BI->mayWriteToMemory() || BI->mayReadFromMemory()) 384 break; 385 continue; 386 } 387 388 if (StoreInst *NextStore = dyn_cast<StoreInst>(BI)) { 389 // If this is a store, see if we can merge it in. 390 if (!NextStore->isSimple()) break; 391 392 // Check to see if this stored value is of the same byte-splattable value. 393 if (ByteVal != isBytewiseValue(NextStore->getOperand(0))) 394 break; 395 396 // Check to see if this store is to a constant offset from the start ptr. 397 int64_t Offset; 398 if (!IsPointerOffset(StartPtr, NextStore->getPointerOperand(), 399 Offset, *TD)) 400 break; 401 402 Ranges.addStore(Offset, NextStore); 403 } else { 404 MemSetInst *MSI = cast<MemSetInst>(BI); 405 406 if (MSI->isVolatile() || ByteVal != MSI->getValue() || 407 !isa<ConstantInt>(MSI->getLength())) 408 break; 409 410 // Check to see if this store is to a constant offset from the start ptr. 411 int64_t Offset; 412 if (!IsPointerOffset(StartPtr, MSI->getDest(), Offset, *TD)) 413 break; 414 415 Ranges.addMemSet(Offset, MSI); 416 } 417 } 418 419 // If we have no ranges, then we just had a single store with nothing that 420 // could be merged in. This is a very common case of course. 421 if (Ranges.empty()) 422 return 0; 423 424 // If we had at least one store that could be merged in, add the starting 425 // store as well. We try to avoid this unless there is at least something 426 // interesting as a small compile-time optimization. 427 Ranges.addInst(0, StartInst); 428 429 // If we create any memsets, we put it right before the first instruction that 430 // isn't part of the memset block. This ensure that the memset is dominated 431 // by any addressing instruction needed by the start of the block. 432 IRBuilder<> Builder(BI); 433 434 // Now that we have full information about ranges, loop over the ranges and 435 // emit memset's for anything big enough to be worthwhile. 436 Instruction *AMemSet = 0; 437 for (MemsetRanges::const_iterator I = Ranges.begin(), E = Ranges.end(); 438 I != E; ++I) { 439 const MemsetRange &Range = *I; 440 441 if (Range.TheStores.size() == 1) continue; 442 443 // If it is profitable to lower this range to memset, do so now. 444 if (!Range.isProfitableToUseMemset(*TD)) 445 continue; 446 447 // Otherwise, we do want to transform this! Create a new memset. 448 // Get the starting pointer of the block. 449 StartPtr = Range.StartPtr; 450 451 // Determine alignment 452 unsigned Alignment = Range.Alignment; 453 if (Alignment == 0) { 454 Type *EltType = 455 cast<PointerType>(StartPtr->getType())->getElementType(); 456 Alignment = TD->getABITypeAlignment(EltType); 457 } 458 459 AMemSet = 460 Builder.CreateMemSet(StartPtr, ByteVal, Range.End-Range.Start, Alignment); 461 462 DEBUG(dbgs() << "Replace stores:\n"; 463 for (unsigned i = 0, e = Range.TheStores.size(); i != e; ++i) 464 dbgs() << *Range.TheStores[i] << '\n'; 465 dbgs() << "With: " << *AMemSet << '\n'); 466 467 if (!Range.TheStores.empty()) 468 AMemSet->setDebugLoc(Range.TheStores[0]->getDebugLoc()); 469 470 // Zap all the stores. 471 for (SmallVectorImpl<Instruction *>::const_iterator 472 SI = Range.TheStores.begin(), 473 SE = Range.TheStores.end(); SI != SE; ++SI) { 474 MD->removeInstruction(*SI); 475 (*SI)->eraseFromParent(); 476 } 477 ++NumMemSetInfer; 478 } 479 480 return AMemSet; 481 } 482 483 484 bool MemCpyOpt::processStore(StoreInst *SI, BasicBlock::iterator &BBI) { 485 if (!SI->isSimple()) return false; 486 487 if (TD == 0) return false; 488 489 // Detect cases where we're performing call slot forwarding, but 490 // happen to be using a load-store pair to implement it, rather than 491 // a memcpy. 492 if (LoadInst *LI = dyn_cast<LoadInst>(SI->getOperand(0))) { 493 if (LI->isSimple() && LI->hasOneUse() && 494 LI->getParent() == SI->getParent()) { 495 MemDepResult ldep = MD->getDependency(LI); 496 CallInst *C = 0; 497 if (ldep.isClobber() && !isa<MemCpyInst>(ldep.getInst())) 498 C = dyn_cast<CallInst>(ldep.getInst()); 499 500 if (C) { 501 // Check that nothing touches the dest of the "copy" between 502 // the call and the store. 503 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 504 AliasAnalysis::Location StoreLoc = AA.getLocation(SI); 505 for (BasicBlock::iterator I = --BasicBlock::iterator(SI), 506 E = C; I != E; --I) { 507 if (AA.getModRefInfo(&*I, StoreLoc) != AliasAnalysis::NoModRef) { 508 C = 0; 509 break; 510 } 511 } 512 } 513 514 if (C) { 515 unsigned storeAlign = SI->getAlignment(); 516 if (!storeAlign) 517 storeAlign = TD->getABITypeAlignment(SI->getOperand(0)->getType()); 518 unsigned loadAlign = LI->getAlignment(); 519 if (!loadAlign) 520 loadAlign = TD->getABITypeAlignment(LI->getType()); 521 522 bool changed = performCallSlotOptzn(LI, 523 SI->getPointerOperand()->stripPointerCasts(), 524 LI->getPointerOperand()->stripPointerCasts(), 525 TD->getTypeStoreSize(SI->getOperand(0)->getType()), 526 std::min(storeAlign, loadAlign), C); 527 if (changed) { 528 MD->removeInstruction(SI); 529 SI->eraseFromParent(); 530 MD->removeInstruction(LI); 531 LI->eraseFromParent(); 532 ++NumMemCpyInstr; 533 return true; 534 } 535 } 536 } 537 } 538 539 // There are two cases that are interesting for this code to handle: memcpy 540 // and memset. Right now we only handle memset. 541 542 // Ensure that the value being stored is something that can be memset'able a 543 // byte at a time like "0" or "-1" or any width, as well as things like 544 // 0xA0A0A0A0 and 0.0. 545 if (Value *ByteVal = isBytewiseValue(SI->getOperand(0))) 546 if (Instruction *I = tryMergingIntoMemset(SI, SI->getPointerOperand(), 547 ByteVal)) { 548 BBI = I; // Don't invalidate iterator. 549 return true; 550 } 551 552 return false; 553 } 554 555 bool MemCpyOpt::processMemSet(MemSetInst *MSI, BasicBlock::iterator &BBI) { 556 // See if there is another memset or store neighboring this memset which 557 // allows us to widen out the memset to do a single larger store. 558 if (isa<ConstantInt>(MSI->getLength()) && !MSI->isVolatile()) 559 if (Instruction *I = tryMergingIntoMemset(MSI, MSI->getDest(), 560 MSI->getValue())) { 561 BBI = I; // Don't invalidate iterator. 562 return true; 563 } 564 return false; 565 } 566 567 568 /// performCallSlotOptzn - takes a memcpy and a call that it depends on, 569 /// and checks for the possibility of a call slot optimization by having 570 /// the call write its result directly into the destination of the memcpy. 571 bool MemCpyOpt::performCallSlotOptzn(Instruction *cpy, 572 Value *cpyDest, Value *cpySrc, 573 uint64_t cpyLen, unsigned cpyAlign, 574 CallInst *C) { 575 // The general transformation to keep in mind is 576 // 577 // call @func(..., src, ...) 578 // memcpy(dest, src, ...) 579 // 580 // -> 581 // 582 // memcpy(dest, src, ...) 583 // call @func(..., dest, ...) 584 // 585 // Since moving the memcpy is technically awkward, we additionally check that 586 // src only holds uninitialized values at the moment of the call, meaning that 587 // the memcpy can be discarded rather than moved. 588 589 // Deliberately get the source and destination with bitcasts stripped away, 590 // because we'll need to do type comparisons based on the underlying type. 591 CallSite CS(C); 592 593 // Require that src be an alloca. This simplifies the reasoning considerably. 594 AllocaInst *srcAlloca = dyn_cast<AllocaInst>(cpySrc); 595 if (!srcAlloca) 596 return false; 597 598 // Check that all of src is copied to dest. 599 if (TD == 0) return false; 600 601 ConstantInt *srcArraySize = dyn_cast<ConstantInt>(srcAlloca->getArraySize()); 602 if (!srcArraySize) 603 return false; 604 605 uint64_t srcSize = TD->getTypeAllocSize(srcAlloca->getAllocatedType()) * 606 srcArraySize->getZExtValue(); 607 608 if (cpyLen < srcSize) 609 return false; 610 611 // Check that accessing the first srcSize bytes of dest will not cause a 612 // trap. Otherwise the transform is invalid since it might cause a trap 613 // to occur earlier than it otherwise would. 614 if (AllocaInst *A = dyn_cast<AllocaInst>(cpyDest)) { 615 // The destination is an alloca. Check it is larger than srcSize. 616 ConstantInt *destArraySize = dyn_cast<ConstantInt>(A->getArraySize()); 617 if (!destArraySize) 618 return false; 619 620 uint64_t destSize = TD->getTypeAllocSize(A->getAllocatedType()) * 621 destArraySize->getZExtValue(); 622 623 if (destSize < srcSize) 624 return false; 625 } else if (Argument *A = dyn_cast<Argument>(cpyDest)) { 626 // If the destination is an sret parameter then only accesses that are 627 // outside of the returned struct type can trap. 628 if (!A->hasStructRetAttr()) 629 return false; 630 631 Type *StructTy = cast<PointerType>(A->getType())->getElementType(); 632 if (!StructTy->isSized()) { 633 // The call may never return and hence the copy-instruction may never 634 // be executed, and therefore it's not safe to say "the destination 635 // has at least <cpyLen> bytes, as implied by the copy-instruction", 636 return false; 637 } 638 639 uint64_t destSize = TD->getTypeAllocSize(StructTy); 640 if (destSize < srcSize) 641 return false; 642 } else { 643 return false; 644 } 645 646 // Check that dest points to memory that is at least as aligned as src. 647 unsigned srcAlign = srcAlloca->getAlignment(); 648 if (!srcAlign) 649 srcAlign = TD->getABITypeAlignment(srcAlloca->getAllocatedType()); 650 bool isDestSufficientlyAligned = srcAlign <= cpyAlign; 651 // If dest is not aligned enough and we can't increase its alignment then 652 // bail out. 653 if (!isDestSufficientlyAligned && !isa<AllocaInst>(cpyDest)) 654 return false; 655 656 // Check that src is not accessed except via the call and the memcpy. This 657 // guarantees that it holds only undefined values when passed in (so the final 658 // memcpy can be dropped), that it is not read or written between the call and 659 // the memcpy, and that writing beyond the end of it is undefined. 660 SmallVector<User*, 8> srcUseList(srcAlloca->use_begin(), 661 srcAlloca->use_end()); 662 while (!srcUseList.empty()) { 663 User *UI = srcUseList.pop_back_val(); 664 665 if (isa<BitCastInst>(UI)) { 666 for (User::use_iterator I = UI->use_begin(), E = UI->use_end(); 667 I != E; ++I) 668 srcUseList.push_back(*I); 669 } else if (GetElementPtrInst *G = dyn_cast<GetElementPtrInst>(UI)) { 670 if (G->hasAllZeroIndices()) 671 for (User::use_iterator I = UI->use_begin(), E = UI->use_end(); 672 I != E; ++I) 673 srcUseList.push_back(*I); 674 else 675 return false; 676 } else if (UI != C && UI != cpy) { 677 return false; 678 } 679 } 680 681 // Since we're changing the parameter to the callsite, we need to make sure 682 // that what would be the new parameter dominates the callsite. 683 DominatorTree &DT = getAnalysis<DominatorTree>(); 684 if (Instruction *cpyDestInst = dyn_cast<Instruction>(cpyDest)) 685 if (!DT.dominates(cpyDestInst, C)) 686 return false; 687 688 // In addition to knowing that the call does not access src in some 689 // unexpected manner, for example via a global, which we deduce from 690 // the use analysis, we also need to know that it does not sneakily 691 // access dest. We rely on AA to figure this out for us. 692 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 693 AliasAnalysis::ModRefResult MR = AA.getModRefInfo(C, cpyDest, srcSize); 694 // If necessary, perform additional analysis. 695 if (MR != AliasAnalysis::NoModRef) 696 MR = AA.callCapturesBefore(C, cpyDest, srcSize, &DT); 697 if (MR != AliasAnalysis::NoModRef) 698 return false; 699 700 // All the checks have passed, so do the transformation. 701 bool changedArgument = false; 702 for (unsigned i = 0; i < CS.arg_size(); ++i) 703 if (CS.getArgument(i)->stripPointerCasts() == cpySrc) { 704 Value *Dest = cpySrc->getType() == cpyDest->getType() ? cpyDest 705 : CastInst::CreatePointerCast(cpyDest, cpySrc->getType(), 706 cpyDest->getName(), C); 707 changedArgument = true; 708 if (CS.getArgument(i)->getType() == Dest->getType()) 709 CS.setArgument(i, Dest); 710 else 711 CS.setArgument(i, CastInst::CreatePointerCast(Dest, 712 CS.getArgument(i)->getType(), Dest->getName(), C)); 713 } 714 715 if (!changedArgument) 716 return false; 717 718 // If the destination wasn't sufficiently aligned then increase its alignment. 719 if (!isDestSufficientlyAligned) { 720 assert(isa<AllocaInst>(cpyDest) && "Can only increase alloca alignment!"); 721 cast<AllocaInst>(cpyDest)->setAlignment(srcAlign); 722 } 723 724 // Drop any cached information about the call, because we may have changed 725 // its dependence information by changing its parameter. 726 MD->removeInstruction(C); 727 728 // Remove the memcpy. 729 MD->removeInstruction(cpy); 730 ++NumMemCpyInstr; 731 732 return true; 733 } 734 735 /// processMemCpyMemCpyDependence - We've found that the (upward scanning) 736 /// memory dependence of memcpy 'M' is the memcpy 'MDep'. Try to simplify M to 737 /// copy from MDep's input if we can. MSize is the size of M's copy. 738 /// 739 bool MemCpyOpt::processMemCpyMemCpyDependence(MemCpyInst *M, MemCpyInst *MDep, 740 uint64_t MSize) { 741 // We can only transforms memcpy's where the dest of one is the source of the 742 // other. 743 if (M->getSource() != MDep->getDest() || MDep->isVolatile()) 744 return false; 745 746 // If dep instruction is reading from our current input, then it is a noop 747 // transfer and substituting the input won't change this instruction. Just 748 // ignore the input and let someone else zap MDep. This handles cases like: 749 // memcpy(a <- a) 750 // memcpy(b <- a) 751 if (M->getSource() == MDep->getSource()) 752 return false; 753 754 // Second, the length of the memcpy's must be the same, or the preceding one 755 // must be larger than the following one. 756 ConstantInt *MDepLen = dyn_cast<ConstantInt>(MDep->getLength()); 757 ConstantInt *MLen = dyn_cast<ConstantInt>(M->getLength()); 758 if (!MDepLen || !MLen || MDepLen->getZExtValue() < MLen->getZExtValue()) 759 return false; 760 761 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 762 763 // Verify that the copied-from memory doesn't change in between the two 764 // transfers. For example, in: 765 // memcpy(a <- b) 766 // *b = 42; 767 // memcpy(c <- a) 768 // It would be invalid to transform the second memcpy into memcpy(c <- b). 769 // 770 // TODO: If the code between M and MDep is transparent to the destination "c", 771 // then we could still perform the xform by moving M up to the first memcpy. 772 // 773 // NOTE: This is conservative, it will stop on any read from the source loc, 774 // not just the defining memcpy. 775 MemDepResult SourceDep = 776 MD->getPointerDependencyFrom(AA.getLocationForSource(MDep), 777 false, M, M->getParent()); 778 if (!SourceDep.isClobber() || SourceDep.getInst() != MDep) 779 return false; 780 781 // If the dest of the second might alias the source of the first, then the 782 // source and dest might overlap. We still want to eliminate the intermediate 783 // value, but we have to generate a memmove instead of memcpy. 784 bool UseMemMove = false; 785 if (!AA.isNoAlias(AA.getLocationForDest(M), AA.getLocationForSource(MDep))) 786 UseMemMove = true; 787 788 // If all checks passed, then we can transform M. 789 790 // Make sure to use the lesser of the alignment of the source and the dest 791 // since we're changing where we're reading from, but don't want to increase 792 // the alignment past what can be read from or written to. 793 // TODO: Is this worth it if we're creating a less aligned memcpy? For 794 // example we could be moving from movaps -> movq on x86. 795 unsigned Align = std::min(MDep->getAlignment(), M->getAlignment()); 796 797 IRBuilder<> Builder(M); 798 if (UseMemMove) 799 Builder.CreateMemMove(M->getRawDest(), MDep->getRawSource(), M->getLength(), 800 Align, M->isVolatile()); 801 else 802 Builder.CreateMemCpy(M->getRawDest(), MDep->getRawSource(), M->getLength(), 803 Align, M->isVolatile()); 804 805 // Remove the instruction we're replacing. 806 MD->removeInstruction(M); 807 M->eraseFromParent(); 808 ++NumMemCpyInstr; 809 return true; 810 } 811 812 813 /// processMemCpy - perform simplification of memcpy's. If we have memcpy A 814 /// which copies X to Y, and memcpy B which copies Y to Z, then we can rewrite 815 /// B to be a memcpy from X to Z (or potentially a memmove, depending on 816 /// circumstances). This allows later passes to remove the first memcpy 817 /// altogether. 818 bool MemCpyOpt::processMemCpy(MemCpyInst *M) { 819 // We can only optimize statically-sized memcpy's that are non-volatile. 820 ConstantInt *CopySize = dyn_cast<ConstantInt>(M->getLength()); 821 if (CopySize == 0 || M->isVolatile()) return false; 822 823 // If the source and destination of the memcpy are the same, then zap it. 824 if (M->getSource() == M->getDest()) { 825 MD->removeInstruction(M); 826 M->eraseFromParent(); 827 return false; 828 } 829 830 // If copying from a constant, try to turn the memcpy into a memset. 831 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getSource())) 832 if (GV->isConstant() && GV->hasDefinitiveInitializer()) 833 if (Value *ByteVal = isBytewiseValue(GV->getInitializer())) { 834 IRBuilder<> Builder(M); 835 Builder.CreateMemSet(M->getRawDest(), ByteVal, CopySize, 836 M->getAlignment(), false); 837 MD->removeInstruction(M); 838 M->eraseFromParent(); 839 ++NumCpyToSet; 840 return true; 841 } 842 843 // The are two possible optimizations we can do for memcpy: 844 // a) memcpy-memcpy xform which exposes redundance for DSE. 845 // b) call-memcpy xform for return slot optimization. 846 MemDepResult DepInfo = MD->getDependency(M); 847 if (DepInfo.isClobber()) { 848 if (CallInst *C = dyn_cast<CallInst>(DepInfo.getInst())) { 849 if (performCallSlotOptzn(M, M->getDest(), M->getSource(), 850 CopySize->getZExtValue(), M->getAlignment(), 851 C)) { 852 MD->removeInstruction(M); 853 M->eraseFromParent(); 854 return true; 855 } 856 } 857 } 858 859 AliasAnalysis::Location SrcLoc = AliasAnalysis::getLocationForSource(M); 860 MemDepResult SrcDepInfo = MD->getPointerDependencyFrom(SrcLoc, true, 861 M, M->getParent()); 862 if (SrcDepInfo.isClobber()) { 863 if (MemCpyInst *MDep = dyn_cast<MemCpyInst>(SrcDepInfo.getInst())) 864 return processMemCpyMemCpyDependence(M, MDep, CopySize->getZExtValue()); 865 } 866 867 return false; 868 } 869 870 /// processMemMove - Transforms memmove calls to memcpy calls when the src/dst 871 /// are guaranteed not to alias. 872 bool MemCpyOpt::processMemMove(MemMoveInst *M) { 873 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 874 875 if (!TLI->has(LibFunc::memmove)) 876 return false; 877 878 // See if the pointers alias. 879 if (!AA.isNoAlias(AA.getLocationForDest(M), AA.getLocationForSource(M))) 880 return false; 881 882 DEBUG(dbgs() << "MemCpyOpt: Optimizing memmove -> memcpy: " << *M << "\n"); 883 884 // If not, then we know we can transform this. 885 Module *Mod = M->getParent()->getParent()->getParent(); 886 Type *ArgTys[3] = { M->getRawDest()->getType(), 887 M->getRawSource()->getType(), 888 M->getLength()->getType() }; 889 M->setCalledFunction(Intrinsic::getDeclaration(Mod, Intrinsic::memcpy, 890 ArgTys)); 891 892 // MemDep may have over conservative information about this instruction, just 893 // conservatively flush it from the cache. 894 MD->removeInstruction(M); 895 896 ++NumMoveToCpy; 897 return true; 898 } 899 900 /// processByValArgument - This is called on every byval argument in call sites. 901 bool MemCpyOpt::processByValArgument(CallSite CS, unsigned ArgNo) { 902 if (TD == 0) return false; 903 904 // Find out what feeds this byval argument. 905 Value *ByValArg = CS.getArgument(ArgNo); 906 Type *ByValTy = cast<PointerType>(ByValArg->getType())->getElementType(); 907 uint64_t ByValSize = TD->getTypeAllocSize(ByValTy); 908 MemDepResult DepInfo = 909 MD->getPointerDependencyFrom(AliasAnalysis::Location(ByValArg, ByValSize), 910 true, CS.getInstruction(), 911 CS.getInstruction()->getParent()); 912 if (!DepInfo.isClobber()) 913 return false; 914 915 // If the byval argument isn't fed by a memcpy, ignore it. If it is fed by 916 // a memcpy, see if we can byval from the source of the memcpy instead of the 917 // result. 918 MemCpyInst *MDep = dyn_cast<MemCpyInst>(DepInfo.getInst()); 919 if (MDep == 0 || MDep->isVolatile() || 920 ByValArg->stripPointerCasts() != MDep->getDest()) 921 return false; 922 923 // The length of the memcpy must be larger or equal to the size of the byval. 924 ConstantInt *C1 = dyn_cast<ConstantInt>(MDep->getLength()); 925 if (C1 == 0 || C1->getValue().getZExtValue() < ByValSize) 926 return false; 927 928 // Get the alignment of the byval. If the call doesn't specify the alignment, 929 // then it is some target specific value that we can't know. 930 unsigned ByValAlign = CS.getParamAlignment(ArgNo+1); 931 if (ByValAlign == 0) return false; 932 933 // If it is greater than the memcpy, then we check to see if we can force the 934 // source of the memcpy to the alignment we need. If we fail, we bail out. 935 if (MDep->getAlignment() < ByValAlign && 936 getOrEnforceKnownAlignment(MDep->getSource(),ByValAlign, TD) < ByValAlign) 937 return false; 938 939 // Verify that the copied-from memory doesn't change in between the memcpy and 940 // the byval call. 941 // memcpy(a <- b) 942 // *b = 42; 943 // foo(*a) 944 // It would be invalid to transform the second memcpy into foo(*b). 945 // 946 // NOTE: This is conservative, it will stop on any read from the source loc, 947 // not just the defining memcpy. 948 MemDepResult SourceDep = 949 MD->getPointerDependencyFrom(AliasAnalysis::getLocationForSource(MDep), 950 false, CS.getInstruction(), MDep->getParent()); 951 if (!SourceDep.isClobber() || SourceDep.getInst() != MDep) 952 return false; 953 954 Value *TmpCast = MDep->getSource(); 955 if (MDep->getSource()->getType() != ByValArg->getType()) 956 TmpCast = new BitCastInst(MDep->getSource(), ByValArg->getType(), 957 "tmpcast", CS.getInstruction()); 958 959 DEBUG(dbgs() << "MemCpyOpt: Forwarding memcpy to byval:\n" 960 << " " << *MDep << "\n" 961 << " " << *CS.getInstruction() << "\n"); 962 963 // Otherwise we're good! Update the byval argument. 964 CS.setArgument(ArgNo, TmpCast); 965 ++NumMemCpyInstr; 966 return true; 967 } 968 969 /// iterateOnFunction - Executes one iteration of MemCpyOpt. 970 bool MemCpyOpt::iterateOnFunction(Function &F) { 971 bool MadeChange = false; 972 973 // Walk all instruction in the function. 974 for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) { 975 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { 976 // Avoid invalidating the iterator. 977 Instruction *I = BI++; 978 979 bool RepeatInstruction = false; 980 981 if (StoreInst *SI = dyn_cast<StoreInst>(I)) 982 MadeChange |= processStore(SI, BI); 983 else if (MemSetInst *M = dyn_cast<MemSetInst>(I)) 984 RepeatInstruction = processMemSet(M, BI); 985 else if (MemCpyInst *M = dyn_cast<MemCpyInst>(I)) 986 RepeatInstruction = processMemCpy(M); 987 else if (MemMoveInst *M = dyn_cast<MemMoveInst>(I)) 988 RepeatInstruction = processMemMove(M); 989 else if (CallSite CS = (Value*)I) { 990 for (unsigned i = 0, e = CS.arg_size(); i != e; ++i) 991 if (CS.isByValArgument(i)) 992 MadeChange |= processByValArgument(CS, i); 993 } 994 995 // Reprocess the instruction if desired. 996 if (RepeatInstruction) { 997 if (BI != BB->begin()) --BI; 998 MadeChange = true; 999 } 1000 } 1001 } 1002 1003 return MadeChange; 1004 } 1005 1006 // MemCpyOpt::runOnFunction - This is the main transformation entry point for a 1007 // function. 1008 // 1009 bool MemCpyOpt::runOnFunction(Function &F) { 1010 bool MadeChange = false; 1011 MD = &getAnalysis<MemoryDependenceAnalysis>(); 1012 TD = getAnalysisIfAvailable<DataLayout>(); 1013 TLI = &getAnalysis<TargetLibraryInfo>(); 1014 1015 // If we don't have at least memset and memcpy, there is little point of doing 1016 // anything here. These are required by a freestanding implementation, so if 1017 // even they are disabled, there is no point in trying hard. 1018 if (!TLI->has(LibFunc::memset) || !TLI->has(LibFunc::memcpy)) 1019 return false; 1020 1021 while (1) { 1022 if (!iterateOnFunction(F)) 1023 break; 1024 MadeChange = true; 1025 } 1026 1027 MD = 0; 1028 return MadeChange; 1029 } 1030