Bug Summary

File:llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
Warning:line 2565, column 25
Called C++ object pointer is null

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