Bug Summary

File:llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
Warning:line 2500, column 19
Value stored to 'Current' during its initialization is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name DeadStoreElimination.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-13/lib/clang/13.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/build-llvm/include -I /build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-13/lib/clang/13.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2021-02-23-121308-24221-1 -x c++ /build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1//===- DeadStoreElimination.cpp - Fast 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// This file implements a trivial dead store elimination that only considers
10// basic-block local redundant stores.
11//
12// FIXME: This should eventually be extended to be a post-dominator tree
13// traversal. Doing so would be pretty trivial.
14//
15//===----------------------------------------------------------------------===//
16
17#include "llvm/Transforms/Scalar/DeadStoreElimination.h"
18#include "llvm/ADT/APInt.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/MapVector.h"
21#include "llvm/ADT/PostOrderIterator.h"
22#include "llvm/ADT/SetVector.h"
23#include "llvm/ADT/SmallPtrSet.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/ADT/Statistic.h"
26#include "llvm/ADT/StringRef.h"
27#include "llvm/Analysis/AliasAnalysis.h"
28#include "llvm/Analysis/CaptureTracking.h"
29#include "llvm/Analysis/GlobalsModRef.h"
30#include "llvm/Analysis/MemoryBuiltins.h"
31#include "llvm/Analysis/MemoryDependenceAnalysis.h"
32#include "llvm/Analysis/MemoryLocation.h"
33#include "llvm/Analysis/MemorySSA.h"
34#include "llvm/Analysis/MemorySSAUpdater.h"
35#include "llvm/Analysis/PostDominators.h"
36#include "llvm/Analysis/TargetLibraryInfo.h"
37#include "llvm/Analysis/ValueTracking.h"
38#include "llvm/IR/Argument.h"
39#include "llvm/IR/BasicBlock.h"
40#include "llvm/IR/Constant.h"
41#include "llvm/IR/Constants.h"
42#include "llvm/IR/DataLayout.h"
43#include "llvm/IR/Dominators.h"
44#include "llvm/IR/Function.h"
45#include "llvm/IR/InstIterator.h"
46#include "llvm/IR/InstrTypes.h"
47#include "llvm/IR/Instruction.h"
48#include "llvm/IR/Instructions.h"
49#include "llvm/IR/IntrinsicInst.h"
50#include "llvm/IR/Intrinsics.h"
51#include "llvm/IR/LLVMContext.h"
52#include "llvm/IR/Module.h"
53#include "llvm/IR/PassManager.h"
54#include "llvm/IR/PatternMatch.h"
55#include "llvm/IR/Value.h"
56#include "llvm/InitializePasses.h"
57#include "llvm/Pass.h"
58#include "llvm/Support/Casting.h"
59#include "llvm/Support/CommandLine.h"
60#include "llvm/Support/Debug.h"
61#include "llvm/Support/DebugCounter.h"
62#include "llvm/Support/ErrorHandling.h"
63#include "llvm/Support/MathExtras.h"
64#include "llvm/Support/raw_ostream.h"
65#include "llvm/Transforms/Scalar.h"
66#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
67#include "llvm/Transforms/Utils/Local.h"
68#include <algorithm>
69#include <cassert>
70#include <cstddef>
71#include <cstdint>
72#include <iterator>
73#include <map>
74#include <utility>
75
76using namespace llvm;
77using namespace PatternMatch;
78
79#define DEBUG_TYPE"dse" "dse"
80
81STATISTIC(NumRemainingStores, "Number of stores remaining after DSE")static llvm::Statistic NumRemainingStores = {"dse", "NumRemainingStores"
, "Number of stores remaining after DSE"}
;
82STATISTIC(NumRedundantStores, "Number of redundant stores deleted")static llvm::Statistic NumRedundantStores = {"dse", "NumRedundantStores"
, "Number of redundant stores deleted"}
;
83STATISTIC(NumFastStores, "Number of stores deleted")static llvm::Statistic NumFastStores = {"dse", "NumFastStores"
, "Number of stores deleted"}
;
84STATISTIC(NumFastOther, "Number of other instrs removed")static llvm::Statistic NumFastOther = {"dse", "NumFastOther",
"Number of other instrs removed"}
;
85STATISTIC(NumCompletePartials, "Number of stores dead by later partials")static llvm::Statistic NumCompletePartials = {"dse", "NumCompletePartials"
, "Number of stores dead by later partials"}
;
86STATISTIC(NumModifiedStores, "Number of stores modified")static llvm::Statistic NumModifiedStores = {"dse", "NumModifiedStores"
, "Number of stores modified"}
;
87STATISTIC(NumCFGChecks, "Number of stores modified")static llvm::Statistic NumCFGChecks = {"dse", "NumCFGChecks",
"Number of stores modified"}
;
88STATISTIC(NumCFGTries, "Number of stores modified")static llvm::Statistic NumCFGTries = {"dse", "NumCFGTries", "Number of stores modified"
}
;
89STATISTIC(NumCFGSuccess, "Number of stores modified")static llvm::Statistic NumCFGSuccess = {"dse", "NumCFGSuccess"
, "Number of stores modified"}
;
90STATISTIC(NumGetDomMemoryDefPassed,static llvm::Statistic NumGetDomMemoryDefPassed = {"dse", "NumGetDomMemoryDefPassed"
, "Number of times a valid candidate is returned from getDomMemoryDef"
}
91 "Number of times a valid candidate is returned from getDomMemoryDef")static llvm::Statistic NumGetDomMemoryDefPassed = {"dse", "NumGetDomMemoryDefPassed"
, "Number of times a valid candidate is returned from getDomMemoryDef"
}
;
92STATISTIC(NumDomMemDefChecks,static llvm::Statistic NumDomMemDefChecks = {"dse", "NumDomMemDefChecks"
, "Number iterations check for reads in getDomMemoryDef"}
93 "Number iterations check for reads in getDomMemoryDef")static llvm::Statistic NumDomMemDefChecks = {"dse", "NumDomMemDefChecks"
, "Number iterations check for reads in getDomMemoryDef"}
;
94
95DEBUG_COUNTER(MemorySSACounter, "dse-memoryssa",static const unsigned MemorySSACounter = DebugCounter::registerCounter
("dse-memoryssa", "Controls which MemoryDefs are eliminated."
)
96 "Controls which MemoryDefs are eliminated.")static const unsigned MemorySSACounter = DebugCounter::registerCounter
("dse-memoryssa", "Controls which MemoryDefs are eliminated."
)
;
97
98static cl::opt<bool>
99EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking",
100 cl::init(true), cl::Hidden,
101 cl::desc("Enable partial-overwrite tracking in DSE"));
102
103static cl::opt<bool>
104EnablePartialStoreMerging("enable-dse-partial-store-merging",
105 cl::init(true), cl::Hidden,
106 cl::desc("Enable partial store merging in DSE"));
107
108static cl::opt<bool>
109 EnableMemorySSA("enable-dse-memoryssa", cl::init(true), cl::Hidden,
110 cl::desc("Use the new MemorySSA-backed DSE."));
111
112static cl::opt<unsigned>
113 MemorySSAScanLimit("dse-memoryssa-scanlimit", cl::init(150), cl::Hidden,
114 cl::desc("The number of memory instructions to scan for "
115 "dead store elimination (default = 100)"));
116static cl::opt<unsigned> MemorySSAUpwardsStepLimit(
117 "dse-memoryssa-walklimit", cl::init(90), cl::Hidden,
118 cl::desc("The maximum number of steps while walking upwards to find "
119 "MemoryDefs that may be killed (default = 90)"));
120
121static cl::opt<unsigned> MemorySSAPartialStoreLimit(
122 "dse-memoryssa-partial-store-limit", cl::init(5), cl::Hidden,
123 cl::desc("The maximum number candidates that only partially overwrite the "
124 "killing MemoryDef to consider"
125 " (default = 5)"));
126
127static cl::opt<unsigned> MemorySSADefsPerBlockLimit(
128 "dse-memoryssa-defs-per-block-limit", cl::init(5000), cl::Hidden,
129 cl::desc("The number of MemoryDefs we consider as candidates to eliminated "
130 "other stores per basic block (default = 5000)"));
131
132static cl::opt<unsigned> MemorySSASameBBStepCost(
133 "dse-memoryssa-samebb-cost", cl::init(1), cl::Hidden,
134 cl::desc(
135 "The cost of a step in the same basic block as the killing MemoryDef"
136 "(default = 1)"));
137
138static cl::opt<unsigned>
139 MemorySSAOtherBBStepCost("dse-memoryssa-otherbb-cost", cl::init(5),
140 cl::Hidden,
141 cl::desc("The cost of a step in a different basic "
142 "block than the killing MemoryDef"
143 "(default = 5)"));
144
145static cl::opt<unsigned> MemorySSAPathCheckLimit(
146 "dse-memoryssa-path-check-limit", cl::init(50), cl::Hidden,
147 cl::desc("The maximum number of blocks to check when trying to prove that "
148 "all paths to an exit go through a killing block (default = 50)"));
149
150//===----------------------------------------------------------------------===//
151// Helper functions
152//===----------------------------------------------------------------------===//
153using OverlapIntervalsTy = std::map<int64_t, int64_t>;
154using InstOverlapIntervalsTy = DenseMap<Instruction *, OverlapIntervalsTy>;
155
156/// Delete this instruction. Before we do, go through and zero out all the
157/// operands of this instruction. If any of them become dead, delete them and
158/// the computation tree that feeds them.
159/// If ValueSet is non-null, remove any deleted instructions from it as well.
160static void
161deleteDeadInstruction(Instruction *I, BasicBlock::iterator *BBI,
162 MemoryDependenceResults &MD, const TargetLibraryInfo &TLI,
163 InstOverlapIntervalsTy &IOL,
164 MapVector<Instruction *, bool> &ThrowableInst,
165 SmallSetVector<const Value *, 16> *ValueSet = nullptr) {
166 SmallVector<Instruction*, 32> NowDeadInsts;
167
168 NowDeadInsts.push_back(I);
169 --NumFastOther;
170
171 // Keeping the iterator straight is a pain, so we let this routine tell the
172 // caller what the next instruction is after we're done mucking about.
173 BasicBlock::iterator NewIter = *BBI;
174
175 // Before we touch this instruction, remove it from memdep!
176 do {
177 Instruction *DeadInst = NowDeadInsts.pop_back_val();
178 // Mark the DeadInst as dead in the list of throwable instructions.
179 auto It = ThrowableInst.find(DeadInst);
180 if (It != ThrowableInst.end())
181 ThrowableInst[It->first] = false;
182 ++NumFastOther;
183
184 // Try to preserve debug information attached to the dead instruction.
185 salvageDebugInfo(*DeadInst);
186 salvageKnowledge(DeadInst);
187
188 // This instruction is dead, zap it, in stages. Start by removing it from
189 // MemDep, which needs to know the operands and needs it to be in the
190 // function.
191 MD.removeInstruction(DeadInst);
192
193 for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
194 Value *Op = DeadInst->getOperand(op);
195 DeadInst->setOperand(op, nullptr);
196
197 // If this operand just became dead, add it to the NowDeadInsts list.
198 if (!Op->use_empty()) continue;
199
200 if (Instruction *OpI = dyn_cast<Instruction>(Op))
201 if (isInstructionTriviallyDead(OpI, &TLI))
202 NowDeadInsts.push_back(OpI);
203 }
204
205 if (ValueSet) ValueSet->remove(DeadInst);
206 IOL.erase(DeadInst);
207
208 if (NewIter == DeadInst->getIterator())
209 NewIter = DeadInst->eraseFromParent();
210 else
211 DeadInst->eraseFromParent();
212 } while (!NowDeadInsts.empty());
213 *BBI = NewIter;
214 // Pop dead entries from back of ThrowableInst till we find an alive entry.
215 while (!ThrowableInst.empty() && !ThrowableInst.back().second)
216 ThrowableInst.pop_back();
217}
218
219/// Does this instruction write some memory? This only returns true for things
220/// that we can analyze with other helpers below.
221static bool hasAnalyzableMemoryWrite(Instruction *I,
222 const TargetLibraryInfo &TLI) {
223 if (isa<StoreInst>(I))
224 return true;
225 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
226 switch (II->getIntrinsicID()) {
227 default:
228 return false;
229 case Intrinsic::memset:
230 case Intrinsic::memmove:
231 case Intrinsic::memcpy:
232 case Intrinsic::memcpy_inline:
233 case Intrinsic::memcpy_element_unordered_atomic:
234 case Intrinsic::memmove_element_unordered_atomic:
235 case Intrinsic::memset_element_unordered_atomic:
236 case Intrinsic::init_trampoline:
237 case Intrinsic::lifetime_end:
238 case Intrinsic::masked_store:
239 return true;
240 }
241 }
242 if (auto *CB = dyn_cast<CallBase>(I)) {
243 LibFunc LF;
244 if (TLI.getLibFunc(*CB, LF) && TLI.has(LF)) {
245 switch (LF) {
246 case LibFunc_strcpy:
247 case LibFunc_strncpy:
248 case LibFunc_strcat:
249 case LibFunc_strncat:
250 return true;
251 default:
252 return false;
253 }
254 }
255 }
256 return false;
257}
258
259/// Return a Location stored to by the specified instruction. If isRemovable
260/// returns true, this function and getLocForRead completely describe the memory
261/// operations for this instruction.
262static MemoryLocation getLocForWrite(Instruction *Inst,
263 const TargetLibraryInfo &TLI) {
264 if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
265 return MemoryLocation::get(SI);
266
267 // memcpy/memmove/memset.
268 if (auto *MI = dyn_cast<AnyMemIntrinsic>(Inst))
269 return MemoryLocation::getForDest(MI);
270
271 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
272 switch (II->getIntrinsicID()) {
273 default:
274 return MemoryLocation(); // Unhandled intrinsic.
275 case Intrinsic::init_trampoline:
276 return MemoryLocation::getAfter(II->getArgOperand(0));
277 case Intrinsic::masked_store:
278 return MemoryLocation::getForArgument(II, 1, TLI);
279 case Intrinsic::lifetime_end: {
280 uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue();
281 return MemoryLocation(II->getArgOperand(1), Len);
282 }
283 }
284 }
285 if (auto *CB = dyn_cast<CallBase>(Inst))
286 // All the supported TLI functions so far happen to have dest as their
287 // first argument.
288 return MemoryLocation::getAfter(CB->getArgOperand(0));
289 return MemoryLocation();
290}
291
292/// Return the location read by the specified "hasAnalyzableMemoryWrite"
293/// instruction if any.
294static MemoryLocation getLocForRead(Instruction *Inst,
295 const TargetLibraryInfo &TLI) {
296 assert(hasAnalyzableMemoryWrite(Inst, TLI) && "Unknown instruction case")((hasAnalyzableMemoryWrite(Inst, TLI) && "Unknown instruction case"
) ? static_cast<void> (0) : __assert_fail ("hasAnalyzableMemoryWrite(Inst, TLI) && \"Unknown instruction case\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 296, __PRETTY_FUNCTION__))
;
297
298 // The only instructions that both read and write are the mem transfer
299 // instructions (memcpy/memmove).
300 if (auto *MTI = dyn_cast<AnyMemTransferInst>(Inst))
301 return MemoryLocation::getForSource(MTI);
302 return MemoryLocation();
303}
304
305/// If the value of this instruction and the memory it writes to is unused, may
306/// we delete this instruction?
307static bool isRemovable(Instruction *I) {
308 // Don't remove volatile/atomic stores.
309 if (StoreInst *SI = dyn_cast<StoreInst>(I))
310 return SI->isUnordered();
311
312 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
313 switch (II->getIntrinsicID()) {
314 default: llvm_unreachable("doesn't pass 'hasAnalyzableMemoryWrite' predicate")::llvm::llvm_unreachable_internal("doesn't pass 'hasAnalyzableMemoryWrite' predicate"
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 314)
;
315 case Intrinsic::lifetime_end:
316 // Never remove dead lifetime_end's, e.g. because it is followed by a
317 // free.
318 return false;
319 case Intrinsic::init_trampoline:
320 // Always safe to remove init_trampoline.
321 return true;
322 case Intrinsic::memset:
323 case Intrinsic::memmove:
324 case Intrinsic::memcpy:
325 case Intrinsic::memcpy_inline:
326 // Don't remove volatile memory intrinsics.
327 return !cast<MemIntrinsic>(II)->isVolatile();
328 case Intrinsic::memcpy_element_unordered_atomic:
329 case Intrinsic::memmove_element_unordered_atomic:
330 case Intrinsic::memset_element_unordered_atomic:
331 case Intrinsic::masked_store:
332 return true;
333 }
334 }
335
336 // note: only get here for calls with analyzable writes - i.e. libcalls
337 if (auto *CB = dyn_cast<CallBase>(I))
338 return CB->use_empty();
339
340 return false;
341}
342
343/// Returns true if the end of this instruction can be safely shortened in
344/// length.
345static bool isShortenableAtTheEnd(Instruction *I) {
346 // Don't shorten stores for now
347 if (isa<StoreInst>(I))
348 return false;
349
350 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
351 switch (II->getIntrinsicID()) {
352 default: return false;
353 case Intrinsic::memset:
354 case Intrinsic::memcpy:
355 case Intrinsic::memcpy_element_unordered_atomic:
356 case Intrinsic::memset_element_unordered_atomic:
357 // Do shorten memory intrinsics.
358 // FIXME: Add memmove if it's also safe to transform.
359 return true;
360 }
361 }
362
363 // Don't shorten libcalls calls for now.
364
365 return false;
366}
367
368/// Returns true if the beginning of this instruction can be safely shortened
369/// in length.
370static bool isShortenableAtTheBeginning(Instruction *I) {
371 // FIXME: Handle only memset for now. Supporting memcpy/memmove should be
372 // easily done by offsetting the source address.
373 return isa<AnyMemSetInst>(I);
374}
375
376/// Return the pointer that is being written to.
377static Value *getStoredPointerOperand(Instruction *I,
378 const TargetLibraryInfo &TLI) {
379 //TODO: factor this to reuse getLocForWrite
380 MemoryLocation Loc = getLocForWrite(I, TLI);
381 assert(Loc.Ptr &&((Loc.Ptr && "unable to find pointer written for analyzable instruction?"
) ? static_cast<void> (0) : __assert_fail ("Loc.Ptr && \"unable to find pointer written for analyzable instruction?\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 382, __PRETTY_FUNCTION__))
382 "unable to find pointer written for analyzable instruction?")((Loc.Ptr && "unable to find pointer written for analyzable instruction?"
) ? static_cast<void> (0) : __assert_fail ("Loc.Ptr && \"unable to find pointer written for analyzable instruction?\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 382, __PRETTY_FUNCTION__))
;
383 // TODO: most APIs don't expect const Value *
384 return const_cast<Value*>(Loc.Ptr);
385}
386
387static uint64_t getPointerSize(const Value *V, const DataLayout &DL,
388 const TargetLibraryInfo &TLI,
389 const Function *F) {
390 uint64_t Size;
391 ObjectSizeOpts Opts;
392 Opts.NullIsUnknownSize = NullPointerIsDefined(F);
393
394 if (getObjectSize(V, Size, DL, &TLI, Opts))
395 return Size;
396 return MemoryLocation::UnknownSize;
397}
398
399namespace {
400
401enum OverwriteResult {
402 OW_Begin,
403 OW_Complete,
404 OW_End,
405 OW_PartialEarlierWithFullLater,
406 OW_MaybePartial,
407 OW_Unknown
408};
409
410} // end anonymous namespace
411
412/// Check if two instruction are masked stores that completely
413/// overwrite one another. More specifically, \p Later has to
414/// overwrite \p Earlier.
415template <typename AATy>
416static OverwriteResult isMaskedStoreOverwrite(const Instruction *Later,
417 const Instruction *Earlier,
418 AATy &AA) {
419 const auto *IIL = dyn_cast<IntrinsicInst>(Later);
420 const auto *IIE = dyn_cast<IntrinsicInst>(Earlier);
421 if (IIL == nullptr || IIE == nullptr)
422 return OW_Unknown;
423 if (IIL->getIntrinsicID() != Intrinsic::masked_store ||
424 IIE->getIntrinsicID() != Intrinsic::masked_store)
425 return OW_Unknown;
426 // Pointers.
427 Value *LP = IIL->getArgOperand(1)->stripPointerCasts();
428 Value *EP = IIE->getArgOperand(1)->stripPointerCasts();
429 if (LP != EP && !AA.isMustAlias(LP, EP))
430 return OW_Unknown;
431 // Masks.
432 // TODO: check that Later's mask is a superset of the Earlier's mask.
433 if (IIL->getArgOperand(3) != IIE->getArgOperand(3))
434 return OW_Unknown;
435 return OW_Complete;
436}
437
438/// Return 'OW_Complete' if a store to the 'Later' location (by \p LaterI
439/// instruction) completely overwrites a store to the 'Earlier' location.
440/// (by \p EarlierI instruction).
441/// Return OW_MaybePartial if \p Later does not completely overwrite
442/// \p Earlier, but they both write to the same underlying object. In that
443/// case, use isPartialOverwrite to check if \p Later partially overwrites
444/// \p Earlier. Returns 'OW_Unknown' if nothing can be determined.
445template <typename AATy>
446static OverwriteResult
447isOverwrite(const Instruction *LaterI, const Instruction *EarlierI,
448 const MemoryLocation &Later, const MemoryLocation &Earlier,
449 const DataLayout &DL, const TargetLibraryInfo &TLI,
450 int64_t &EarlierOff, int64_t &LaterOff, AATy &AA,
451 const Function *F) {
452 // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
453 // get imprecise values here, though (except for unknown sizes).
454 if (!Later.Size.isPrecise() || !Earlier.Size.isPrecise()) {
455 // Masked stores have imprecise locations, but we can reason about them
456 // to some extent.
457 return isMaskedStoreOverwrite(LaterI, EarlierI, AA);
458 }
459
460 const uint64_t LaterSize = Later.Size.getValue();
461 const uint64_t EarlierSize = Earlier.Size.getValue();
462
463 const Value *P1 = Earlier.Ptr->stripPointerCasts();
464 const Value *P2 = Later.Ptr->stripPointerCasts();
465
466 // If the start pointers are the same, we just have to compare sizes to see if
467 // the later store was larger than the earlier store.
468 if (P1 == P2 || AA.isMustAlias(P1, P2)) {
469 // Make sure that the Later size is >= the Earlier size.
470 if (LaterSize >= EarlierSize)
471 return OW_Complete;
472 }
473
474 // Check to see if the later store is to the entire object (either a global,
475 // an alloca, or a byval/inalloca argument). If so, then it clearly
476 // overwrites any other store to the same object.
477 const Value *UO1 = getUnderlyingObject(P1), *UO2 = getUnderlyingObject(P2);
478
479 // If we can't resolve the same pointers to the same object, then we can't
480 // analyze them at all.
481 if (UO1 != UO2)
482 return OW_Unknown;
483
484 // If the "Later" store is to a recognizable object, get its size.
485 uint64_t ObjectSize = getPointerSize(UO2, DL, TLI, F);
486 if (ObjectSize != MemoryLocation::UnknownSize)
487 if (ObjectSize == LaterSize && ObjectSize >= EarlierSize)
488 return OW_Complete;
489
490 // Okay, we have stores to two completely different pointers. Try to
491 // decompose the pointer into a "base + constant_offset" form. If the base
492 // pointers are equal, then we can reason about the two stores.
493 EarlierOff = 0;
494 LaterOff = 0;
495 const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, DL);
496 const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, DL);
497
498 // If the base pointers still differ, we have two completely different stores.
499 if (BP1 != BP2)
500 return OW_Unknown;
501
502 // The later access completely overlaps the earlier store if and only if
503 // both start and end of the earlier one is "inside" the later one:
504 // |<->|--earlier--|<->|
505 // |-------later-------|
506 // Accesses may overlap if and only if start of one of them is "inside"
507 // another one:
508 // |<->|--earlier--|<----->|
509 // |-------later-------|
510 // OR
511 // |----- earlier -----|
512 // |<->|---later---|<----->|
513 //
514 // We have to be careful here as *Off is signed while *.Size is unsigned.
515
516 // Check if the earlier access starts "not before" the later one.
517 if (EarlierOff >= LaterOff) {
518 // If the earlier access ends "not after" the later access then the earlier
519 // one is completely overwritten by the later one.
520 if (uint64_t(EarlierOff - LaterOff) + EarlierSize <= LaterSize)
521 return OW_Complete;
522 // If start of the earlier access is "before" end of the later access then
523 // accesses overlap.
524 else if ((uint64_t)(EarlierOff - LaterOff) < LaterSize)
525 return OW_MaybePartial;
526 }
527 // If start of the later access is "before" end of the earlier access then
528 // accesses overlap.
529 else if ((uint64_t)(LaterOff - EarlierOff) < EarlierSize) {
530 return OW_MaybePartial;
531 }
532
533 // Can reach here only if accesses are known not to overlap. There is no
534 // dedicated code to indicate no overlap so signal "unknown".
535 return OW_Unknown;
536}
537
538/// Return 'OW_Complete' if a store to the 'Later' location completely
539/// overwrites a store to the 'Earlier' location, 'OW_End' if the end of the
540/// 'Earlier' location is completely overwritten by 'Later', 'OW_Begin' if the
541/// beginning of the 'Earlier' location is overwritten by 'Later'.
542/// 'OW_PartialEarlierWithFullLater' means that an earlier (big) store was
543/// overwritten by a latter (smaller) store which doesn't write outside the big
544/// store's memory locations. Returns 'OW_Unknown' if nothing can be determined.
545/// NOTE: This function must only be called if both \p Later and \p Earlier
546/// write to the same underlying object with valid \p EarlierOff and \p
547/// LaterOff.
548static OverwriteResult isPartialOverwrite(const MemoryLocation &Later,
549 const MemoryLocation &Earlier,
550 int64_t EarlierOff, int64_t LaterOff,
551 Instruction *DepWrite,
552 InstOverlapIntervalsTy &IOL) {
553 const uint64_t LaterSize = Later.Size.getValue();
554 const uint64_t EarlierSize = Earlier.Size.getValue();
555 // We may now overlap, although the overlap is not complete. There might also
556 // be other incomplete overlaps, and together, they might cover the complete
557 // earlier write.
558 // Note: The correctness of this logic depends on the fact that this function
559 // is not even called providing DepWrite when there are any intervening reads.
560 if (EnablePartialOverwriteTracking &&
561 LaterOff < int64_t(EarlierOff + EarlierSize) &&
562 int64_t(LaterOff + LaterSize) >= EarlierOff) {
563
564 // Insert our part of the overlap into the map.
565 auto &IM = IOL[DepWrite];
566 LLVM_DEBUG(dbgs() << "DSE: Partial overwrite: Earlier [" << EarlierOffdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite: Earlier ["
<< EarlierOff << ", " << int64_t(EarlierOff
+ EarlierSize) << ") Later [" << LaterOff <<
", " << int64_t(LaterOff + LaterSize) << ")\n"; }
} while (false)
567 << ", " << int64_t(EarlierOff + EarlierSize)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite: Earlier ["
<< EarlierOff << ", " << int64_t(EarlierOff
+ EarlierSize) << ") Later [" << LaterOff <<
", " << int64_t(LaterOff + LaterSize) << ")\n"; }
} while (false)
568 << ") Later [" << LaterOff << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite: Earlier ["
<< EarlierOff << ", " << int64_t(EarlierOff
+ EarlierSize) << ") Later [" << LaterOff <<
", " << int64_t(LaterOff + LaterSize) << ")\n"; }
} while (false)
569 << int64_t(LaterOff + LaterSize) << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite: Earlier ["
<< EarlierOff << ", " << int64_t(EarlierOff
+ EarlierSize) << ") Later [" << LaterOff <<
", " << int64_t(LaterOff + LaterSize) << ")\n"; }
} while (false)
;
570
571 // Make sure that we only insert non-overlapping intervals and combine
572 // adjacent intervals. The intervals are stored in the map with the ending
573 // offset as the key (in the half-open sense) and the starting offset as
574 // the value.
575 int64_t LaterIntStart = LaterOff, LaterIntEnd = LaterOff + LaterSize;
576
577 // Find any intervals ending at, or after, LaterIntStart which start
578 // before LaterIntEnd.
579 auto ILI = IM.lower_bound(LaterIntStart);
580 if (ILI != IM.end() && ILI->second <= LaterIntEnd) {
581 // This existing interval is overlapped with the current store somewhere
582 // in [LaterIntStart, LaterIntEnd]. Merge them by erasing the existing
583 // intervals and adjusting our start and end.
584 LaterIntStart = std::min(LaterIntStart, ILI->second);
585 LaterIntEnd = std::max(LaterIntEnd, ILI->first);
586 ILI = IM.erase(ILI);
587
588 // Continue erasing and adjusting our end in case other previous
589 // intervals are also overlapped with the current store.
590 //
591 // |--- ealier 1 ---| |--- ealier 2 ---|
592 // |------- later---------|
593 //
594 while (ILI != IM.end() && ILI->second <= LaterIntEnd) {
595 assert(ILI->second > LaterIntStart && "Unexpected interval")((ILI->second > LaterIntStart && "Unexpected interval"
) ? static_cast<void> (0) : __assert_fail ("ILI->second > LaterIntStart && \"Unexpected interval\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 595, __PRETTY_FUNCTION__))
;
596 LaterIntEnd = std::max(LaterIntEnd, ILI->first);
597 ILI = IM.erase(ILI);
598 }
599 }
600
601 IM[LaterIntEnd] = LaterIntStart;
602
603 ILI = IM.begin();
604 if (ILI->second <= EarlierOff &&
605 ILI->first >= int64_t(EarlierOff + EarlierSize)) {
606 LLVM_DEBUG(dbgs() << "DSE: Full overwrite from partials: Earlier ["do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Full overwrite from partials: Earlier ["
<< EarlierOff << ", " << int64_t(EarlierOff
+ EarlierSize) << ") Composite Later [" << ILI->
second << ", " << ILI->first << ")\n"; }
} while (false)
607 << EarlierOff << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Full overwrite from partials: Earlier ["
<< EarlierOff << ", " << int64_t(EarlierOff
+ EarlierSize) << ") Composite Later [" << ILI->
second << ", " << ILI->first << ")\n"; }
} while (false)
608 << int64_t(EarlierOff + EarlierSize)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Full overwrite from partials: Earlier ["
<< EarlierOff << ", " << int64_t(EarlierOff
+ EarlierSize) << ") Composite Later [" << ILI->
second << ", " << ILI->first << ")\n"; }
} while (false)
609 << ") Composite Later [" << ILI->second << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Full overwrite from partials: Earlier ["
<< EarlierOff << ", " << int64_t(EarlierOff
+ EarlierSize) << ") Composite Later [" << ILI->
second << ", " << ILI->first << ")\n"; }
} while (false)
610 << ILI->first << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Full overwrite from partials: Earlier ["
<< EarlierOff << ", " << int64_t(EarlierOff
+ EarlierSize) << ") Composite Later [" << ILI->
second << ", " << ILI->first << ")\n"; }
} while (false)
;
611 ++NumCompletePartials;
612 return OW_Complete;
613 }
614 }
615
616 // Check for an earlier store which writes to all the memory locations that
617 // the later store writes to.
618 if (EnablePartialStoreMerging && LaterOff >= EarlierOff &&
619 int64_t(EarlierOff + EarlierSize) > LaterOff &&
620 uint64_t(LaterOff - EarlierOff) + LaterSize <= EarlierSize) {
621 LLVM_DEBUG(dbgs() << "DSE: Partial overwrite an earlier load ["do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite an earlier load ["
<< EarlierOff << ", " << int64_t(EarlierOff
+ EarlierSize) << ") by a later store [" << LaterOff
<< ", " << int64_t(LaterOff + LaterSize) <<
")\n"; } } while (false)
622 << EarlierOff << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite an earlier load ["
<< EarlierOff << ", " << int64_t(EarlierOff
+ EarlierSize) << ") by a later store [" << LaterOff
<< ", " << int64_t(LaterOff + LaterSize) <<
")\n"; } } while (false)
623 << int64_t(EarlierOff + EarlierSize)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite an earlier load ["
<< EarlierOff << ", " << int64_t(EarlierOff
+ EarlierSize) << ") by a later store [" << LaterOff
<< ", " << int64_t(LaterOff + LaterSize) <<
")\n"; } } while (false)
624 << ") by a later store [" << LaterOff << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite an earlier load ["
<< EarlierOff << ", " << int64_t(EarlierOff
+ EarlierSize) << ") by a later store [" << LaterOff
<< ", " << int64_t(LaterOff + LaterSize) <<
")\n"; } } while (false)
625 << int64_t(LaterOff + LaterSize) << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite an earlier load ["
<< EarlierOff << ", " << int64_t(EarlierOff
+ EarlierSize) << ") by a later store [" << LaterOff
<< ", " << int64_t(LaterOff + LaterSize) <<
")\n"; } } while (false)
;
626 // TODO: Maybe come up with a better name?
627 return OW_PartialEarlierWithFullLater;
628 }
629
630 // Another interesting case is if the later store overwrites the end of the
631 // earlier store.
632 //
633 // |--earlier--|
634 // |-- later --|
635 //
636 // In this case we may want to trim the size of earlier to avoid generating
637 // writes to addresses which will definitely be overwritten later
638 if (!EnablePartialOverwriteTracking &&
639 (LaterOff > EarlierOff && LaterOff < int64_t(EarlierOff + EarlierSize) &&
640 int64_t(LaterOff + LaterSize) >= int64_t(EarlierOff + EarlierSize)))
641 return OW_End;
642
643 // Finally, we also need to check if the later store overwrites the beginning
644 // of the earlier store.
645 //
646 // |--earlier--|
647 // |-- later --|
648 //
649 // In this case we may want to move the destination address and trim the size
650 // of earlier to avoid generating writes to addresses which will definitely
651 // be overwritten later.
652 if (!EnablePartialOverwriteTracking &&
653 (LaterOff <= EarlierOff && int64_t(LaterOff + LaterSize) > EarlierOff)) {
654 assert(int64_t(LaterOff + LaterSize) < int64_t(EarlierOff + EarlierSize) &&((int64_t(LaterOff + LaterSize) < int64_t(EarlierOff + EarlierSize
) && "Expect to be handled as OW_Complete") ? static_cast
<void> (0) : __assert_fail ("int64_t(LaterOff + LaterSize) < int64_t(EarlierOff + EarlierSize) && \"Expect to be handled as OW_Complete\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 655, __PRETTY_FUNCTION__))
655 "Expect to be handled as OW_Complete")((int64_t(LaterOff + LaterSize) < int64_t(EarlierOff + EarlierSize
) && "Expect to be handled as OW_Complete") ? static_cast
<void> (0) : __assert_fail ("int64_t(LaterOff + LaterSize) < int64_t(EarlierOff + EarlierSize) && \"Expect to be handled as OW_Complete\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 655, __PRETTY_FUNCTION__))
;
656 return OW_Begin;
657 }
658 // Otherwise, they don't completely overlap.
659 return OW_Unknown;
660}
661
662/// If 'Inst' might be a self read (i.e. a noop copy of a
663/// memory region into an identical pointer) then it doesn't actually make its
664/// input dead in the traditional sense. Consider this case:
665///
666/// memmove(A <- B)
667/// memmove(A <- A)
668///
669/// In this case, the second store to A does not make the first store to A dead.
670/// The usual situation isn't an explicit A<-A store like this (which can be
671/// trivially removed) but a case where two pointers may alias.
672///
673/// This function detects when it is unsafe to remove a dependent instruction
674/// because the DSE inducing instruction may be a self-read.
675static bool isPossibleSelfRead(Instruction *Inst,
676 const MemoryLocation &InstStoreLoc,
677 Instruction *DepWrite,
678 const TargetLibraryInfo &TLI,
679 AliasAnalysis &AA) {
680 // Self reads can only happen for instructions that read memory. Get the
681 // location read.
682 MemoryLocation InstReadLoc = getLocForRead(Inst, TLI);
683 if (!InstReadLoc.Ptr)
684 return false; // Not a reading instruction.
685
686 // If the read and written loc obviously don't alias, it isn't a read.
687 if (AA.isNoAlias(InstReadLoc, InstStoreLoc))
688 return false;
689
690 if (isa<AnyMemCpyInst>(Inst)) {
691 // LLVM's memcpy overlap semantics are not fully fleshed out (see PR11763)
692 // but in practice memcpy(A <- B) either means that A and B are disjoint or
693 // are equal (i.e. there are not partial overlaps). Given that, if we have:
694 //
695 // memcpy/memmove(A <- B) // DepWrite
696 // memcpy(A <- B) // Inst
697 //
698 // with Inst reading/writing a >= size than DepWrite, we can reason as
699 // follows:
700 //
701 // - If A == B then both the copies are no-ops, so the DepWrite can be
702 // removed.
703 // - If A != B then A and B are disjoint locations in Inst. Since
704 // Inst.size >= DepWrite.size A and B are disjoint in DepWrite too.
705 // Therefore DepWrite can be removed.
706 MemoryLocation DepReadLoc = getLocForRead(DepWrite, TLI);
707
708 if (DepReadLoc.Ptr && AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr))
709 return false;
710 }
711
712 // If DepWrite doesn't read memory or if we can't prove it is a must alias,
713 // then it can't be considered dead.
714 return true;
715}
716
717/// Returns true if the memory which is accessed by the second instruction is not
718/// modified between the first and the second instruction.
719/// Precondition: Second instruction must be dominated by the first
720/// instruction.
721template <typename AATy>
722static bool
723memoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI, AATy &AA,
724 const DataLayout &DL, DominatorTree *DT) {
725 // Do a backwards scan through the CFG from SecondI to FirstI. Look for
726 // instructions which can modify the memory location accessed by SecondI.
727 //
728 // While doing the walk keep track of the address to check. It might be
729 // different in different basic blocks due to PHI translation.
730 using BlockAddressPair = std::pair<BasicBlock *, PHITransAddr>;
731 SmallVector<BlockAddressPair, 16> WorkList;
732 // Keep track of the address we visited each block with. Bail out if we
733 // visit a block with different addresses.
734 DenseMap<BasicBlock *, Value *> Visited;
735
736 BasicBlock::iterator FirstBBI(FirstI);
737 ++FirstBBI;
738 BasicBlock::iterator SecondBBI(SecondI);
739 BasicBlock *FirstBB = FirstI->getParent();
740 BasicBlock *SecondBB = SecondI->getParent();
741 MemoryLocation MemLoc = MemoryLocation::get(SecondI);
742 auto *MemLocPtr = const_cast<Value *>(MemLoc.Ptr);
743
744 // Start checking the SecondBB.
745 WorkList.push_back(
746 std::make_pair(SecondBB, PHITransAddr(MemLocPtr, DL, nullptr)));
747 bool isFirstBlock = true;
748
749 // Check all blocks going backward until we reach the FirstBB.
750 while (!WorkList.empty()) {
751 BlockAddressPair Current = WorkList.pop_back_val();
752 BasicBlock *B = Current.first;
753 PHITransAddr &Addr = Current.second;
754 Value *Ptr = Addr.getAddr();
755
756 // Ignore instructions before FirstI if this is the FirstBB.
757 BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());
758
759 BasicBlock::iterator EI;
760 if (isFirstBlock) {
761 // Ignore instructions after SecondI if this is the first visit of SecondBB.
762 assert(B == SecondBB && "first block is not the store block")((B == SecondBB && "first block is not the store block"
) ? static_cast<void> (0) : __assert_fail ("B == SecondBB && \"first block is not the store block\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 762, __PRETTY_FUNCTION__))
;
763 EI = SecondBBI;
764 isFirstBlock = false;
765 } else {
766 // It's not SecondBB or (in case of a loop) the second visit of SecondBB.
767 // In this case we also have to look at instructions after SecondI.
768 EI = B->end();
769 }
770 for (; BI != EI; ++BI) {
771 Instruction *I = &*BI;
772 if (I->mayWriteToMemory() && I != SecondI)
773 if (isModSet(AA.getModRefInfo(I, MemLoc.getWithNewPtr(Ptr))))
774 return false;
775 }
776 if (B != FirstBB) {
777 assert(B != &FirstBB->getParent()->getEntryBlock() &&((B != &FirstBB->getParent()->getEntryBlock() &&
"Should not hit the entry block because SI must be dominated by LI"
) ? static_cast<void> (0) : __assert_fail ("B != &FirstBB->getParent()->getEntryBlock() && \"Should not hit the entry block because SI must be dominated by LI\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 778, __PRETTY_FUNCTION__))
778 "Should not hit the entry block because SI must be dominated by LI")((B != &FirstBB->getParent()->getEntryBlock() &&
"Should not hit the entry block because SI must be dominated by LI"
) ? static_cast<void> (0) : __assert_fail ("B != &FirstBB->getParent()->getEntryBlock() && \"Should not hit the entry block because SI must be dominated by LI\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 778, __PRETTY_FUNCTION__))
;
779 for (BasicBlock *Pred : predecessors(B)) {
780 PHITransAddr PredAddr = Addr;
781 if (PredAddr.NeedsPHITranslationFromBlock(B)) {
782 if (!PredAddr.IsPotentiallyPHITranslatable())
783 return false;
784 if (PredAddr.PHITranslateValue(B, Pred, DT, false))
785 return false;
786 }
787 Value *TranslatedPtr = PredAddr.getAddr();
788 auto Inserted = Visited.insert(std::make_pair(Pred, TranslatedPtr));
789 if (!Inserted.second) {
790 // We already visited this block before. If it was with a different
791 // address - bail out!
792 if (TranslatedPtr != Inserted.first->second)
793 return false;
794 // ... otherwise just skip it.
795 continue;
796 }
797 WorkList.push_back(std::make_pair(Pred, PredAddr));
798 }
799 }
800 }
801 return true;
802}
803
804/// Find all blocks that will unconditionally lead to the block BB and append
805/// them to F.
806static void findUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks,
807 BasicBlock *BB, DominatorTree *DT) {
808 for (BasicBlock *Pred : predecessors(BB)) {
809 if (Pred == BB) continue;
810 Instruction *PredTI = Pred->getTerminator();
811 if (PredTI->getNumSuccessors() != 1)
812 continue;
813
814 if (DT->isReachableFromEntry(Pred))
815 Blocks.push_back(Pred);
816 }
817}
818
819/// Handle frees of entire structures whose dependency is a store
820/// to a field of that structure.
821static bool handleFree(CallInst *F, AliasAnalysis *AA,
822 MemoryDependenceResults *MD, DominatorTree *DT,
823 const TargetLibraryInfo *TLI,
824 InstOverlapIntervalsTy &IOL,
825 MapVector<Instruction *, bool> &ThrowableInst) {
826 bool MadeChange = false;
827
828 MemoryLocation Loc = MemoryLocation::getAfter(F->getOperand(0));
829 SmallVector<BasicBlock *, 16> Blocks;
830 Blocks.push_back(F->getParent());
831
832 while (!Blocks.empty()) {
833 BasicBlock *BB = Blocks.pop_back_val();
834 Instruction *InstPt = BB->getTerminator();
835 if (BB == F->getParent()) InstPt = F;
836
837 MemDepResult Dep =
838 MD->getPointerDependencyFrom(Loc, false, InstPt->getIterator(), BB);
839 while (Dep.isDef() || Dep.isClobber()) {
840 Instruction *Dependency = Dep.getInst();
841 if (!hasAnalyzableMemoryWrite(Dependency, *TLI) ||
842 !isRemovable(Dependency))
843 break;
844
845 Value *DepPointer =
846 getUnderlyingObject(getStoredPointerOperand(Dependency, *TLI));
847
848 // Check for aliasing.
849 if (!AA->isMustAlias(F->getArgOperand(0), DepPointer))
850 break;
851
852 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store to soon to be freed memory:\n DEAD: "
<< *Dependency << '\n'; } } while (false)
853 dbgs() << "DSE: Dead Store to soon to be freed memory:\n DEAD: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store to soon to be freed memory:\n DEAD: "
<< *Dependency << '\n'; } } while (false)
854 << *Dependency << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store to soon to be freed memory:\n DEAD: "
<< *Dependency << '\n'; } } while (false)
;
855
856 // DCE instructions only used to calculate that store.
857 BasicBlock::iterator BBI(Dependency);
858 deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, IOL,
859 ThrowableInst);
860 ++NumFastStores;
861 MadeChange = true;
862
863 // Inst's old Dependency is now deleted. Compute the next dependency,
864 // which may also be dead, as in
865 // s[0] = 0;
866 // s[1] = 0; // This has just been deleted.
867 // free(s);
868 Dep = MD->getPointerDependencyFrom(Loc, false, BBI, BB);
869 }
870
871 if (Dep.isNonLocal())
872 findUnconditionalPreds(Blocks, BB, DT);
873 }
874
875 return MadeChange;
876}
877
878/// Check to see if the specified location may alias any of the stack objects in
879/// the DeadStackObjects set. If so, they become live because the location is
880/// being loaded.
881static void removeAccessedObjects(const MemoryLocation &LoadedLoc,
882 SmallSetVector<const Value *, 16> &DeadStackObjects,
883 const DataLayout &DL, AliasAnalysis *AA,
884 const TargetLibraryInfo *TLI,
885 const Function *F) {
886 const Value *UnderlyingPointer = getUnderlyingObject(LoadedLoc.Ptr);
887
888 // A constant can't be in the dead pointer set.
889 if (isa<Constant>(UnderlyingPointer))
890 return;
891
892 // If the kill pointer can be easily reduced to an alloca, don't bother doing
893 // extraneous AA queries.
894 if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) {
895 DeadStackObjects.remove(UnderlyingPointer);
896 return;
897 }
898
899 // Remove objects that could alias LoadedLoc.
900 DeadStackObjects.remove_if([&](const Value *I) {
901 // See if the loaded location could alias the stack location.
902 MemoryLocation StackLoc(I, getPointerSize(I, DL, *TLI, F));
903 return !AA->isNoAlias(StackLoc, LoadedLoc);
904 });
905}
906
907/// Remove dead stores to stack-allocated locations in the function end block.
908/// Ex:
909/// %A = alloca i32
910/// ...
911/// store i32 1, i32* %A
912/// ret void
913static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA,
914 MemoryDependenceResults *MD,
915 const TargetLibraryInfo *TLI,
916 InstOverlapIntervalsTy &IOL,
917 MapVector<Instruction *, bool> &ThrowableInst) {
918 bool MadeChange = false;
919
920 // Keep track of all of the stack objects that are dead at the end of the
921 // function.
922 SmallSetVector<const Value*, 16> DeadStackObjects;
923
924 // Find all of the alloca'd pointers in the entry block.
925 BasicBlock &Entry = BB.getParent()->front();
926 for (Instruction &I : Entry) {
927 if (isa<AllocaInst>(&I))
928 DeadStackObjects.insert(&I);
929
930 // Okay, so these are dead heap objects, but if the pointer never escapes
931 // then it's leaked by this function anyways.
932 else if (isAllocLikeFn(&I, TLI) && !PointerMayBeCaptured(&I, true, true))
933 DeadStackObjects.insert(&I);
934 }
935
936 // Treat byval or inalloca arguments the same, stores to them are dead at the
937 // end of the function.
938 for (Argument &AI : BB.getParent()->args())
939 if (AI.hasPassPointeeByValueCopyAttr())
940 DeadStackObjects.insert(&AI);
941
942 const DataLayout &DL = BB.getModule()->getDataLayout();
943
944 // Scan the basic block backwards
945 for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
946 --BBI;
947
948 // If we find a store, check to see if it points into a dead stack value.
949 if (hasAnalyzableMemoryWrite(&*BBI, *TLI) && isRemovable(&*BBI)) {
950 // See through pointer-to-pointer bitcasts
951 SmallVector<const Value *, 4> Pointers;
952 getUnderlyingObjects(getStoredPointerOperand(&*BBI, *TLI), Pointers);
953
954 // Stores to stack values are valid candidates for removal.
955 bool AllDead = true;
956 for (const Value *Pointer : Pointers)
957 if (!DeadStackObjects.count(Pointer)) {
958 AllDead = false;
959 break;
960 }
961
962 if (AllDead) {
963 Instruction *Dead = &*BBI;
964
965 LLVM_DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "
<< *Dead << "\n Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
966 << *Dead << "\n Objects: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "
<< *Dead << "\n Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
967 for (SmallVectorImpl<const Value *>::iterator I =do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "
<< *Dead << "\n Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
968 Pointers.begin(),do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "
<< *Dead << "\n Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
969 E = Pointers.end();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "
<< *Dead << "\n Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
970 I != E; ++I) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "
<< *Dead << "\n Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
971 dbgs() << **I;do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "
<< *Dead << "\n Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
972 if (std::next(I) != E)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "
<< *Dead << "\n Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
973 dbgs() << ", ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "
<< *Dead << "\n Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
974 } dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "
<< *Dead << "\n Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
975 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n DEAD: "
<< *Dead << "\n Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
;
976
977 // DCE instructions only used to calculate that store.
978 deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, ThrowableInst,
979 &DeadStackObjects);
980 ++NumFastStores;
981 MadeChange = true;
982 continue;
983 }
984 }
985
986 // Remove any dead non-memory-mutating instructions.
987 if (isInstructionTriviallyDead(&*BBI, TLI)) {
988 LLVM_DEBUG(dbgs() << "DSE: Removing trivially dead instruction:\n DEAD: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Removing trivially dead instruction:\n DEAD: "
<< *&*BBI << '\n'; } } while (false)
989 << *&*BBI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Removing trivially dead instruction:\n DEAD: "
<< *&*BBI << '\n'; } } while (false)
;
990 deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, ThrowableInst,
991 &DeadStackObjects);
992 ++NumFastOther;
993 MadeChange = true;
994 continue;
995 }
996
997 if (isa<AllocaInst>(BBI)) {
998 // Remove allocas from the list of dead stack objects; there can't be
999 // any references before the definition.
1000 DeadStackObjects.remove(&*BBI);
1001 continue;
1002 }
1003
1004 if (auto *Call = dyn_cast<CallBase>(&*BBI)) {
1005 // Remove allocation function calls from the list of dead stack objects;
1006 // there can't be any references before the definition.
1007 if (isAllocLikeFn(&*BBI, TLI))
1008 DeadStackObjects.remove(&*BBI);
1009
1010 // If this call does not access memory, it can't be loading any of our
1011 // pointers.
1012 if (AA->doesNotAccessMemory(Call))
1013 continue;
1014
1015 // If the call might load from any of our allocas, then any store above
1016 // the call is live.
1017 DeadStackObjects.remove_if([&](const Value *I) {
1018 // See if the call site touches the value.
1019 return isRefSet(AA->getModRefInfo(
1020 Call, I, getPointerSize(I, DL, *TLI, BB.getParent())));
1021 });
1022
1023 // If all of the allocas were clobbered by the call then we're not going
1024 // to find anything else to process.
1025 if (DeadStackObjects.empty())
1026 break;
1027
1028 continue;
1029 }
1030
1031 // We can remove the dead stores, irrespective of the fence and its ordering
1032 // (release/acquire/seq_cst). Fences only constraints the ordering of
1033 // already visible stores, it does not make a store visible to other
1034 // threads. So, skipping over a fence does not change a store from being
1035 // dead.
1036 if (isa<FenceInst>(*BBI))
1037 continue;
1038
1039 MemoryLocation LoadedLoc;
1040
1041 // If we encounter a use of the pointer, it is no longer considered dead
1042 if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
1043 if (!L->isUnordered()) // Be conservative with atomic/volatile load
1044 break;
1045 LoadedLoc = MemoryLocation::get(L);
1046 } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
1047 LoadedLoc = MemoryLocation::get(V);
1048 } else if (!BBI->mayReadFromMemory()) {
1049 // Instruction doesn't read memory. Note that stores that weren't removed
1050 // above will hit this case.
1051 continue;
1052 } else {
1053 // Unknown inst; assume it clobbers everything.
1054 break;
1055 }
1056
1057 // Remove any allocas from the DeadPointer set that are loaded, as this
1058 // makes any stores above the access live.
1059 removeAccessedObjects(LoadedLoc, DeadStackObjects, DL, AA, TLI, BB.getParent());
1060
1061 // If all of the allocas were clobbered by the access then we're not going
1062 // to find anything else to process.
1063 if (DeadStackObjects.empty())
1064 break;
1065 }
1066
1067 return MadeChange;
1068}
1069
1070static bool tryToShorten(Instruction *EarlierWrite, int64_t &EarlierOffset,
1071 uint64_t &EarlierSize, int64_t LaterOffset,
1072 uint64_t LaterSize, bool IsOverwriteEnd) {
1073 // TODO: base this on the target vector size so that if the earlier
1074 // store was too small to get vector writes anyway then its likely
1075 // a good idea to shorten it
1076 // Power of 2 vector writes are probably always a bad idea to optimize
1077 // as any store/memset/memcpy is likely using vector instructions so
1078 // shortening it to not vector size is likely to be slower
1079 auto *EarlierIntrinsic = cast<AnyMemIntrinsic>(EarlierWrite);
1080 unsigned EarlierWriteAlign = EarlierIntrinsic->getDestAlignment();
1081 if (!IsOverwriteEnd)
1082 LaterOffset = int64_t(LaterOffset + LaterSize);
1083
1084 if (!(isPowerOf2_64(LaterOffset) && EarlierWriteAlign <= LaterOffset) &&
1085 !((EarlierWriteAlign != 0) && LaterOffset % EarlierWriteAlign == 0))
1086 return false;
1087
1088 int64_t NewLength = IsOverwriteEnd
1089 ? LaterOffset - EarlierOffset
1090 : EarlierSize - (LaterOffset - EarlierOffset);
1091
1092 if (auto *AMI = dyn_cast<AtomicMemIntrinsic>(EarlierWrite)) {
1093 // When shortening an atomic memory intrinsic, the newly shortened
1094 // length must remain an integer multiple of the element size.
1095 const uint32_t ElementSize = AMI->getElementSizeInBytes();
1096 if (0 != NewLength % ElementSize)
1097 return false;
1098 }
1099
1100 LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n OW "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n OW " <<
(IsOverwriteEnd ? "END" : "BEGIN") << ": " << *EarlierWrite
<< "\n KILLER (offset " << LaterOffset <<
", " << EarlierSize << ")\n"; } } while (false)
1101 << (IsOverwriteEnd ? "END" : "BEGIN") << ": "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n OW " <<
(IsOverwriteEnd ? "END" : "BEGIN") << ": " << *EarlierWrite
<< "\n KILLER (offset " << LaterOffset <<
", " << EarlierSize << ")\n"; } } while (false)
1102 << *EarlierWrite << "\n KILLER (offset " << LaterOffsetdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n OW " <<
(IsOverwriteEnd ? "END" : "BEGIN") << ": " << *EarlierWrite
<< "\n KILLER (offset " << LaterOffset <<
", " << EarlierSize << ")\n"; } } while (false)
1103 << ", " << EarlierSize << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n OW " <<
(IsOverwriteEnd ? "END" : "BEGIN") << ": " << *EarlierWrite
<< "\n KILLER (offset " << LaterOffset <<
", " << EarlierSize << ")\n"; } } while (false)
;
1104
1105 Value *EarlierWriteLength = EarlierIntrinsic->getLength();
1106 Value *TrimmedLength =
1107 ConstantInt::get(EarlierWriteLength->getType(), NewLength);
1108 EarlierIntrinsic->setLength(TrimmedLength);
1109
1110 EarlierSize = NewLength;
1111 if (!IsOverwriteEnd) {
1112 int64_t OffsetMoved = (LaterOffset - EarlierOffset);
1113 Value *Indices[1] = {
1114 ConstantInt::get(EarlierWriteLength->getType(), OffsetMoved)};
1115 GetElementPtrInst *NewDestGEP = GetElementPtrInst::CreateInBounds(
1116 EarlierIntrinsic->getRawDest()->getType()->getPointerElementType(),
1117 EarlierIntrinsic->getRawDest(), Indices, "", EarlierWrite);
1118 NewDestGEP->setDebugLoc(EarlierIntrinsic->getDebugLoc());
1119 EarlierIntrinsic->setDest(NewDestGEP);
1120 EarlierOffset = EarlierOffset + OffsetMoved;
1121 }
1122 return true;
1123}
1124
1125static bool tryToShortenEnd(Instruction *EarlierWrite,
1126 OverlapIntervalsTy &IntervalMap,
1127 int64_t &EarlierStart, uint64_t &EarlierSize) {
1128 if (IntervalMap.empty() || !isShortenableAtTheEnd(EarlierWrite))
1129 return false;
1130
1131 OverlapIntervalsTy::iterator OII = --IntervalMap.end();
1132 int64_t LaterStart = OII->second;
1133 uint64_t LaterSize = OII->first - LaterStart;
1134
1135 assert(OII->first - LaterStart >= 0 && "Size expected to be positive")((OII->first - LaterStart >= 0 && "Size expected to be positive"
) ? static_cast<void> (0) : __assert_fail ("OII->first - LaterStart >= 0 && \"Size expected to be positive\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1135, __PRETTY_FUNCTION__))
;
1136
1137 if (LaterStart > EarlierStart &&
1138 // Note: "LaterStart - EarlierStart" is known to be positive due to
1139 // preceding check.
1140 (uint64_t)(LaterStart - EarlierStart) < EarlierSize &&
1141 // Note: "EarlierSize - (uint64_t)(LaterStart - EarlierStart)" is known to
1142 // be non negative due to preceding checks.
1143 LaterSize >= EarlierSize - (uint64_t)(LaterStart - EarlierStart)) {
1144 if (tryToShorten(EarlierWrite, EarlierStart, EarlierSize, LaterStart,
1145 LaterSize, true)) {
1146 IntervalMap.erase(OII);
1147 return true;
1148 }
1149 }
1150 return false;
1151}
1152
1153static bool tryToShortenBegin(Instruction *EarlierWrite,
1154 OverlapIntervalsTy &IntervalMap,
1155 int64_t &EarlierStart, uint64_t &EarlierSize) {
1156 if (IntervalMap.empty() || !isShortenableAtTheBeginning(EarlierWrite))
1157 return false;
1158
1159 OverlapIntervalsTy::iterator OII = IntervalMap.begin();
1160 int64_t LaterStart = OII->second;
1161 uint64_t LaterSize = OII->first - LaterStart;
1162
1163 assert(OII->first - LaterStart >= 0 && "Size expected to be positive")((OII->first - LaterStart >= 0 && "Size expected to be positive"
) ? static_cast<void> (0) : __assert_fail ("OII->first - LaterStart >= 0 && \"Size expected to be positive\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1163, __PRETTY_FUNCTION__))
;
1164
1165 if (LaterStart <= EarlierStart &&
1166 // Note: "EarlierStart - LaterStart" is known to be non negative due to
1167 // preceding check.
1168 LaterSize > (uint64_t)(EarlierStart - LaterStart)) {
1169 // Note: "LaterSize - (uint64_t)(EarlierStart - LaterStart)" is known to be
1170 // positive due to preceding checks.
1171 assert(LaterSize - (uint64_t)(EarlierStart - LaterStart) < EarlierSize &&((LaterSize - (uint64_t)(EarlierStart - LaterStart) < EarlierSize
&& "Should have been handled as OW_Complete") ? static_cast
<void> (0) : __assert_fail ("LaterSize - (uint64_t)(EarlierStart - LaterStart) < EarlierSize && \"Should have been handled as OW_Complete\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1172, __PRETTY_FUNCTION__))
1172 "Should have been handled as OW_Complete")((LaterSize - (uint64_t)(EarlierStart - LaterStart) < EarlierSize
&& "Should have been handled as OW_Complete") ? static_cast
<void> (0) : __assert_fail ("LaterSize - (uint64_t)(EarlierStart - LaterStart) < EarlierSize && \"Should have been handled as OW_Complete\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1172, __PRETTY_FUNCTION__))
;
1173 if (tryToShorten(EarlierWrite, EarlierStart, EarlierSize, LaterStart,
1174 LaterSize, false)) {
1175 IntervalMap.erase(OII);
1176 return true;
1177 }
1178 }
1179 return false;
1180}
1181
1182static bool removePartiallyOverlappedStores(const DataLayout &DL,
1183 InstOverlapIntervalsTy &IOL,
1184 const TargetLibraryInfo &TLI) {
1185 bool Changed = false;
1186 for (auto OI : IOL) {
1187 Instruction *EarlierWrite = OI.first;
1188 MemoryLocation Loc = getLocForWrite(EarlierWrite, TLI);
1189 assert(isRemovable(EarlierWrite) && "Expect only removable instruction")((isRemovable(EarlierWrite) && "Expect only removable instruction"
) ? static_cast<void> (0) : __assert_fail ("isRemovable(EarlierWrite) && \"Expect only removable instruction\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1189, __PRETTY_FUNCTION__))
;
1190
1191 const Value *Ptr = Loc.Ptr->stripPointerCasts();
1192 int64_t EarlierStart = 0;
1193 uint64_t EarlierSize = Loc.Size.getValue();
1194 GetPointerBaseWithConstantOffset(Ptr, EarlierStart, DL);
1195 OverlapIntervalsTy &IntervalMap = OI.second;
1196 Changed |=
1197 tryToShortenEnd(EarlierWrite, IntervalMap, EarlierStart, EarlierSize);
1198 if (IntervalMap.empty())
1199 continue;
1200 Changed |=
1201 tryToShortenBegin(EarlierWrite, IntervalMap, EarlierStart, EarlierSize);
1202 }
1203 return Changed;
1204}
1205
1206static bool eliminateNoopStore(Instruction *Inst, BasicBlock::iterator &BBI,
1207 AliasAnalysis *AA, MemoryDependenceResults *MD,
1208 const DataLayout &DL,
1209 const TargetLibraryInfo *TLI,
1210 InstOverlapIntervalsTy &IOL,
1211 MapVector<Instruction *, bool> &ThrowableInst,
1212 DominatorTree *DT) {
1213 // Must be a store instruction.
1214 StoreInst *SI = dyn_cast<StoreInst>(Inst);
1215 if (!SI)
1216 return false;
1217
1218 // If we're storing the same value back to a pointer that we just loaded from,
1219 // then the store can be removed.
1220 if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
1221 if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
1222 isRemovable(SI) &&
1223 memoryIsNotModifiedBetween(DepLoad, SI, *AA, DL, DT)) {
1224
1225 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Store Of Load from same pointer:\n LOAD: "
<< *DepLoad << "\n STORE: " << *SI <<
'\n'; } } while (false)
1226 dbgs() << "DSE: Remove Store Of Load from same pointer:\n LOAD: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Store Of Load from same pointer:\n LOAD: "
<< *DepLoad << "\n STORE: " << *SI <<
'\n'; } } while (false)
1227 << *DepLoad << "\n STORE: " << *SI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Store Of Load from same pointer:\n LOAD: "
<< *DepLoad << "\n STORE: " << *SI <<
'\n'; } } while (false)
;
1228
1229 deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, ThrowableInst);
1230 ++NumRedundantStores;
1231 return true;
1232 }
1233 }
1234
1235 // Remove null stores into the calloc'ed objects
1236 Constant *StoredConstant = dyn_cast<Constant>(SI->getValueOperand());
1237 if (StoredConstant && StoredConstant->isNullValue() && isRemovable(SI)) {
1238 Instruction *UnderlyingPointer =
1239 dyn_cast<Instruction>(getUnderlyingObject(SI->getPointerOperand()));
1240
1241 if (UnderlyingPointer && isCallocLikeFn(UnderlyingPointer, TLI) &&
1242 memoryIsNotModifiedBetween(UnderlyingPointer, SI, *AA, DL, DT)) {
1243 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove null store to the calloc'ed object:\n DEAD: "
<< *Inst << "\n OBJECT: " << *UnderlyingPointer
<< '\n'; } } while (false)
1244 dbgs() << "DSE: Remove null store to the calloc'ed object:\n DEAD: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove null store to the calloc'ed object:\n DEAD: "
<< *Inst << "\n OBJECT: " << *UnderlyingPointer
<< '\n'; } } while (false)
1245 << *Inst << "\n OBJECT: " << *UnderlyingPointer << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove null store to the calloc'ed object:\n DEAD: "
<< *Inst << "\n OBJECT: " << *UnderlyingPointer
<< '\n'; } } while (false)
;
1246
1247 deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, ThrowableInst);
1248 ++NumRedundantStores;
1249 return true;
1250 }
1251 }
1252 return false;
1253}
1254
1255template <typename AATy>
1256static Constant *tryToMergePartialOverlappingStores(
1257 StoreInst *Earlier, StoreInst *Later, int64_t InstWriteOffset,
1258 int64_t DepWriteOffset, const DataLayout &DL, AATy &AA, DominatorTree *DT) {
1259
1260 if (Earlier && isa<ConstantInt>(Earlier->getValueOperand()) &&
1261 DL.typeSizeEqualsStoreSize(Earlier->getValueOperand()->getType()) &&
1262 Later && isa<ConstantInt>(Later->getValueOperand()) &&
1263 DL.typeSizeEqualsStoreSize(Later->getValueOperand()->getType()) &&
1264 memoryIsNotModifiedBetween(Earlier, Later, AA, DL, DT)) {
1265 // If the store we find is:
1266 // a) partially overwritten by the store to 'Loc'
1267 // b) the later store is fully contained in the earlier one and
1268 // c) they both have a constant value
1269 // d) none of the two stores need padding
1270 // Merge the two stores, replacing the earlier store's value with a
1271 // merge of both values.
1272 // TODO: Deal with other constant types (vectors, etc), and probably
1273 // some mem intrinsics (if needed)
1274
1275 APInt EarlierValue =
1276 cast<ConstantInt>(Earlier->getValueOperand())->getValue();
1277 APInt LaterValue = cast<ConstantInt>(Later->getValueOperand())->getValue();
1278 unsigned LaterBits = LaterValue.getBitWidth();
1279 assert(EarlierValue.getBitWidth() > LaterValue.getBitWidth())((EarlierValue.getBitWidth() > LaterValue.getBitWidth()) ?
static_cast<void> (0) : __assert_fail ("EarlierValue.getBitWidth() > LaterValue.getBitWidth()"
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1279, __PRETTY_FUNCTION__))
;
1280 LaterValue = LaterValue.zext(EarlierValue.getBitWidth());
1281
1282 // Offset of the smaller store inside the larger store
1283 unsigned BitOffsetDiff = (InstWriteOffset - DepWriteOffset) * 8;
1284 unsigned LShiftAmount = DL.isBigEndian() ? EarlierValue.getBitWidth() -
1285 BitOffsetDiff - LaterBits
1286 : BitOffsetDiff;
1287 APInt Mask = APInt::getBitsSet(EarlierValue.getBitWidth(), LShiftAmount,
1288 LShiftAmount + LaterBits);
1289 // Clear the bits we'll be replacing, then OR with the smaller
1290 // store, shifted appropriately.
1291 APInt Merged = (EarlierValue & ~Mask) | (LaterValue << LShiftAmount);
1292 LLVM_DEBUG(dbgs() << "DSE: Merge Stores:\n Earlier: " << *Earlierdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Merge Stores:\n Earlier: " <<
*Earlier << "\n Later: " << *Later << "\n Merged Value: "
<< Merged << '\n'; } } while (false)
1293 << "\n Later: " << *Laterdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Merge Stores:\n Earlier: " <<
*Earlier << "\n Later: " << *Later << "\n Merged Value: "
<< Merged << '\n'; } } while (false)
1294 << "\n Merged Value: " << Merged << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Merge Stores:\n Earlier: " <<
*Earlier << "\n Later: " << *Later << "\n Merged Value: "
<< Merged << '\n'; } } while (false)
;
1295 return ConstantInt::get(Earlier->getValueOperand()->getType(), Merged);
1296 }
1297 return nullptr;
1298}
1299
1300static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
1301 MemoryDependenceResults *MD, DominatorTree *DT,
1302 const TargetLibraryInfo *TLI) {
1303 const DataLayout &DL = BB.getModule()->getDataLayout();
1304 bool MadeChange = false;
1305
1306 MapVector<Instruction *, bool> ThrowableInst;
1307
1308 // A map of interval maps representing partially-overwritten value parts.
1309 InstOverlapIntervalsTy IOL;
1310
1311 // Do a top-down walk on the BB.
1312 for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
1313 // Handle 'free' calls specially.
1314 if (CallInst *F = isFreeCall(&*BBI, TLI)) {
1315 MadeChange |= handleFree(F, AA, MD, DT, TLI, IOL, ThrowableInst);
1316 // Increment BBI after handleFree has potentially deleted instructions.
1317 // This ensures we maintain a valid iterator.
1318 ++BBI;
1319 continue;
1320 }
1321
1322 Instruction *Inst = &*BBI++;
1323
1324 if (Inst->mayThrow()) {
1325 ThrowableInst[Inst] = true;
1326 continue;
1327 }
1328
1329 // Check to see if Inst writes to memory. If not, continue.
1330 if (!hasAnalyzableMemoryWrite(Inst, *TLI))
1331 continue;
1332
1333 // eliminateNoopStore will update in iterator, if necessary.
1334 if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL,
1335 ThrowableInst, DT)) {
1336 MadeChange = true;
1337 continue;
1338 }
1339
1340 // If we find something that writes memory, get its memory dependence.
1341 MemDepResult InstDep = MD->getDependency(Inst);
1342
1343 // Ignore any store where we can't find a local dependence.
1344 // FIXME: cross-block DSE would be fun. :)
1345 if (!InstDep.isDef() && !InstDep.isClobber())
1346 continue;
1347
1348 // Figure out what location is being stored to.
1349 MemoryLocation Loc = getLocForWrite(Inst, *TLI);
1350
1351 // If we didn't get a useful location, fail.
1352 if (!Loc.Ptr)
1353 continue;
1354
1355 // Loop until we find a store we can eliminate or a load that
1356 // invalidates the analysis. Without an upper bound on the number of
1357 // instructions examined, this analysis can become very time-consuming.
1358 // However, the potential gain diminishes as we process more instructions
1359 // without eliminating any of them. Therefore, we limit the number of
1360 // instructions we look at.
1361 auto Limit = MD->getDefaultBlockScanLimit();
1362 while (InstDep.isDef() || InstDep.isClobber()) {
1363 // Get the memory clobbered by the instruction we depend on. MemDep will
1364 // skip any instructions that 'Loc' clearly doesn't interact with. If we
1365 // end up depending on a may- or must-aliased load, then we can't optimize
1366 // away the store and we bail out. However, if we depend on something
1367 // that overwrites the memory location we *can* potentially optimize it.
1368 //
1369 // Find out what memory location the dependent instruction stores.
1370 Instruction *DepWrite = InstDep.getInst();
1371 if (!hasAnalyzableMemoryWrite(DepWrite, *TLI))
1372 break;
1373 MemoryLocation DepLoc = getLocForWrite(DepWrite, *TLI);
1374 // If we didn't get a useful location, or if it isn't a size, bail out.
1375 if (!DepLoc.Ptr)
1376 break;
1377
1378 // Find the last throwable instruction not removed by call to
1379 // deleteDeadInstruction.
1380 Instruction *LastThrowing = nullptr;
1381 if (!ThrowableInst.empty())
1382 LastThrowing = ThrowableInst.back().first;
1383
1384 // Make sure we don't look past a call which might throw. This is an
1385 // issue because MemoryDependenceAnalysis works in the wrong direction:
1386 // it finds instructions which dominate the current instruction, rather than
1387 // instructions which are post-dominated by the current instruction.
1388 //
1389 // If the underlying object is a non-escaping memory allocation, any store
1390 // to it is dead along the unwind edge. Otherwise, we need to preserve
1391 // the store.
1392 if (LastThrowing && DepWrite->comesBefore(LastThrowing)) {
1393 const Value *Underlying = getUnderlyingObject(DepLoc.Ptr);
1394 bool IsStoreDeadOnUnwind = isa<AllocaInst>(Underlying);
1395 if (!IsStoreDeadOnUnwind) {
1396 // We're looking for a call to an allocation function
1397 // where the allocation doesn't escape before the last
1398 // throwing instruction; PointerMayBeCaptured
1399 // reasonably fast approximation.
1400 IsStoreDeadOnUnwind = isAllocLikeFn(Underlying, TLI) &&
1401 !PointerMayBeCaptured(Underlying, false, true);
1402 }
1403 if (!IsStoreDeadOnUnwind)
1404 break;
1405 }
1406
1407 // If we find a write that is a) removable (i.e., non-volatile), b) is
1408 // completely obliterated by the store to 'Loc', and c) which we know that
1409 // 'Inst' doesn't load from, then we can remove it.
1410 // Also try to merge two stores if a later one only touches memory written
1411 // to by the earlier one.
1412 if (isRemovable(DepWrite) &&
1413 !isPossibleSelfRead(Inst, Loc, DepWrite, *TLI, *AA)) {
1414 int64_t InstWriteOffset, DepWriteOffset;
1415 OverwriteResult OR = isOverwrite(Inst, DepWrite, Loc, DepLoc, DL, *TLI,
1416 DepWriteOffset, InstWriteOffset, *AA,
1417 BB.getParent());
1418 if (OR == OW_MaybePartial)
1419 OR = isPartialOverwrite(Loc, DepLoc, DepWriteOffset, InstWriteOffset,
1420 DepWrite, IOL);
1421
1422 if (OR == OW_Complete) {
1423 LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " << *DepWritedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n DEAD: "
<< *DepWrite << "\n KILLER: " << *Inst <<
'\n'; } } while (false)
1424 << "\n KILLER: " << *Inst << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n DEAD: "
<< *DepWrite << "\n KILLER: " << *Inst <<
'\n'; } } while (false)
;
1425
1426 // Delete the store and now-dead instructions that feed it.
1427 deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL,
1428 ThrowableInst);
1429 ++NumFastStores;
1430 MadeChange = true;
1431
1432 // We erased DepWrite; start over.
1433 InstDep = MD->getDependency(Inst);
1434 continue;
1435 } else if ((OR == OW_End && isShortenableAtTheEnd(DepWrite)) ||
1436 ((OR == OW_Begin &&
1437 isShortenableAtTheBeginning(DepWrite)))) {
1438 assert(!EnablePartialOverwriteTracking && "Do not expect to perform "((!EnablePartialOverwriteTracking && "Do not expect to perform "
"when partial-overwrite " "tracking is enabled") ? static_cast
<void> (0) : __assert_fail ("!EnablePartialOverwriteTracking && \"Do not expect to perform \" \"when partial-overwrite \" \"tracking is enabled\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1440, __PRETTY_FUNCTION__))
1439 "when partial-overwrite "((!EnablePartialOverwriteTracking && "Do not expect to perform "
"when partial-overwrite " "tracking is enabled") ? static_cast
<void> (0) : __assert_fail ("!EnablePartialOverwriteTracking && \"Do not expect to perform \" \"when partial-overwrite \" \"tracking is enabled\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1440, __PRETTY_FUNCTION__))
1440 "tracking is enabled")((!EnablePartialOverwriteTracking && "Do not expect to perform "
"when partial-overwrite " "tracking is enabled") ? static_cast
<void> (0) : __assert_fail ("!EnablePartialOverwriteTracking && \"Do not expect to perform \" \"when partial-overwrite \" \"tracking is enabled\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1440, __PRETTY_FUNCTION__))
;
1441 // The overwrite result is known, so these must be known, too.
1442 uint64_t EarlierSize = DepLoc.Size.getValue();
1443 uint64_t LaterSize = Loc.Size.getValue();
1444 bool IsOverwriteEnd = (OR == OW_End);
1445 MadeChange |= tryToShorten(DepWrite, DepWriteOffset, EarlierSize,
1446 InstWriteOffset, LaterSize, IsOverwriteEnd);
1447 } else if (EnablePartialStoreMerging &&
1448 OR == OW_PartialEarlierWithFullLater) {
1449 auto *Earlier = dyn_cast<StoreInst>(DepWrite);
1450 auto *Later = dyn_cast<StoreInst>(Inst);
1451 if (Constant *C = tryToMergePartialOverlappingStores(
1452 Earlier, Later, InstWriteOffset, DepWriteOffset, DL, *AA,
1453 DT)) {
1454 auto *SI = new StoreInst(
1455 C, Earlier->getPointerOperand(), false, Earlier->getAlign(),
1456 Earlier->getOrdering(), Earlier->getSyncScopeID(), DepWrite);
1457
1458 unsigned MDToKeep[] = {LLVMContext::MD_dbg, LLVMContext::MD_tbaa,
1459 LLVMContext::MD_alias_scope,
1460 LLVMContext::MD_noalias,
1461 LLVMContext::MD_nontemporal};
1462 SI->copyMetadata(*DepWrite, MDToKeep);
1463 ++NumModifiedStores;
1464
1465 // Delete the old stores and now-dead instructions that feed them.
1466 deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL,
1467 ThrowableInst);
1468 deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL,
1469 ThrowableInst);
1470 MadeChange = true;
1471
1472 // We erased DepWrite and Inst (Loc); start over.
1473 break;
1474 }
1475 }
1476 }
1477
1478 // If this is a may-aliased store that is clobbering the store value, we
1479 // can keep searching past it for another must-aliased pointer that stores
1480 // to the same location. For example, in:
1481 // store -> P
1482 // store -> Q
1483 // store -> P
1484 // we can remove the first store to P even though we don't know if P and Q
1485 // alias.
1486 if (DepWrite == &BB.front()) break;
1487
1488 // Can't look past this instruction if it might read 'Loc'.
1489 if (isRefSet(AA->getModRefInfo(DepWrite, Loc)))
1490 break;
1491
1492 InstDep = MD->getPointerDependencyFrom(Loc, /*isLoad=*/ false,
1493 DepWrite->getIterator(), &BB,
1494 /*QueryInst=*/ nullptr, &Limit);
1495 }
1496 }
1497
1498 if (EnablePartialOverwriteTracking)
1499 MadeChange |= removePartiallyOverlappedStores(DL, IOL, *TLI);
1500
1501 // If this block ends in a return, unwind, or unreachable, all allocas are
1502 // dead at its end, which means stores to them are also dead.
1503 if (BB.getTerminator()->getNumSuccessors() == 0)
1504 MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, ThrowableInst);
1505
1506 return MadeChange;
1507}
1508
1509static bool eliminateDeadStores(Function &F, AliasAnalysis *AA,
1510 MemoryDependenceResults *MD, DominatorTree *DT,
1511 const TargetLibraryInfo *TLI) {
1512 bool MadeChange = false;
1513 for (BasicBlock &BB : F)
1514 // Only check non-dead blocks. Dead blocks may have strange pointer
1515 // cycles that will confuse alias analysis.
1516 if (DT->isReachableFromEntry(&BB))
1517 MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI);
1518
1519 return MadeChange;
1520}
1521
1522namespace {
1523//=============================================================================
1524// MemorySSA backed dead store elimination.
1525//
1526// The code below implements dead store elimination using MemorySSA. It uses
1527// the following general approach: given a MemoryDef, walk upwards to find
1528// clobbering MemoryDefs that may be killed by the starting def. Then check
1529// that there are no uses that may read the location of the original MemoryDef
1530// in between both MemoryDefs. A bit more concretely:
1531//
1532// For all MemoryDefs StartDef:
1533// 1. Get the next dominating clobbering MemoryDef (EarlierAccess) by walking
1534// upwards.
1535// 2. Check that there are no reads between EarlierAccess and the StartDef by
1536// checking all uses starting at EarlierAccess and walking until we see
1537// StartDef.
1538// 3. For each found CurrentDef, check that:
1539// 1. There are no barrier instructions between CurrentDef and StartDef (like
1540// throws or stores with ordering constraints).
1541// 2. StartDef is executed whenever CurrentDef is executed.
1542// 3. StartDef completely overwrites CurrentDef.
1543// 4. Erase CurrentDef from the function and MemorySSA.
1544
1545// Returns true if \p I is an intrisnic that does not read or write memory.
1546bool isNoopIntrinsic(Instruction *I) {
1547 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
1548 switch (II->getIntrinsicID()) {
1549 case Intrinsic::lifetime_start:
1550 case Intrinsic::lifetime_end:
1551 case Intrinsic::invariant_end:
1552 case Intrinsic::launder_invariant_group:
1553 case Intrinsic::assume:
1554 return true;
1555 case Intrinsic::dbg_addr:
1556 case Intrinsic::dbg_declare:
1557 case Intrinsic::dbg_label:
1558 case Intrinsic::dbg_value:
1559 llvm_unreachable("Intrinsic should not be modeled in MemorySSA")::llvm::llvm_unreachable_internal("Intrinsic should not be modeled in MemorySSA"
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1559)
;
1560 default:
1561 return false;
1562 }
1563 }
1564 return false;
1565}
1566
1567// Check if we can ignore \p D for DSE.
1568bool canSkipDef(MemoryDef *D, bool DefVisibleToCaller) {
1569 Instruction *DI = D->getMemoryInst();
1570 // Calls that only access inaccessible memory cannot read or write any memory
1571 // locations we consider for elimination.
1572 if (auto *CB = dyn_cast<CallBase>(DI))
1573 if (CB->onlyAccessesInaccessibleMemory())
1574 return true;
1575
1576 // We can eliminate stores to locations not visible to the caller across
1577 // throwing instructions.
1578 if (DI->mayThrow() && !DefVisibleToCaller)
1579 return true;
1580
1581 // We can remove the dead stores, irrespective of the fence and its ordering
1582 // (release/acquire/seq_cst). Fences only constraints the ordering of
1583 // already visible stores, it does not make a store visible to other
1584 // threads. So, skipping over a fence does not change a store from being
1585 // dead.
1586 if (isa<FenceInst>(DI))
1587 return true;
1588
1589 // Skip intrinsics that do not really read or modify memory.
1590 if (isNoopIntrinsic(D->getMemoryInst()))
1591 return true;
1592
1593 return false;
1594}
1595
1596struct DSEState {
1597 Function &F;
1598 AliasAnalysis &AA;
1599
1600 /// The single BatchAA instance that is used to cache AA queries. It will
1601 /// not be invalidated over the whole run. This is safe, because:
1602 /// 1. Only memory writes are removed, so the alias cache for memory
1603 /// locations remains valid.
1604 /// 2. No new instructions are added (only instructions removed), so cached
1605 /// information for a deleted value cannot be accessed by a re-used new
1606 /// value pointer.
1607 BatchAAResults BatchAA;
1608
1609 MemorySSA &MSSA;
1610 DominatorTree &DT;
1611 PostDominatorTree &PDT;
1612 const TargetLibraryInfo &TLI;
1613 const DataLayout &DL;
1614
1615 // All MemoryDefs that potentially could kill other MemDefs.
1616 SmallVector<MemoryDef *, 64> MemDefs;
1617 // Any that should be skipped as they are already deleted
1618 SmallPtrSet<MemoryAccess *, 4> SkipStores;
1619 // Keep track of all of the objects that are invisible to the caller before
1620 // the function returns.
1621 // SmallPtrSet<const Value *, 16> InvisibleToCallerBeforeRet;
1622 DenseMap<const Value *, bool> InvisibleToCallerBeforeRet;
1623 // Keep track of all of the objects that are invisible to the caller after
1624 // the function returns.
1625 DenseMap<const Value *, bool> InvisibleToCallerAfterRet;
1626 // Keep track of blocks with throwing instructions not modeled in MemorySSA.
1627 SmallPtrSet<BasicBlock *, 16> ThrowingBlocks;
1628 // Post-order numbers for each basic block. Used to figure out if memory
1629 // accesses are executed before another access.
1630 DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
1631
1632 /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
1633 /// basic block.
1634 DenseMap<BasicBlock *, InstOverlapIntervalsTy> IOLs;
1635
1636 DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
1637 PostDominatorTree &PDT, const TargetLibraryInfo &TLI)
1638 : F(F), AA(AA), BatchAA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI),
1639 DL(F.getParent()->getDataLayout()) {}
1640
1641 static DSEState get(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
1642 DominatorTree &DT, PostDominatorTree &PDT,
1643 const TargetLibraryInfo &TLI) {
1644 DSEState State(F, AA, MSSA, DT, PDT, TLI);
1645 // Collect blocks with throwing instructions not modeled in MemorySSA and
1646 // alloc-like objects.
1647 unsigned PO = 0;
1648 for (BasicBlock *BB : post_order(&F)) {
1649 State.PostOrderNumbers[BB] = PO++;
1650 for (Instruction &I : *BB) {
1651 MemoryAccess *MA = MSSA.getMemoryAccess(&I);
1652 if (I.mayThrow() && !MA)
1653 State.ThrowingBlocks.insert(I.getParent());
1654
1655 auto *MD = dyn_cast_or_null<MemoryDef>(MA);
1656 if (MD && State.MemDefs.size() < MemorySSADefsPerBlockLimit &&
1657 (State.getLocForWriteEx(&I) || State.isMemTerminatorInst(&I)))
1658 State.MemDefs.push_back(MD);
1659 }
1660 }
1661
1662 // Treat byval or inalloca arguments the same as Allocas, stores to them are
1663 // dead at the end of the function.
1664 for (Argument &AI : F.args())
1665 if (AI.hasPassPointeeByValueCopyAttr()) {
1666 // For byval, the caller doesn't know the address of the allocation.
1667 if (AI.hasByValAttr())
1668 State.InvisibleToCallerBeforeRet.insert({&AI, true});
1669 State.InvisibleToCallerAfterRet.insert({&AI, true});
1670 }
1671
1672 return State;
1673 }
1674
1675 bool isInvisibleToCallerAfterRet(const Value *V) {
1676 if (isa<AllocaInst>(V))
1677 return true;
1678 auto I = InvisibleToCallerAfterRet.insert({V, false});
1679 if (I.second) {
1680 if (!isInvisibleToCallerBeforeRet(V)) {
1681 I.first->second = false;
1682 } else {
1683 auto *Inst = dyn_cast<Instruction>(V);
1684 if (Inst && isAllocLikeFn(Inst, &TLI))
1685 I.first->second = !PointerMayBeCaptured(V, true, false);
1686 }
1687 }
1688 return I.first->second;
1689 }
1690
1691 bool isInvisibleToCallerBeforeRet(const Value *V) {
1692 if (isa<AllocaInst>(V))
1693 return true;
1694 auto I = InvisibleToCallerBeforeRet.insert({V, false});
1695 if (I.second) {
1696 auto *Inst = dyn_cast<Instruction>(V);
1697 if (Inst && isAllocLikeFn(Inst, &TLI))
1698 // NOTE: This could be made more precise by PointerMayBeCapturedBefore
1699 // with the killing MemoryDef. But we refrain from doing so for now to
1700 // limit compile-time and this does not cause any changes to the number
1701 // of stores removed on a large test set in practice.
1702 I.first->second = !PointerMayBeCaptured(V, false, true);
1703 }
1704 return I.first->second;
1705 }
1706
1707 Optional<MemoryLocation> getLocForWriteEx(Instruction *I) const {
1708 if (!I->mayWriteToMemory())
1709 return None;
1710
1711 if (auto *MTI = dyn_cast<AnyMemIntrinsic>(I))
1712 return {MemoryLocation::getForDest(MTI)};
1713
1714 if (auto *CB = dyn_cast<CallBase>(I)) {
1715 // If the functions may write to memory we do not know about, bail out.
1716 if (!CB->onlyAccessesArgMemory() &&
1717 !CB->onlyAccessesInaccessibleMemOrArgMem())
1718 return None;
1719
1720 LibFunc LF;
1721 if (TLI.getLibFunc(*CB, LF) && TLI.has(LF)) {
1722 switch (LF) {
1723 case LibFunc_strcpy:
1724 case LibFunc_strncpy:
1725 case LibFunc_strcat:
1726 case LibFunc_strncat:
1727 return {MemoryLocation::getAfter(CB->getArgOperand(0))};
1728 default:
1729 break;
1730 }
1731 }
1732 switch (CB->getIntrinsicID()) {
1733 case Intrinsic::init_trampoline:
1734 return {MemoryLocation::getAfter(CB->getArgOperand(0))};
1735 case Intrinsic::masked_store:
1736 return {MemoryLocation::getForArgument(CB, 1, TLI)};
1737 default:
1738 break;
1739 }
1740 return None;
1741 }
1742
1743 return MemoryLocation::getOrNone(I);
1744 }
1745
1746 /// Returns true if \p UseInst completely overwrites \p DefLoc
1747 /// (stored by \p DefInst).
1748 bool isCompleteOverwrite(const MemoryLocation &DefLoc, Instruction *DefInst,
1749 Instruction *UseInst) {
1750 // UseInst has a MemoryDef associated in MemorySSA. It's possible for a
1751 // MemoryDef to not write to memory, e.g. a volatile load is modeled as a
1752 // MemoryDef.
1753 if (!UseInst->mayWriteToMemory())
1754 return false;
1755
1756 if (auto *CB = dyn_cast<CallBase>(UseInst))
1757 if (CB->onlyAccessesInaccessibleMemory())
1758 return false;
1759
1760 int64_t InstWriteOffset, DepWriteOffset;
1761 if (auto CC = getLocForWriteEx(UseInst))
1762 return isOverwrite(UseInst, DefInst, *CC, DefLoc, DL, TLI, DepWriteOffset,
1763 InstWriteOffset, BatchAA, &F) == OW_Complete;
1764 return false;
1765 }
1766
1767 /// Returns true if \p Def is not read before returning from the function.
1768 bool isWriteAtEndOfFunction(MemoryDef *Def) {
1769 LLVM_DEBUG(dbgs() << " Check if def " << *Def << " ("do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " Check if def " << *Def <<
" (" << *Def->getMemoryInst() << ") is at the end the function \n"
; } } while (false)
1770 << *Def->getMemoryInst()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " Check if def " << *Def <<
" (" << *Def->getMemoryInst() << ") is at the end the function \n"
; } } while (false)
1771 << ") is at the end the function \n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " Check if def " << *Def <<
" (" << *Def->getMemoryInst() << ") is at the end the function \n"
; } } while (false)
;
1772
1773 auto MaybeLoc = getLocForWriteEx(Def->getMemoryInst());
1774 if (!MaybeLoc) {
1775 LLVM_DEBUG(dbgs() << " ... could not get location for write.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... could not get location for write.\n"
; } } while (false)
;
1776 return false;
1777 }
1778
1779 SmallVector<MemoryAccess *, 4> WorkList;
1780 SmallPtrSet<MemoryAccess *, 8> Visited;
1781 auto PushMemUses = [&WorkList, &Visited](MemoryAccess *Acc) {
1782 if (!Visited.insert(Acc).second)
1783 return;
1784 for (Use &U : Acc->uses())
1785 WorkList.push_back(cast<MemoryAccess>(U.getUser()));
1786 };
1787 PushMemUses(Def);
1788 for (unsigned I = 0; I < WorkList.size(); I++) {
1789 if (WorkList.size() >= MemorySSAScanLimit) {
1790 LLVM_DEBUG(dbgs() << " ... hit exploration limit.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... hit exploration limit.\n"; }
} while (false)
;
1791 return false;
1792 }
1793
1794 MemoryAccess *UseAccess = WorkList[I];
1795 // Simply adding the users of MemoryPhi to the worklist is not enough,
1796 // because we might miss read clobbers in different iterations of a loop,
1797 // for example.
1798 // TODO: Add support for phi translation to handle the loop case.
1799 if (isa<MemoryPhi>(UseAccess))
1800 return false;
1801
1802 // TODO: Checking for aliasing is expensive. Consider reducing the amount
1803 // of times this is called and/or caching it.
1804 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1805 if (isReadClobber(*MaybeLoc, UseInst)) {
1806 LLVM_DEBUG(dbgs() << " ... hit read clobber " << *UseInst << ".\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... hit read clobber " <<
*UseInst << ".\n"; } } while (false)
;
1807 return false;
1808 }
1809
1810 if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))
1811 PushMemUses(UseDef);
1812 }
1813 return true;
1814 }
1815
1816 /// If \p I is a memory terminator like llvm.lifetime.end or free, return a
1817 /// pair with the MemoryLocation terminated by \p I and a boolean flag
1818 /// indicating whether \p I is a free-like call.
1819 Optional<std::pair<MemoryLocation, bool>>
1820 getLocForTerminator(Instruction *I) const {
1821 uint64_t Len;
1822 Value *Ptr;
1823 if (match(I, m_Intrinsic<Intrinsic::lifetime_end>(m_ConstantInt(Len),
1824 m_Value(Ptr))))
1825 return {std::make_pair(MemoryLocation(Ptr, Len), false)};
1826
1827 if (auto *CB = dyn_cast<CallBase>(I)) {
1828 if (isFreeCall(I, &TLI))
1829 return {std::make_pair(MemoryLocation::getAfter(CB->getArgOperand(0)),
1830 true)};
1831 }
1832
1833 return None;
1834 }
1835
1836 /// Returns true if \p I is a memory terminator instruction like
1837 /// llvm.lifetime.end or free.
1838 bool isMemTerminatorInst(Instruction *I) const {
1839 IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
1840 return (II && II->getIntrinsicID() == Intrinsic::lifetime_end) ||
1841 isFreeCall(I, &TLI);
1842 }
1843
1844 /// Returns true if \p MaybeTerm is a memory terminator for \p Loc from
1845 /// instruction \p AccessI.
1846 bool isMemTerminator(const MemoryLocation &Loc, Instruction *AccessI,
1847 Instruction *MaybeTerm) {
1848 Optional<std::pair<MemoryLocation, bool>> MaybeTermLoc =
1849 getLocForTerminator(MaybeTerm);
1850
1851 if (!MaybeTermLoc)
1852 return false;
1853
1854 // If the terminator is a free-like call, all accesses to the underlying
1855 // object can be considered terminated.
1856 if (getUnderlyingObject(Loc.Ptr) !=
1857 getUnderlyingObject(MaybeTermLoc->first.Ptr))
1858 return false;
1859
1860 auto TermLoc = MaybeTermLoc->first;
1861 if (MaybeTermLoc->second) {
1862 const Value *LocUO = getUnderlyingObject(Loc.Ptr);
1863 return BatchAA.isMustAlias(TermLoc.Ptr, LocUO);
1864 }
1865 int64_t InstWriteOffset, DepWriteOffset;
1866 return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, DL, TLI,
1867 DepWriteOffset, InstWriteOffset, BatchAA,
1868 &F) == OW_Complete;
1869 }
1870
1871 // Returns true if \p Use may read from \p DefLoc.
1872 bool isReadClobber(const MemoryLocation &DefLoc, Instruction *UseInst) {
1873 if (isNoopIntrinsic(UseInst))
1874 return false;
1875
1876 // Monotonic or weaker atomic stores can be re-ordered and do not need to be
1877 // treated as read clobber.
1878 if (auto SI = dyn_cast<StoreInst>(UseInst))
1879 return isStrongerThan(SI->getOrdering(), AtomicOrdering::Monotonic);
1880
1881 if (!UseInst->mayReadFromMemory())
1882 return false;
1883
1884 if (auto *CB = dyn_cast<CallBase>(UseInst))
1885 if (CB->onlyAccessesInaccessibleMemory())
1886 return false;
1887
1888 // NOTE: For calls, the number of stores removed could be slightly improved
1889 // by using AA.callCapturesBefore(UseInst, DefLoc, &DT), but that showed to
1890 // be expensive compared to the benefits in practice. For now, avoid more
1891 // expensive analysis to limit compile-time.
1892 return isRefSet(BatchAA.getModRefInfo(UseInst, DefLoc));
1893 }
1894
1895 /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
1896 /// loop. In particular, this guarantees that it only references a single
1897 /// MemoryLocation during execution of the containing function.
1898 bool IsGuaranteedLoopInvariant(Value *Ptr) {
1899 auto IsGuaranteedLoopInvariantBase = [this](Value *Ptr) {
1900 Ptr = Ptr->stripPointerCasts();
1901 if (auto *I = dyn_cast<Instruction>(Ptr)) {
1902 if (isa<AllocaInst>(Ptr))
1903 return true;
1904
1905 if (isAllocLikeFn(I, &TLI))
1906 return true;
1907
1908 return false;
1909 }
1910 return true;
1911 };
1912
1913 Ptr = Ptr->stripPointerCasts();
1914 if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
1915 return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) &&
1916 GEP->hasAllConstantIndices();
1917 }
1918 return IsGuaranteedLoopInvariantBase(Ptr);
1919 }
1920
1921 // Find a MemoryDef writing to \p DefLoc and dominating \p StartAccess, with
1922 // no read access between them or on any other path to a function exit block
1923 // if \p DefLoc is not accessible after the function returns. If there is no
1924 // such MemoryDef, return None. The returned value may not (completely)
1925 // overwrite \p DefLoc. Currently we bail out when we encounter an aliasing
1926 // MemoryUse (read).
1927 Optional<MemoryAccess *>
1928 getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *StartAccess,
1929 const MemoryLocation &DefLoc, const Value *DefUO,
1930 unsigned &ScanLimit, unsigned &WalkerStepLimit,
1931 bool IsMemTerm, unsigned &PartialLimit) {
1932 if (ScanLimit == 0 || WalkerStepLimit == 0) {
1933 LLVM_DEBUG(dbgs() << "\n ... hit scan limit\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "\n ... hit scan limit\n"; } }
while (false)
;
1934 return None;
1935 }
1936
1937 MemoryAccess *Current = StartAccess;
1938 Instruction *KillingI = KillingDef->getMemoryInst();
1939 bool StepAgain;
1940 LLVM_DEBUG(dbgs() << " trying to get dominating access\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " trying to get dominating access\n"
; } } while (false)
;
1941
1942 // Find the next clobbering Mod access for DefLoc, starting at StartAccess.
1943 Optional<MemoryLocation> CurrentLoc;
1944 do {
1945 StepAgain = false;
1946 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { { dbgs() << " visiting " << *Current
; if (!MSSA.isLiveOnEntryDef(Current) && isa<MemoryUseOrDef
>(Current)) dbgs() << " (" << *cast<MemoryUseOrDef
>(Current)->getMemoryInst() << ")"; dbgs() <<
"\n"; }; } } while (false)
1947 dbgs() << " visiting " << *Current;do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { { dbgs() << " visiting " << *Current
; if (!MSSA.isLiveOnEntryDef(Current) && isa<MemoryUseOrDef
>(Current)) dbgs() << " (" << *cast<MemoryUseOrDef
>(Current)->getMemoryInst() << ")"; dbgs() <<
"\n"; }; } } while (false)
1948 if (!MSSA.isLiveOnEntryDef(Current) && isa<MemoryUseOrDef>(Current))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { { dbgs() << " visiting " << *Current
; if (!MSSA.isLiveOnEntryDef(Current) && isa<MemoryUseOrDef
>(Current)) dbgs() << " (" << *cast<MemoryUseOrDef
>(Current)->getMemoryInst() << ")"; dbgs() <<
"\n"; }; } } while (false)
1949 dbgs() << " (" << *cast<MemoryUseOrDef>(Current)->getMemoryInst()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { { dbgs() << " visiting " << *Current
; if (!MSSA.isLiveOnEntryDef(Current) && isa<MemoryUseOrDef
>(Current)) dbgs() << " (" << *cast<MemoryUseOrDef
>(Current)->getMemoryInst() << ")"; dbgs() <<
"\n"; }; } } while (false)
1950 << ")";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { { dbgs() << " visiting " << *Current
; if (!MSSA.isLiveOnEntryDef(Current) && isa<MemoryUseOrDef
>(Current)) dbgs() << " (" << *cast<MemoryUseOrDef
>(Current)->getMemoryInst() << ")"; dbgs() <<
"\n"; }; } } while (false)
1951 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { { dbgs() << " visiting " << *Current
; if (!MSSA.isLiveOnEntryDef(Current) && isa<MemoryUseOrDef
>(Current)) dbgs() << " (" << *cast<MemoryUseOrDef
>(Current)->getMemoryInst() << ")"; dbgs() <<
"\n"; }; } } while (false)
1952 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { { dbgs() << " visiting " << *Current
; if (!MSSA.isLiveOnEntryDef(Current) && isa<MemoryUseOrDef
>(Current)) dbgs() << " (" << *cast<MemoryUseOrDef
>(Current)->getMemoryInst() << ")"; dbgs() <<
"\n"; }; } } while (false)
;
1953
1954 // Reached TOP.
1955 if (MSSA.isLiveOnEntryDef(Current)) {
1956 LLVM_DEBUG(dbgs() << " ... found LiveOnEntryDef\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found LiveOnEntryDef\n"; }
} while (false)
;
1957 return None;
1958 }
1959
1960 // Cost of a step. Accesses in the same block are more likely to be valid
1961 // candidates for elimination, hence consider them cheaper.
1962 unsigned StepCost = KillingDef->getBlock() == Current->getBlock()
1963 ? MemorySSASameBBStepCost
1964 : MemorySSAOtherBBStepCost;
1965 if (WalkerStepLimit <= StepCost) {
1966 LLVM_DEBUG(dbgs() << " ... hit walker step limit\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... hit walker step limit\n";
} } while (false)
;
1967 return None;
1968 }
1969 WalkerStepLimit -= StepCost;
1970
1971 // Return for MemoryPhis. They cannot be eliminated directly and the
1972 // caller is responsible for traversing them.
1973 if (isa<MemoryPhi>(Current)) {
1974 LLVM_DEBUG(dbgs() << " ... found MemoryPhi\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found MemoryPhi\n"; } } while
(false)
;
1975 return Current;
1976 }
1977
1978 // Below, check if CurrentDef is a valid candidate to be eliminated by
1979 // KillingDef. If it is not, check the next candidate.
1980 MemoryDef *CurrentDef = cast<MemoryDef>(Current);
1981 Instruction *CurrentI = CurrentDef->getMemoryInst();
1982
1983 if (canSkipDef(CurrentDef, !isInvisibleToCallerBeforeRet(DefUO))) {
1984 StepAgain = true;
1985 Current = CurrentDef->getDefiningAccess();
1986 continue;
1987 }
1988
1989 // Before we try to remove anything, check for any extra throwing
1990 // instructions that block us from DSEing
1991 if (mayThrowBetween(KillingI, CurrentI, DefUO)) {
1992 LLVM_DEBUG(dbgs() << " ... skip, may throw!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skip, may throw!\n"; } } while
(false)
;
1993 return None;
1994 }
1995
1996 // Check for anything that looks like it will be a barrier to further
1997 // removal
1998 if (isDSEBarrier(DefUO, CurrentI)) {
1999 LLVM_DEBUG(dbgs() << " ... skip, barrier\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skip, barrier\n"; } } while
(false)
;
2000 return None;
2001 }
2002
2003 // If Current is known to be on path that reads DefLoc or is a read
2004 // clobber, bail out, as the path is not profitable. We skip this check
2005 // for intrinsic calls, because the code knows how to handle memcpy
2006 // intrinsics.
2007 if (!isa<IntrinsicInst>(CurrentI) && isReadClobber(DefLoc, CurrentI))
2008 return None;
2009
2010 // Quick check if there are direct uses that are read-clobbers.
2011 if (any_of(Current->uses(), [this, &DefLoc, StartAccess](Use &U) {
2012 if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))
2013 return !MSSA.dominates(StartAccess, UseOrDef) &&
2014 isReadClobber(DefLoc, UseOrDef->getMemoryInst());
2015 return false;
2016 })) {
2017 LLVM_DEBUG(dbgs() << " ... found a read clobber\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found a read clobber\n"; }
} while (false)
;
2018 return None;
2019 }
2020
2021 // If Current cannot be analyzed or is not removable, check the next
2022 // candidate.
2023 if (!hasAnalyzableMemoryWrite(CurrentI, TLI) || !isRemovable(CurrentI)) {
2024 StepAgain = true;
2025 Current = CurrentDef->getDefiningAccess();
2026 continue;
2027 }
2028
2029 // If Current does not have an analyzable write location, skip it
2030 CurrentLoc = getLocForWriteEx(CurrentI);
2031 if (!CurrentLoc) {
2032 StepAgain = true;
2033 Current = CurrentDef->getDefiningAccess();
2034 continue;
2035 }
2036
2037 // AliasAnalysis does not account for loops. Limit elimination to
2038 // candidates for which we can guarantee they always store to the same
2039 // memory location and not multiple locations in a loop.
2040 if (Current->getBlock() != KillingDef->getBlock() &&
2041 !IsGuaranteedLoopInvariant(const_cast<Value *>(CurrentLoc->Ptr))) {
2042 StepAgain = true;
2043 Current = CurrentDef->getDefiningAccess();
2044 WalkerStepLimit -= 1;
2045 continue;
2046 }
2047
2048 if (IsMemTerm) {
2049 // If the killing def is a memory terminator (e.g. lifetime.end), check
2050 // the next candidate if the current Current does not write the same
2051 // underlying object as the terminator.
2052 if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI)) {
2053 StepAgain = true;
2054 Current = CurrentDef->getDefiningAccess();
2055 }
2056 continue;
2057 } else {
2058 int64_t InstWriteOffset, DepWriteOffset;
2059 auto OR = isOverwrite(KillingI, CurrentI, DefLoc, *CurrentLoc, DL, TLI,
2060 DepWriteOffset, InstWriteOffset, BatchAA, &F);
2061 // If Current does not write to the same object as KillingDef, check
2062 // the next candidate.
2063 if (OR == OW_Unknown) {
2064 StepAgain = true;
2065 Current = CurrentDef->getDefiningAccess();
2066 } else if (OR == OW_MaybePartial) {
2067 // If KillingDef only partially overwrites Current, check the next
2068 // candidate if the partial step limit is exceeded. This aggressively
2069 // limits the number of candidates for partial store elimination,
2070 // which are less likely to be removable in the end.
2071 if (PartialLimit <= 1) {
2072 StepAgain = true;
2073 Current = CurrentDef->getDefiningAccess();
2074 WalkerStepLimit -= 1;
2075 continue;
2076 }
2077 PartialLimit -= 1;
2078 }
2079 }
2080 } while (StepAgain);
2081
2082 // Accesses to objects accessible after the function returns can only be
2083 // eliminated if the access is killed along all paths to the exit. Collect
2084 // the blocks with killing (=completely overwriting MemoryDefs) and check if
2085 // they cover all paths from EarlierAccess to any function exit.
2086 SmallPtrSet<Instruction *, 16> KillingDefs;
2087 KillingDefs.insert(KillingDef->getMemoryInst());
2088 MemoryAccess *EarlierAccess = Current;
2089 Instruction *EarlierMemInst =
2090 cast<MemoryDef>(EarlierAccess)->getMemoryInst();
2091 LLVM_DEBUG(dbgs() << " Checking for reads of " << *EarlierAccess << " ("do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " Checking for reads of " <<
*EarlierAccess << " (" << *EarlierMemInst <<
")\n"; } } while (false)
2092 << *EarlierMemInst << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " Checking for reads of " <<
*EarlierAccess << " (" << *EarlierMemInst <<
")\n"; } } while (false)
;
2093
2094 SmallSetVector<MemoryAccess *, 32> WorkList;
2095 auto PushMemUses = [&WorkList](MemoryAccess *Acc) {
2096 for (Use &U : Acc->uses())
2097 WorkList.insert(cast<MemoryAccess>(U.getUser()));
2098 };
2099 PushMemUses(EarlierAccess);
2100
2101 // Optimistically collect all accesses for reads. If we do not find any
2102 // read clobbers, add them to the cache.
2103 SmallPtrSet<MemoryAccess *, 16> KnownNoReads;
2104 if (!EarlierMemInst->mayReadFromMemory())
2105 KnownNoReads.insert(EarlierAccess);
2106 // Check if EarlierDef may be read.
2107 for (unsigned I = 0; I < WorkList.size(); I++) {
2108 MemoryAccess *UseAccess = WorkList[I];
2109
2110 LLVM_DEBUG(dbgs() << " " << *UseAccess)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " " << *UseAccess; } } while
(false)
;
2111 // Bail out if the number of accesses to check exceeds the scan limit.
2112 if (ScanLimit < (WorkList.size() - I)) {
2113 LLVM_DEBUG(dbgs() << "\n ... hit scan limit\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "\n ... hit scan limit\n"; } }
while (false)
;
2114 return None;
2115 }
2116 --ScanLimit;
2117 NumDomMemDefChecks++;
2118 KnownNoReads.insert(UseAccess);
2119
2120 if (isa<MemoryPhi>(UseAccess)) {
2121 if (any_of(KillingDefs, [this, UseAccess](Instruction *KI) {
2122 return DT.properlyDominates(KI->getParent(),
2123 UseAccess->getBlock());
2124 })) {
2125 LLVM_DEBUG(dbgs() << " ... skipping, dominated by killing block\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skipping, dominated by killing block\n"
; } } while (false)
;
2126 continue;
2127 }
2128 LLVM_DEBUG(dbgs() << "\n ... adding PHI uses\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "\n ... adding PHI uses\n"; } }
while (false)
;
2129 PushMemUses(UseAccess);
2130 continue;
2131 }
2132
2133 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
2134 LLVM_DEBUG(dbgs() << " (" << *UseInst << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " (" << *UseInst << ")\n"
; } } while (false)
;
2135
2136 if (any_of(KillingDefs, [this, UseInst](Instruction *KI) {
2137 return DT.dominates(KI, UseInst);
2138 })) {
2139 LLVM_DEBUG(dbgs() << " ... skipping, dominated by killing def\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skipping, dominated by killing def\n"
; } } while (false)
;
2140 continue;
2141 }
2142
2143 // A memory terminator kills all preceeding MemoryDefs and all succeeding
2144 // MemoryAccesses. We do not have to check it's users.
2145 if (isMemTerminator(*CurrentLoc, EarlierMemInst, UseInst)) {
2146 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skipping, memterminator invalidates following accesses\n"
; } } while (false)
2147 dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skipping, memterminator invalidates following accesses\n"
; } } while (false)
2148 << " ... skipping, memterminator invalidates following accesses\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skipping, memterminator invalidates following accesses\n"
; } } while (false)
;
2149 continue;
2150 }
2151
2152 if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess)->getMemoryInst())) {
2153 LLVM_DEBUG(dbgs() << " ... adding uses of intrinsic\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... adding uses of intrinsic\n"
; } } while (false)
;
2154 PushMemUses(UseAccess);
2155 continue;
2156 }
2157
2158 if (UseInst->mayThrow() && !isInvisibleToCallerBeforeRet(DefUO)) {
2159 LLVM_DEBUG(dbgs() << " ... found throwing instruction\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found throwing instruction\n"
; } } while (false)
;
2160 return None;
2161 }
2162
2163 // Uses which may read the original MemoryDef mean we cannot eliminate the
2164 // original MD. Stop walk.
2165 if (isReadClobber(*CurrentLoc, UseInst)) {
2166 LLVM_DEBUG(dbgs() << " ... found read clobber\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found read clobber\n"; } }
while (false)
;
2167 return None;
2168 }
2169
2170 // For the KillingDef and EarlierAccess we only have to check if it reads
2171 // the memory location.
2172 // TODO: It would probably be better to check for self-reads before
2173 // calling the function.
2174 if (KillingDef == UseAccess || EarlierAccess == UseAccess) {
2175 LLVM_DEBUG(dbgs() << " ... skipping killing def/dom access\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skipping killing def/dom access\n"
; } } while (false)
;
2176 continue;
2177 }
2178
2179 // Check all uses for MemoryDefs, except for defs completely overwriting
2180 // the original location. Otherwise we have to check uses of *all*
2181 // MemoryDefs we discover, including non-aliasing ones. Otherwise we might
2182 // miss cases like the following
2183 // 1 = Def(LoE) ; <----- EarlierDef stores [0,1]
2184 // 2 = Def(1) ; (2, 1) = NoAlias, stores [2,3]
2185 // Use(2) ; MayAlias 2 *and* 1, loads [0, 3].
2186 // (The Use points to the *first* Def it may alias)
2187 // 3 = Def(1) ; <---- Current (3, 2) = NoAlias, (3,1) = MayAlias,
2188 // stores [0,1]
2189 if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {
2190 if (isCompleteOverwrite(*CurrentLoc, EarlierMemInst, UseInst)) {
2191 if (!isInvisibleToCallerAfterRet(DefUO) &&
2192 UseAccess != EarlierAccess) {
2193 BasicBlock *MaybeKillingBlock = UseInst->getParent();
2194 if (PostOrderNumbers.find(MaybeKillingBlock)->second <
2195 PostOrderNumbers.find(EarlierAccess->getBlock())->second) {
2196
2197 LLVM_DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found killing def " <<
*UseInst << "\n"; } } while (false)
2198 << " ... found killing def " << *UseInst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found killing def " <<
*UseInst << "\n"; } } while (false)
;
2199 KillingDefs.insert(UseInst);
2200 }
2201 }
2202 } else
2203 PushMemUses(UseDef);
2204 }
2205 }
2206
2207 // For accesses to locations visible after the function returns, make sure
2208 // that the location is killed (=overwritten) along all paths from
2209 // EarlierAccess to the exit.
2210 if (!isInvisibleToCallerAfterRet(DefUO)) {
2211 SmallPtrSet<BasicBlock *, 16> KillingBlocks;
2212 for (Instruction *KD : KillingDefs)
2213 KillingBlocks.insert(KD->getParent());
2214 assert(!KillingBlocks.empty() &&((!KillingBlocks.empty() && "Expected at least a single killing block"
) ? static_cast<void> (0) : __assert_fail ("!KillingBlocks.empty() && \"Expected at least a single killing block\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2215, __PRETTY_FUNCTION__))
2215 "Expected at least a single killing block")((!KillingBlocks.empty() && "Expected at least a single killing block"
) ? static_cast<void> (0) : __assert_fail ("!KillingBlocks.empty() && \"Expected at least a single killing block\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2215, __PRETTY_FUNCTION__))
;
2216
2217 // Find the common post-dominator of all killing blocks.
2218 BasicBlock *CommonPred = *KillingBlocks.begin();
2219 for (auto I = std::next(KillingBlocks.begin()), E = KillingBlocks.end();
2220 I != E; I++) {
2221 if (!CommonPred)
2222 break;
2223 CommonPred = PDT.findNearestCommonDominator(CommonPred, *I);
2224 }
2225
2226 // If CommonPred is in the set of killing blocks, just check if it
2227 // post-dominates EarlierAccess.
2228 if (KillingBlocks.count(CommonPred)) {
2229 if (PDT.dominates(CommonPred, EarlierAccess->getBlock()))
2230 return {EarlierAccess};
2231 return None;
2232 }
2233
2234 // If the common post-dominator does not post-dominate EarlierAccess,
2235 // there is a path from EarlierAccess to an exit not going through a
2236 // killing block.
2237 if (PDT.dominates(CommonPred, EarlierAccess->getBlock())) {
2238 SetVector<BasicBlock *> WorkList;
2239
2240 // If CommonPred is null, there are multiple exits from the function.
2241 // They all have to be added to the worklist.
2242 if (CommonPred)
2243 WorkList.insert(CommonPred);
2244 else
2245 for (BasicBlock *R : PDT.roots())
2246 WorkList.insert(R);
2247
2248 NumCFGTries++;
2249 // Check if all paths starting from an exit node go through one of the
2250 // killing blocks before reaching EarlierAccess.
2251 for (unsigned I = 0; I < WorkList.size(); I++) {
2252 NumCFGChecks++;
2253 BasicBlock *Current = WorkList[I];
2254 if (KillingBlocks.count(Current))
2255 continue;
2256 if (Current == EarlierAccess->getBlock())
2257 return None;
2258
2259 // EarlierAccess is reachable from the entry, so we don't have to
2260 // explore unreachable blocks further.
2261 if (!DT.isReachableFromEntry(Current))
2262 continue;
2263
2264 for (BasicBlock *Pred : predecessors(Current))
2265 WorkList.insert(Pred);
2266
2267 if (WorkList.size() >= MemorySSAPathCheckLimit)
2268 return None;
2269 }
2270 NumCFGSuccess++;
2271 return {EarlierAccess};
2272 }
2273 return None;
2274 }
2275
2276 // No aliasing MemoryUses of EarlierAccess found, EarlierAccess is
2277 // potentially dead.
2278 return {EarlierAccess};
2279 }
2280
2281 // Delete dead memory defs
2282 void deleteDeadInstruction(Instruction *SI) {
2283 MemorySSAUpdater Updater(&MSSA);
2284 SmallVector<Instruction *, 32> NowDeadInsts;
2285 NowDeadInsts.push_back(SI);
2286 --NumFastOther;
2287
2288 while (!NowDeadInsts.empty()) {
2289 Instruction *DeadInst = NowDeadInsts.pop_back_val();
2290 ++NumFastOther;
2291
2292 // Try to preserve debug information attached to the dead instruction.
2293 salvageDebugInfo(*DeadInst);
2294 salvageKnowledge(DeadInst);
2295
2296 // Remove the Instruction from MSSA.
2297 if (MemoryAccess *MA = MSSA.getMemoryAccess(DeadInst)) {
2298 if (MemoryDef *MD = dyn_cast<MemoryDef>(MA)) {
2299 SkipStores.insert(MD);
2300 }
2301 Updater.removeMemoryAccess(MA);
2302 }
2303
2304 auto I = IOLs.find(DeadInst->getParent());
2305 if (I != IOLs.end())
2306 I->second.erase(DeadInst);
2307 // Remove its operands
2308 for (Use &O : DeadInst->operands())
2309 if (Instruction *OpI = dyn_cast<Instruction>(O)) {
2310 O = nullptr;
2311 if (isInstructionTriviallyDead(OpI, &TLI))
2312 NowDeadInsts.push_back(OpI);
2313 }
2314
2315 DeadInst->eraseFromParent();
2316 }
2317 }
2318
2319 // Check for any extra throws between SI and NI that block DSE. This only
2320 // checks extra maythrows (those that aren't MemoryDef's). MemoryDef that may
2321 // throw are handled during the walk from one def to the next.
2322 bool mayThrowBetween(Instruction *SI, Instruction *NI,
2323 const Value *SILocUnd) {
2324 // First see if we can ignore it by using the fact that SI is an
2325 // alloca/alloca like object that is not visible to the caller during
2326 // execution of the function.
2327 if (SILocUnd && isInvisibleToCallerBeforeRet(SILocUnd))
2328 return false;
2329
2330 if (SI->getParent() == NI->getParent())
2331 return ThrowingBlocks.count(SI->getParent());
2332 return !ThrowingBlocks.empty();
2333 }
2334
2335 // Check if \p NI acts as a DSE barrier for \p SI. The following instructions
2336 // act as barriers:
2337 // * A memory instruction that may throw and \p SI accesses a non-stack
2338 // object.
2339 // * Atomic stores stronger that monotonic.
2340 bool isDSEBarrier(const Value *SILocUnd, Instruction *NI) {
2341 // If NI may throw it acts as a barrier, unless we are to an alloca/alloca
2342 // like object that does not escape.
2343 if (NI->mayThrow() && !isInvisibleToCallerBeforeRet(SILocUnd))
2344 return true;
2345
2346 // If NI is an atomic load/store stronger than monotonic, do not try to
2347 // eliminate/reorder it.
2348 if (NI->isAtomic()) {
2349 if (auto *LI = dyn_cast<LoadInst>(NI))
2350 return isStrongerThanMonotonic(LI->getOrdering());
2351 if (auto *SI = dyn_cast<StoreInst>(NI))
2352 return isStrongerThanMonotonic(SI->getOrdering());
2353 if (auto *ARMW = dyn_cast<AtomicRMWInst>(NI))
2354 return isStrongerThanMonotonic(ARMW->getOrdering());
2355 if (auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(NI))
2356 return isStrongerThanMonotonic(CmpXchg->getSuccessOrdering()) ||
2357 isStrongerThanMonotonic(CmpXchg->getFailureOrdering());
2358 llvm_unreachable("other instructions should be skipped in MemorySSA")::llvm::llvm_unreachable_internal("other instructions should be skipped in MemorySSA"
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2358)
;
2359 }
2360 return false;
2361 }
2362
2363 /// Eliminate writes to objects that are not visible in the caller and are not
2364 /// accessed before returning from the function.
2365 bool eliminateDeadWritesAtEndOfFunction() {
2366 bool MadeChange = false;
2367 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs at the end of the function\n"
; } } while (false)
2368 dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs at the end of the function\n"
; } } while (false)
2369 << "Trying to eliminate MemoryDefs at the end of the function\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs at the end of the function\n"
; } } while (false)
;
2370 for (int I = MemDefs.size() - 1; I >= 0; I--) {
2371 MemoryDef *Def = MemDefs[I];
2372 if (SkipStores.contains(Def) || !isRemovable(Def->getMemoryInst()))
2373 continue;
2374
2375 Instruction *DefI = Def->getMemoryInst();
2376 SmallVector<const Value *, 4> Pointers;
2377 auto DefLoc = getLocForWriteEx(DefI);
2378 if (!DefLoc)
2379 continue;
2380
2381 // NOTE: Currently eliminating writes at the end of a function is limited
2382 // to MemoryDefs with a single underlying object, to save compile-time. In
2383 // practice it appears the case with multiple underlying objects is very
2384 // uncommon. If it turns out to be important, we can use
2385 // getUnderlyingObjects here instead.
2386 const Value *UO = getUnderlyingObject(DefLoc->Ptr);
2387 if (!UO || !isInvisibleToCallerAfterRet(UO))
2388 continue;
2389
2390 if (isWriteAtEndOfFunction(Def)) {
2391 // See through pointer-to-pointer bitcasts
2392 LLVM_DEBUG(dbgs() << " ... MemoryDef is not accessed until the end "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... MemoryDef is not accessed until the end "
"of the function\n"; } } while (false)
2393 "of the function\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... MemoryDef is not accessed until the end "
"of the function\n"; } } while (false)
;
2394 deleteDeadInstruction(DefI);
2395 ++NumFastStores;
2396 MadeChange = true;
2397 }
2398 }
2399 return MadeChange;
2400 }
2401
2402 /// \returns true if \p Def is a no-op store, either because it
2403 /// directly stores back a loaded value or stores zero to a calloced object.
2404 bool storeIsNoop(MemoryDef *Def, const MemoryLocation &DefLoc,
2405 const Value *DefUO) {
2406 StoreInst *Store = dyn_cast<StoreInst>(Def->getMemoryInst());
2407 if (!Store)
2408 return false;
2409
2410 if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {
2411 if (LoadI->getPointerOperand() == Store->getOperand(1)) {
2412 // Get the defining access for the load.
2413 auto *LoadAccess = MSSA.getMemoryAccess(LoadI)->getDefiningAccess();
2414 // Fast path: the defining accesses are the same.
2415 if (LoadAccess == Def->getDefiningAccess())
2416 return true;
2417
2418 // Look through phi accesses. Recursively scan all phi accesses by
2419 // adding them to a worklist. Bail when we run into a memory def that
2420 // does not match LoadAccess.
2421 SetVector<MemoryAccess *> ToCheck;
2422 MemoryAccess *Current =
2423 MSSA.getWalker()->getClobberingMemoryAccess(Def);
2424 // We don't want to bail when we run into the store memory def. But,
2425 // the phi access may point to it. So, pretend like we've already
2426 // checked it.
2427 ToCheck.insert(Def);
2428 ToCheck.insert(Current);
2429 // Start at current (1) to simulate already having checked Def.
2430 for (unsigned I = 1; I < ToCheck.size(); ++I) {
2431 Current = ToCheck[I];
2432 if (auto PhiAccess = dyn_cast<MemoryPhi>(Current)) {
2433 // Check all the operands.
2434 for (auto &Use : PhiAccess->incoming_values())
2435 ToCheck.insert(cast<MemoryAccess>(&Use));
2436 continue;
2437 }
2438
2439 // If we found a memory def, bail. This happens when we have an
2440 // unrelated write in between an otherwise noop store.
2441 assert(isa<MemoryDef>(Current) &&((isa<MemoryDef>(Current) && "Only MemoryDefs should reach here."
) ? static_cast<void> (0) : __assert_fail ("isa<MemoryDef>(Current) && \"Only MemoryDefs should reach here.\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2442, __PRETTY_FUNCTION__))
2442 "Only MemoryDefs should reach here.")((isa<MemoryDef>(Current) && "Only MemoryDefs should reach here."
) ? static_cast<void> (0) : __assert_fail ("isa<MemoryDef>(Current) && \"Only MemoryDefs should reach here.\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2442, __PRETTY_FUNCTION__))
;
2443 // TODO: Skip no alias MemoryDefs that have no aliasing reads.
2444 // We are searching for the definition of the store's destination.
2445 // So, if that is the same definition as the load, then this is a
2446 // noop. Otherwise, fail.
2447 if (LoadAccess != Current)
2448 return false;
2449 }
2450 return true;
2451 }
2452 }
2453
2454 Constant *StoredConstant = dyn_cast<Constant>(Store->getOperand(0));
2455 if (StoredConstant && StoredConstant->isNullValue()) {
2456 auto *DefUOInst = dyn_cast<Instruction>(DefUO);
2457 if (DefUOInst && isCallocLikeFn(DefUOInst, &TLI)) {
2458 auto *UnderlyingDef = cast<MemoryDef>(MSSA.getMemoryAccess(DefUOInst));
2459 // If UnderlyingDef is the clobbering access of Def, no instructions
2460 // between them can modify the memory location.
2461 auto *ClobberDef =
2462 MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def);
2463 return UnderlyingDef == ClobberDef;
2464 }
2465 }
2466 return false;
2467 }
2468};
2469
2470bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA,
2471 MemorySSA &MSSA, DominatorTree &DT,
2472 PostDominatorTree &PDT,
2473 const TargetLibraryInfo &TLI) {
2474 bool MadeChange = false;
2475
2476 DSEState State = DSEState::get(F, AA, MSSA, DT, PDT, TLI);
2477 // For each store:
2478 for (unsigned I = 0; I < State.MemDefs.size(); I++) {
2479 MemoryDef *KillingDef = State.MemDefs[I];
2480 if (State.SkipStores.count(KillingDef))
2481 continue;
2482 Instruction *SI = KillingDef->getMemoryInst();
2483
2484 Optional<MemoryLocation> MaybeSILoc;
2485 if (State.isMemTerminatorInst(SI))
2486 MaybeSILoc = State.getLocForTerminator(SI).map(
2487 [](const std::pair<MemoryLocation, bool> &P) { return P.first; });
2488 else
2489 MaybeSILoc = State.getLocForWriteEx(SI);
2490
2491 if (!MaybeSILoc) {
2492 LLVM_DEBUG(dbgs() << "Failed to find analyzable write location for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Failed to find analyzable write location for "
<< *SI << "\n"; } } while (false)
2493 << *SI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Failed to find analyzable write location for "
<< *SI << "\n"; } } while (false)
;
2494 continue;
2495 }
2496 MemoryLocation SILoc = *MaybeSILoc;
2497 assert(SILoc.Ptr && "SILoc should not be null")((SILoc.Ptr && "SILoc should not be null") ? static_cast
<void> (0) : __assert_fail ("SILoc.Ptr && \"SILoc should not be null\""
, "/build/llvm-toolchain-snapshot-13~++20210223111116+16ede0956cb1/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2497, __PRETTY_FUNCTION__))
;
2498 const Value *SILocUnd = getUnderlyingObject(SILoc.Ptr);
2499
2500 MemoryAccess *Current = KillingDef;
Value stored to 'Current' during its initialization is never read
2501 LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs killed by "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs killed by "
<< *KillingDef << " (" << *SI << ")\n"
; } } while (false)
2502 << *KillingDef << " (" << *SI << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs killed by "
<< *KillingDef << " (" << *SI << ")\n"
; } } while (false)
;
2503
2504 unsigned ScanLimit = MemorySSAScanLimit;
2505 unsigned WalkerStepLimit = MemorySSAUpwardsStepLimit;
2506 unsigned PartialLimit = MemorySSAPartialStoreLimit;
2507 // Worklist of MemoryAccesses that may be killed by KillingDef.
2508 SetVector<MemoryAccess *> ToCheck;
2509
2510 if (SILocUnd)
2511 ToCheck.insert(KillingDef->getDefiningAccess());
2512
2513 bool Shortend = false;
2514 bool IsMemTerm = State.isMemTerminatorInst(SI);
2515 // Check if MemoryAccesses in the worklist are killed by KillingDef.
2516 for (unsigned I = 0; I < ToCheck.size(); I++) {
2517 Current = ToCheck[I];
2518 if (State.SkipStores.count(Current))
2519 continue;
2520
2521 Optional<MemoryAccess *> Next = State.getDomMemoryDef(
2522 KillingDef, Current, SILoc, SILocUnd, ScanLimit, WalkerStepLimit,
2523 IsMemTerm, PartialLimit);
2524
2525 if (!Next) {
2526 LLVM_DEBUG(dbgs() << " finished walk\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " finished walk\n"; } } while (false
)
;
2527 continue;
2528 }
2529
2530 MemoryAccess *EarlierAccess = *Next;
2531 LLVM_DEBUG(dbgs() << " Checking if we can kill " << *EarlierAccess)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " Checking if we can kill " <<
*EarlierAccess; } } while (false)
;
2532 if (isa<MemoryPhi>(EarlierAccess)) {
2533 LLVM_DEBUG(dbgs() << "\n ... adding incoming values to worklist\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "\n ... adding incoming values to worklist\n"
; } } while (false)
;
2534 for (Value *V : cast<MemoryPhi>(EarlierAccess)->incoming_values()) {
2535 MemoryAccess *IncomingAccess = cast<MemoryAccess>(V);
2536 BasicBlock *IncomingBlock = IncomingAccess->getBlock();
2537 BasicBlock *PhiBlock = EarlierAccess->getBlock();
2538
2539 // We only consider incoming MemoryAccesses that come before the
2540 // MemoryPhi. Otherwise we could discover candidates that do not
2541 // strictly dominate our starting def.
2542 if (State.PostOrderNumbers[IncomingBlock] >
2543 State.PostOrderNumbers[PhiBlock])
2544 ToCheck.insert(IncomingAccess);
2545 }
2546 continue;
2547 }
2548 auto *NextDef = cast<MemoryDef>(EarlierAccess);
2549 Instruction *NI = NextDef->getMemoryInst();
2550 LLVM_DEBUG(dbgs() << " (" << *NI << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " (" << *NI << ")\n"; }
} while (false)
;
2551 ToCheck.insert(NextDef->getDefiningAccess());
2552 NumGetDomMemoryDefPassed++;
2553
2554 if (!DebugCounter::shouldExecute(MemorySSACounter))
2555 continue;
2556
2557 MemoryLocation NILoc = *State.getLocForWriteEx(NI);
2558
2559 if (IsMemTerm) {
2560 const Value *NIUnd = getUnderlyingObject(NILoc.Ptr);
2561 if (SILocUnd != NIUnd)
2562 continue;
2563 LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " << *NIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n DEAD: "
<< *NI << "\n KILLER: " << *SI << '\n'
; } } while (false)
2564 << "\n KILLER: " << *SI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n DEAD: "
<< *NI << "\n KILLER: " << *SI << '\n'
; } } while (false)
;
2565 State.deleteDeadInstruction(NI);
2566 ++NumFastStores;
2567 MadeChange = true;
2568 } else {
2569 // Check if NI overwrites SI.
2570 int64_t InstWriteOffset, DepWriteOffset;
2571 OverwriteResult OR =
2572 isOverwrite(SI, NI, SILoc, NILoc, State.DL, TLI, DepWriteOffset,
2573 InstWriteOffset, State.BatchAA, &F);
2574 if (OR == OW_MaybePartial) {
2575 auto Iter = State.IOLs.insert(
2576 std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
2577 NI->getParent(), InstOverlapIntervalsTy()));
2578 auto &IOL = Iter.first->second;
2579 OR = isPartialOverwrite(SILoc, NILoc, DepWriteOffset, InstWriteOffset,
2580 NI, IOL);
2581 }
2582
2583 if (EnablePartialStoreMerging && OR == OW_PartialEarlierWithFullLater) {
2584 auto *Earlier = dyn_cast<StoreInst>(NI);
2585 auto *Later = dyn_cast<StoreInst>(SI);
2586 // We are re-using tryToMergePartialOverlappingStores, which requires
2587 // Earlier to domiante Later.
2588 // TODO: implement tryToMergeParialOverlappingStores using MemorySSA.
2589 if (Earlier && Later && DT.dominates(Earlier, Later)) {
2590 if (Constant *Merged = tryToMergePartialOverlappingStores(
2591 Earlier, Later, InstWriteOffset, DepWriteOffset, State.DL,
2592 State.BatchAA, &DT)) {
2593
2594 // Update stored value of earlier store to merged constant.
2595 Earlier->setOperand(0, Merged);
2596 ++NumModifiedStores;
2597 MadeChange = true;
2598
2599 Shortend = true;
2600 // Remove later store and remove any outstanding overlap intervals
2601 // for the updated store.
2602 State.deleteDeadInstruction(Later);
2603 auto I = State.IOLs.find(Earlier->getParent());
2604 if (I != State.IOLs.end())
2605 I->second.erase(Earlier);
2606 break;
2607 }
2608 }
2609 }
2610
2611 if (OR == OW_Complete) {
2612 LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " << *NIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n DEAD: "
<< *NI << "\n KILLER: " << *SI << '\n'
; } } while (false)
2613 << "\n KILLER: " << *SI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n DEAD: "
<< *NI << "\n KILLER: " << *SI << '\n'
; } } while (false)
;
2614 State.deleteDeadInstruction(NI);
2615 ++NumFastStores;
2616 MadeChange = true;
2617 }
2618 }
2619 }
2620
2621 // Check if the store is a no-op.
2622 if (!Shortend && isRemovable(SI) &&
2623 State.storeIsNoop(KillingDef, SILoc, SILocUnd)) {
2624 LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n DEAD: " << *SI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove No-Op Store:\n DEAD: "
<< *SI << '\n'; } } while (false)
;
2625 State.deleteDeadInstruction(SI);
2626 NumRedundantStores++;
2627 MadeChange = true;
2628 continue;
2629 }
2630 }
2631
2632 if (EnablePartialOverwriteTracking)
2633 for (auto &KV : State.IOLs)
2634 MadeChange |= removePartiallyOverlappedStores(State.DL, KV.second, TLI);
2635
2636 MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
2637 return MadeChange;
2638}
2639} // end anonymous namespace
2640
2641//===----------------------------------------------------------------------===//
2642// DSE Pass
2643//===----------------------------------------------------------------------===//
2644PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
2645 AliasAnalysis &AA = AM.getResult<AAManager>(F);
2646 const TargetLibraryInfo &TLI = AM.getResult<TargetLibraryAnalysis>(F);
2647 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
2648
2649 bool Changed = false;
2650 if (EnableMemorySSA) {
2651 MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
2652 PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
2653
2654 Changed = eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, PDT, TLI);
2655 } else {
2656 MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);
2657
2658 Changed = eliminateDeadStores(F, &AA, &MD, &DT, &TLI);
2659 }
2660
2661#ifdef LLVM_ENABLE_STATS1
2662 if (AreStatisticsEnabled())
2663 for (auto &I : instructions(F))
2664 NumRemainingStores += isa<StoreInst>(&I);
2665#endif
2666
2667 if (!Changed)
2668 return PreservedAnalyses::all();
2669
2670 PreservedAnalyses PA;
2671 PA.preserveSet<CFGAnalyses>();
2672 PA.preserve<GlobalsAA>();
2673 if (EnableMemorySSA)
2674 PA.preserve<MemorySSAAnalysis>();
2675 else
2676 PA.preserve<MemoryDependenceAnalysis>();
2677 return PA;
2678}
2679
2680namespace {
2681
2682/// A legacy pass for the legacy pass manager that wraps \c DSEPass.
2683class DSELegacyPass : public FunctionPass {
2684public:
2685 static char ID; // Pass identification, replacement for typeid
2686
2687 DSELegacyPass() : FunctionPass(ID) {
2688 initializeDSELegacyPassPass(*PassRegistry::getPassRegistry());
2689 }
2690
2691 bool runOnFunction(Function &F) override {
2692 if (skipFunction(F))
2693 return false;
2694
2695 AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2696 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2697 const TargetLibraryInfo &TLI =
2698 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
2699
2700 bool Changed = false;
2701 if (EnableMemorySSA) {
2702 MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
2703 PostDominatorTree &PDT =
2704 getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
2705
2706 Changed = eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, PDT, TLI);
2707 } else {
2708 MemoryDependenceResults &MD =
2709 getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
2710
2711 Changed = eliminateDeadStores(F, &AA, &MD, &DT, &TLI);
2712 }
2713
2714#ifdef LLVM_ENABLE_STATS1
2715 if (AreStatisticsEnabled())
2716 for (auto &I : instructions(F))
2717 NumRemainingStores += isa<StoreInst>(&I);
2718#endif
2719
2720 return Changed;
2721 }
2722
2723 void getAnalysisUsage(AnalysisUsage &AU) const override {
2724 AU.setPreservesCFG();
2725 AU.addRequired<AAResultsWrapperPass>();
2726 AU.addRequired<TargetLibraryInfoWrapperPass>();
2727 AU.addPreserved<GlobalsAAWrapperPass>();
2728 AU.addRequired<DominatorTreeWrapperPass>();
2729 AU.addPreserved<DominatorTreeWrapperPass>();
2730
2731 if (EnableMemorySSA) {
2732 AU.addRequired<PostDominatorTreeWrapperPass>();
2733 AU.addRequired<MemorySSAWrapperPass>();
2734 AU.addPreserved<PostDominatorTreeWrapperPass>();
2735 AU.addPreserved<MemorySSAWrapperPass>();
2736 } else {
2737 AU.addRequired<MemoryDependenceWrapperPass>();
2738 AU.addPreserved<MemoryDependenceWrapperPass>();
2739 }
2740 }
2741};
2742
2743} // end anonymous namespace
2744
2745char DSELegacyPass::ID = 0;
2746
2747INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,static void *initializeDSELegacyPassPassOnce(PassRegistry &
Registry) {
2748 false)static void *initializeDSELegacyPassPassOnce(PassRegistry &
Registry) {
2749INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
2750INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)initializePostDominatorTreeWrapperPassPass(Registry);
2751INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
2752INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)initializeGlobalsAAWrapperPassPass(Registry);
2753INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)initializeMemorySSAWrapperPassPass(Registry);
2754INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)initializeMemoryDependenceWrapperPassPass(Registry);
2755INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
2756INITIALIZE_PASS_END(DSELegacyPass, "dse", "Dead Store Elimination", false,PassInfo *PI = new PassInfo( "Dead Store Elimination", "dse",
&DSELegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<DSELegacyPass>), false, false); Registry.registerPass(
*PI, true); return PI; } static llvm::once_flag InitializeDSELegacyPassPassFlag
; void llvm::initializeDSELegacyPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeDSELegacyPassPassFlag, initializeDSELegacyPassPassOnce
, std::ref(Registry)); }
2757 false)PassInfo *PI = new PassInfo( "Dead Store Elimination", "dse",
&DSELegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<DSELegacyPass>), false, false); Registry.registerPass(
*PI, true); return PI; } static llvm::once_flag InitializeDSELegacyPassPassFlag
; void llvm::initializeDSELegacyPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeDSELegacyPassPassFlag, initializeDSELegacyPassPassOnce
, std::ref(Registry)); }
2758
2759FunctionPass *llvm::createDeadStoreEliminationPass() {
2760 return new DSELegacyPass();
2761}