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