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 #include "llvm/Transforms/Scalar/MemCpyOptimizer.h" 16 #include "llvm/ADT/DenseSet.h" 17 #include "llvm/ADT/None.h" 18 #include "llvm/ADT/STLExtras.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/ADT/Statistic.h" 21 #include "llvm/ADT/iterator_range.h" 22 #include "llvm/Analysis/AliasAnalysis.h" 23 #include "llvm/Analysis/AssumptionCache.h" 24 #include "llvm/Analysis/GlobalsModRef.h" 25 #include "llvm/Analysis/MemoryDependenceAnalysis.h" 26 #include "llvm/Analysis/MemoryLocation.h" 27 #include "llvm/Analysis/TargetLibraryInfo.h" 28 #include "llvm/Transforms/Utils/Local.h" 29 #include "llvm/Analysis/ValueTracking.h" 30 #include "llvm/IR/Argument.h" 31 #include "llvm/IR/BasicBlock.h" 32 #include "llvm/IR/CallSite.h" 33 #include "llvm/IR/Constants.h" 34 #include "llvm/IR/DataLayout.h" 35 #include "llvm/IR/DerivedTypes.h" 36 #include "llvm/IR/Dominators.h" 37 #include "llvm/IR/Function.h" 38 #include "llvm/IR/GetElementPtrTypeIterator.h" 39 #include "llvm/IR/GlobalVariable.h" 40 #include "llvm/IR/IRBuilder.h" 41 #include "llvm/IR/InstrTypes.h" 42 #include "llvm/IR/Instruction.h" 43 #include "llvm/IR/Instructions.h" 44 #include "llvm/IR/IntrinsicInst.h" 45 #include "llvm/IR/Intrinsics.h" 46 #include "llvm/IR/LLVMContext.h" 47 #include "llvm/IR/Module.h" 48 #include "llvm/IR/Operator.h" 49 #include "llvm/IR/PassManager.h" 50 #include "llvm/IR/Type.h" 51 #include "llvm/IR/User.h" 52 #include "llvm/IR/Value.h" 53 #include "llvm/Pass.h" 54 #include "llvm/Support/Casting.h" 55 #include "llvm/Support/Debug.h" 56 #include "llvm/Support/MathExtras.h" 57 #include "llvm/Support/raw_ostream.h" 58 #include "llvm/Transforms/Scalar.h" 59 #include <algorithm> 60 #include <cassert> 61 #include <cstdint> 62 #include <utility> 63 64 using namespace llvm; 65 66 #define DEBUG_TYPE "memcpyopt" 67 68 STATISTIC(NumMemCpyInstr, "Number of memcpy instructions deleted"); 69 STATISTIC(NumMemSetInfer, "Number of memsets inferred"); 70 STATISTIC(NumMoveToCpy, "Number of memmoves converted to memcpy"); 71 STATISTIC(NumCpyToSet, "Number of memcpys converted to memset"); 72 73 static int64_t GetOffsetFromIndex(const GEPOperator *GEP, unsigned Idx, 74 bool &VariableIdxFound, 75 const DataLayout &DL) { 76 // Skip over the first indices. 77 gep_type_iterator GTI = gep_type_begin(GEP); 78 for (unsigned i = 1; i != Idx; ++i, ++GTI) 79 /*skip along*/; 80 81 // Compute the offset implied by the rest of the indices. 82 int64_t Offset = 0; 83 for (unsigned i = Idx, e = GEP->getNumOperands(); i != e; ++i, ++GTI) { 84 ConstantInt *OpC = dyn_cast<ConstantInt>(GEP->getOperand(i)); 85 if (!OpC) 86 return VariableIdxFound = true; 87 if (OpC->isZero()) continue; // No offset. 88 89 // Handle struct indices, which add their field offset to the pointer. 90 if (StructType *STy = GTI.getStructTypeOrNull()) { 91 Offset += DL.getStructLayout(STy)->getElementOffset(OpC->getZExtValue()); 92 continue; 93 } 94 95 // Otherwise, we have a sequential type like an array or vector. Multiply 96 // the index by the ElementSize. 97 uint64_t Size = DL.getTypeAllocSize(GTI.getIndexedType()); 98 Offset += Size*OpC->getSExtValue(); 99 } 100 101 return Offset; 102 } 103 104 /// Return true if Ptr1 is provably equal to Ptr2 plus a constant offset, and 105 /// return that constant offset. For example, Ptr1 might be &A[42], and Ptr2 106 /// might be &A[40]. In this case offset would be -8. 107 static bool IsPointerOffset(Value *Ptr1, Value *Ptr2, int64_t &Offset, 108 const DataLayout &DL) { 109 Ptr1 = Ptr1->stripPointerCasts(); 110 Ptr2 = Ptr2->stripPointerCasts(); 111 112 // Handle the trivial case first. 113 if (Ptr1 == Ptr2) { 114 Offset = 0; 115 return true; 116 } 117 118 GEPOperator *GEP1 = dyn_cast<GEPOperator>(Ptr1); 119 GEPOperator *GEP2 = dyn_cast<GEPOperator>(Ptr2); 120 121 bool VariableIdxFound = false; 122 123 // If one pointer is a GEP and the other isn't, then see if the GEP is a 124 // constant offset from the base, as in "P" and "gep P, 1". 125 if (GEP1 && !GEP2 && GEP1->getOperand(0)->stripPointerCasts() == Ptr2) { 126 Offset = -GetOffsetFromIndex(GEP1, 1, VariableIdxFound, DL); 127 return !VariableIdxFound; 128 } 129 130 if (GEP2 && !GEP1 && GEP2->getOperand(0)->stripPointerCasts() == Ptr1) { 131 Offset = GetOffsetFromIndex(GEP2, 1, VariableIdxFound, DL); 132 return !VariableIdxFound; 133 } 134 135 // Right now we handle the case when Ptr1/Ptr2 are both GEPs with an identical 136 // base. After that base, they may have some number of common (and 137 // potentially variable) indices. After that they handle some constant 138 // offset, which determines their offset from each other. At this point, we 139 // handle no other case. 140 if (!GEP1 || !GEP2 || GEP1->getOperand(0) != GEP2->getOperand(0)) 141 return false; 142 143 // Skip any common indices and track the GEP types. 144 unsigned Idx = 1; 145 for (; Idx != GEP1->getNumOperands() && Idx != GEP2->getNumOperands(); ++Idx) 146 if (GEP1->getOperand(Idx) != GEP2->getOperand(Idx)) 147 break; 148 149 int64_t Offset1 = GetOffsetFromIndex(GEP1, Idx, VariableIdxFound, DL); 150 int64_t Offset2 = GetOffsetFromIndex(GEP2, Idx, VariableIdxFound, DL); 151 if (VariableIdxFound) return false; 152 153 Offset = Offset2-Offset1; 154 return true; 155 } 156 157 namespace { 158 159 /// Represents a range of memset'd bytes with the ByteVal value. 160 /// This allows us to analyze stores like: 161 /// store 0 -> P+1 162 /// store 0 -> P+0 163 /// store 0 -> P+3 164 /// store 0 -> P+2 165 /// which sometimes happens with stores to arrays of structs etc. When we see 166 /// the first store, we make a range [1, 2). The second store extends the range 167 /// to [0, 2). The third makes a new range [2, 3). The fourth store joins the 168 /// two ranges into [0, 3) which is memset'able. 169 struct MemsetRange { 170 // Start/End - A semi range that describes the span that this range covers. 171 // The range is closed at the start and open at the end: [Start, End). 172 int64_t Start, End; 173 174 /// StartPtr - The getelementptr instruction that points to the start of the 175 /// range. 176 Value *StartPtr; 177 178 /// Alignment - The known alignment of the first store. 179 unsigned Alignment; 180 181 /// TheStores - The actual stores that make up this range. 182 SmallVector<Instruction*, 16> TheStores; 183 184 bool isProfitableToUseMemset(const DataLayout &DL) const; 185 }; 186 187 } // end anonymous namespace 188 189 bool MemsetRange::isProfitableToUseMemset(const DataLayout &DL) const { 190 // If we found more than 4 stores to merge or 16 bytes, use memset. 191 if (TheStores.size() >= 4 || End-Start >= 16) return true; 192 193 // If there is nothing to merge, don't do anything. 194 if (TheStores.size() < 2) return false; 195 196 // If any of the stores are a memset, then it is always good to extend the 197 // memset. 198 for (Instruction *SI : TheStores) 199 if (!isa<StoreInst>(SI)) 200 return true; 201 202 // Assume that the code generator is capable of merging pairs of stores 203 // together if it wants to. 204 if (TheStores.size() == 2) return false; 205 206 // If we have fewer than 8 stores, it can still be worthwhile to do this. 207 // For example, merging 4 i8 stores into an i32 store is useful almost always. 208 // However, merging 2 32-bit stores isn't useful on a 32-bit architecture (the 209 // memset will be split into 2 32-bit stores anyway) and doing so can 210 // pessimize the llvm optimizer. 211 // 212 // Since we don't have perfect knowledge here, make some assumptions: assume 213 // the maximum GPR width is the same size as the largest legal integer 214 // size. If so, check to see whether we will end up actually reducing the 215 // number of stores used. 216 unsigned Bytes = unsigned(End-Start); 217 unsigned MaxIntSize = DL.getLargestLegalIntTypeSizeInBits() / 8; 218 if (MaxIntSize == 0) 219 MaxIntSize = 1; 220 unsigned NumPointerStores = Bytes / MaxIntSize; 221 222 // Assume the remaining bytes if any are done a byte at a time. 223 unsigned NumByteStores = Bytes % MaxIntSize; 224 225 // If we will reduce the # stores (according to this heuristic), do the 226 // transformation. This encourages merging 4 x i8 -> i32 and 2 x i16 -> i32 227 // etc. 228 return TheStores.size() > NumPointerStores+NumByteStores; 229 } 230 231 namespace { 232 233 class MemsetRanges { 234 using range_iterator = SmallVectorImpl<MemsetRange>::iterator; 235 236 /// A sorted list of the memset ranges. 237 SmallVector<MemsetRange, 8> Ranges; 238 239 const DataLayout &DL; 240 241 public: 242 MemsetRanges(const DataLayout &DL) : DL(DL) {} 243 244 using const_iterator = SmallVectorImpl<MemsetRange>::const_iterator; 245 246 const_iterator begin() const { return Ranges.begin(); } 247 const_iterator end() const { return Ranges.end(); } 248 bool empty() const { return Ranges.empty(); } 249 250 void addInst(int64_t OffsetFromFirst, Instruction *Inst) { 251 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) 252 addStore(OffsetFromFirst, SI); 253 else 254 addMemSet(OffsetFromFirst, cast<MemSetInst>(Inst)); 255 } 256 257 void addStore(int64_t OffsetFromFirst, StoreInst *SI) { 258 int64_t StoreSize = DL.getTypeStoreSize(SI->getOperand(0)->getType()); 259 260 addRange(OffsetFromFirst, StoreSize, 261 SI->getPointerOperand(), SI->getAlignment(), SI); 262 } 263 264 void addMemSet(int64_t OffsetFromFirst, MemSetInst *MSI) { 265 int64_t Size = cast<ConstantInt>(MSI->getLength())->getZExtValue(); 266 addRange(OffsetFromFirst, Size, MSI->getDest(), MSI->getDestAlignment(), MSI); 267 } 268 269 void addRange(int64_t Start, int64_t Size, Value *Ptr, 270 unsigned Alignment, Instruction *Inst); 271 }; 272 273 } // end anonymous namespace 274 275 /// Add a new store to the MemsetRanges data structure. This adds a 276 /// new range for the specified store at the specified offset, merging into 277 /// existing ranges as appropriate. 278 void MemsetRanges::addRange(int64_t Start, int64_t Size, Value *Ptr, 279 unsigned Alignment, Instruction *Inst) { 280 int64_t End = Start+Size; 281 282 range_iterator I = std::lower_bound(Ranges.begin(), Ranges.end(), Start, 283 [](const MemsetRange &LHS, int64_t RHS) { return LHS.End < RHS; }); 284 285 // We now know that I == E, in which case we didn't find anything to merge 286 // with, or that Start <= I->End. If End < I->Start or I == E, then we need 287 // to insert a new range. Handle this now. 288 if (I == Ranges.end() || End < I->Start) { 289 MemsetRange &R = *Ranges.insert(I, MemsetRange()); 290 R.Start = Start; 291 R.End = End; 292 R.StartPtr = Ptr; 293 R.Alignment = Alignment; 294 R.TheStores.push_back(Inst); 295 return; 296 } 297 298 // This store overlaps with I, add it. 299 I->TheStores.push_back(Inst); 300 301 // At this point, we may have an interval that completely contains our store. 302 // If so, just add it to the interval and return. 303 if (I->Start <= Start && I->End >= End) 304 return; 305 306 // Now we know that Start <= I->End and End >= I->Start so the range overlaps 307 // but is not entirely contained within the range. 308 309 // See if the range extends the start of the range. In this case, it couldn't 310 // possibly cause it to join the prior range, because otherwise we would have 311 // stopped on *it*. 312 if (Start < I->Start) { 313 I->Start = Start; 314 I->StartPtr = Ptr; 315 I->Alignment = Alignment; 316 } 317 318 // Now we know that Start <= I->End and Start >= I->Start (so the startpoint 319 // is in or right at the end of I), and that End >= I->Start. Extend I out to 320 // End. 321 if (End > I->End) { 322 I->End = End; 323 range_iterator NextI = I; 324 while (++NextI != Ranges.end() && End >= NextI->Start) { 325 // Merge the range in. 326 I->TheStores.append(NextI->TheStores.begin(), NextI->TheStores.end()); 327 if (NextI->End > I->End) 328 I->End = NextI->End; 329 Ranges.erase(NextI); 330 NextI = I; 331 } 332 } 333 } 334 335 //===----------------------------------------------------------------------===// 336 // MemCpyOptLegacyPass Pass 337 //===----------------------------------------------------------------------===// 338 339 namespace { 340 341 class MemCpyOptLegacyPass : public FunctionPass { 342 MemCpyOptPass Impl; 343 344 public: 345 static char ID; // Pass identification, replacement for typeid 346 347 MemCpyOptLegacyPass() : FunctionPass(ID) { 348 initializeMemCpyOptLegacyPassPass(*PassRegistry::getPassRegistry()); 349 } 350 351 bool runOnFunction(Function &F) override; 352 353 private: 354 // This transformation requires dominator postdominator info 355 void getAnalysisUsage(AnalysisUsage &AU) const override { 356 AU.setPreservesCFG(); 357 AU.addRequired<AssumptionCacheTracker>(); 358 AU.addRequired<DominatorTreeWrapperPass>(); 359 AU.addRequired<MemoryDependenceWrapperPass>(); 360 AU.addRequired<AAResultsWrapperPass>(); 361 AU.addRequired<TargetLibraryInfoWrapperPass>(); 362 AU.addPreserved<GlobalsAAWrapperPass>(); 363 AU.addPreserved<MemoryDependenceWrapperPass>(); 364 } 365 }; 366 367 } // end anonymous namespace 368 369 char MemCpyOptLegacyPass::ID = 0; 370 371 /// The public interface to this file... 372 FunctionPass *llvm::createMemCpyOptPass() { return new MemCpyOptLegacyPass(); } 373 374 INITIALIZE_PASS_BEGIN(MemCpyOptLegacyPass, "memcpyopt", "MemCpy Optimization", 375 false, false) 376 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 377 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 378 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass) 379 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 380 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 381 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) 382 INITIALIZE_PASS_END(MemCpyOptLegacyPass, "memcpyopt", "MemCpy Optimization", 383 false, false) 384 385 /// When scanning forward over instructions, we look for some other patterns to 386 /// fold away. In particular, this looks for stores to neighboring locations of 387 /// memory. If it sees enough consecutive ones, it attempts to merge them 388 /// together into a memcpy/memset. 389 Instruction *MemCpyOptPass::tryMergingIntoMemset(Instruction *StartInst, 390 Value *StartPtr, 391 Value *ByteVal) { 392 const DataLayout &DL = StartInst->getModule()->getDataLayout(); 393 394 // Okay, so we now have a single store that can be splatable. Scan to find 395 // all subsequent stores of the same value to offset from the same pointer. 396 // Join these together into ranges, so we can decide whether contiguous blocks 397 // are stored. 398 MemsetRanges Ranges(DL); 399 400 BasicBlock::iterator BI(StartInst); 401 for (++BI; !isa<TerminatorInst>(BI); ++BI) { 402 if (!isa<StoreInst>(BI) && !isa<MemSetInst>(BI)) { 403 // If the instruction is readnone, ignore it, otherwise bail out. We 404 // don't even allow readonly here because we don't want something like: 405 // A[1] = 2; strlen(A); A[2] = 2; -> memcpy(A, ...); strlen(A). 406 if (BI->mayWriteToMemory() || BI->mayReadFromMemory()) 407 break; 408 continue; 409 } 410 411 if (StoreInst *NextStore = dyn_cast<StoreInst>(BI)) { 412 // If this is a store, see if we can merge it in. 413 if (!NextStore->isSimple()) break; 414 415 // Check to see if this stored value is of the same byte-splattable value. 416 if (ByteVal != isBytewiseValue(NextStore->getOperand(0))) 417 break; 418 419 // Check to see if this store is to a constant offset from the start ptr. 420 int64_t Offset; 421 if (!IsPointerOffset(StartPtr, NextStore->getPointerOperand(), Offset, 422 DL)) 423 break; 424 425 Ranges.addStore(Offset, NextStore); 426 } else { 427 MemSetInst *MSI = cast<MemSetInst>(BI); 428 429 if (MSI->isVolatile() || ByteVal != MSI->getValue() || 430 !isa<ConstantInt>(MSI->getLength())) 431 break; 432 433 // Check to see if this store is to a constant offset from the start ptr. 434 int64_t Offset; 435 if (!IsPointerOffset(StartPtr, MSI->getDest(), Offset, DL)) 436 break; 437 438 Ranges.addMemSet(Offset, MSI); 439 } 440 } 441 442 // If we have no ranges, then we just had a single store with nothing that 443 // could be merged in. This is a very common case of course. 444 if (Ranges.empty()) 445 return nullptr; 446 447 // If we had at least one store that could be merged in, add the starting 448 // store as well. We try to avoid this unless there is at least something 449 // interesting as a small compile-time optimization. 450 Ranges.addInst(0, StartInst); 451 452 // If we create any memsets, we put it right before the first instruction that 453 // isn't part of the memset block. This ensure that the memset is dominated 454 // by any addressing instruction needed by the start of the block. 455 IRBuilder<> Builder(&*BI); 456 457 // Now that we have full information about ranges, loop over the ranges and 458 // emit memset's for anything big enough to be worthwhile. 459 Instruction *AMemSet = nullptr; 460 for (const MemsetRange &Range : Ranges) { 461 if (Range.TheStores.size() == 1) continue; 462 463 // If it is profitable to lower this range to memset, do so now. 464 if (!Range.isProfitableToUseMemset(DL)) 465 continue; 466 467 // Otherwise, we do want to transform this! Create a new memset. 468 // Get the starting pointer of the block. 469 StartPtr = Range.StartPtr; 470 471 // Determine alignment 472 unsigned Alignment = Range.Alignment; 473 if (Alignment == 0) { 474 Type *EltType = 475 cast<PointerType>(StartPtr->getType())->getElementType(); 476 Alignment = DL.getABITypeAlignment(EltType); 477 } 478 479 AMemSet = 480 Builder.CreateMemSet(StartPtr, ByteVal, Range.End-Range.Start, Alignment); 481 482 LLVM_DEBUG(dbgs() << "Replace stores:\n"; for (Instruction *SI 483 : Range.TheStores) dbgs() 484 << *SI << '\n'; 485 dbgs() << "With: " << *AMemSet << '\n'); 486 487 if (!Range.TheStores.empty()) 488 AMemSet->setDebugLoc(Range.TheStores[0]->getDebugLoc()); 489 490 // Zap all the stores. 491 for (Instruction *SI : Range.TheStores) { 492 MD->removeInstruction(SI); 493 SI->eraseFromParent(); 494 } 495 ++NumMemSetInfer; 496 } 497 498 return AMemSet; 499 } 500 501 static unsigned findStoreAlignment(const DataLayout &DL, const StoreInst *SI) { 502 unsigned StoreAlign = SI->getAlignment(); 503 if (!StoreAlign) 504 StoreAlign = DL.getABITypeAlignment(SI->getOperand(0)->getType()); 505 return StoreAlign; 506 } 507 508 static unsigned findLoadAlignment(const DataLayout &DL, const LoadInst *LI) { 509 unsigned LoadAlign = LI->getAlignment(); 510 if (!LoadAlign) 511 LoadAlign = DL.getABITypeAlignment(LI->getType()); 512 return LoadAlign; 513 } 514 515 static unsigned findCommonAlignment(const DataLayout &DL, const StoreInst *SI, 516 const LoadInst *LI) { 517 unsigned StoreAlign = findStoreAlignment(DL, SI); 518 unsigned LoadAlign = findLoadAlignment(DL, LI); 519 return MinAlign(StoreAlign, LoadAlign); 520 } 521 522 // This method try to lift a store instruction before position P. 523 // It will lift the store and its argument + that anything that 524 // may alias with these. 525 // The method returns true if it was successful. 526 static bool moveUp(AliasAnalysis &AA, StoreInst *SI, Instruction *P, 527 const LoadInst *LI) { 528 // If the store alias this position, early bail out. 529 MemoryLocation StoreLoc = MemoryLocation::get(SI); 530 if (isModOrRefSet(AA.getModRefInfo(P, StoreLoc))) 531 return false; 532 533 // Keep track of the arguments of all instruction we plan to lift 534 // so we can make sure to lift them as well if appropriate. 535 DenseSet<Instruction*> Args; 536 if (auto *Ptr = dyn_cast<Instruction>(SI->getPointerOperand())) 537 if (Ptr->getParent() == SI->getParent()) 538 Args.insert(Ptr); 539 540 // Instruction to lift before P. 541 SmallVector<Instruction*, 8> ToLift; 542 543 // Memory locations of lifted instructions. 544 SmallVector<MemoryLocation, 8> MemLocs{StoreLoc}; 545 546 // Lifted callsites. 547 SmallVector<ImmutableCallSite, 8> CallSites; 548 549 const MemoryLocation LoadLoc = MemoryLocation::get(LI); 550 551 for (auto I = --SI->getIterator(), E = P->getIterator(); I != E; --I) { 552 auto *C = &*I; 553 554 bool MayAlias = isModOrRefSet(AA.getModRefInfo(C, None)); 555 556 bool NeedLift = false; 557 if (Args.erase(C)) 558 NeedLift = true; 559 else if (MayAlias) { 560 NeedLift = llvm::any_of(MemLocs, [C, &AA](const MemoryLocation &ML) { 561 return isModOrRefSet(AA.getModRefInfo(C, ML)); 562 }); 563 564 if (!NeedLift) 565 NeedLift = 566 llvm::any_of(CallSites, [C, &AA](const ImmutableCallSite &CS) { 567 return isModOrRefSet(AA.getModRefInfo(C, CS)); 568 }); 569 } 570 571 if (!NeedLift) 572 continue; 573 574 if (MayAlias) { 575 // Since LI is implicitly moved downwards past the lifted instructions, 576 // none of them may modify its source. 577 if (isModSet(AA.getModRefInfo(C, LoadLoc))) 578 return false; 579 else if (auto CS = ImmutableCallSite(C)) { 580 // If we can't lift this before P, it's game over. 581 if (isModOrRefSet(AA.getModRefInfo(P, CS))) 582 return false; 583 584 CallSites.push_back(CS); 585 } else if (isa<LoadInst>(C) || isa<StoreInst>(C) || isa<VAArgInst>(C)) { 586 // If we can't lift this before P, it's game over. 587 auto ML = MemoryLocation::get(C); 588 if (isModOrRefSet(AA.getModRefInfo(P, ML))) 589 return false; 590 591 MemLocs.push_back(ML); 592 } else 593 // We don't know how to lift this instruction. 594 return false; 595 } 596 597 ToLift.push_back(C); 598 for (unsigned k = 0, e = C->getNumOperands(); k != e; ++k) 599 if (auto *A = dyn_cast<Instruction>(C->getOperand(k))) 600 if (A->getParent() == SI->getParent()) 601 Args.insert(A); 602 } 603 604 // We made it, we need to lift 605 for (auto *I : llvm::reverse(ToLift)) { 606 LLVM_DEBUG(dbgs() << "Lifting " << *I << " before " << *P << "\n"); 607 I->moveBefore(P); 608 } 609 610 return true; 611 } 612 613 bool MemCpyOptPass::processStore(StoreInst *SI, BasicBlock::iterator &BBI) { 614 if (!SI->isSimple()) return false; 615 616 // Avoid merging nontemporal stores since the resulting 617 // memcpy/memset would not be able to preserve the nontemporal hint. 618 // In theory we could teach how to propagate the !nontemporal metadata to 619 // memset calls. However, that change would force the backend to 620 // conservatively expand !nontemporal memset calls back to sequences of 621 // store instructions (effectively undoing the merging). 622 if (SI->getMetadata(LLVMContext::MD_nontemporal)) 623 return false; 624 625 const DataLayout &DL = SI->getModule()->getDataLayout(); 626 627 // Load to store forwarding can be interpreted as memcpy. 628 if (LoadInst *LI = dyn_cast<LoadInst>(SI->getOperand(0))) { 629 if (LI->isSimple() && LI->hasOneUse() && 630 LI->getParent() == SI->getParent()) { 631 632 auto *T = LI->getType(); 633 if (T->isAggregateType()) { 634 AliasAnalysis &AA = LookupAliasAnalysis(); 635 MemoryLocation LoadLoc = MemoryLocation::get(LI); 636 637 // We use alias analysis to check if an instruction may store to 638 // the memory we load from in between the load and the store. If 639 // such an instruction is found, we try to promote there instead 640 // of at the store position. 641 Instruction *P = SI; 642 for (auto &I : make_range(++LI->getIterator(), SI->getIterator())) { 643 if (isModSet(AA.getModRefInfo(&I, LoadLoc))) { 644 P = &I; 645 break; 646 } 647 } 648 649 // We found an instruction that may write to the loaded memory. 650 // We can try to promote at this position instead of the store 651 // position if nothing alias the store memory after this and the store 652 // destination is not in the range. 653 if (P && P != SI) { 654 if (!moveUp(AA, SI, P, LI)) 655 P = nullptr; 656 } 657 658 // If a valid insertion position is found, then we can promote 659 // the load/store pair to a memcpy. 660 if (P) { 661 // If we load from memory that may alias the memory we store to, 662 // memmove must be used to preserve semantic. If not, memcpy can 663 // be used. 664 bool UseMemMove = false; 665 if (!AA.isNoAlias(MemoryLocation::get(SI), LoadLoc)) 666 UseMemMove = true; 667 668 uint64_t Size = DL.getTypeStoreSize(T); 669 670 IRBuilder<> Builder(P); 671 Instruction *M; 672 if (UseMemMove) 673 M = Builder.CreateMemMove( 674 SI->getPointerOperand(), findStoreAlignment(DL, SI), 675 LI->getPointerOperand(), findLoadAlignment(DL, LI), Size, 676 SI->isVolatile()); 677 else 678 M = Builder.CreateMemCpy( 679 SI->getPointerOperand(), findStoreAlignment(DL, SI), 680 LI->getPointerOperand(), findLoadAlignment(DL, LI), Size, 681 SI->isVolatile()); 682 683 LLVM_DEBUG(dbgs() << "Promoting " << *LI << " to " << *SI << " => " 684 << *M << "\n"); 685 686 MD->removeInstruction(SI); 687 SI->eraseFromParent(); 688 MD->removeInstruction(LI); 689 LI->eraseFromParent(); 690 ++NumMemCpyInstr; 691 692 // Make sure we do not invalidate the iterator. 693 BBI = M->getIterator(); 694 return true; 695 } 696 } 697 698 // Detect cases where we're performing call slot forwarding, but 699 // happen to be using a load-store pair to implement it, rather than 700 // a memcpy. 701 MemDepResult ldep = MD->getDependency(LI); 702 CallInst *C = nullptr; 703 if (ldep.isClobber() && !isa<MemCpyInst>(ldep.getInst())) 704 C = dyn_cast<CallInst>(ldep.getInst()); 705 706 if (C) { 707 // Check that nothing touches the dest of the "copy" between 708 // the call and the store. 709 Value *CpyDest = SI->getPointerOperand()->stripPointerCasts(); 710 bool CpyDestIsLocal = isa<AllocaInst>(CpyDest); 711 AliasAnalysis &AA = LookupAliasAnalysis(); 712 MemoryLocation StoreLoc = MemoryLocation::get(SI); 713 for (BasicBlock::iterator I = --SI->getIterator(), E = C->getIterator(); 714 I != E; --I) { 715 if (isModOrRefSet(AA.getModRefInfo(&*I, StoreLoc))) { 716 C = nullptr; 717 break; 718 } 719 // The store to dest may never happen if an exception can be thrown 720 // between the load and the store. 721 if (I->mayThrow() && !CpyDestIsLocal) { 722 C = nullptr; 723 break; 724 } 725 } 726 } 727 728 if (C) { 729 bool changed = performCallSlotOptzn( 730 LI, SI->getPointerOperand()->stripPointerCasts(), 731 LI->getPointerOperand()->stripPointerCasts(), 732 DL.getTypeStoreSize(SI->getOperand(0)->getType()), 733 findCommonAlignment(DL, SI, LI), C); 734 if (changed) { 735 MD->removeInstruction(SI); 736 SI->eraseFromParent(); 737 MD->removeInstruction(LI); 738 LI->eraseFromParent(); 739 ++NumMemCpyInstr; 740 return true; 741 } 742 } 743 } 744 } 745 746 // There are two cases that are interesting for this code to handle: memcpy 747 // and memset. Right now we only handle memset. 748 749 // Ensure that the value being stored is something that can be memset'able a 750 // byte at a time like "0" or "-1" or any width, as well as things like 751 // 0xA0A0A0A0 and 0.0. 752 auto *V = SI->getOperand(0); 753 if (Value *ByteVal = isBytewiseValue(V)) { 754 if (Instruction *I = tryMergingIntoMemset(SI, SI->getPointerOperand(), 755 ByteVal)) { 756 BBI = I->getIterator(); // Don't invalidate iterator. 757 return true; 758 } 759 760 // If we have an aggregate, we try to promote it to memset regardless 761 // of opportunity for merging as it can expose optimization opportunities 762 // in subsequent passes. 763 auto *T = V->getType(); 764 if (T->isAggregateType()) { 765 uint64_t Size = DL.getTypeStoreSize(T); 766 unsigned Align = SI->getAlignment(); 767 if (!Align) 768 Align = DL.getABITypeAlignment(T); 769 IRBuilder<> Builder(SI); 770 auto *M = Builder.CreateMemSet(SI->getPointerOperand(), ByteVal, 771 Size, Align, SI->isVolatile()); 772 773 LLVM_DEBUG(dbgs() << "Promoting " << *SI << " to " << *M << "\n"); 774 775 MD->removeInstruction(SI); 776 SI->eraseFromParent(); 777 NumMemSetInfer++; 778 779 // Make sure we do not invalidate the iterator. 780 BBI = M->getIterator(); 781 return true; 782 } 783 } 784 785 return false; 786 } 787 788 bool MemCpyOptPass::processMemSet(MemSetInst *MSI, BasicBlock::iterator &BBI) { 789 // See if there is another memset or store neighboring this memset which 790 // allows us to widen out the memset to do a single larger store. 791 if (isa<ConstantInt>(MSI->getLength()) && !MSI->isVolatile()) 792 if (Instruction *I = tryMergingIntoMemset(MSI, MSI->getDest(), 793 MSI->getValue())) { 794 BBI = I->getIterator(); // Don't invalidate iterator. 795 return true; 796 } 797 return false; 798 } 799 800 /// Takes a memcpy and a call that it depends on, 801 /// and checks for the possibility of a call slot optimization by having 802 /// the call write its result directly into the destination of the memcpy. 803 bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpy, Value *cpyDest, 804 Value *cpySrc, uint64_t cpyLen, 805 unsigned cpyAlign, CallInst *C) { 806 // The general transformation to keep in mind is 807 // 808 // call @func(..., src, ...) 809 // memcpy(dest, src, ...) 810 // 811 // -> 812 // 813 // memcpy(dest, src, ...) 814 // call @func(..., dest, ...) 815 // 816 // Since moving the memcpy is technically awkward, we additionally check that 817 // src only holds uninitialized values at the moment of the call, meaning that 818 // the memcpy can be discarded rather than moved. 819 820 // Lifetime marks shouldn't be operated on. 821 if (Function *F = C->getCalledFunction()) 822 if (F->isIntrinsic() && F->getIntrinsicID() == Intrinsic::lifetime_start) 823 return false; 824 825 // Deliberately get the source and destination with bitcasts stripped away, 826 // because we'll need to do type comparisons based on the underlying type. 827 CallSite CS(C); 828 829 // Require that src be an alloca. This simplifies the reasoning considerably. 830 AllocaInst *srcAlloca = dyn_cast<AllocaInst>(cpySrc); 831 if (!srcAlloca) 832 return false; 833 834 ConstantInt *srcArraySize = dyn_cast<ConstantInt>(srcAlloca->getArraySize()); 835 if (!srcArraySize) 836 return false; 837 838 const DataLayout &DL = cpy->getModule()->getDataLayout(); 839 uint64_t srcSize = DL.getTypeAllocSize(srcAlloca->getAllocatedType()) * 840 srcArraySize->getZExtValue(); 841 842 if (cpyLen < srcSize) 843 return false; 844 845 // Check that accessing the first srcSize bytes of dest will not cause a 846 // trap. Otherwise the transform is invalid since it might cause a trap 847 // to occur earlier than it otherwise would. 848 if (AllocaInst *A = dyn_cast<AllocaInst>(cpyDest)) { 849 // The destination is an alloca. Check it is larger than srcSize. 850 ConstantInt *destArraySize = dyn_cast<ConstantInt>(A->getArraySize()); 851 if (!destArraySize) 852 return false; 853 854 uint64_t destSize = DL.getTypeAllocSize(A->getAllocatedType()) * 855 destArraySize->getZExtValue(); 856 857 if (destSize < srcSize) 858 return false; 859 } else if (Argument *A = dyn_cast<Argument>(cpyDest)) { 860 // The store to dest may never happen if the call can throw. 861 if (C->mayThrow()) 862 return false; 863 864 if (A->getDereferenceableBytes() < srcSize) { 865 // If the destination is an sret parameter then only accesses that are 866 // outside of the returned struct type can trap. 867 if (!A->hasStructRetAttr()) 868 return false; 869 870 Type *StructTy = cast<PointerType>(A->getType())->getElementType(); 871 if (!StructTy->isSized()) { 872 // The call may never return and hence the copy-instruction may never 873 // be executed, and therefore it's not safe to say "the destination 874 // has at least <cpyLen> bytes, as implied by the copy-instruction", 875 return false; 876 } 877 878 uint64_t destSize = DL.getTypeAllocSize(StructTy); 879 if (destSize < srcSize) 880 return false; 881 } 882 } else { 883 return false; 884 } 885 886 // Check that dest points to memory that is at least as aligned as src. 887 unsigned srcAlign = srcAlloca->getAlignment(); 888 if (!srcAlign) 889 srcAlign = DL.getABITypeAlignment(srcAlloca->getAllocatedType()); 890 bool isDestSufficientlyAligned = srcAlign <= cpyAlign; 891 // If dest is not aligned enough and we can't increase its alignment then 892 // bail out. 893 if (!isDestSufficientlyAligned && !isa<AllocaInst>(cpyDest)) 894 return false; 895 896 // Check that src is not accessed except via the call and the memcpy. This 897 // guarantees that it holds only undefined values when passed in (so the final 898 // memcpy can be dropped), that it is not read or written between the call and 899 // the memcpy, and that writing beyond the end of it is undefined. 900 SmallVector<User*, 8> srcUseList(srcAlloca->user_begin(), 901 srcAlloca->user_end()); 902 while (!srcUseList.empty()) { 903 User *U = srcUseList.pop_back_val(); 904 905 if (isa<BitCastInst>(U) || isa<AddrSpaceCastInst>(U)) { 906 for (User *UU : U->users()) 907 srcUseList.push_back(UU); 908 continue; 909 } 910 if (GetElementPtrInst *G = dyn_cast<GetElementPtrInst>(U)) { 911 if (!G->hasAllZeroIndices()) 912 return false; 913 914 for (User *UU : U->users()) 915 srcUseList.push_back(UU); 916 continue; 917 } 918 if (const IntrinsicInst *IT = dyn_cast<IntrinsicInst>(U)) 919 if (IT->getIntrinsicID() == Intrinsic::lifetime_start || 920 IT->getIntrinsicID() == Intrinsic::lifetime_end) 921 continue; 922 923 if (U != C && U != cpy) 924 return false; 925 } 926 927 // Check that src isn't captured by the called function since the 928 // transformation can cause aliasing issues in that case. 929 for (unsigned i = 0, e = CS.arg_size(); i != e; ++i) 930 if (CS.getArgument(i) == cpySrc && !CS.doesNotCapture(i)) 931 return false; 932 933 // Since we're changing the parameter to the callsite, we need to make sure 934 // that what would be the new parameter dominates the callsite. 935 DominatorTree &DT = LookupDomTree(); 936 if (Instruction *cpyDestInst = dyn_cast<Instruction>(cpyDest)) 937 if (!DT.dominates(cpyDestInst, C)) 938 return false; 939 940 // In addition to knowing that the call does not access src in some 941 // unexpected manner, for example via a global, which we deduce from 942 // the use analysis, we also need to know that it does not sneakily 943 // access dest. We rely on AA to figure this out for us. 944 AliasAnalysis &AA = LookupAliasAnalysis(); 945 ModRefInfo MR = AA.getModRefInfo(C, cpyDest, srcSize); 946 // If necessary, perform additional analysis. 947 if (isModOrRefSet(MR)) 948 MR = AA.callCapturesBefore(C, cpyDest, srcSize, &DT); 949 if (isModOrRefSet(MR)) 950 return false; 951 952 // We can't create address space casts here because we don't know if they're 953 // safe for the target. 954 if (cpySrc->getType()->getPointerAddressSpace() != 955 cpyDest->getType()->getPointerAddressSpace()) 956 return false; 957 for (unsigned i = 0; i < CS.arg_size(); ++i) 958 if (CS.getArgument(i)->stripPointerCasts() == cpySrc && 959 cpySrc->getType()->getPointerAddressSpace() != 960 CS.getArgument(i)->getType()->getPointerAddressSpace()) 961 return false; 962 963 // All the checks have passed, so do the transformation. 964 bool changedArgument = false; 965 for (unsigned i = 0; i < CS.arg_size(); ++i) 966 if (CS.getArgument(i)->stripPointerCasts() == cpySrc) { 967 Value *Dest = cpySrc->getType() == cpyDest->getType() ? cpyDest 968 : CastInst::CreatePointerCast(cpyDest, cpySrc->getType(), 969 cpyDest->getName(), C); 970 changedArgument = true; 971 if (CS.getArgument(i)->getType() == Dest->getType()) 972 CS.setArgument(i, Dest); 973 else 974 CS.setArgument(i, CastInst::CreatePointerCast(Dest, 975 CS.getArgument(i)->getType(), Dest->getName(), C)); 976 } 977 978 if (!changedArgument) 979 return false; 980 981 // If the destination wasn't sufficiently aligned then increase its alignment. 982 if (!isDestSufficientlyAligned) { 983 assert(isa<AllocaInst>(cpyDest) && "Can only increase alloca alignment!"); 984 cast<AllocaInst>(cpyDest)->setAlignment(srcAlign); 985 } 986 987 // Drop any cached information about the call, because we may have changed 988 // its dependence information by changing its parameter. 989 MD->removeInstruction(C); 990 991 // Update AA metadata 992 // FIXME: MD_tbaa_struct and MD_mem_parallel_loop_access should also be 993 // handled here, but combineMetadata doesn't support them yet 994 unsigned KnownIDs[] = {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope, 995 LLVMContext::MD_noalias, 996 LLVMContext::MD_invariant_group}; 997 combineMetadata(C, cpy, KnownIDs); 998 999 // Remove the memcpy. 1000 MD->removeInstruction(cpy); 1001 ++NumMemCpyInstr; 1002 1003 return true; 1004 } 1005 1006 /// We've found that the (upward scanning) memory dependence of memcpy 'M' is 1007 /// the memcpy 'MDep'. Try to simplify M to copy from MDep's input if we can. 1008 bool MemCpyOptPass::processMemCpyMemCpyDependence(MemCpyInst *M, 1009 MemCpyInst *MDep) { 1010 // We can only transforms memcpy's where the dest of one is the source of the 1011 // other. 1012 if (M->getSource() != MDep->getDest() || MDep->isVolatile()) 1013 return false; 1014 1015 // If dep instruction is reading from our current input, then it is a noop 1016 // transfer and substituting the input won't change this instruction. Just 1017 // ignore the input and let someone else zap MDep. This handles cases like: 1018 // memcpy(a <- a) 1019 // memcpy(b <- a) 1020 if (M->getSource() == MDep->getSource()) 1021 return false; 1022 1023 // Second, the length of the memcpy's must be the same, or the preceding one 1024 // must be larger than the following one. 1025 ConstantInt *MDepLen = dyn_cast<ConstantInt>(MDep->getLength()); 1026 ConstantInt *MLen = dyn_cast<ConstantInt>(M->getLength()); 1027 if (!MDepLen || !MLen || MDepLen->getZExtValue() < MLen->getZExtValue()) 1028 return false; 1029 1030 AliasAnalysis &AA = LookupAliasAnalysis(); 1031 1032 // Verify that the copied-from memory doesn't change in between the two 1033 // transfers. For example, in: 1034 // memcpy(a <- b) 1035 // *b = 42; 1036 // memcpy(c <- a) 1037 // It would be invalid to transform the second memcpy into memcpy(c <- b). 1038 // 1039 // TODO: If the code between M and MDep is transparent to the destination "c", 1040 // then we could still perform the xform by moving M up to the first memcpy. 1041 // 1042 // NOTE: This is conservative, it will stop on any read from the source loc, 1043 // not just the defining memcpy. 1044 MemDepResult SourceDep = 1045 MD->getPointerDependencyFrom(MemoryLocation::getForSource(MDep), false, 1046 M->getIterator(), M->getParent()); 1047 if (!SourceDep.isClobber() || SourceDep.getInst() != MDep) 1048 return false; 1049 1050 // If the dest of the second might alias the source of the first, then the 1051 // source and dest might overlap. We still want to eliminate the intermediate 1052 // value, but we have to generate a memmove instead of memcpy. 1053 bool UseMemMove = false; 1054 if (!AA.isNoAlias(MemoryLocation::getForDest(M), 1055 MemoryLocation::getForSource(MDep))) 1056 UseMemMove = true; 1057 1058 // If all checks passed, then we can transform M. 1059 1060 // TODO: Is this worth it if we're creating a less aligned memcpy? For 1061 // example we could be moving from movaps -> movq on x86. 1062 IRBuilder<> Builder(M); 1063 if (UseMemMove) 1064 Builder.CreateMemMove(M->getRawDest(), M->getDestAlignment(), 1065 MDep->getRawSource(), MDep->getSourceAlignment(), 1066 M->getLength(), M->isVolatile()); 1067 else 1068 Builder.CreateMemCpy(M->getRawDest(), M->getDestAlignment(), 1069 MDep->getRawSource(), MDep->getSourceAlignment(), 1070 M->getLength(), M->isVolatile()); 1071 1072 // Remove the instruction we're replacing. 1073 MD->removeInstruction(M); 1074 M->eraseFromParent(); 1075 ++NumMemCpyInstr; 1076 return true; 1077 } 1078 1079 /// We've found that the (upward scanning) memory dependence of \p MemCpy is 1080 /// \p MemSet. Try to simplify \p MemSet to only set the trailing bytes that 1081 /// weren't copied over by \p MemCpy. 1082 /// 1083 /// In other words, transform: 1084 /// \code 1085 /// memset(dst, c, dst_size); 1086 /// memcpy(dst, src, src_size); 1087 /// \endcode 1088 /// into: 1089 /// \code 1090 /// memcpy(dst, src, src_size); 1091 /// memset(dst + src_size, c, dst_size <= src_size ? 0 : dst_size - src_size); 1092 /// \endcode 1093 bool MemCpyOptPass::processMemSetMemCpyDependence(MemCpyInst *MemCpy, 1094 MemSetInst *MemSet) { 1095 // We can only transform memset/memcpy with the same destination. 1096 if (MemSet->getDest() != MemCpy->getDest()) 1097 return false; 1098 1099 // Check that there are no other dependencies on the memset destination. 1100 MemDepResult DstDepInfo = 1101 MD->getPointerDependencyFrom(MemoryLocation::getForDest(MemSet), false, 1102 MemCpy->getIterator(), MemCpy->getParent()); 1103 if (DstDepInfo.getInst() != MemSet) 1104 return false; 1105 1106 // Use the same i8* dest as the memcpy, killing the memset dest if different. 1107 Value *Dest = MemCpy->getRawDest(); 1108 Value *DestSize = MemSet->getLength(); 1109 Value *SrcSize = MemCpy->getLength(); 1110 1111 // By default, create an unaligned memset. 1112 unsigned Align = 1; 1113 // If Dest is aligned, and SrcSize is constant, use the minimum alignment 1114 // of the sum. 1115 const unsigned DestAlign = 1116 std::max(MemSet->getDestAlignment(), MemCpy->getDestAlignment()); 1117 if (DestAlign > 1) 1118 if (ConstantInt *SrcSizeC = dyn_cast<ConstantInt>(SrcSize)) 1119 Align = MinAlign(SrcSizeC->getZExtValue(), DestAlign); 1120 1121 IRBuilder<> Builder(MemCpy); 1122 1123 // If the sizes have different types, zext the smaller one. 1124 if (DestSize->getType() != SrcSize->getType()) { 1125 if (DestSize->getType()->getIntegerBitWidth() > 1126 SrcSize->getType()->getIntegerBitWidth()) 1127 SrcSize = Builder.CreateZExt(SrcSize, DestSize->getType()); 1128 else 1129 DestSize = Builder.CreateZExt(DestSize, SrcSize->getType()); 1130 } 1131 1132 Value *Ule = Builder.CreateICmpULE(DestSize, SrcSize); 1133 Value *SizeDiff = Builder.CreateSub(DestSize, SrcSize); 1134 Value *MemsetLen = Builder.CreateSelect( 1135 Ule, ConstantInt::getNullValue(DestSize->getType()), SizeDiff); 1136 Builder.CreateMemSet(Builder.CreateGEP(Dest, SrcSize), MemSet->getOperand(1), 1137 MemsetLen, Align); 1138 1139 MD->removeInstruction(MemSet); 1140 MemSet->eraseFromParent(); 1141 return true; 1142 } 1143 1144 /// Transform memcpy to memset when its source was just memset. 1145 /// In other words, turn: 1146 /// \code 1147 /// memset(dst1, c, dst1_size); 1148 /// memcpy(dst2, dst1, dst2_size); 1149 /// \endcode 1150 /// into: 1151 /// \code 1152 /// memset(dst1, c, dst1_size); 1153 /// memset(dst2, c, dst2_size); 1154 /// \endcode 1155 /// When dst2_size <= dst1_size. 1156 /// 1157 /// The \p MemCpy must have a Constant length. 1158 bool MemCpyOptPass::performMemCpyToMemSetOptzn(MemCpyInst *MemCpy, 1159 MemSetInst *MemSet) { 1160 AliasAnalysis &AA = LookupAliasAnalysis(); 1161 1162 // Make sure that memcpy(..., memset(...), ...), that is we are memsetting and 1163 // memcpying from the same address. Otherwise it is hard to reason about. 1164 if (!AA.isMustAlias(MemSet->getRawDest(), MemCpy->getRawSource())) 1165 return false; 1166 1167 ConstantInt *CopySize = cast<ConstantInt>(MemCpy->getLength()); 1168 ConstantInt *MemSetSize = dyn_cast<ConstantInt>(MemSet->getLength()); 1169 // Make sure the memcpy doesn't read any more than what the memset wrote. 1170 // Don't worry about sizes larger than i64. 1171 if (!MemSetSize || CopySize->getZExtValue() > MemSetSize->getZExtValue()) 1172 return false; 1173 1174 IRBuilder<> Builder(MemCpy); 1175 Builder.CreateMemSet(MemCpy->getRawDest(), MemSet->getOperand(1), 1176 CopySize, MemCpy->getDestAlignment()); 1177 return true; 1178 } 1179 1180 /// Perform simplification of memcpy's. If we have memcpy A 1181 /// which copies X to Y, and memcpy B which copies Y to Z, then we can rewrite 1182 /// B to be a memcpy from X to Z (or potentially a memmove, depending on 1183 /// circumstances). This allows later passes to remove the first memcpy 1184 /// altogether. 1185 bool MemCpyOptPass::processMemCpy(MemCpyInst *M) { 1186 // We can only optimize non-volatile memcpy's. 1187 if (M->isVolatile()) return false; 1188 1189 // If the source and destination of the memcpy are the same, then zap it. 1190 if (M->getSource() == M->getDest()) { 1191 MD->removeInstruction(M); 1192 M->eraseFromParent(); 1193 return false; 1194 } 1195 1196 // If copying from a constant, try to turn the memcpy into a memset. 1197 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getSource())) 1198 if (GV->isConstant() && GV->hasDefinitiveInitializer()) 1199 if (Value *ByteVal = isBytewiseValue(GV->getInitializer())) { 1200 IRBuilder<> Builder(M); 1201 Builder.CreateMemSet(M->getRawDest(), ByteVal, M->getLength(), 1202 M->getDestAlignment(), false); 1203 MD->removeInstruction(M); 1204 M->eraseFromParent(); 1205 ++NumCpyToSet; 1206 return true; 1207 } 1208 1209 MemDepResult DepInfo = MD->getDependency(M); 1210 1211 // Try to turn a partially redundant memset + memcpy into 1212 // memcpy + smaller memset. We don't need the memcpy size for this. 1213 if (DepInfo.isClobber()) 1214 if (MemSetInst *MDep = dyn_cast<MemSetInst>(DepInfo.getInst())) 1215 if (processMemSetMemCpyDependence(M, MDep)) 1216 return true; 1217 1218 // The optimizations after this point require the memcpy size. 1219 ConstantInt *CopySize = dyn_cast<ConstantInt>(M->getLength()); 1220 if (!CopySize) return false; 1221 1222 // There are four possible optimizations we can do for memcpy: 1223 // a) memcpy-memcpy xform which exposes redundance for DSE. 1224 // b) call-memcpy xform for return slot optimization. 1225 // c) memcpy from freshly alloca'd space or space that has just started its 1226 // lifetime copies undefined data, and we can therefore eliminate the 1227 // memcpy in favor of the data that was already at the destination. 1228 // d) memcpy from a just-memset'd source can be turned into memset. 1229 if (DepInfo.isClobber()) { 1230 if (CallInst *C = dyn_cast<CallInst>(DepInfo.getInst())) { 1231 // FIXME: Can we pass in either of dest/src alignment here instead 1232 // of conservatively taking the minimum? 1233 unsigned Align = MinAlign(M->getDestAlignment(), M->getSourceAlignment()); 1234 if (performCallSlotOptzn(M, M->getDest(), M->getSource(), 1235 CopySize->getZExtValue(), Align, 1236 C)) { 1237 MD->removeInstruction(M); 1238 M->eraseFromParent(); 1239 return true; 1240 } 1241 } 1242 } 1243 1244 MemoryLocation SrcLoc = MemoryLocation::getForSource(M); 1245 MemDepResult SrcDepInfo = MD->getPointerDependencyFrom( 1246 SrcLoc, true, M->getIterator(), M->getParent()); 1247 1248 if (SrcDepInfo.isClobber()) { 1249 if (MemCpyInst *MDep = dyn_cast<MemCpyInst>(SrcDepInfo.getInst())) 1250 return processMemCpyMemCpyDependence(M, MDep); 1251 } else if (SrcDepInfo.isDef()) { 1252 Instruction *I = SrcDepInfo.getInst(); 1253 bool hasUndefContents = false; 1254 1255 if (isa<AllocaInst>(I)) { 1256 hasUndefContents = true; 1257 } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 1258 if (II->getIntrinsicID() == Intrinsic::lifetime_start) 1259 if (ConstantInt *LTSize = dyn_cast<ConstantInt>(II->getArgOperand(0))) 1260 if (LTSize->getZExtValue() >= CopySize->getZExtValue()) 1261 hasUndefContents = true; 1262 } 1263 1264 if (hasUndefContents) { 1265 MD->removeInstruction(M); 1266 M->eraseFromParent(); 1267 ++NumMemCpyInstr; 1268 return true; 1269 } 1270 } 1271 1272 if (SrcDepInfo.isClobber()) 1273 if (MemSetInst *MDep = dyn_cast<MemSetInst>(SrcDepInfo.getInst())) 1274 if (performMemCpyToMemSetOptzn(M, MDep)) { 1275 MD->removeInstruction(M); 1276 M->eraseFromParent(); 1277 ++NumCpyToSet; 1278 return true; 1279 } 1280 1281 return false; 1282 } 1283 1284 /// Transforms memmove calls to memcpy calls when the src/dst are guaranteed 1285 /// not to alias. 1286 bool MemCpyOptPass::processMemMove(MemMoveInst *M) { 1287 AliasAnalysis &AA = LookupAliasAnalysis(); 1288 1289 if (!TLI->has(LibFunc_memmove)) 1290 return false; 1291 1292 // See if the pointers alias. 1293 if (!AA.isNoAlias(MemoryLocation::getForDest(M), 1294 MemoryLocation::getForSource(M))) 1295 return false; 1296 1297 LLVM_DEBUG(dbgs() << "MemCpyOptPass: Optimizing memmove -> memcpy: " << *M 1298 << "\n"); 1299 1300 // If not, then we know we can transform this. 1301 Type *ArgTys[3] = { M->getRawDest()->getType(), 1302 M->getRawSource()->getType(), 1303 M->getLength()->getType() }; 1304 M->setCalledFunction(Intrinsic::getDeclaration(M->getModule(), 1305 Intrinsic::memcpy, ArgTys)); 1306 1307 // MemDep may have over conservative information about this instruction, just 1308 // conservatively flush it from the cache. 1309 MD->removeInstruction(M); 1310 1311 ++NumMoveToCpy; 1312 return true; 1313 } 1314 1315 /// This is called on every byval argument in call sites. 1316 bool MemCpyOptPass::processByValArgument(CallSite CS, unsigned ArgNo) { 1317 const DataLayout &DL = CS.getCaller()->getParent()->getDataLayout(); 1318 // Find out what feeds this byval argument. 1319 Value *ByValArg = CS.getArgument(ArgNo); 1320 Type *ByValTy = cast<PointerType>(ByValArg->getType())->getElementType(); 1321 uint64_t ByValSize = DL.getTypeAllocSize(ByValTy); 1322 MemDepResult DepInfo = MD->getPointerDependencyFrom( 1323 MemoryLocation(ByValArg, ByValSize), true, 1324 CS.getInstruction()->getIterator(), CS.getInstruction()->getParent()); 1325 if (!DepInfo.isClobber()) 1326 return false; 1327 1328 // If the byval argument isn't fed by a memcpy, ignore it. If it is fed by 1329 // a memcpy, see if we can byval from the source of the memcpy instead of the 1330 // result. 1331 MemCpyInst *MDep = dyn_cast<MemCpyInst>(DepInfo.getInst()); 1332 if (!MDep || MDep->isVolatile() || 1333 ByValArg->stripPointerCasts() != MDep->getDest()) 1334 return false; 1335 1336 // The length of the memcpy must be larger or equal to the size of the byval. 1337 ConstantInt *C1 = dyn_cast<ConstantInt>(MDep->getLength()); 1338 if (!C1 || C1->getValue().getZExtValue() < ByValSize) 1339 return false; 1340 1341 // Get the alignment of the byval. If the call doesn't specify the alignment, 1342 // then it is some target specific value that we can't know. 1343 unsigned ByValAlign = CS.getParamAlignment(ArgNo); 1344 if (ByValAlign == 0) return false; 1345 1346 // If it is greater than the memcpy, then we check to see if we can force the 1347 // source of the memcpy to the alignment we need. If we fail, we bail out. 1348 AssumptionCache &AC = LookupAssumptionCache(); 1349 DominatorTree &DT = LookupDomTree(); 1350 if (MDep->getSourceAlignment() < ByValAlign && 1351 getOrEnforceKnownAlignment(MDep->getSource(), ByValAlign, DL, 1352 CS.getInstruction(), &AC, &DT) < ByValAlign) 1353 return false; 1354 1355 // The address space of the memcpy source must match the byval argument 1356 if (MDep->getSource()->getType()->getPointerAddressSpace() != 1357 ByValArg->getType()->getPointerAddressSpace()) 1358 return false; 1359 1360 // Verify that the copied-from memory doesn't change in between the memcpy and 1361 // the byval call. 1362 // memcpy(a <- b) 1363 // *b = 42; 1364 // foo(*a) 1365 // It would be invalid to transform the second memcpy into foo(*b). 1366 // 1367 // NOTE: This is conservative, it will stop on any read from the source loc, 1368 // not just the defining memcpy. 1369 MemDepResult SourceDep = MD->getPointerDependencyFrom( 1370 MemoryLocation::getForSource(MDep), false, 1371 CS.getInstruction()->getIterator(), MDep->getParent()); 1372 if (!SourceDep.isClobber() || SourceDep.getInst() != MDep) 1373 return false; 1374 1375 Value *TmpCast = MDep->getSource(); 1376 if (MDep->getSource()->getType() != ByValArg->getType()) 1377 TmpCast = new BitCastInst(MDep->getSource(), ByValArg->getType(), 1378 "tmpcast", CS.getInstruction()); 1379 1380 LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n" 1381 << " " << *MDep << "\n" 1382 << " " << *CS.getInstruction() << "\n"); 1383 1384 // Otherwise we're good! Update the byval argument. 1385 CS.setArgument(ArgNo, TmpCast); 1386 ++NumMemCpyInstr; 1387 return true; 1388 } 1389 1390 /// Executes one iteration of MemCpyOptPass. 1391 bool MemCpyOptPass::iterateOnFunction(Function &F) { 1392 bool MadeChange = false; 1393 1394 DominatorTree &DT = LookupDomTree(); 1395 1396 // Walk all instruction in the function. 1397 for (BasicBlock &BB : F) { 1398 // Skip unreachable blocks. For example processStore assumes that an 1399 // instruction in a BB can't be dominated by a later instruction in the 1400 // same BB (which is a scenario that can happen for an unreachable BB that 1401 // has itself as a predecessor). 1402 if (!DT.isReachableFromEntry(&BB)) 1403 continue; 1404 1405 for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) { 1406 // Avoid invalidating the iterator. 1407 Instruction *I = &*BI++; 1408 1409 bool RepeatInstruction = false; 1410 1411 if (StoreInst *SI = dyn_cast<StoreInst>(I)) 1412 MadeChange |= processStore(SI, BI); 1413 else if (MemSetInst *M = dyn_cast<MemSetInst>(I)) 1414 RepeatInstruction = processMemSet(M, BI); 1415 else if (MemCpyInst *M = dyn_cast<MemCpyInst>(I)) 1416 RepeatInstruction = processMemCpy(M); 1417 else if (MemMoveInst *M = dyn_cast<MemMoveInst>(I)) 1418 RepeatInstruction = processMemMove(M); 1419 else if (auto CS = CallSite(I)) { 1420 for (unsigned i = 0, e = CS.arg_size(); i != e; ++i) 1421 if (CS.isByValArgument(i)) 1422 MadeChange |= processByValArgument(CS, i); 1423 } 1424 1425 // Reprocess the instruction if desired. 1426 if (RepeatInstruction) { 1427 if (BI != BB.begin()) 1428 --BI; 1429 MadeChange = true; 1430 } 1431 } 1432 } 1433 1434 return MadeChange; 1435 } 1436 1437 PreservedAnalyses MemCpyOptPass::run(Function &F, FunctionAnalysisManager &AM) { 1438 auto &MD = AM.getResult<MemoryDependenceAnalysis>(F); 1439 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 1440 1441 auto LookupAliasAnalysis = [&]() -> AliasAnalysis & { 1442 return AM.getResult<AAManager>(F); 1443 }; 1444 auto LookupAssumptionCache = [&]() -> AssumptionCache & { 1445 return AM.getResult<AssumptionAnalysis>(F); 1446 }; 1447 auto LookupDomTree = [&]() -> DominatorTree & { 1448 return AM.getResult<DominatorTreeAnalysis>(F); 1449 }; 1450 1451 bool MadeChange = runImpl(F, &MD, &TLI, LookupAliasAnalysis, 1452 LookupAssumptionCache, LookupDomTree); 1453 if (!MadeChange) 1454 return PreservedAnalyses::all(); 1455 1456 PreservedAnalyses PA; 1457 PA.preserveSet<CFGAnalyses>(); 1458 PA.preserve<GlobalsAA>(); 1459 PA.preserve<MemoryDependenceAnalysis>(); 1460 return PA; 1461 } 1462 1463 bool MemCpyOptPass::runImpl( 1464 Function &F, MemoryDependenceResults *MD_, TargetLibraryInfo *TLI_, 1465 std::function<AliasAnalysis &()> LookupAliasAnalysis_, 1466 std::function<AssumptionCache &()> LookupAssumptionCache_, 1467 std::function<DominatorTree &()> LookupDomTree_) { 1468 bool MadeChange = false; 1469 MD = MD_; 1470 TLI = TLI_; 1471 LookupAliasAnalysis = std::move(LookupAliasAnalysis_); 1472 LookupAssumptionCache = std::move(LookupAssumptionCache_); 1473 LookupDomTree = std::move(LookupDomTree_); 1474 1475 // If we don't have at least memset and memcpy, there is little point of doing 1476 // anything here. These are required by a freestanding implementation, so if 1477 // even they are disabled, there is no point in trying hard. 1478 if (!TLI->has(LibFunc_memset) || !TLI->has(LibFunc_memcpy)) 1479 return false; 1480 1481 while (true) { 1482 if (!iterateOnFunction(F)) 1483 break; 1484 MadeChange = true; 1485 } 1486 1487 MD = nullptr; 1488 return MadeChange; 1489 } 1490 1491 /// This is the main transformation entry point for a function. 1492 bool MemCpyOptLegacyPass::runOnFunction(Function &F) { 1493 if (skipFunction(F)) 1494 return false; 1495 1496 auto *MD = &getAnalysis<MemoryDependenceWrapperPass>().getMemDep(); 1497 auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 1498 1499 auto LookupAliasAnalysis = [this]() -> AliasAnalysis & { 1500 return getAnalysis<AAResultsWrapperPass>().getAAResults(); 1501 }; 1502 auto LookupAssumptionCache = [this, &F]() -> AssumptionCache & { 1503 return getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 1504 }; 1505 auto LookupDomTree = [this]() -> DominatorTree & { 1506 return getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1507 }; 1508 1509 return Impl.runImpl(F, MD, TLI, LookupAliasAnalysis, LookupAssumptionCache, 1510 LookupDomTree); 1511 } 1512