LLVM 24.0.0git
MemCpyOptimizer.cpp
Go to the documentation of this file.
1//===- MemCpyOptimizer.cpp - Optimize use of memcpy and friends -----------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass performs various transformations related to eliminating memcpy
10// calls, or transforming sets of stores into memset's.
11//
12//===----------------------------------------------------------------------===//
13
15#include "llvm/ADT/DenseSet.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/ScopeExit.h"
19#include "llvm/ADT/Statistic.h"
23#include "llvm/Analysis/CFG.h"
27#include "llvm/Analysis/Loads.h"
34#include "llvm/IR/BasicBlock.h"
35#include "llvm/IR/Constants.h"
36#include "llvm/IR/DataLayout.h"
38#include "llvm/IR/Dominators.h"
39#include "llvm/IR/Function.h"
41#include "llvm/IR/IRBuilder.h"
42#include "llvm/IR/InstrTypes.h"
43#include "llvm/IR/Instruction.h"
46#include "llvm/IR/Intrinsics.h"
47#include "llvm/IR/LLVMContext.h"
48#include "llvm/IR/Module.h"
49#include "llvm/IR/PassManager.h"
51#include "llvm/IR/Type.h"
52#include "llvm/IR/User.h"
53#include "llvm/IR/Value.h"
55#include "llvm/Support/Debug.h"
58#include <algorithm>
59#include <cassert>
60#include <cstdint>
61#include <optional>
62
63using namespace llvm;
64
65#define DEBUG_TYPE "memcpyopt"
66
67STATISTIC(NumMemCpyInstr, "Number of memcpy instructions deleted");
68STATISTIC(NumMemMoveInstr, "Number of memmove instructions deleted");
69STATISTIC(NumMemSetInfer, "Number of memsets inferred");
70STATISTIC(NumMoveToCpy, "Number of memmoves converted to memcpy");
71STATISTIC(NumCpyToSet, "Number of memcpys converted to memset");
72STATISTIC(NumCallSlot, "Number of call slot optimizations performed");
73STATISTIC(NumStackMove, "Number of stack-move optimizations performed");
74
75namespace {
76
77/// Represents a range of memset'd bytes with the ByteVal value.
78/// This allows us to analyze stores like:
79/// store 0 -> P+1
80/// store 0 -> P+0
81/// store 0 -> P+3
82/// store 0 -> P+2
83/// which sometimes happens with stores to arrays of structs etc. When we see
84/// the first store, we make a range [1, 2). The second store extends the range
85/// to [0, 2). The third makes a new range [2, 3). The fourth store joins the
86/// two ranges into [0, 3) which is memset'able.
87struct MemsetRange {
88 // Start/End - A semi range that describes the span that this range covers.
89 // The range is closed at the start and open at the end: [Start, End).
90 int64_t Start, End;
91
92 /// StartPtr - The getelementptr instruction that points to the start of the
93 /// range.
94 Value *StartPtr;
95
96 /// Alignment - The known alignment of the first store.
97 MaybeAlign Alignment;
98
99 /// TheStores - The actual stores that make up this range.
101
102 bool isProfitableToUseMemset(const DataLayout &DL) const;
103};
104
105} // end anonymous namespace
106
107static bool overreadUndefContents(MemorySSA *MSSA, MemCpyInst *MemCpy,
108 MemIntrinsic *MemSrc, BatchAAResults &BAA);
109
110bool MemsetRange::isProfitableToUseMemset(const DataLayout &DL) const {
111 // If we found more than 4 stores to merge or 16 bytes, use memset.
112 if (TheStores.size() >= 4 || End - Start >= 16)
113 return true;
114
115 // If there is nothing to merge, don't do anything.
116 if (TheStores.size() < 2)
117 return false;
118
119 // If any of the stores are a memset, then it is always good to extend the
120 // memset.
121 for (Instruction *SI : TheStores)
122 if (!isa<StoreInst>(SI))
123 return true;
124
125 // Assume that the code generator is capable of merging pairs of stores
126 // together if it wants to.
127 if (TheStores.size() == 2)
128 return false;
129
130 // If we have fewer than 8 stores, it can still be worthwhile to do this.
131 // For example, merging 4 i8 stores into an i32 store is useful almost always.
132 // However, merging 2 32-bit stores isn't useful on a 32-bit architecture (the
133 // memset will be split into 2 32-bit stores anyway) and doing so can
134 // pessimize the llvm optimizer.
135 //
136 // Since we don't have perfect knowledge here, make some assumptions: assume
137 // the maximum GPR width is the same size as the largest legal integer
138 // size. If so, check to see whether we will end up actually reducing the
139 // number of stores used.
140 unsigned Bytes = unsigned(End - Start);
141 unsigned MaxIntSize = DL.getLargestLegalIntTypeSizeInBits() / 8;
142 if (MaxIntSize == 0)
143 MaxIntSize = 1;
144 unsigned NumPointerStores = Bytes / MaxIntSize;
145
146 // Assume the remaining bytes if any are done a byte at a time.
147 unsigned NumByteStores = Bytes % MaxIntSize;
148
149 // If we will reduce the # stores (according to this heuristic), do the
150 // transformation. This encourages merging 4 x i8 -> i32 and 2 x i16 -> i32
151 // etc.
152 return TheStores.size() > NumPointerStores + NumByteStores;
153}
154
155namespace {
156
157class MemsetRanges {
158 using range_iterator = SmallVectorImpl<MemsetRange>::iterator;
159
160 /// A sorted list of the memset ranges.
162
163 const DataLayout &DL;
164
165public:
166 MemsetRanges(const DataLayout &DL) : DL(DL) {}
167
169
170 const_iterator begin() const { return Ranges.begin(); }
171 const_iterator end() const { return Ranges.end(); }
172 bool empty() const { return Ranges.empty(); }
173
174 void addInst(int64_t OffsetFromFirst, Instruction *Inst) {
175 if (auto *SI = dyn_cast<StoreInst>(Inst))
176 addStore(OffsetFromFirst, SI);
177 else
178 addMemSet(OffsetFromFirst, cast<MemSetInst>(Inst));
179 }
180
181 void addStore(int64_t OffsetFromFirst, StoreInst *SI) {
182 TypeSize StoreSize = DL.getTypeStoreSize(SI->getOperand(0)->getType());
183 assert(!StoreSize.isScalable() && "Can't track scalable-typed stores");
184 addRange(OffsetFromFirst, StoreSize.getFixedValue(),
185 SI->getPointerOperand(), SI->getAlign(), SI);
186 }
187
188 void addMemSet(int64_t OffsetFromFirst, MemSetInst *MSI) {
189 int64_t Size = cast<ConstantInt>(MSI->getLength())->getZExtValue();
190 addRange(OffsetFromFirst, Size, MSI->getDest(), MSI->getDestAlign(), MSI);
191 }
192
193 void addRange(int64_t Start, int64_t Size, Value *Ptr, MaybeAlign Alignment,
194 Instruction *Inst);
195};
196
197} // end anonymous namespace
198
199/// Add a new store to the MemsetRanges data structure. This adds a
200/// new range for the specified store at the specified offset, merging into
201/// existing ranges as appropriate.
202void MemsetRanges::addRange(int64_t Start, int64_t Size, Value *Ptr,
203 MaybeAlign Alignment, Instruction *Inst) {
204 int64_t End = Start + Size;
205
206 range_iterator I = partition_point(
207 Ranges, [=](const MemsetRange &O) { return O.End < Start; });
208
209 // We now know that I == E, in which case we didn't find anything to merge
210 // with, or that Start <= I->End. If End < I->Start or I == E, then we need
211 // to insert a new range. Handle this now.
212 if (I == Ranges.end() || End < I->Start) {
213 MemsetRange &R = *Ranges.insert(I, MemsetRange());
214 R.Start = Start;
215 R.End = End;
216 R.StartPtr = Ptr;
217 R.Alignment = Alignment;
218 R.TheStores.push_back(Inst);
219 return;
220 }
221
222 // This store overlaps with I, add it.
223 I->TheStores.push_back(Inst);
224
225 // At this point, we may have an interval that completely contains our store.
226 // If so, just add it to the interval and return.
227 if (I->Start <= Start && I->End >= End)
228 return;
229
230 // Now we know that Start <= I->End and End >= I->Start so the range overlaps
231 // but is not entirely contained within the range.
232
233 // See if the range extends the start of the range. In this case, it couldn't
234 // possibly cause it to join the prior range, because otherwise we would have
235 // stopped on *it*.
236 if (Start < I->Start) {
237 I->Start = Start;
238 I->StartPtr = Ptr;
239 I->Alignment = Alignment;
240 }
241
242 // Now we know that Start <= I->End and Start >= I->Start (so the startpoint
243 // is in or right at the end of I), and that End >= I->Start. Extend I out to
244 // End.
245 if (End > I->End) {
246 I->End = End;
247 range_iterator NextI = I;
248 while (++NextI != Ranges.end() && End >= NextI->Start) {
249 // Merge the range in.
250 I->TheStores.append(NextI->TheStores.begin(), NextI->TheStores.end());
251 if (NextI->End > I->End)
252 I->End = NextI->End;
253 Ranges.erase(NextI);
254 NextI = I;
255 }
256 }
257}
258
259//===----------------------------------------------------------------------===//
260// MemCpyOptLegacyPass Pass
261//===----------------------------------------------------------------------===//
262
263// Check that V is either not accessible by the caller, or unwinding cannot
264// occur between Start and End.
266 Instruction *End) {
267 assert(Start->getParent() == End->getParent() && "Must be in same block");
268 // Function can't unwind, so it also can't be visible through unwinding.
269 if (Start->getFunction()->doesNotThrow())
270 return false;
271
272 // Object is not visible on unwind.
273 // TODO: Support RequiresNoCaptureBeforeUnwind case.
274 bool RequiresNoCaptureBeforeUnwind;
276 RequiresNoCaptureBeforeUnwind) &&
277 !RequiresNoCaptureBeforeUnwind)
278 return false;
279
280 // Check whether there are any unwinding instructions in the range.
281 return any_of(make_range(Start->getIterator(), End->getIterator()),
282 [](const Instruction &I) { return I.mayThrow(); });
283}
284
285void MemCpyOptPass::eraseInstruction(Instruction *I) {
286 MSSAU->removeMemoryAccess(I);
287 EEA->removeInstruction(I);
288 I->eraseFromParent();
289}
290
291// Check for mod or ref of Loc between Start and End, excluding both boundaries.
292// Start and End must be in the same block.
293// If SkippedLifetimeStart is provided, skip over one clobbering lifetime.start
294// intrinsic and store it inside SkippedLifetimeStart.
296 const MemoryUseOrDef *Start,
297 const MemoryUseOrDef *End,
298 Instruction **SkippedLifetimeStart = nullptr) {
299 assert(Start->getBlock() == End->getBlock() && "Only local supported");
300 for (const MemoryAccess &MA :
301 make_range(++Start->getIterator(), End->getIterator())) {
302 Instruction *I = cast<MemoryUseOrDef>(MA).getMemoryInst();
303 if (isModOrRefSet(AA.getModRefInfo(I, Loc))) {
305 if (II && II->getIntrinsicID() == Intrinsic::lifetime_start &&
306 SkippedLifetimeStart && !*SkippedLifetimeStart) {
307 *SkippedLifetimeStart = I;
308 continue;
309 }
310
311 return true;
312 }
313 }
314 return false;
315}
316
317// Check for mod of Loc between Start and End, excluding both boundaries.
318// Start and End can be in different blocks.
320 MemoryLocation Loc, const MemoryUseOrDef *Start,
321 const MemoryUseOrDef *End) {
322 if (isa<MemoryUse>(End)) {
323 // For MemoryUses, getClobberingMemoryAccess may skip non-clobbering writes.
324 // Manually check read accesses between Start and End, if they are in the
325 // same block, for clobbers. Otherwise assume Loc is clobbered.
326 return Start->getBlock() != End->getBlock() ||
327 any_of(
328 make_range(std::next(Start->getIterator()), End->getIterator()),
329 [&AA, Loc](const MemoryAccess &Acc) {
330 if (isa<MemoryUse>(&Acc))
331 return false;
332 Instruction *AccInst =
333 cast<MemoryUseOrDef>(&Acc)->getMemoryInst();
334 return isModSet(AA.getModRefInfo(AccInst, Loc));
335 });
336 }
337
338 // TODO: Only walk until we hit Start.
340 End->getDefiningAccess(), Loc, AA);
341 return !MSSA->dominates(Clobber, Start);
342}
343
344/// When scanning forward over instructions, we look for some other patterns to
345/// fold away. In particular, this looks for stores to neighboring locations of
346/// memory. If it sees enough consecutive ones, it attempts to merge them
347/// together into a memcpy/memset.
348Instruction *MemCpyOptPass::tryMergingIntoMemset(Instruction *StartInst,
349 Value *StartPtr,
350 Value *ByteVal) {
351 const DataLayout &DL = StartInst->getDataLayout();
352
353 // We can't track scalable types
354 if (auto *SI = dyn_cast<StoreInst>(StartInst))
355 if (DL.getTypeStoreSize(SI->getOperand(0)->getType()).isScalable())
356 return nullptr;
357
358 // Okay, so we now have a single store that can be splatable. Scan to find
359 // all subsequent stores of the same value to offset from the same pointer.
360 // Join these together into ranges, so we can decide whether contiguous blocks
361 // are stored.
362 MemsetRanges Ranges(DL);
363
364 BasicBlock::iterator BI(StartInst);
365
366 // Keeps track of the last memory use or def before the insertion point for
367 // the new memset. The new MemoryDef for the inserted memsets will be inserted
368 // after MemInsertPoint.
369 MemoryUseOrDef *MemInsertPoint = nullptr;
370 for (++BI; !BI->isTerminator(); ++BI) {
371 auto *CurrentAcc =
372 cast_or_null<MemoryUseOrDef>(MSSA->getMemoryAccess(&*BI));
373 if (CurrentAcc)
374 MemInsertPoint = CurrentAcc;
375
376 // Calls that only access inaccessible memory do not block merging
377 // accessible stores.
378 if (auto *CB = dyn_cast<CallBase>(BI)) {
379 if (CB->onlyAccessesInaccessibleMemory())
380 continue;
381 }
382
383 if (!isa<StoreInst>(BI) && !isa<MemSetInst>(BI)) {
384 // If the instruction is readnone, ignore it, otherwise bail out. We
385 // don't even allow readonly here because we don't want something like:
386 // A[1] = 2; strlen(A); A[2] = 2; -> memcpy(A, ...); strlen(A).
387 if (BI->mayWriteToMemory() || BI->mayReadFromMemory())
388 break;
389 continue;
390 }
391
392 if (auto *NextStore = dyn_cast<StoreInst>(BI)) {
393 // If this is a store, see if we can merge it in.
394 if (!NextStore->isSimple())
395 break;
396
397 Value *StoredVal = NextStore->getValueOperand();
398
399 // Don't convert stores of non-integral pointer types to memsets (which
400 // stores integers).
401 if (DL.isNonIntegralPointerType(StoredVal->getType()->getScalarType()))
402 break;
403
404 // We can't track ranges involving scalable types.
405 if (DL.getTypeStoreSize(StoredVal->getType()).isScalable())
406 break;
407
408 // Check to see if this stored value is of the same byte-splattable value.
409 Value *StoredByte = isBytewiseValue(StoredVal, DL);
410 // We can blindly merge this store into `StartInst` if it's being filled
411 // with an undef value but we don't because:
412 // 1. `StartInst` can be removed since it's storing an `undef`.
413 // 2. The resulting memset will be much larger than it needs to be.
414 if (ByteVal != StoredByte)
415 break;
416
417 // Check to see if this store is to a constant offset from the start ptr.
418 std::optional<int64_t> Offset =
419 NextStore->getPointerOperand()->getPointerOffsetFrom(StartPtr, DL);
420 if (!Offset)
421 break;
422
423 Ranges.addStore(*Offset, NextStore);
424 } else {
425 auto *MSI = cast<MemSetInst>(BI);
426
427 if (MSI->isVolatile() || ByteVal != MSI->getValue() ||
428 !isa<ConstantInt>(MSI->getLength()))
429 break;
430
431 // Check to see if this store is to a constant offset from the start ptr.
432 std::optional<int64_t> Offset =
433 MSI->getDest()->getPointerOffsetFrom(StartPtr, DL);
434 if (!Offset)
435 break;
436
437 Ranges.addMemSet(*Offset, MSI);
438 }
439 }
440
441 // If we have no ranges, then we just had a single store with nothing that
442 // could be merged in. This is a very common case of course.
443 if (Ranges.empty())
444 return nullptr;
445
446 // If we had at least one store that could be merged in, add the starting
447 // store as well. We try to avoid this unless there is at least something
448 // interesting as a small compile-time optimization.
449 Ranges.addInst(0, StartInst);
450
451 // If we create any memsets, we put it right before the first instruction that
452 // isn't part of the memset block. This ensure that the memset is dominated
453 // by any addressing instruction needed by the start of the block.
454 IRBuilder<> Builder(&*BI);
455
456 // Now that we have full information about ranges, loop over the ranges and
457 // emit memset's for anything big enough to be worthwhile.
458 Instruction *AMemSet = nullptr;
459 for (const MemsetRange &Range : Ranges) {
460 if (Range.TheStores.size() == 1)
461 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 AMemSet = Builder.CreateMemSet(StartPtr, ByteVal, Range.End - Range.Start,
472 Range.Alignment);
473 AMemSet->mergeDIAssignID(Range.TheStores);
474
475 LLVM_DEBUG(dbgs() << "Replace stores:\n"; for (Instruction *SI
476 : Range.TheStores) dbgs()
477 << *SI << '\n';
478 dbgs() << "With: " << *AMemSet << '\n');
479 if (!Range.TheStores.empty())
480 AMemSet->setDebugLoc(Range.TheStores[0]->getDebugLoc());
481
482 auto *NewDef = cast<MemoryDef>(
483 MemInsertPoint->getMemoryInst() == &*BI
484 ? MSSAU->createMemoryAccessBefore(AMemSet, nullptr, MemInsertPoint)
485 : MSSAU->createMemoryAccessAfter(AMemSet, nullptr, MemInsertPoint));
486 MSSAU->insertDef(NewDef, /*RenameUses=*/true);
487 MemInsertPoint = NewDef;
488
489 // Zap all the stores.
490 for (Instruction *SI : Range.TheStores)
492
493 ++NumMemSetInfer;
494 }
495
496 return AMemSet;
497}
498
499// This method try to lift a store instruction before position P.
500// It will lift the store and its argument + that anything that
501// may alias with these.
502// The method returns true if it was successful.
503bool MemCpyOptPass::moveUp(StoreInst *SI, Instruction *P, const LoadInst *LI) {
504 // If the store alias this position, early bail out.
505 MemoryLocation StoreLoc = MemoryLocation::get(SI);
506 if (isModOrRefSet(AA->getModRefInfo(P, StoreLoc)))
507 return false;
508
509 // Keep track of the arguments of all instruction we plan to lift
510 // so we can make sure to lift them as well if appropriate.
511 DenseSet<Instruction *> Args;
512 auto AddArg = [&](Value *Arg) {
513 auto *I = dyn_cast<Instruction>(Arg);
514 if (I && I->getParent() == SI->getParent()) {
515 // Cannot hoist user of P above P
516 if (I == P)
517 return false;
518 Args.insert(I);
519 }
520 return true;
521 };
522 if (!AddArg(SI->getPointerOperand()))
523 return false;
524
525 // Instruction to lift before P.
526 SmallVector<Instruction *, 8> ToLift{SI};
527
528 // Memory locations of lifted instructions.
529 SmallVector<MemoryLocation, 8> MemLocs{StoreLoc};
530
531 // Lifted calls.
533
534 const MemoryLocation LoadLoc = MemoryLocation::get(LI);
535
536 for (auto I = --SI->getIterator(), E = P->getIterator(); I != E; --I) {
537 auto *C = &*I;
538
539 // Make sure hoisting does not perform a store that was not guaranteed to
540 // happen.
542 return false;
543
544 bool MayAlias = isModOrRefSet(AA->getModRefInfo(C, std::nullopt));
545
546 bool NeedLift = false;
547 if (Args.erase(C))
548 NeedLift = true;
549 else if (MayAlias) {
550 NeedLift = llvm::any_of(MemLocs, [C, this](const MemoryLocation &ML) {
551 return isModOrRefSet(AA->getModRefInfo(C, ML));
552 });
553
554 if (!NeedLift)
555 NeedLift = llvm::any_of(Calls, [C, this](const CallBase *Call) {
556 return isModOrRefSet(AA->getModRefInfo(C, Call));
557 });
558 }
559
560 if (!NeedLift)
561 continue;
562
563 if (MayAlias) {
564 // Since LI is implicitly moved downwards past the lifted instructions,
565 // none of them may modify its source.
566 if (isModSet(AA->getModRefInfo(C, LoadLoc)))
567 return false;
568 else if (const auto *Call = dyn_cast<CallBase>(C)) {
569 // If we can't lift this before P, it's game over.
570 if (isModOrRefSet(AA->getModRefInfo(P, Call)))
571 return false;
572
573 Calls.push_back(Call);
574 } else if (isa<LoadInst>(C) || isa<StoreInst>(C) || isa<VAArgInst>(C)) {
575 // If we can't lift this before P, it's game over.
576 auto ML = MemoryLocation::get(C);
577 if (isModOrRefSet(AA->getModRefInfo(P, ML)))
578 return false;
579
580 MemLocs.push_back(ML);
581 } else
582 // We don't know how to lift this instruction.
583 return false;
584 }
585
586 ToLift.push_back(C);
587 for (Value *Op : C->operands())
588 if (!AddArg(Op))
589 return false;
590 }
591
592 // Find MSSA insertion point. Normally P will always have a corresponding
593 // memory access before which we can insert. However, with non-standard AA
594 // pipelines, there may be a mismatch between AA and MSSA, in which case we
595 // will scan for a memory access before P. In either case, we know for sure
596 // that at least the load will have a memory access.
597 // TODO: Simplify this once P will be determined by MSSA, in which case the
598 // discrepancy can no longer occur.
599 MemoryUseOrDef *MemInsertPoint = nullptr;
600 if (MemoryUseOrDef *MA = MSSA->getMemoryAccess(P)) {
601 MemInsertPoint = cast<MemoryUseOrDef>(--MA->getIterator());
602 } else {
603 const Instruction *ConstP = P;
604 for (const Instruction &I : make_range(++ConstP->getReverseIterator(),
605 ++LI->getReverseIterator())) {
606 if (MemoryUseOrDef *MA = MSSA->getMemoryAccess(&I)) {
607 MemInsertPoint = MA;
608 break;
609 }
610 }
611 }
612
613 // We made it, we need to lift.
614 for (auto *I : llvm::reverse(ToLift)) {
615 LLVM_DEBUG(dbgs() << "Lifting " << *I << " before " << *P << "\n");
616 EEA->insertPotentialCapture(I);
617 I->moveBefore(P->getIterator());
618 assert(MemInsertPoint && "Must have found insert point");
619 if (MemoryUseOrDef *MA = MSSA->getMemoryAccess(I)) {
620 MSSAU->moveAfter(MA, MemInsertPoint);
621 MemInsertPoint = MA;
622 }
623 }
624
625 return true;
626}
627
628bool MemCpyOptPass::processStoreOfLoad(StoreInst *SI, LoadInst *LI,
629 const DataLayout &DL,
631 if (!LI->isSimple() || !LI->hasOneUse() || LI->getParent() != SI->getParent())
632 return false;
633
634 BatchAAResults BAA(*AA, EEA);
635 auto *T = LI->getType();
636 if (T->isAggregateType()) {
637 MemoryLocation LoadLoc = MemoryLocation::get(LI);
638
639 // We use alias analysis to check if an instruction may store to
640 // the memory we load from in between the load and the store. If
641 // such an instruction is found, we try to promote there instead
642 // of at the store position.
643 // TODO: Can use MSSA for this.
644 Instruction *P = SI;
645 for (auto &I : make_range(++LI->getIterator(), SI->getIterator())) {
646 if (isModSet(BAA.getModRefInfo(&I, LoadLoc))) {
647 P = &I;
648 break;
649 }
650 }
651
652 // If we found an instruction that may write to the loaded memory,
653 // we can try to promote at this position instead of the store
654 // position if nothing aliases the store memory after this and the store
655 // destination is not in the range.
656 if (P == SI || moveUp(SI, P, LI)) {
657 // If we load from memory that may alias the memory we store to,
658 // memmove must be used to preserve semantic. If not, memcpy can
659 // be used. Also, if we load from constant memory, memcpy can be used
660 // as the constant memory won't be modified.
661 bool UseMemMove = false;
662 if (isModSet(AA->getModRefInfo(SI, LoadLoc)))
663 UseMemMove = true;
664
665 IRBuilder<> Builder(P);
666 Value *Size =
667 Builder.CreateTypeSize(Builder.getInt64Ty(), DL.getTypeStoreSize(T));
668 Instruction *M;
669 if (UseMemMove)
670 M = Builder.CreateMemMove(SI->getPointerOperand(), SI->getAlign(),
671 LI->getPointerOperand(), LI->getAlign(),
672 Size);
673 else
674 M = Builder.CreateMemCpy(SI->getPointerOperand(), SI->getAlign(),
675 LI->getPointerOperand(), LI->getAlign(), Size);
676 M->copyMetadata(*SI, LLVMContext::MD_DIAssignID);
677
678 LLVM_DEBUG(dbgs() << "Promoting " << *LI << " to " << *SI << " => " << *M
679 << "\n");
680
681 auto *LastDef = cast<MemoryDef>(MSSA->getMemoryAccess(SI));
682 auto *NewAccess = MSSAU->createMemoryAccessAfter(M, nullptr, LastDef);
683 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
684
687 ++NumMemCpyInstr;
688
689 // Make sure we do not invalidate the iterator.
690 BBI = M->getIterator();
691 return true;
692 }
693 }
694
695 // Detect cases where we're performing call slot forwarding, but
696 // happen to be using a load-store pair to implement it, rather than
697 // a memcpy.
698 auto GetCall = [&]() -> CallInst * {
699 // We defer this expensive clobber walk until the cheap checks
700 // have been done on the source inside performCallSlotOptzn.
701 if (auto *LoadClobber = dyn_cast<MemoryUseOrDef>(
702 MSSA->getWalker()->getClobberingMemoryAccess(LI, BAA)))
703 return dyn_cast_or_null<CallInst>(LoadClobber->getMemoryInst());
704 return nullptr;
705 };
706
707 bool Changed = performCallSlotOptzn(
708 LI, SI, SI->getPointerOperand()->stripPointerCasts(),
710 DL.getTypeStoreSize(SI->getOperand(0)->getType()),
711 std::min(SI->getAlign(), LI->getAlign()), BAA, GetCall);
712 if (Changed) {
715 ++NumMemCpyInstr;
716 return true;
717 }
718
719 // If this is a load-store pair from a stack slot to a stack slot, we
720 // might be able to perform the stack-move optimization just as we do for
721 // memcpys from an alloca to an alloca.
722 if (performStackMoveOptzn(LI, SI, SI->getPointerOperand(),
723 LI->getPointerOperand(), DL.getTypeStoreSize(T),
724 BAA)) {
725 // Avoid invalidating the iterator.
726 BBI = SI->getNextNode()->getIterator();
729 ++NumMemCpyInstr;
730 return true;
731 }
732
733 return false;
734}
735
736bool MemCpyOptPass::processStore(StoreInst *SI, BasicBlock::iterator &BBI) {
737 if (!SI->isSimple())
738 return false;
739
740 // Avoid merging nontemporal stores since the resulting
741 // memcpy/memset would not be able to preserve the nontemporal hint.
742 // In theory we could teach how to propagate the !nontemporal metadata to
743 // memset calls. However, that change would force the backend to
744 // conservatively expand !nontemporal memset calls back to sequences of
745 // store instructions (effectively undoing the merging).
746 if (SI->getMetadata(LLVMContext::MD_nontemporal))
747 return false;
748
749 const DataLayout &DL = SI->getDataLayout();
750
751 Value *StoredVal = SI->getValueOperand();
752
753 // Not all the transforms below are correct for non-integral pointers, bail
754 // until we've audited the individual pieces.
755 if (DL.isNonIntegralPointerType(StoredVal->getType()->getScalarType()))
756 return false;
757
758 // Load to store forwarding can be interpreted as memcpy.
759 if (auto *LI = dyn_cast<LoadInst>(StoredVal))
760 return processStoreOfLoad(SI, LI, DL, BBI);
761
762 // There are two cases that are interesting for this code to handle: memcpy
763 // and memset. Right now we only handle memset.
764
765 // Ensure that the value being stored is something that can be memset'able a
766 // byte at a time like "0" or "-1" or any width, as well as things like
767 // 0xA0A0A0A0 and 0.0.
768 Value *V = SI->getOperand(0);
769 Value *ByteVal = isBytewiseValue(V, DL);
770 if (!ByteVal)
771 return false;
772
773 if (Instruction *I =
774 tryMergingIntoMemset(SI, SI->getPointerOperand(), ByteVal)) {
775 BBI = I->getIterator(); // Don't invalidate iterator.
776 return true;
777 }
778
779 // If we have an aggregate, we try to promote it to memset regardless
780 // of opportunity for merging as it can expose optimization opportunities
781 // in subsequent passes.
782 auto *T = V->getType();
783 if (!T->isAggregateType())
784 return false;
785
786 TypeSize Size = DL.getTypeStoreSize(T);
787 if (Size.isScalable())
788 return false;
789
790 IRBuilder<> Builder(SI);
791 auto *M = Builder.CreateMemSet(SI->getPointerOperand(), ByteVal, Size,
792 SI->getAlign());
793 M->copyMetadata(*SI, LLVMContext::MD_DIAssignID);
794
795 LLVM_DEBUG(dbgs() << "Promoting " << *SI << " to " << *M << "\n");
796
797 // The newly inserted memset is immediately overwritten by the original
798 // store, so we do not need to rename uses.
799 auto *StoreDef = cast<MemoryDef>(MSSA->getMemoryAccess(SI));
800 auto *NewAccess = MSSAU->createMemoryAccessBefore(M, nullptr, StoreDef);
801 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/false);
802
804 NumMemSetInfer++;
805
806 // Make sure we do not invalidate the iterator.
807 BBI = M->getIterator();
808 return true;
809}
810
811bool MemCpyOptPass::processMemSet(MemSetInst *MSI, BasicBlock::iterator &BBI) {
812 // See if there is another memset or store neighboring this memset which
813 // allows us to widen out the memset to do a single larger store.
814 if (isa<ConstantInt>(MSI->getLength()) && !MSI->isVolatile())
815 if (Instruction *I =
816 tryMergingIntoMemset(MSI, MSI->getDest(), MSI->getValue())) {
817 BBI = I->getIterator(); // Don't invalidate iterator.
818 return true;
819 }
820 return false;
821}
822
823/// Takes a memcpy and a call that it depends on,
824/// and checks for the possibility of a call slot optimization by having
825/// the call write its result directly into the destination of the memcpy.
826bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpyLoad,
827 Instruction *cpyStore, Value *cpyDest,
828 Value *cpySrc, TypeSize cpySize,
829 Align cpyDestAlign,
830 BatchAAResults &BAA,
831 std::function<CallInst *()> GetC) {
832 // The general transformation to keep in mind is
833 //
834 // call @func(..., src, ...)
835 // memcpy(dest, src, ...)
836 //
837 // ->
838 //
839 // memcpy(dest, src, ...)
840 // call @func(..., dest, ...)
841 //
842 // Since moving the memcpy is technically awkward, we additionally check that
843 // src only holds uninitialized values at the moment of the call, meaning that
844 // the memcpy can be discarded rather than moved.
845
846 // We can't optimize scalable types.
847 if (cpySize.isScalable())
848 return false;
849
850 // Require that src be an alloca. This simplifies the reasoning considerably.
851 auto *srcAlloca = dyn_cast<AllocaInst>(cpySrc);
852 if (!srcAlloca)
853 return false;
854
855 const DataLayout &DL = cpyLoad->getDataLayout();
856 // We can't optimize scalable types or variable-length allocas.
857 std::optional<TypeSize> SrcAllocaSize = srcAlloca->getAllocationSize(DL);
858 if (!SrcAllocaSize || SrcAllocaSize->isScalable())
859 return false;
860 uint64_t srcSize = SrcAllocaSize->getFixedValue();
861
862 if (cpySize < srcSize)
863 return false;
864
865 CallInst *C = GetC();
866 if (!C)
867 return false;
868
869 // Lifetime marks shouldn't be operated on.
870 if (Function *F = C->getCalledFunction())
871 if (F->isIntrinsic() && F->getIntrinsicID() == Intrinsic::lifetime_start)
872 return false;
873
874 if (C->getParent() != cpyStore->getParent()) {
875 LLVM_DEBUG(dbgs() << "Call Slot: block local restriction\n");
876 return false;
877 }
878
879 MemoryLocation DestLoc =
880 isa<StoreInst>(cpyStore)
881 ? MemoryLocation::get(cpyStore)
882 : MemoryLocation::getForDest(cast<MemCpyInst>(cpyStore));
883
884 // Check that nothing touches the dest of the copy between
885 // the call and the store/memcpy.
886 Instruction *SkippedLifetimeStart = nullptr;
887 if (accessedBetween(BAA, DestLoc, MSSA->getMemoryAccess(C),
888 MSSA->getMemoryAccess(cpyStore), &SkippedLifetimeStart)) {
889 LLVM_DEBUG(dbgs() << "Call Slot: Dest pointer modified after call\n");
890 return false;
891 }
892
893 // If we need to move a lifetime.start above the call, make sure that we can
894 // actually do so. If the argument is bitcasted for example, we would have to
895 // move the bitcast as well, which we don't handle.
896 if (SkippedLifetimeStart) {
897 auto *LifetimeArg =
898 dyn_cast<Instruction>(SkippedLifetimeStart->getOperand(0));
899 if (LifetimeArg && LifetimeArg->getParent() == C->getParent() &&
900 C->comesBefore(LifetimeArg))
901 return false;
902 }
903
904 // Check that storing to the first srcSize bytes of dest will not cause a
905 // trap or data race.
906 bool ExplicitlyDereferenceableOnly;
908 ExplicitlyDereferenceableOnly) ||
909 !isDereferenceablePointer(cpyDest, APInt(64, cpySize),
910 SimplifyQuery(DL, DT, AC, C))) {
911 // If the call is guaranteed to return normally (willreturn + nounwind),
912 // and there are no instructions between the call and the store that might
913 // trap or throw, execution will reach the store. Since the store would
914 // trap anyway if the pointer was not dereferenceable, we can forward the
915 // pointer to the call. Perform optimization only for non-memcpy/memset
916 // calls, as those are special cased later.
918 cpyStore->getIterator())) {
919 LLVM_DEBUG(dbgs() << "Call Slot: Dest pointer not dereferenceable\n");
920 return false;
921 }
922 }
923
924 // Make sure that nothing can observe cpyDest being written early. There are
925 // a number of cases to consider:
926 // 1. cpyDest cannot be accessed between C and cpyStore as a precondition of
927 // the transform.
928 // 2. C itself may not access cpyDest (prior to the transform). This is
929 // checked further below.
930 // 3. If cpyDest is accessible to the caller of this function (potentially
931 // captured and not based on an alloca), we need to ensure that we cannot
932 // unwind between C and cpyStore. This is checked here.
933 // 4. If cpyDest is potentially captured, there may be accesses to it from
934 // another thread. In this case, we need to check that cpyStore is
935 // guaranteed to be executed if C is. As it is a non-atomic access, it
936 // renders accesses from other threads undefined.
937 // TODO: This is currently not checked.
938 if (mayBeVisibleThroughUnwinding(cpyDest, C, cpyStore)) {
939 LLVM_DEBUG(dbgs() << "Call Slot: Dest may be visible through unwinding\n");
940 return false;
941 }
942
943 // Check that dest points to memory that is at least as aligned as src.
944 Align srcAlign = srcAlloca->getAlign();
945 bool isDestSufficientlyAligned = srcAlign <= cpyDestAlign;
946 // If dest is not aligned enough and we can't increase its alignment then
947 // bail out.
948 if (!isDestSufficientlyAligned && !isa<AllocaInst>(cpyDest)) {
949 LLVM_DEBUG(dbgs() << "Call Slot: Dest not sufficiently aligned\n");
950 return false;
951 }
952
953 // Check that src is not accessed except via the call and the memcpy. This
954 // guarantees that it holds only undefined values when passed in (so the final
955 // memcpy can be dropped), that it is not read or written between the call and
956 // the memcpy, and that writing beyond the end of it is undefined.
957 SmallVector<User *, 8> srcUseList(srcAlloca->users());
958 while (!srcUseList.empty()) {
959 User *U = srcUseList.pop_back_val();
960
961 if (isa<AddrSpaceCastInst>(U)) {
962 append_range(srcUseList, U->users());
963 continue;
964 }
966 continue;
967
968 if (U != C && U != cpyLoad) {
969 LLVM_DEBUG(dbgs() << "Call slot: Source accessed by " << *U << "\n");
970 return false;
971 }
972 }
973
974 // Check whether src is captured by the called function, in which case there
975 // may be further indirect uses of src.
976 bool SrcIsCaptured = any_of(C->args(), [&](Use &U) {
977 return U->stripPointerCasts() == cpySrc &&
978 !C->doesNotCapture(C->getArgOperandNo(&U));
979 });
980
981 // If src is captured, then check whether there are any potential uses of
982 // src through the captured pointer before the lifetime of src ends, either
983 // due to a lifetime.end or a return from the function.
984 if (SrcIsCaptured) {
985 // Check that dest is not captured before/at the call. We have already
986 // checked that src is not captured before it. If either had been captured,
987 // then the call might be comparing the argument against the captured dest
988 // or src pointer.
989 Value *DestObj = getUnderlyingObject(cpyDest);
990 if (!isIdentifiedFunctionLocal(DestObj) ||
991 PointerMayBeCapturedBefore(DestObj, /* ReturnCaptures */ true, C, DT,
992 /* IncludeI */ true))
993 return false;
994
995 MemoryLocation SrcLoc =
996 MemoryLocation(srcAlloca, LocationSize::precise(srcSize));
997 for (Instruction &I :
998 make_range(++C->getIterator(), C->getParent()->end())) {
999 // Lifetime of srcAlloca ends at lifetime.end.
1000 if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
1001 if (II->getIntrinsicID() == Intrinsic::lifetime_end &&
1002 II->getArgOperand(0) == srcAlloca)
1003 break;
1004 }
1005
1006 // Lifetime of srcAlloca ends at return.
1007 if (isa<ReturnInst>(&I))
1008 break;
1009
1010 // Ignore the direct read of src in the load.
1011 if (&I == cpyLoad)
1012 continue;
1013
1014 // Check whether this instruction may mod/ref src through the captured
1015 // pointer (we have already any direct mod/refs in the loop above).
1016 // Also bail if we hit a terminator, as we don't want to scan into other
1017 // blocks.
1018 if (isModOrRefSet(BAA.getModRefInfo(&I, SrcLoc)) || I.isTerminator())
1019 return false;
1020 }
1021 }
1022
1023 // Since we're changing the parameter to the callsite, we need to make sure
1024 // that what would be the new parameter dominates the callsite.
1025 bool NeedMoveGEP = false;
1026 if (!DT->dominates(cpyDest, C)) {
1027 // Support moving a constant index GEP before the call.
1028 auto *GEP = dyn_cast<GetElementPtrInst>(cpyDest);
1029 if (GEP && GEP->hasAllConstantIndices() &&
1030 DT->dominates(GEP->getPointerOperand(), C))
1031 NeedMoveGEP = true;
1032 else
1033 return false;
1034 }
1035
1036 // In addition to knowing that the call does not access src in some
1037 // unexpected manner, for example via a global, which we deduce from
1038 // the use analysis, we also need to know that it does not sneakily
1039 // access dest. We rely on AA to figure this out for us.
1040 MemoryLocation DestWithSrcSize(cpyDest, LocationSize::precise(srcSize));
1041 ModRefInfo MR = BAA.getModRefInfo(C, DestWithSrcSize);
1042 // If necessary, perform additional analysis.
1043 if (isModOrRefSet(MR))
1044 MR = BAA.callCapturesBefore(C, DestWithSrcSize, DT);
1045 if (isModOrRefSet(MR))
1046 return false;
1047
1048 // We can't create address space casts here because we don't know if they're
1049 // safe for the target.
1050 if (cpySrc->getType() != cpyDest->getType())
1051 return false;
1052 for (unsigned ArgI = 0; ArgI < C->arg_size(); ++ArgI)
1053 if (C->getArgOperand(ArgI)->stripPointerCasts() == cpySrc &&
1054 cpySrc->getType() != C->getArgOperand(ArgI)->getType())
1055 return false;
1056
1057 // All the checks have passed, so do the transformation.
1058 bool changedArgument = false;
1059 for (unsigned ArgI = 0; ArgI < C->arg_size(); ++ArgI)
1060 if (C->getArgOperand(ArgI)->stripPointerCasts() == cpySrc) {
1061 changedArgument = true;
1062 C->setArgOperand(ArgI, cpyDest);
1063 }
1064
1065 if (!changedArgument)
1066 return false;
1067
1068 // If the destination wasn't sufficiently aligned then increase its alignment.
1069 if (!isDestSufficientlyAligned) {
1070 assert(isa<AllocaInst>(cpyDest) && "Can only increase alloca alignment!");
1071 AllocaInst *DestAlloca = cast<AllocaInst>(cpyDest);
1072 DestAlloca->setAlignment(std::max(DestAlloca->getAlign(), srcAlign));
1073 }
1074
1075 if (NeedMoveGEP) {
1076 auto *GEP = dyn_cast<GetElementPtrInst>(cpyDest);
1077 GEP->moveBefore(C->getIterator());
1078 }
1079
1080 if (SkippedLifetimeStart) {
1081 SkippedLifetimeStart->moveBefore(C->getIterator());
1082 MSSAU->moveBefore(MSSA->getMemoryAccess(SkippedLifetimeStart),
1083 MSSA->getMemoryAccess(C));
1084 }
1085
1086 combineAAMetadata(C, cpyLoad);
1087 if (cpyLoad != cpyStore)
1088 combineAAMetadata(C, cpyStore);
1089
1090 ++NumCallSlot;
1091 return true;
1092}
1093
1094/// We've found that the (upward scanning) memory dependence of memcpy 'M' is
1095/// the memcpy 'MDep'. Try to simplify M to copy from MDep's input if we can.
1096bool MemCpyOptPass::processMemCpyMemCpyDependence(MemCpyInst *M,
1097 MemCpyInst *MDep,
1098 BatchAAResults &BAA) {
1099 // We can only optimize non-volatile memcpy's.
1100 if (MDep->isVolatile())
1101 return false;
1102
1103 // If dep instruction is reading from our current input, then it is a noop
1104 // transfer and substituting the input won't change this instruction. Just
1105 // ignore the input and let someone else zap MDep. This handles cases like:
1106 // memcpy(a <- a)
1107 // memcpy(b <- a)
1108 // This also avoids infinite loops.
1109 if (BAA.isMustAlias(MDep->getDest(), MDep->getSource()))
1110 return false;
1111
1112 int64_t MForwardOffset = 0;
1113 const DataLayout &DL = M->getDataLayout();
1114 // We can only transforms memcpy's where the dest of one is the source of the
1115 // other, or they have an offset in a range.
1116 if (M->getSource() != MDep->getDest()) {
1117 std::optional<int64_t> Offset =
1118 M->getSource()->getPointerOffsetFrom(MDep->getDest(), DL);
1119 if (!Offset || *Offset < 0)
1120 return false;
1121 MForwardOffset = *Offset;
1122 }
1123
1124 Value *CopyLength = M->getLength();
1125
1126 // The length of the memcpy's must be the same, or the preceding one must be
1127 // larger than the following one, or the contents of the overread must be
1128 // undefined bytes of a defined size.
1129 if (MForwardOffset != 0 || MDep->getLength() != CopyLength) {
1130 auto *MDepLen = dyn_cast<ConstantInt>(MDep->getLength());
1131 auto *MLen = dyn_cast<ConstantInt>(CopyLength);
1132 // This could be converted to a runtime test (%CopyLength =
1133 // min(max(0, MDepLen - MForwardOffset), MLen)), but it is
1134 // unclear if that is useful
1135 if (!MDepLen || !MLen)
1136 return false;
1137 if (MDepLen->getZExtValue() < MLen->getZExtValue() + MForwardOffset) {
1138 if (!overreadUndefContents(MSSA, M, MDep, BAA))
1139 return false;
1140 if (MDepLen->getZExtValue() <= (uint64_t)MForwardOffset)
1141 return false; // Should not reach here (there is obviously no aliasing
1142 // with MDep), so just bail in case it had incomplete info
1143 // somehow
1144 CopyLength = ConstantInt::get(CopyLength->getType(),
1145 MDepLen->getZExtValue() - MForwardOffset);
1146 }
1147 }
1148
1149 IRBuilder<> Builder(M);
1150 auto *CopySource = MDep->getSource();
1151 Instruction *NewCopySource = nullptr;
1152 llvm::scope_exit CleanupOnRet([&] {
1153 if (NewCopySource && NewCopySource->use_empty())
1154 // Safety: It's safe here because we will only allocate more instructions
1155 // after finishing all BatchAA queries, but we have to be careful if we
1156 // want to do something like this in another place. Then we'd probably
1157 // have to delay instruction removal until all transforms on an
1158 // instruction finished.
1159 eraseInstruction(NewCopySource);
1160 });
1161 MaybeAlign CopySourceAlign = MDep->getSourceAlign();
1162 auto MCopyLoc = MemoryLocation::getForSource(MDep);
1163 // Truncate the size of the MDep access to just the bytes read
1164 if (MDep->getLength() != CopyLength) {
1165 auto *ConstLength = cast<ConstantInt>(CopyLength);
1166 MCopyLoc = MCopyLoc.getWithNewSize(
1167 LocationSize::precise(ConstLength->getZExtValue()));
1168 }
1169
1170 // When the forwarding offset is greater than 0, we transform
1171 // memcpy(d1 <- s1)
1172 // memcpy(d2 <- d1+o)
1173 // to
1174 // memcpy(d2 <- s1+o)
1175 if (MForwardOffset > 0) {
1176 // The copy destination of `M` maybe can serve as the source of copying.
1177 std::optional<int64_t> MDestOffset =
1178 M->getRawDest()->getPointerOffsetFrom(MDep->getRawSource(), DL);
1179 if (MDestOffset == MForwardOffset)
1180 CopySource = M->getDest();
1181 else {
1182 CopySource = Builder.CreatePtrAddWithSignedOffset(
1183 CopySource, MForwardOffset, "", GEPNoWrapFlags::inBounds());
1184 NewCopySource = dyn_cast<Instruction>(CopySource);
1185 }
1186 // We need to update `MCopyLoc` if an offset exists.
1187 MCopyLoc = MCopyLoc.getWithNewPtr(CopySource);
1188 if (CopySourceAlign)
1189 CopySourceAlign = commonAlignment(*CopySourceAlign, MForwardOffset);
1190 }
1191
1192 // Verify that the copied-from memory doesn't change in between the two
1193 // transfers. For example, in:
1194 // memcpy(a <- b)
1195 // *b = 42;
1196 // memcpy(c <- a)
1197 // It would be invalid to transform the second memcpy into memcpy(c <- b).
1198 //
1199 // TODO: If the code between M and MDep is transparent to the destination "c",
1200 // then we could still perform the xform by moving M up to the first memcpy.
1201 if (writtenBetween(MSSA, BAA, MCopyLoc, MSSA->getMemoryAccess(MDep),
1202 MSSA->getMemoryAccess(M)))
1203 return false;
1204
1205 // No need to create `memcpy(a <- a)`.
1206 if (BAA.isMustAlias(M->getDest(), CopySource)) {
1207 // Remove the instruction we're replacing.
1209 ++NumMemCpyInstr;
1210 return true;
1211 }
1212
1213 // If the dest of the second might alias the source of the first, then the
1214 // source and dest might overlap. In addition, if the source of the first
1215 // points to constant memory, they won't overlap by definition. Otherwise, we
1216 // still want to eliminate the intermediate value, but we have to generate a
1217 // memmove instead of memcpy.
1218 bool UseMemMove = false;
1220 // Don't convert llvm.memcpy.inline into memmove because memmove can be
1221 // lowered as a call, and that is not allowed for llvm.memcpy.inline (and
1222 // there is no inline version of llvm.memmove)
1223 if (M->isForceInlined())
1224 return false;
1225 UseMemMove = true;
1226 }
1227
1228 // If all checks passed, then we can transform M.
1229 LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy->memcpy src:\n"
1230 << *MDep << '\n'
1231 << *M << '\n');
1232
1233 // TODO: Is this worth it if we're creating a less aligned memcpy? For
1234 // example we could be moving from movaps -> movq on x86.
1235 Instruction *NewM;
1236 if (UseMemMove)
1237 NewM = Builder.CreateMemMove(M->getDest(), M->getDestAlign(), CopySource,
1238 CopySourceAlign, CopyLength, M->isVolatile());
1239 else if (M->isForceInlined())
1240 // llvm.memcpy may be promoted to llvm.memcpy.inline, but the converse is
1241 // never allowed since that would allow the latter to be lowered as a call
1242 // to an external function.
1243 NewM = Builder.CreateMemCpyInline(M->getDest(), M->getDestAlign(),
1244 CopySource, CopySourceAlign, CopyLength,
1245 M->isVolatile());
1246 else
1247 NewM = Builder.CreateMemCpy(M->getDest(), M->getDestAlign(), CopySource,
1248 CopySourceAlign, CopyLength, M->isVolatile());
1249
1250 NewM->copyMetadata(*M, LLVMContext::MD_DIAssignID);
1251
1252 assert(isa<MemoryDef>(MSSA->getMemoryAccess(M)));
1253 auto *LastDef = cast<MemoryDef>(MSSA->getMemoryAccess(M));
1254 auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM, nullptr, LastDef);
1255 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
1256
1257 // Remove the instruction we're replacing.
1259 ++NumMemCpyInstr;
1260 return true;
1261}
1262
1263/// We've found that the (upward scanning) memory dependence of \p MemCpy is
1264/// \p MemSet. Try to simplify \p MemSet to only set the trailing bytes that
1265/// weren't copied over by \p MemCpy.
1266///
1267/// In other words, transform:
1268/// \code
1269/// memset(dst, c, dst_size);
1270/// ...
1271/// memcpy(dst, src, src_size);
1272/// \endcode
1273/// into:
1274/// \code
1275/// ...
1276/// memset(dst + src_size, c, dst_size <= src_size ? 0 : dst_size - src_size);
1277/// memcpy(dst, src, src_size);
1278/// \endcode
1279///
1280/// The memset is sunk to just before the memcpy to ensure that src_size is
1281/// present when emitting the simplified memset.
1282bool MemCpyOptPass::processMemSetMemCpyDependence(MemCpyInst *MemCpy,
1283 MemSetInst *MemSet,
1284 BatchAAResults &BAA) {
1285 // We can only transform memset/memcpy with the same destination.
1286 if (!BAA.isMustAlias(MemSet->getDest(), MemCpy->getDest()))
1287 return false;
1288
1289 if (MemSet->isVolatile())
1290 return false;
1291
1292 // Don't perform the transform if src_size may be zero. In that case, the
1293 // transform is essentially a complex no-op and may lead to an infinite
1294 // loop if BasicAA is smart enough to understand that dst and dst + src_size
1295 // are still MustAlias after the transform.
1296 Value *SrcSize = MemCpy->getLength();
1297 if (!isKnownNonZero(SrcSize,
1298 SimplifyQuery(MemCpy->getDataLayout(), DT, AC, MemCpy)))
1299 return false;
1300
1301 // Check that src and dst of the memcpy aren't the same. While memcpy
1302 // operands cannot partially overlap, exact equality is allowed.
1303 if (isModSet(BAA.getModRefInfo(MemCpy, MemoryLocation::getForSource(MemCpy))))
1304 return false;
1305
1306 // We know that dst up to src_size is not written. We now need to make sure
1307 // that dst up to dst_size is not accessed. (If we did not move the memset,
1308 // checking for reads would be sufficient.)
1310 MSSA->getMemoryAccess(MemSet),
1311 MSSA->getMemoryAccess(MemCpy)))
1312 return false;
1313
1314 // Use the same i8* dest as the memcpy, killing the memset dest if different.
1315 Value *Dest = MemCpy->getRawDest();
1316 Value *DestSize = MemSet->getLength();
1317
1318 if (mayBeVisibleThroughUnwinding(Dest, MemSet, MemCpy))
1319 return false;
1320
1321 // If the sizes are the same, simply drop the memset instead of generating
1322 // a replacement with zero size.
1323 if (DestSize == SrcSize) {
1324 eraseInstruction(MemSet);
1325 return true;
1326 }
1327
1328 // By default, create an unaligned memset.
1329 Align Alignment = Align(1);
1330 // If Dest is aligned, and SrcSize is constant, use the minimum alignment
1331 // of the sum.
1332 const Align DestAlign = std::max(MemSet->getDestAlign().valueOrOne(),
1333 MemCpy->getDestAlign().valueOrOne());
1334 if (DestAlign > 1)
1335 if (auto *SrcSizeC = dyn_cast<ConstantInt>(SrcSize))
1336 Alignment = commonAlignment(DestAlign, SrcSizeC->getZExtValue());
1337
1338 IRBuilder<> Builder(MemCpy);
1339
1340 // Preserve the debug location of the old memset for the code emitted here
1341 // related to the new memset. This is correct according to the rules in
1342 // https://llvm.org/docs/HowToUpdateDebugInfo.html about "when to preserve an
1343 // instruction location", given that we move the memset within the basic
1344 // block.
1345 assert(MemSet->getParent() == MemCpy->getParent() &&
1346 "Preserving debug location based on moving memset within BB.");
1347 Builder.SetCurrentDebugLocation(MemSet->getDebugLoc());
1348
1349 // Convert both sizes to the index size.
1350 Type *IdxTy = MemCpy->getDataLayout().getIndexType(Dest->getType());
1351 SrcSize = Builder.CreateZExtOrTrunc(SrcSize, IdxTy);
1352 DestSize = Builder.CreateZExtOrTrunc(DestSize, IdxTy);
1353
1354 Value *Ule = Builder.CreateICmpULE(DestSize, SrcSize);
1355 Value *SizeDiff = Builder.CreateSub(DestSize, SrcSize);
1356 Value *MemsetLen = Builder.CreateSelect(
1357 Ule, ConstantInt::getNullValue(DestSize->getType()), SizeDiff);
1358 // FIXME (#167968): we could explore estimating the branch_weights based on
1359 // value profiling data about the 2 sizes.
1360 if (auto *SI = dyn_cast<SelectInst>(MemsetLen))
1362 Instruction *NewMemSet =
1363 Builder.CreateMemSet(Builder.CreatePtrAdd(Dest, SrcSize),
1364 MemSet->getOperand(1), MemsetLen, Alignment);
1365
1366 assert(isa<MemoryDef>(MSSA->getMemoryAccess(MemCpy)) &&
1367 "MemCpy must be a MemoryDef");
1368 // The new memset is inserted before the memcpy, and it is known that the
1369 // memcpy's defining access is the memset about to be removed.
1370 auto *LastDef = cast<MemoryDef>(MSSA->getMemoryAccess(MemCpy));
1371 auto *NewAccess =
1372 MSSAU->createMemoryAccessBefore(NewMemSet, nullptr, LastDef);
1373 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
1374
1375 eraseInstruction(MemSet);
1376 return true;
1377}
1378
1379/// Determine whether the pointer V had only undefined content (due to Def),
1380/// either because it was freshly alloca'd or started its lifetime.
1382 MemoryDef *Def) {
1383 if (MSSA->isLiveOnEntryDef(Def))
1385
1386 if (auto *II = dyn_cast_or_null<IntrinsicInst>(Def->getMemoryInst()))
1387 if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1388 if (auto *Alloca = dyn_cast<AllocaInst>(getUnderlyingObject(V)))
1389 return II->getArgOperand(0) == Alloca;
1390
1391 return false;
1392}
1393
1394// If the memcpy is larger than the previous, but the memory was undef prior to
1395// that, we can just ignore the tail. Technically we're only interested in the
1396// bytes from 0..MemSrcOffset and MemSrcLength+MemSrcOffset..CopySize here, but
1397// as we can't easily represent this location (hasUndefContents uses mustAlias
1398// which cannot deal with offsets), we use the full 0..CopySize range.
1399static bool overreadUndefContents(MemorySSA *MSSA, MemCpyInst *MemCpy,
1400 MemIntrinsic *MemSrc, BatchAAResults &BAA) {
1401 MemoryLocation MemCpyLoc = MemoryLocation::getForSource(MemCpy);
1402 MemoryUseOrDef *MemSrcAccess = MSSA->getMemoryAccess(MemSrc);
1404 MemSrcAccess->getDefiningAccess(), MemCpyLoc, BAA);
1405 if (auto *MD = dyn_cast<MemoryDef>(Clobber))
1406 if (hasUndefContents(MSSA, BAA, MemCpy->getSource(), MD))
1407 return true;
1408 return false;
1409}
1410
1411/// Transform memcpy to memset when its source was just memset.
1412/// In other words, turn:
1413/// \code
1414/// memset(dst1, c, dst1_size);
1415/// memcpy(dst2, dst1, dst2_size);
1416/// \endcode
1417/// into:
1418/// \code
1419/// memset(dst1, c, dst1_size);
1420/// memset(dst2, c, dst2_size);
1421/// \endcode
1422bool MemCpyOptPass::performMemCpyToMemSetOptzn(MemCpyInst *MemCpy,
1423 MemSetInst *MemSet,
1424 BatchAAResults &BAA) {
1425 Value *MemSetSize = MemSet->getLength();
1426 Value *CopySize = MemCpy->getLength();
1427
1428 int64_t MOffset = 0;
1429 const DataLayout &DL = MemCpy->getDataLayout();
1430 // We can only transforms memcpy's where the dest of one is the source of the
1431 // other, or they have a known offset.
1432 if (MemCpy->getSource() != MemSet->getDest()) {
1433 std::optional<int64_t> Offset =
1434 MemCpy->getSource()->getPointerOffsetFrom(MemSet->getDest(), DL);
1435 if (!Offset)
1436 return false;
1437 // On positive offsets, the memcpy source is at a offset into the memset'd
1438 // region. On negative offsets, the copy starts at a offset prior to the
1439 // previously memset'd area, namely, we memcpy from a partially initialized
1440 // region.
1441 MOffset = *Offset;
1442 }
1443
1444 if (MOffset != 0 || MemSetSize != CopySize) {
1445 // Make sure the memcpy doesn't read any more than what the memset wrote,
1446 // other than undef. Likewise, the memcpy should not read from an area not
1447 // covered by the memset unless undef bytes. Don't worry about sizes larger
1448 // than i64.
1449 auto *CMemSetSize = dyn_cast<ConstantInt>(MemSetSize);
1450 auto *CCopySize = dyn_cast<ConstantInt>(CopySize);
1451 if (!CMemSetSize || !CCopySize || MOffset < 0 ||
1452 CCopySize->getZExtValue() + MOffset > CMemSetSize->getZExtValue()) {
1453 if (!overreadUndefContents(MSSA, MemCpy, MemSet, BAA))
1454 return false;
1455
1456 if (CMemSetSize && CCopySize) {
1457 uint64_t MemSetSizeVal = CMemSetSize->getZExtValue();
1458 uint64_t MemCpySizeVal = CCopySize->getZExtValue();
1459 uint64_t NewSize;
1460
1461 if (MOffset < 0) {
1462 // Offset from beginning of the initialized region.
1463 uint64_t Offset = -MOffset;
1464 NewSize = MemCpySizeVal <= Offset ? 0 : MemCpySizeVal - Offset;
1465 } else if (MOffset == 0) {
1466 NewSize = MemSetSizeVal;
1467 } else {
1468 NewSize =
1469 MemSetSizeVal <= (uint64_t)MOffset ? 0 : MemSetSizeVal - MOffset;
1470 }
1471 CopySize = ConstantInt::get(CopySize->getType(), NewSize);
1472 } else {
1473 if (MOffset < 0)
1474 return false;
1475 }
1476 }
1477 }
1478
1479 IRBuilder<> Builder(MemCpy);
1480 Value *DestPtr = MemCpy->getRawDest();
1481 MaybeAlign Align = MemCpy->getDestAlign();
1482 if (MOffset < 0) {
1483 DestPtr = Builder.CreatePtrAddWithSignedOffset(DestPtr, -MOffset);
1484 if (Align)
1485 Align = commonAlignment(*Align, -MOffset);
1486 }
1487
1488 Instruction *NewM =
1489 Builder.CreateMemSet(DestPtr, MemSet->getOperand(1), CopySize, Align);
1490 auto *LastDef = cast<MemoryDef>(MSSA->getMemoryAccess(MemCpy));
1491 auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM, nullptr, LastDef);
1492 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
1493
1494 return true;
1495}
1496
1497// Attempts to optimize the pattern whereby memory is copied from an alloca to
1498// another alloca, where the two allocas don't have conflicting mod/ref. If
1499// successful, the two allocas can be merged into one and the transfer can be
1500// deleted. This pattern is generated frequently in Rust, due to the ubiquity of
1501// move operations in that language.
1502//
1503// Once we determine that the optimization is safe to perform, we replace all
1504// uses of the destination alloca with the source alloca. We also "shrink wrap"
1505// the lifetime markers of the single merged alloca to before the first use
1506// and after the last use. Note that the "shrink wrapping" procedure is a safe
1507// transformation only because we restrict the scope of this optimization to
1508// allocas that aren't captured.
1509bool MemCpyOptPass::performStackMoveOptzn(Instruction *Load, Instruction *Store,
1510 Value *DestPtr, Value *SrcPtr,
1511 TypeSize Size, BatchAAResults &BAA) {
1512 LLVM_DEBUG(dbgs() << "Stack Move: Attempting to optimize:\n"
1513 << *Store << "\n");
1514
1515 AllocaInst *DestAlloca = dyn_cast<AllocaInst>(getUnderlyingObject(DestPtr));
1516 if (!DestAlloca)
1517 return false;
1518
1519 AllocaInst *SrcAlloca = dyn_cast<AllocaInst>(getUnderlyingObject(SrcPtr));
1520 if (!SrcAlloca)
1521 return false;
1522
1523 // Explicitly don't handle degenerate case of a partial copy within one
1524 // alloca. It would always fail the dominator check later anyways, and
1525 // possibly the modref checks also.
1526 if (SrcAlloca == DestAlloca)
1527 return false;
1528
1529 // Make sure the two allocas are in the same address space.
1530 if (SrcAlloca->getAddressSpace() != DestAlloca->getAddressSpace()) {
1531 LLVM_DEBUG(dbgs() << "Stack Move: Address space mismatch\n");
1532 return false;
1533 }
1534
1535 if (!SrcAlloca->isStaticAlloca() || !DestAlloca->isStaticAlloca())
1536 return false;
1537
1538 // Check that copy is full with static size.
1539 const DataLayout &DL = DestAlloca->getDataLayout();
1540
1541 auto DestOffset = DestPtr->getPointerOffsetFrom(DestAlloca, DL);
1542 if (!DestOffset)
1543 return false;
1544
1545 auto SrcOffset = SrcPtr->getPointerOffsetFrom(SrcAlloca, DL);
1546 if (!SrcOffset || *SrcOffset < *DestOffset || *SrcOffset < 0)
1547 return false;
1548 // Offset difference must preserve dest alloca's alignment.
1549 if ((*SrcOffset - *DestOffset) % DestAlloca->getAlign().value() != 0)
1550 return false;
1551 std::optional<TypeSize> SrcSize = SrcAlloca->getAllocationSize(DL);
1552 std::optional<TypeSize> DestSize = DestAlloca->getAllocationSize(DL);
1553 if (!SrcSize || !DestSize)
1554 return false;
1555 if (*SrcSize != *DestSize)
1556 if (!SrcSize->isFixed() || !DestSize->isFixed())
1557 return false;
1558 // Check that copy covers entirety of dest alloca.
1559 if (Size != *DestSize || *DestOffset != 0) {
1560 LLVM_DEBUG(dbgs() << "Stack Move: Destination alloca size mismatch\n");
1561 return false;
1562 }
1563
1564 // Make sure that the copied offset is actually part of the alloca. There
1565 // might be an out-of-bounds copy in dead code.
1566 if (Size.isFixed()) {
1567 if (*SrcOffset + Size > *SrcSize)
1568 return false;
1569 } else if (*SrcOffset != 0) {
1570 // Cannot compute an in-bounds offset on scalable sizes.
1571 return false;
1572 }
1573
1574 // Check if it will be legal to combine allocas without breaking dominator.
1575 bool MoveSrc = !DT->dominates(SrcAlloca, DestAlloca);
1576 if (MoveSrc) {
1577 if (!DT->dominates(DestAlloca, SrcAlloca))
1578 return false;
1579 }
1580
1581 // Check that src and dest are never captured, unescaped allocas. Also
1582 // find the nearest common dominator and postdominator for all users in
1583 // order to shrink wrap the lifetimes, and instructions with noalias metadata
1584 // to remove them.
1585
1586 SmallVector<Instruction *, 4> LifetimeMarkers;
1587 SmallPtrSet<Instruction *, 4> AAMetadataInstrs;
1588
1589 auto CaptureTrackingWithModRef =
1590 [&](Instruction *AI, function_ref<bool(Instruction *)> ModRefCallback,
1591 bool &AddressCaptured) -> bool {
1592 SmallVector<Instruction *, 8> Worklist;
1593 Worklist.push_back(AI);
1594 unsigned MaxUsesToExplore = getDefaultMaxUsesToExploreForCaptureTracking();
1595 Worklist.reserve(MaxUsesToExplore);
1596 SmallPtrSet<const Use *, 20> Visited;
1597 while (!Worklist.empty()) {
1598 Instruction *I = Worklist.pop_back_val();
1599 for (const Use &U : I->uses()) {
1600 auto *UI = cast<Instruction>(U.getUser());
1601
1602 if (Visited.size() >= MaxUsesToExplore) {
1603 LLVM_DEBUG(
1604 dbgs()
1605 << "Stack Move: Exceeded max uses to see ModRef, bailing\n");
1606 return false;
1607 }
1608 if (!Visited.insert(&U).second)
1609 continue;
1610 UseCaptureInfo CI = DetermineUseCaptureKind(U, AI);
1612 return false;
1613 AddressCaptured |= capturesAddress(CI.UseCC);
1614
1615 if (UI->mayReadOrWriteMemory()) {
1616 if (UI->isLifetimeStartOrEnd()) {
1617 // We note the locations of these intrinsic calls so that we can
1618 // delete them later if the optimization succeeds, this is safe
1619 // since both llvm.lifetime.start and llvm.lifetime.end intrinsics
1620 // practically fill all the bytes of the alloca with an undefined
1621 // value, although conceptually marked as alive/dead.
1622 LifetimeMarkers.push_back(UI);
1623 continue;
1624 }
1625 AAMetadataInstrs.insert(UI);
1626
1627 if (!ModRefCallback(UI))
1628 return false;
1629 }
1630
1631 if (capturesAnything(CI.ResultCC)) {
1632 Worklist.push_back(UI);
1633 continue;
1634 }
1635 }
1636 }
1637 return true;
1638 };
1639
1640 // Check that dest alloca has no Mod/Ref, from the alloca to the Store. And
1641 // collect modref inst for the reachability check.
1642 ModRefInfo DestModRef = ModRefInfo::NoModRef;
1643 MemoryLocation DestLoc(DestAlloca, LocationSize::precise(*DestSize));
1644 SmallVector<BasicBlock *, 8> ReachabilityWorklist;
1645 auto DestModRefCallback = [&](Instruction *UI) -> bool {
1646 // We don't care about the store itself.
1647 if (UI == Store)
1648 return true;
1649 ModRefInfo Res = BAA.getModRefInfo(UI, DestLoc);
1650 DestModRef |= Res;
1651 if (isModOrRefSet(Res)) {
1652 // Instructions reachability checks.
1653 // FIXME: adding the Instruction version isPotentiallyReachableFromMany on
1654 // lib/Analysis/CFG.cpp (currently only for BasicBlocks) might be helpful.
1655 if (UI->getParent() == Store->getParent()) {
1656 // The same block case is special because it's the only time we're
1657 // looking within a single block to see which instruction comes first.
1658 // Once we start looking at multiple blocks, the first instruction of
1659 // the block is reachable, so we only need to determine reachability
1660 // between whole blocks.
1661 BasicBlock *BB = UI->getParent();
1662
1663 // If A comes before B, then B is definitively reachable from A.
1664 if (UI->comesBefore(Store))
1665 return false;
1666
1667 // If the user's parent block is entry, no predecessor exists.
1668 if (BB->isEntryBlock())
1669 return true;
1670
1671 // Otherwise, continue doing the normal per-BB CFG walk.
1672 ReachabilityWorklist.append(succ_begin(BB), succ_end(BB));
1673 } else {
1674 ReachabilityWorklist.push_back(UI->getParent());
1675 }
1676 }
1677 return true;
1678 };
1679
1680 bool DestAddressCaptured = false;
1681 if (!CaptureTrackingWithModRef(DestAlloca, DestModRefCallback,
1682 DestAddressCaptured))
1683 return false;
1684 // Bailout if Dest may have any ModRef before Store.
1685 if (!ReachabilityWorklist.empty() &&
1686 isPotentiallyReachableFromMany(ReachabilityWorklist, Store->getParent(),
1687 nullptr, DT, nullptr))
1688 return false;
1689
1690 // Check that, from after the Load to the end of the BB,
1691 // - if the dest has any Mod, src has no Ref, and
1692 // - if the dest has any Ref, src has no Mod except full-sized lifetimes
1693 // Where:
1694 // - src is defined as the memory from max(SrcAlloca, SrcPtr minus
1695 // dest_offset) to min(dest_size, SrcSize minus SrcOffset)
1696 // - dest_offset and dest_size could be computed by DestModRefCallback
1697 // to be the bounds of the first and last mod region, and which is at
1698 // least as large as DestOffset to DestSize, and at most as large as
1699 // SrcAlloca to SrcSize.
1700 // - Currently DestOffset==0 and DestSize==Size, so this math is simplified.
1701 MemoryLocation SrcLoc(SrcPtr, LocationSize::precise(Size));
1702
1703 auto SrcModRefCallback = [&](Instruction *UI) -> bool {
1704 // Any ModRef post-dominated by Load doesn't matter, also Load and Store
1705 // themselves can be ignored.
1706 if (PDT->dominates(Load, UI) || UI == Load || UI == Store)
1707 return true;
1708 ModRefInfo Res = BAA.getModRefInfo(UI, SrcLoc);
1709 if ((isModSet(DestModRef) && isRefSet(Res)) ||
1710 (isRefSet(DestModRef) && isModSet(Res)))
1711 return false;
1712
1713 return true;
1714 };
1715
1716 bool SrcAddressCaptured = false;
1717 if (!CaptureTrackingWithModRef(SrcAlloca, SrcModRefCallback,
1718 SrcAddressCaptured))
1719 return false;
1720
1721 // If both the source and destination address are captured, the fact that they
1722 // are no longer two separate allocations may be observed.
1723 if (DestAddressCaptured && SrcAddressCaptured)
1724 return false;
1725
1726 // We can now do the transformation. First move the Src if it was after Dest.
1727 if (MoveSrc)
1728 SrcAlloca->moveBefore(DestAlloca->getIterator());
1729
1730 // Align the allocas appropriately.
1731 SrcAlloca->setAlignment(
1732 std::max(SrcAlloca->getAlign(), DestAlloca->getAlign()));
1733
1734 // Size the allocas appropriately.
1735 if (*SrcSize != *DestSize) {
1736 // Only possible if both sizes are fixed (due to earlier check)
1737 // Set Src to the type and array size of Dest if Dest was larger
1738 if (DestSize->getFixedValue() > SrcSize->getFixedValue()) {
1739 SrcAlloca->setAllocatedType(DestAlloca->getAllocatedType());
1740 SrcAlloca->setOperand(0, DestAlloca->getArraySize());
1741 }
1742 }
1743
1744 // Merge the two allocas.
1745 Value *NewDestPtr = SrcAlloca;
1746 if (*SrcOffset != *DestOffset) {
1747 IRBuilder<> Builder(DestAlloca);
1748 NewDestPtr = Builder.CreatePtrAddWithSignedOffset(
1749 SrcAlloca, *SrcOffset - *DestOffset, "", GEPNoWrapFlags::inBounds());
1750 }
1751 DestAlloca->replaceAllUsesWith(NewDestPtr);
1752 eraseInstruction(DestAlloca);
1753
1754 // Drop metadata on the source alloca.
1755 SrcAlloca->dropUnknownNonDebugMetadata();
1756
1757 // TODO: Reconstruct merged lifetime markers.
1758 // Remove all other lifetime markers. if the original lifetime intrinsics
1759 // exists.
1760 if (!LifetimeMarkers.empty()) {
1761 for (Instruction *I : LifetimeMarkers)
1763 }
1764
1765 // As this transformation can cause memory accesses that didn't previously
1766 // alias to begin to alias one another, we remove !alias.scope, !noalias,
1767 // !tbaa and !tbaa_struct metadata from any uses of either alloca.
1768 // This is conservative, but more precision doesn't seem worthwhile
1769 // right now.
1770 for (Instruction *I : AAMetadataInstrs) {
1771 I->setMetadata(LLVMContext::MD_alias_scope, nullptr);
1772 I->setMetadata(LLVMContext::MD_noalias, nullptr);
1773 I->setMetadata(LLVMContext::MD_tbaa, nullptr);
1774 I->setMetadata(LLVMContext::MD_tbaa_struct, nullptr);
1775 }
1776
1777 LLVM_DEBUG(dbgs() << "Stack Move: Performed stack-move optimization\n");
1778 NumStackMove++;
1779 return true;
1780}
1781
1782static bool isZeroSize(Value *Size) {
1783 if (auto *I = dyn_cast<Instruction>(Size))
1784 if (auto *Res = simplifyInstruction(I, I->getDataLayout()))
1785 Size = Res;
1786 // Treat undef/poison size like zero.
1787 if (auto *C = dyn_cast<Constant>(Size))
1788 return isa<UndefValue>(C) || C->isNullValue();
1789 return false;
1790}
1791
1792/// Perform simplification of memcpy's. If we have memcpy A
1793/// which copies X to Y, and memcpy B which copies Y to Z, then we can rewrite
1794/// B to be a memcpy from X to Z (or potentially a memmove, depending on
1795/// circumstances). This allows later passes to remove the first memcpy
1796/// altogether.
1797bool MemCpyOptPass::processMemCpy(MemCpyInst *M, BasicBlock::iterator &BBI) {
1798 // We can only optimize non-volatile memcpy's.
1799 if (M->isVolatile())
1800 return false;
1801
1802 // If the source and destination of the memcpy are the same, then zap it.
1803 if (M->getSource() == M->getDest()) {
1804 ++BBI;
1806 return true;
1807 }
1808
1809 // If the size is zero, remove the memcpy.
1810 if (isZeroSize(M->getLength())) {
1811 ++BBI;
1813 return true;
1814 }
1815
1816 MemoryUseOrDef *MA = MSSA->getMemoryAccess(M);
1817 if (!MA)
1818 // Degenerate case: memcpy marked as not accessing memory.
1819 return false;
1820
1821 // If copying from a constant, try to turn the memcpy into a memset.
1822 if (auto *GV = dyn_cast<GlobalVariable>(getUnderlyingObject(M->getSource())))
1823 if (GV->isConstant() && GV->hasDefinitiveInitializer())
1824 if (Value *ByteVal = isBytewiseValue(GV->getInitializer(),
1825 M->getDataLayout())) {
1826 IRBuilder<> Builder(M);
1827 Instruction *NewM = Builder.CreateMemSet(
1828 M->getRawDest(), ByteVal, M->getLength(), M->getDestAlign(), false);
1829 auto *LastDef = cast<MemoryDef>(MA);
1830 auto *NewAccess =
1831 MSSAU->createMemoryAccessAfter(NewM, nullptr, LastDef);
1832 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
1833
1835 ++NumCpyToSet;
1836 return true;
1837 }
1838
1839 BatchAAResults BAA(*AA, EEA);
1840 // FIXME: Not using getClobberingMemoryAccess() here due to PR54682.
1841 MemoryAccess *AnyClobber = MA->getDefiningAccess();
1842 MemoryLocation DestLoc = MemoryLocation::getForDest(M);
1843 const MemoryAccess *DestClobber =
1844 MSSA->getWalker()->getClobberingMemoryAccess(AnyClobber, DestLoc, BAA);
1845
1846 // Try to turn a partially redundant memset + memcpy into
1847 // smaller memset + memcpy. We don't need the memcpy size for this.
1848 // The memcpy must post-dom the memset, so limit this to the same basic
1849 // block. A non-local generalization is likely not worthwhile.
1850 if (auto *MD = dyn_cast<MemoryDef>(DestClobber))
1851 if (auto *MDep = dyn_cast_or_null<MemSetInst>(MD->getMemoryInst()))
1852 if (DestClobber->getBlock() == M->getParent())
1853 if (processMemSetMemCpyDependence(M, MDep, BAA))
1854 return true;
1855
1856 MemoryAccess *SrcClobber = MSSA->getWalker()->getClobberingMemoryAccess(
1857 AnyClobber, MemoryLocation::getForSource(M), BAA);
1858
1859 // There are five possible optimizations we can do for memcpy:
1860 // a) memcpy-memcpy xform which exposes redundance for DSE.
1861 // b) call-memcpy xform for return slot optimization.
1862 // c) memcpy from freshly alloca'd space or space that has just started
1863 // its lifetime copies undefined data, and we can therefore eliminate
1864 // the memcpy in favor of the data that was already at the destination.
1865 // d) memcpy from a just-memset'd source can be turned into memset.
1866 // e) elimination of memcpy via stack-move optimization.
1867 if (auto *MD = dyn_cast<MemoryDef>(SrcClobber)) {
1868 if (Instruction *MI = MD->getMemoryInst()) {
1869 if (auto *CopySize = dyn_cast<ConstantInt>(M->getLength())) {
1870 if (auto *C = dyn_cast<CallInst>(MI)) {
1871 if (performCallSlotOptzn(M, M, M->getDest(), M->getSource(),
1872 TypeSize::getFixed(CopySize->getZExtValue()),
1873 M->getDestAlign().valueOrOne(), BAA,
1874 [C]() -> CallInst * { return C; })) {
1875 LLVM_DEBUG(dbgs() << "Performed call slot optimization:\n"
1876 << " call: " << *C << "\n"
1877 << " memcpy: " << *M << "\n");
1879 ++NumMemCpyInstr;
1880 return true;
1881 }
1882 }
1883 }
1884 if (auto *MDep = dyn_cast<MemCpyInst>(MI))
1885 if (processMemCpyMemCpyDependence(M, MDep, BAA))
1886 return true;
1887 if (auto *MDep = dyn_cast<MemSetInst>(MI)) {
1888 if (performMemCpyToMemSetOptzn(M, MDep, BAA)) {
1889 LLVM_DEBUG(dbgs() << "Converted memcpy to memset\n");
1891 ++NumCpyToSet;
1892 return true;
1893 }
1894 }
1895 }
1896
1897 if (hasUndefContents(MSSA, BAA, M->getSource(), MD)) {
1898 LLVM_DEBUG(dbgs() << "Removed memcpy from undef\n");
1900 ++NumMemCpyInstr;
1901 return true;
1902 }
1903 }
1904
1905 // If the transfer is from a stack slot to a stack slot, then we may be able
1906 // to perform the stack-move optimization. See the comments in
1907 // performStackMoveOptzn() for more details.
1908 ConstantInt *Len = dyn_cast<ConstantInt>(M->getLength());
1909 if (Len == nullptr)
1910 return false;
1911 if (performStackMoveOptzn(M, M, M->getDest(), M->getSource(),
1912 TypeSize::getFixed(Len->getZExtValue()), BAA)) {
1913 // Avoid invalidating the iterator.
1914 BBI = M->getNextNode()->getIterator();
1916 ++NumMemCpyInstr;
1917 return true;
1918 }
1919
1920 return false;
1921}
1922
1923/// Memmove calls with overlapping src/dest buffers that come after a memset may
1924/// be removed.
1925bool MemCpyOptPass::isMemMoveMemSetDependency(MemMoveInst *M) {
1926 const auto &DL = M->getDataLayout();
1927 MemoryUseOrDef *MemMoveAccess = MSSA->getMemoryAccess(M);
1928 if (!MemMoveAccess)
1929 return false;
1930
1931 // The memmove is of form memmove(x, x + A, B).
1932 MemoryLocation SourceLoc = MemoryLocation::getForSource(M);
1933 auto *MemMoveSourceOp = M->getSource();
1934 auto *Source = dyn_cast<GEPOperator>(MemMoveSourceOp);
1935 if (!Source)
1936 return false;
1937
1938 APInt Offset(DL.getIndexTypeSizeInBits(Source->getType()), 0);
1939 LocationSize MemMoveLocSize = SourceLoc.Size;
1940 if (Source->getPointerOperand() != M->getDest() ||
1941 !MemMoveLocSize.hasValue() ||
1942 !Source->accumulateConstantOffset(DL, Offset) || Offset.isNegative()) {
1943 return false;
1944 }
1945
1946 uint64_t MemMoveSize = MemMoveLocSize.getValue();
1947 LocationSize TotalSize =
1948 LocationSize::precise(Offset.getZExtValue() + MemMoveSize);
1949 MemoryLocation CombinedLoc(M->getDest(), TotalSize);
1950
1951 // The first dominating clobbering MemoryAccess for the combined location
1952 // needs to be a memset.
1953 BatchAAResults BAA(*AA);
1954 MemoryAccess *FirstDef = MemMoveAccess->getDefiningAccess();
1955 auto *DestClobber = dyn_cast<MemoryDef>(
1956 MSSA->getWalker()->getClobberingMemoryAccess(FirstDef, CombinedLoc, BAA));
1957 if (!DestClobber)
1958 return false;
1959
1960 auto *MS = dyn_cast_or_null<MemSetInst>(DestClobber->getMemoryInst());
1961 if (!MS)
1962 return false;
1963
1964 // Memset length must be sufficiently large.
1965 auto *MemSetLength = dyn_cast<ConstantInt>(MS->getLength());
1966 if (!MemSetLength ||
1967 MemSetLength->getZExtValue() < Offset.getZExtValue() + MemMoveSize)
1968 return false;
1969
1970 // The destination buffer must have been memset'd.
1971 if (!BAA.isMustAlias(MS->getDest(), M->getDest()))
1972 return false;
1973
1974 return true;
1975}
1976
1977/// Transforms memmove calls to memcpy calls when the src/dst are guaranteed
1978/// not to alias.
1979bool MemCpyOptPass::processMemMove(MemMoveInst *M, BasicBlock::iterator &BBI) {
1980 // See if the source could be modified by this memmove potentially.
1981 if (isModSet(AA->getModRefInfo(M, MemoryLocation::getForSource(M)))) {
1982 // On the off-chance the memmove clobbers src with previously memset'd
1983 // bytes, the memmove may be redundant.
1984 if (!M->isVolatile() && isMemMoveMemSetDependency(M)) {
1985 LLVM_DEBUG(dbgs() << "Removed redundant memmove.\n");
1986 ++BBI;
1988 ++NumMemMoveInstr;
1989 return true;
1990 }
1991 return false;
1992 }
1993
1994 LLVM_DEBUG(dbgs() << "MemCpyOptPass: Optimizing memmove -> memcpy: " << *M
1995 << "\n");
1996
1997 // If not, then we know we can transform this.
1998 Type *ArgTys[3] = {M->getRawDest()->getType(), M->getRawSource()->getType(),
1999 M->getLength()->getType()};
2000 M->setCalledFunction(Intrinsic::getOrInsertDeclaration(
2001 M->getModule(), Intrinsic::memcpy, ArgTys));
2002
2003 // For MemorySSA nothing really changes (except that memcpy may imply stricter
2004 // aliasing guarantees).
2005
2006 ++NumMoveToCpy;
2007 return true;
2008}
2009
2010/// This is called on every byval argument in call sites.
2011bool MemCpyOptPass::processByValArgument(CallBase &CB, unsigned ArgNo) {
2012 const DataLayout &DL = CB.getDataLayout();
2013 // Find out what feeds this byval argument.
2014 Value *ByValArg = CB.getArgOperand(ArgNo);
2015 Type *ByValTy = CB.getParamByValType(ArgNo);
2016 TypeSize ByValSize = DL.getTypeAllocSize(ByValTy);
2017 MemoryLocation Loc(ByValArg, LocationSize::precise(ByValSize));
2018 MemoryUseOrDef *CallAccess = MSSA->getMemoryAccess(&CB);
2019 if (!CallAccess)
2020 return false;
2021 MemCpyInst *MDep = nullptr;
2022 BatchAAResults BAA(*AA, EEA);
2023 MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(
2024 CallAccess->getDefiningAccess(), Loc, BAA);
2025 if (auto *MD = dyn_cast<MemoryDef>(Clobber))
2026 MDep = dyn_cast_or_null<MemCpyInst>(MD->getMemoryInst());
2027
2028 // If the byval argument isn't fed by a memcpy, ignore it. If it is fed by
2029 // a memcpy, see if we can byval from the source of the memcpy instead of the
2030 // result.
2031 if (!MDep || MDep->isVolatile() ||
2032 ByValArg->stripPointerCasts() != MDep->getDest())
2033 return false;
2034
2035 // The length of the memcpy must be larger or equal to the size of the byval.
2036 auto *C1 = dyn_cast<ConstantInt>(MDep->getLength());
2037 if (!C1 || !TypeSize::isKnownGE(
2038 TypeSize::getFixed(C1->getValue().getZExtValue()), ByValSize))
2039 return false;
2040
2041 // Get the alignment of the byval. If the call doesn't specify the alignment,
2042 // then it is some target specific value that we can't know.
2043 MaybeAlign ByValAlign = CB.getParamAlign(ArgNo);
2044 if (!ByValAlign)
2045 return false;
2046
2047 // If it is greater than the memcpy, then we check to see if we can force the
2048 // source of the memcpy to the alignment we need. If we fail, we bail out.
2049 MaybeAlign MemDepAlign = MDep->getSourceAlign();
2050 if ((!MemDepAlign || *MemDepAlign < *ByValAlign) &&
2051 getOrEnforceKnownAlignment(MDep->getSource(), ByValAlign, DL, &CB, AC,
2052 DT) < *ByValAlign)
2053 return false;
2054
2055 // The type of the memcpy source must match the byval argument
2056 if (MDep->getSource()->getType() != ByValArg->getType())
2057 return false;
2058
2059 // Verify that the copied-from memory doesn't change in between the memcpy and
2060 // the byval call.
2061 // memcpy(a <- b)
2062 // *b = 42;
2063 // foo(*a)
2064 // It would be invalid to transform the second memcpy into foo(*b).
2065 if (writtenBetween(MSSA, BAA, MemoryLocation::getForSource(MDep),
2066 MSSA->getMemoryAccess(MDep), CallAccess))
2067 return false;
2068
2069 LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n"
2070 << " " << *MDep << "\n"
2071 << " " << CB << "\n");
2072
2073 // Otherwise we're good! Update the byval argument.
2074 combineAAMetadata(&CB, MDep);
2075 CB.setArgOperand(ArgNo, MDep->getSource());
2076 ++NumMemCpyInstr;
2077 return true;
2078}
2079
2080/// This is called on memcpy dest pointer arguments attributed as immutable
2081/// during call. Try to use memcpy source directly if all of the following
2082/// conditions are satisfied.
2083/// 1. The memcpy dst is neither modified during the call nor captured by the
2084/// call.
2085/// 2. The memcpy dst is an alloca with known alignment & size.
2086/// 2-1. The memcpy length == the alloca size which ensures that the new
2087/// pointer is dereferenceable for the required range
2088/// 2-2. The src pointer has alignment >= the alloca alignment or can be
2089/// enforced so.
2090/// 3. The memcpy dst and src is not modified between the memcpy and the call.
2091/// (if MSSA clobber check is safe.)
2092/// 4. The memcpy src is not modified during the call. (ModRef check shows no
2093/// Mod.)
2094bool MemCpyOptPass::processImmutArgument(CallBase &CB, unsigned ArgNo) {
2095 BatchAAResults BAA(*AA, EEA);
2096 Value *ImmutArg = CB.getArgOperand(ArgNo);
2097
2098 // 1. Ensure passed argument is immutable during call.
2099 if (!CB.doesNotCapture(ArgNo))
2100 return false;
2101
2102 // We know that the argument is readonly at this point, but the function
2103 // might still modify the same memory through a different pointer. Exclude
2104 // this either via noalias, or alias analysis.
2105 if (!CB.paramHasAttr(ArgNo, Attribute::NoAlias) &&
2106 isModSet(
2108 return false;
2109
2110 const DataLayout &DL = CB.getDataLayout();
2111
2112 // 2. Check that arg is alloca
2113 // TODO: Even if the arg gets back to branches, we can remove memcpy if all
2114 // the alloca alignments can be enforced to source alignment.
2115 auto *AI = dyn_cast<AllocaInst>(ImmutArg->stripPointerCasts());
2116 if (!AI)
2117 return false;
2118
2119 std::optional<TypeSize> AllocaSize = AI->getAllocationSize(DL);
2120 // Can't handle unknown size alloca.
2121 // (e.g. Variable Length Array, Scalable Vector)
2122 if (!AllocaSize || AllocaSize->isScalable())
2123 return false;
2124 MemoryLocation Loc(ImmutArg, LocationSize::precise(*AllocaSize));
2125 MemoryUseOrDef *CallAccess = MSSA->getMemoryAccess(&CB);
2126 if (!CallAccess)
2127 return false;
2128
2129 MemCpyInst *MDep = nullptr;
2130 MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(
2131 CallAccess->getDefiningAccess(), Loc, BAA);
2132 if (auto *MD = dyn_cast<MemoryDef>(Clobber))
2133 MDep = dyn_cast_or_null<MemCpyInst>(MD->getMemoryInst());
2134
2135 // If the immut argument isn't fed by a memcpy, ignore it. If it is fed by
2136 // a memcpy, check that the arg equals the memcpy dest.
2137 if (!MDep || MDep->isVolatile() || AI != MDep->getDest())
2138 return false;
2139
2140 // The type of the memcpy source must match the immut argument
2141 if (MDep->getSource()->getType() != ImmutArg->getType())
2142 return false;
2143
2144 // 2-1. The length of the memcpy must be equal to the size of the alloca.
2145 auto *MDepLen = dyn_cast<ConstantInt>(MDep->getLength());
2146 if (!MDepLen || AllocaSize != MDepLen->getValue())
2147 return false;
2148
2149 // 2-2. the memcpy source align must be larger than or equal the alloca's
2150 // align. If not so, we check to see if we can force the source of the memcpy
2151 // to the alignment we need. If we fail, we bail out.
2152 Align MemDepAlign = MDep->getSourceAlign().valueOrOne();
2153 Align AllocaAlign = AI->getAlign();
2154 if (MemDepAlign < AllocaAlign &&
2155 getOrEnforceKnownAlignment(MDep->getSource(), AllocaAlign, DL, &CB, AC,
2156 DT) < AllocaAlign)
2157 return false;
2158
2159 // 3. Verify that the source doesn't change in between the memcpy and
2160 // the call.
2161 // memcpy(a <- b)
2162 // *b = 42;
2163 // foo(*a)
2164 // It would be invalid to transform the second memcpy into foo(*b).
2165 if (writtenBetween(MSSA, BAA, MemoryLocation::getForSource(MDep),
2166 MSSA->getMemoryAccess(MDep), CallAccess))
2167 return false;
2168
2169 // 4. The memcpy src must not be modified during the call.
2171 return false;
2172
2173 LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy to Immut src:\n"
2174 << " " << *MDep << "\n"
2175 << " " << CB << "\n");
2176
2177 // Otherwise we're good! Update the immut argument.
2178 combineAAMetadata(&CB, MDep);
2179 CB.setArgOperand(ArgNo, MDep->getSource());
2180 ++NumMemCpyInstr;
2181 return true;
2182}
2183
2184/// Executes one iteration of MemCpyOptPass.
2185bool MemCpyOptPass::iterateOnFunction(Function &F) {
2186 bool MadeChange = false;
2187
2188 // Walk all instruction in the function.
2189 for (BasicBlock &BB : F) {
2190 // Skip unreachable blocks. For example processStore assumes that an
2191 // instruction in a BB can't be dominated by a later instruction in the
2192 // same BB (which is a scenario that can happen for an unreachable BB that
2193 // has itself as a predecessor).
2194 if (!DT->isReachableFromEntry(&BB))
2195 continue;
2196
2197 for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) {
2198 // Avoid invalidating the iterator.
2199 Instruction *I = &*BI++;
2200
2201 bool RepeatInstruction = false;
2202
2203 if (auto *SI = dyn_cast<StoreInst>(I))
2204 MadeChange |= processStore(SI, BI);
2205 else if (auto *M = dyn_cast<MemSetInst>(I))
2206 RepeatInstruction = processMemSet(M, BI);
2207 else if (auto *M = dyn_cast<MemCpyInst>(I))
2208 RepeatInstruction = processMemCpy(M, BI);
2209 else if (auto *M = dyn_cast<MemMoveInst>(I))
2210 RepeatInstruction = processMemMove(M, BI);
2211 else if (auto *CB = dyn_cast<CallBase>(I)) {
2212 for (unsigned i = 0, e = CB->arg_size(); i != e; ++i) {
2213 if (CB->isByValArgument(i))
2214 MadeChange |= processByValArgument(*CB, i);
2215 else if (CB->onlyReadsMemory(i))
2216 MadeChange |= processImmutArgument(*CB, i);
2217 }
2218 }
2219
2220 // Reprocess the instruction if desired.
2221 if (RepeatInstruction) {
2222 if (BI != BB.begin())
2223 --BI;
2224 MadeChange = true;
2225 }
2226 }
2227 }
2228
2229 return MadeChange;
2230}
2231
2233 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
2234 auto *AA = &AM.getResult<AAManager>(F);
2235 auto *AC = &AM.getResult<AssumptionAnalysis>(F);
2236 auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
2237 auto *PDT = &AM.getResult<PostDominatorTreeAnalysis>(F);
2238 auto *MSSA = &AM.getResult<MemorySSAAnalysis>(F);
2239
2240 bool MadeChange = runImpl(F, &TLI, AA, AC, DT, PDT, &MSSA->getMSSA());
2241 if (!MadeChange)
2242 return PreservedAnalyses::all();
2243
2247 return PA;
2248}
2249
2250bool MemCpyOptPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
2251 AliasAnalysis *AA_, AssumptionCache *AC_,
2252 DominatorTree *DT_, PostDominatorTree *PDT_,
2253 MemorySSA *MSSA_) {
2254 bool MadeChange = false;
2255 TLI = TLI_;
2256 AA = AA_;
2257 AC = AC_;
2258 DT = DT_;
2259 PDT = PDT_;
2260 MSSA = MSSA_;
2261 MemorySSAUpdater MSSAU_(MSSA_);
2262 MSSAU = &MSSAU_;
2263 EarliestEscapeAnalysis EEA_(*DT);
2264 EEA = &EEA_;
2265
2266 while (true) {
2267 if (!iterateOnFunction(F))
2268 break;
2269 MadeChange = true;
2270 }
2271
2272 if (VerifyMemorySSA)
2273 MSSA_->verifyMemorySSA();
2274
2275 return MadeChange;
2276}
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
uint64_t uint64_t
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static bool runImpl(MachineFunction &MF)
Definition CFIFixup.cpp:304
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines the DenseSet and SmallDenseSet classes.
#define DEBUG_TYPE
This is the interface for a simple mod/ref and alias analysis over globals.
Hexagon Common GEP
IRTranslator LLVM IR MI
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
static void eraseInstruction(Instruction &I, const LICMDependencies &Deps)
Definition LICM.cpp:1173
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
static bool mayBeVisibleThroughUnwinding(Value *V, Instruction *Start, Instruction *End)
static bool isZeroSize(Value *Size)
static bool hasUndefContents(MemorySSA *MSSA, BatchAAResults &AA, Value *V, MemoryDef *Def)
Determine whether the pointer V had only undefined content (due to Def), either because it was freshl...
static bool accessedBetween(BatchAAResults &AA, MemoryLocation Loc, const MemoryUseOrDef *Start, const MemoryUseOrDef *End, Instruction **SkippedLifetimeStart=nullptr)
static bool overreadUndefContents(MemorySSA *MSSA, MemCpyInst *MemCpy, MemIntrinsic *MemSrc, BatchAAResults &BAA)
static bool writtenBetween(MemorySSA *MSSA, BatchAAResults &AA, MemoryLocation Loc, const MemoryUseOrDef *Start, const MemoryUseOrDef *End)
This file provides utility analysis objects describing memory locations.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
static void addRange(SmallVectorImpl< ConstantInt * > &EndPoints, ConstantInt *Low, ConstantInt *High)
#define T
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
#define P(N)
if(PassOpts->AAPipeline)
This file contains the declarations for profiling metadata utility functions.
int64_t C1
This file contains some templates that are useful if you are working with the STL at all.
This file defines the scope_exit class, which executes user-defined cleanup logic at scope exit.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
A manager for alias analyses.
LLVM_ABI bool isStaticAlloca() const
Return true if this alloca is in the entry block of the function and is a constant size.
Align getAlign() const
Return the alignment of the memory that is being allocated by the instruction.
void setAllocatedType(Type *Ty)
for use only in special circumstances that need to generically transform a whole instruction (eg: IR ...
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
unsigned getAddressSpace() const
Return the address space for the allocation.
LLVM_ABI std::optional< TypeSize > getAllocationSize(const DataLayout &DL) const
Get allocation size in bytes.
void setAlignment(Align Align)
const Value * getArraySize() const
Get the number of elements allocated.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
iterator end()
Definition BasicBlock.h:453
iterator begin()
Instruction iterator methods.
Definition BasicBlock.h:440
LLVM_ABI bool isEntryBlock() const
Return true if this is the entry block of the containing function.
InstListType::iterator iterator
Instruction iterators...
Definition BasicBlock.h:170
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
ModRefInfo callCapturesBefore(const Instruction *I, const MemoryLocation &MemLoc, DominatorTree *DT)
Represents analyses that only rely on functions' control flow.
Definition Analysis.h:73
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
LLVM_ABI bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Determine whether the argument or parameter has the given attribute.
bool isByValArgument(unsigned ArgNo) const
Determine whether this argument is passed by value.
MaybeAlign getParamAlign(unsigned ArgNo) const
Extract the alignment for a call or parameter (0=unknown).
bool onlyReadsMemory(unsigned OpNo) const
Type * getParamByValType(unsigned ArgNo) const
Extract the byval type for a call or parameter.
Value * getArgOperand(unsigned i) const
void setArgOperand(unsigned i, Value *v)
unsigned arg_size() const
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:64
LLVM_ABI IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
Analysis pass which computes a DominatorTree.
Definition Dominators.h:241
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition Dominators.h:122
Context-sensitive CaptureAnalysis provider, which computes and caches the earliest common dominator c...
static GEPNoWrapFlags inBounds()
LLVM_ABI void mergeDIAssignID(ArrayRef< const Instruction * > SourceInstructions)
Merge the DIAssignID metadata from this instruction and those attached to instructions in SourceInstr...
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI void moveBefore(InstListType::iterator InsertPos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
LLVM_ABI void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs={})
Drop all unknown metadata except for debug locations.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
Value * getPointerOperand()
bool isSimple() const
Align getAlign() const
Return the alignment of the access that is being performed.
bool hasValue() const
static LocationSize precise(uint64_t Value)
TypeSize getValue() const
This class wraps the llvm.memcpy intrinsic.
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Value * getLength() const
Value * getRawDest() const
Value * getDest() const
This is just like getRawDest, but it strips off any cast instructions (including addrspacecast) that ...
MaybeAlign getDestAlign() const
This is the common base class for memset/memcpy/memmove.
bool isVolatile() const
Value * getValue() const
Value * getRawSource() const
Return the arguments to the instruction.
MaybeAlign getSourceAlign() const
Value * getSource() const
This is just like getRawSource, but it strips off any cast instructions that feed it,...
BasicBlock * getBlock() const
Definition MemorySSA.h:164
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Definition MemorySSA.h:369
Representation for a specific memory location.
static LLVM_ABI MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static LLVM_ABI MemoryLocation getForSource(const MemTransferInst *MTI)
Return a location representing the source of a memory transfer.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
static MemoryLocation getBeforeOrAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location before or after Ptr, while remaining within the underl...
static LLVM_ABI MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
An analysis that produces MemorySSA for a function.
Definition MemorySSA.h:936
MemoryAccess * getClobberingMemoryAccess(const Instruction *I, BatchAAResults &AA)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Definition MemorySSA.h:1049
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition MemorySSA.h:689
LLVM_ABI bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
LLVM_ABI void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
LLVM_ABI MemorySSAWalker * getWalker()
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition MemorySSA.h:707
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition MemorySSA.h:727
Class that has the common methods + fields of memory uses/defs.
Definition MemorySSA.h:252
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Definition MemorySSA.h:262
Instruction * getMemoryInst() const
Get the instruction that this MemoryUse represents.
Definition MemorySSA.h:259
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
PreservedAnalyses & preserveSet()
Mark an analysis set as preserved.
Definition Analysis.h:152
PreservedAnalyses & preserve()
Mark an analysis as preserved.
Definition Analysis.h:133
size_type size() const
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
void reserve(size_type N)
typename SuperClass::const_iterator const_iterator
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
typename SuperClass::iterator iterator
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
static constexpr TypeSize getFixed(ScalarTy ExactSize)
Definition TypeSize.h:352
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition Type.h:370
void setOperand(unsigned i, Value *Val)
Definition User.h:212
Value * getOperand(unsigned i) const
Definition User.h:207
LLVM Value Representation.
Definition Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:257
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition Value.h:441
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition Value.cpp:548
LLVM_ABI const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition Value.cpp:707
bool use_empty() const
Definition Value.h:348
LLVM_ABI std::optional< int64_t > getPointerOffsetFrom(const Value *Other, const DataLayout &DL) const
If this ptr is provably equal to Other plus a constant offset, return that offset in bytes.
Definition Value.cpp:1078
constexpr ScalarTy getFixedValue() const
Definition TypeSize.h:201
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
Definition TypeSize.h:169
const ParentTy * getParent() const
Definition ilist_node.h:34
reverse_self_iterator getReverseIterator()
Definition ilist_node.h:126
self_iterator getIterator()
Definition ilist_node.h:123
CallInst * Call
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
Abstract Attribute helper functions.
Definition Attributor.h:166
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:83
LLVM_ABI Function * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > OverloadTys={})
Look up the Function declaration of the intrinsic id in the Module M.
@ User
could "use" a pointer
bool empty() const
Definition BasicBlock.h:101
iterator end() const
Definition BasicBlock.h:89
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
LLVM_ABI iterator begin() const
This is an optimization pass for GlobalISel generic memory operations.
@ Offset
Definition DWP.cpp:577
bool capturesAddress(CaptureComponents CC)
Definition ModRef.h:387
LLVM_ABI Align getOrEnforceKnownAlignment(Value *V, MaybeAlign PrefAlign, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr)
Try to ensure that the alignment of V is at least PrefAlign bytes.
Definition Local.cpp:1607
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
scope_exit(Callable) -> scope_exit< Callable >
@ Load
The value being inserted comes from a load (InsertElement only).
@ Store
The extracted value is stored (ExtractElement only).
auto partition_point(R &&Range, Predicate P)
Binary search for the first iterator in a range where a predicate is false.
Definition STLExtras.h:2145
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition STLExtras.h:2229
auto cast_or_null(const Y &Val)
Definition Casting.h:714
LLVM_ABI unsigned getDefaultMaxUsesToExploreForCaptureTracking()
getDefaultMaxUsesToExploreForCaptureTracking - Return default value of the maximal number of uses to ...
LLVM_ABI bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, const Instruction *I, const DominatorTree *DT, bool IncludeI=false, unsigned MaxUsesToExplore=0, const LoopInfo *LI=nullptr)
PointerMayBeCapturedBefore - Return true if this pointer value may be captured by the enclosing funct...
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
auto dyn_cast_or_null(const Y &Val)
Definition Casting.h:753
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1762
auto reverse(ContainerTy &&C)
Definition STLExtras.h:408
bool isModSet(const ModRefInfo MRI)
Definition ModRef.h:49
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
IRBuilder(LLVMContext &, FolderTy, InserterTy) -> IRBuilder< FolderTy, InserterTy >
bool isModOrRefSet(const ModRefInfo MRI)
Definition ModRef.h:43
LLVM_ABI bool isNotVisibleOnUnwind(const Value *Object, bool &RequiresNoCaptureBeforeUnwind)
Return true if Object memory is not visible after an unwind, in the sense that program semantics cann...
LLVM_ABI bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition MemorySSA.cpp:76
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth, bool MustPreserveProvenance=false)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
LLVM_ABI bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition ModRef.h:28
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
DWARFExpression::Operation Op
LLVM_ABI bool isPotentiallyReachableFromMany(SmallVectorImpl< BasicBlock * > &Worklist, const BasicBlock *StopBB, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr, const CycleInfo *CI=nullptr)
Determine whether there is at least one path from a block in 'Worklist' to 'StopBB' without passing t...
Definition CFG.cpp:293
LLVM_ABI bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
LLVM_ABI Value * isBytewiseValue(Value *V, const DataLayout &DL)
If the specified value can be set by repeating the same byte in memory, return the i8 value that it i...
Align commonAlignment(Align A, uint64_t Offset)
Returns the alignment that satisfies both alignments.
Definition Alignment.h:206
LLVM_ABI void combineAAMetadata(Instruction *K, const Instruction *J)
Combine metadata of two instructions, where instruction J is a memory access that has been merged int...
Definition Local.cpp:3191
bool capturesAnything(CaptureComponents CC)
Definition ModRef.h:379
LLVM_ABI UseCaptureInfo DetermineUseCaptureKind(const Use &U, const Value *Base)
Determine what kind of capture behaviour U may exhibit.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI bool isDereferenceablePointer(const Value *V, Type *Ty, const SimplifyQuery &Q, bool IgnoreFree=false)
Equivalent to isDereferenceableAndAlignedPointer with an alignment of 1.
Definition Loads.cpp:266
@ End
Run the machine verifier once, at the end of the pipeline.
Definition CodeGen.h:320
AAResults AliasAnalysis
Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.
bool capturesAnyProvenance(CaptureComponents CC)
Definition ModRef.h:400
bool isRefSet(const ModRefInfo MRI)
Definition ModRef.h:52
LLVM_ABI bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
constexpr uint64_t value() const
This is a hole in the type system and should not be abused.
Definition Alignment.h:82
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition Alignment.h:111
Align valueOrOne() const
For convenience, returns a valid alignment or 1 if undefined.
Definition Alignment.h:135
CaptureComponents UseCC
Components captured by this use.
CaptureComponents ResultCC
Components captured by the return value of the user of this Use.