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