LLVM 20.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"
50#include "llvm/IR/Type.h"
51#include "llvm/IR/User.h"
52#include "llvm/IR/Value.h"
54#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
68 "enable-memcpyopt-without-libcalls", cl::Hidden,
69 cl::desc("Enable memcpyopt even when libcalls are disabled"));
70
71STATISTIC(NumMemCpyInstr, "Number of memcpy instructions deleted");
72STATISTIC(NumMemSetInfer, "Number of memsets inferred");
73STATISTIC(NumMoveToCpy, "Number of memmoves converted to memcpy");
74STATISTIC(NumCpyToSet, "Number of memcpys converted to memset");
75STATISTIC(NumCallSlot, "Number of call slot optimizations performed");
76STATISTIC(NumStackMove, "Number of stack-move optimizations performed");
77
78namespace {
79
80/// Represents a range of memset'd bytes with the ByteVal value.
81/// This allows us to analyze stores like:
82/// store 0 -> P+1
83/// store 0 -> P+0
84/// store 0 -> P+3
85/// store 0 -> P+2
86/// which sometimes happens with stores to arrays of structs etc. When we see
87/// the first store, we make a range [1, 2). The second store extends the range
88/// to [0, 2). The third makes a new range [2, 3). The fourth store joins the
89/// two ranges into [0, 3) which is memset'able.
90struct MemsetRange {
91 // Start/End - A semi range that describes the span that this range covers.
92 // The range is closed at the start and open at the end: [Start, End).
93 int64_t Start, End;
94
95 /// StartPtr - The getelementptr instruction that points to the start of the
96 /// range.
97 Value *StartPtr;
98
99 /// Alignment - The known alignment of the first store.
100 MaybeAlign Alignment;
101
102 /// TheStores - The actual stores that make up this range.
104
105 bool isProfitableToUseMemset(const DataLayout &DL) const;
106};
107
108} // end anonymous namespace
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 I->eraseFromParent();
288}
289
290// Check for mod or ref of Loc between Start and End, excluding both boundaries.
291// Start and End must be in the same block.
292// If SkippedLifetimeStart is provided, skip over one clobbering lifetime.start
293// intrinsic and store it inside SkippedLifetimeStart.
295 const MemoryUseOrDef *Start,
296 const MemoryUseOrDef *End,
297 Instruction **SkippedLifetimeStart = nullptr) {
298 assert(Start->getBlock() == End->getBlock() && "Only local supported");
299 for (const MemoryAccess &MA :
300 make_range(++Start->getIterator(), End->getIterator())) {
301 Instruction *I = cast<MemoryUseOrDef>(MA).getMemoryInst();
302 if (isModOrRefSet(AA.getModRefInfo(I, Loc))) {
303 auto *II = dyn_cast<IntrinsicInst>(I);
304 if (II && II->getIntrinsicID() == Intrinsic::lifetime_start &&
305 SkippedLifetimeStart && !*SkippedLifetimeStart) {
306 *SkippedLifetimeStart = I;
307 continue;
308 }
309
310 return true;
311 }
312 }
313 return false;
314}
315
316// Check for mod of Loc between Start and End, excluding both boundaries.
317// Start and End can be in different blocks.
319 MemoryLocation Loc, const MemoryUseOrDef *Start,
320 const MemoryUseOrDef *End) {
321 if (isa<MemoryUse>(End)) {
322 // For MemoryUses, getClobberingMemoryAccess may skip non-clobbering writes.
323 // Manually check read accesses between Start and End, if they are in the
324 // same block, for clobbers. Otherwise assume Loc is clobbered.
325 return Start->getBlock() != End->getBlock() ||
326 any_of(
327 make_range(std::next(Start->getIterator()), End->getIterator()),
328 [&AA, Loc](const MemoryAccess &Acc) {
329 if (isa<MemoryUse>(&Acc))
330 return false;
331 Instruction *AccInst =
332 cast<MemoryUseOrDef>(&Acc)->getMemoryInst();
333 return isModSet(AA.getModRefInfo(AccInst, Loc));
334 });
335 }
336
337 // TODO: Only walk until we hit Start.
339 End->getDefiningAccess(), Loc, AA);
340 return !MSSA->dominates(Clobber, Start);
341}
342
343// Update AA metadata
344static void combineAAMetadata(Instruction *ReplInst, Instruction *I) {
345 // FIXME: MD_tbaa_struct and MD_mem_parallel_loop_access should also be
346 // handled here, but combineMetadata doesn't support them yet
347 unsigned KnownIDs[] = {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
348 LLVMContext::MD_noalias,
349 LLVMContext::MD_invariant_group,
350 LLVMContext::MD_access_group};
351 combineMetadata(ReplInst, I, KnownIDs, true);
352}
353
354/// When scanning forward over instructions, we look for some other patterns to
355/// fold away. In particular, this looks for stores to neighboring locations of
356/// memory. If it sees enough consecutive ones, it attempts to merge them
357/// together into a memcpy/memset.
358Instruction *MemCpyOptPass::tryMergingIntoMemset(Instruction *StartInst,
359 Value *StartPtr,
360 Value *ByteVal) {
361 const DataLayout &DL = StartInst->getDataLayout();
362
363 // We can't track scalable types
364 if (auto *SI = dyn_cast<StoreInst>(StartInst))
365 if (DL.getTypeStoreSize(SI->getOperand(0)->getType()).isScalable())
366 return nullptr;
367
368 // Okay, so we now have a single store that can be splatable. Scan to find
369 // all subsequent stores of the same value to offset from the same pointer.
370 // Join these together into ranges, so we can decide whether contiguous blocks
371 // are stored.
372 MemsetRanges Ranges(DL);
373
374 BasicBlock::iterator BI(StartInst);
375
376 // Keeps track of the last memory use or def before the insertion point for
377 // the new memset. The new MemoryDef for the inserted memsets will be inserted
378 // after MemInsertPoint.
379 MemoryUseOrDef *MemInsertPoint = nullptr;
380 for (++BI; !BI->isTerminator(); ++BI) {
381 auto *CurrentAcc = cast_or_null<MemoryUseOrDef>(
382 MSSAU->getMemorySSA()->getMemoryAccess(&*BI));
383 if (CurrentAcc)
384 MemInsertPoint = CurrentAcc;
385
386 // Calls that only access inaccessible memory do not block merging
387 // accessible stores.
388 if (auto *CB = dyn_cast<CallBase>(BI)) {
389 if (CB->onlyAccessesInaccessibleMemory())
390 continue;
391 }
392
393 if (!isa<StoreInst>(BI) && !isa<MemSetInst>(BI)) {
394 // If the instruction is readnone, ignore it, otherwise bail out. We
395 // don't even allow readonly here because we don't want something like:
396 // A[1] = 2; strlen(A); A[2] = 2; -> memcpy(A, ...); strlen(A).
397 if (BI->mayWriteToMemory() || BI->mayReadFromMemory())
398 break;
399 continue;
400 }
401
402 if (auto *NextStore = dyn_cast<StoreInst>(BI)) {
403 // If this is a store, see if we can merge it in.
404 if (!NextStore->isSimple())
405 break;
406
407 Value *StoredVal = NextStore->getValueOperand();
408
409 // Don't convert stores of non-integral pointer types to memsets (which
410 // stores integers).
411 if (DL.isNonIntegralPointerType(StoredVal->getType()->getScalarType()))
412 break;
413
414 // We can't track ranges involving scalable types.
415 if (DL.getTypeStoreSize(StoredVal->getType()).isScalable())
416 break;
417
418 // Check to see if this stored value is of the same byte-splattable value.
419 Value *StoredByte = isBytewiseValue(StoredVal, DL);
420 if (isa<UndefValue>(ByteVal) && StoredByte)
421 ByteVal = StoredByte;
422 if (ByteVal != StoredByte)
423 break;
424
425 // Check to see if this store is to a constant offset from the start ptr.
426 std::optional<int64_t> Offset =
427 NextStore->getPointerOperand()->getPointerOffsetFrom(StartPtr, DL);
428 if (!Offset)
429 break;
430
431 Ranges.addStore(*Offset, NextStore);
432 } else {
433 auto *MSI = cast<MemSetInst>(BI);
434
435 if (MSI->isVolatile() || ByteVal != MSI->getValue() ||
436 !isa<ConstantInt>(MSI->getLength()))
437 break;
438
439 // Check to see if this store is to a constant offset from the start ptr.
440 std::optional<int64_t> Offset =
441 MSI->getDest()->getPointerOffsetFrom(StartPtr, DL);
442 if (!Offset)
443 break;
444
445 Ranges.addMemSet(*Offset, MSI);
446 }
447 }
448
449 // If we have no ranges, then we just had a single store with nothing that
450 // could be merged in. This is a very common case of course.
451 if (Ranges.empty())
452 return nullptr;
453
454 // If we had at least one store that could be merged in, add the starting
455 // store as well. We try to avoid this unless there is at least something
456 // interesting as a small compile-time optimization.
457 Ranges.addInst(0, StartInst);
458
459 // If we create any memsets, we put it right before the first instruction that
460 // isn't part of the memset block. This ensure that the memset is dominated
461 // by any addressing instruction needed by the start of the block.
462 IRBuilder<> Builder(&*BI);
463
464 // Now that we have full information about ranges, loop over the ranges and
465 // emit memset's for anything big enough to be worthwhile.
466 Instruction *AMemSet = nullptr;
467 for (const MemsetRange &Range : Ranges) {
468 if (Range.TheStores.size() == 1)
469 continue;
470
471 // If it is profitable to lower this range to memset, do so now.
472 if (!Range.isProfitableToUseMemset(DL))
473 continue;
474
475 // Otherwise, we do want to transform this! Create a new memset.
476 // Get the starting pointer of the block.
477 StartPtr = Range.StartPtr;
478
479 AMemSet = Builder.CreateMemSet(StartPtr, ByteVal, Range.End - Range.Start,
480 Range.Alignment);
481 AMemSet->mergeDIAssignID(Range.TheStores);
482
483 LLVM_DEBUG(dbgs() << "Replace stores:\n"; for (Instruction *SI
484 : Range.TheStores) dbgs()
485 << *SI << '\n';
486 dbgs() << "With: " << *AMemSet << '\n');
487 if (!Range.TheStores.empty())
488 AMemSet->setDebugLoc(Range.TheStores[0]->getDebugLoc());
489
490 auto *NewDef = cast<MemoryDef>(
491 MemInsertPoint->getMemoryInst() == &*BI
492 ? MSSAU->createMemoryAccessBefore(AMemSet, nullptr, MemInsertPoint)
493 : MSSAU->createMemoryAccessAfter(AMemSet, nullptr, MemInsertPoint));
494 MSSAU->insertDef(NewDef, /*RenameUses=*/true);
495 MemInsertPoint = NewDef;
496
497 // Zap all the stores.
498 for (Instruction *SI : Range.TheStores)
499 eraseInstruction(SI);
500
501 ++NumMemSetInfer;
502 }
503
504 return AMemSet;
505}
506
507// This method try to lift a store instruction before position P.
508// It will lift the store and its argument + that anything that
509// may alias with these.
510// The method returns true if it was successful.
511bool MemCpyOptPass::moveUp(StoreInst *SI, Instruction *P, const LoadInst *LI) {
512 // If the store alias this position, early bail out.
513 MemoryLocation StoreLoc = MemoryLocation::get(SI);
514 if (isModOrRefSet(AA->getModRefInfo(P, StoreLoc)))
515 return false;
516
517 // Keep track of the arguments of all instruction we plan to lift
518 // so we can make sure to lift them as well if appropriate.
520 auto AddArg = [&](Value *Arg) {
521 auto *I = dyn_cast<Instruction>(Arg);
522 if (I && I->getParent() == SI->getParent()) {
523 // Cannot hoist user of P above P
524 if (I == P)
525 return false;
526 Args.insert(I);
527 }
528 return true;
529 };
530 if (!AddArg(SI->getPointerOperand()))
531 return false;
532
533 // Instruction to lift before P.
535
536 // Memory locations of lifted instructions.
537 SmallVector<MemoryLocation, 8> MemLocs{StoreLoc};
538
539 // Lifted calls.
541
542 const MemoryLocation LoadLoc = MemoryLocation::get(LI);
543
544 for (auto I = --SI->getIterator(), E = P->getIterator(); I != E; --I) {
545 auto *C = &*I;
546
547 // Make sure hoisting does not perform a store that was not guaranteed to
548 // happen.
550 return false;
551
552 bool MayAlias = isModOrRefSet(AA->getModRefInfo(C, std::nullopt));
553
554 bool NeedLift = false;
555 if (Args.erase(C))
556 NeedLift = true;
557 else if (MayAlias) {
558 NeedLift = llvm::any_of(MemLocs, [C, this](const MemoryLocation &ML) {
559 return isModOrRefSet(AA->getModRefInfo(C, ML));
560 });
561
562 if (!NeedLift)
563 NeedLift = llvm::any_of(Calls, [C, this](const CallBase *Call) {
564 return isModOrRefSet(AA->getModRefInfo(C, Call));
565 });
566 }
567
568 if (!NeedLift)
569 continue;
570
571 if (MayAlias) {
572 // Since LI is implicitly moved downwards past the lifted instructions,
573 // none of them may modify its source.
574 if (isModSet(AA->getModRefInfo(C, LoadLoc)))
575 return false;
576 else if (const auto *Call = dyn_cast<CallBase>(C)) {
577 // If we can't lift this before P, it's game over.
578 if (isModOrRefSet(AA->getModRefInfo(P, Call)))
579 return false;
580
581 Calls.push_back(Call);
582 } else if (isa<LoadInst>(C) || isa<StoreInst>(C) || isa<VAArgInst>(C)) {
583 // If we can't lift this before P, it's game over.
584 auto ML = MemoryLocation::get(C);
585 if (isModOrRefSet(AA->getModRefInfo(P, ML)))
586 return false;
587
588 MemLocs.push_back(ML);
589 } else
590 // We don't know how to lift this instruction.
591 return false;
592 }
593
594 ToLift.push_back(C);
595 for (Value *Op : C->operands())
596 if (!AddArg(Op))
597 return false;
598 }
599
600 // Find MSSA insertion point. Normally P will always have a corresponding
601 // memory access before which we can insert. However, with non-standard AA
602 // pipelines, there may be a mismatch between AA and MSSA, in which case we
603 // will scan for a memory access before P. In either case, we know for sure
604 // that at least the load will have a memory access.
605 // TODO: Simplify this once P will be determined by MSSA, in which case the
606 // discrepancy can no longer occur.
607 MemoryUseOrDef *MemInsertPoint = nullptr;
608 if (MemoryUseOrDef *MA = MSSAU->getMemorySSA()->getMemoryAccess(P)) {
609 MemInsertPoint = cast<MemoryUseOrDef>(--MA->getIterator());
610 } else {
611 const Instruction *ConstP = P;
612 for (const Instruction &I : make_range(++ConstP->getReverseIterator(),
613 ++LI->getReverseIterator())) {
614 if (MemoryUseOrDef *MA = MSSAU->getMemorySSA()->getMemoryAccess(&I)) {
615 MemInsertPoint = MA;
616 break;
617 }
618 }
619 }
620
621 // We made it, we need to lift.
622 for (auto *I : llvm::reverse(ToLift)) {
623 LLVM_DEBUG(dbgs() << "Lifting " << *I << " before " << *P << "\n");
624 I->moveBefore(P);
625 assert(MemInsertPoint && "Must have found insert point");
626 if (MemoryUseOrDef *MA = MSSAU->getMemorySSA()->getMemoryAccess(I)) {
627 MSSAU->moveAfter(MA, MemInsertPoint);
628 MemInsertPoint = MA;
629 }
630 }
631
632 return true;
633}
634
635bool MemCpyOptPass::processStoreOfLoad(StoreInst *SI, LoadInst *LI,
636 const DataLayout &DL,
638 if (!LI->isSimple() || !LI->hasOneUse() || LI->getParent() != SI->getParent())
639 return false;
640
641 auto *T = LI->getType();
642 // Don't introduce calls to memcpy/memmove intrinsics out of thin air if
643 // the corresponding libcalls are not available.
644 // TODO: We should really distinguish between libcall availability and
645 // our ability to introduce intrinsics.
646 if (T->isAggregateType() &&
648 (TLI->has(LibFunc_memcpy) && TLI->has(LibFunc_memmove)))) {
650
651 // We use alias analysis to check if an instruction may store to
652 // the memory we load from in between the load and the store. If
653 // such an instruction is found, we try to promote there instead
654 // of at the store position.
655 // TODO: Can use MSSA for this.
656 Instruction *P = SI;
657 for (auto &I : make_range(++LI->getIterator(), SI->getIterator())) {
658 if (isModSet(AA->getModRefInfo(&I, LoadLoc))) {
659 P = &I;
660 break;
661 }
662 }
663
664 // We found an instruction that may write to the loaded memory.
665 // We can try to promote at this position instead of the store
666 // position if nothing aliases the store memory after this and the store
667 // destination is not in the range.
668 if (P && P != SI) {
669 if (!moveUp(SI, P, LI))
670 P = nullptr;
671 }
672
673 // If a valid insertion position is found, then we can promote
674 // the load/store pair to a memcpy.
675 if (P) {
676 // If we load from memory that may alias the memory we store to,
677 // memmove must be used to preserve semantic. If not, memcpy can
678 // be used. Also, if we load from constant memory, memcpy can be used
679 // as the constant memory won't be modified.
680 bool UseMemMove = false;
681 if (isModSet(AA->getModRefInfo(SI, LoadLoc)))
682 UseMemMove = true;
683
684 IRBuilder<> Builder(P);
685 Value *Size =
686 Builder.CreateTypeSize(Builder.getInt64Ty(), DL.getTypeStoreSize(T));
687 Instruction *M;
688 if (UseMemMove)
689 M = Builder.CreateMemMove(SI->getPointerOperand(), SI->getAlign(),
690 LI->getPointerOperand(), LI->getAlign(),
691 Size);
692 else
693 M = Builder.CreateMemCpy(SI->getPointerOperand(), SI->getAlign(),
694 LI->getPointerOperand(), LI->getAlign(), Size);
695 M->copyMetadata(*SI, LLVMContext::MD_DIAssignID);
696
697 LLVM_DEBUG(dbgs() << "Promoting " << *LI << " to " << *SI << " => " << *M
698 << "\n");
699
700 auto *LastDef =
701 cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(SI));
702 auto *NewAccess = MSSAU->createMemoryAccessAfter(M, nullptr, LastDef);
703 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
704
705 eraseInstruction(SI);
706 eraseInstruction(LI);
707 ++NumMemCpyInstr;
708
709 // Make sure we do not invalidate the iterator.
710 BBI = M->getIterator();
711 return true;
712 }
713 }
714
715 // Detect cases where we're performing call slot forwarding, but
716 // happen to be using a load-store pair to implement it, rather than
717 // a memcpy.
718 BatchAAResults BAA(*AA);
719 auto GetCall = [&]() -> CallInst * {
720 // We defer this expensive clobber walk until the cheap checks
721 // have been done on the source inside performCallSlotOptzn.
722 if (auto *LoadClobber = dyn_cast<MemoryUseOrDef>(
723 MSSA->getWalker()->getClobberingMemoryAccess(LI, BAA)))
724 return dyn_cast_or_null<CallInst>(LoadClobber->getMemoryInst());
725 return nullptr;
726 };
727
728 bool Changed = performCallSlotOptzn(
729 LI, SI, SI->getPointerOperand()->stripPointerCasts(),
731 DL.getTypeStoreSize(SI->getOperand(0)->getType()),
732 std::min(SI->getAlign(), LI->getAlign()), BAA, GetCall);
733 if (Changed) {
734 eraseInstruction(SI);
735 eraseInstruction(LI);
736 ++NumMemCpyInstr;
737 return true;
738 }
739
740 // If this is a load-store pair from a stack slot to a stack slot, we
741 // might be able to perform the stack-move optimization just as we do for
742 // memcpys from an alloca to an alloca.
743 if (auto *DestAlloca = dyn_cast<AllocaInst>(SI->getPointerOperand())) {
744 if (auto *SrcAlloca = dyn_cast<AllocaInst>(LI->getPointerOperand())) {
745 if (performStackMoveOptzn(LI, SI, DestAlloca, SrcAlloca,
746 DL.getTypeStoreSize(T), BAA)) {
747 // Avoid invalidating the iterator.
748 BBI = SI->getNextNonDebugInstruction()->getIterator();
749 eraseInstruction(SI);
750 eraseInstruction(LI);
751 ++NumMemCpyInstr;
752 return true;
753 }
754 }
755 }
756
757 return false;
758}
759
760bool MemCpyOptPass::processStore(StoreInst *SI, BasicBlock::iterator &BBI) {
761 if (!SI->isSimple())
762 return false;
763
764 // Avoid merging nontemporal stores since the resulting
765 // memcpy/memset would not be able to preserve the nontemporal hint.
766 // In theory we could teach how to propagate the !nontemporal metadata to
767 // memset calls. However, that change would force the backend to
768 // conservatively expand !nontemporal memset calls back to sequences of
769 // store instructions (effectively undoing the merging).
770 if (SI->getMetadata(LLVMContext::MD_nontemporal))
771 return false;
772
773 const DataLayout &DL = SI->getDataLayout();
774
775 Value *StoredVal = SI->getValueOperand();
776
777 // Not all the transforms below are correct for non-integral pointers, bail
778 // until we've audited the individual pieces.
779 if (DL.isNonIntegralPointerType(StoredVal->getType()->getScalarType()))
780 return false;
781
782 // Load to store forwarding can be interpreted as memcpy.
783 if (auto *LI = dyn_cast<LoadInst>(StoredVal))
784 return processStoreOfLoad(SI, LI, DL, BBI);
785
786 // The following code creates memset intrinsics out of thin air. Don't do
787 // this if the corresponding libfunc is not available.
788 // TODO: We should really distinguish between libcall availability and
789 // our ability to introduce intrinsics.
790 if (!(TLI->has(LibFunc_memset) || EnableMemCpyOptWithoutLibcalls))
791 return false;
792
793 // There are two cases that are interesting for this code to handle: memcpy
794 // and memset. Right now we only handle memset.
795
796 // Ensure that the value being stored is something that can be memset'able a
797 // byte at a time like "0" or "-1" or any width, as well as things like
798 // 0xA0A0A0A0 and 0.0.
799 auto *V = SI->getOperand(0);
800 if (Value *ByteVal = isBytewiseValue(V, DL)) {
801 if (Instruction *I =
802 tryMergingIntoMemset(SI, SI->getPointerOperand(), ByteVal)) {
803 BBI = I->getIterator(); // Don't invalidate iterator.
804 return true;
805 }
806
807 // If we have an aggregate, we try to promote it to memset regardless
808 // of opportunity for merging as it can expose optimization opportunities
809 // in subsequent passes.
810 auto *T = V->getType();
811 if (T->isAggregateType()) {
812 uint64_t Size = DL.getTypeStoreSize(T);
813 IRBuilder<> Builder(SI);
814 auto *M = Builder.CreateMemSet(SI->getPointerOperand(), ByteVal, Size,
815 SI->getAlign());
816 M->copyMetadata(*SI, LLVMContext::MD_DIAssignID);
817
818 LLVM_DEBUG(dbgs() << "Promoting " << *SI << " to " << *M << "\n");
819
820 // The newly inserted memset is immediately overwritten by the original
821 // store, so we do not need to rename uses.
822 auto *StoreDef = cast<MemoryDef>(MSSA->getMemoryAccess(SI));
823 auto *NewAccess = MSSAU->createMemoryAccessBefore(M, nullptr, StoreDef);
824 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/false);
825
826 eraseInstruction(SI);
827 NumMemSetInfer++;
828
829 // Make sure we do not invalidate the iterator.
830 BBI = M->getIterator();
831 return true;
832 }
833 }
834
835 return false;
836}
837
838bool MemCpyOptPass::processMemSet(MemSetInst *MSI, BasicBlock::iterator &BBI) {
839 // See if there is another memset or store neighboring this memset which
840 // allows us to widen out the memset to do a single larger store.
841 if (isa<ConstantInt>(MSI->getLength()) && !MSI->isVolatile())
842 if (Instruction *I =
843 tryMergingIntoMemset(MSI, MSI->getDest(), MSI->getValue())) {
844 BBI = I->getIterator(); // Don't invalidate iterator.
845 return true;
846 }
847 return false;
848}
849
850/// Takes a memcpy and a call that it depends on,
851/// and checks for the possibility of a call slot optimization by having
852/// the call write its result directly into the destination of the memcpy.
853bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpyLoad,
854 Instruction *cpyStore, Value *cpyDest,
855 Value *cpySrc, TypeSize cpySize,
856 Align cpyDestAlign,
857 BatchAAResults &BAA,
858 std::function<CallInst *()> GetC) {
859 // The general transformation to keep in mind is
860 //
861 // call @func(..., src, ...)
862 // memcpy(dest, src, ...)
863 //
864 // ->
865 //
866 // memcpy(dest, src, ...)
867 // call @func(..., dest, ...)
868 //
869 // Since moving the memcpy is technically awkward, we additionally check that
870 // src only holds uninitialized values at the moment of the call, meaning that
871 // the memcpy can be discarded rather than moved.
872
873 // We can't optimize scalable types.
874 if (cpySize.isScalable())
875 return false;
876
877 // Require that src be an alloca. This simplifies the reasoning considerably.
878 auto *srcAlloca = dyn_cast<AllocaInst>(cpySrc);
879 if (!srcAlloca)
880 return false;
881
882 ConstantInt *srcArraySize = dyn_cast<ConstantInt>(srcAlloca->getArraySize());
883 if (!srcArraySize)
884 return false;
885
886 const DataLayout &DL = cpyLoad->getDataLayout();
887 TypeSize SrcAllocaSize = DL.getTypeAllocSize(srcAlloca->getAllocatedType());
888 // We can't optimize scalable types.
889 if (SrcAllocaSize.isScalable())
890 return false;
891 uint64_t srcSize = SrcAllocaSize * srcArraySize->getZExtValue();
892
893 if (cpySize < srcSize)
894 return false;
895
896 CallInst *C = GetC();
897 if (!C)
898 return false;
899
900 // Lifetime marks shouldn't be operated on.
901 if (Function *F = C->getCalledFunction())
902 if (F->isIntrinsic() && F->getIntrinsicID() == Intrinsic::lifetime_start)
903 return false;
904
905 if (C->getParent() != cpyStore->getParent()) {
906 LLVM_DEBUG(dbgs() << "Call Slot: block local restriction\n");
907 return false;
908 }
909
910 MemoryLocation DestLoc =
911 isa<StoreInst>(cpyStore)
912 ? MemoryLocation::get(cpyStore)
913 : MemoryLocation::getForDest(cast<MemCpyInst>(cpyStore));
914
915 // Check that nothing touches the dest of the copy between
916 // the call and the store/memcpy.
917 Instruction *SkippedLifetimeStart = nullptr;
918 if (accessedBetween(BAA, DestLoc, MSSA->getMemoryAccess(C),
919 MSSA->getMemoryAccess(cpyStore), &SkippedLifetimeStart)) {
920 LLVM_DEBUG(dbgs() << "Call Slot: Dest pointer modified after call\n");
921 return false;
922 }
923
924 // If we need to move a lifetime.start above the call, make sure that we can
925 // actually do so. If the argument is bitcasted for example, we would have to
926 // move the bitcast as well, which we don't handle.
927 if (SkippedLifetimeStart) {
928 auto *LifetimeArg =
929 dyn_cast<Instruction>(SkippedLifetimeStart->getOperand(1));
930 if (LifetimeArg && LifetimeArg->getParent() == C->getParent() &&
931 C->comesBefore(LifetimeArg))
932 return false;
933 }
934
935 // Check that storing to the first srcSize bytes of dest will not cause a
936 // trap or data race.
937 bool ExplicitlyDereferenceableOnly;
939 ExplicitlyDereferenceableOnly) ||
940 !isDereferenceableAndAlignedPointer(cpyDest, Align(1), APInt(64, cpySize),
941 DL, C, AC, DT)) {
942 LLVM_DEBUG(dbgs() << "Call Slot: Dest pointer not dereferenceable\n");
943 return false;
944 }
945
946 // Make sure that nothing can observe cpyDest being written early. There are
947 // a number of cases to consider:
948 // 1. cpyDest cannot be accessed between C and cpyStore as a precondition of
949 // the transform.
950 // 2. C itself may not access cpyDest (prior to the transform). This is
951 // checked further below.
952 // 3. If cpyDest is accessible to the caller of this function (potentially
953 // captured and not based on an alloca), we need to ensure that we cannot
954 // unwind between C and cpyStore. This is checked here.
955 // 4. If cpyDest is potentially captured, there may be accesses to it from
956 // another thread. In this case, we need to check that cpyStore is
957 // guaranteed to be executed if C is. As it is a non-atomic access, it
958 // renders accesses from other threads undefined.
959 // TODO: This is currently not checked.
960 if (mayBeVisibleThroughUnwinding(cpyDest, C, cpyStore)) {
961 LLVM_DEBUG(dbgs() << "Call Slot: Dest may be visible through unwinding\n");
962 return false;
963 }
964
965 // Check that dest points to memory that is at least as aligned as src.
966 Align srcAlign = srcAlloca->getAlign();
967 bool isDestSufficientlyAligned = srcAlign <= cpyDestAlign;
968 // If dest is not aligned enough and we can't increase its alignment then
969 // bail out.
970 if (!isDestSufficientlyAligned && !isa<AllocaInst>(cpyDest)) {
971 LLVM_DEBUG(dbgs() << "Call Slot: Dest not sufficiently aligned\n");
972 return false;
973 }
974
975 // Check that src is not accessed except via the call and the memcpy. This
976 // guarantees that it holds only undefined values when passed in (so the final
977 // memcpy can be dropped), that it is not read or written between the call and
978 // the memcpy, and that writing beyond the end of it is undefined.
979 SmallVector<User *, 8> srcUseList(srcAlloca->users());
980 while (!srcUseList.empty()) {
981 User *U = srcUseList.pop_back_val();
982
983 if (isa<AddrSpaceCastInst>(U)) {
984 append_range(srcUseList, U->users());
985 continue;
986 }
987 if (const auto *IT = dyn_cast<IntrinsicInst>(U))
988 if (IT->isLifetimeStartOrEnd())
989 continue;
990
991 if (U != C && U != cpyLoad) {
992 LLVM_DEBUG(dbgs() << "Call slot: Source accessed by " << *U << "\n");
993 return false;
994 }
995 }
996
997 // Check whether src is captured by the called function, in which case there
998 // may be further indirect uses of src.
999 bool SrcIsCaptured = any_of(C->args(), [&](Use &U) {
1000 return U->stripPointerCasts() == cpySrc &&
1001 !C->doesNotCapture(C->getArgOperandNo(&U));
1002 });
1003
1004 // If src is captured, then check whether there are any potential uses of
1005 // src through the captured pointer before the lifetime of src ends, either
1006 // due to a lifetime.end or a return from the function.
1007 if (SrcIsCaptured) {
1008 // Check that dest is not captured before/at the call. We have already
1009 // checked that src is not captured before it. If either had been captured,
1010 // then the call might be comparing the argument against the captured dest
1011 // or src pointer.
1012 Value *DestObj = getUnderlyingObject(cpyDest);
1013 if (!isIdentifiedFunctionLocal(DestObj) ||
1014 PointerMayBeCapturedBefore(DestObj, /* ReturnCaptures */ true,
1015 /* StoreCaptures */ true, C, DT,
1016 /* IncludeI */ true))
1017 return false;
1018
1019 MemoryLocation SrcLoc =
1020 MemoryLocation(srcAlloca, LocationSize::precise(srcSize));
1021 for (Instruction &I :
1022 make_range(++C->getIterator(), C->getParent()->end())) {
1023 // Lifetime of srcAlloca ends at lifetime.end.
1024 if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
1025 if (II->getIntrinsicID() == Intrinsic::lifetime_end &&
1026 II->getArgOperand(1)->stripPointerCasts() == srcAlloca &&
1027 cast<ConstantInt>(II->getArgOperand(0))->uge(srcSize))
1028 break;
1029 }
1030
1031 // Lifetime of srcAlloca ends at return.
1032 if (isa<ReturnInst>(&I))
1033 break;
1034
1035 // Ignore the direct read of src in the load.
1036 if (&I == cpyLoad)
1037 continue;
1038
1039 // Check whether this instruction may mod/ref src through the captured
1040 // pointer (we have already any direct mod/refs in the loop above).
1041 // Also bail if we hit a terminator, as we don't want to scan into other
1042 // blocks.
1043 if (isModOrRefSet(BAA.getModRefInfo(&I, SrcLoc)) || I.isTerminator())
1044 return false;
1045 }
1046 }
1047
1048 // Since we're changing the parameter to the callsite, we need to make sure
1049 // that what would be the new parameter dominates the callsite.
1050 bool NeedMoveGEP = false;
1051 if (!DT->dominates(cpyDest, C)) {
1052 // Support moving a constant index GEP before the call.
1053 auto *GEP = dyn_cast<GetElementPtrInst>(cpyDest);
1054 if (GEP && GEP->hasAllConstantIndices() &&
1055 DT->dominates(GEP->getPointerOperand(), C))
1056 NeedMoveGEP = true;
1057 else
1058 return false;
1059 }
1060
1061 // In addition to knowing that the call does not access src in some
1062 // unexpected manner, for example via a global, which we deduce from
1063 // the use analysis, we also need to know that it does not sneakily
1064 // access dest. We rely on AA to figure this out for us.
1065 MemoryLocation DestWithSrcSize(cpyDest, LocationSize::precise(srcSize));
1066 ModRefInfo MR = BAA.getModRefInfo(C, DestWithSrcSize);
1067 // If necessary, perform additional analysis.
1068 if (isModOrRefSet(MR))
1069 MR = BAA.callCapturesBefore(C, DestWithSrcSize, DT);
1070 if (isModOrRefSet(MR))
1071 return false;
1072
1073 // We can't create address space casts here because we don't know if they're
1074 // safe for the target.
1075 if (cpySrc->getType() != cpyDest->getType())
1076 return false;
1077 for (unsigned ArgI = 0; ArgI < C->arg_size(); ++ArgI)
1078 if (C->getArgOperand(ArgI)->stripPointerCasts() == cpySrc &&
1079 cpySrc->getType() != C->getArgOperand(ArgI)->getType())
1080 return false;
1081
1082 // All the checks have passed, so do the transformation.
1083 bool changedArgument = false;
1084 for (unsigned ArgI = 0; ArgI < C->arg_size(); ++ArgI)
1085 if (C->getArgOperand(ArgI)->stripPointerCasts() == cpySrc) {
1086 changedArgument = true;
1087 C->setArgOperand(ArgI, cpyDest);
1088 }
1089
1090 if (!changedArgument)
1091 return false;
1092
1093 // If the destination wasn't sufficiently aligned then increase its alignment.
1094 if (!isDestSufficientlyAligned) {
1095 assert(isa<AllocaInst>(cpyDest) && "Can only increase alloca alignment!");
1096 cast<AllocaInst>(cpyDest)->setAlignment(srcAlign);
1097 }
1098
1099 if (NeedMoveGEP) {
1100 auto *GEP = dyn_cast<GetElementPtrInst>(cpyDest);
1101 GEP->moveBefore(C);
1102 }
1103
1104 if (SkippedLifetimeStart) {
1105 SkippedLifetimeStart->moveBefore(C);
1106 MSSAU->moveBefore(MSSA->getMemoryAccess(SkippedLifetimeStart),
1107 MSSA->getMemoryAccess(C));
1108 }
1109
1110 combineAAMetadata(C, cpyLoad);
1111 if (cpyLoad != cpyStore)
1112 combineAAMetadata(C, cpyStore);
1113
1114 ++NumCallSlot;
1115 return true;
1116}
1117
1118/// We've found that the (upward scanning) memory dependence of memcpy 'M' is
1119/// the memcpy 'MDep'. Try to simplify M to copy from MDep's input if we can.
1120bool MemCpyOptPass::processMemCpyMemCpyDependence(MemCpyInst *M,
1121 MemCpyInst *MDep,
1122 BatchAAResults &BAA) {
1123 // If dep instruction is reading from our current input, then it is a noop
1124 // transfer and substituting the input won't change this instruction. Just
1125 // ignore the input and let someone else zap MDep. This handles cases like:
1126 // memcpy(a <- a)
1127 // memcpy(b <- a)
1128 if (M->getSource() == MDep->getSource())
1129 return false;
1130
1131 // We can only optimize non-volatile memcpy's.
1132 if (MDep->isVolatile())
1133 return false;
1134
1135 int64_t MForwardOffset = 0;
1136 const DataLayout &DL = M->getModule()->getDataLayout();
1137 // We can only transforms memcpy's where the dest of one is the source of the
1138 // other, or they have an offset in a range.
1139 if (M->getSource() != MDep->getDest()) {
1140 std::optional<int64_t> Offset =
1141 M->getSource()->getPointerOffsetFrom(MDep->getDest(), DL);
1142 if (!Offset || *Offset < 0)
1143 return false;
1144 MForwardOffset = *Offset;
1145 }
1146
1147 // The length of the memcpy's must be the same, or the preceding one
1148 // must be larger than the following one.
1149 if (MForwardOffset != 0 || MDep->getLength() != M->getLength()) {
1150 auto *MDepLen = dyn_cast<ConstantInt>(MDep->getLength());
1151 auto *MLen = dyn_cast<ConstantInt>(M->getLength());
1152 if (!MDepLen || !MLen ||
1153 MDepLen->getZExtValue() < MLen->getZExtValue() + MForwardOffset)
1154 return false;
1155 }
1156
1157 IRBuilder<> Builder(M);
1158 auto *CopySource = MDep->getSource();
1159 Instruction *NewCopySource = nullptr;
1160 auto CleanupOnRet = llvm::make_scope_exit([&NewCopySource] {
1161 if (NewCopySource && NewCopySource->use_empty())
1162 // Safety: It's safe here because we will only allocate more instructions
1163 // after finishing all BatchAA queries, but we have to be careful if we
1164 // want to do something like this in another place. Then we'd probably
1165 // have to delay instruction removal until all transforms on an
1166 // instruction finished.
1167 NewCopySource->eraseFromParent();
1168 });
1169 MaybeAlign CopySourceAlign = MDep->getSourceAlign();
1170 // We just need to calculate the actual size of the copy.
1171 auto MCopyLoc = MemoryLocation::getForSource(MDep).getWithNewSize(
1173
1174 // When the forwarding offset is greater than 0, we transform
1175 // memcpy(d1 <- s1)
1176 // memcpy(d2 <- d1+o)
1177 // to
1178 // memcpy(d2 <- s1+o)
1179 if (MForwardOffset > 0) {
1180 // The copy destination of `M` maybe can serve as the source of copying.
1181 std::optional<int64_t> MDestOffset =
1182 M->getRawDest()->getPointerOffsetFrom(MDep->getRawSource(), DL);
1183 if (MDestOffset == MForwardOffset)
1184 CopySource = M->getDest();
1185 else {
1186 CopySource = Builder.CreateInBoundsPtrAdd(
1187 CopySource, Builder.getInt64(MForwardOffset));
1188 NewCopySource = dyn_cast<Instruction>(CopySource);
1189 }
1190 // We need to update `MCopyLoc` if an offset exists.
1191 MCopyLoc = MCopyLoc.getWithNewPtr(CopySource);
1192 if (CopySourceAlign)
1193 CopySourceAlign = commonAlignment(*CopySourceAlign, MForwardOffset);
1194 }
1195
1196 // Verify that the copied-from memory doesn't change in between the two
1197 // transfers. For example, in:
1198 // memcpy(a <- b)
1199 // *b = 42;
1200 // memcpy(c <- a)
1201 // It would be invalid to transform the second memcpy into memcpy(c <- b).
1202 //
1203 // TODO: If the code between M and MDep is transparent to the destination "c",
1204 // then we could still perform the xform by moving M up to the first memcpy.
1205 if (writtenBetween(MSSA, BAA, MCopyLoc, MSSA->getMemoryAccess(MDep),
1206 MSSA->getMemoryAccess(M)))
1207 return false;
1208
1209 // No need to create `memcpy(a <- a)`.
1210 if (BAA.isMustAlias(M->getDest(), CopySource)) {
1211 // Remove the instruction we're replacing.
1212 eraseInstruction(M);
1213 ++NumMemCpyInstr;
1214 return true;
1215 }
1216
1217 // If the dest of the second might alias the source of the first, then the
1218 // source and dest might overlap. In addition, if the source of the first
1219 // points to constant memory, they won't overlap by definition. Otherwise, we
1220 // still want to eliminate the intermediate value, but we have to generate a
1221 // memmove instead of memcpy.
1222 bool UseMemMove = false;
1224 // Don't convert llvm.memcpy.inline into memmove because memmove can be
1225 // lowered as a call, and that is not allowed for llvm.memcpy.inline (and
1226 // there is no inline version of llvm.memmove)
1227 if (isa<MemCpyInlineInst>(M))
1228 return false;
1229 UseMemMove = true;
1230 }
1231
1232 // If all checks passed, then we can transform M.
1233 LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy->memcpy src:\n"
1234 << *MDep << '\n'
1235 << *M << '\n');
1236
1237 // TODO: Is this worth it if we're creating a less aligned memcpy? For
1238 // example we could be moving from movaps -> movq on x86.
1239 Instruction *NewM;
1240 if (UseMemMove)
1241 NewM =
1242 Builder.CreateMemMove(M->getDest(), M->getDestAlign(), CopySource,
1243 CopySourceAlign, M->getLength(), M->isVolatile());
1244 else if (isa<MemCpyInlineInst>(M)) {
1245 // llvm.memcpy may be promoted to llvm.memcpy.inline, but the converse is
1246 // never allowed since that would allow the latter to be lowered as a call
1247 // to an external function.
1248 NewM = Builder.CreateMemCpyInline(M->getDest(), M->getDestAlign(),
1249 CopySource, CopySourceAlign,
1250 M->getLength(), M->isVolatile());
1251 } else
1252 NewM =
1253 Builder.CreateMemCpy(M->getDest(), M->getDestAlign(), CopySource,
1254 CopySourceAlign, M->getLength(), M->isVolatile());
1255 NewM->copyMetadata(*M, LLVMContext::MD_DIAssignID);
1256
1257 assert(isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(M)));
1258 auto *LastDef = cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(M));
1259 auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM, nullptr, LastDef);
1260 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
1261
1262 // Remove the instruction we're replacing.
1263 eraseInstruction(M);
1264 ++NumMemCpyInstr;
1265 return true;
1266}
1267
1268/// We've found that the (upward scanning) memory dependence of \p MemCpy is
1269/// \p MemSet. Try to simplify \p MemSet to only set the trailing bytes that
1270/// weren't copied over by \p MemCpy.
1271///
1272/// In other words, transform:
1273/// \code
1274/// memset(dst, c, dst_size);
1275/// ...
1276/// memcpy(dst, src, src_size);
1277/// \endcode
1278/// into:
1279/// \code
1280/// ...
1281/// memset(dst + src_size, c, dst_size <= src_size ? 0 : dst_size - src_size);
1282/// memcpy(dst, src, src_size);
1283/// \endcode
1284///
1285/// The memset is sunk to just before the memcpy to ensure that src_size is
1286/// present when emitting the simplified memset.
1287bool MemCpyOptPass::processMemSetMemCpyDependence(MemCpyInst *MemCpy,
1288 MemSetInst *MemSet,
1289 BatchAAResults &BAA) {
1290 // We can only transform memset/memcpy with the same destination.
1291 if (!BAA.isMustAlias(MemSet->getDest(), MemCpy->getDest()))
1292 return false;
1293
1294 // Don't perform the transform if src_size may be zero. In that case, the
1295 // transform is essentially a complex no-op and may lead to an infinite
1296 // loop if BasicAA is smart enough to understand that dst and dst + src_size
1297 // are still MustAlias after the transform.
1298 Value *SrcSize = MemCpy->getLength();
1299 if (!isKnownNonZero(SrcSize,
1300 SimplifyQuery(MemCpy->getDataLayout(), DT, AC, MemCpy)))
1301 return false;
1302
1303 // Check that src and dst of the memcpy aren't the same. While memcpy
1304 // operands cannot partially overlap, exact equality is allowed.
1305 if (isModSet(BAA.getModRefInfo(MemCpy, MemoryLocation::getForSource(MemCpy))))
1306 return false;
1307
1308 // We know that dst up to src_size is not written. We now need to make sure
1309 // that dst up to dst_size is not accessed. (If we did not move the memset,
1310 // checking for reads would be sufficient.)
1312 MSSA->getMemoryAccess(MemSet),
1313 MSSA->getMemoryAccess(MemCpy)))
1314 return false;
1315
1316 // Use the same i8* dest as the memcpy, killing the memset dest if different.
1317 Value *Dest = MemCpy->getRawDest();
1318 Value *DestSize = MemSet->getLength();
1319
1320 if (mayBeVisibleThroughUnwinding(Dest, MemSet, MemCpy))
1321 return false;
1322
1323 // If the sizes are the same, simply drop the memset instead of generating
1324 // a replacement with zero size.
1325 if (DestSize == SrcSize) {
1326 eraseInstruction(MemSet);
1327 return true;
1328 }
1329
1330 // By default, create an unaligned memset.
1331 Align Alignment = Align(1);
1332 // If Dest is aligned, and SrcSize is constant, use the minimum alignment
1333 // of the sum.
1334 const Align DestAlign = std::max(MemSet->getDestAlign().valueOrOne(),
1335 MemCpy->getDestAlign().valueOrOne());
1336 if (DestAlign > 1)
1337 if (auto *SrcSizeC = dyn_cast<ConstantInt>(SrcSize))
1338 Alignment = commonAlignment(DestAlign, SrcSizeC->getZExtValue());
1339
1340 IRBuilder<> Builder(MemCpy);
1341
1342 // Preserve the debug location of the old memset for the code emitted here
1343 // related to the new memset. This is correct according to the rules in
1344 // https://llvm.org/docs/HowToUpdateDebugInfo.html about "when to preserve an
1345 // instruction location", given that we move the memset within the basic
1346 // block.
1347 assert(MemSet->getParent() == MemCpy->getParent() &&
1348 "Preserving debug location based on moving memset within BB.");
1349 Builder.SetCurrentDebugLocation(MemSet->getDebugLoc());
1350
1351 // If the sizes have different types, zext the smaller one.
1352 if (DestSize->getType() != SrcSize->getType()) {
1353 if (DestSize->getType()->getIntegerBitWidth() >
1354 SrcSize->getType()->getIntegerBitWidth())
1355 SrcSize = Builder.CreateZExt(SrcSize, DestSize->getType());
1356 else
1357 DestSize = Builder.CreateZExt(DestSize, SrcSize->getType());
1358 }
1359
1360 Value *Ule = Builder.CreateICmpULE(DestSize, SrcSize);
1361 Value *SizeDiff = Builder.CreateSub(DestSize, SrcSize);
1362 Value *MemsetLen = Builder.CreateSelect(
1363 Ule, ConstantInt::getNullValue(DestSize->getType()), SizeDiff);
1364 Instruction *NewMemSet =
1365 Builder.CreateMemSet(Builder.CreatePtrAdd(Dest, SrcSize),
1366 MemSet->getOperand(1), MemsetLen, Alignment);
1367
1368 assert(isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy)) &&
1369 "MemCpy must be a MemoryDef");
1370 // The new memset is inserted before the memcpy, and it is known that the
1371 // memcpy's defining access is the memset about to be removed.
1372 auto *LastDef =
1373 cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy));
1374 auto *NewAccess =
1375 MSSAU->createMemoryAccessBefore(NewMemSet, nullptr, LastDef);
1376 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
1377
1378 eraseInstruction(MemSet);
1379 return true;
1380}
1381
1382/// Determine whether the instruction has undefined content for the given Size,
1383/// either because it was freshly alloca'd or started its lifetime.
1385 MemoryDef *Def, Value *Size) {
1386 if (MSSA->isLiveOnEntryDef(Def))
1387 return isa<AllocaInst>(getUnderlyingObject(V));
1388
1389 if (auto *II = dyn_cast_or_null<IntrinsicInst>(Def->getMemoryInst())) {
1390 if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
1391 auto *LTSize = cast<ConstantInt>(II->getArgOperand(0));
1392
1393 if (auto *CSize = dyn_cast<ConstantInt>(Size)) {
1394 if (AA.isMustAlias(V, II->getArgOperand(1)) &&
1395 LTSize->getZExtValue() >= CSize->getZExtValue())
1396 return true;
1397 }
1398
1399 // If the lifetime.start covers a whole alloca (as it almost always
1400 // does) and we're querying a pointer based on that alloca, then we know
1401 // the memory is definitely undef, regardless of how exactly we alias.
1402 // The size also doesn't matter, as an out-of-bounds access would be UB.
1403 if (auto *Alloca = dyn_cast<AllocaInst>(getUnderlyingObject(V))) {
1404 if (getUnderlyingObject(II->getArgOperand(1)) == Alloca) {
1405 const DataLayout &DL = Alloca->getDataLayout();
1406 if (std::optional<TypeSize> AllocaSize =
1407 Alloca->getAllocationSize(DL))
1408 if (*AllocaSize == LTSize->getValue())
1409 return true;
1410 }
1411 }
1412 }
1413 }
1414
1415 return false;
1416}
1417
1418/// Transform memcpy to memset when its source was just memset.
1419/// In other words, turn:
1420/// \code
1421/// memset(dst1, c, dst1_size);
1422/// memcpy(dst2, dst1, dst2_size);
1423/// \endcode
1424/// into:
1425/// \code
1426/// memset(dst1, c, dst1_size);
1427/// memset(dst2, c, dst2_size);
1428/// \endcode
1429/// When dst2_size <= dst1_size.
1430bool MemCpyOptPass::performMemCpyToMemSetOptzn(MemCpyInst *MemCpy,
1431 MemSetInst *MemSet,
1432 BatchAAResults &BAA) {
1433 // Make sure that memcpy(..., memset(...), ...), that is we are memsetting and
1434 // memcpying from the same address. Otherwise it is hard to reason about.
1435 if (!BAA.isMustAlias(MemSet->getRawDest(), MemCpy->getRawSource()))
1436 return false;
1437
1438 Value *MemSetSize = MemSet->getLength();
1439 Value *CopySize = MemCpy->getLength();
1440
1441 if (MemSetSize != CopySize) {
1442 // Make sure the memcpy doesn't read any more than what the memset wrote.
1443 // Don't worry about sizes larger than i64.
1444
1445 // A known memset size is required.
1446 auto *CMemSetSize = dyn_cast<ConstantInt>(MemSetSize);
1447 if (!CMemSetSize)
1448 return false;
1449
1450 // A known memcpy size is also required.
1451 auto *CCopySize = dyn_cast<ConstantInt>(CopySize);
1452 if (!CCopySize)
1453 return false;
1454 if (CCopySize->getZExtValue() > CMemSetSize->getZExtValue()) {
1455 // If the memcpy is larger than the memset, but the memory was undef prior
1456 // to the memset, we can just ignore the tail. Technically we're only
1457 // interested in the bytes from MemSetSize..CopySize here, but as we can't
1458 // easily represent this location, we use the full 0..CopySize range.
1459 MemoryLocation MemCpyLoc = MemoryLocation::getForSource(MemCpy);
1460 bool CanReduceSize = false;
1461 MemoryUseOrDef *MemSetAccess = MSSA->getMemoryAccess(MemSet);
1463 MemSetAccess->getDefiningAccess(), MemCpyLoc, BAA);
1464 if (auto *MD = dyn_cast<MemoryDef>(Clobber))
1465 if (hasUndefContents(MSSA, BAA, MemCpy->getSource(), MD, CopySize))
1466 CanReduceSize = true;
1467
1468 if (!CanReduceSize)
1469 return false;
1470 CopySize = MemSetSize;
1471 }
1472 }
1473
1474 IRBuilder<> Builder(MemCpy);
1475 Instruction *NewM =
1476 Builder.CreateMemSet(MemCpy->getRawDest(), MemSet->getOperand(1),
1477 CopySize, MemCpy->getDestAlign());
1478 auto *LastDef =
1479 cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy));
1480 auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM, nullptr, LastDef);
1481 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
1482
1483 return true;
1484}
1485
1486// Attempts to optimize the pattern whereby memory is copied from an alloca to
1487// another alloca, where the two allocas don't have conflicting mod/ref. If
1488// successful, the two allocas can be merged into one and the transfer can be
1489// deleted. This pattern is generated frequently in Rust, due to the ubiquity of
1490// move operations in that language.
1491//
1492// Once we determine that the optimization is safe to perform, we replace all
1493// uses of the destination alloca with the source alloca. We also "shrink wrap"
1494// the lifetime markers of the single merged alloca to before the first use
1495// and after the last use. Note that the "shrink wrapping" procedure is a safe
1496// transformation only because we restrict the scope of this optimization to
1497// allocas that aren't captured.
1498bool MemCpyOptPass::performStackMoveOptzn(Instruction *Load, Instruction *Store,
1499 AllocaInst *DestAlloca,
1500 AllocaInst *SrcAlloca, TypeSize Size,
1501 BatchAAResults &BAA) {
1502 LLVM_DEBUG(dbgs() << "Stack Move: Attempting to optimize:\n"
1503 << *Store << "\n");
1504
1505 // Make sure the two allocas are in the same address space.
1506 if (SrcAlloca->getAddressSpace() != DestAlloca->getAddressSpace()) {
1507 LLVM_DEBUG(dbgs() << "Stack Move: Address space mismatch\n");
1508 return false;
1509 }
1510
1511 // Check that copy is full with static size.
1512 const DataLayout &DL = DestAlloca->getDataLayout();
1513 std::optional<TypeSize> SrcSize = SrcAlloca->getAllocationSize(DL);
1514 if (!SrcSize || Size != *SrcSize) {
1515 LLVM_DEBUG(dbgs() << "Stack Move: Source alloca size mismatch\n");
1516 return false;
1517 }
1518 std::optional<TypeSize> DestSize = DestAlloca->getAllocationSize(DL);
1519 if (!DestSize || Size != *DestSize) {
1520 LLVM_DEBUG(dbgs() << "Stack Move: Destination alloca size mismatch\n");
1521 return false;
1522 }
1523
1524 if (!SrcAlloca->isStaticAlloca() || !DestAlloca->isStaticAlloca())
1525 return false;
1526
1527 // Check that src and dest are never captured, unescaped allocas. Also
1528 // find the nearest common dominator and postdominator for all users in
1529 // order to shrink wrap the lifetimes, and instructions with noalias metadata
1530 // to remove them.
1531
1532 SmallVector<Instruction *, 4> LifetimeMarkers;
1533 SmallSet<Instruction *, 4> NoAliasInstrs;
1534 bool SrcNotDom = false;
1535
1536 // Recursively track the user and check whether modified alias exist.
1537 auto IsDereferenceableOrNull = [](Value *V, const DataLayout &DL) -> bool {
1538 bool CanBeNull, CanBeFreed;
1539 return V->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
1540 };
1541
1542 auto CaptureTrackingWithModRef =
1543 [&](Instruction *AI,
1544 function_ref<bool(Instruction *)> ModRefCallback) -> bool {
1546 Worklist.push_back(AI);
1547 unsigned MaxUsesToExplore = getDefaultMaxUsesToExploreForCaptureTracking();
1548 Worklist.reserve(MaxUsesToExplore);
1550 while (!Worklist.empty()) {
1551 Instruction *I = Worklist.back();
1552 Worklist.pop_back();
1553 for (const Use &U : I->uses()) {
1554 auto *UI = cast<Instruction>(U.getUser());
1555 // If any use that isn't dominated by SrcAlloca exists, we move src
1556 // alloca to the entry before the transformation.
1557 if (!DT->dominates(SrcAlloca, UI))
1558 SrcNotDom = true;
1559
1560 if (Visited.size() >= MaxUsesToExplore) {
1561 LLVM_DEBUG(
1562 dbgs()
1563 << "Stack Move: Exceeded max uses to see ModRef, bailing\n");
1564 return false;
1565 }
1566 if (!Visited.insert(&U).second)
1567 continue;
1568 switch (DetermineUseCaptureKind(U, IsDereferenceableOrNull)) {
1570 return false;
1572 // Instructions cannot have non-instruction users.
1573 Worklist.push_back(UI);
1574 continue;
1576 if (UI->isLifetimeStartOrEnd()) {
1577 // We note the locations of these intrinsic calls so that we can
1578 // delete them later if the optimization succeeds, this is safe
1579 // since both llvm.lifetime.start and llvm.lifetime.end intrinsics
1580 // practically fill all the bytes of the alloca with an undefined
1581 // value, although conceptually marked as alive/dead.
1582 int64_t Size = cast<ConstantInt>(UI->getOperand(0))->getSExtValue();
1583 if (Size < 0 || Size == DestSize) {
1584 LifetimeMarkers.push_back(UI);
1585 continue;
1586 }
1587 }
1588 if (UI->hasMetadata(LLVMContext::MD_noalias))
1589 NoAliasInstrs.insert(UI);
1590 if (!ModRefCallback(UI))
1591 return false;
1592 }
1593 }
1594 }
1595 }
1596 return true;
1597 };
1598
1599 // Check that dest has no Mod/Ref, from the alloca to the Store, except full
1600 // size lifetime intrinsics. And collect modref inst for the reachability
1601 // check.
1602 ModRefInfo DestModRef = ModRefInfo::NoModRef;
1603 MemoryLocation DestLoc(DestAlloca, LocationSize::precise(Size));
1604 SmallVector<BasicBlock *, 8> ReachabilityWorklist;
1605 auto DestModRefCallback = [&](Instruction *UI) -> bool {
1606 // We don't care about the store itself.
1607 if (UI == Store)
1608 return true;
1609 ModRefInfo Res = BAA.getModRefInfo(UI, DestLoc);
1610 DestModRef |= Res;
1611 if (isModOrRefSet(Res)) {
1612 // Instructions reachability checks.
1613 // FIXME: adding the Instruction version isPotentiallyReachableFromMany on
1614 // lib/Analysis/CFG.cpp (currently only for BasicBlocks) might be helpful.
1615 if (UI->getParent() == Store->getParent()) {
1616 // The same block case is special because it's the only time we're
1617 // looking within a single block to see which instruction comes first.
1618 // Once we start looking at multiple blocks, the first instruction of
1619 // the block is reachable, so we only need to determine reachability
1620 // between whole blocks.
1621 BasicBlock *BB = UI->getParent();
1622
1623 // If A comes before B, then B is definitively reachable from A.
1624 if (UI->comesBefore(Store))
1625 return false;
1626
1627 // If the user's parent block is entry, no predecessor exists.
1628 if (BB->isEntryBlock())
1629 return true;
1630
1631 // Otherwise, continue doing the normal per-BB CFG walk.
1632 ReachabilityWorklist.append(succ_begin(BB), succ_end(BB));
1633 } else {
1634 ReachabilityWorklist.push_back(UI->getParent());
1635 }
1636 }
1637 return true;
1638 };
1639
1640 if (!CaptureTrackingWithModRef(DestAlloca, DestModRefCallback))
1641 return false;
1642 // Bailout if Dest may have any ModRef before Store.
1643 if (!ReachabilityWorklist.empty() &&
1644 isPotentiallyReachableFromMany(ReachabilityWorklist, Store->getParent(),
1645 nullptr, DT, nullptr))
1646 return false;
1647
1648 // Check that, from after the Load to the end of the BB,
1649 // - if the dest has any Mod, src has no Ref, and
1650 // - if the dest has any Ref, src has no Mod except full-sized lifetimes.
1651 MemoryLocation SrcLoc(SrcAlloca, LocationSize::precise(Size));
1652
1653 auto SrcModRefCallback = [&](Instruction *UI) -> bool {
1654 // Any ModRef post-dominated by Load doesn't matter, also Load and Store
1655 // themselves can be ignored.
1656 if (PDT->dominates(Load, UI) || UI == Load || UI == Store)
1657 return true;
1658 ModRefInfo Res = BAA.getModRefInfo(UI, SrcLoc);
1659 if ((isModSet(DestModRef) && isRefSet(Res)) ||
1660 (isRefSet(DestModRef) && isModSet(Res)))
1661 return false;
1662
1663 return true;
1664 };
1665
1666 if (!CaptureTrackingWithModRef(SrcAlloca, SrcModRefCallback))
1667 return false;
1668
1669 // We can do the transformation. First, move the SrcAlloca to the start of the
1670 // BB.
1671 if (SrcNotDom)
1672 SrcAlloca->moveBefore(*SrcAlloca->getParent(),
1673 SrcAlloca->getParent()->getFirstInsertionPt());
1674 // Align the allocas appropriately.
1675 SrcAlloca->setAlignment(
1676 std::max(SrcAlloca->getAlign(), DestAlloca->getAlign()));
1677
1678 // Merge the two allocas.
1679 DestAlloca->replaceAllUsesWith(SrcAlloca);
1680 eraseInstruction(DestAlloca);
1681
1682 // Drop metadata on the source alloca.
1683 SrcAlloca->dropUnknownNonDebugMetadata();
1684
1685 // TODO: Reconstruct merged lifetime markers.
1686 // Remove all other lifetime markers. if the original lifetime intrinsics
1687 // exists.
1688 if (!LifetimeMarkers.empty()) {
1689 for (Instruction *I : LifetimeMarkers)
1690 eraseInstruction(I);
1691 }
1692
1693 // As this transformation can cause memory accesses that didn't previously
1694 // alias to begin to alias one another, we remove !noalias metadata from any
1695 // uses of either alloca. This is conservative, but more precision doesn't
1696 // seem worthwhile right now.
1697 for (Instruction *I : NoAliasInstrs)
1698 I->setMetadata(LLVMContext::MD_noalias, nullptr);
1699
1700 LLVM_DEBUG(dbgs() << "Stack Move: Performed staack-move optimization\n");
1701 NumStackMove++;
1702 return true;
1703}
1704
1705static bool isZeroSize(Value *Size) {
1706 if (auto *I = dyn_cast<Instruction>(Size))
1707 if (auto *Res = simplifyInstruction(I, I->getDataLayout()))
1708 Size = Res;
1709 // Treat undef/poison size like zero.
1710 if (auto *C = dyn_cast<Constant>(Size))
1711 return isa<UndefValue>(C) || C->isNullValue();
1712 return false;
1713}
1714
1715/// Perform simplification of memcpy's. If we have memcpy A
1716/// which copies X to Y, and memcpy B which copies Y to Z, then we can rewrite
1717/// B to be a memcpy from X to Z (or potentially a memmove, depending on
1718/// circumstances). This allows later passes to remove the first memcpy
1719/// altogether.
1720bool MemCpyOptPass::processMemCpy(MemCpyInst *M, BasicBlock::iterator &BBI) {
1721 // We can only optimize non-volatile memcpy's.
1722 if (M->isVolatile())
1723 return false;
1724
1725 // If the source and destination of the memcpy are the same, then zap it.
1726 if (M->getSource() == M->getDest()) {
1727 ++BBI;
1728 eraseInstruction(M);
1729 return true;
1730 }
1731
1732 // If the size is zero, remove the memcpy.
1733 if (isZeroSize(M->getLength())) {
1734 ++BBI;
1735 eraseInstruction(M);
1736 return true;
1737 }
1738
1739 MemoryUseOrDef *MA = MSSA->getMemoryAccess(M);
1740 if (!MA)
1741 // Degenerate case: memcpy marked as not accessing memory.
1742 return false;
1743
1744 // If copying from a constant, try to turn the memcpy into a memset.
1745 if (auto *GV = dyn_cast<GlobalVariable>(M->getSource()))
1746 if (GV->isConstant() && GV->hasDefinitiveInitializer())
1747 if (Value *ByteVal = isBytewiseValue(GV->getInitializer(),
1748 M->getDataLayout())) {
1749 IRBuilder<> Builder(M);
1750 Instruction *NewM = Builder.CreateMemSet(
1751 M->getRawDest(), ByteVal, M->getLength(), M->getDestAlign(), false);
1752 auto *LastDef = cast<MemoryDef>(MA);
1753 auto *NewAccess =
1754 MSSAU->createMemoryAccessAfter(NewM, nullptr, LastDef);
1755 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
1756
1757 eraseInstruction(M);
1758 ++NumCpyToSet;
1759 return true;
1760 }
1761
1762 BatchAAResults BAA(*AA);
1763 // FIXME: Not using getClobberingMemoryAccess() here due to PR54682.
1764 MemoryAccess *AnyClobber = MA->getDefiningAccess();
1766 const MemoryAccess *DestClobber =
1767 MSSA->getWalker()->getClobberingMemoryAccess(AnyClobber, DestLoc, BAA);
1768
1769 // Try to turn a partially redundant memset + memcpy into
1770 // smaller memset + memcpy. We don't need the memcpy size for this.
1771 // The memcpy must post-dom the memset, so limit this to the same basic
1772 // block. A non-local generalization is likely not worthwhile.
1773 if (auto *MD = dyn_cast<MemoryDef>(DestClobber))
1774 if (auto *MDep = dyn_cast_or_null<MemSetInst>(MD->getMemoryInst()))
1775 if (DestClobber->getBlock() == M->getParent())
1776 if (processMemSetMemCpyDependence(M, MDep, BAA))
1777 return true;
1778
1779 MemoryAccess *SrcClobber = MSSA->getWalker()->getClobberingMemoryAccess(
1780 AnyClobber, MemoryLocation::getForSource(M), BAA);
1781
1782 // There are five possible optimizations we can do for memcpy:
1783 // a) memcpy-memcpy xform which exposes redundance for DSE.
1784 // b) call-memcpy xform for return slot optimization.
1785 // c) memcpy from freshly alloca'd space or space that has just started
1786 // its lifetime copies undefined data, and we can therefore eliminate
1787 // the memcpy in favor of the data that was already at the destination.
1788 // d) memcpy from a just-memset'd source can be turned into memset.
1789 // e) elimination of memcpy via stack-move optimization.
1790 if (auto *MD = dyn_cast<MemoryDef>(SrcClobber)) {
1791 if (Instruction *MI = MD->getMemoryInst()) {
1792 if (auto *CopySize = dyn_cast<ConstantInt>(M->getLength())) {
1793 if (auto *C = dyn_cast<CallInst>(MI)) {
1794 if (performCallSlotOptzn(M, M, M->getDest(), M->getSource(),
1795 TypeSize::getFixed(CopySize->getZExtValue()),
1796 M->getDestAlign().valueOrOne(), BAA,
1797 [C]() -> CallInst * { return C; })) {
1798 LLVM_DEBUG(dbgs() << "Performed call slot optimization:\n"
1799 << " call: " << *C << "\n"
1800 << " memcpy: " << *M << "\n");
1801 eraseInstruction(M);
1802 ++NumMemCpyInstr;
1803 return true;
1804 }
1805 }
1806 }
1807 if (auto *MDep = dyn_cast<MemCpyInst>(MI))
1808 if (processMemCpyMemCpyDependence(M, MDep, BAA))
1809 return true;
1810 if (auto *MDep = dyn_cast<MemSetInst>(MI)) {
1811 if (performMemCpyToMemSetOptzn(M, MDep, BAA)) {
1812 LLVM_DEBUG(dbgs() << "Converted memcpy to memset\n");
1813 eraseInstruction(M);
1814 ++NumCpyToSet;
1815 return true;
1816 }
1817 }
1818 }
1819
1820 if (hasUndefContents(MSSA, BAA, M->getSource(), MD, M->getLength())) {
1821 LLVM_DEBUG(dbgs() << "Removed memcpy from undef\n");
1822 eraseInstruction(M);
1823 ++NumMemCpyInstr;
1824 return true;
1825 }
1826 }
1827
1828 // If the transfer is from a stack slot to a stack slot, then we may be able
1829 // to perform the stack-move optimization. See the comments in
1830 // performStackMoveOptzn() for more details.
1831 auto *DestAlloca = dyn_cast<AllocaInst>(M->getDest());
1832 if (!DestAlloca)
1833 return false;
1834 auto *SrcAlloca = dyn_cast<AllocaInst>(M->getSource());
1835 if (!SrcAlloca)
1836 return false;
1837 ConstantInt *Len = dyn_cast<ConstantInt>(M->getLength());
1838 if (Len == nullptr)
1839 return false;
1840 if (performStackMoveOptzn(M, M, DestAlloca, SrcAlloca,
1841 TypeSize::getFixed(Len->getZExtValue()), BAA)) {
1842 // Avoid invalidating the iterator.
1843 BBI = M->getNextNonDebugInstruction()->getIterator();
1844 eraseInstruction(M);
1845 ++NumMemCpyInstr;
1846 return true;
1847 }
1848
1849 return false;
1850}
1851
1852/// Transforms memmove calls to memcpy calls when the src/dst are guaranteed
1853/// not to alias.
1854bool MemCpyOptPass::processMemMove(MemMoveInst *M) {
1855 // See if the source could be modified by this memmove potentially.
1857 return false;
1858
1859 LLVM_DEBUG(dbgs() << "MemCpyOptPass: Optimizing memmove -> memcpy: " << *M
1860 << "\n");
1861
1862 // If not, then we know we can transform this.
1863 Type *ArgTys[3] = {M->getRawDest()->getType(), M->getRawSource()->getType(),
1864 M->getLength()->getType()};
1865 M->setCalledFunction(
1866 Intrinsic::getDeclaration(M->getModule(), Intrinsic::memcpy, ArgTys));
1867
1868 // For MemorySSA nothing really changes (except that memcpy may imply stricter
1869 // aliasing guarantees).
1870
1871 ++NumMoveToCpy;
1872 return true;
1873}
1874
1875/// This is called on every byval argument in call sites.
1876bool MemCpyOptPass::processByValArgument(CallBase &CB, unsigned ArgNo) {
1877 const DataLayout &DL = CB.getDataLayout();
1878 // Find out what feeds this byval argument.
1879 Value *ByValArg = CB.getArgOperand(ArgNo);
1880 Type *ByValTy = CB.getParamByValType(ArgNo);
1881 TypeSize ByValSize = DL.getTypeAllocSize(ByValTy);
1882 MemoryLocation Loc(ByValArg, LocationSize::precise(ByValSize));
1883 MemoryUseOrDef *CallAccess = MSSA->getMemoryAccess(&CB);
1884 if (!CallAccess)
1885 return false;
1886 MemCpyInst *MDep = nullptr;
1887 BatchAAResults BAA(*AA);
1889 CallAccess->getDefiningAccess(), Loc, BAA);
1890 if (auto *MD = dyn_cast<MemoryDef>(Clobber))
1891 MDep = dyn_cast_or_null<MemCpyInst>(MD->getMemoryInst());
1892
1893 // If the byval argument isn't fed by a memcpy, ignore it. If it is fed by
1894 // a memcpy, see if we can byval from the source of the memcpy instead of the
1895 // result.
1896 if (!MDep || MDep->isVolatile() ||
1897 ByValArg->stripPointerCasts() != MDep->getDest())
1898 return false;
1899
1900 // The length of the memcpy must be larger or equal to the size of the byval.
1901 auto *C1 = dyn_cast<ConstantInt>(MDep->getLength());
1902 if (!C1 || !TypeSize::isKnownGE(
1903 TypeSize::getFixed(C1->getValue().getZExtValue()), ByValSize))
1904 return false;
1905
1906 // Get the alignment of the byval. If the call doesn't specify the alignment,
1907 // then it is some target specific value that we can't know.
1908 MaybeAlign ByValAlign = CB.getParamAlign(ArgNo);
1909 if (!ByValAlign)
1910 return false;
1911
1912 // If it is greater than the memcpy, then we check to see if we can force the
1913 // source of the memcpy to the alignment we need. If we fail, we bail out.
1914 MaybeAlign MemDepAlign = MDep->getSourceAlign();
1915 if ((!MemDepAlign || *MemDepAlign < *ByValAlign) &&
1916 getOrEnforceKnownAlignment(MDep->getSource(), ByValAlign, DL, &CB, AC,
1917 DT) < *ByValAlign)
1918 return false;
1919
1920 // The type of the memcpy source must match the byval argument
1921 if (MDep->getSource()->getType() != ByValArg->getType())
1922 return false;
1923
1924 // Verify that the copied-from memory doesn't change in between the memcpy and
1925 // the byval call.
1926 // memcpy(a <- b)
1927 // *b = 42;
1928 // foo(*a)
1929 // It would be invalid to transform the second memcpy into foo(*b).
1930 if (writtenBetween(MSSA, BAA, MemoryLocation::getForSource(MDep),
1931 MSSA->getMemoryAccess(MDep), CallAccess))
1932 return false;
1933
1934 LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n"
1935 << " " << *MDep << "\n"
1936 << " " << CB << "\n");
1937
1938 // Otherwise we're good! Update the byval argument.
1939 combineAAMetadata(&CB, MDep);
1940 CB.setArgOperand(ArgNo, MDep->getSource());
1941 ++NumMemCpyInstr;
1942 return true;
1943}
1944
1945/// This is called on memcpy dest pointer arguments attributed as immutable
1946/// during call. Try to use memcpy source directly if all of the following
1947/// conditions are satisfied.
1948/// 1. The memcpy dst is neither modified during the call nor captured by the
1949/// call. (if readonly, noalias, nocapture attributes on call-site.)
1950/// 2. The memcpy dst is an alloca with known alignment & size.
1951/// 2-1. The memcpy length == the alloca size which ensures that the new
1952/// pointer is dereferenceable for the required range
1953/// 2-2. The src pointer has alignment >= the alloca alignment or can be
1954/// enforced so.
1955/// 3. The memcpy dst and src is not modified between the memcpy and the call.
1956/// (if MSSA clobber check is safe.)
1957/// 4. The memcpy src is not modified during the call. (ModRef check shows no
1958/// Mod.)
1959bool MemCpyOptPass::processImmutArgument(CallBase &CB, unsigned ArgNo) {
1960 // 1. Ensure passed argument is immutable during call.
1961 if (!(CB.paramHasAttr(ArgNo, Attribute::NoAlias) &&
1962 CB.paramHasAttr(ArgNo, Attribute::NoCapture)))
1963 return false;
1964 const DataLayout &DL = CB.getDataLayout();
1965 Value *ImmutArg = CB.getArgOperand(ArgNo);
1966
1967 // 2. Check that arg is alloca
1968 // TODO: Even if the arg gets back to branches, we can remove memcpy if all
1969 // the alloca alignments can be enforced to source alignment.
1970 auto *AI = dyn_cast<AllocaInst>(ImmutArg->stripPointerCasts());
1971 if (!AI)
1972 return false;
1973
1974 std::optional<TypeSize> AllocaSize = AI->getAllocationSize(DL);
1975 // Can't handle unknown size alloca.
1976 // (e.g. Variable Length Array, Scalable Vector)
1977 if (!AllocaSize || AllocaSize->isScalable())
1978 return false;
1979 MemoryLocation Loc(ImmutArg, LocationSize::precise(*AllocaSize));
1980 MemoryUseOrDef *CallAccess = MSSA->getMemoryAccess(&CB);
1981 if (!CallAccess)
1982 return false;
1983
1984 MemCpyInst *MDep = nullptr;
1985 BatchAAResults BAA(*AA);
1987 CallAccess->getDefiningAccess(), Loc, BAA);
1988 if (auto *MD = dyn_cast<MemoryDef>(Clobber))
1989 MDep = dyn_cast_or_null<MemCpyInst>(MD->getMemoryInst());
1990
1991 // If the immut argument isn't fed by a memcpy, ignore it. If it is fed by
1992 // a memcpy, check that the arg equals the memcpy dest.
1993 if (!MDep || MDep->isVolatile() || AI != MDep->getDest())
1994 return false;
1995
1996 // The type of the memcpy source must match the immut argument
1997 if (MDep->getSource()->getType() != ImmutArg->getType())
1998 return false;
1999
2000 // 2-1. The length of the memcpy must be equal to the size of the alloca.
2001 auto *MDepLen = dyn_cast<ConstantInt>(MDep->getLength());
2002 if (!MDepLen || AllocaSize != MDepLen->getValue())
2003 return false;
2004
2005 // 2-2. the memcpy source align must be larger than or equal the alloca's
2006 // align. If not so, we check to see if we can force the source of the memcpy
2007 // to the alignment we need. If we fail, we bail out.
2008 Align MemDepAlign = MDep->getSourceAlign().valueOrOne();
2009 Align AllocaAlign = AI->getAlign();
2010 if (MemDepAlign < AllocaAlign &&
2011 getOrEnforceKnownAlignment(MDep->getSource(), AllocaAlign, DL, &CB, AC,
2012 DT) < AllocaAlign)
2013 return false;
2014
2015 // 3. Verify that the source doesn't change in between the memcpy and
2016 // the call.
2017 // memcpy(a <- b)
2018 // *b = 42;
2019 // foo(*a)
2020 // It would be invalid to transform the second memcpy into foo(*b).
2021 if (writtenBetween(MSSA, BAA, MemoryLocation::getForSource(MDep),
2022 MSSA->getMemoryAccess(MDep), CallAccess))
2023 return false;
2024
2025 // 4. The memcpy src must not be modified during the call.
2027 return false;
2028
2029 LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy to Immut src:\n"
2030 << " " << *MDep << "\n"
2031 << " " << CB << "\n");
2032
2033 // Otherwise we're good! Update the immut argument.
2034 combineAAMetadata(&CB, MDep);
2035 CB.setArgOperand(ArgNo, MDep->getSource());
2036 ++NumMemCpyInstr;
2037 return true;
2038}
2039
2040/// Executes one iteration of MemCpyOptPass.
2041bool MemCpyOptPass::iterateOnFunction(Function &F) {
2042 bool MadeChange = false;
2043
2044 // Walk all instruction in the function.
2045 for (BasicBlock &BB : F) {
2046 // Skip unreachable blocks. For example processStore assumes that an
2047 // instruction in a BB can't be dominated by a later instruction in the
2048 // same BB (which is a scenario that can happen for an unreachable BB that
2049 // has itself as a predecessor).
2050 if (!DT->isReachableFromEntry(&BB))
2051 continue;
2052
2053 for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) {
2054 // Avoid invalidating the iterator.
2055 Instruction *I = &*BI++;
2056
2057 bool RepeatInstruction = false;
2058
2059 if (auto *SI = dyn_cast<StoreInst>(I))
2060 MadeChange |= processStore(SI, BI);
2061 else if (auto *M = dyn_cast<MemSetInst>(I))
2062 RepeatInstruction = processMemSet(M, BI);
2063 else if (auto *M = dyn_cast<MemCpyInst>(I))
2064 RepeatInstruction = processMemCpy(M, BI);
2065 else if (auto *M = dyn_cast<MemMoveInst>(I))
2066 RepeatInstruction = processMemMove(M);
2067 else if (auto *CB = dyn_cast<CallBase>(I)) {
2068 for (unsigned i = 0, e = CB->arg_size(); i != e; ++i) {
2069 if (CB->isByValArgument(i))
2070 MadeChange |= processByValArgument(*CB, i);
2071 else if (CB->onlyReadsMemory(i))
2072 MadeChange |= processImmutArgument(*CB, i);
2073 }
2074 }
2075
2076 // Reprocess the instruction if desired.
2077 if (RepeatInstruction) {
2078 if (BI != BB.begin())
2079 --BI;
2080 MadeChange = true;
2081 }
2082 }
2083 }
2084
2085 return MadeChange;
2086}
2087
2089 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
2090 auto *AA = &AM.getResult<AAManager>(F);
2091 auto *AC = &AM.getResult<AssumptionAnalysis>(F);
2092 auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
2093 auto *PDT = &AM.getResult<PostDominatorTreeAnalysis>(F);
2094 auto *MSSA = &AM.getResult<MemorySSAAnalysis>(F);
2095
2096 bool MadeChange = runImpl(F, &TLI, AA, AC, DT, PDT, &MSSA->getMSSA());
2097 if (!MadeChange)
2098 return PreservedAnalyses::all();
2099
2103 return PA;
2104}
2105
2107 AliasAnalysis *AA_, AssumptionCache *AC_,
2108 DominatorTree *DT_, PostDominatorTree *PDT_,
2109 MemorySSA *MSSA_) {
2110 bool MadeChange = false;
2111 TLI = TLI_;
2112 AA = AA_;
2113 AC = AC_;
2114 DT = DT_;
2115 PDT = PDT_;
2116 MSSA = MSSA_;
2117 MemorySSAUpdater MSSAU_(MSSA_);
2118 MSSAU = &MSSAU_;
2119
2120 while (true) {
2121 if (!iterateOnFunction(F))
2122 break;
2123 MadeChange = true;
2124 }
2125
2126 if (VerifyMemorySSA)
2127 MSSA_->verifyMemorySSA();
2128
2129 return MadeChange;
2130}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseSet and SmallDenseSet classes.
uint64_t Size
bool End
Definition: ELF_riscv.cpp:480
This is the interface for a simple mod/ref and alias analysis over globals.
Hexagon Common GEP
IRTranslator LLVM IR MI
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
static bool mayBeVisibleThroughUnwinding(Value *V, Instruction *Start, Instruction *End)
static bool isZeroSize(Value *Size)
static void combineAAMetadata(Instruction *ReplInst, Instruction *I)
static bool accessedBetween(BatchAAResults &AA, MemoryLocation Loc, const MemoryUseOrDef *Start, const MemoryUseOrDef *End, Instruction **SkippedLifetimeStart=nullptr)
static bool hasUndefContents(MemorySSA *MSSA, BatchAAResults &AA, Value *V, MemoryDef *Def, Value *Size)
Determine whether the instruction has undefined content for the given Size, either because it was fre...
static cl::opt< bool > EnableMemCpyOptWithoutLibcalls("enable-memcpyopt-without-libcalls", cl::Hidden, cl::desc("Enable memcpyopt even when libcalls are disabled"))
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)
Definition: Metadata.cpp:1274
Module.h This file contains the declarations for the Module class.
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
#define P(N)
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
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:166
A manager for alias analyses.
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
Class for arbitrary precision integers.
Definition: APInt.h:78
an instruction to allocate memory on the stack
Definition: Instructions.h:61
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.
Definition: Instructions.h:122
unsigned getAddressSpace() const
Return the address space for the allocation.
Definition: Instructions.h:102
std::optional< TypeSize > getAllocationSize(const DataLayout &DL) const
Get allocation size in bytes.
void setAlignment(Align Align)
Definition: Instructions.h:126
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:405
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
iterator end()
Definition: BasicBlock.h:461
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:448
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
Definition: BasicBlock.cpp:571
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:219
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:177
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:72
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1236
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.
Definition: InstrTypes.h:1774
MaybeAlign getParamAlign(unsigned ArgNo) const
Extract the alignment for a call or parameter (0=unknown).
Definition: InstrTypes.h:1838
bool onlyReadsMemory(unsigned OpNo) const
Definition: InstrTypes.h:1816
Type * getParamByValType(unsigned ArgNo) const
Extract the byval type for a call or parameter.
Definition: InstrTypes.h:1856
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1410
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1415
unsigned arg_size() const
Definition: InstrTypes.h:1408
This class represents a function call, abstracting a target machine's calling convention.
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:155
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:370
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:63
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:321
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2686
void mergeDIAssignID(ArrayRef< const Instruction * > SourceInstructions)
Merge the DIAssignID metadata from this instruction and those attached to instructions in SourceInstr...
Definition: DebugInfo.cpp:936
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:466
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:92
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs=std::nullopt)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1596
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:463
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
Definition: Instruction.cpp:74
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
An instruction for reading from memory.
Definition: Instructions.h:174
Value * getPointerOperand()
Definition: Instructions.h:253
bool isSimple() const
Definition: Instructions.h:245
Align getAlign() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:209
static LocationSize precise(uint64_t Value)
This class wraps the llvm.memcpy intrinsic.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
bool runImpl(Function &F, TargetLibraryInfo *TLI, AAResults *AA, AssumptionCache *AC, DominatorTree *DT, PostDominatorTree *PDT, MemorySSA *MSSA)
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
bool isVolatile() const
This class wraps the llvm.memmove intrinsic.
Value * getValue() const
This class wraps the llvm.memset and llvm.memset.inline intrinsics.
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:161
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.
MemoryLocation getWithNewSize(LocationSize NewSize) const
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static MemoryLocation getForSource(const MemTransferInst *MTI)
Return a location representing the source of a memory transfer.
static 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:924
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
MemoryUseOrDef * createMemoryAccessBefore(Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt)
Create a MemoryAccess in MemorySSA before an existing MemoryAccess.
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where)
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
MemoryUseOrDef * createMemoryAccessAfter(Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt)
Create a MemoryAccess in MemorySSA after an existing MemoryAccess.
void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where)
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:1041
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:697
bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
Definition: MemorySSA.cpp:2173
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1905
MemorySSAWalker * getWalker()
Definition: MemorySSA.cpp:1590
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:715
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition: MemorySSA.h:735
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:249
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Definition: MemorySSA.h:259
Instruction * getMemoryInst() const
Get the instruction that this MemoryUse represents.
Definition: MemorySSA.h:256
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:146
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:131
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
size_type size() const
Definition: SmallSet.h:161
bool empty() const
Definition: SmallVector.h:94
void reserve(size_type N)
Definition: SmallVector.h:676
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:591
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:696
typename SuperClass::iterator iterator
Definition: SmallVector.h:590
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
An instruction for storing to memory.
Definition: Instructions.h:290
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
bool has(LibFunc F) const
Tests whether a library function is available.
static constexpr TypeSize getFixed(ScalarTy ExactSize)
Definition: TypeSize.h:345
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
unsigned getIntegerBitWidth() const
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:343
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:694
bool use_empty() const
Definition: Value.h:344
constexpr ScalarTy getFixedValue() const
Definition: TypeSize.h:202
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
Definition: TypeSize.h:171
static constexpr bool isKnownGE(const FixedOrScalableQuantity &LHS, const FixedOrScalableQuantity &RHS)
Definition: TypeSize.h:239
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
Definition: ilist_node.h:32
reverse_self_iterator getReverseIterator()
Definition: ilist_node.h:135
self_iterator getIterator()
Definition: ilist_node.h:132
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1539
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:227
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:236
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:480
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
bool isPotentiallyReachableFromMany(SmallVectorImpl< BasicBlock * > &Worklist, const BasicBlock *StopBB, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether there is at least one path from a block in 'Worklist' to 'StopBB' without passing t...
Definition: CFG.cpp:239
bool isDereferenceableAndAlignedPointer(const Value *V, Type *Ty, Align Alignment, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Returns true if V is always a dereferenceable pointer with alignment greater or equal than requested.
Definition: Loads.cpp:201
UseCaptureKind DetermineUseCaptureKind(const Use &U, llvm::function_ref< bool(Value *, const DataLayout &)> IsDereferenceableOrNull)
Determine what kind of capture behaviour U may exhibit.
auto partition_point(R &&Range, Predicate P)
Binary search for the first iterator in a range where a predicate is false.
Definition: STLExtras.h:2033
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, 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...
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2098
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
unsigned getDefaultMaxUsesToExploreForCaptureTracking()
getDefaultMaxUsesToExploreForCaptureTracking - Return default value of the maximal number of uses to ...
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
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:1729
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
Align getOrEnforceKnownAlignment(Value *V, MaybeAlign PrefAlign, const DataLayout &DL, const Instruction *CxtI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr)
Try to ensure that the alignment of V is at least PrefAlign bytes.
Definition: Local.cpp:1541
bool isModSet(const ModRefInfo MRI)
Definition: ModRef.h:48
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool isModOrRefSet(const ModRefInfo MRI)
Definition: ModRef.h:42
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...
void combineMetadata(Instruction *K, const Instruction *J, ArrayRef< unsigned > KnownIDs, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:3239
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:27
@ NoModRef
The access neither references nor modifies the value stored in memory.
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:84
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
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:565
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:212
bool isRefSet(const ModRefInfo MRI)
Definition: ModRef.h:51
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 ...
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition: Alignment.h:117
Align valueOrOne() const
For convenience, returns a valid alignment or 1 if undefined.
Definition: Alignment.h:141