1//===- DeadStoreElimination.cpp - MemorySSA Backed Dead Store Elimination -===//
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// The code below implements dead store elimination using MemorySSA. It uses
10// the following general approach: given a MemoryDef, walk upwards to find
11// clobbering MemoryDefs that may be killed by the starting def. Then check
12// that there are no uses that may read the location of the original MemoryDef
13// in between both MemoryDefs. A bit more concretely:
14//
15// For all MemoryDefs StartDef:
16// 1. Get the next dominating clobbering MemoryDef (MaybeDeadAccess) by walking
17// upwards.
18// 2. Check that there are no reads between MaybeDeadAccess and the StartDef by
19// checking all uses starting at MaybeDeadAccess and walking until we see
20// StartDef.
21// 3. For each found CurrentDef, check that:
22// 1. There are no barrier instructions between CurrentDef and StartDef (like
23// throws or stores with ordering constraints).
24// 2. StartDef is executed whenever CurrentDef is executed.
25// 3. StartDef completely overwrites CurrentDef.
26// 4. Erase CurrentDef from the function and MemorySSA.
27//
28//===----------------------------------------------------------------------===//
29
30#include "llvm/Transforms/Scalar/DeadStoreElimination.h"
31#include "ScalarOptions.h"
32#include "llvm/ADT/APInt.h"
33#include "llvm/ADT/DenseMap.h"
34#include "llvm/ADT/MapVector.h"
35#include "llvm/ADT/PostOrderIterator.h"
36#include "llvm/ADT/STLExtras.h"
37#include "llvm/ADT/ScopedHashTable.h"
38#include "llvm/ADT/SetVector.h"
39#include "llvm/ADT/SmallPtrSet.h"
40#include "llvm/ADT/SmallVector.h"
41#include "llvm/ADT/Statistic.h"
42#include "llvm/ADT/StringRef.h"
43#include "llvm/Analysis/AliasAnalysis.h"
44#include "llvm/Analysis/AssumptionCache.h"
45#include "llvm/Analysis/CaptureTracking.h"
46#include "llvm/Analysis/CycleAnalysis.h"
47#include "llvm/Analysis/GlobalsModRef.h"
48#include "llvm/Analysis/Loads.h"
49#include "llvm/Analysis/MemoryBuiltins.h"
50#include "llvm/Analysis/MemoryLocation.h"
51#include "llvm/Analysis/MemorySSA.h"
52#include "llvm/Analysis/MemorySSAUpdater.h"
53#include "llvm/Analysis/MustExecute.h"
54#include "llvm/Analysis/PostDominators.h"
55#include "llvm/Analysis/TargetLibraryInfo.h"
56#include "llvm/Analysis/ValueTracking.h"
57#include "llvm/IR/Argument.h"
58#include "llvm/IR/AttributeMask.h"
59#include "llvm/IR/BasicBlock.h"
60#include "llvm/IR/Constant.h"
61#include "llvm/IR/ConstantRangeList.h"
62#include "llvm/IR/Constants.h"
63#include "llvm/IR/DataLayout.h"
64#include "llvm/IR/DebugInfo.h"
65#include "llvm/IR/Dominators.h"
66#include "llvm/IR/Function.h"
67#include "llvm/IR/IRBuilder.h"
68#include "llvm/IR/InstIterator.h"
69#include "llvm/IR/InstrTypes.h"
70#include "llvm/IR/Instruction.h"
71#include "llvm/IR/Instructions.h"
72#include "llvm/IR/IntrinsicInst.h"
73#include "llvm/IR/Module.h"
74#include "llvm/IR/PassManager.h"
75#include "llvm/IR/PatternMatch.h"
76#include "llvm/IR/Value.h"
77#include "llvm/InitializePasses.h"
78#include "llvm/Support/Casting.h"
79#include "llvm/Support/Debug.h"
80#include "llvm/Support/DebugCounter.h"
81#include "llvm/Support/ErrorHandling.h"
82#include "llvm/Support/raw_ostream.h"
83#include "llvm/Transforms/Scalar.h"
84#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
85#include "llvm/Transforms/Utils/BuildLibCalls.h"
86#include "llvm/Transforms/Utils/Local.h"
87#include <algorithm>
88#include <cassert>
89#include <cstdint>
90#include <map>
91#include <optional>
92#include <utility>
93
94using namespace llvm;
95using namespace PatternMatch;
96
97#define DEBUG_TYPE "dse"
98
99STATISTIC(NumRemainingStores, "Number of stores remaining after DSE");
100STATISTIC(NumRedundantStores, "Number of redundant stores deleted");
101STATISTIC(NumFastStores, "Number of stores deleted");
102STATISTIC(NumFastOther, "Number of other instrs removed");
103STATISTIC(NumCompletePartials, "Number of stores dead by later partials");
104STATISTIC(NumModifiedStores, "Number of stores modified");
105STATISTIC(NumCFGChecks, "Number of stores modified");
106STATISTIC(NumCFGTries, "Number of stores modified");
107STATISTIC(NumCFGSuccess, "Number of stores modified");
108STATISTIC(NumGetDomMemoryDefPassed,
109 "Number of times a valid candidate is returned from getDomMemoryDef");
110STATISTIC(NumDomMemDefChecks,
111 "Number iterations check for reads in getDomMemoryDef");
112
113DEBUG_COUNTER(MemorySSACounter, "dse-memoryssa",
114 "Controls which MemoryDefs are eliminated.");
115
116//===----------------------------------------------------------------------===//
117// Helper functions
118//===----------------------------------------------------------------------===//
119using OverlapIntervalsTy = std::map<int64_t, int64_t>;
120using InstOverlapIntervalsTy = MapVector<Instruction *, OverlapIntervalsTy>;
121
122/// Returns true if the end of this instruction can be safely shortened in
123/// length.
124static bool isShortenableAtTheEnd(Instruction *I) {
125 // Don't shorten stores for now
126 if (isa<StoreInst>(Val: I))
127 return false;
128
129 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: I)) {
130 switch (II->getIntrinsicID()) {
131 default: return false;
132 case Intrinsic::memset:
133 case Intrinsic::memcpy:
134 case Intrinsic::memcpy_element_unordered_atomic:
135 case Intrinsic::memset_element_unordered_atomic:
136 // Do shorten memory intrinsics.
137 // FIXME: Add memmove if it's also safe to transform.
138 return true;
139 }
140 }
141
142 // Don't shorten libcalls calls for now.
143
144 return false;
145}
146
147/// Returns true if the beginning of this instruction can be safely shortened
148/// in length.
149static bool isShortenableAtTheBeginning(Instruction *I) {
150 // FIXME: Handle only memset for now. Supporting memcpy/memmove should be
151 // easily done by offsetting the source address.
152 return isa<AnyMemSetInst>(Val: I);
153}
154
155static std::optional<TypeSize> getPointerSize(const Value *V,
156 const DataLayout &DL,
157 const TargetLibraryInfo &TLI,
158 const Function *F) {
159 uint64_t Size;
160 ObjectSizeOpts Opts;
161 Opts.NullIsUnknownSize = NullPointerIsDefined(F);
162
163 if (getObjectSize(Ptr: V, Size, DL, TLI: &TLI, Opts))
164 return TypeSize::getFixed(ExactSize: Size);
165 return std::nullopt;
166}
167
168namespace {
169
170enum OverwriteResult {
171 OW_Begin,
172 OW_Complete,
173 OW_End,
174 OW_PartialEarlierWithFullLater,
175 OW_MaybePartial,
176 OW_None,
177 OW_Unknown
178};
179
180} // end anonymous namespace
181
182/// Check if two instruction are masked stores that completely
183/// overwrite one another. More specifically, \p KillingI has to
184/// overwrite \p DeadI.
185static OverwriteResult isMaskedStoreOverwrite(const Instruction *KillingI,
186 const Instruction *DeadI,
187 BatchAAResults &AA) {
188 const auto *KillingII = dyn_cast<IntrinsicInst>(Val: KillingI);
189 const auto *DeadII = dyn_cast<IntrinsicInst>(Val: DeadI);
190 if (KillingII == nullptr || DeadII == nullptr)
191 return OW_Unknown;
192 if (KillingII->getIntrinsicID() != DeadII->getIntrinsicID())
193 return OW_Unknown;
194
195 switch (KillingII->getIntrinsicID()) {
196 case Intrinsic::masked_store:
197 case Intrinsic::vp_store: {
198 const DataLayout &DL = KillingII->getDataLayout();
199 auto *KillingTy = KillingII->getArgOperand(i: 0)->getType();
200 auto *DeadTy = DeadII->getArgOperand(i: 0)->getType();
201 if (DL.getTypeSizeInBits(Ty: KillingTy) != DL.getTypeSizeInBits(Ty: DeadTy))
202 return OW_Unknown;
203 // Element count.
204 if (cast<VectorType>(Val: KillingTy)->getElementCount() !=
205 cast<VectorType>(Val: DeadTy)->getElementCount())
206 return OW_Unknown;
207 // Pointers.
208 Value *KillingPtr = KillingII->getArgOperand(i: 1);
209 Value *DeadPtr = DeadII->getArgOperand(i: 1);
210 if (KillingPtr != DeadPtr && !AA.isMustAlias(V1: KillingPtr, V2: DeadPtr))
211 return OW_Unknown;
212 if (KillingII->getIntrinsicID() == Intrinsic::masked_store) {
213 // Masks.
214 // TODO: check that KillingII's mask is a superset of the DeadII's mask.
215 if (KillingII->getArgOperand(i: 2) != DeadII->getArgOperand(i: 2))
216 return OW_Unknown;
217 } else if (KillingII->getIntrinsicID() == Intrinsic::vp_store) {
218 // Masks.
219 // TODO: check that KillingII's mask is a superset of the DeadII's mask.
220 if (KillingII->getArgOperand(i: 2) != DeadII->getArgOperand(i: 2))
221 return OW_Unknown;
222 // Lengths.
223 if (KillingII->getArgOperand(i: 3) != DeadII->getArgOperand(i: 3))
224 return OW_Unknown;
225 }
226 return OW_Complete;
227 }
228 default:
229 return OW_Unknown;
230 }
231}
232
233/// Return 'OW_Complete' if a store to the 'KillingLoc' location completely
234/// overwrites a store to the 'DeadLoc' location, 'OW_End' if the end of the
235/// 'DeadLoc' location is completely overwritten by 'KillingLoc', 'OW_Begin'
236/// if the beginning of the 'DeadLoc' location is overwritten by 'KillingLoc'.
237/// 'OW_PartialEarlierWithFullLater' means that a dead (big) store was
238/// overwritten by a killing (smaller) store which doesn't write outside the big
239/// store's memory locations. Returns 'OW_Unknown' if nothing can be determined.
240/// NOTE: This function must only be called if both \p KillingLoc and \p
241/// DeadLoc belong to the same underlying object with valid \p KillingOff and
242/// \p DeadOff.
243static OverwriteResult isPartialOverwrite(const ScalarOptions &Opts,
244 const MemoryLocation &KillingLoc,
245 const MemoryLocation &DeadLoc,
246 int64_t KillingOff, int64_t DeadOff,
247 Instruction *DeadI,
248 InstOverlapIntervalsTy &IOL) {
249 const uint64_t KillingSize = KillingLoc.Size.getValue();
250 const uint64_t DeadSize = DeadLoc.Size.getValue();
251 // We may now overlap, although the overlap is not complete. There might also
252 // be other incomplete overlaps, and together, they might cover the complete
253 // dead store.
254 // Note: The correctness of this logic depends on the fact that this function
255 // is not even called providing DepWrite when there are any intervening reads.
256 if (Opts.enable_dse_partial_overwrite_tracking &&
257 KillingOff < int64_t(DeadOff + DeadSize) &&
258 int64_t(KillingOff + KillingSize) >= DeadOff) {
259
260 // Insert our part of the overlap into the map.
261 auto &IM = IOL[DeadI];
262 LLVM_DEBUG(dbgs() << "DSE: Partial overwrite: DeadLoc [" << DeadOff << ", "
263 << int64_t(DeadOff + DeadSize) << ") KillingLoc ["
264 << KillingOff << ", " << int64_t(KillingOff + KillingSize)
265 << ")\n");
266
267 // Make sure that we only insert non-overlapping intervals and combine
268 // adjacent intervals. The intervals are stored in the map with the ending
269 // offset as the key (in the half-open sense) and the starting offset as
270 // the value.
271 int64_t KillingIntStart = KillingOff;
272 int64_t KillingIntEnd = KillingOff + KillingSize;
273
274 // Find any intervals ending at, or after, KillingIntStart which start
275 // before KillingIntEnd.
276 auto ILI = IM.lower_bound(x: KillingIntStart);
277 if (ILI != IM.end() && ILI->second <= KillingIntEnd) {
278 // This existing interval is overlapped with the current store somewhere
279 // in [KillingIntStart, KillingIntEnd]. Merge them by erasing the existing
280 // intervals and adjusting our start and end.
281 KillingIntStart = std::min(a: KillingIntStart, b: ILI->second);
282 KillingIntEnd = std::max(a: KillingIntEnd, b: ILI->first);
283 ILI = IM.erase(position: ILI);
284
285 // Continue erasing and adjusting our end in case other previous
286 // intervals are also overlapped with the current store.
287 //
288 // |--- dead 1 ---| |--- dead 2 ---|
289 // |------- killing---------|
290 //
291 while (ILI != IM.end() && ILI->second <= KillingIntEnd) {
292 assert(ILI->second > KillingIntStart && "Unexpected interval");
293 KillingIntEnd = std::max(a: KillingIntEnd, b: ILI->first);
294 ILI = IM.erase(position: ILI);
295 }
296 }
297
298 IM[KillingIntEnd] = KillingIntStart;
299
300 ILI = IM.begin();
301 if (ILI->second <= DeadOff && ILI->first >= int64_t(DeadOff + DeadSize)) {
302 LLVM_DEBUG(dbgs() << "DSE: Full overwrite from partials: DeadLoc ["
303 << DeadOff << ", " << int64_t(DeadOff + DeadSize)
304 << ") Composite KillingLoc [" << ILI->second << ", "
305 << ILI->first << ")\n");
306 ++NumCompletePartials;
307 return OW_Complete;
308 }
309 }
310
311 // Check for a dead store which writes to all the memory locations that
312 // the killing store writes to.
313 if (Opts.enable_dse_partial_store_merging && KillingOff >= DeadOff &&
314 int64_t(DeadOff + DeadSize) > KillingOff &&
315 uint64_t(KillingOff - DeadOff) + KillingSize <= DeadSize) {
316 LLVM_DEBUG(dbgs() << "DSE: Partial overwrite a dead load [" << DeadOff
317 << ", " << int64_t(DeadOff + DeadSize)
318 << ") by a killing store [" << KillingOff << ", "
319 << int64_t(KillingOff + KillingSize) << ")\n");
320 // TODO: Maybe come up with a better name?
321 return OW_PartialEarlierWithFullLater;
322 }
323
324 // Another interesting case is if the killing store overwrites the end of the
325 // dead store.
326 //
327 // |--dead--|
328 // |-- killing --|
329 //
330 // In this case we may want to trim the size of dead store to avoid
331 // generating stores to addresses which will definitely be overwritten killing
332 // store.
333 if (!Opts.enable_dse_partial_overwrite_tracking &&
334 (KillingOff > DeadOff && KillingOff < int64_t(DeadOff + DeadSize) &&
335 int64_t(KillingOff + KillingSize) >= int64_t(DeadOff + DeadSize)))
336 return OW_End;
337
338 // Finally, we also need to check if the killing store overwrites the
339 // beginning of the dead store.
340 //
341 // |--dead--|
342 // |-- killing --|
343 //
344 // In this case we may want to move the destination address and trim the size
345 // of dead store to avoid generating stores to addresses which will definitely
346 // be overwritten killing store.
347 if (!Opts.enable_dse_partial_overwrite_tracking &&
348 (KillingOff <= DeadOff && int64_t(KillingOff + KillingSize) > DeadOff)) {
349 assert(int64_t(KillingOff + KillingSize) < int64_t(DeadOff + DeadSize) &&
350 "Expect to be handled as OW_Complete");
351 return OW_Begin;
352 }
353 // Otherwise, they don't completely overlap.
354 return OW_Unknown;
355}
356
357/// Returns true if the memory which is accessed by the second instruction is not
358/// modified between the first and the second instruction.
359/// Precondition: Second instruction must be dominated by the first
360/// instruction.
361static bool
362memoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI,
363 BatchAAResults &AA, const DataLayout &DL,
364 DominatorTree *DT) {
365 // Do a backwards scan through the CFG from SecondI to FirstI. Look for
366 // instructions which can modify the memory location accessed by SecondI.
367 //
368 // While doing the walk keep track of the address to check. It might be
369 // different in different basic blocks due to PHI translation.
370 using BlockAddressPair = std::pair<BasicBlock *, PHITransAddr>;
371 SmallVector<BlockAddressPair, 16> WorkList;
372 // Keep track of the address we visited each block with. Bail out if we
373 // visit a block with different addresses.
374 DenseMap<BasicBlock *, Value *> Visited;
375
376 BasicBlock::iterator FirstBBI(FirstI);
377 ++FirstBBI;
378 BasicBlock::iterator SecondBBI(SecondI);
379 BasicBlock *FirstBB = FirstI->getParent();
380 BasicBlock *SecondBB = SecondI->getParent();
381 MemoryLocation MemLoc;
382 if (auto *MemSet = dyn_cast<MemSetInst>(Val: SecondI))
383 MemLoc = MemoryLocation::getForDest(MI: MemSet);
384 else
385 MemLoc = MemoryLocation::get(Inst: SecondI);
386
387 auto *MemLocPtr = const_cast<Value *>(MemLoc.Ptr);
388
389 // Start checking the SecondBB.
390 WorkList.push_back(
391 Elt: std::make_pair(x&: SecondBB, y: PHITransAddr(MemLocPtr, DL, nullptr)));
392 bool isFirstBlock = true;
393
394 // Check all blocks going backward until we reach the FirstBB.
395 while (!WorkList.empty()) {
396 BlockAddressPair Current = WorkList.pop_back_val();
397 BasicBlock *B = Current.first;
398 PHITransAddr &Addr = Current.second;
399 Value *Ptr = Addr.getAddr();
400
401 // Ignore instructions before FirstI if this is the FirstBB.
402 BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());
403
404 BasicBlock::iterator EI;
405 if (isFirstBlock) {
406 // Ignore instructions after SecondI if this is the first visit of SecondBB.
407 assert(B == SecondBB && "first block is not the store block");
408 EI = SecondBBI;
409 isFirstBlock = false;
410 } else {
411 // It's not SecondBB or (in case of a loop) the second visit of SecondBB.
412 // In this case we also have to look at instructions after SecondI.
413 EI = B->end();
414 }
415 for (; BI != EI; ++BI) {
416 Instruction *I = &*BI;
417 if (I->mayWriteToMemory() && I != SecondI)
418 if (isModSet(MRI: AA.getModRefInfo(I, OptLoc: MemLoc.getWithNewPtr(NewPtr: Ptr))))
419 return false;
420 }
421 if (B != FirstBB) {
422 assert(B != &FirstBB->getParent()->getEntryBlock() &&
423 "Should not hit the entry block because SI must be dominated by LI");
424 for (BasicBlock *Pred : predecessors(BB: B)) {
425 PHITransAddr PredAddr = Addr;
426 if (PredAddr.needsPHITranslationFromBlock(BB: B)) {
427 if (!PredAddr.isPotentiallyPHITranslatable())
428 return false;
429 if (!PredAddr.translateValue(CurBB: B, PredBB: Pred, DT, MustDominate: false))
430 return false;
431 }
432 Value *TranslatedPtr = PredAddr.getAddr();
433 auto Inserted = Visited.insert(KV: std::make_pair(x&: Pred, y&: TranslatedPtr));
434 if (!Inserted.second) {
435 // We already visited this block before. If it was with a different
436 // address - bail out!
437 if (TranslatedPtr != Inserted.first->second)
438 return false;
439 // ... otherwise just skip it.
440 continue;
441 }
442 WorkList.push_back(Elt: std::make_pair(x&: Pred, y&: PredAddr));
443 }
444 }
445 }
446 return true;
447}
448
449static void shortenAssignment(Instruction *Inst, Value *OriginalDest,
450 uint64_t OldSizeInBits, uint64_t NewSizeInBits,
451 bool IsOverwriteEnd) {
452 const DataLayout &DL = Inst->getDataLayout();
453 uint64_t DeadSliceSizeInBits = OldSizeInBits - NewSizeInBits;
454 // The dead slice offset is relative to OriginalDest, the slice start we hand
455 // calculateFragmentIntersect. Shortening the end keeps the front of the
456 // store, so the dead bits start where the new store ends; shortening the
457 // beginning kills the bits at OriginalDest itself. Don't add OriginalDest's
458 // offset from its base object here. calculateFragmentIntersect already
459 // measures that pointer against the marker's address.
460 uint64_t DeadSliceOffsetInBits = IsOverwriteEnd ? NewSizeInBits : 0;
461 auto SetDeadFragExpr = [](auto *Assign,
462 DIExpression::FragmentInfo DeadFragment) {
463 // createFragmentExpression expects an offset relative to the existing
464 // fragment offset if there is one.
465 uint64_t RelativeOffset = DeadFragment.OffsetInBits -
466 Assign->getExpression()
467 ->getFragmentInfo()
468 .value_or(DIExpression::FragmentInfo(0, 0))
469 .OffsetInBits;
470 if (auto NewExpr = DIExpression::createFragmentExpression(
471 Expr: Assign->getExpression(), OffsetInBits: RelativeOffset, SizeInBits: DeadFragment.SizeInBits)) {
472 Assign->setExpression(*NewExpr);
473 return;
474 }
475 // Failed to create a fragment expression for this so discard the value,
476 // making this a kill location.
477 auto *Expr = *DIExpression::createFragmentExpression(
478 Expr: DIExpression::get(Context&: Assign->getContext(), Elements: {}), OffsetInBits: DeadFragment.OffsetInBits,
479 SizeInBits: DeadFragment.SizeInBits);
480 Assign->setExpression(Expr);
481 Assign->setKillLocation();
482 };
483
484 // A DIAssignID to use so that the inserted dbg.assign intrinsics do not
485 // link to any instructions. Created in the loop below (once).
486 DIAssignID *LinkToNothing = nullptr;
487 LLVMContext &Ctx = Inst->getContext();
488 auto GetDeadLink = [&Ctx, &LinkToNothing]() {
489 if (!LinkToNothing)
490 LinkToNothing = DIAssignID::getDistinct(Context&: Ctx);
491 return LinkToNothing;
492 };
493
494 // Insert an unlinked dbg.assign intrinsic for the dead fragment after each
495 // overlapping dbg.assign intrinsic.
496 for (DbgVariableRecord *Assign : at::getDVRAssignmentMarkers(Inst)) {
497 std::optional<DIExpression::FragmentInfo> NewFragment;
498 if (!at::calculateFragmentIntersect(DL, Dest: OriginalDest, SliceOffsetInBits: DeadSliceOffsetInBits,
499 SliceSizeInBits: DeadSliceSizeInBits, DVRAssign: Assign,
500 Result&: NewFragment) ||
501 !NewFragment) {
502 // Either the intersection couldn't be worked out, or it covers the
503 // entire variable region described by the record. Full coverage leaves
504 // NewFragment empty rather than making calculateFragmentIntersect fail,
505 // so unlink the whole assignment from the store in both cases.
506 Assign->setKillAddress();
507 Assign->setAssignId(GetDeadLink());
508 continue;
509 }
510 // No intersect.
511 if (NewFragment->SizeInBits == 0)
512 continue;
513
514 // Fragments overlap: insert a new dbg.assign for this dead part.
515 auto *NewAssign = static_cast<decltype(Assign)>(Assign->clone());
516 NewAssign->insertAfter(InsertAfter: Assign->getIterator());
517 NewAssign->setAssignId(GetDeadLink());
518 if (NewFragment)
519 SetDeadFragExpr(NewAssign, *NewFragment);
520 NewAssign->setKillAddress();
521 }
522}
523
524/// Update the attributes given that a memory access is updated (the
525/// dereferenced pointer could be moved forward when shortening a
526/// mem intrinsic).
527static void adjustArgAttributes(AnyMemIntrinsic *Intrinsic, unsigned ArgNo,
528 uint64_t PtrOffset) {
529 // Remember old attributes.
530 AttributeSet OldAttrs = Intrinsic->getParamAttributes(ArgNo);
531
532 // Find attributes that should be kept, and remove the rest.
533 AttributeMask AttrsToRemove;
534 for (auto &Attr : OldAttrs) {
535 if (Attr.hasKindAsEnum()) {
536 switch (Attr.getKindAsEnum()) {
537 default:
538 break;
539 case Attribute::Alignment:
540 // Only keep alignment if PtrOffset satisfy the alignment.
541 if (isAligned(Lhs: Attr.getAlignment().valueOrOne(), SizeInBytes: PtrOffset))
542 continue;
543 break;
544 case Attribute::Dereferenceable:
545 case Attribute::DereferenceableOrNull:
546 // We could reduce the size of these attributes according to
547 // PtrOffset. But we simply drop these for now.
548 break;
549 case Attribute::NonNull:
550 case Attribute::NoUndef:
551 continue;
552 }
553 }
554 AttrsToRemove.addAttribute(A: Attr);
555 }
556
557 // Remove the attributes that should be dropped.
558 Intrinsic->removeParamAttrs(ArgNo, AttrsToRemove);
559}
560
561static bool tryToShorten(Instruction *DeadI, int64_t &DeadStart,
562 uint64_t &DeadSize, int64_t KillingStart,
563 uint64_t KillingSize, bool IsOverwriteEnd) {
564 auto *DeadIntrinsic = cast<AnyMemIntrinsic>(Val: DeadI);
565 Align PrefAlign = DeadIntrinsic->getDestAlign().valueOrOne();
566
567 // We assume that memet/memcpy operates in chunks of the "largest" native
568 // type size and aligned on the same value. That means optimal start and size
569 // of memset/memcpy should be modulo of preferred alignment of that type. That
570 // is it there is no any sense in trying to reduce store size any further
571 // since any "extra" stores comes for free anyway.
572 // On the other hand, maximum alignment we can achieve is limited by alignment
573 // of initial store.
574
575 // TODO: Limit maximum alignment by preferred (or abi?) alignment of the
576 // "largest" native type.
577 // Note: What is the proper way to get that value?
578 // Should TargetTransformInfo::getRegisterBitWidth be used or anything else?
579 // PrefAlign = std::min(DL.getPrefTypeAlign(LargestType), PrefAlign);
580
581 int64_t ToRemoveStart = 0;
582 uint64_t ToRemoveSize = 0;
583 // Compute start and size of the region to remove. Make sure 'PrefAlign' is
584 // maintained on the remaining store.
585 if (IsOverwriteEnd) {
586 // Calculate required adjustment for 'KillingStart' in order to keep
587 // remaining store size aligned on 'PerfAlign'.
588 uint64_t Off =
589 offsetToAlignment(Value: uint64_t(KillingStart - DeadStart), Alignment: PrefAlign);
590 ToRemoveStart = KillingStart + Off;
591 if (DeadSize <= uint64_t(ToRemoveStart - DeadStart))
592 return false;
593 ToRemoveSize = DeadSize - uint64_t(ToRemoveStart - DeadStart);
594 } else {
595 ToRemoveStart = DeadStart;
596 assert(KillingSize >= uint64_t(DeadStart - KillingStart) &&
597 "Not overlapping accesses?");
598 ToRemoveSize = KillingSize - uint64_t(DeadStart - KillingStart);
599 // Calculate required adjustment for 'ToRemoveSize'in order to keep
600 // start of the remaining store aligned on 'PerfAlign'.
601 uint64_t Off = offsetToAlignment(Value: ToRemoveSize, Alignment: PrefAlign);
602 if (Off != 0) {
603 if (ToRemoveSize <= (PrefAlign.value() - Off))
604 return false;
605 ToRemoveSize -= PrefAlign.value() - Off;
606 }
607 assert(isAligned(PrefAlign, ToRemoveSize) &&
608 "Should preserve selected alignment");
609 }
610
611 assert(ToRemoveSize > 0 && "Shouldn't reach here if nothing to remove");
612 assert(DeadSize > ToRemoveSize && "Can't remove more than original size");
613
614 uint64_t NewSize = DeadSize - ToRemoveSize;
615 if (DeadIntrinsic->isAtomic()) {
616 // When shortening an atomic memory intrinsic, the newly shortened
617 // length must remain an integer multiple of the element size.
618 const uint32_t ElementSize = DeadIntrinsic->getElementSizeInBytes();
619 if (0 != NewSize % ElementSize)
620 return false;
621 }
622
623 LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n OW "
624 << (IsOverwriteEnd ? "END" : "BEGIN") << ": " << *DeadI
625 << "\n KILLER [" << ToRemoveStart << ", "
626 << int64_t(ToRemoveStart + ToRemoveSize) << ")\n");
627
628 DeadIntrinsic->setLength(NewSize);
629 DeadIntrinsic->setDestAlignment(PrefAlign);
630
631 Value *OrigDest = DeadIntrinsic->getRawDest();
632 if (!IsOverwriteEnd) {
633 Value *Indices[1] = {
634 ConstantInt::get(Ty: DeadIntrinsic->getLength()->getType(), V: ToRemoveSize)};
635 Instruction *NewDestGEP = GetElementPtrInst::CreateInBounds(
636 PointeeType: Type::getInt8Ty(C&: DeadIntrinsic->getContext()), Ptr: OrigDest, IdxList: Indices, NameStr: "",
637 InsertBefore: DeadI->getIterator());
638 NewDestGEP->setDebugLoc(DeadIntrinsic->getDebugLoc());
639 DeadIntrinsic->setDest(NewDestGEP);
640 adjustArgAttributes(Intrinsic: DeadIntrinsic, ArgNo: 0, PtrOffset: ToRemoveSize);
641 }
642
643 // Update attached dbg.assign intrinsics. Assume 8-bit byte.
644 shortenAssignment(Inst: DeadI, OriginalDest: OrigDest, OldSizeInBits: DeadSize * 8, NewSizeInBits: NewSize * 8, IsOverwriteEnd);
645
646 // Finally update start and size of dead access.
647 if (!IsOverwriteEnd)
648 DeadStart += ToRemoveSize;
649 DeadSize = NewSize;
650
651 return true;
652}
653
654static bool tryToShortenEnd(Instruction *DeadI, OverlapIntervalsTy &IntervalMap,
655 int64_t &DeadStart, uint64_t &DeadSize) {
656 if (IntervalMap.empty() || !isShortenableAtTheEnd(I: DeadI))
657 return false;
658
659 OverlapIntervalsTy::iterator OII = --IntervalMap.end();
660 int64_t KillingStart = OII->second;
661 uint64_t KillingSize = OII->first - KillingStart;
662
663 assert(OII->first - KillingStart >= 0 && "Size expected to be positive");
664
665 if (KillingStart > DeadStart &&
666 // Note: "KillingStart - KillingStart" is known to be positive due to
667 // preceding check.
668 (uint64_t)(KillingStart - DeadStart) < DeadSize &&
669 // Note: "DeadSize - (uint64_t)(KillingStart - DeadStart)" is known to
670 // be non negative due to preceding checks.
671 KillingSize >= DeadSize - (uint64_t)(KillingStart - DeadStart)) {
672 if (tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
673 IsOverwriteEnd: true)) {
674 IntervalMap.erase(position: OII);
675 return true;
676 }
677 }
678 return false;
679}
680
681static bool tryToShortenBegin(Instruction *DeadI,
682 OverlapIntervalsTy &IntervalMap,
683 int64_t &DeadStart, uint64_t &DeadSize) {
684 if (IntervalMap.empty() || !isShortenableAtTheBeginning(I: DeadI))
685 return false;
686
687 OverlapIntervalsTy::iterator OII = IntervalMap.begin();
688 int64_t KillingStart = OII->second;
689 uint64_t KillingSize = OII->first - KillingStart;
690
691 assert(OII->first - KillingStart >= 0 && "Size expected to be positive");
692
693 if (KillingStart <= DeadStart &&
694 // Note: "DeadStart - KillingStart" is known to be non negative due to
695 // preceding check.
696 KillingSize > (uint64_t)(DeadStart - KillingStart)) {
697 // Note: "KillingSize - (uint64_t)(DeadStart - DeadStart)" is known to
698 // be positive due to preceding checks.
699 assert(KillingSize - (uint64_t)(DeadStart - KillingStart) < DeadSize &&
700 "Should have been handled as OW_Complete");
701 if (tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
702 IsOverwriteEnd: false)) {
703 IntervalMap.erase(position: OII);
704 return true;
705 }
706 }
707 return false;
708}
709
710static Constant *
711tryToMergePartialOverlappingStores(StoreInst *KillingI, StoreInst *DeadI,
712 int64_t KillingOffset, int64_t DeadOffset,
713 const DataLayout &DL, BatchAAResults &AA,
714 DominatorTree *DT) {
715 assert(KillingI);
716 assert(DeadI);
717
718 // If the store we find is:
719 // a) partially overwritten by the store to 'Loc'
720 // b) the killing store is fully contained in the dead one and
721 // c) they both have a constant value
722 // d) none of the two stores need padding
723 // Merge the two stores, replacing the dead store's value with a
724 // merge of both values.
725 //
726 // TODO: Deal with other constant types (vectors, etc), and probably
727 // some mem intrinsics (if needed)
728 if (!isa<ConstantInt>(Val: DeadI->getValueOperand()) ||
729 !DL.typeSizeEqualsStoreSize(Ty: DeadI->getValueOperand()->getType()) ||
730 !isa<ConstantInt>(Val: KillingI->getValueOperand()) ||
731 !DL.typeSizeEqualsStoreSize(Ty: KillingI->getValueOperand()->getType()) ||
732 !memoryIsNotModifiedBetween(FirstI: DeadI, SecondI: KillingI, AA, DL, DT))
733 return nullptr;
734
735 // The merge erases KillingI and writes its bytes via DeadI. For that to be
736 // safe:
737 // - KillingI must be deletable (not volatile, ordering at most unordered),
738 // - DeadI must be safe to rewrite, and
739 // - their orderings must match, so the bytes originally written by
740 // KillingI keep the same atomicity after they are folded into DeadI.
741 // This allows merging two simple stores or two unordered-atomic stores with
742 // matching ordering, while leaving volatile and ordered-atomic stores in
743 // place.
744 if (!KillingI->isUnordered() || !DeadI->isUnordered() ||
745 KillingI->getOrdering() != DeadI->getOrdering())
746 return nullptr;
747
748 APInt DeadValue = cast<ConstantInt>(Val: DeadI->getValueOperand())->getValue();
749 APInt KillingValue =
750 cast<ConstantInt>(Val: KillingI->getValueOperand())->getValue();
751 unsigned KillingBits = KillingValue.getBitWidth();
752 assert(DeadValue.getBitWidth() > KillingValue.getBitWidth());
753 KillingValue = KillingValue.zext(width: DeadValue.getBitWidth());
754
755 // Offset of the smaller store inside the larger store
756 unsigned BitOffsetDiff = (KillingOffset - DeadOffset) * 8;
757 unsigned LShiftAmount =
758 DL.isBigEndian() ? DeadValue.getBitWidth() - BitOffsetDiff - KillingBits
759 : BitOffsetDiff;
760 APInt Mask = APInt::getBitsSet(numBits: DeadValue.getBitWidth(), loBit: LShiftAmount,
761 hiBit: LShiftAmount + KillingBits);
762 // Clear the bits we'll be replacing, then OR with the smaller
763 // store, shifted appropriately.
764 APInt Merged = (DeadValue & ~Mask) | (KillingValue << LShiftAmount);
765 LLVM_DEBUG(dbgs() << "DSE: Merge Stores:\n Dead: " << *DeadI
766 << "\n Killing: " << *KillingI
767 << "\n Merged Value: " << Merged << '\n');
768 return ConstantInt::get(Ty: DeadI->getValueOperand()->getType(), V: Merged);
769}
770
771// Returns true if \p I is an intrinsic that does not read or write memory.
772static bool isNoopIntrinsic(Instruction *I) {
773 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: I)) {
774 switch (II->getIntrinsicID()) {
775 case Intrinsic::lifetime_start:
776 case Intrinsic::lifetime_end:
777 case Intrinsic::invariant_end:
778 case Intrinsic::launder_invariant_group:
779 case Intrinsic::assume:
780 return true;
781 case Intrinsic::dbg_declare:
782 case Intrinsic::dbg_label:
783 case Intrinsic::dbg_value:
784 llvm_unreachable("Intrinsic should not be modeled in MemorySSA");
785 default:
786 return false;
787 }
788 }
789 return false;
790}
791
792// Check if we can ignore \p D for DSE.
793static bool canSkipDef(MemoryDef *D, bool DefVisibleToCaller) {
794 Instruction *DI = D->getMemoryInst();
795 // Calls that only access inaccessible memory cannot read or write any memory
796 // locations we consider for elimination.
797 if (auto *CB = dyn_cast<CallBase>(Val: DI))
798 if (CB->onlyAccessesInaccessibleMemory())
799 return true;
800
801 // We can eliminate stores to locations not visible to the caller across
802 // throwing instructions.
803 if (DI->mayThrow() && !DefVisibleToCaller)
804 return true;
805
806 // We can remove the dead stores, irrespective of the fence and its ordering
807 // (release/acquire/seq_cst). Fences only constraints the ordering of
808 // already visible stores, it does not make a store visible to other
809 // threads. So, skipping over a fence does not change a store from being
810 // dead.
811 if (isa<FenceInst>(Val: DI))
812 return true;
813
814 // Skip intrinsics that do not really read or modify memory.
815 if (isNoopIntrinsic(I: DI))
816 return true;
817
818 return false;
819}
820
821namespace {
822
823// A memory location wrapper that represents a MemoryLocation, `MemLoc`,
824// defined by `MemDef`.
825struct MemoryLocationWrapper {
826 MemoryLocationWrapper(MemoryLocation MemLoc, MemoryDef *MemDef,
827 bool DefByInitializesAttr)
828 : MemLoc(MemLoc), MemDef(MemDef),
829 DefByInitializesAttr(DefByInitializesAttr) {
830 assert(MemLoc.Ptr && "MemLoc should be not null");
831 UnderlyingObject = getUnderlyingObject(V: MemLoc.Ptr);
832 DefInst = MemDef->getMemoryInst();
833 }
834
835 MemoryLocation MemLoc;
836 const Value *UnderlyingObject;
837 MemoryDef *MemDef;
838 Instruction *DefInst;
839 bool DefByInitializesAttr = false;
840};
841
842// A memory def wrapper that represents a MemoryDef and the MemoryLocation(s)
843// defined by this MemoryDef.
844struct MemoryDefWrapper {
845 MemoryDefWrapper(MemoryDef *MemDef,
846 ArrayRef<std::pair<MemoryLocation, bool>> MemLocations) {
847 DefInst = MemDef->getMemoryInst();
848 for (auto &[MemLoc, DefByInitializesAttr] : MemLocations)
849 DefinedLocations.push_back(
850 Elt: MemoryLocationWrapper(MemLoc, MemDef, DefByInitializesAttr));
851 }
852 Instruction *DefInst;
853 SmallVector<MemoryLocationWrapper, 1> DefinedLocations;
854};
855
856struct ArgumentInitInfo {
857 unsigned Idx;
858 bool IsDeadOrInvisibleOnUnwind;
859 ConstantRangeList Inits;
860};
861} // namespace
862
863static bool hasInitializesAttr(Instruction *I) {
864 CallBase *CB = dyn_cast<CallBase>(Val: I);
865 return CB && CB->getArgOperandWithAttribute(Kind: Attribute::Initializes);
866}
867
868// Return the intersected range list of the initializes attributes of "Args".
869// "Args" are call arguments that alias to each other.
870// If any argument in "Args" doesn't have dead_on_unwind attr and
871// "CallHasNoUnwindAttr" is false, return empty.
872static ConstantRangeList
873getIntersectedInitRangeList(ArrayRef<ArgumentInitInfo> Args,
874 bool CallHasNoUnwindAttr) {
875 if (Args.empty())
876 return {};
877
878 // To address unwind, the function should have nounwind attribute or the
879 // arguments have dead or invisible on unwind. Otherwise, return empty.
880 for (const auto &Arg : Args) {
881 if (!CallHasNoUnwindAttr && !Arg.IsDeadOrInvisibleOnUnwind)
882 return {};
883 if (Arg.Inits.empty())
884 return {};
885 }
886
887 ConstantRangeList IntersectedIntervals = Args.front().Inits;
888 for (auto &Arg : Args.drop_front())
889 IntersectedIntervals = IntersectedIntervals.intersectWith(CRL: Arg.Inits);
890
891 return IntersectedIntervals;
892}
893
894namespace {
895
896struct DSEState {
897 const ScalarOptions &Opts;
898 Function &F;
899 AliasAnalysis &AA;
900 EarliestEscapeAnalysis EA;
901
902 /// The single BatchAA instance that is used to cache AA queries. It will
903 /// not be invalidated over the whole run. This is safe, because:
904 /// 1. Only memory writes are removed, so the alias cache for memory
905 /// locations remains valid.
906 /// 2. No new instructions are added (only instructions removed), so cached
907 /// information for a deleted value cannot be accessed by a re-used new
908 /// value pointer.
909 BatchAAResults BatchAA;
910
911 MemorySSA &MSSA;
912 DominatorTree &DT;
913 PostDominatorTree &PDT;
914 const TargetLibraryInfo &TLI;
915 const DataLayout &DL;
916 const CycleInfo &CI;
917
918 // All MemoryDefs that potentially could kill other MemDefs.
919 SmallVector<MemoryDef *, 64> MemDefs;
920 // Any that should be skipped as they are already deleted
921 SmallPtrSet<MemoryAccess *, 4> SkipStores;
922 // Keep track whether a given object is captured before return or not.
923 DenseMap<const Value *, bool> CapturedBeforeReturn;
924 // Keep track of all of the objects that are invisible to the caller after
925 // the function returns.
926 DenseMap<const Value *, bool> InvisibleToCallerAfterRet;
927 DenseMap<const Value *, uint64_t> InvisibleToCallerAfterRetBounded;
928 // Keep track of blocks with throwing instructions not modeled in MemorySSA.
929 SmallPtrSet<BasicBlock *, 16> ThrowingBlocks;
930 // Post-order numbers for each basic block. Used to figure out if memory
931 // accesses are executed before another access.
932 DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
933
934 /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
935 /// basic block.
936 MapVector<BasicBlock *, InstOverlapIntervalsTy> IOLs;
937 // Check if there are root nodes that are terminated by UnreachableInst.
938 // Those roots pessimize post-dominance queries. If there are such roots,
939 // fall back to CFG scan starting from all non-unreachable roots.
940 bool AnyUnreachableExit;
941
942 // Whether or not we should iterate on removing dead stores at the end of the
943 // function due to removing a store causing a previously captured pointer to
944 // no longer be captured.
945 bool ShouldIterateEndOfFunctionDSE;
946
947 /// Dead instructions to be removed at the end of DSE.
948 SmallVector<Instruction *> ToRemove;
949
950 // Class contains self-reference, make sure it's not copied/moved.
951 DSEState(const ScalarOptions &Opts, Function &F, AliasAnalysis &AA,
952 MemorySSA &MSSA, DominatorTree &DT, PostDominatorTree &PDT,
953 const TargetLibraryInfo &TLI, const CycleInfo &CI);
954 DSEState(const DSEState &) = delete;
955 DSEState &operator=(const DSEState &) = delete;
956
957 LocationSize strengthenLocationSize(const Instruction *I,
958 LocationSize Size) const;
959
960 /// Return 'OW_Complete' if a store to the 'KillingLoc' location (by \p
961 /// KillingI instruction) completely overwrites a store to the 'DeadLoc'
962 /// location (by \p DeadI instruction).
963 /// Return OW_MaybePartial if \p KillingI does not completely overwrite
964 /// \p DeadI, but they both write to the same underlying object. In that
965 /// case, use isPartialOverwrite to check if \p KillingI partially overwrites
966 /// \p DeadI. Returns 'OR_None' if \p KillingI is known to not overwrite the
967 /// \p DeadI. Returns 'OW_Unknown' if nothing can be determined.
968 OverwriteResult isOverwrite(const Instruction *KillingI,
969 const Instruction *DeadI,
970 const MemoryLocation &KillingLoc,
971 const MemoryLocation &DeadLoc,
972 int64_t &KillingOff, int64_t &DeadOff);
973
974 bool isInvisibleToCallerAfterRet(const Value *V, const Value *Ptr,
975 const LocationSize StoreSize);
976
977 bool isInvisibleToCallerOnUnwind(const Value *V);
978
979 std::optional<MemoryLocation> getLocForWrite(Instruction *I) const;
980
981 // Returns a list of <MemoryLocation, bool> pairs written by I.
982 // The bool means whether the write is from Initializes attr.
983 SmallVector<std::pair<MemoryLocation, bool>, 1>
984 getLocForInst(Instruction *I, bool ConsiderInitializesAttr);
985
986 /// Assuming this instruction has a dead analyzable write, can we delete
987 /// this instruction?
988 bool isRemovable(Instruction *I);
989
990 /// Returns true if \p UseInst completely overwrites \p DefLoc
991 /// (stored by \p DefInst).
992 bool isCompleteOverwrite(const MemoryLocation &DefLoc, Instruction *DefInst,
993 Instruction *UseInst);
994
995 /// Returns true if \p Def is not read before returning from the function.
996 bool isWriteAtEndOfFunction(MemoryDef *Def, const MemoryLocation &DefLoc);
997
998 /// If \p I is a memory terminator like llvm.lifetime.end or free, return a
999 /// pair with the MemoryLocation terminated by \p I and a boolean flag
1000 /// indicating whether \p I is a free-like call.
1001 std::optional<std::pair<MemoryLocation, bool>>
1002 getLocForTerminator(Instruction *I) const;
1003
1004 /// Returns true if \p I is a memory terminator instruction like
1005 /// llvm.lifetime.end or free.
1006 bool isMemTerminatorInst(Instruction *I) const;
1007
1008 /// Returns true if \p MaybeTerm is a memory terminator for \p Loc from
1009 /// instruction \p AccessI.
1010 bool isMemTerminator(const MemoryLocation &Loc, Instruction *AccessI,
1011 Instruction *MaybeTerm);
1012
1013 // Returns true if \p Use may read from \p DefLoc.
1014 bool isReadClobber(const MemoryLocation &DefLoc, Instruction *UseInst);
1015
1016 /// Returns true if a dependency between \p Current and \p KillingDef is
1017 /// guaranteed to be loop invariant for the loops that they are in. Either
1018 /// because they are known to be in the same block, in the same loop level or
1019 /// by guaranteeing that \p CurrentLoc only references a single MemoryLocation
1020 /// during execution of the containing function.
1021 bool isGuaranteedLoopIndependent(const Instruction *Current,
1022 const Instruction *KillingDef,
1023 const MemoryLocation &CurrentLoc);
1024
1025 /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
1026 /// loop. In particular, this guarantees that it only references a single
1027 /// MemoryLocation during execution of the containing function.
1028 bool isGuaranteedLoopInvariant(const Value *Ptr);
1029
1030 // Find a MemoryDef writing to \p KillingLoc and dominating \p StartAccess,
1031 // with no read access between them or on any other path to a function exit
1032 // block if \p KillingLoc is not accessible after the function returns. If
1033 // there is no such MemoryDef, return std::nullopt. The returned value may not
1034 // (completely) overwrite \p KillingLoc. Currently we bail out when we
1035 // encounter an aliasing MemoryUse (read).
1036 std::optional<MemoryAccess *>
1037 getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *StartAccess,
1038 const MemoryLocation &KillingLoc, const Value *KillingUndObj,
1039 unsigned &ScanLimit, unsigned &WalkerStepLimit,
1040 bool IsMemTerm, unsigned &PartialLimit,
1041 bool IsInitializesAttrMemLoc);
1042
1043 /// Delete dead memory defs and recursively add their operands to ToRemove if
1044 /// they became dead.
1045 void
1046 deleteDeadInstruction(Instruction *SI,
1047 SmallPtrSetImpl<MemoryAccess *> *Deleted = nullptr);
1048
1049 // Check for any extra throws between \p KillingI and \p DeadI that block
1050 // DSE. This only checks extra maythrows (those that aren't MemoryDef's).
1051 // MemoryDef that may throw are handled during the walk from one def to the
1052 // next.
1053 bool mayThrowBetween(Instruction *KillingI, Instruction *DeadI,
1054 const Value *KillingUndObj);
1055
1056 // Check if \p DeadI acts as a DSE barrier for \p KillingI. The following
1057 // instructions act as barriers:
1058 // * A memory instruction that may throw and \p KillingI accesses a non-stack
1059 // object.
1060 // * Atomic stores stronger that monotonic.
1061 bool isDSEBarrier(const Value *KillingUndObj, Instruction *DeadI);
1062
1063 /// Eliminate writes to objects that are not visible in the caller and are not
1064 /// accessed before returning from the function.
1065 bool eliminateDeadWritesAtEndOfFunction();
1066
1067 /// If we have a zero initializing memset following a call to malloc,
1068 /// try folding it into a call to calloc.
1069 bool tryFoldIntoCalloc(MemoryDef *Def, const Value *DefUO);
1070
1071 /// \returns true if \p Def is a no-op store, either because it
1072 /// directly stores back a loaded value or stores zero to a calloced object.
1073 bool storeIsNoop(MemoryDef *Def, const Value *DefUO);
1074
1075 bool removePartiallyOverlappedStores(InstOverlapIntervalsTy &IOL);
1076
1077 /// Eliminates writes to locations where the value that is being written
1078 /// is already stored at the same location.
1079 bool eliminateRedundantStoresOfExistingValues();
1080
1081 /// If there is a dominating condition that implies the value being stored in
1082 /// a pointer, and such a condition appears in a node that dominates the
1083 /// store, then the store may be redundant if no write occurs in between.
1084 bool eliminateRedundantStoresViaDominatingConditions();
1085
1086 // Return the locations written by the initializes attribute.
1087 // Note that this function considers:
1088 // 1. Unwind edge: use "initializes" attribute only if the callee has
1089 // "nounwind" attribute, or the argument has "dead_on_unwind" attribute,
1090 // or the argument is invisible to caller on unwind. That is, we don't
1091 // perform incorrect DSE on unwind edges in the current function.
1092 // 2. Argument alias: for aliasing arguments, the "initializes" attribute is
1093 // the intersected range list of their "initializes" attributes.
1094 SmallVector<MemoryLocation, 1> getInitializesArgMemLoc(const Instruction *I);
1095
1096 // Try to eliminate dead defs that access `KillingLocWrapper.MemLoc` and are
1097 // killed by `KillingLocWrapper.MemDef`. Return whether
1098 // any changes were made, and whether `KillingLocWrapper.DefInst` was deleted.
1099 std::pair<bool, bool>
1100 eliminateDeadDefs(const MemoryLocationWrapper &KillingLocWrapper);
1101
1102 // Try to eliminate dead defs killed by `KillingDefWrapper` and return the
1103 // change state: whether make any change.
1104 bool eliminateDeadDefs(const MemoryDefWrapper &KillingDefWrapper);
1105};
1106
1107} // end anonymous namespace
1108
1109static void pushMemUses(MemoryAccess *Acc,
1110 SmallVectorImpl<MemoryAccess *> &WorkList,
1111 SmallPtrSetImpl<MemoryAccess *> &Visited) {
1112 for (Use &U : Acc->uses()) {
1113 auto *MA = cast<MemoryAccess>(Val: U.getUser());
1114 if (Visited.insert(Ptr: MA).second)
1115 WorkList.push_back(Elt: MA);
1116 }
1117}
1118
1119// Return true if "Arg" is function local and isn't captured before "CB".
1120static bool isFuncLocalAndNotCaptured(Value *Arg, const CallBase *CB,
1121 EarliestEscapeAnalysis &EA) {
1122 const Value *UnderlyingObj = getUnderlyingObject(V: Arg);
1123 return isIdentifiedFunctionLocal(V: UnderlyingObj) &&
1124 capturesNothing(CC: EA.getCapturesBefore(Object: UnderlyingObj, I: CB, /*OrAt=*/true,
1125 /*ReturnCaptures=*/false));
1126}
1127
1128DSEState::DSEState(const ScalarOptions &Opts, Function &F, AliasAnalysis &AA,
1129 MemorySSA &MSSA, DominatorTree &DT, PostDominatorTree &PDT,
1130 const TargetLibraryInfo &TLI, const CycleInfo &CI)
1131 : Opts(Opts), F(F), AA(AA), EA(DT, nullptr, &CI), BatchAA(AA, &EA),
1132 MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI), DL(F.getDataLayout()), CI(CI) {
1133 // Collect blocks with throwing instructions not modeled in MemorySSA and
1134 // alloc-like objects.
1135 unsigned PO = 0;
1136 for (BasicBlock *BB : post_order(G: &F)) {
1137 PostOrderNumbers[BB] = PO++;
1138 for (Instruction &I : *BB) {
1139 MemoryAccess *MA = MSSA.getMemoryAccess(I: &I);
1140 if (I.mayThrow() && !MA)
1141 ThrowingBlocks.insert(Ptr: I.getParent());
1142
1143 auto *MD = dyn_cast_or_null<MemoryDef>(Val: MA);
1144 if (MD && MemDefs.size() < Opts.dse_memoryssa_defs_per_block_limit &&
1145 (getLocForWrite(I: &I) || isMemTerminatorInst(I: &I) ||
1146 (Opts.enable_dse_initializes_attr_improvement &&
1147 hasInitializesAttr(I: &I))))
1148 MemDefs.push_back(Elt: MD);
1149 }
1150 }
1151
1152 // Treat byval, inalloca or dead on return arguments the same as Allocas,
1153 // stores to them are dead at the end of the function.
1154 for (Argument &AI : F.args()) {
1155 if (AI.hasPassPointeeByValueCopyAttr()) {
1156 InvisibleToCallerAfterRet.insert(KV: {&AI, true});
1157 continue;
1158 }
1159
1160 if (!AI.getType()->isPointerTy())
1161 continue;
1162
1163 const DeadOnReturnInfo &Info = AI.getDeadOnReturnInfo();
1164 if (Info.coversAllReachableMemory())
1165 InvisibleToCallerAfterRet.insert(KV: {&AI, true});
1166 else if (uint64_t DeadBytes = Info.getNumberOfDeadBytes())
1167 InvisibleToCallerAfterRetBounded.insert(KV: {&AI, DeadBytes});
1168 }
1169
1170 AnyUnreachableExit = any_of(Range: PDT.roots(), P: [](const BasicBlock *E) {
1171 return isa<UnreachableInst>(Val: E->getTerminator());
1172 });
1173}
1174
1175LocationSize DSEState::strengthenLocationSize(const Instruction *I,
1176 LocationSize Size) const {
1177 if (auto *CB = dyn_cast<CallBase>(Val: I)) {
1178 LibFunc F = TLI.getLibFunc(CB: *CB);
1179 if (TLI.has(F) && (F == LibFunc_memset_chk || F == LibFunc_memcpy_chk)) {
1180 // Use the precise location size specified by the 3rd argument
1181 // for determining KillingI overwrites DeadLoc if it is a memset_chk
1182 // instruction. memset_chk will write either the amount specified as 3rd
1183 // argument or the function will immediately abort and exit the program.
1184 // NOTE: AA may determine NoAlias if it can prove that the access size
1185 // is larger than the allocation size due to that being UB. To avoid
1186 // returning potentially invalid NoAlias results by AA, limit the use of
1187 // the precise location size to isOverwrite.
1188 if (const auto *Len = dyn_cast<ConstantInt>(Val: CB->getArgOperand(i: 2)))
1189 return LocationSize::precise(Value: Len->getZExtValue());
1190 }
1191 }
1192 return Size;
1193}
1194
1195OverwriteResult DSEState::isOverwrite(const Instruction *KillingI,
1196 const Instruction *DeadI,
1197 const MemoryLocation &KillingLoc,
1198 const MemoryLocation &DeadLoc,
1199 int64_t &KillingOff, int64_t &DeadOff) {
1200 // AliasAnalysis does not always account for loops. Limit overwrite checks
1201 // to dependencies for which we can guarantee they are independent of any
1202 // loops they are in.
1203 if (!isGuaranteedLoopIndependent(Current: DeadI, KillingDef: KillingI, CurrentLoc: DeadLoc))
1204 return OW_Unknown;
1205
1206 LocationSize KillingLocSize =
1207 strengthenLocationSize(I: KillingI, Size: KillingLoc.Size);
1208 const Value *DeadPtr = DeadLoc.Ptr->stripPointerCasts();
1209 const Value *KillingPtr = KillingLoc.Ptr->stripPointerCasts();
1210 const Value *DeadUndObj = getUnderlyingObject(V: DeadPtr);
1211 const Value *KillingUndObj = getUnderlyingObject(V: KillingPtr);
1212
1213 // Check whether the killing store overwrites the whole object, in which
1214 // case the size/offset of the dead store does not matter.
1215 if (DeadUndObj == KillingUndObj && KillingLocSize.isPrecise() &&
1216 isIdentifiedObject(V: KillingUndObj)) {
1217 std::optional<TypeSize> KillingUndObjSize =
1218 getPointerSize(V: KillingUndObj, DL, TLI, F: &F);
1219 if (KillingUndObjSize && *KillingUndObjSize == KillingLocSize.getValue())
1220 return OW_Complete;
1221 }
1222
1223 // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
1224 // get imprecise values here, though (except for unknown sizes).
1225 if (!KillingLocSize.isPrecise() || !DeadLoc.Size.isPrecise()) {
1226 // In case no constant size is known, try to an IR values for the number
1227 // of bytes written and check if they match.
1228 const auto *KillingMemI = dyn_cast<MemIntrinsic>(Val: KillingI);
1229 const auto *DeadMemI = dyn_cast<MemIntrinsic>(Val: DeadI);
1230 if (KillingMemI && DeadMemI) {
1231 const Value *KillingV = KillingMemI->getLength();
1232 const Value *DeadV = DeadMemI->getLength();
1233 if (KillingV == DeadV && BatchAA.isMustAlias(LocA: DeadLoc, LocB: KillingLoc))
1234 return OW_Complete;
1235 }
1236
1237 // Masked stores have imprecise locations, but we can reason about them
1238 // to some extent.
1239 return isMaskedStoreOverwrite(KillingI, DeadI, AA&: BatchAA);
1240 }
1241
1242 const TypeSize KillingSize = KillingLocSize.getValue();
1243 const TypeSize DeadSize = DeadLoc.Size.getValue();
1244 // Bail on doing Size comparison which depends on AA for now
1245 // TODO: Remove AnyScalable once Alias Analysis deal with scalable vectors
1246 const bool AnyScalable = DeadSize.isScalable() || KillingLocSize.isScalable();
1247
1248 if (AnyScalable)
1249 return OW_Unknown;
1250 // Query the alias information
1251 AliasResult AAR = BatchAA.alias(LocA: KillingLoc, LocB: DeadLoc);
1252
1253 // If the start pointers are the same, we just have to compare sizes to see if
1254 // the killing store was larger than the dead store.
1255 if (AAR == AliasResult::MustAlias) {
1256 // Make sure that the KillingSize size is >= the DeadSize size.
1257 if (KillingSize >= DeadSize)
1258 return OW_Complete;
1259 }
1260
1261 // If we hit a partial alias we may have a full overwrite
1262 if (AAR == AliasResult::PartialAlias && AAR.hasOffset()) {
1263 int32_t Off = AAR.getOffset();
1264 if (Off >= 0 && (uint64_t)Off + DeadSize <= KillingSize)
1265 return OW_Complete;
1266 }
1267
1268 // If we can't resolve the same pointers to the same object, then we can't
1269 // analyze them at all.
1270 if (DeadUndObj != KillingUndObj) {
1271 // Non aliasing stores to different objects don't overlap. Note that
1272 // if the killing store is known to overwrite whole object (out of
1273 // bounds access overwrites whole object as well) then it is assumed to
1274 // completely overwrite any store to the same object even if they don't
1275 // actually alias (see next check).
1276 if (AAR == AliasResult::NoAlias)
1277 return OW_None;
1278 return OW_Unknown;
1279 }
1280
1281 // Okay, we have stores to two completely different pointers. Try to
1282 // decompose the pointer into a "base + constant_offset" form. If the base
1283 // pointers are equal, then we can reason about the two stores.
1284 DeadOff = 0;
1285 KillingOff = 0;
1286 const Value *DeadBasePtr =
1287 GetPointerBaseWithConstantOffset(Ptr: DeadPtr, Offset&: DeadOff, DL);
1288 const Value *KillingBasePtr =
1289 GetPointerBaseWithConstantOffset(Ptr: KillingPtr, Offset&: KillingOff, DL);
1290
1291 // If the base pointers still differ, we have two completely different
1292 // stores.
1293 if (DeadBasePtr != KillingBasePtr)
1294 return OW_Unknown;
1295
1296 // The killing access completely overlaps the dead store if and only if
1297 // both start and end of the dead one is "inside" the killing one:
1298 // |<->|--dead--|<->|
1299 // |-----killing------|
1300 // Accesses may overlap if and only if start of one of them is "inside"
1301 // another one:
1302 // |<->|--dead--|<-------->|
1303 // |-------killing--------|
1304 // OR
1305 // |-------dead-------|
1306 // |<->|---killing---|<----->|
1307 //
1308 // We have to be careful here as *Off is signed while *.Size is unsigned.
1309
1310 // Check if the dead access starts "not before" the killing one.
1311 if (DeadOff >= KillingOff) {
1312 // If the dead access ends "not after" the killing access then the
1313 // dead one is completely overwritten by the killing one.
1314 if (uint64_t(DeadOff - KillingOff) + DeadSize <= KillingSize)
1315 return OW_Complete;
1316 // If start of the dead access is "before" end of the killing access
1317 // then accesses overlap.
1318 else if ((uint64_t)(DeadOff - KillingOff) < KillingSize)
1319 return OW_MaybePartial;
1320 }
1321 // If start of the killing access is "before" end of the dead access then
1322 // accesses overlap.
1323 else if ((uint64_t)(KillingOff - DeadOff) < DeadSize) {
1324 return OW_MaybePartial;
1325 }
1326
1327 // Can reach here only if accesses are known not to overlap.
1328 return OW_None;
1329}
1330
1331bool DSEState::isInvisibleToCallerAfterRet(const Value *V, const Value *Ptr,
1332 const LocationSize StoreSize) {
1333 if (isa<AllocaInst>(Val: V))
1334 return true;
1335
1336 auto IBounded = InvisibleToCallerAfterRetBounded.find(Val: V);
1337 if (IBounded != InvisibleToCallerAfterRetBounded.end()) {
1338 int64_t ValueOffset;
1339 [[maybe_unused]] const Value *BaseValue =
1340 GetPointerBaseWithConstantOffset(Ptr, Offset&: ValueOffset, DL);
1341 // If we are not able to find a constant offset from the UO, we have to
1342 // pessimistically assume that the store writes to memory out of the
1343 // dead_on_return bounds.
1344 if (BaseValue != V)
1345 return false;
1346 // This store is only invisible after return if we are in bounds of the
1347 // range marked dead.
1348 if (StoreSize.hasValue() &&
1349 ValueOffset + StoreSize.getValue() <= IBounded->second &&
1350 ValueOffset >= 0)
1351 return true;
1352 }
1353 auto I = InvisibleToCallerAfterRet.insert(KV: {V, false});
1354 if (I.second && isInvisibleToCallerOnUnwind(V) && isNoAliasCall(V))
1355 I.first->second = capturesNothing(
1356 CC: PointerMayBeCaptured(V, Mask: CaptureComponents::Provenance).WithRet);
1357 return I.first->second;
1358}
1359
1360bool DSEState::isInvisibleToCallerOnUnwind(const Value *V) {
1361 bool RequiresNoCaptureBeforeUnwind;
1362 if (!isNotVisibleOnUnwind(Object: V, RequiresNoCaptureBeforeUnwind))
1363 return false;
1364 if (!RequiresNoCaptureBeforeUnwind)
1365 return true;
1366
1367 auto I = CapturedBeforeReturn.insert(KV: {V, true});
1368 if (I.second)
1369 // NOTE: This could be made more precise by PointerMayBeCapturedBefore
1370 // with the killing MemoryDef. But we refrain from doing so for now to
1371 // limit compile-time and this does not cause any changes to the number
1372 // of stores removed on a large test set in practice.
1373 I.first->second = capturesAnything(
1374 CC: PointerMayBeCaptured(V, Mask: CaptureComponents::Provenance).WithoutRet);
1375 return !I.first->second;
1376}
1377
1378std::optional<MemoryLocation> DSEState::getLocForWrite(Instruction *I) const {
1379 if (!I->mayWriteToMemory())
1380 return std::nullopt;
1381
1382 if (auto *CB = dyn_cast<CallBase>(Val: I))
1383 return MemoryLocation::getForDest(CI: CB, TLI);
1384
1385 return MemoryLocation::getOrNone(Inst: I);
1386}
1387
1388SmallVector<std::pair<MemoryLocation, bool>, 1>
1389DSEState::getLocForInst(Instruction *I, bool ConsiderInitializesAttr) {
1390 SmallVector<std::pair<MemoryLocation, bool>, 1> Locations;
1391 if (isMemTerminatorInst(I)) {
1392 if (auto Loc = getLocForTerminator(I))
1393 Locations.push_back(Elt: std::make_pair(x&: Loc->first, y: false));
1394 return Locations;
1395 }
1396
1397 if (auto Loc = getLocForWrite(I))
1398 Locations.push_back(Elt: std::make_pair(x&: *Loc, y: false));
1399
1400 if (ConsiderInitializesAttr) {
1401 for (auto &MemLoc : getInitializesArgMemLoc(I)) {
1402 Locations.push_back(Elt: std::make_pair(x&: MemLoc, y: true));
1403 }
1404 }
1405 return Locations;
1406}
1407
1408bool DSEState::isRemovable(Instruction *I) {
1409 assert(getLocForWrite(I) && "Must have analyzable write");
1410
1411 // Don't remove volatile/atomic stores.
1412 if (StoreInst *SI = dyn_cast<StoreInst>(Val: I))
1413 return SI->isUnordered();
1414
1415 if (auto *CB = dyn_cast<CallBase>(Val: I)) {
1416 // Don't remove volatile memory intrinsics.
1417 if (auto *MI = dyn_cast<MemIntrinsic>(Val: CB))
1418 return !MI->isVolatile();
1419
1420 // Never remove dead lifetime intrinsics, e.g. because they are followed
1421 // by a free.
1422 if (CB->isLifetimeStartOrEnd())
1423 return false;
1424
1425 return CB->use_empty() && CB->willReturn() && CB->doesNotThrow() &&
1426 !CB->isTerminator();
1427 }
1428
1429 return false;
1430}
1431
1432bool DSEState::isCompleteOverwrite(const MemoryLocation &DefLoc,
1433 Instruction *DefInst, Instruction *UseInst) {
1434 // UseInst has a MemoryDef associated in MemorySSA. It's possible for a
1435 // MemoryDef to not write to memory, e.g. a volatile load is modeled as a
1436 // MemoryDef.
1437 if (!UseInst->mayWriteToMemory())
1438 return false;
1439
1440 if (auto *CB = dyn_cast<CallBase>(Val: UseInst))
1441 if (CB->onlyAccessesInaccessibleMemory())
1442 return false;
1443
1444 int64_t InstWriteOffset, DepWriteOffset;
1445 if (auto CC = getLocForWrite(I: UseInst))
1446 return isOverwrite(KillingI: UseInst, DeadI: DefInst, KillingLoc: *CC, DeadLoc: DefLoc, KillingOff&: InstWriteOffset,
1447 DeadOff&: DepWriteOffset) == OW_Complete;
1448 return false;
1449}
1450
1451bool DSEState::isWriteAtEndOfFunction(MemoryDef *Def,
1452 const MemoryLocation &DefLoc) {
1453 LLVM_DEBUG(dbgs() << " Check if def " << *Def << " ("
1454 << *Def->getMemoryInst()
1455 << ") is at the end the function \n");
1456 SmallVector<MemoryAccess *, 4> WorkList;
1457 SmallPtrSet<MemoryAccess *, 8> Visited;
1458
1459 pushMemUses(Acc: Def, WorkList, Visited);
1460 for (unsigned I = 0; I < WorkList.size(); I++) {
1461 if (WorkList.size() >= Opts.dse_memoryssa_scanlimit) {
1462 LLVM_DEBUG(dbgs() << " ... hit exploration limit.\n");
1463 return false;
1464 }
1465
1466 MemoryAccess *UseAccess = WorkList[I];
1467 if (isa<MemoryPhi>(Val: UseAccess)) {
1468 // AliasAnalysis does not account for loops. Limit elimination to
1469 // candidates for which we can guarantee they always store to the same
1470 // memory location.
1471 if (!isGuaranteedLoopInvariant(Ptr: DefLoc.Ptr))
1472 return false;
1473
1474 pushMemUses(Acc: cast<MemoryPhi>(Val: UseAccess), WorkList, Visited);
1475 continue;
1476 }
1477 // TODO: Checking for aliasing is expensive. Consider reducing the amount
1478 // of times this is called and/or caching it.
1479 Instruction *UseInst = cast<MemoryUseOrDef>(Val: UseAccess)->getMemoryInst();
1480 if (isReadClobber(DefLoc, UseInst)) {
1481 LLVM_DEBUG(dbgs() << " ... hit read clobber " << *UseInst << ".\n");
1482 return false;
1483 }
1484
1485 if (MemoryDef *UseDef = dyn_cast<MemoryDef>(Val: UseAccess))
1486 pushMemUses(Acc: UseDef, WorkList, Visited);
1487 }
1488 return true;
1489}
1490
1491std::optional<std::pair<MemoryLocation, bool>>
1492DSEState::getLocForTerminator(Instruction *I) const {
1493 if (auto *CB = dyn_cast<CallBase>(Val: I)) {
1494 if (CB->getIntrinsicID() == Intrinsic::lifetime_end)
1495 return {
1496 std::make_pair(x: MemoryLocation::getForArgument(Call: CB, ArgIdx: 0, TLI: &TLI), y: false)};
1497 if (Value *FreedOp = getFreedOperand(CB, TLI: &TLI))
1498 return {std::make_pair(x: MemoryLocation::getAfter(Ptr: FreedOp), y: true)};
1499 }
1500
1501 return std::nullopt;
1502}
1503
1504bool DSEState::isMemTerminatorInst(Instruction *I) const {
1505 auto *CB = dyn_cast<CallBase>(Val: I);
1506 return CB && (CB->getIntrinsicID() == Intrinsic::lifetime_end ||
1507 getFreedOperand(CB, TLI: &TLI) != nullptr);
1508}
1509
1510bool DSEState::isMemTerminator(const MemoryLocation &Loc, Instruction *AccessI,
1511 Instruction *MaybeTerm) {
1512 std::optional<std::pair<MemoryLocation, bool>> MaybeTermLoc =
1513 getLocForTerminator(I: MaybeTerm);
1514
1515 if (!MaybeTermLoc)
1516 return false;
1517
1518 // If the terminator is a free-like call, all accesses to the underlying
1519 // object can be considered terminated.
1520 if (getUnderlyingObject(V: Loc.Ptr) !=
1521 getUnderlyingObject(V: MaybeTermLoc->first.Ptr))
1522 return false;
1523
1524 auto TermLoc = MaybeTermLoc->first;
1525 if (MaybeTermLoc->second) {
1526 const Value *LocUO = getUnderlyingObject(V: Loc.Ptr);
1527 return BatchAA.isMustAlias(V1: TermLoc.Ptr, V2: LocUO);
1528 }
1529 int64_t InstWriteOffset = 0;
1530 int64_t DepWriteOffset = 0;
1531 return isOverwrite(KillingI: MaybeTerm, DeadI: AccessI, KillingLoc: TermLoc, DeadLoc: Loc, KillingOff&: InstWriteOffset,
1532 DeadOff&: DepWriteOffset) == OW_Complete;
1533}
1534
1535bool DSEState::isReadClobber(const MemoryLocation &DefLoc,
1536 Instruction *UseInst) {
1537 if (isNoopIntrinsic(I: UseInst))
1538 return false;
1539
1540 // Monotonic or weaker atomic stores can be re-ordered and do not need to be
1541 // treated as read clobber.
1542 if (auto SI = dyn_cast<StoreInst>(Val: UseInst))
1543 return isStrongerThan(AO: SI->getOrdering(), Other: AtomicOrdering::Monotonic);
1544
1545 if (!UseInst->mayReadFromMemory())
1546 return false;
1547
1548 if (auto *CB = dyn_cast<CallBase>(Val: UseInst))
1549 if (CB->onlyAccessesInaccessibleMemory())
1550 return false;
1551
1552 return isRefSet(MRI: BatchAA.getModRefInfo(I: UseInst, OptLoc: DefLoc));
1553}
1554
1555bool DSEState::isGuaranteedLoopIndependent(const Instruction *Current,
1556 const Instruction *KillingDef,
1557 const MemoryLocation &CurrentLoc) {
1558 // If the dependency is within the same block or loop level (being careful
1559 // of irreducible loops), we know that AA will return a valid result for the
1560 // memory dependency. (Both at the function level, outside of any loop,
1561 // would also be valid but we currently disable that to limit compile time).
1562 if (Current->getParent() == KillingDef->getParent())
1563 return true;
1564 CycleRef CurrentC = CI.getCycle(Block: Current->getParent());
1565 if (CurrentC && CurrentC == CI.getCycle(Block: KillingDef->getParent()))
1566 return true;
1567 // Otherwise check the memory location is invariant to any loops.
1568 return isGuaranteedLoopInvariant(Ptr: CurrentLoc.Ptr);
1569}
1570
1571bool DSEState::isGuaranteedLoopInvariant(const Value *Ptr) {
1572 Ptr = Ptr->stripPointerCasts();
1573 if (auto *GEP = dyn_cast<GEPOperator>(Val: Ptr))
1574 if (GEP->hasAllConstantIndices())
1575 Ptr = GEP->getPointerOperand()->stripPointerCasts();
1576
1577 if (auto *I = dyn_cast<Instruction>(Val: Ptr)) {
1578 return I->getParent()->isEntryBlock() || !CI.getCycle(Block: I->getParent());
1579 }
1580 return true;
1581}
1582
1583std::optional<MemoryAccess *> DSEState::getDomMemoryDef(
1584 MemoryDef *KillingDef, MemoryAccess *StartAccess,
1585 const MemoryLocation &KillingLoc, const Value *KillingUndObj,
1586 unsigned &ScanLimit, unsigned &WalkerStepLimit, bool IsMemTerm,
1587 unsigned &PartialLimit, bool IsInitializesAttrMemLoc) {
1588 if (ScanLimit == 0 || WalkerStepLimit == 0) {
1589 LLVM_DEBUG(dbgs() << "\n ... hit scan limit\n");
1590 return std::nullopt;
1591 }
1592
1593 MemoryAccess *Current = StartAccess;
1594 Instruction *KillingI = KillingDef->getMemoryInst();
1595 LLVM_DEBUG(dbgs() << " trying to get dominating access\n");
1596
1597 // Only optimize defining access of KillingDef when directly starting at its
1598 // defining access. The defining access also must only access KillingLoc. At
1599 // the moment we only support instructions with a single write location, so
1600 // it should be sufficient to disable optimizations for instructions that
1601 // also read from memory.
1602 bool CanOptimize = Opts.dse_optimize_memoryssa &&
1603 KillingDef->getDefiningAccess() == StartAccess &&
1604 !KillingI->mayReadFromMemory();
1605
1606 // Find the next clobbering Mod access for DefLoc, starting at StartAccess.
1607 std::optional<MemoryLocation> CurrentLoc;
1608 for (;; Current = cast<MemoryDef>(Val: Current)->getDefiningAccess()) {
1609 LLVM_DEBUG({
1610 dbgs() << " visiting " << *Current;
1611 if (!MSSA.isLiveOnEntryDef(Current) && isa<MemoryUseOrDef>(Current))
1612 dbgs() << " (" << *cast<MemoryUseOrDef>(Current)->getMemoryInst()
1613 << ")";
1614 dbgs() << "\n";
1615 });
1616
1617 // Reached TOP.
1618 if (MSSA.isLiveOnEntryDef(MA: Current)) {
1619 LLVM_DEBUG(dbgs() << " ... found LiveOnEntryDef\n");
1620 if (CanOptimize && Current != KillingDef->getDefiningAccess())
1621 // The first clobbering def is... none.
1622 KillingDef->setOptimized(Current);
1623 return std::nullopt;
1624 }
1625
1626 // Cost of a step. Accesses in the same block are more likely to be valid
1627 // candidates for elimination, hence consider them cheaper.
1628 unsigned StepCost = KillingDef->getBlock() == Current->getBlock()
1629 ? Opts.dse_memoryssa_samebb_cost
1630 : Opts.dse_memoryssa_otherbb_cost;
1631 if (WalkerStepLimit <= StepCost) {
1632 LLVM_DEBUG(dbgs() << " ... hit walker step limit\n");
1633 return std::nullopt;
1634 }
1635 WalkerStepLimit -= StepCost;
1636
1637 // Return for MemoryPhis. They cannot be eliminated directly and the
1638 // caller is responsible for traversing them.
1639 if (isa<MemoryPhi>(Val: Current)) {
1640 LLVM_DEBUG(dbgs() << " ... found MemoryPhi\n");
1641 return Current;
1642 }
1643
1644 // Below, check if CurrentDef is a valid candidate to be eliminated by
1645 // KillingDef. If it is not, check the next candidate.
1646 MemoryDef *CurrentDef = cast<MemoryDef>(Val: Current);
1647 Instruction *CurrentI = CurrentDef->getMemoryInst();
1648
1649 if (canSkipDef(D: CurrentDef, DefVisibleToCaller: !isInvisibleToCallerOnUnwind(V: KillingUndObj))) {
1650 CanOptimize = false;
1651 continue;
1652 }
1653
1654 // Before we try to remove anything, check for any extra throwing
1655 // instructions that block us from DSEing
1656 if (mayThrowBetween(KillingI, DeadI: CurrentI, KillingUndObj)) {
1657 LLVM_DEBUG(dbgs() << " ... skip, may throw!\n");
1658 return std::nullopt;
1659 }
1660
1661 // Check for anything that looks like it will be a barrier to further
1662 // removal
1663 if (isDSEBarrier(KillingUndObj, DeadI: CurrentI)) {
1664 LLVM_DEBUG(dbgs() << " ... skip, barrier\n");
1665 return std::nullopt;
1666 }
1667
1668 // If Current is known to be on path that reads DefLoc or is a read
1669 // clobber, bail out, as the path is not profitable. We skip this check
1670 // for intrinsic calls, because the code knows how to handle memcpy
1671 // intrinsics.
1672 if (!isa<IntrinsicInst>(Val: CurrentI) && isReadClobber(DefLoc: KillingLoc, UseInst: CurrentI))
1673 return std::nullopt;
1674
1675 // Quick check if there are direct uses that are read-clobbers.
1676 if (any_of(Range: Current->uses(), P: [this, &KillingLoc, StartAccess](Use &U) {
1677 if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(Val: U.getUser()))
1678 return !MSSA.dominates(A: StartAccess, B: UseOrDef) &&
1679 isReadClobber(DefLoc: KillingLoc, UseInst: UseOrDef->getMemoryInst());
1680 return false;
1681 })) {
1682 LLVM_DEBUG(dbgs() << " ... found a read clobber\n");
1683 return std::nullopt;
1684 }
1685
1686 // If Current does not have an analyzable write location or is not
1687 // removable, skip it.
1688 CurrentLoc = getLocForWrite(I: CurrentI);
1689 if (!CurrentLoc || !isRemovable(I: CurrentI)) {
1690 CanOptimize = false;
1691 continue;
1692 }
1693
1694 // AliasAnalysis does not account for loops. Limit elimination to
1695 // candidates for which we can guarantee they always store to the same
1696 // memory location and not located in different loops.
1697 if (!isGuaranteedLoopIndependent(Current: CurrentI, KillingDef: KillingI, CurrentLoc: *CurrentLoc)) {
1698 LLVM_DEBUG(dbgs() << " ... not guaranteed loop independent\n");
1699 CanOptimize = false;
1700 continue;
1701 }
1702
1703 if (IsMemTerm) {
1704 // If the killing def is a memory terminator (e.g. lifetime.end), check
1705 // the next candidate if the current Current does not write the same
1706 // underlying object as the terminator.
1707 if (!isMemTerminator(Loc: *CurrentLoc, AccessI: CurrentI, MaybeTerm: KillingI)) {
1708 CanOptimize = false;
1709 continue;
1710 }
1711 } else {
1712 int64_t KillingOffset = 0;
1713 int64_t DeadOffset = 0;
1714 auto OR = isOverwrite(KillingI, DeadI: CurrentI, KillingLoc, DeadLoc: *CurrentLoc,
1715 KillingOff&: KillingOffset, DeadOff&: DeadOffset);
1716 if (CanOptimize) {
1717 // CurrentDef is the earliest write clobber of KillingDef. Use it as
1718 // optimized access. Do not optimize if CurrentDef is already the
1719 // defining access of KillingDef.
1720 if (CurrentDef != KillingDef->getDefiningAccess() &&
1721 (OR == OW_Complete || OR == OW_MaybePartial))
1722 KillingDef->setOptimized(CurrentDef);
1723
1724 // Once a may-aliasing def is encountered do not set an optimized
1725 // access.
1726 if (OR != OW_None)
1727 CanOptimize = false;
1728 }
1729
1730 // If Current does not write to the same object as KillingDef, check
1731 // the next candidate.
1732 if (OR == OW_Unknown || OR == OW_None)
1733 continue;
1734 else if (OR == OW_MaybePartial) {
1735 // If KillingDef only partially overwrites Current, check the next
1736 // candidate if the partial step limit is exceeded. This aggressively
1737 // limits the number of candidates for partial store elimination,
1738 // which are less likely to be removable in the end.
1739 if (PartialLimit <= 1) {
1740 WalkerStepLimit -= 1;
1741 LLVM_DEBUG(dbgs() << " ... reached partial limit ... continue with "
1742 "next access\n");
1743 continue;
1744 }
1745 PartialLimit -= 1;
1746 }
1747 }
1748 break;
1749 };
1750
1751 // Accesses to objects accessible after the function returns can only be
1752 // eliminated if the access is dead along all paths to the exit. Collect
1753 // the blocks with killing (=completely overwriting MemoryDefs) and check if
1754 // they cover all paths from MaybeDeadAccess to any function exit.
1755 SmallPtrSet<Instruction *, 16> KillingDefs;
1756 KillingDefs.insert(Ptr: KillingDef->getMemoryInst());
1757 MemoryAccess *MaybeDeadAccess = Current;
1758 MemoryLocation MaybeDeadLoc = *CurrentLoc;
1759 Instruction *MaybeDeadI = cast<MemoryDef>(Val: MaybeDeadAccess)->getMemoryInst();
1760 LLVM_DEBUG(dbgs() << " Checking for reads of " << *MaybeDeadAccess << " ("
1761 << *MaybeDeadI << ")\n");
1762
1763 SmallVector<MemoryAccess *, 32> WorkList;
1764 SmallPtrSet<MemoryAccess *, 32> Visited;
1765 pushMemUses(Acc: MaybeDeadAccess, WorkList, Visited);
1766
1767 // Check if DeadDef may be read.
1768 for (unsigned I = 0; I < WorkList.size(); I++) {
1769 MemoryAccess *UseAccess = WorkList[I];
1770
1771 LLVM_DEBUG(dbgs() << " " << *UseAccess);
1772 // Bail out if the number of accesses to check exceeds the scan limit.
1773 if (ScanLimit < (WorkList.size() - I)) {
1774 LLVM_DEBUG(dbgs() << "\n ... hit scan limit\n");
1775 return std::nullopt;
1776 }
1777 --ScanLimit;
1778 NumDomMemDefChecks++;
1779
1780 if (isa<MemoryPhi>(Val: UseAccess)) {
1781 if (any_of(Range&: KillingDefs, P: [this, UseAccess](Instruction *KI) {
1782 return DT.properlyDominates(A: KI->getParent(), B: UseAccess->getBlock());
1783 })) {
1784 LLVM_DEBUG(dbgs() << " ... skipping, dominated by killing block\n");
1785 continue;
1786 }
1787 LLVM_DEBUG(dbgs() << "\n ... adding PHI uses\n");
1788 pushMemUses(Acc: UseAccess, WorkList, Visited);
1789 continue;
1790 }
1791
1792 Instruction *UseInst = cast<MemoryUseOrDef>(Val: UseAccess)->getMemoryInst();
1793 LLVM_DEBUG(dbgs() << " (" << *UseInst << ")\n");
1794
1795 if (any_of(Range&: KillingDefs, P: [this, UseInst](Instruction *KI) {
1796 return DT.dominates(Def: KI, User: UseInst);
1797 })) {
1798 LLVM_DEBUG(dbgs() << " ... skipping, dominated by killing def\n");
1799 continue;
1800 }
1801
1802 // A memory terminator kills all preceeding MemoryDefs and all succeeding
1803 // MemoryAccesses. We do not have to check it's users.
1804 if (isMemTerminator(Loc: MaybeDeadLoc, AccessI: MaybeDeadI, MaybeTerm: UseInst)) {
1805 LLVM_DEBUG(
1806 dbgs()
1807 << " ... skipping, memterminator invalidates following accesses\n");
1808 continue;
1809 }
1810
1811 if (isNoopIntrinsic(I: cast<MemoryUseOrDef>(Val: UseAccess)->getMemoryInst())) {
1812 LLVM_DEBUG(dbgs() << " ... adding uses of intrinsic\n");
1813 pushMemUses(Acc: UseAccess, WorkList, Visited);
1814 continue;
1815 }
1816
1817 if (UseInst->mayThrow() && !isInvisibleToCallerOnUnwind(V: KillingUndObj)) {
1818 LLVM_DEBUG(dbgs() << " ... found throwing instruction\n");
1819 return std::nullopt;
1820 }
1821
1822 // Uses which may read the original MemoryDef mean we cannot eliminate the
1823 // original MD. Stop walk.
1824 // If KillingDef is a CallInst with "initializes" attribute, the reads in
1825 // the callee would be dominated by initializations, so it should be safe.
1826 bool IsKillingDefFromInitAttr = false;
1827 if (IsInitializesAttrMemLoc) {
1828 if (KillingI == UseInst &&
1829 KillingUndObj == getUnderlyingObject(V: MaybeDeadLoc.Ptr))
1830 IsKillingDefFromInitAttr = true;
1831 }
1832
1833 if (isReadClobber(DefLoc: MaybeDeadLoc, UseInst) && !IsKillingDefFromInitAttr) {
1834 LLVM_DEBUG(dbgs() << " ... found read clobber\n");
1835 return std::nullopt;
1836 }
1837
1838 // If this worklist walks back to the original memory access (and the
1839 // pointer is not guarenteed loop invariant) then we cannot assume that a
1840 // store kills itself.
1841 if (MaybeDeadAccess == UseAccess &&
1842 !isGuaranteedLoopInvariant(Ptr: MaybeDeadLoc.Ptr)) {
1843 LLVM_DEBUG(dbgs() << " ... found not loop invariant self access\n");
1844 return std::nullopt;
1845 }
1846 // Otherwise, for the KillingDef and MaybeDeadAccess we only have to check
1847 // if it reads the memory location.
1848 // TODO: It would probably be better to check for self-reads before
1849 // calling the function.
1850 if (KillingDef == UseAccess || MaybeDeadAccess == UseAccess) {
1851 LLVM_DEBUG(dbgs() << " ... skipping killing def/dom access\n");
1852 continue;
1853 }
1854
1855 // Check all uses for MemoryDefs, except for defs completely overwriting
1856 // the original location. Otherwise we have to check uses of *all*
1857 // MemoryDefs we discover, including non-aliasing ones. Otherwise we might
1858 // miss cases like the following
1859 // 1 = Def(LoE) ; <----- DeadDef stores [0,1]
1860 // 2 = Def(1) ; (2, 1) = NoAlias, stores [2,3]
1861 // Use(2) ; MayAlias 2 *and* 1, loads [0, 3].
1862 // (The Use points to the *first* Def it may alias)
1863 // 3 = Def(1) ; <---- Current (3, 2) = NoAlias, (3,1) = MayAlias,
1864 // stores [0,1]
1865 if (MemoryDef *UseDef = dyn_cast<MemoryDef>(Val: UseAccess)) {
1866 if (isCompleteOverwrite(DefLoc: MaybeDeadLoc, DefInst: MaybeDeadI, UseInst)) {
1867 BasicBlock *MaybeKillingBlock = UseInst->getParent();
1868 if (PostOrderNumbers.find(Val: MaybeKillingBlock)->second <
1869 PostOrderNumbers.find(Val: MaybeDeadAccess->getBlock())->second) {
1870 if (!isInvisibleToCallerAfterRet(V: KillingUndObj, Ptr: KillingLoc.Ptr,
1871 StoreSize: KillingLoc.Size)) {
1872 LLVM_DEBUG(dbgs()
1873 << " ... found killing def " << *UseInst << "\n");
1874 KillingDefs.insert(Ptr: UseInst);
1875 }
1876 } else {
1877 LLVM_DEBUG(dbgs()
1878 << " ... found preceeding def " << *UseInst << "\n");
1879 return std::nullopt;
1880 }
1881 } else
1882 pushMemUses(Acc: UseDef, WorkList, Visited);
1883 }
1884 }
1885
1886 // For accesses to locations visible after the function returns, make sure
1887 // that the location is dead (=overwritten) along all paths from
1888 // MaybeDeadAccess to the exit.
1889 if (!isInvisibleToCallerAfterRet(V: KillingUndObj, Ptr: KillingLoc.Ptr,
1890 StoreSize: KillingLoc.Size)) {
1891 SmallPtrSet<BasicBlock *, 16> KillingBlocks;
1892 for (Instruction *KD : KillingDefs)
1893 KillingBlocks.insert(Ptr: KD->getParent());
1894 assert(!KillingBlocks.empty() &&
1895 "Expected at least a single killing block");
1896
1897 // Find the common post-dominator of all killing blocks.
1898 BasicBlock *CommonPred = *KillingBlocks.begin();
1899 for (BasicBlock *BB : llvm::drop_begin(RangeOrContainer&: KillingBlocks)) {
1900 if (!CommonPred)
1901 break;
1902 CommonPred = PDT.findNearestCommonDominator(A: CommonPred, B: BB);
1903 }
1904
1905 // If the common post-dominator does not post-dominate MaybeDeadAccess,
1906 // there is a path from MaybeDeadAccess to an exit not going through a
1907 // killing block.
1908 if (!PDT.dominates(A: CommonPred, B: MaybeDeadAccess->getBlock())) {
1909 if (!AnyUnreachableExit)
1910 return std::nullopt;
1911
1912 // Fall back to CFG scan starting at all non-unreachable roots if not
1913 // all paths to the exit go through CommonPred.
1914 CommonPred = nullptr;
1915 }
1916
1917 // If CommonPred itself is in the set of killing blocks, we're done.
1918 if (KillingBlocks.count(Ptr: CommonPred))
1919 return {MaybeDeadAccess};
1920
1921 SetVector<BasicBlock *> WorkList;
1922 // If CommonPred is null, there are multiple exits from the function.
1923 // They all have to be added to the worklist.
1924 if (CommonPred)
1925 WorkList.insert(X: CommonPred);
1926 else
1927 for (BasicBlock *R : PDT.roots()) {
1928 if (!isa<UnreachableInst>(Val: R->getTerminator()))
1929 WorkList.insert(X: R);
1930 }
1931
1932 NumCFGTries++;
1933 // Check if all paths starting from an exit node go through one of the
1934 // killing blocks before reaching MaybeDeadAccess.
1935 for (unsigned I = 0; I < WorkList.size(); I++) {
1936 NumCFGChecks++;
1937 BasicBlock *Current = WorkList[I];
1938 if (KillingBlocks.count(Ptr: Current))
1939 continue;
1940 if (Current == MaybeDeadAccess->getBlock())
1941 return std::nullopt;
1942
1943 // MaybeDeadAccess is reachable from the entry, so we don't have to
1944 // explore unreachable blocks further.
1945 if (!DT.isReachableFromEntry(A: Current))
1946 continue;
1947
1948 WorkList.insert_range(R: predecessors(BB: Current));
1949
1950 if (WorkList.size() >= Opts.dse_memoryssa_path_check_limit)
1951 return std::nullopt;
1952 }
1953 NumCFGSuccess++;
1954 }
1955
1956 // No aliasing MemoryUses of MaybeDeadAccess found, MaybeDeadAccess is
1957 // potentially dead.
1958 return {MaybeDeadAccess};
1959}
1960
1961void DSEState::deleteDeadInstruction(Instruction *SI,
1962 SmallPtrSetImpl<MemoryAccess *> *Deleted) {
1963 MemorySSAUpdater Updater(&MSSA);
1964 SmallVector<Instruction *, 32> NowDeadInsts;
1965 NowDeadInsts.push_back(Elt: SI);
1966 --NumFastOther;
1967
1968 while (!NowDeadInsts.empty()) {
1969 Instruction *DeadInst = NowDeadInsts.pop_back_val();
1970 ++NumFastOther;
1971
1972 // Try to preserve debug information attached to the dead instruction.
1973 salvageDebugInfo(I&: *DeadInst);
1974 salvageKnowledge(I: DeadInst);
1975
1976 // Remove the Instruction from MSSA.
1977 MemoryAccess *MA = MSSA.getMemoryAccess(I: DeadInst);
1978 bool IsMemDef = MA && isa<MemoryDef>(Val: MA);
1979 if (MA) {
1980 if (IsMemDef) {
1981 auto *MD = cast<MemoryDef>(Val: MA);
1982 SkipStores.insert(Ptr: MD);
1983 if (Deleted)
1984 Deleted->insert(Ptr: MD);
1985 if (auto *SI = dyn_cast<StoreInst>(Val: MD->getMemoryInst())) {
1986 if (SI->getValueOperand()->getType()->isPointerTy()) {
1987 const Value *UO = getUnderlyingObject(V: SI->getValueOperand());
1988 if (CapturedBeforeReturn.erase(Val: UO))
1989 ShouldIterateEndOfFunctionDSE = true;
1990 InvisibleToCallerAfterRet.erase(Val: UO);
1991 InvisibleToCallerAfterRetBounded.erase(Val: UO);
1992 }
1993 }
1994 }
1995
1996 Updater.removeMemoryAccess(MA);
1997 }
1998
1999 auto I = IOLs.find(Key: DeadInst->getParent());
2000 if (I != IOLs.end())
2001 I->second.erase(Key: DeadInst);
2002 // Remove its operands
2003 for (Use &O : DeadInst->operands())
2004 if (Instruction *OpI = dyn_cast<Instruction>(Val&: O)) {
2005 O.set(PoisonValue::get(T: O->getType()));
2006 if (isInstructionTriviallyDead(I: OpI, TLI: &TLI))
2007 NowDeadInsts.push_back(Elt: OpI);
2008 }
2009
2010 EA.removeInstruction(I: DeadInst);
2011 // Remove memory defs directly if they don't produce results, but only
2012 // queue other dead instructions for later removal. They may have been
2013 // used as memory locations that have been cached by BatchAA. Removing
2014 // them here may lead to newly created instructions to be allocated at the
2015 // same address, yielding stale cache entries.
2016 if (IsMemDef && DeadInst->getType()->isVoidTy())
2017 DeadInst->eraseFromParent();
2018 else
2019 ToRemove.push_back(Elt: DeadInst);
2020 }
2021}
2022
2023bool DSEState::mayThrowBetween(Instruction *KillingI, Instruction *DeadI,
2024 const Value *KillingUndObj) {
2025 // First see if we can ignore it by using the fact that KillingI is an
2026 // alloca/alloca like object that is not visible to the caller during
2027 // execution of the function.
2028 if (KillingUndObj && isInvisibleToCallerOnUnwind(V: KillingUndObj))
2029 return false;
2030
2031 if (KillingI->getParent() == DeadI->getParent())
2032 return ThrowingBlocks.count(Ptr: KillingI->getParent());
2033 return !ThrowingBlocks.empty();
2034}
2035
2036bool DSEState::isDSEBarrier(const Value *KillingUndObj, Instruction *DeadI) {
2037 // If DeadI may throw it acts as a barrier, unless we are to an
2038 // alloca/alloca like object that does not escape.
2039 if (DeadI->mayThrow() && !isInvisibleToCallerOnUnwind(V: KillingUndObj))
2040 return true;
2041
2042 // If DeadI is an atomic load/store stronger than monotonic, do not try to
2043 // eliminate/reorder it.
2044 if (DeadI->isAtomic()) {
2045 if (auto *LI = dyn_cast<LoadInst>(Val: DeadI))
2046 return isStrongerThanMonotonic(AO: LI->getOrdering());
2047 if (auto *SI = dyn_cast<StoreInst>(Val: DeadI))
2048 return isStrongerThanMonotonic(AO: SI->getOrdering());
2049 if (auto *ARMW = dyn_cast<AtomicRMWInst>(Val: DeadI))
2050 return isStrongerThanMonotonic(AO: ARMW->getOrdering());
2051 if (auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(Val: DeadI))
2052 return isStrongerThanMonotonic(AO: CmpXchg->getSuccessOrdering()) ||
2053 isStrongerThanMonotonic(AO: CmpXchg->getFailureOrdering());
2054 llvm_unreachable("other instructions should be skipped in MemorySSA");
2055 }
2056 return false;
2057}
2058
2059bool DSEState::eliminateDeadWritesAtEndOfFunction() {
2060 bool MadeChange = false;
2061 LLVM_DEBUG(
2062 dbgs() << "Trying to eliminate MemoryDefs at the end of the function\n");
2063 do {
2064 ShouldIterateEndOfFunctionDSE = false;
2065 for (MemoryDef *Def : llvm::reverse(C&: MemDefs)) {
2066 if (SkipStores.contains(Ptr: Def))
2067 continue;
2068
2069 Instruction *DefI = Def->getMemoryInst();
2070 auto DefLoc = getLocForWrite(I: DefI);
2071 if (!DefLoc || !isRemovable(I: DefI)) {
2072 LLVM_DEBUG(dbgs() << " ... could not get location for write or "
2073 "instruction not removable.\n");
2074 continue;
2075 }
2076
2077 // NOTE: Currently eliminating writes at the end of a function is
2078 // limited to MemoryDefs with a single underlying object, to save
2079 // compile-time. In practice it appears the case with multiple
2080 // underlying objects is very uncommon. If it turns out to be important,
2081 // we can use getUnderlyingObjects here instead.
2082 const Value *UO = getUnderlyingObject(V: DefLoc->Ptr);
2083 if (!isInvisibleToCallerAfterRet(V: UO, Ptr: DefLoc->Ptr, StoreSize: DefLoc->Size))
2084 continue;
2085
2086 if (isWriteAtEndOfFunction(Def, DefLoc: *DefLoc)) {
2087 // See through pointer-to-pointer bitcasts
2088 LLVM_DEBUG(dbgs() << " ... MemoryDef is not accessed until the end "
2089 "of the function\n");
2090 deleteDeadInstruction(SI: DefI);
2091 ++NumFastStores;
2092 MadeChange = true;
2093 }
2094 }
2095 } while (ShouldIterateEndOfFunctionDSE);
2096 return MadeChange;
2097}
2098
2099bool DSEState::eliminateRedundantStoresViaDominatingConditions() {
2100 bool MadeChange = false;
2101 LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs whose value being "
2102 "written is implied by a dominating condition\n");
2103
2104 using ConditionInfo = std::pair<Value *, Value *>;
2105 using ScopedHTType = ScopedHashTable<ConditionInfo, Instruction *>;
2106
2107 // We maintain a scoped hash table of the active dominating conditions for a
2108 // given node.
2109 ScopedHTType ActiveConditions;
2110 auto GetDominatingCondition = [&](BasicBlock *BB)
2111 -> std::optional<std::tuple<ConditionInfo, Instruction *, BasicBlock *>> {
2112 auto *BI = dyn_cast<CondBrInst>(Val: BB->getTerminator());
2113 if (!BI)
2114 return std::nullopt;
2115
2116 // In case both blocks are the same, it is not possible to determine
2117 // if optimization is possible. (We would not want to optimize a store
2118 // in the FalseBB if condition is true and vice versa.)
2119 if (BI->getSuccessor(i: 0) == BI->getSuccessor(i: 1))
2120 return std::nullopt;
2121
2122 Instruction *ICmpL;
2123 CmpPredicate Pred;
2124 Value *StorePtr, *StoreVal;
2125 if (!match(V: BI->getCondition(),
2126 P: m_c_ICmp(Pred, L: m_Instruction(I&: ICmpL, P: m_Load(Op: m_Value(V&: StorePtr))),
2127 R: m_Value(V&: StoreVal))) ||
2128 !ICmpInst::isEquality(P: Pred))
2129 return std::nullopt;
2130
2131 // Ensure the replacement is allowed when comparing pointers, as
2132 // the equality compares addresses only, not pointers' provenance.
2133 if (StoreVal->getType()->isPointerTy() &&
2134 !canReplacePointersIfEqual(From: StoreVal, To: ICmpL, DL))
2135 return std::nullopt;
2136
2137 unsigned ImpliedSuccIdx = Pred == ICmpInst::ICMP_EQ ? 0 : 1;
2138 BasicBlock *ImpliedSucc = BI->getSuccessor(i: ImpliedSuccIdx);
2139 return {{ConditionInfo(StorePtr, StoreVal), ICmpL, ImpliedSucc}};
2140 };
2141
2142 auto VisitNode = [&](DomTreeNode *Node, unsigned Depth, auto &Self) -> void {
2143 if (Depth > Opts.dse_max_dom_cond_depth)
2144 return;
2145
2146 BasicBlock *BB = Node->getBlock();
2147 // Check for redundant stores against active known conditions.
2148 if (auto *Accesses = MSSA.getBlockDefs(BB)) {
2149 for (MemoryDef &Def :
2150 make_early_inc_range(Range: make_isa_range<MemoryDef>(Range&: *Accesses))) {
2151 auto *SI = dyn_cast<StoreInst>(Val: Def.getMemoryInst());
2152 if (!SI || !SI->isUnordered())
2153 continue;
2154
2155 Instruction *LI = ActiveConditions.lookup(
2156 Key: {SI->getPointerOperand(), SI->getValueOperand()});
2157 if (!LI)
2158 continue;
2159
2160 // Found a dominating condition that may imply the value being stored.
2161 // Make sure there does not exist any clobbering access between the
2162 // load and the potential redundant store.
2163 MemoryAccess *LoadAccess = MSSA.getMemoryAccess(I: LI);
2164 MemoryAccess *ClobberingAccess =
2165 MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(&Def, AA&: BatchAA);
2166 if (MSSA.dominates(A: ClobberingAccess, B: LoadAccess)) {
2167 LLVM_DEBUG(dbgs()
2168 << "Removing No-Op Store:\n DEAD: " << *SI << '\n');
2169 deleteDeadInstruction(SI);
2170 NumRedundantStores++;
2171 MadeChange = true;
2172 }
2173 }
2174 }
2175
2176 // See whether this basic block establishes a dominating condition.
2177 auto MaybeCondition = GetDominatingCondition(BB);
2178
2179 for (DomTreeNode *Child : Node->children()) {
2180 // RAII scope for the active conditions.
2181 ScopedHTType::ScopeTy Scope(ActiveConditions);
2182 if (MaybeCondition) {
2183 const auto &[Cond, LI, ImpliedSucc] = *MaybeCondition;
2184 if (DT.dominates(BBE: BasicBlockEdge(BB, ImpliedSucc), BB: Child->getBlock())) {
2185 // Found a condition that holds for this child, dominated by the
2186 // current node via the equality edge. Propagate the condition to
2187 // the children by pushing it onto the table.
2188 ActiveConditions.insert(Key: Cond, Val: LI);
2189 }
2190 }
2191
2192 // Recursively visit the children of this node. Upon destruction, the no
2193 // longer active condition before visiting any sibling nodes is popped
2194 // from the active scope.
2195 Self(Child, Depth + 1, Self);
2196 }
2197 };
2198
2199 // Do a DFS walk of the dom-tree.
2200 VisitNode(DT.getRootNode(), 0, VisitNode);
2201
2202 return MadeChange;
2203}
2204
2205bool DSEState::tryFoldIntoCalloc(MemoryDef *Def, const Value *DefUO) {
2206 Instruction *DefI = Def->getMemoryInst();
2207 MemSetInst *MemSet = dyn_cast<MemSetInst>(Val: DefI);
2208 if (!MemSet)
2209 // TODO: Could handle zero store to small allocation as well.
2210 return false;
2211 Constant *StoredConstant = dyn_cast<Constant>(Val: MemSet->getValue());
2212 if (!StoredConstant || !StoredConstant->isNullValue())
2213 return false;
2214
2215 if (!isRemovable(I: DefI))
2216 // The memset might be volatile..
2217 return false;
2218
2219 if (F.hasFnAttribute(Kind: Attribute::SanitizeMemory) ||
2220 F.hasFnAttribute(Kind: Attribute::SanitizeAddress) ||
2221 F.hasFnAttribute(Kind: Attribute::SanitizeHWAddress) || F.getName() == "calloc")
2222 return false;
2223 auto *Malloc = const_cast<CallInst *>(dyn_cast<CallInst>(Val: DefUO));
2224 if (!Malloc)
2225 return false;
2226 auto *InnerCallee = Malloc->getCalledFunction();
2227 if (!InnerCallee)
2228 return false;
2229 LibFunc Func = TLI.getLibFunc(FDecl: *InnerCallee);
2230 StringRef ZeroedVariantName;
2231 if (Func != LibFunc_malloc || !TLI.has(F: Func)) {
2232 Attribute Attr = Malloc->getFnAttr(Kind: "alloc-variant-zeroed");
2233 if (!Attr.isValid())
2234 return false;
2235 ZeroedVariantName = Attr.getValueAsString();
2236 if (ZeroedVariantName.empty())
2237 return false;
2238 }
2239
2240 // Gracefully handle malloc with unexpected memory attributes.
2241 auto *MallocDef = dyn_cast_or_null<MemoryDef>(Val: MSSA.getMemoryAccess(I: Malloc));
2242 if (!MallocDef)
2243 return false;
2244
2245 auto shouldCreateCalloc = [](CallInst *Malloc, CallInst *Memset) {
2246 // Check for br(icmp ptr, null), truebb, falsebb) pattern at the end
2247 // of malloc block
2248 auto *MallocBB = Malloc->getParent(), *MemsetBB = Memset->getParent();
2249 if (MallocBB == MemsetBB)
2250 return true;
2251 auto *Ptr = Memset->getArgOperand(i: 0);
2252 auto *TI = MallocBB->getTerminator();
2253 BasicBlock *TrueBB, *FalseBB;
2254 if (!match(V: TI, P: m_Br(C: m_SpecificICmp(MatchPred: ICmpInst::ICMP_EQ, L: m_Specific(V: Ptr),
2255 R: m_Zero()),
2256 T&: TrueBB, F&: FalseBB)))
2257 return false;
2258 if (MemsetBB != FalseBB)
2259 return false;
2260 return true;
2261 };
2262
2263 if (Malloc->getOperand(i_nocapture: 0) != MemSet->getLength())
2264 return false;
2265 if (!shouldCreateCalloc(Malloc, MemSet) || !DT.dominates(Def: Malloc, User: MemSet) ||
2266 !memoryIsNotModifiedBetween(FirstI: Malloc, SecondI: MemSet, AA&: BatchAA, DL, DT: &DT))
2267 return false;
2268 IRBuilder<> IRB(Malloc);
2269 assert(Func == LibFunc_malloc || !ZeroedVariantName.empty());
2270 Value *Calloc = nullptr;
2271 if (!ZeroedVariantName.empty()) {
2272 LLVMContext &Ctx = Malloc->getContext();
2273 AttributeList Attrs = InnerCallee->getAttributes();
2274 AllocFnKind AllocKind =
2275 Attrs.getFnAttr(Kind: Attribute::AllocKind).getAllocKind() |
2276 AllocFnKind::Zeroed;
2277 AllocKind &= ~AllocFnKind::Uninitialized;
2278 Attrs =
2279 Attrs.addFnAttribute(C&: Ctx, Attr: Attribute::getWithAllocKind(Context&: Ctx, Kind: AllocKind))
2280 .removeFnAttribute(C&: Ctx, Kind: "alloc-variant-zeroed");
2281 FunctionCallee ZeroedVariant = Malloc->getModule()->getOrInsertFunction(
2282 Name: ZeroedVariantName, T: InnerCallee->getFunctionType(), AttributeList: Attrs);
2283 cast<Function>(Val: ZeroedVariant.getCallee())
2284 ->setCallingConv(Malloc->getCallingConv());
2285 SmallVector<Value *, 3> Args;
2286 Args.append(in_start: Malloc->arg_begin(), in_end: Malloc->arg_end());
2287 CallInst *CI = IRB.CreateCall(Callee: ZeroedVariant, Args, Name: ZeroedVariantName);
2288 CI->setCallingConv(Malloc->getCallingConv());
2289 Calloc = CI;
2290 } else {
2291 Type *SizeTTy = Malloc->getArgOperand(i: 0)->getType();
2292 Calloc = emitCalloc(Num: ConstantInt::get(Ty: SizeTTy, V: 1), Size: Malloc->getArgOperand(i: 0),
2293 B&: IRB, TLI, AddrSpace: Malloc->getType()->getPointerAddressSpace());
2294 }
2295 if (!Calloc)
2296 return false;
2297
2298 if (MDNode *MD = Malloc->getMetadata(KindID: LLVMContext::MD_alloc_token))
2299 cast<Instruction>(Val: Calloc)->setMetadata(KindID: LLVMContext::MD_alloc_token, Node: MD);
2300
2301 MemorySSAUpdater Updater(&MSSA);
2302 auto *NewAccess = Updater.createMemoryAccessAfter(I: cast<Instruction>(Val: Calloc),
2303 Definition: nullptr, InsertPt: MallocDef);
2304 auto *NewAccessMD = cast<MemoryDef>(Val: NewAccess);
2305 Updater.insertDef(Def: NewAccessMD, /*RenameUses=*/true);
2306 Malloc->replaceAllUsesWith(V: Calloc);
2307 deleteDeadInstruction(SI: Malloc);
2308 return true;
2309}
2310
2311bool DSEState::storeIsNoop(MemoryDef *Def, const Value *DefUO) {
2312 Instruction *DefI = Def->getMemoryInst();
2313 StoreInst *Store = dyn_cast<StoreInst>(Val: DefI);
2314 MemSetInst *MemSet = dyn_cast<MemSetInst>(Val: DefI);
2315 Constant *StoredConstant = nullptr;
2316 if (Store)
2317 StoredConstant = dyn_cast<Constant>(Val: Store->getOperand(i_nocapture: 0));
2318 else if (MemSet)
2319 StoredConstant = dyn_cast<Constant>(Val: MemSet->getValue());
2320 else
2321 return false;
2322
2323 if (!isRemovable(I: DefI))
2324 return false;
2325
2326 if (StoredConstant) {
2327 Constant *InitC =
2328 getInitialValueOfAllocation(V: DefUO, TLI: &TLI, Ty: StoredConstant->getType());
2329 // If the clobbering access is LiveOnEntry, no instructions between them
2330 // can modify the memory location.
2331 if (InitC && InitC == StoredConstant)
2332 return MSSA.isLiveOnEntryDef(
2333 MA: MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def, AA&: BatchAA));
2334 }
2335
2336 if (!Store)
2337 return false;
2338
2339 if (auto *LoadI = dyn_cast<LoadInst>(Val: Store->getOperand(i_nocapture: 0))) {
2340 if (LoadI->getPointerOperand() == Store->getOperand(i_nocapture: 1)) {
2341 // Get the defining access for the load.
2342 auto *LoadAccess = MSSA.getMemoryAccess(I: LoadI)->getDefiningAccess();
2343 // Fast path: the defining accesses are the same.
2344 if (LoadAccess == Def->getDefiningAccess())
2345 return true;
2346
2347 // Look through phi accesses. Recursively scan all phi accesses by
2348 // adding them to a worklist. Bail when we run into a memory def that
2349 // does not match LoadAccess.
2350 SetVector<MemoryAccess *> ToCheck;
2351 MemoryAccess *Current =
2352 MSSA.getWalker()->getClobberingMemoryAccess(Def, AA&: BatchAA);
2353 // We don't want to bail when we run into the store memory def. But,
2354 // the phi access may point to it. So, pretend like we've already
2355 // checked it.
2356 ToCheck.insert(X: Def);
2357 ToCheck.insert(X: Current);
2358 // Start at current (1) to simulate already having checked Def.
2359 for (unsigned I = 1; I < ToCheck.size(); ++I) {
2360 Current = ToCheck[I];
2361 if (auto PhiAccess = dyn_cast<MemoryPhi>(Val: Current)) {
2362 // Check all the operands.
2363 for (auto &Use : PhiAccess->incoming_values())
2364 ToCheck.insert(X: cast<MemoryAccess>(Val: &Use));
2365 continue;
2366 }
2367
2368 // If we found a memory def, bail. This happens when we have an
2369 // unrelated write in between an otherwise noop store.
2370 assert(isa<MemoryDef>(Current) && "Only MemoryDefs should reach here.");
2371 // TODO: Skip no alias MemoryDefs that have no aliasing reads.
2372 // We are searching for the definition of the store's destination.
2373 // So, if that is the same definition as the load, then this is a
2374 // noop. Otherwise, fail.
2375 if (LoadAccess != Current)
2376 return false;
2377 }
2378 return true;
2379 }
2380 }
2381
2382 return false;
2383}
2384
2385bool DSEState::removePartiallyOverlappedStores(InstOverlapIntervalsTy &IOL) {
2386 bool Changed = false;
2387 for (auto OI : IOL) {
2388 Instruction *DeadI = OI.first;
2389 MemoryLocation Loc = *getLocForWrite(I: DeadI);
2390 assert(isRemovable(DeadI) && "Expect only removable instruction");
2391
2392 const Value *Ptr = Loc.Ptr->stripPointerCasts();
2393 int64_t DeadStart = 0;
2394 uint64_t DeadSize = Loc.Size.getValue();
2395 GetPointerBaseWithConstantOffset(Ptr, Offset&: DeadStart, DL);
2396 OverlapIntervalsTy &IntervalMap = OI.second;
2397 Changed |= tryToShortenEnd(DeadI, IntervalMap, DeadStart, DeadSize);
2398 if (IntervalMap.empty())
2399 continue;
2400 Changed |= tryToShortenBegin(DeadI, IntervalMap, DeadStart, DeadSize);
2401 }
2402 return Changed;
2403}
2404
2405bool DSEState::eliminateRedundantStoresOfExistingValues() {
2406 bool MadeChange = false;
2407 LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs that write the "
2408 "already existing value\n");
2409 for (auto *Def : MemDefs) {
2410 if (SkipStores.contains(Ptr: Def) || MSSA.isLiveOnEntryDef(MA: Def))
2411 continue;
2412
2413 Instruction *DefInst = Def->getMemoryInst();
2414 auto MaybeDefLoc = getLocForWrite(I: DefInst);
2415 if (!MaybeDefLoc || !isRemovable(I: DefInst))
2416 continue;
2417
2418 MemoryDef *UpperDef;
2419 // To conserve compile-time, we avoid walking to the next clobbering def.
2420 // Instead, we just try to get the optimized access, if it exists. DSE
2421 // will try to optimize defs during the earlier traversal.
2422 if (Def->isOptimized())
2423 UpperDef = dyn_cast<MemoryDef>(Val: Def->getOptimized());
2424 else
2425 UpperDef = dyn_cast<MemoryDef>(Val: Def->getDefiningAccess());
2426 if (!UpperDef || MSSA.isLiveOnEntryDef(MA: UpperDef))
2427 continue;
2428
2429 Instruction *UpperInst = UpperDef->getMemoryInst();
2430 auto IsRedundantStore = [&]() {
2431 // We don't care about differences in call attributes here.
2432 if (DefInst->isIdenticalToWhenDefined(I: UpperInst,
2433 /*IntersectAttrs=*/true))
2434 return true;
2435 if (auto *MemSetI = dyn_cast<MemSetInst>(Val: UpperInst)) {
2436 if (auto *SI = dyn_cast<StoreInst>(Val: DefInst)) {
2437 // MemSetInst must have a write location.
2438 auto UpperLoc = getLocForWrite(I: UpperInst);
2439 if (!UpperLoc)
2440 return false;
2441 int64_t InstWriteOffset = 0;
2442 int64_t DepWriteOffset = 0;
2443 auto OR = isOverwrite(KillingI: UpperInst, DeadI: DefInst, KillingLoc: *UpperLoc, DeadLoc: *MaybeDefLoc,
2444 KillingOff&: InstWriteOffset, DeadOff&: DepWriteOffset);
2445 Value *StoredByte = isBytewiseValue(V: SI->getValueOperand(), DL);
2446 return StoredByte && StoredByte == MemSetI->getOperand(i_nocapture: 1) &&
2447 OR == OW_Complete;
2448 }
2449 }
2450 return false;
2451 };
2452
2453 if (!IsRedundantStore() || isReadClobber(DefLoc: *MaybeDefLoc, UseInst: DefInst))
2454 continue;
2455 LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n DEAD: " << *DefInst
2456 << '\n');
2457 deleteDeadInstruction(SI: DefInst);
2458 NumRedundantStores++;
2459 MadeChange = true;
2460 }
2461 return MadeChange;
2462}
2463
2464SmallVector<MemoryLocation, 1>
2465DSEState::getInitializesArgMemLoc(const Instruction *I) {
2466 const CallBase *CB = dyn_cast<CallBase>(Val: I);
2467 if (!CB)
2468 return {};
2469
2470 // Collect aliasing arguments and their initializes ranges.
2471 SmallMapVector<Value *, SmallVector<ArgumentInitInfo, 2>, 2> Arguments;
2472 for (unsigned Idx = 0, Count = CB->arg_size(); Idx < Count; ++Idx) {
2473 Value *CurArg = CB->getArgOperand(i: Idx);
2474 if (!CurArg->getType()->isPointerTy())
2475 continue;
2476
2477 ConstantRangeList Inits;
2478 Attribute InitializesAttr = CB->getParamAttr(ArgNo: Idx, Kind: Attribute::Initializes);
2479 // initializes on byval arguments refers to the callee copy, not the
2480 // original memory the caller passed in.
2481 if (InitializesAttr.isValid() && !CB->isByValArgument(ArgNo: Idx))
2482 Inits = InitializesAttr.getValueAsConstantRangeList();
2483
2484 // Check whether "CurArg" could alias with global variables. We require
2485 // either it's function local and isn't captured before or the "CB" only
2486 // accesses arg or inaccessible mem.
2487 if (!Inits.empty() && !CB->onlyAccessesInaccessibleMemOrArgMem() &&
2488 !isFuncLocalAndNotCaptured(Arg: CurArg, CB, EA))
2489 Inits = ConstantRangeList();
2490
2491 // We don't perform incorrect DSE on unwind edges in the current function,
2492 // and use the "initializes" attribute to kill dead stores if:
2493 // - The call does not throw exceptions, "CB->doesNotThrow()".
2494 // - Or the callee parameter has "dead_on_unwind" attribute.
2495 // - Or the argument is invisible to caller on unwind, and there are no
2496 // unwind edges from this call in the current function (e.g. `CallInst`).
2497 bool IsDeadOrInvisibleOnUnwind =
2498 CB->paramHasAttr(ArgNo: Idx, Kind: Attribute::DeadOnUnwind) ||
2499 (isa<CallInst>(Val: CB) && isInvisibleToCallerOnUnwind(V: CurArg));
2500 ArgumentInitInfo InitInfo{.Idx: Idx, .IsDeadOrInvisibleOnUnwind: IsDeadOrInvisibleOnUnwind, .Inits: Inits};
2501 bool FoundAliasing = false;
2502 for (auto &[Arg, AliasList] : Arguments) {
2503 auto AAR = BatchAA.alias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: Arg),
2504 LocB: MemoryLocation::getBeforeOrAfter(Ptr: CurArg));
2505 if (AAR == AliasResult::NoAlias) {
2506 continue;
2507 } else if (AAR == AliasResult::MustAlias) {
2508 FoundAliasing = true;
2509 AliasList.push_back(Elt: InitInfo);
2510 } else {
2511 // For PartialAlias and MayAlias, there is an offset or may be an
2512 // unknown offset between the arguments and we insert an empty init
2513 // range to discard the entire initializes info while intersecting.
2514 FoundAliasing = true;
2515 AliasList.push_back(Elt: ArgumentInitInfo{.Idx: Idx, .IsDeadOrInvisibleOnUnwind: IsDeadOrInvisibleOnUnwind,
2516 .Inits: ConstantRangeList()});
2517 }
2518 }
2519 if (!FoundAliasing)
2520 Arguments[CurArg] = {InitInfo};
2521 }
2522
2523 SmallVector<MemoryLocation, 1> Locations;
2524 for (const auto &[_, Args] : Arguments) {
2525 auto IntersectedRanges =
2526 getIntersectedInitRangeList(Args, CallHasNoUnwindAttr: CB->doesNotThrow());
2527 if (IntersectedRanges.empty())
2528 continue;
2529
2530 for (const auto &Arg : Args) {
2531 for (const auto &Range : IntersectedRanges) {
2532 int64_t Start = Range.getLower().getSExtValue();
2533 int64_t End = Range.getUpper().getSExtValue();
2534 // For now, we only handle locations starting at offset 0.
2535 if (Start == 0)
2536 Locations.push_back(Elt: MemoryLocation(CB->getArgOperand(i: Arg.Idx),
2537 LocationSize::precise(Value: End - Start),
2538 CB->getAAMetadata()));
2539 }
2540 }
2541 }
2542 return Locations;
2543}
2544
2545std::pair<bool, bool>
2546DSEState::eliminateDeadDefs(const MemoryLocationWrapper &KillingLocWrapper) {
2547 bool Changed = false;
2548 bool DeletedKillingLoc = false;
2549 unsigned ScanLimit = Opts.dse_memoryssa_scanlimit;
2550 unsigned WalkerStepLimit = Opts.dse_memoryssa_walklimit;
2551 unsigned PartialLimit = Opts.dse_memoryssa_partial_store_limit;
2552 // Worklist of MemoryAccesses that may be killed by
2553 // "KillingLocWrapper.MemDef".
2554 SmallSetVector<MemoryAccess *, 8> ToCheck;
2555 // Track MemoryAccesses that have been deleted in the loop below, so we can
2556 // skip them. Don't use SkipStores for this, which may contain reused
2557 // MemoryAccess addresses.
2558 SmallPtrSet<MemoryAccess *, 8> Deleted;
2559 [[maybe_unused]] unsigned OrigNumSkipStores = SkipStores.size();
2560 ToCheck.insert(X: KillingLocWrapper.MemDef->getDefiningAccess());
2561
2562 // Check if MemoryAccesses in the worklist are killed by
2563 // "KillingLocWrapper.MemDef".
2564 for (unsigned I = 0; I < ToCheck.size(); I++) {
2565 MemoryAccess *Current = ToCheck[I];
2566 if (Deleted.contains(Ptr: Current))
2567 continue;
2568 std::optional<MemoryAccess *> MaybeDeadAccess = getDomMemoryDef(
2569 KillingDef: KillingLocWrapper.MemDef, StartAccess: Current, KillingLoc: KillingLocWrapper.MemLoc,
2570 KillingUndObj: KillingLocWrapper.UnderlyingObject, ScanLimit, WalkerStepLimit,
2571 IsMemTerm: isMemTerminatorInst(I: KillingLocWrapper.DefInst), PartialLimit,
2572 IsInitializesAttrMemLoc: KillingLocWrapper.DefByInitializesAttr);
2573
2574 if (!MaybeDeadAccess) {
2575 LLVM_DEBUG(dbgs() << " finished walk\n");
2576 continue;
2577 }
2578 MemoryAccess *DeadAccess = *MaybeDeadAccess;
2579 LLVM_DEBUG(dbgs() << " Checking if we can kill " << *DeadAccess);
2580 if (isa<MemoryPhi>(Val: DeadAccess)) {
2581 LLVM_DEBUG(dbgs() << "\n ... adding incoming values to worklist\n");
2582 for (Value *V : cast<MemoryPhi>(Val: DeadAccess)->incoming_values()) {
2583 MemoryAccess *IncomingAccess = cast<MemoryAccess>(Val: V);
2584 BasicBlock *IncomingBlock = IncomingAccess->getBlock();
2585 BasicBlock *PhiBlock = DeadAccess->getBlock();
2586
2587 // We only consider incoming MemoryAccesses that come before the
2588 // MemoryPhi. Otherwise we could discover candidates that do not
2589 // strictly dominate our starting def.
2590 if (PostOrderNumbers[IncomingBlock] > PostOrderNumbers[PhiBlock])
2591 ToCheck.insert(X: IncomingAccess);
2592 }
2593 continue;
2594 }
2595 // We cannot apply the initializes attribute to DeadAccess/DeadDef.
2596 // It would incorrectly consider a call instruction as redundant store
2597 // and remove this call instruction.
2598 // TODO: this conflates the existence of a MemoryLocation with being able
2599 // to delete the instruction. Fix isRemovable() to consider calls with
2600 // side effects that cannot be removed, e.g. calls with the initializes
2601 // attribute, and remove getLocForInst(ConsiderInitializesAttr = false).
2602 MemoryDefWrapper DeadDefWrapper(
2603 cast<MemoryDef>(Val: DeadAccess),
2604 getLocForInst(I: cast<MemoryDef>(Val: DeadAccess)->getMemoryInst(),
2605 /*ConsiderInitializesAttr=*/false));
2606 assert(DeadDefWrapper.DefinedLocations.size() == 1);
2607 MemoryLocationWrapper &DeadLocWrapper =
2608 DeadDefWrapper.DefinedLocations.front();
2609 LLVM_DEBUG(dbgs() << " (" << *DeadLocWrapper.DefInst << ")\n");
2610 ToCheck.insert(X: DeadLocWrapper.MemDef->getDefiningAccess());
2611 NumGetDomMemoryDefPassed++;
2612
2613 if (!DebugCounter::shouldExecute(Counter&: MemorySSACounter))
2614 continue;
2615 if (isMemTerminatorInst(I: KillingLocWrapper.DefInst)) {
2616 if (KillingLocWrapper.UnderlyingObject != DeadLocWrapper.UnderlyingObject)
2617 continue;
2618 LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: "
2619 << *DeadLocWrapper.DefInst << "\n KILLER: "
2620 << *KillingLocWrapper.DefInst << '\n');
2621 deleteDeadInstruction(SI: DeadLocWrapper.DefInst, Deleted: &Deleted);
2622 ++NumFastStores;
2623 Changed = true;
2624 } else {
2625 // Check if DeadI overwrites KillingI.
2626 int64_t KillingOffset = 0;
2627 int64_t DeadOffset = 0;
2628 OverwriteResult OR =
2629 isOverwrite(KillingI: KillingLocWrapper.DefInst, DeadI: DeadLocWrapper.DefInst,
2630 KillingLoc: KillingLocWrapper.MemLoc, DeadLoc: DeadLocWrapper.MemLoc,
2631 KillingOff&: KillingOffset, DeadOff&: DeadOffset);
2632 if (OR == OW_MaybePartial) {
2633 auto &IOL = IOLs[DeadLocWrapper.DefInst->getParent()];
2634 OR = isPartialOverwrite(Opts, KillingLoc: KillingLocWrapper.MemLoc,
2635 DeadLoc: DeadLocWrapper.MemLoc, KillingOff: KillingOffset,
2636 DeadOff: DeadOffset, DeadI: DeadLocWrapper.DefInst, IOL);
2637 }
2638 if (Opts.enable_dse_partial_store_merging &&
2639 OR == OW_PartialEarlierWithFullLater) {
2640 auto *DeadSI = dyn_cast<StoreInst>(Val: DeadLocWrapper.DefInst);
2641 auto *KillingSI = dyn_cast<StoreInst>(Val: KillingLocWrapper.DefInst);
2642 // We are re-using tryToMergePartialOverlappingStores, which requires
2643 // DeadSI to dominate KillingSI.
2644 // TODO: implement tryToMergeParialOverlappingStores using MemorySSA.
2645 if (DeadSI && KillingSI && DT.dominates(Def: DeadSI, User: KillingSI)) {
2646 if (Constant *Merged = tryToMergePartialOverlappingStores(
2647 KillingI: KillingSI, DeadI: DeadSI, KillingOffset, DeadOffset, DL, AA&: BatchAA,
2648 DT: &DT)) {
2649
2650 // Update stored value of earlier store to merged constant.
2651 DeadSI->setOperand(i_nocapture: 0, Val_nocapture: Merged);
2652 ++NumModifiedStores;
2653 Changed = true;
2654 DeletedKillingLoc = true;
2655
2656 // Remove killing store and remove any outstanding overlap
2657 // intervals for the updated store.
2658 deleteDeadInstruction(SI: KillingSI, Deleted: &Deleted);
2659 auto I = IOLs.find(Key: DeadSI->getParent());
2660 if (I != IOLs.end())
2661 I->second.erase(Key: DeadSI);
2662 break;
2663 }
2664 }
2665 }
2666 if (OR == OW_Complete) {
2667 LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: "
2668 << *DeadLocWrapper.DefInst << "\n KILLER: "
2669 << *KillingLocWrapper.DefInst << '\n');
2670 deleteDeadInstruction(SI: DeadLocWrapper.DefInst, Deleted: &Deleted);
2671 ++NumFastStores;
2672 Changed = true;
2673 }
2674 }
2675 }
2676
2677 assert(SkipStores.size() - OrigNumSkipStores == Deleted.size() &&
2678 "SkipStores and Deleted out of sync?");
2679
2680 return {Changed, DeletedKillingLoc};
2681}
2682
2683bool DSEState::eliminateDeadDefs(const MemoryDefWrapper &KillingDefWrapper) {
2684 if (KillingDefWrapper.DefinedLocations.empty()) {
2685 LLVM_DEBUG(dbgs() << "Failed to find analyzable write location for "
2686 << *KillingDefWrapper.DefInst << "\n");
2687 return false;
2688 }
2689
2690 bool MadeChange = false;
2691 for (auto &KillingLocWrapper : KillingDefWrapper.DefinedLocations) {
2692 LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs killed by "
2693 << *KillingLocWrapper.MemDef << " ("
2694 << *KillingLocWrapper.DefInst << ")\n");
2695 auto [Changed, DeletedKillingLoc] = eliminateDeadDefs(KillingLocWrapper);
2696 MadeChange |= Changed;
2697
2698 // Check if the store is a no-op.
2699 if (!DeletedKillingLoc && storeIsNoop(Def: KillingLocWrapper.MemDef,
2700 DefUO: KillingLocWrapper.UnderlyingObject)) {
2701 LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n DEAD: "
2702 << *KillingLocWrapper.DefInst << '\n');
2703 deleteDeadInstruction(SI: KillingLocWrapper.DefInst);
2704 NumRedundantStores++;
2705 MadeChange = true;
2706 continue;
2707 }
2708 // Can we form a calloc from a memset/malloc pair?
2709 if (!DeletedKillingLoc &&
2710 tryFoldIntoCalloc(Def: KillingLocWrapper.MemDef,
2711 DefUO: KillingLocWrapper.UnderlyingObject)) {
2712 LLVM_DEBUG(dbgs() << "DSE: Remove memset after forming calloc:\n"
2713 << " DEAD: " << *KillingLocWrapper.DefInst << '\n');
2714 deleteDeadInstruction(SI: KillingLocWrapper.DefInst);
2715 MadeChange = true;
2716 continue;
2717 }
2718 }
2719 return MadeChange;
2720}
2721
2722static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
2723 DominatorTree &DT, PostDominatorTree &PDT,
2724 const TargetLibraryInfo &TLI,
2725 const CycleInfo &CI) {
2726 const ScalarOptions &Opts = ScalarOptions::Global;
2727 bool MadeChange = false;
2728 DSEState State(Opts, F, AA, MSSA, DT, PDT, TLI, CI);
2729 // For each store:
2730 for (unsigned I = 0; I < State.MemDefs.size(); I++) {
2731 MemoryDef *KillingDef = State.MemDefs[I];
2732 if (State.SkipStores.count(Ptr: KillingDef))
2733 continue;
2734
2735 MemoryDefWrapper KillingDefWrapper(
2736 KillingDef,
2737 State.getLocForInst(I: KillingDef->getMemoryInst(),
2738 ConsiderInitializesAttr: Opts.enable_dse_initializes_attr_improvement));
2739 MadeChange |= State.eliminateDeadDefs(KillingDefWrapper);
2740 }
2741
2742 if (Opts.enable_dse_partial_overwrite_tracking)
2743 for (auto &KV : State.IOLs)
2744 MadeChange |= State.removePartiallyOverlappedStores(IOL&: KV.second);
2745
2746 MadeChange |= State.eliminateRedundantStoresOfExistingValues();
2747 MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
2748 MadeChange |= State.eliminateRedundantStoresViaDominatingConditions();
2749
2750 while (!State.ToRemove.empty()) {
2751 Instruction *DeadInst = State.ToRemove.pop_back_val();
2752 DeadInst->eraseFromParent();
2753 }
2754
2755 return MadeChange;
2756}
2757
2758//===----------------------------------------------------------------------===//
2759// DSE Pass
2760//===----------------------------------------------------------------------===//
2761PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
2762 AliasAnalysis &AA = AM.getResult<AAManager>(IR&: F);
2763 const TargetLibraryInfo &TLI = AM.getResult<TargetLibraryAnalysis>(IR&: F);
2764 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
2765 MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(IR&: F).getMSSA();
2766 PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(IR&: F);
2767 CycleInfo &CI = AM.getResult<CycleAnalysis>(IR&: F);
2768
2769 bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, CI);
2770
2771#ifdef LLVM_ENABLE_STATS
2772 if (AreStatisticsEnabled())
2773 for (auto &I : instructions(F))
2774 NumRemainingStores += isa<StoreInst>(Val: &I);
2775#endif
2776
2777 if (!Changed)
2778 return PreservedAnalyses::all();
2779
2780 PreservedAnalyses PA;
2781 PA.preserveSet<CFGAnalyses>();
2782 PA.preserve<MemorySSAAnalysis>();
2783 return PA;
2784}
2785
2786namespace {
2787
2788/// A legacy pass for the legacy pass manager that wraps \c DSEPass.
2789class DSELegacyPass : public FunctionPass {
2790public:
2791 static char ID; // Pass identification, replacement for typeid
2792
2793 DSELegacyPass() : FunctionPass(ID) {
2794 initializeDSELegacyPassPass(*PassRegistry::getPassRegistry());
2795 }
2796
2797 bool runOnFunction(Function &F) override {
2798 if (skipFunction(F))
2799 return false;
2800
2801 AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2802 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2803 const TargetLibraryInfo &TLI =
2804 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
2805 MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
2806 PostDominatorTree &PDT =
2807 getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
2808 CycleInfo &CI = getAnalysis<CycleInfoWrapperPass>().getResult();
2809
2810 bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, CI);
2811
2812#ifdef LLVM_ENABLE_STATS
2813 if (AreStatisticsEnabled())
2814 for (auto &I : instructions(F))
2815 NumRemainingStores += isa<StoreInst>(Val: &I);
2816#endif
2817
2818 return Changed;
2819 }
2820
2821 void getAnalysisUsage(AnalysisUsage &AU) const override {
2822 AU.setPreservesCFG();
2823 AU.addRequired<AAResultsWrapperPass>();
2824 AU.addRequired<TargetLibraryInfoWrapperPass>();
2825 AU.addPreserved<GlobalsAAWrapperPass>();
2826 AU.addRequired<DominatorTreeWrapperPass>();
2827 AU.addRequired<PostDominatorTreeWrapperPass>();
2828 AU.addRequired<MemorySSAWrapperPass>();
2829 AU.addPreserved<MemorySSAWrapperPass>();
2830 AU.addRequired<CycleInfoWrapperPass>();
2831 AU.addRequired<AssumptionCacheTracker>();
2832 }
2833};
2834
2835} // end anonymous namespace
2836
2837char DSELegacyPass::ID = 0;
2838
2839INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,
2840 false)
2841INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
2842INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
2843INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
2844INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
2845INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
2846INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
2847INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
2848INITIALIZE_PASS_DEPENDENCY(CycleInfoWrapperPass)
2849INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
2850INITIALIZE_PASS_END(DSELegacyPass, "dse", "Dead Store Elimination", false,
2851 false)
2852
2853LLVM_ABI FunctionPass *llvm::createDeadStoreEliminationPass() {
2854 return new DSELegacyPass();
2855}
2856